УСТРОЙСТВО ГРУППОВОЙ СТРУКТУРЫ ДЛЯ ДЕТЕКТИРОВАНИЯ ГРУПП НУЛЕВЫХ И ЕДИНИЧНЫХ БИТ И ОПРЕДЕЛЕНИЕ ИХ КОЛИЧЕСТВА Российский патент 2019 года по МПК G06F7/74 

ОБЛАСТЬ ТЕХНИКИ

Изобретение относится к области вычислительной техники, в частности к устройствам обработки данных, и может быть использовано для построения средств автоматики и функциональных узлов систем управления, для анализа свойств генераторов псевдослучайных последовательностей двоичных чисел, а также для обработки результатов физических экспериментов.

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

Известны система и способ подсчета начальных нулевых разрядов и подсчета начальных единичных разрядов в цифровом процессоре сигналов (RU №2409837 С2, МПК G06F 7/74, заявлен 27.07.2006, опубликовано 20.01.2011, Бюл. №2) в котором определяется количество разрядов для различных размеров слов данных. В устройстве проводится расширение входных данных знаком до временного шестидесятичетырехразрядного слова данных. При подсчете нулевых разрядов проводится инвертирование разрядов слова. Для подсчета начальных разрядов используется двоичный счетчик.

Недостатком данного устройства является низкое быстродействие, а также подсчет только начальных нулевых разрядов и начальных единичных разрядов в цифровом сигнале.

Известно устройство для определения количества единиц в упорядоченном двоичном числе (RU №2522875, МПК Н03К 21/12, заявлено 24.05.2012, опубликовано 20.07.2014, Бюл. №20), содержащее буферы с тремя состояниями с прямым и инверсным входами разрешения, n разрядов входного двоичного числа, (k+1) разрядов выходного двоичного кода (k=[log₂n] меньшее целое), причем буферы с тремя состояниями объединены в пирамидальную структуру, состоящую из (m-1) ступеней (m=]log₂n[большее целое), и в выходной блок, содержащий k буферов с тремя состояниями с инверсным входом разрешения и k буферов с тремя состояниями с прямым входом разрешения, при этом каждая i-я ступень (i=1, …, (m-1)) содержит (2ⁱ-1) буферов с тремя состояниями с инверсным входом разрешения и 2ⁱ-1 буферов с тремя состояниями с прямым входом разрешения.

Недостатком данного устройства является определение количества единиц в только упорядоченном двоичном числе, а не в группах нулевых и единичных разрядов.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для определения количества единиц (нулей) в двоичном числе (RU №2446442, МПК G06F 7/50, Н03К 21/00, заявлено 11.04.2011, опубликовано 27.03.2012, Бюл. №9), содержащее блок управляемой инверсии, состоящий из n-элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» (n - количество разрядов входного числа), элементы ИЛИ и модули, состоящие из элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, которые объединены в группы, состоящие из ярусов, и объединены в k-каскадов (k=]log₂n[), так, что каждый i-й каскад содержит g(i)=n/2ⁱ групп (i=1, …, k), каждая группа i-го каскада разделена на j ярусов (j=1, …, i), при этом первый ярус каждой группы i-го каскада содержит i модулей, а каждый j-й ярус каждой группы i-го каскада (j=2, …, i,) содержит (i-j) модулей и элемент «ИЛИ».

Недостатком данного устройства является определение только общего количества единиц (нулей) в двоичном числе, а не по группам нулевых и единичных разрядов.

К причинам, препятствующим достижению указанного ниже технического результата, относится отсутствие средств для выявления групп и определения количества нулевых и единичных бит в группах, и определение общего количества групп.

ЗАДАЧА ИЗОБРЕТЕНИЯ

Задачей изобретения является разработка аппаратных средств для исследования свойств генераторов псевдослучайных последовательностей двоичных чисел, а также для обработки результатов физических экспериментов.

При анализе генераторов псевдослучайных последовательностей двоичных чисел устройство предназначено для выявления групп (рядов) подряд идущих единичных и нулевых бит, определение количества бит в группах, общего количества групп и общего количества единичных бит.

При обработке результатов физических экспериментов устройство предназначено для выявления событий (групп единичных бит) и интервалов между событиями (групп нулевых бит), определение их длительности и определение общего количества и длительности событий.

Техническим результатом изобретения является расширение функциональных возможностей в части возможности выявления групп единичных и нулевых бит в двоичных числах, определение количества бит в группах и определение общего количества единичных бит в двоичных числах, а также простое увеличение разрядности входной информации при сокращении аппаратных затрат и увеличение быстродействия устройства.

КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Указанный технический результат при осуществлении изобретения достигается тем, что устройство групповой структуры для детектирования групп нулевых и единичных бит и определение их количества

содержит N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на L групп по М разрядов в группе (N=L*M), Z ступеней блоков элементов, где Z=]log₂L[+1 (] [- большее целое), причем первая ступень содержит L блоков элементов 1₁, 1₂, …, 1_L первого типа, а каждая i-ая ступень, начиная со второй ступени до Z-й ступени, содержит по L/2^(i-1) блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, …, L/2^(i-1),

причем N разрядов входного двоичного числа D1, D2, …, DN группами по М разрядов соединены с входами одноименных входным группам блоков элементов 1₁, 1₂, …, 1_L первого типа первой ступени, выходы нечетных блоков элементов 1₁, 1₃, …, 1_1(L-1)(нч) и выходы четных блоков элементов 1₂, 1₄, …, 1_L(чт) первой ступени попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2₂₁, 2₂₂, …, 2_2L/2 второго типа второй ступени, а выходы нечетных блоков элементов 2ij(нч) и выходы четных блоков элементов 2ij(чт) каждой i-ой ступени, начиная со второй ступени до предпоследней (Z-1)-й ступени, попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2ij последующих ступеней, начиная с третьей ступени до последней Z-й ступени, а выходы групп блока элементов 2zj последней ступени Z являются соответствующими группами Q внешних одноименных выходов устройства группы QK общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, w групп QG нулевых и единичных бит (w=1, 2, …, N+1), причем выходы нечетных групп QG(wнч)⁰ соответствуют группам нулевых бит, а выходы четных групп QG(wчт)¹ соответствуют группам единичных бит, и выход QDL, соответствующий левому биту входного двоичного числа D1,

причем выходная группа QК общего количества групп единичных и нулевых бит и выходная группа QU количества единичных бит во входном двоичном числе D1, D2, …, DN содержат по ]log₂(N+1)[ (большее целое) разрядов, выходные группы нулевых и единичных бит QGw содержат по ]log₂(N+3-w)[ (большее целое) разрядов,

каждый блок элементов 1₁, 1₂, …, 1_L первого типа первой ступени содержит (М-1) каскадов формирователей упорядоченных двоичных чисел 3₁, 3₂, …, 3_(M-1), которые объединены в пирамидальную структуру, причем каждый v-й каскад 3_v (v=1, …, (М-1)) содержит группу из (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v), группу из (M-v) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v), группу из (M+1-v) входов A1, А2, …, A(M+1-v), группу из (M-v) выходов O1, O2, …, O(M-v) в следующий каскад и группу из (M+1-v) выходов разрядов соответствующей v-й внутренней шины Sv из группы S1, S2, …, S(M-1),

а также в каждый блок элементов 1₁, 1₂, …, 1_L первого типа первой ступени введены элемент ИЛИ с одним инверсным входом 6, группа из (М-1) модулей счета младших упорядоченных единиц 7₁, 7₂, …, 7_(M-1), первая группа из М сумматоров 8₁, 8₂, …, 8_M с инверсной группой входов второго слагаемого, модуль счета единиц 9 и второй многогрупповой сумматор 10, причем каждый v-й сумматор 8_v содержит по ]log₂(M+3-v)[ (большее целое) разряда входов слагаемых, а последний М-ый сумматор 8_M содержит по два разряда входов слагаемых,

причем М разрядов каждой из L групп входного двоичного числа D1, D2, …, DN, начиная с первого разряда до М-го разряда, соединены в обратном порядке соответственно с входами AM, АМ-1, …, А1 первых каскадов 3₁ в соответствующих блоках элементов 1₁, 1₂, …, 1_L первого типа первой ступени одноименных группам L,

в каждом v-м каскаде формирователей 3_v первые (M-v) входов A1, А2, …, A(M-v), кроме последнего входа A(M+1-v), соединены со вторыми входами соответствующих одноименных элементов ИЛИ 4₁, 4₂, …, 4_(M-v) и вторыми входами одноименных элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v), а первые входы первых (М-v-1) элементов ИЛИ 4₁, 4₂, …, 4_(M-v-1) из группы элементов ИЛИ, начиная с первого элемента ИЛИ, соединены с выходами соответствующих последующих элементов 4₂, 4₃, …, 4_(M-v) из группы элементов ИЛИ, начиная со второго элемента, первый вход последнего (M-v)-го элемента 4_(M-v) из группы элементов ИЛИ соединен с последним входом A(M+1-v) v-го каскада формирователей 3_v, выходы (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v) соединены также с первыми входами соответствующих одноименных элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v), выходы которых являются группой (M-v) выходов O1, O2, …, O(M-v) в следующий каскад каждого v-го каскада 3_v, а выходы всех (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v) также являются одноименными первыми младшими (M-v) разрядами соответствующей v-й внутренней шины Sv из группы S1, S2, …, S(M-1), начиная с первого разряда, а последний A(M+1-v)-й вход v-го каскада 3_v является старшим (M+1-v)-м разрядом соответствующей v-й внутренней шины Sv,

причем в первых (М-2) каскадах формирователей, кроме последнего (M-1)-го каскада 3_(M-1), (M-v) выходов O1, O2, …, O(M-v) в следующий (v+1)-й каскад 3_(v+1) соединены с соответствующими (M-v) одноименными входами A1, А2, …, A(M-v) следующего (v+1)-го каскада формирователей 3_(v+1), все разряды каждой v-й внутренней шины Sv из группы S1, S2, …, S(M-1), в каждом блоке элементов 1₁, 1₂, …, 1_L первого типа первой ступени, соединены с входами соответствующего одноименного модуля 7_v из группы из (М-1) модулей счета младших упорядоченных единиц, а выходы каждого v-го модуля 7_v соединены с инверсной группой входов второго слагаемого соответствующего v-го сумматора 8_v и первой группой прямых входов первого слагаемого последующего (v+1)-го сумматора 8_(v+1) из первой группы из М сумматоров 8₁, 8₂, …, 8_M, выходы которых являются соответствующими первыми М группами выходных данных единичных и нулевых бит G1, G2, …, GM соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, а последний одноразрядный выход группы единичных и нулевых бит G(M+1), соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, соединен с выходом O1 последнего (М-1) каскада 3_(M-1), который также соединен с входом второй инверсной группы последнего М-го сумматора 8_M и первым прямым входом элемента ИЛИ с одним инверсным входом 6, второй инверсный вход которого соединен со старшим М-ым входом AM первого каскада 3₁ соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, а также является выходом левого бита DL соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа,

кроме того на группу прямых входов первого слагаемого первого сумматора 8₁ подан код двоичного числа «М», а на входы переносов CI всех М сумматоров 8₁, 8₂, …, 8_M подано значение логической единицы «1»,

входы групп второго многогруппового сумматора 10 подключены к выходам всех четных сумматоров 8(чт) в каждом блоке элементов 1₁, 1₂, …, 1_L первого типа, а группа выходов сумматора 10 является выходной группой U количества единичных бит во входных данных соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа,

младшие первые разряды всех (М-1) внутренних шин упорядоченных двоичных чисел S1, S2, …, S(M-1) соединены с соответствующими входами модуля счета единиц 9, у которого М-ый вход соединен с выходом элемента ИЛИ с одним инверсным входом 6, а выходы модуля счета единиц 9 являются выходной группой К общего количества групп единичных и нулевых бит соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, причем группа общего количества групп К содержит ]log₂(M+1)[ (большее целое) разрядов,

причем, каждый блок элементов 2_ij второго типа второй, третьей, …, Z-ой ступени содержит третью группу из (М*2^(i-2)+1) сумматоров 11, четвертый сумматор 12, модуль сдвига групп 13, модуль формирования кода сдвига и кода общего количества групп 14, который содержит первый элемент И с одним инверсным входом 15, второй элемент И с одним инверсным входом 16, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, пятый сумматор 18, шестой сумматор 19, седьмой сумматор 20,

причем в каждом блоке элементов 2_ij второго типа соответствующие (М*2^(i-2)+1) группы входов нулевых и единичных бит 1G первых секций входов соединены с группами входов первых слагаемых соответствующих одноименных сумматоров из третьей группы сумматоров 11, у которых вторые группы входов вторых слагаемых соединены с соответствующими первыми (М*2^(i-2)+1) группами выходов модуля сдвига групп 13, у которого информационные группы входов соединены с соответствующими (М*2^(i-2)+1) группами входов нулевых и единичных бит 2G вторых секций входов блоков элементов 2_ij второго типа, а управляющие входы модуля сдвига групп 13 по шине задания значения количества сдвигов SK подключены к выходам модуля формирования кода сдвига и кода общего количества групп 14,

причем в модуле формирования кода сдвига и кода общего количества групп 14 вход левого бита 1DL первой секции входов соединен с первым прямым входом первого элемента И 15 с одним инверсным входом, со вторым инверсным входом второго элемента И 16 с одним инверсным входом, первым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17 и является выходом левого бита DL соответствующего блока элементов 2_ij, вход левого бита 2DL второй секции входов соединен со вторым инверсным входом первого элемента И 15 с одним инверсным входом, с первым прямым входом второго элемента И 16 с одним инверсным входом и со вторым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, третий вход которого соединен с младшим нулевым разрядом 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции, а также все разряды группы 1К соединены с группой входов второго слагаемого пятого сумматора 18, у которого все разряды первого слагаемого соединены между собой и подключены к выходу элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, группа выходов пятого сумматора 18 соединена с группой входов второго слагаемого шестого сумматора 19 и с группой входов первого слагаемого седьмого сумматора 20, у которого группа входов второго слагаемого соединена с разрядами группы 2К общего количества групп единичных и нулевых бит второй секции, а группа выходов седьмого сумматора 20 является выходной группой К общего количества групп единичных и нулевых бит соответствующего блока элементов 2_ij второго типа,

а также все разряды первого слагаемого шестого сумматора 19 соединены между собой и подключены к выходу второго элемента И с одним инверсным входом 16, а вход переноса CI шестого сумматора 19 соединен с выходом первого элемента И с одним инверсным входом 15, а разряды группы выходов шестого сумматора 19 являются разрядами шины задания значения количества сдвигов SK,

выходы групп количества единичных бит первой секции 1U и второй секции 2U соединены соответственно с группами первого и второго слагаемых четвертого сумматора 12, группа выходов которого является группой выходов U соответствующего блока элементов 2_ij второго типа,

кроме того, в каждом блоке 2_ij второго типа выходы третьей группы сумматоров 11 и вторые группы выходов модуля сдвига групп 13, начиная с группы выходов (М*2^(i-2)+2) до группы выходов (М*2^(i-1)+1), являются выходами соответствующих групп G единичных и нулевых бит соответствующего блока элементов 2_ij второго типа.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

На фиг. 1 представлена структурная схема предлагаемого устройства групповой структуры для детектирования групп нулевых и единичных бит и определение их количества. На фиг. 2 представлена функциональная схема предлагаемого устройства при N=8, М=4, L=2, Z=2. На фиг. 3 приведены форматы выходных данных для N разрядов входных данных и для М=4 и N=8. В таблице 1 приведены примеры формирования значений количества нулевых и единичных бит по группам G1, G2, …, G5 по каскадам и общего количества групп К при N=4 для блоков элементов 1. В таблице 2 приведены примеры формирования значений нечетных групп нулевых бит G1⁰, G3⁰, G5⁰, G7⁰, G9⁰ и четных групп единичных бит G2¹, G4¹, G6¹, G8¹, общего количества (суммы) групп единичных и нулевых бит К, шины задания значения количества сдвигов SK при N=8, М=4, L=2, Z=2 для блоков элементов 2. В таблице 3 приведены значения функций для корректировки кода суммы К количества групп и кода количества сдвига на шине SK.

На фиг. 1, фиг. 2, фиг. 3, в таблицах и в тексте приняты следующие обозначения:

D1, D2, …, DN - N разрядов входного двоичного числа,

L - количество групп разрядов,

М - количество разрядов в группе, причем N=L*M,

Z - количество ступеней, где Z=]log₂L[+1 (] [ - большее целое),

А - входы каскадов блоков элементов 1 первого типа первой ступени,

О - выходы каскадов блоков элементов 1 первого типа первой ступени,

G - группы единичных и нулевых бит,

G⁰ - группы нулевых бит,

G¹ - группы единичных бит,

K - группа общего количества (суммы) групп единичных и нулевых бит,

U - группа количества (сумму) единичных бит,

DL - левый бит,

SM - сумматор,

CI - вход переноса сумматора,

F - модуль счета младших упорядоченных двоичных чисел,

SF - модуль сдвига групп,

SK - шина задания значения количества сдвигов,

S1, S2, …, S(M-1) - (М-1) внутренних шин упорядоченных двоичных чисел,

1G, 1K, 1U, 1DL - группы входов первых секций блоков элементов 2ij,

1k0 - младший нулевой разряд группы 1К общего количества групп единичных и нулевых бит первой секции,

2G, 2K, 2U, 2DL - группы входов вторых секций блоков элементов 2ij,

QG, QK, QU, QDL - группы выходов устройства,

i - номер ступени, где i=2, 3, …, Z,

j - номер блока элементов в i-й ступени, где j=1, 2, …, L/2^(i-1),

v - номер каскада формирователя упорядоченных двоичных чисел блоков первой ступени, v=1, …, (М-1),

1₁, 1₂, …, 1_L - L блоков элементов первого типа первой ступени,

2_ij - блоки элементов второго типа i-й ступени, где i=2, 3, …, Z, j=1, 2, …, L/2^(i-1),

3₁, 3₂, …, 3_(M-1) - (М-1) каскадов формирователя упорядоченных двоичных чисел блоков первой ступени 1,

4 - группы элементов ИЛИ,

5 - группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR),

6 - элемент ИЛИ с одним инверсным входом,

7 - группа из (М-1) модулей счета младших упорядоченных единиц,

8 - первая группа из М сумматоров с инверсной группой входов второго слагаемого,

9 - модуль счета единиц,

10 - второй многогрупповой сумматор,

11 - третья группа из (М*2^(i-2)+1) сумматоров,

12 - четвертый сумматор,

13 - модуль сдвига групп,

14 - модуль формирования кода сдвига и кода общего количества групп,

15 - первый элемент И с одним инверсным входом,

16 - второй элемент И с одним инверсным входом,

17 - элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR),

18 - пятый сумматор,

19 - шестой сумматор,

20 - седьмой сумматор.

Предлагаемое устройство групповой структуры для детектирования групп нулевых и единичных бит и определение их количества содержит N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на L групп по М разрядов в группе (N=L*M), Z ступеней блоков элементов, где Z=]log₂L[+1 (] [ - большее целое), причем первая ступень содержит L блоков элементов 1₁, 1₂, …, 1_L первого типа, а каждая i-ая ступень, начиная со второй ступени до Z-й ступени, содержит по L/2^(i-1) блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, …, L/2^(i-1).

Причем N разрядов входного двоичного числа D1, D2, …, DN группами по М разрядов соединены с входами одноименных входным группам блоков элементов 1₁, 1₂, …, 1_L первого типа первой ступени.

Выходы нечетных блоков элементов 1₁, 1₃, …, 1_1(L-1)(нч) и выходы четных блоков элементов 1₂, 1₄, …, 1_L(чт) первой ступени попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2₂₁, 2₂₂, …, 2_2L/2 второго типа второй ступени.

Выходы нечетных блоков элементов 2ij(нч) и выходы четных блоков элементов 2ij(чт) каждой i-ой ступени, начиная со второй ступени до предпоследней (Z-1)-й ступени, попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2ij последующих ступеней, начиная с третьей ступени до последней Z-й ступени.

Выходы групп блока элементов 2zj последней ступени Z являются соответствующими группами Q внешних одноименных выходов устройства - группы QK общего количества (суммы) групп единичных и нулевых бит, группы QU количества (суммы) единичных бит во входном двоичном числе D1, D2, …, DN, w групп QG нулевых и единичных бит (w=1, 2, …, N+1), причем выходы нечетных групп QG(wнч)⁰ соответствуют группам нулевых бит, а выходы четных групп QG(wчт)¹ соответствуют группам единичных бит, и выход QDL, соответствующий левому биту входного двоичного числа D1. Причем выходная группа QК общего количества групп единичных и нулевых бит и выходная группа QU количества единичных бит во входном двоичном числе D1, D2, …, DN содержат по ]log₂(N+1)[ (большее целое) разрядов, выходные группы нулевых и единичных бит QGw содержат по ]log₂(N+3-w)[ (большее целое) разрядов.

Каждый блок элементов 1₁, 1₂, …, 1_L первого типа первой ступени содержит (М-1) каскадов формирователей упорядоченных двоичных чисел 3₁, 3₂, …, 3_(M-1), которые объединены в пирамидальную структуру, причем каждый v-й каскад 3_v (v=1, …, (М-1)) содержит группу из (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v), группу из (M-v) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v), группу из (M+1-v) входов A1, А2, …, А(М+1-v), группу из (M-v) выходов O1, O2, …, O(M-v) в следующий каскад и группу из (M+1-v) выходов разрядов соответствующей v-й внутренней шины Sv из группы S1, S2, …, S(M-1).

Также в каждый блок элементов 1₁, 1₂, …, 1_L первого типа первой ступени введены элемент ИЛИ с одним инверсным входом 6, группа из (М-1) модулей счета младших упорядоченных единиц 7₁, 7₂, …, 7_(M-1), первая группа из М сумматоров 8₁, 8₂, …, 8_M с инверсной группой входов второго слагаемого, модуль счета единиц 9 и второй многогрупповой сумматор 10, причем каждый v-й сумматор 8_v содержит по ]log₂(M+3-v)[ (большее целое) разряда входов слагаемых, а последний М-ый сумматор 8_M содержит по два разряда входов слагаемых.

Причем М разрядов каждой из L групп входного двоичного числа D1, D2, …, DN, начиная с первого разряда до М-го разряда, соединены в обратном порядке соответственно с входами AM, АМ-1, …, А1 первых каскадов 3₁ в соответствующих блоках элементов 1₁, 1₂, …, 1_L первого типа первой ступени одноименных группам L.

В каждом v-м каскаде формирователей 3_v первые (M-v) входов A1, А2, …, A(M-v), кроме последнего входа A(M+1-v), соединены со вторыми входами соответствующих одноименных элементов ИЛИ 4₁, 4₂, …, 4_(M-v) и вторыми входами одноименных элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v). Первые входы первых (М-v-1) элементов ИЛИ 4₁, 4₂, …, 4_(M-v-1) из группы элементов ИЛИ, начиная с первого элемента ИЛИ, соединены с выходами соответствующих последующих элементов 4₂, 4₃, …, 4_(M-v) из группы элементов ИЛИ, начиная со второго элемента. Первый вход последнего (M-v)-го элемента 4_(M-v) из группы элементов ИЛИ соединен с последним входом A(M+1-v) v-го каскада формирователей 3_v. Выходы (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v) соединены также с первыми входами соответствующих одноименных элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v), выходы которых являются группой (M-v) выходов O1, O2, …, O(M-v) в следующий каскад каждого v-го каскада 3_v. Выходы всех (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v) также являются одноименными первыми младшими (M-v) разрядами соответствующей v-й внутренней шины Sv из группы S1, S2, …, S(M-1), начиная с первого разряда, а последний A(M+1-v)-й вход v-го каскада 3_v является старшим (M+1-v)-м разрядом соответствующей v-й внутренней шины Sv.

Причем в первых (М-2) каскадах формирователей, кроме последнего (M-1)-го каскада 3_(M-1), (M-v) выходов O1, O2, …, O(M-v) в следующий (v+1)-й каскад 3_(v+1) соединены с соответствующими (M-v) одноименными входами A1, А2, …, A(M-v) следующего (v+1)-го каскада формирователей 3_(v+1).

Все разряды каждой v-й внутренней шины Sv из группы S1, S2, …, S(M-1), в каждом блоке элементов 1₁, 1₂, …, 1_L первого типа первой ступени, соединены с входами соответствующего одноименного модуля 7_v из группы из (М-1) модулей счета младших упорядоченных единиц. Выходы каждого v-го модуля 7_v соединены с инверсной группой входов второго слагаемого соответствующего v-го сумматора 8_v и первой группой прямых входов первого слагаемого последующего (v+1)-го сумматора 8_(v+1) из первой группы из М сумматоров 8₁, 8₂, …, 8_M. Выходы сумматоров из первой группы из М сумматоров 8₁, 8₂, …, 8_M являются соответствующими первыми М группами выходных данных единичных и нулевых бит G1, G2, …, GM соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа. Последний одноразрядный выход группы единичных и нулевых бит G(M+1), соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, соединен с выходом O1 последнего (М-1) каскада 3_(M-1), который также соединен с входом второй инверсной группы последнего М-го сумматора 8_M и первым прямым входом элемента ИЛИ с одним инверсным входом 6, второй инверсный вход которого соединен со старшим М-ым входом AM первого каскада 3₁ соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, а также является выходом левого бита DL соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа.

Кроме того на группу прямых входов первого слагаемого первого сумматора 8₁ подан код двоичного числа «М», а на входы переносов CI всех М сумматоров 8₁, 8₂, …, 8_M подано значение логической единицы «1».

Входы групп второго многогруппового сумматора 10 подключены к выходам всех четных сумматоров 8(чт) в каждом блоке элементов 1₁, 1₂, …, 1_L первого типа, а группа выходов сумматора 10 является выходной группой U количества единичных бит во входных данных соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа.

Младшие первые разряды всех (М-1) внутренних шин упорядоченных двоичных чисел S1, S2, …, S(M-1) соединены с соответствующими входами модуля счета единиц 9, у которого М-ый вход соединен с выходом элемента ИЛИ с одним инверсным входом 6. Выходы модуля счета единиц 9 являются выходной группой К общего количества (суммы) групп единичных и нулевых бит соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, причем группа общего количества групп К содержит ]log₂(M+1)[ (большее целое) разрядов.

Причем, каждый блок элементов 2_ij второго типа второй, третьей, …, Z-ой ступени содержит третью группу из (М*2^(i-2)+1) сумматоров 11, четвертый сумматор 12, модуль сдвига групп 13, модуль формирования кода сдвига и кода общего количества групп 14, который содержит первый элемент И с одним инверсным входом 15, второй элемент И с одним инверсным входом 16, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, пятый сумматор 18, шестой сумматор 19, седьмой сумматор 20.

В каждом блоке элементов 2_ij второго типа соответствующие (М*2^(1-2)+1) группы входов нулевых и единичных бит 1G первых секций входов соединены с группами входов первых слагаемых соответствующих одноименных сумматоров из третьей группы сумматоров 11, у которых вторые группы входов вторых слагаемых соединены с соответствующими первыми (М*2^(i-2)+1) группами выходов модуля сдвига групп 13. Информационные группы входов модуля сдвига групп 13 соединены с соответствующими (М*2^(i-2)+1) группами входов нулевых и единичных бит 2G вторых секций входов блоков элементов 2_ij второго типа, а управляющие входы модуля сдвига групп 13 по шине задания значения количества сдвигов SK подключены к выходам модуля формирования кода сдвига и кода общего количества групп 14.

Причем в модуле формирования кода сдвига и кода общего количества групп 14 вход левого бита 1DL первой секции входов соединен с первым прямым входом первого элемента И 15 с одним инверсным входом, со вторым инверсным входом второго элемента И 16 с одним инверсным входом, первым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17 и является выходом левого бита DL соответствующего блока элементов 2_ij. Вход левого бита 2DL второй секции входов соединен со вторым инверсным входом первого элемента И 15 с одним инверсным входом, с первым прямым входом второго элемента И 16 с одним инверсным входом и со вторым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, третий вход которого соединен с младшим нулевым разрядом 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции. Также все разряды группы 1К соединены с группой входов второго слагаемого пятого сумматора 18, у которого все разряды первого слагаемого соединены между собой и подключены к выходу элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17. Группа выходов пятого сумматора 18 соединена с группой входов второго слагаемого шестого сумматора 19 и с группой входов первого слагаемого седьмого сумматора 20, у которого группа входов второго слагаемого соединена с разрядами группы 2К общего количества групп единичных и нулевых бит второй секции. Группа выходов седьмого сумматора 20 является выходной группой К общего количества (суммы) групп единичных и нулевых бит соответствующего блока элементов 2_ij второго типа.

Все разряды первого слагаемого шестого сумматора 19 соединены между собой и подключены к выходу второго элемента И с одним инверсным входом 16, а вход переноса CI шестого сумматора 19 соединен с выходом первого элемента И с одним инверсным входом 15. Разряды группы выходов шестого сумматора 19 являются разрядами шины задания значения количества сдвигов SK.

Выходы групп количества (суммы) единичных бит первой секции 1U и второй секции 2U соединены соответственно с группами первого и второго слагаемых четвертого сумматора 12, группа выходов которого является группой выходов U соответствующего блока элементов 2_ij второго типа.

В каждом блоке 2_ij второго типа выходы третьей группы сумматоров 11 и вторые группы выходов модуля сдвига групп 13, начиная с группы выходов (М*2^(i-2)+2) до группы выходов (М*2^(i-1)+1), являются выходами соответствующих групп G единичных и нулевых бит соответствующего блока элементов 2_ij второго типа.

ПОДРОБНОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Принцип работы предлагаемого устройства состоит в следующем.

Входное N разрядное двоичное число без знака разбивается на L групп по М разрядов в группе (N=L*M) и поступает на соответствующие L одноименных блоков элементов 1₁, 1₂, …, 1_L первого типа первой ступени.

В блоках элементов 1₁, 1₂, …, 1_L первого типа первой ступени в каскадах формирователей 3₁, 3₂, …, 3_(M-1) группы входных данных А преобразуются в цепочках групп элементов ИЛИ 4₁, 4₂, …, 4_(M-v), в группы упорядоченных двоичных кодов «00…011…1» с единицами расположенными подряд, начиная с младших разрядов, где левая единица соответствует старшей единице в соответствующей группе входных данных, и устанавливаются на выходах групп элементов ИЛИ 4₁, 4₂, …, 4_(M-v), а также совместно с соответствующим старшим входным разрядом A(M+1-v) v-го каскада формирователей 3_v передаются на внутренние шины S1, S2, …, S(M-1).

В группах элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v), которые можно рассматривать как элементы «управляемый инвертор», инвертируются младшие разряды групп входных данных А, соответствующие единичным значениям в упорядоченном двоичном коде «00…011…1» на выходах группы элементов ИЛИ 4₁, 4₂, …, 4_(M-v). При этом старшие нулевые разряды групп входных данных А не изменяются и остаются нулевыми, а разряды левой старшей группы единичных бит входных данных А, соответствующие единичным значениям упорядоченного двоичного кода «00…011…1», инвертируются и принимают нулевые значения. Значения с выходов, соответствующих групп элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-v), поступают на выходы O1, O2, …, O(M-v) соответствующих каскадов формирователей 3_v.

Подсчет количества единичных разрядов в шинах S1, S2, …, S(M-1) осуществляется в группе модулей 7₁, 7₂, …, 7_(M-1) счета младших упорядоченных единиц. Сумма количества единиц на выходах модулей 7_v является дополнением до М к количеству старших нулей в группах входных данных А соответствующих каскадов формирователей 3_v. Значения сумм количества единиц поступают на инверсные входы вторых слагаемых одноименных сумматоров 8₁, 8₂, …, 8_(M-1) и прямые входы первых слагаемых последующих сумматоров 8₂, 8₃, …, 8_M, на которых выполняется вычисление количества нулевых или единичных бит в соответствующих группах G, так как дополнения до М в соседних каскадах отличаются на количество бит в группах нулевых или единичных бит.

В таблице 1 приведены примеры формирования значений количества нулевых и единичных бит по группам G1, G2, …, G5 каскадов и общего количества групп К при N=4 для блоков элементов 1. При этом в нечетных группах G(нч)⁰ формируются коды соответствующие количеству нулевых бит в группах, а в четных группах G(чт)¹ формируются коды соответствующие количеству единичных бит в группах. В первой группе бит G1⁰ всегда формируется код для группы нулевых бит, а если левый старший разряд в группе принимает единичное значение АМ=1, то код суммы бит первой группы принимает нулевое значение G1⁰=0.

Одновременно в модулях 9 счета единиц осуществляется подсчет количества (суммы) единичных значений в младших разрядах всех внутренних шин из группы S1, S2, …, S_(M-1) и на выходе элемента ИЛИ 6, что соответствует общему количеству К групп нулевых и единичных бит.Также на вторых многогрупповых сумматорах 10 вычисляется общее количество U единичных бит во входных данных соответствующего блока элементов 1.

Далее значения кодов по группам с выходов нечетных блоков элементов 1₁, 1₃, …, 1_1(L-1)(нч) и с выходов четных блоков элементов 1₁, 1₂, …, 1_L(чт) первой ступени попарно передаются на одноименные группы входов соответственно первых и вторых секций входов блоков 2₂₁, 2₂₂, …, 2_2L/2 второй ступени. Затем значения с выходов нечетных блоков элементов 2ij(нч) и с выходов четных блоков элементов 2ij(чт) каждой i-ой ступени, начиная со второй ступени до предпоследней (Z-1)-й ступени, попарно передаются на соответствующие группы одноименных входов соответственно первых и вторых секций входов блоков элементов 2 последующих ступеней, начиная с третьей ступени до последней Z-й ступени. На фиг. 1 представлена структурная схема объединения блоков элементов ступеней.

В каждом блоке элементов 2_ij второго типа проводится объединение значений групп входов нулевых и единичных бит первых 1G и вторых 2G секций. Для объединения групп, в зависимости от значений входов старших левых разрядов секций 1DL и 2DL и значения младшего нулевого разряда 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции, в модулях 14 проводится формирование значения кода сдвига SK и в модулях сдвига групп 13 осуществляется сдвиг групп нулевых и единичных бит вторых 2G секций на четное количество групп SK. Далее на третьей группе сумматоров 11 осуществляется объединение групп и формирование групп нулевых и единичных бит G для двух секций. В таблице 2 приведены примеры формирования значений нечетных групп нулевых бит G1⁰, G3⁰, G5⁰, G7⁰, G9⁰ и четных групп единичных бит G2¹, G4¹, G6¹, G8¹, общего количества (суммы) групп единичных и нулевых бит К, шины задания значения количества сдвигов SK при N=8, М=4, L=2, Z=2 для блоков элементов 2. При этом группы G1-G5 формируются на выходах третьей группы сумматоров 11, а группы G6-G9 формируются на выходах модуля сдвига 13. В таблице 3 приведены значения функций (-1 и +1), формируемые на выходах элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, первого 15 и второго 16 элементов И с одним инверсным входом, для корректировки кода суммы количества групп (2К+1К) и кода количества сдвигов на шине SK.

Выходы групп последней ступени Z являются соответствующими группами Q внешних одноименных выходов устройства - группы QK общего количества (суммы) групп единичных и нулевых бит, группы QU количества (суммы) единичных бит во входном двоичном числе D1, D2, …, DN, w групп QG нулевых и единичных бит (w=1, 2, …, N+1), причем выходы нечетных групп QG(wнч)⁰ соответствуют группам нулевых бит, а выходы четных групп QG(wчт)¹ соответствуют группам единичных бит, и выход QDL, соответствующий левому биту входного двоичного числа D1. На фиг. 3 приведены форматы выходных данных для N разрядов входных данных и для М=4 и N=8.

Предлагаемое устройство работает следующим образом.

На входы устройства поступает N разрядов входного двоичного числа без знака D1, D2, …, DN, которые разделены на L групп по М разрядов в группе (N=L*M). Младший разряд D1 является левым старшим разрядом входного двоичного числа. Причем М разрядов каждой из L групп входного двоичного числа D1, D2, …, DN, начиная с первого разряда до М-го разряда, соединены в обратном порядке соответственно с входами AM, АМ-1, …, А1 первых каскадов 3₁ в соответствующих блоках элементов 1₁, 1₂, …, 1_L первого типа первой ступени одноименных группам L.

В первых каскадах формирователей 3₁ в соответствующих блоках элементов 1₁, 1₂, …, 1_L в каждой соответствующей М разрядной группе входных данных A1, А2, …, AM детектируется старший единичный бит и на выходах группы элементов ИЛИ 4₁, 4₂, …, 4_(M-1), объединенных в цепочку, входные данные A1, А2, …, AM преобразуются в упорядоченный двоичный код «00…011…1» с единицами расположенными подряд, начиная с младших разрядов, где левая единица соответствует старшей единице в соответствующей группе входных данных. Одновременно упорядоченный двоичный код «00…011…1» совместно со старшим входным разрядом AM формирователя первого каскада 3₁ поступают на внутреннюю шину S₁.

Далее в модулях 7₁ счета младших упорядоченных единиц проводится подсчет количества единиц на внутренней шине S₁. Количество единиц является дополнением до М к количеству старших нулей в группе входных данных A1, А2, …, AM. Полученное количество единиц поступает на вторую инверсную группу второго слагаемого первого сумматора 8₁ и вычитается из количества разрядов М группы входных данных, заданном двоичным кодом «М» на входах первого слагаемого, при единичном значении на входе переноса CI=1 сумматора, что соответствует операции вычитания для чисел без знака. При этом полученная разность на выходах первых сумматоров 8₁ соответствует количеству (сумме) нулевых бит в первой группе G1⁰ в соответствующей группе входного двоичного числа D1, D2, …, DN. Вычисленное значение кода количества (суммы) нулевых бит в первой группе G1⁰ поступает на выходы первой группы G1 соответствующих блоков элементов 1₁, 1₂, …, 1_L.

Например, для блоков элементов 1₁, 1₂, …, 1_L в таблице 1 при М=4 для входного числа А4-А1=0010 на выходах элементов ИЛИ 4₁, 4₂, 4₃ первого каскада 3₁ формируется упорядоченный двоичный код «011», который совместно со старшим разрядом А4=0 входных данных поступает на первую внутреннюю шину S1 и в модуле 7₁ вычисляется код «2» суммы младших единиц. Далее этот код «2» поступает на инверсные входы первого сумматора 8₁ и вычитается из кода «4» количества разрядов М=4 входного числа (4-2). Таким образом, на выходах первой «нулевой» группы G1⁰ будет сформирован код «2» (G1⁰=2), соответствующий количеству первых старших нулей в группе входных данных А4-А1.

Одновременно в первых каскадах формирователей 3₁ младшие разряды групп входных данных А4-А1, соответствующих групп входного двоичного числа D1, D2, …, D(N-1), соответствующие единичным значениям в упорядоченном двоичном коде «00…011…1» на выходах группы элементов ИЛИ 4₁, 4₂, …, 4_(M-1), инвертируются в группе элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, …, 5_(M-1), которые можно рассматривать как элементы «управляемый инвертор», и поступают на выходы O1, O2, …, O(М-1) первого каскада формирователей 3₁ и далее на входы A1, А2, …, А(М-2) следующего второго каскада 3₂. При этом разряды первой группы единичных бит G2¹, соответствующей группы входного двоичного числа A1, А2, …, AM, преобразуются в нулевые значения, а разряды второй группы нулевых бит (третья группа во входном числе G3⁰) преобразуются в единичные значения и т.д. Например, в таблице 1 в группе элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR) 5₁, 5₂, 5₃ (при М=4) первого каскада 3₁ инвертируются два младших разряда, и формируется код «001» (для входных данных А4-А1=0010), который поступает на соответствующие выходы O3, O2, O1 и далее на входы A3, А2, А1 второго каскада 3₂.

Во вторых каскадах формирователей 3₂, аналогично первым каскадам 3₁, детектируется старший единичный бит и формируется упорядоченный двоичный код «00…011…1», который поступает на внутреннюю шину S₂, где левая единица соответствует старшей единице - началу третьей группы (третья группа содержит нулевые бит) в группах входного двоичного числа D1, D2, …, DN, а количество нулей в упорядоченном двоичном коде «00…011…1» соответствует сумме двух групп - первой группы нулевых бит и второй группы единичных бит, в соответствующей группе входного двоичного числа D1, D2, …, DN. Во вторых модулях 7₂ счета младших упорядоченных единиц аналогично проводится подсчет количества единиц. Полученный код количества (суммы) единиц, с выходов вторых модулей 7₂, поступает на вторую инверсную группу второго слагаемого вторых сумматорах 8₂, и вычитается из кода «М» уменьшенного на количество (сумму) нулевых бит в первой группе, которое поступает с выходов первого модуля 7₁ счета младших упорядоченных единиц на входы первого слагаемого вторых сумматора 8₂ и далее на выходах вторых сумматоров 8₂ формируются значения, соответствующие количеству (сумме) единиц во второй группе единичных бит G2¹ соответствующих групп входного двоичного числа D1, D2, …, DN, которое поступает на выходы второй группы G2 соответствующих блоков элементов 1₁, 1₂, …, 1_L. Далее аналогично в группе элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5 инвертируются младшие разряды групп входных данных А второго каскада 3₂, которые поступают на выходы O1, O2, …, O(М-2) второго каскада.

Например, в таблице 1 во втором каскаде 3₂ на выходах элементов ИЛИ 4₁, 4₂ (при М=4) формируется упорядоченный двоичный код «01», который совместно со значением старшего разряда А3=0 поступают на внутреннюю шину S₂. Затем во втором модуле 7₂ вычисляется код суммы единиц «1» и далее на втором сумматоре 8₂ формируется код «1», как разность (2-1), соответствующий количеству единиц в первой группе во входной группе данных А, и который поступает на выходы второй «единичной» группы G2¹=1. Затем в группе элементов ИСКЛЮЧАЮЩЕЕ ИЛИ XOR 5₁, 5₂ (при М=4) второго каскада 3₂ инвертируются младшие разряды, и формируется код «00», который поступает на соответствующие выходы O1, O2 и далее на входы A1, А2 третьего каскада 3₃.

Затем аналогично проводится детектирование старших единичных бит, вычисление и формирование кодов значений количества бит в третьем 3₃, четвертом 3₄ и последующих каскадах формирователей. Если во входных данных в каскадах формирователей 3 отсутствуют единичные бит, то в разрядах соответствующих старших групп формируются нулевые значения.

Например, в таблице 1 (при М=4 для входных данных А4-А1=0010) в третьем каскаде 3₃ аналогично формируется упорядоченный двоичный код «0» на выходе элемента ИЛИ 4₁, который поступает на внутреннюю шину S₃, далее в третьем модуле 7₃ вычисляется код суммы единиц «0» и далее на третьем сумматоре 8₃ формируется код «1» как разность (1-0), соответствующий количеству нулей во второй группе бит во входной группе данных. Таким образом, на выходах второй «нулевой» группы G3⁰ будет сформирован код «1» (G3⁰=1), соответствующий количеству нулевых бит в третьей группе во входном числе. Далее так как на выходах каскада отсутствуют единичные бит, то нулевые коды формируются в следующих четвертой и пятой группах G4¹⁼0 и G5⁰=0.

Одновременно выход O1 последнего (М-1) каскада формирователей 3_(M-1) поступает на первый прямой вход элемента ИЛИ с одним инверсным входом 6, на второй инверсный вход которого поступает значение старшего М-го разряда AM входного кода соответствующего блок элементов 1. Таким образом на выходе элемента ИЛИ 6 формируется единичное значение при нулевом значении старшего разряда АМ=0 или при единичном значении на выходе O1 последнего (М-1) каскада 3_(M-1).

Кроме того, одновременно в блоках элементов 1₁, 1₂, …, 1_L младшие первые разряды всех внутренних шин из группы S1, S2, …, S_(M-1) и выходы элементов ИЛИ 6 поступают на соответствующие входы модуля 9 счета единиц, в котором проводится подсчет количества единиц, и это значение соответствует общему количеству групп нулевых и единичных бит в соответствующей группе входных данных А4-А1 входного двоичного числа D1, D2, …, DN, и это значение поступает на выходную группу К соответствующего блока элементов 1₁, 1₂, …, 1_L.

Например, в таблице 1 (при М=4 для входных данных А4-А1=0010) младшие разряды внутренних шин S₁, S₂, S₃, на которых установлены значения «110», и инверсное значение старшего разряда А4 (AM) входной группы данных (единичное значение для входных данных 0010) с выхода элемента ИЛИ 6 поступают на входы модуля 9 счета единиц, в котором будет сформирован код «3» соответствующий общему количеству (сумме) групп нулевых и единичных бит для входного двоичного числа А4-А1=0010, который поступает в выходную группу К=3. При этом также в группах бит будут установлены значения: G1⁰=2, G2¹=1, G3⁰=1, G4¹=0 и G5⁰=0.

Аналогично для входного двоичного числа D1-D4=0101 (таблица 1), при нулевом значении старшего разряда А4=0 (AM) входных данных, формируются значения нулевых и единичных бит G1⁰=1, G2¹=1, G3⁰=1, G4¹=1, G5⁰=0 и общее количество групп К=4, соответствующее максимальному количеству групп при количестве разрядов М=4 входной группы данных.

В таблице 1 для входной группы данных «все нули» А4-А1=0000 на выходах элементов ИЛИ 4₁, 4₂, 4₃ первого каскада 3₁ формируется также «нулевой» упорядоченный двоичный код «000», и далее также формируется «нулевой» код суммы «0» младших единиц в модуле 7₁ (при этом также А4=0), который поступает на инверсные входы первого сумматора 8₁ и вычитается из кода «4» для количества разрядов М=4 входного числа (4-0). Таким образом, на выходах первой «нулевой» группы G1⁰ будет сформирован код «4» (G1⁰=4), соответствующий количеству всех нулевых разрядов во входном числе А4-А1=0000. При этом нулевые значения также будут установлены на всех внутренних шинах S1, S2, S3, в том числе, и на младших первых разрядах шин, которые поступают на входы модуля 9 счета единиц, на который также поступает единичное значение с выхода элемента ИЛИ 6 с одним инверсным входом, который соединен со старшим разрядом входных данных А4=0, и поэтому на выходах модуля 9 будет сформирован код «1», который поступает на выходы общего количества групп К=1.

Для входной группы данных А4-А1=1ХХХ, при единичном значении старшего разряда A4=1 (AM) входных данных (X - любое значение), на выходах элементов ИЛИ 4₁, 4₂, 4₃ первого каскада 3₁ всегда формируется упорядоченный двоичный код все единицы «111», для которого совместно с А4=1 вычисляется код суммы «4» младших единиц в модуле 7₁, который поступает на инверсные входы первого сумматора 8₁ и вычитается из кода «4» количества разрядов М=4 входной группы данных числа (4-4). При этом на выходах первой «нулевой» группы G1⁰ будет сформирован код «0» (G1⁰=0), что соответствует отсутствию старшей «нулевой» группы во входных данных, когда старший разряд имеет единичное значение А4=1.

Например, в таблице 1 для входной группы данных D1-D4=1010, так как на выходах элементов ИЛИ 4₁, 4₂, 4₃ первого каскада 3₁ установлен упорядоченный двоичный код все единицы «111», то в группе элементов XOR 5₁, 5₂, 5₃ первого каскада 3₁ инвертируются все разряды, и формируется код «101», который поступает на соответствующие выходы O1, O2, O3 и далее на входы A1, А2, A3 второго каскада 3₂.

Во втором каскаде 3₂ на выходах элементов ИЛИ 4₁, 4₂ формируется упорядоченный двоичный код «11», который совместно со значением старшего разряда А3=1 поступают на внутреннюю шину S₂. Затем во втором модуле 7₂ вычисляется код суммы единиц «3» и далее на втором сумматоре 8₂ формируется код «1» как разность (4-3), соответствующий количеству единичных бит в первой группе во входной группе данных, и который поступает на выходы второй «единичной» группы G2¹=1. Далее аналогично вычисляются последующие значения нулевых и единичных групп и на выходах групп блока элементов 1 устанавливаются значения G1⁰=0, G2¹=1, G3⁰=1, G4¹=1, G5⁰=1. Одновременно единичные значения с младших разрядов всех внутренних шинах S1, S2, S3 и с выхода элемента ИЛИ 6 с одним инверсным входом (так как единичное значение установлено на выходе O1 третьего каскада 3₃) поступают на входы модуля 9 счета единиц и формируется код «4» общего количества групп К=4.

Для входного двоичного числа «все единицы» А4-А1=1111 на выходах элементов ИЛИ 4₁, 4₂, 4₃ первого каскада 3₁ формируется также упорядоченный двоичный код «111» и на внутренней шине S1 код «все единицы» «1111», для которого формируется код суммы «4» младших единиц в модуле 7₁ (так как при этом А4=1), который поступает на инверсные входы первого сумматора 8₁ и вычитается из кода количества разрядов М=4 входного числа (4-4). Таким образом, на выходах первой «нулевой» группы G1⁰ будет сформирован код «0» (G1⁰=0), что соответствует отсутствию «нулевой» первой группы во входном числе. Далее в группе элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5₁, 5₂, 5₃ (при М=4) первого каскада 3₁ инвертируются все младшие разряды, и формируется код «000», который поступает на соответствующие выходы O1, O2, O3 и далее на входы A1, А2, A3 второго каскада 3₂. Затем во втором каскаде 3₂ на выходах элементов ИЛИ 4₁, 4₂ формируется двоичный код «00», который поступает на внутреннюю шину S₂. Затем во втором модуле 7₂ вычисляется код суммы единиц «0», который вычитается из кода «4» с первого модуля 7₁ (4-0) и формируется код «4» соответствующий количеству единичных бит в группе, который поступает на выходы второй «единичной» группы G2¹=4. Одновременно единичное значение с младшего разряда первой внутренней шины S₁ и нулевое значение с выхода элемента ИЛИ 6 поступают на вход модуля 9 счета единиц и формируется код «1» общего количества групп К=1.

Кроме того, одновременно в каждом блоке элементов 1 на входы групп второго многогруппового сумматора 10 поступают значения с выходов всех четных сумматоров 8(чт), в которых сформированы коды соответствующие группам единичных бит, а группа выходов сумматора 10 является выходной группой U количества (суммы) единичных бит в соответствующей группе входных данных соответствующего блока элементов 1. Также на выход DL, каждого блока элементов 1₁, 1₃, …, 1_L, передается значение с левого старшего разряда входа AM соответствующего блока элементов 1.

Далее значения с выходов нечетных блоков элементов 1₁, 1₃, …, 1_1(L-1)(нч) и выходов четных блоков элементов 1₁, 1₂, …, 1_L(чт) первой ступени попарно поступают на соответствующие группы одноименных входов соответственно первых и вторых секций входов соответствующих блоков 2₂₁, 2₂₂, …, 2_2L/2 второй ступени (фиг. 1).

В каждом блоке элементов 2_ij второго типа, в модулях формирования кода сдвига и кода общего количества групп 14 на основании значений левых старших разрядов 1DL первой секции и 2DL второй секции и значения младшего нулевого разряда 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции, проводится формирование значения кода сдвига SK. При этом значение кода сдвига SK всегда принимает четное значении, т.е. в модуле сдвига групп 13 осуществляется сдвиг на четное количество групп. Формирование кода SK осуществляется на основании таблицы 2 и в соответствии с таблицей 3. На основе таблицы 3 после минимизации для функций корректировки (-1 и +1) кода суммы количества групп (2К+1К) и кода количества сдвига на шине SK получены следующие выражения:

Q17 (-1)=1DL xor 1k0 xor 2DL,

Q16 (-1)=not 1DL and 2DL,

Q15(+1)=not 2DL and 1DL.

Далее на пятом сумматоре 18 формируется значение соответствующее коду 1К общего количества (суммы) групп единичных и нулевых бит в первой секции уменьшенное на единицу, когда сумма по модулю два значений 1DL, 2DL и 1k0 на выходе элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17 принимает единичное значение. На шестом сумматоре 19, в соответствии со значениями, устанавливаемыми на выходах пятого сумматора 18, первого 15 и второго 16 элементов И с одним инверсным входом, осуществляется формирование соответствующего кода сдвига SK на 1Кчт, (1Кчт-2), (1Кнч-1)чт, (1Кнч+1)чт групп разрядов (таблица 3).

В каждом блоке элементов 2_ij второго типа значения с соответствующих групп входов нулевых и единичных бит 1G первых секций входов блоков элементов 2_ij второго типа поступают на группы входов первых слагаемых соответствующих одноименных сумматоров из третьей группы сумматоров 11, у которых на вторые группы входов поступают значения с соответствующих первых (М*2^(i-2)+1) групп выходов модуля сдвига групп 13, в котором значения соответствующих групп входов нулевых и единичных бит 2G вторых секций входов блоков элементов 2_ij второго типа сдвинуты на четное количество групп соответствующее коду SK, которое формируется на выходах модуля 14. Сдвиг осуществляется как логический сдвиг вправо в сторону старших групп G, с вводом нулевых значений в разряды левых младших групп G (таблица 2).

Значения с выходов групп третьей группы сумматоров 11 являются соответствующими первыми (М*2^(i-2)+1) группами выходами нулевых и единичных бит G соответствующего блока элементов 2_ij второго типа. При этом выходы групп модуля сдвига 13, с группы выходов (М*2^(i-2)+2) до группы выходов (М*2^(i-1)+1), являются выходами соответствующих групп G единичных G¹ и нулевых бит G⁰, с группы выходов (М*2^(i-2)+2) до группы выходов (М*2^(i-1)+1), соответствующего блока элементов 2_ij второго типа.

Кроме того, на входы первого и второго слагаемых четвертого сумматора 12 поступают значения с входов количества единичных бит первой секции 1U и второй секции 2U и на выходе четвертого сумматора 12 формируется количество (сумма) единичных бит в двух соответствующих блоках элементов, которое передается на соответствующую группу U выходов блока элементов 2_ij.

На группу входов первого слагаемого седьмого сумматора 20 с выходов пятого сумматора 18 поступает значение кода общего количества групп единичных и нулевых бит 1К с входов первой секции, с учетом коррекции на сдвиг групп второй секции (таблица 2), а на группу входов второго слагаемого седьмого сумматора 20 поступает значение кода общего количества групп единичных и нулевых бит 2К с входов второй секции и на выходах седьмого сумматора 20 формируется код суммы общего количества групп единичных и нулевых бит для двух секций, который поступает на соответствующую группу К выходов блока элементов 2_ij.

Выходы групп последней ступени Z являются соответствующими группами Q внешних одноименных выходов устройства - группы QK общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, w групп QG нулевых и единичных бит (w=1, 2, …, N+1), причем выходы нечетных групп QG(wнч)⁰ соответствуют группам нулевых бит, а выходы четных групп QG(wчт)¹ соответствуют группам единичных бит, и выход QDL, соответствующий левому биту входного двоичного числа D1.

Форматы выходных данных приведены на фиг. 3. Общее количество групп единичных и нулевых бит w равно (N+1). При этом в выходных данных первая группа G1⁰ и последующие нечетные группы содержат количество бит в «нулевых» группах, а вторая группа G2¹ и последующие четные группы содержат количество бит в «единичных» группах. Количество разрядов в каждой группе единичных и нулевых бит равно ]log₂(N+3-w)[ (большее целое), где w=1, 2, …, N+1. Общее количество (сумма) групп К содержит ]log₂(N+1)[ разрядов. Количество (сумма) единичных бит U содержит ]log₂(N+1)[ разрядов.

Рассмотрим работу устройства для входных данных D1-D8=0010 0101, при N=8, М=4, L=2, Z=2. На входы блока элементов 1₁ поступает группа данных 0010 и на входы блока элементов 1₂ поступает группа данных 0101. В соответствии с таблицей 1 для данных групп входных данных формируются соответствующие группы выходов, которые поступают на группы входов блока элементов 2₁.

На входы блока элементов 2₁ поступят следующие значения кодов:

- на первую секцию с выходов блока элементов 1₁ - 1G1⁰=2, 1G2¹=1, 1G3⁰=1, 1G4¹=0, 1G5⁰=0, 1К=3, 1U=1, 1DL=0,

- на вторую секцию с выходов блока элементов 1₂ - 2G1⁰=1, 2G2¹=1, 2G3⁰=1, 2G4¹=1, 2G5⁰=0, 2К=4, 2U=2, 2DL=0.

Из входных данных следует, что в первой секции три группы бит 1К=3 и третья группа (правая) 1G3⁰ является группой нулевых бит, а во второй секции четыре группы бит 2К=4 и первая группа (левая) 2G1⁰ также является группой нулевых бит. Так как в первой секции три группы бит 1К=3„ то младший разряд 1k0=1 принимает единичное значение, а также левые разряды 1DL=0 и 2DL=0 в двух секциях принимают нулевые значения, то в соответствии с таблицами 2 и 3 в модуле 14 формируются код коррекции «-1» (единичное значение на выходе элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17), значение кода сдвига SK=1К-1=2 (шестой сумматор 19) и значение общего количества (суммы) групп К=2К+1К-1=4+3-1=6 (седьмой сумматор 20). Поэтому в модуле сдвига 13 осуществляется сдвиг всех групп единичных и нулевых бит второй секции на две группы SK=2 и вводом нулевых значений в разряды двух первых левых групп 0(2G1⁰) и 0(2G2¹). Далее на входы слагаемых третьей группы сумматоров 11 блока элементов 2₁ поступают коды групп единичных и нулевых бит первой секции и сдвинутые значения с выходов модуля 13. На сумматоре 11₃ суммируются входные коды 1G3⁰=1 и 2G1⁰=1 и формируется код третьей группы G3⁰=2, а на других сумматорах одно из слагаемых принимает нулевое значение. Таким образом, на выходах устройства соответствующих группам бит будут сформированы следующие значения: QG1⁰=2, QG2¹=1, QG3⁰=2, QG4¹=1, QG5⁰=1, QG6¹=1, QG7⁰=0, QG8¹=0, QG9⁰=0 и общее количество (сумма) групп QК=6 (седьмой сумматор 20). Одновременно на четвертом сумматоре 12 формируется код количества (суммы) единичных бит QU=1U+2U=1+2=3, а также значение левого бита QDL=0.

Для входных данных D1-D8=1111 0000, при N=8, М=4, L=2, Z=2, на входы блока элементов 2₁ поступят следующие значения кодов:

- на первую секцию с выходов блока элементов 1₁ - 1G1⁰=0, 1G2¹=4, 1G3⁰=0, 1G4¹=0, 1G5⁰=0, 1К=1, 1U=4, 1DL=1,

- на вторую секцию с выходов блока элементов 1₂ - 2G1⁰=4, 2G2¹=0, 2G3⁰=0, 2G4¹=0, 2G5⁰=0, 2К=1, 2U=0, 2DL=0.

Из входных данных следует, что в первой секции количество групп бит 1К=1 и левый разряд принимает единичное значение 1DL=1, при этом первая группа нулевых бит содержит нулевой код 1G1⁰=0, а вторая группа содержит код «4» 1G2¹=4. Во второй секции содержится также одна группа 2К=1, при этом левый разряд принимает нулевое значение 2DL=0, а первая группа нулевых бит содержит код «4» 2G1⁰=4. Так как в первой секции одна группа бит 1К=1, то младший разряд 1k0=1 принимает единичное значение, а также левый разряд 1DL=1 принимает единичное значение и во второй секции левый разряд 2DL=0 принимает нулевое значение, то в соответствии с таблицами 2 и 3 в модуле 14 формируются код коррекции «+1» (единичное значение на выходе первого элемента И с одним инверсным входом 15), значение кода сдвига SK=1К+1=2 (шестой сумматор 19). и значение общего количества (суммы) групп К=2К+1К=1+1=2 (седьмой сумматор 20). Поэтому в модуле сдвига 13 осуществляется сдвиг всех групп единичных и нулевых бит второй секции на две группы SK=2 и вводом нулевых значений в разряды двух первых левых групп 0(2G1⁰)2 и 0(2G2¹). При этом на всех сумматорах одно из слагаемых принимает нулевое значение, а первая группа нулевых бит второй секции 2G1⁰=4 поступает на входы третьего сумматора 11₃. На выходах устройства соответствующих группам бит будут сформированы следующие значения: QG1⁰=0, QG2¹=4, QG3⁰=4, QG4¹=0, QG5⁰=0, QG6¹=0, QG7⁰=0, QG8¹=0, QG9⁰=0, общее количество (сумма) групп QК=2 (седьмой сумматор 20). код количества (суммы) единичных бит QU=1U+2U=4+0=4 (четвертый сумматор 12), а также значение левого бита QDL=1.

Модули счета единиц 7 и 9 могут быть реализованы как устройства, приведенные в аналоге устройство для определения количества единиц в упорядоченном двоичном числе (RU №2522875, МПК Н03К 21/12, заявлено 24.05.2012, опубликовано 20.07.2014, Бюл. №20) или в прототипе устройство для определения количества единиц (нулей) в двоичном числе (RU №2446442, МПК G06F 7/50, Н03К 21/00, заявлено 11.04.2011, опубликовано 27.03.2012, Бюл. №9). Модули сдвига групп 13 могут быть реализованы на матрице мультиплексоров с одновременным сдвигом всех разрядов групп, в которой реализуется логический сдвиг влево с вводом нулевых значений в разряды левых групп. Многогрупповой сумматор 10 может быть реализован как сумматор древовидной структуры, содержащий на каждом уровне многоразрядные сумматоры (Дж. Ф. Уэйкерли. Проектирование цифровых устройств. В 2-х томах. - М.: Постмаркет, 2002. - 1088 с., рис. 6.15, с. 606-609).

Предлагаемое устройство может быть применено для аппаратной реализации статистических тестов разработанных лабораторией информационных технологий Национального института стандартов и технологий (NIST, США), целью которых является определение меры случайности двоичных последовательностей порожденных генераторами случайных чисел. В частности предлагаемое устройство реализует:

- частотный побитовый тест, суть которого определить соотношение между нулями и единицами во всей двоичной последовательности. Цель - выяснить действительно ли число нулей и единиц в последовательности приблизительно одинаковы. Тест оценивает, насколько близка доля единиц к 0,5.

- частотный блочный тест, суть которого определение доли единиц внутри блока длиной К бит. Цель - выяснить действительно ли частота повторения единиц в блоке длиной К бит приблизительно равна К/2.

- тест на последовательность одинаковых бит, суть которого состоит в подсчете полного числа рядов (групп) в исходной последовательности, где под рядом понимается непрерывная подпоследовательность одинаковых бит. Ряд (группа) длиной к бит состоит из к абсолютно идентичных бит, начинается и заканчивается с бита содержащего противоположное значение. Цель - сделать вывод о том, действительно ли количество рядов (групп), состоящих из единиц и нулей с различными длинами, соответствует их количеству в случайной последовательности. В частности, определяется быстро либо медленно чередуются единицы и нули в исходной последовательности.

При обработке результатов физических экспериментов предлагаемое устройство обеспечивает выявление событий (группы единичных бит) и интервалов между событиями (группы нулевых бит), определение длительности событий и интервалов между ними, а также определение общего количества и длительности событий.

Введение в предлагаемое устройство групповой структуры обеспечивает:

- в блоках элементов 1 первой ступени сокращение на (L-1) каскадов 3 формирователей упорядоченных двоичных чисел (в устройстве без введения групп при N=16 необходимо (N-1)=15 каскадов, а при N=32 - (N-1)=31 каскад, в предлагаемом устройстве при М=4 разрядов в группе, в каждой группе вводится (М-1)=4-1=3 каскадов и для L=4 групп необходимо (M-1)*L=(4-1)*4=12 каскадов, а при N=32 и для L=8 групп - (M-1)*L=(4-1)*8=24 каскада);

- в блоках элементов 1 первой ступени сокращение объема аппаратных средств - общего количества элементов ИЛИ 4 и элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5, так как сумма элементов в каскадах формирователей 3 определяется количеством каскадов и увеличивается в арифметической прогрессии, а, следовательно, сокращается при сокращении количества каскадов (при N=16 в устройстве без введения групп количество (сумма арифметической прогрессии) элементов ИЛИ 4 составляет N*(N-1)/2=16*(16-1)/2=120 элементов и также элементов 5 «ИСКЛЮЧАЮЩЕЕ ИЛИ» 120 элементов, а при N=32 по N*(N-1)/2=32*(32-1)/2=496 элементов ИЛИ 4 и элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5, в предлагаемом устройстве при введении групп по М=4 разрядов, в каждой группе вводится по М*(М-1)/2=4*(4-1)/2=6 элементов, а для L=4 групп необходимо по 24 элемента ИЛИ 4 и элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5, а при N=32, М=4 и L=8 групп необходимо по (М*(М-1)/2)=(4*(4-1)/2)*8=48 элементов ИЛИ 4 и элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5);

- в модулях 7 и 9 счета единиц количество каскадов пропорционально log₂N(M) от общего количества разрядов N или разрядов М в группе и, следовательно, в предлагаемом устройстве сокращается количество каскадов и элементов в каскадах;

- увеличение быстродействия, так как в каскадах 3 формирователей упорядоченных двоичных чисел осуществляется последовательная передача данных между каскадами, то в предлагаемом устройстве при введении групп последовательная передача внутри групп также выполняется последовательно, но одновременно во всех группах, следовательно, время передачи данных сокращается в (N-1)/(M-1) раз (при N=16 и М=4 (N-1)/(M-1)=(16-1)/(4-1)=5 раз, а при N=32 и М=4 (N-1)/(M-1)=(32-1)/(4-1)=10,3 раз), далее при передаче данных в модулях счета 7 и 9 время передачи пропорционально log₂N или log₂M, следовательно сокращается при уменьшении количества каскадов, а затем в предлагаемом устройстве время передаче данных в ступенях пропорционально log₂Z от количества ступеней Z.

Таким образом, на выходах предлагаемого устройства формируются двоичные коды, соответствующие количеству нулевых и единичных бит в группах входного двоичного числа, при этом в нечетных группах QG⁰нч указывается количество нулей, а в четных группах QG¹чт количество единиц, а также формируются общее количество групп QК и общее количество единичных бит QU.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство решает поставленную задачу - выявление групп одинаковых бит, определение количества единичных и нулевых бит в группах и определение общего количества групп, обладает регулярностью узлов и связей, и соответствует заявляемому техническому результату -упрощение увеличения разрядности входных данных при сокращении аппаратных затрат и увеличение быстродействия устройства.

Изобретение относится к области вычислительной техники. Технический результат заключается в расширении функциональных возможностей. Устройство содержит N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на L групп по М разрядов в группе (N=L*M), Z ступеней блоков элементов, где Z=]log2L[+1 (большее целое), причем первая ступень содержит L блоков элементов, 1L первого типа, а каждая i-я ступень содержит по L/2(i-1) блоков элементов 2ij второго типа, 1L первого типа первой ступени содержит (М-1) каскадов формирователей упорядоченных двоичных чисел, 3(M-1), которые объединены в пирамидальную структуру, причем каждый v-й каскад 3v (v=1, …, (М-1)) содержит группу из (M-v) элементов ИЛИ, 4(M-v), группу из (M-v) элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 5(M-v), элемент ИЛИ с одним инверсным входом, группу из (М-1) модулей счета младших упорядоченных единиц, 7(M-1), первую группу из М сумматоров, 8M, модуль счета единиц и второй многогрупповой сумматор, каждый блок элементов 2ij второго типа содержит третью группу из (М*2(i-2)+1) сумматоров И, четвертый сумматор, модуль сдвига групп, модуль формирования кода сдвига и кода общего количества групп. 3 табл., 3 ил.

Устройство групповой структуры для детектирования групп нулевых и единичных бит и определение их количества содержит N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на L групп по М разрядов в группе (N=L*M), Z ступеней блоков элементов, где Z=]log₂L[+1 (] [ - большее целое), причем первая ступень содержит L блоков элементов 1₁, 1₂, …, 1_L первого типа, а каждая i-я ступень, начиная со второй ступени до Z-й ступени, содержит по L/2^(i-1) блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, …, L/2^(i-1),

причем N разрядов входного двоичного числа D1, D2, …, DN группами по М разрядов соединены с входами одноименных входным группам блоков элементов 1₁, 1₂, …, 1_L первого типа первой ступени, выходы нечетных блоков элементов 1₁, 1₃, …, 1_1(L-1)(нч) и выходы четных блоков элементов 1₂, 1₄, …, 1_L(чт) первой ступени попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2₂₁, 2₂₂, …, 2_2L/2 второго типа второй ступени, а выходы нечетных блоков элементов 2ij(нч) и выходы четных блоков элементов 2ij(чт) каждой i-й ступени, начиная со второй ступени до предпоследней (Z-1)-й ступени, попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2ij последующих ступеней, начиная с третьей ступени до последней Z-й ступени, а выходы групп блока элементов 2zj последней ступени Z являются соответствующими группами Q внешних одноименных выходов устройства группы QK общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, w групп QG нулевых и единичных бит (w=1, 2, …, N+1), причем выходы нечетных групп QG(wнч)⁰ соответствуют группам нулевых бит, а выходы четных групп QG(wчт)¹ соответствуют группам единичных бит, и выход QDL соответствует левому биту входного двоичного числа D1,

причем выходная группа QК общего количества групп единичных и нулевых бит и выходная группа QU количества единичных бит во входном двоичном числе D1, D2, …, DN содержат по ]log₂(N+1)[ (большее целое) разрядов, выходные группы нулевых и единичных бит QGw содержат по ]log₂(N+3-w)[ (большее целое) разрядов,

каждый блок элементов 1₁, 1₂, …, 1_L первого типа первой ступени содержит (М-1) каскадов формирователей упорядоченных двоичных чисел 3₁, 3₂, …, 3_(M-1), которые объединены в пирамидальную структуру, причем каждый v-й каскад 3_v (v=1, …, (М-1)) содержит группу из (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v), группу из (M-v) элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 5₁, 5₂, …, 5_(M-v), группу из (M+1-v) входов A1, А2, …, A(M+1-v), группу из (M-v) выходов O1, O2, …, O(M-v) в следующий каскад и группу из (M+1-v) выходов разрядов соответствующей v-й внутренней шины Sv из группы S1, S2, …, S(M-1),

а также в каждый блок элементов 1₁, 1₂, … 1_L первого типа первой ступени введены элемент ИЛИ с одним инверсным входом 6, группа из (М-1) модулей счета младших упорядоченных единиц 7₁, 7₂, …, 7_(M-1), первая группа из М сумматоров 8₁, 8₂, …, 8_M с инверсной группой входов второго слагаемого, модуль счета единиц 9 и второй многогрупповой сумматор 10, причем каждый v-й сумматор 8_v содержит по ]log₂(M+3-v)[ (большее целое) разряда входов слагаемых, а последний М-й сумматор 8_M содержит по два разряда входов слагаемых,

причем М разрядов каждой из L групп входного двоичного числа D1, D2, …, DN, начиная с первого разряда до М-го разряда, соединены в обратном порядке соответственно с входами AM, АМ-1, …, А1 первых каскадов 3₁ в соответствующих блоках элементов 1₁, 1₂, …, 1_L первого типа первой ступени, одноименных группам L,

в каждом v-м каскаде формирователей 3_v первые (M-v) входов A1, А2, …, A(M-v), кроме последнего входа A(M+1-v), соединены со вторыми входами соответствующих одноименных элементов ИЛИ 4₁, 4₂, …, 4_(M-v) и вторыми входами одноименных элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 5₁, 5₂, …, 5_(M-v), а первые входы первых (М-v-1) элементов ИЛИ 4₁, 4₂, …, 4_(M-v-1) из группы элементов ИЛИ, начиная с первого элемента ИЛИ, соединены с выходами соответствующих последующих элементов 4₂, 4₃, …, 4_(M-v) из группы элементов ИЛИ, начиная со второго элемента, первый вход последнего (M-v)-го элемента 4_(M-v) из группы элементов ИЛИ соединен с последним входом A(M+1-v) v-го каскада формирователей 3_v, выходы (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v) соединены также с первыми входами соответствующих одноименных элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 5₁, 5₂, …, 5_(M-v), выходы которых являются группой (M-v) выходов O1, O2, …, O(M-v) в следующий каскад каждого v-го каскада 3_v, а выходы всех (M-v) элементов ИЛИ 4₁, 4₂, …, 4_(M-v) также являются одноименными первыми младшими (M-v) разрядами соответствующей v-й внутренней шины Sv из группы S1, S2, …, S(M-1), начиная с первого разряда, а последний A(M+1-v)-й вход v-го каскада 3_v является старшим (M+1-v)-м разрядом соответствующей v-й внутренней шины Sv,

причем в первых (М-2) каскадах формирователей, кроме последнего (M-1)-го каскада 3_(M-1), (M-v) выходов О1, О2, …, O(M-v) в следующий (v+1)-й каскад 3_(v+1) соединены с соответствующими (M-v) одноименными входами A1, А2, …, A(M-v) следующего (v+1)-го каскада формирователей 3_(v+1),

все разряды каждой v-й внутренней шины Sv из группы S1, S2, …, S(M-1), в каждом блоке элементов 1₁, 1₂, …, 1_L первого типа первой ступени, соединены с входами соответствующего одноименного модуля 7_v из группы из (М-1) модулей счета младших упорядоченных единиц, а выходы каждого v-го модуля 7_v соединены с инверсной группой входов второго слагаемого соответствующего v-го сумматора 8_v и первой группой прямых входов первого слагаемого последующего (v+1)-го сумматора 8_(v+1) из первой группы из М сумматоров 8₁, 8₂, …, 8_M, выходы которых являются соответствующими первыми М группами выходных данных единичных и нулевых бит G1, G2, …, GM соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, а последний одноразрядный выход группы единичных и нулевых бит G(M+1) соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа соединен с выходом O1 последнего (М-1) каскада 3_(M-1), который также соединен с входом второй инверсной группы последнего М-го сумматора 8_M и первым прямым входом элемента ИЛИ с одним инверсным входом 6, второй инверсный вход которого соединен со старшим М-м входом AM первого каскада 3₁ соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, а также является выходом левого бита DL соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа,

кроме того, на группу прямых входов первого слагаемого первого сумматора 8₁ подан код двоичного числа «М», а на входы переносов CI всех М сумматоров 8₁, 8₂, …, 8_M подано значение логической единицы «1»,

входы групп второго многогруппового сумматора 10 подключены к выходам всех четных сумматоров 8(чт) в каждом блоке элементов 1₁, 1₂, …, 1_L первого типа, а группа выходов сумматора 10 является выходной группой U количества единичных бит во входных данных соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа,

младшие первые разряды всех (М-1) внутренних шин упорядоченных двоичных чисел S1, S2, …, S(M-1) соединены с соответствующими входами модуля счета единиц 9, у которого М-й вход соединен с выходом элемента ИЛИ с одним инверсным входом 6, а выходы модуля счета единиц 9 являются выходной группой К общего количества групп единичных и нулевых бит соответствующего блока элементов 1₁, 1₂, …, 1_L первого типа, причем группа общего количества групп К содержит ]log₂(M+1)[ (большее целое) разрядов,

причем каждый блок элементов 2_ij второго типа второй, третьей, …, Z-й ступени содержит третью группу из (М*2^(i-2)+1) сумматоров 11, четвертый сумматор 12, модуль сдвига групп 13, модуль формирования кода сдвига и кода общего количества групп 14, который содержит первый элемент И с одним инверсным входом 15, второй элемент И с одним инверсным входом 16, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 17, пятый сумматор 18, шестой сумматор 19, седьмой сумматор 20,

причем в каждом блоке элементов 2_ij второго типа соответствующие (М*2^(i-2)+1) группы входов нулевых и единичных бит 1G первых секций входов соединены с группами входов первых слагаемых соответствующих одноименных сумматоров из третьей группы сумматоров 11, у которых вторые группы входов вторых слагаемых соединены с соответствующими первыми (М*2^(i-2)+1) группами выходов модуля сдвига групп 13, у которого информационные группы входов соединены с соответствующими (М*2^(i-2)+1) группами входов нулевых и единичных бит 2G вторых секций входов блоков элементов 2_ij второго типа, а управляющие входы модуля сдвига групп 13 по шине задания значения количества сдвигов SK подключены к выходам модуля формирования кода сдвига и кода общего количества групп 14,

причем в модуле формирования кода сдвига и кода общего количества групп 14 вход левого бита 1DL первой секции входов соединен с первым прямым входом первого элемента И 15 с одним инверсным входом, со вторым инверсным входом второго элемента И 16 с одним инверсным входом, первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 17 и является выходом левого бита DL соответствующего блока элементов 2_ij, вход левого бита 2DL второй секции входов соединен со вторым инверсным входом первого элемента И 15 с одним инверсным входом, с первым прямым входом второго элемента И 16 с одним инверсным входом и со вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 17, третий вход которого соединен с младшим нулевым разрядом 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции, а также все разряды группы 1К соединены с группой входов второго слагаемого пятого сумматора 18, у которого все разряды первого слагаемого соединены между собой и подключены к выходу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 17, группа выходов пятого сумматора 18 соединена с группой входов второго слагаемого шестого сумматора 19 и с группой входов первого слагаемого седьмого сумматора 20, у которого группа входов второго слагаемого соединена с разрядами группы 2К общего количества групп единичных и нулевых бит второй секции, а группа выходов седьмого сумматора 20 является выходной группой К общего количества групп единичных и нулевых бит соответствующего блока элементов 2_ij второго типа,

а также все разряды первого слагаемого шестого сумматора 19 соединены между собой и подключены к выходу второго элемента И с одним инверсным входом 16, а вход переноса CI шестого сумматора 19 соединен с выходом первого элемента И с одним инверсным входом 15, а разряды группы выходов шестого сумматора 19 являются разрядами шины задания значения количества сдвигов SK,

выходы групп количества единичных бит первой секции 1U и второй секции 2U соединены соответственно с группами первого и второго слагаемых четвертого сумматора 12, группа выходов которого является группой выходов U соответствующего блока элементов 2_ij второго типа,

кроме того, в каждом блоке 2_ij второго типа выходы третьей группы сумматоров 11 и вторые группы выходов модуля сдвига групп 13, начиная с группы выходов (М*2^(i-2)+2) до группы выходов (М*2^(i-1)+1), являются выходами соответствующих групп G единичных и нулевых бит соответствующего блока элементов 2_ij второго типа.