УСТРОЙСТВО ПИРАМИДАЛЬНОЙ СТРУКТУРЫ ДЛЯ ДЕТЕКТИРОВАНИЯ ГРУПП НУЛЕВЫХ И ЕДИНИЧНЫХ БИТ И ОПРЕДЕЛЕНИЕ ИХ КОЛИЧЕСТВА Российский патент 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) модулей и элемент «ИЛИ».

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

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для определения количества нулей и единиц по группам в двоичном числе (RU №2672626, МПК G06F 7/74, заявлено 21.12.2017, опубликовано 16.11.2018, Бюл. №32), содержащее N разрядов входного двоичного числа D1, D2, …, DN, (N+1) групп выходных данных G1, G1, …, G(N+1), выходную группу К количества групп нулей и единиц, группу из (N-1) внутренних шин упорядоченных двоичных чисел S1, S2, …, S_(N-1), (N-1) каскадов формирователя упорядоченных двоичных чисел 1₁, 1₂, …, 1_N, причем каждый i-й каскад 1_i (i=1, …, (N-1)) содержит группу из (N-i) элементов ИЛИ 2₁, 2₂, …, 2_(N-i), группу из (N-i) элементов XOR 3₁, 3₂, …, 3_(N-i), группу из (N+1-i) входов A1, А2, …, A(N+1-i), группу из (N-i) выходов Q1, Q2, …, Q(N-i) в следующий каскад и группу из (N+1-i) выходов разрядов соответствующей i-й внутренней шины S_i из группы шин S1, S2, …, S_(N-1), а также в устройство введены первая группа из (N-i) блоков счета младших упорядоченных единиц 4₁, 4₂, …, 4_(N-i), группа из N сумматоров 5₁, 5₂, …, 5_N, с инверсной группой входов второго слагаемого, элемент ИЛИ с одним инверсным входом 6 и второй блок счета младших упорядоченных единиц 7, причем каждый i-й сумматор 5_i содержит ]log₂(N+3-i)[ (большее целое) разрядов, последний N-й сумматор 5_N содержит два разряда, а выходы количества групп К содержат ]log₂(N+1)[ (большее целое) разрядов.

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

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

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

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

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

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

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

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

содержит N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на N/2 групп по два разряда в группе, Z ступеней блоков элементов, где Z=]log₂N[ (] [ - большее целое), и модуль формирования флагов устройства 4,

причем первая ступень содержит N/2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа, а каждая i-ая ступень, начиная со второй ступени до Z-й ступени, содержит по N/2ⁱ блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, N/2ⁱ,

причем N разрядов входного двоичного числа D1, D2, …, DN группами по два разряда соединены с входами соответствующих одноименных входным группам блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени, выходы нечетных блоков элементов 1₁, 1₃, …, 1_(N/2-1)(нч) и выходы четных блоков элементов 1₂, 1₄, …, 1_N/2(чт) первой ступени попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2₂₁, 2₂₂, …, 2_2N/4 второго типа второй ступени, а выходы нечетных блоков элементов 2ij(нч) и выходы четных блоков элементов 2ij(чт) каждой i-ой ступени, начиная со второй ступени до предпоследней (Z-1)-ой ступени, попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2ij последующих ступеней, начиная с третьей ступени до последней Z-ой ступени, а выходы групп блока элементов 2zj последней Z-ой ступени являются соответствующими группами Q внешних одноименных выходов устройства группы QK общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, N групп QG1, QG2, …, QGN нулевых и единичных бит и выход QLB, соответствующий левому биту входного двоичного числа D1,

каждый из N/2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени содержит элемент «ЭКВИВАЛЕНТНОСТИ» 5, первый элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 и элемент И 7,

причем пары разрядов каждой из N/2 групп входного двоичного числа D1, D2, …, DN, начиная с первого разряда, соединены соответственно с входами А1 и А2 соответствующих одноименных блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени одноименных группам N/2, при этом входы А1 и А2 соединены с первыми и вторыми входами элемента «ЭКВИВАЛЕНТНОСТИ» 5, первого элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 и элемента И 7, а также первый вход А1 соединен с выходом левого бита LB блока первого типа 1, выход элемента «ЭКВИВАЛЕНТНОСТИ» 5 соединен с первым разрядом g11 первой выходной группы G1 бит и нулевым разрядом k0 выходной группы К общего количества групп единичных и нулевых бит, выход первого элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 соединен с нулевым разрядом g10 первой выходной группы G1 бит, с нулевым разрядом g20 второй выходной группы G2 бит, с первым разрядом k1 выходной группы К общего количества групп единичных и нулевых бит и с нулевым разрядом u0 выходной группы U количества единичных бит, выход элемента И 7 соединен с первым разрядом u1 выходной группы U количества единичных бит,

каждый блок элементов 2ij второго типа второй, третьей, …, Z-ой ступени содержит второй элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, дешифратор DC 9, вычитатель SB 10, группу мультиплексоров MX 11, первый сумматор SM 12, второй сумматор SM 13, модуль сдвига групп SF 14, группы элементов И с одним инверсным входом 15, группы элементов ИЛИ 16 и третий сумматор SM 17,

причем вход 1LB левого бита первой секции соединен с выходом левого бита LB блока второго типа 2, все 2^(i-1) входных групп первых секций, начиная с первой 1G1 группы до последней 1G(2^(i-1)) группы, соединены с первыми прямыми входами элементов соответствующих одноименных групп элементов И с одним инверсным входом 15 и также соединены с соответствующими информационными входами группы мультиплексоров MX 11, выходы которых соединены с группой входов первого слагаемого второго сумматора 13, у которого группа входов второго слагаемого соединена с первой группой 2G1 второй секции, а выход второго сумматора 13 соединен с первой группой входов модуля сдвига групп SF 14, у которого (2^(i-1)-1) входных групп, начиная со второй группы до последней группы, соединены с соответствующими одноименными группами 2G второй секции, начиная со второй 2G2 группы до последней 2G(2^(i-1)) группы, а первые 2^(i-1) выходов модуля сдвига групп SF 14, начиная с первого выхода до 2^(i-1) выхода, соединены со вторыми входами элементов соответствующих одноименных групп элементов ИЛИ 16, первые входы которых соединены с соответствующими одноименными выходами элементов групп элементов И с одним инверсным входом 15,

кроме того в блоках 2 второго типа вход 1LB левого бита первой секции, вход 2LB левого бита второй секции и младший нулевой разряд 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции соединены с соответствующими входами второго элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, выход которого соединен с входом разрешения работы Е дешифратора DC 9 и вторым входом вычитателя SB 10, входная группа 1К общего количества групп единичных и нулевых бит первой секции соединена с первой группой входов вычитателя SB и с группой входов дешифратора DC 9, а выходы вычитателя SB 10 соединены с шиной SK задания значения количества сдвигов, которая подключена к группе управляющих входов модуля сдвига групп SF 14 и к группе входов первого слагаемого первого сумматора SM 12, у которого группа входов второго слагаемого соединена с входной группой 2К общего количества групп единичных и нулевых бит второй секции, входные группы 1U и 2U количества единичных бит первой и второй секций соединены с группами входов первого и второго слагаемых третьего сумматора SM 17, выходы дешифратора DC 9 соединены с соответствующими управляющими входами выборки группы мультиплексоров MX 11 и со вторыми инверсными входами элементов соответствующих одноименных групп элементов И с одним инверсным входом 15,

причем выходы групп элементов ИЛИ 16 являются первыми 2^(i-1) выходами групп блоков 2, начиная с первой G1 группы до G(2^(i-l)) группы, а выходы групп модуля сдвига групп SF 14, начиная с группы (2^(i-1)+1) выходов до группы 2ⁱ выходов, являются соответствующими одноименными выходами групп блоков 2, начиная с группы G(2^(i-1)+1) выходов до группы G2ⁱ выходов, и кроме того выходы первого сумматора SM 12 являются группой выходов К общего количества групп единичных и нулевых бит блоков 2, а выходы третьего сумматора SM 17 являются группой выходов U количества единичных бит,

модуль формирования флагов устройства 4 содержит четвертый сумматор SM с инверсной группой входов 18, пятый сумматор SM с инверсной группой входов 19, первый элемент ИЛИ-НЕ 20, третью группу элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21, второй элемент ИЛИ-НЕ 22 и инкрементор SI 23,

причем группа выходов U количества единичных бит с последней Z-ой ступени соединена с первой группой входов модуля 4 формирования флагов устройства, у которого на вторую группу входов подан код двоичного числа «N», соответствующий количеству разрядов входного двоичного числа D1, D2, …, DN, при этом первая группа входов модуля 4 формирования флагов устройства соединена с первыми инверсными группами входов первых слагаемых пятого сумматора 19 и четвертого сумматора 18, при этом у четвертого сумматора 18 на вторую прямую группу входов второго слагаемого подан код двоичного числа «N» и на вход переноса CI которого подано значение логической единицы «1», а группа выходов четвертого сумматора 18 является группой внешних выходов QZ количества нулевых бит во входном двоичном числе D1, D2, …, DN и также соединена со второй прямой группой входов второго слагаемого пятого сумматора 19, у которого на вход переноса CI подано значение логической единицы «1», а разряды группы выходов пятого сумматора 19 соединена с соответствующими входами первого элемента ИЛИ-НЕ 20 и с первыми входами соответствующих одноименных элементов из третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21, вторые входы которых соединены между собой и подключены к инверсному выходу переноса СО пятого сумматора 19, который также соединен со вторым входом инкрементора SI 23, со вторым входом второго элемента ИЛИ-НЕ 22 и является внешним выходом флага F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ», выход первого элемента ИЛИ-НЕ 20 является внешним выходом флага FE «СУММА НУЛЕЙ РАВНА СУММЕ ЕДИНИЦ» и также соединен с первым входом второго элемента ИЛИ-НЕ 22, выход которого является внешним выходом флага F01 «НУЛЕЙ БОЛЬШЕ ЕДИНИЦ», выходы третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21 соединены с соответствующими разрядами первой группы входов инкрементора SI 23, выходы которого являются группой внешних выходов Q01 разности между количеством нулевых и единичных бит,

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

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

На фиг. 1 представлена структурная схема предлагаемого устройства пирамидальной структуры для детектирования групп нулевых и единичных бит и определение их количества. На фиг. 2 представлена функциональная схема предлагаемого устройства при N=8 и Z=3. На фиг. 3 приведены форматы выходных данных Q на внешних выходах 24 и разрядности групп для N разрядов входных данных при QLB=D1=0 и QLB=D1=1, для N=4 при QLB=D1=0 и для N=8 при QLB=D1=1. В таблице 1 приведены значения выходных функций для блоков 1 первого типа первой ступени. В таблице 2 приведены примеры объединения групп, подряд идущих единичных или нулевых бит и формирования общего количества групп К при N=4 для блоков 2₂ второй ступени. В таблице 3 приведены примеры объединения групп, подряд идущих единичных или нулевых бит и формирования общего количества групп К при N=8 для блоков 2₃ третьей ступени. В таблице 4 приведены значения функций для флага декрементации FD, корректировки кода суммы К общего количества групп и кода количества сдвига на шине SK. В таблице 5 приведены значения функций для формирования внешних флагов FE, F10 и F01.

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

N - количество разрядов входного двоичного числа,

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

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

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

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

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

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

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

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

LB - левый бит,

DC - дешифратор (демультиплексор),

Е - вход разрешения работы,

MX - группа мультиплексоров (коммутаторов),

SB - вычитатель (декрементор),

SI - инкрементор (сумматор),

SM - сумматор,

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

СО - выход переноса сумматора,

FD - флаг декрементации кода суммы 1К количества групп первой секции,

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

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

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

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

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

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

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

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

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

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

ZU - шина суммы QZ + not QU + 1,

Q01 - группа выходов разности между количеством нулевых QZ и единичных бит,

F0 - флаг «ВСЕ НУЛИ»,

F01 - флаг «НУЛЕЙ БОЛЬШЕ ЕДИНИЦ»,

FE - флаг «СУММА НУЛЕЙ РАВНА СУММЕ ЕДИНИЦ»,

F10 - флаг «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ»,

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

2ij - блоки элементов второго типа i-й ступени, где i=2, 3, …, Z, j=1, 2, …, N/2ⁱ,

3 - внешние входы устройства,

4 - модуль формирования флагов устройства,

5 - элемент «ЭКВИВАЛЕНТНОСТИ (РАВНОЗНАЧНОСТИ)» (XNOR),

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

7 - элемент И,

8 - второй элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR),

9 - дешифратор (демультиплексор) DC,

10 - вычитатель (декрементор) SB,

11 - группа мультиплексоров (коммутаторов) MX,

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

13 - второй сумматор SM,

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

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

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

17 - третий сумматор SM,

18 - четвертый сумматор SM с инверсной группой входов,

19 - пятый сумматор SM с инверсной группой входов,

20 - первый элемент ИЛИ-НЕ,

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

22 - второй элемент ИЛИ-НЕ,

23 - инкрементор (сумматор) SI,

24 - внешние выходы устройства.

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

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

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

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

Выходы групп блока элементов 2zj последней Z-ой ступени являются соответствующими группами Q внешних одноименных выходов устройства группы QK общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, N групп QG1, QG2, …, QGN нулевых и единичных бит и выход QLB, соответствующий левому биту входного двоичного числа D1.

Каждый из N/2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени содержит элемент «ЭКВИВАЛЕНТНОСТИ» 5, первый элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 и элемент И 7.

Причем пары разрядов каждой из N/2 групп входного двоичного числа D1, D2, …, DN, начиная с первого разряда, соединены соответственно с входами А1 и А2 соответствующих одноименных блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени одноименных группам N/2. При этом входы А1 и А2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени соединены с первыми и вторыми входами элемента «ЭКВИВАЛЕНТНОСТИ» 5, первого элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 и элемента И 7. Кроме того первый вход А1 соединен с выходом левого бита LB блока первого типа 1. Выход элемента «ЭКВИВАЛЕНТНОСТИ» 5 соединен с первым разрядом g11 первой выходной группы G1 бит и нулевым разрядом k0 выходной группы К общего количества групп единичных и нулевых бит. Выход первого элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 соединен с нулевым разрядом g10 первой выходной группы G1 бит, с нулевым разрядом g20 второй выходной группы G2 бит, с первым разрядом k1 выходной группы К общего количества групп единичных и нулевых бит и с нулевым разрядом u0 выходной группы U количества единичных бит. Выход элемента И 7 соединен с первым разрядом u1 выходной группы U количества единичных бит.

Каждый блок элементов 2_ij второго типа второй, третьей, …, Z-ой ступени содержит второй элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, дешифратор DC 9, вычитатель SB 10, группу мультиплексоров MX 11, первый сумматор SM 12, второй сумматор SM 13, модуль сдвига групп SF 14, группы элементов И с одним инверсным входом 15, группы элементов ИЛИ 16 и третий сумматор SM 17.

Причем вход 1LB левого бита первой секции соединен с выходом левого бита LB блока второго типа 2. Все 2^(i-1) входных групп первых секций, начиная с первой 1G1 группы до последней 1G(2^(i-1)) группы, соединены с первыми прямыми входами элементов соответствующих одноименных групп элементов И с одним инверсным входом 15 и также соединены с соответствующими информационными входами группы мультиплексоров MX 11, выходы которых соединены с группой входов первого слагаемого второго сумматора 13. Группа входов второго слагаемого второго сумматора 13 соединена с первой группой 2G1 второй секции.

Выход второго сумматора 13 соединен с первой группой входов модуля сдвига групп SF 14, у которого (2^(i-1)-1) входных групп, начиная со второй группы до последней группы, соединены с соответствующими одноименными группами 2G второй секции, начиная со второй 2G2 группы до последней 2G(2^(i-1)) группы.

Первые 2^(i-1) выходов модуля сдвига групп SF 14, начиная с первого выхода до 2^(i-1) выхода, соединены со вторыми входами элементов соответствующих одноименных групп элементов ИЛИ 16, первые входы которых соединены с соответствующими одноименными выходами элементов групп элементов И с одним инверсным входом 15.

Кроме того, в блоках 2 второго типа вход 1LB левого бита первой секции, вход 2LB левого бита второй секции и младший нулевой разряд 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции соединены с соответствующими входами второго элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, выход которого соединен с входом разрешения работы Е дешифратора DC 9 и вторым входом вычитателя SB 10. Входная группа 1К общего количества групп единичных и нулевых бит первой секции соединена с первой группой входов вычитателя SB и с группой входов дешифратора DC 9.

Выходы вычитателя SB 10 соединены с шиной SK задания значения количества сдвигов, которая подключена к группе управляющих входов модуля сдвига групп SF 14 и к группе входов первого слагаемого первого сумматора SM 12. Группа входов второго слагаемого первого сумматора SM 12 соединена с входной группой 2К общего количества групп единичных и нулевых бит второй секции, входные. Группы 1U и 2 U количества единичных бит первой и второй секций соединены с группами входов первого и второго слагаемых третьего сумматора SM 17. Выходы дешифратора DC 9 соединены с соответствующими управляющими входами выборки группы мультиплексоров MX 11 и со вторыми инверсными входами элементов соответствующих одноименных групп элементов И с одним инверсным входом 15.

Причем выходы групп элементов ИЛИ 16 являются первыми 2^(i-1) выходами групп блоков 2, начиная с первой G1 группы до G2^(i-1)) группы, а выходы групп модуля сдвига групп SF 14, начиная с группы (2^(i-1)+1) выходов до группы 2ⁱ выходов, являются соответствующими одноименными выходами групп блоков 2, начиная с группы G(2^(i-1)+1) выходов до группы G2ⁱ выходов. Кроме того, выходы первого сумматора SM 12 являются группой выходов К общего количества групп единичных и нулевых бит блоков 2, а выходы третьего сумматора SM 17 являются группой выходов U количества единичных бит.

Модуль формирования флагов устройства 4 содержит четвертый сумматор SM с инверсной группой входов 18, пятый сумматор SM с инверсной группой входов 19, первый элемент ИЛИ-НЕ 20, третью группу элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21, второй элемент ИЛИ-НЕ 22 и инкрементор SI 23.

Причем группа выходов U количества единичных бит с последней Z-ой ступени соединена с первой группой входов модуля 4 формирования флагов устройства, у которого на вторую группу входов подан код двоичного числа «N», соответствующий количеству разрядов входного двоичного числа D1, D2, …, DN. При этом первая группа входов модуля 4 формирования флагов устройства соединена с первыми инверсными группами входов первых слагаемых пятого сумматора 19 и четвертого сумматора 18. При этом у четвертого сумматора 18 на вторую прямую группу входов второго слагаемого подан код двоичного числа «N», а на вход переноса CI которого подано значение логической единицы «1».

Группа выходов четвертого сумматора 18 является группой внешних выходов QZ количества нулевых бит во входном двоичном числе D1, D2, …, DN и также соединена со второй прямой группой входов второго слагаемого пятого сумматора 19. На вход переноса CI пятого сумматора 19 подано значение логической единицы «1». Разряды группы выходов пятого сумматора 19 соединена с соответствующими входами первого элемента ИЛИ-НЕ 20 и с первыми входами соответствующих одноименных элементов из третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21.

Инверсный выход переноса СО пятого сумматора 19 подключен ко вторым входам элементов из третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21, соединенных между собой, а также соединен со вторым входом инкрементора SI 23, со вторым входом второго элемента ИЛИ-НЕ 22 и является внешним выходом флага F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ».

Выход первого элемента ИЛИ-НЕ 20 является внешним выходом флага FE «СУММА НУЛЕЙ РАВНА СУММЕ ЕДИНИЦ» и также соединен с первым входом второго элемента ИЛИ-НЕ 22. Выход второго элемента ИЛИ-НЕ 22 является внешним выходом флага F01 «НУЛЕЙ БОЛЬШЕ ЕДИНИЦ». Выходы третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21 соединены с соответствующими разрядами первой группы входов инкрементора SI 23, выходы которого являются группой внешних выходов Q01 разности между количеством нулевых и единичных бит.

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

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

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

Входное N разрядное двоичное число без знака разбивается на N/2 групп по два разряда в группе и попарно поступает на входы А1 и А2 в соответствующие N/2 одноименных блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени.

В блоках элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени, в соответствии с таблицей 1, для каждой пары разрядов A1, А2 формируются значения двоичных кодов групп G1 и G2, соответствующих количеству подряд идущих единичных или нулевых бит в группе, а также формируются двоичный код К общего количества групп и двоичный код U общего количества единичных бит. Кроме того, также на выходы LB блоков элементов 1₁, 1₂, …, 1_N/2 передается значение левого бита А1. При этом если LB принимает нулевое значение LB=0, то первая группа бит содержит нулевые биты G1⁰, а если LB принимает единичное значение LB=1, то первая группа бит содержит единичные биты G1¹. При этом последующие группы единичных бит G¹ и нулевых бит G⁰ чередуются. Двоичные коды групп G1 могут принимать значения 0, 1 или 2, а двоичные коды групп G2 могут принимать значения 0 или 1. Двоичные коды К общего количества (суммы) групп принимают значения 1 или 2. Двоичные коды U общего количества единичных бит могут принимать значения 0, 1 или 2. Данные значения кодов формируются на элементе «ЭКВИВАЛЕНТНОСТИ» (XNOR) 5, первом элементе «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR) 6 и элементе И 7 и передаются на соответствующие выходы блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени.

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

В каждом блоке элементов 2ij второго типа проводится объединение значений двоичных кодов соседних групп входов нулевых G⁰ бит или групп входов единичных G¹ бит первых 1G и вторых 2G секций. Возможные варианты объединения групп для второй ступени приведены в таблице 2 и для третьей ступени приведены в таблице 3. На вторых сумматорах 13 проводится суммирование двоичных кодов старшей группы первых секций 1G и младшей группы 2G1 вторых секций при одновременном совпадении в них подряд идущих единичных или нулевых бит. На группу входов первого слагаемого вторых сумматоров 13 передается старшая группа первой секции 1G, при подряд идущих единичных или нулевых бит в соседних секциях, или нулевое значение двоичного кода, если в одной группе содержатся единичные бит G¹, а в другой группе нулевые бит G⁰. На группу входов второго слагаемого всегда поступает значение двоичного кода младшей первой группы 2G1 второй секции. В таблицах 2 и 3 штриховкой отмечены группы суммируемые на вторых сумматорах 13.

Группы единичных бит G¹ и нулевых бит G⁰ последовательно чередуются, при этом значение первой группы G1 задается левым битом LB. Для определения типа значения единичных или нулевых бит в старшей группе первых секций достаточно анализировать значение левых бит 1LB первых секций и значение младшего нулевого разряда 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции, который указывает на четность количества групп (при 1k0=0) и соответственно разнотипность первой и старшей групп или нечетность количества групп (при 1k0=1) и соответственно однотипность первой и старшей групп (таблицы 2 и 3).

Для выявления групп (рядов) подряд идущих единичных и нулевых бит и объединения однотипных групп соседних секций анализируются значения входов левых разрядов 1LB и 2LB первой и второй секций соответственно и значение младшего нулевого разряда 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции. При совпадении в соседних секциях в старшей группе первой секции 1G и в младшей группе второй секции 2G1 подряд идущих единичных G¹ или нулевых G⁰ бит на выходе второго элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8 в соответствии с таблицей 4 формируется флаг декрементации FD. При единичном значении флага декрементации FD=1 проводится вычитание единицы из кода суммы 1К количества групп первой секции на вычитателе SB (декременторе) 10, на выходе которого формируется код количества сдвигов поступающий на шину SK. Одновременно на входы выборки дешифратора DC (демультиплексора) 9 передается значение кода группы 1К общего количества групп единичных и нулевых бит первой секции. При нулевом значении флага декрементации FD=0 по входу разрешения работы Е запрещается работа дешифратора DC (демультиплексора) 9 и на всех выходах которого формируются нулевые значения. При единичном значении флага декрементации FD=1 на выходах дешифратора DC (демультиплексора) 9 формируется унитарный код «1 из 2^(i-1)», по которому на выходы группы мультиплексоров MX (коммутаторов) 11 передается двоичный код старшей группы первой секции 1G, который поступает на группу входов первого слагаемого вторых сумматоров 13.

В модулях SF сдвига групп 14 на входы младшей группы передается значение с выходов вторых сумматоров 13, а на последующие старшие группы входов, начиная со второй группы, поступают соответствующие одноименные группы 2G вторых секций. В модулях SF сдвига групп 14 осуществляется сдвиг групп нулевых G⁰ и единичных G¹ бит на значение кода сдвига на шине SK в сторону старших групп и вводом в сдвигаемые разряды младших групп нулевых значений.

Значения нулевых G⁰ и единичных G¹ бит групп 1G первых секций поступают на первые прямые входы соответствующих групп элементов И с одним инверсным входом 15, на вторые инверсные входы которых поступают значения с соответствующих одноименных выходов дешифратора DC (демультиплексора) 9. Таким образом на выходы групп элементов И с одним инверсным входом 15 передаются значения групп 1G первых секций или нулевые значения, которые поступают на первые входы соответствующих одноименных групп элементов ИЛИ 16, на вторые входы которых поступают значения с выходов соответствующих одноименных групп модуля SF сдвига групп 14.

Во всех ступенях в каждом блоке элементов 2ij выходы группы элементов ИЛИ 16 являются соответствующими одноименными младшими группами выходов G1, G2, …, G2^(i-1), а выходы старших групп модуля SF сдвига групп 14 соответствующими одноименными старшими группами выходов G(2^(i-1)+1), G(2^(i-1)+2), …, G2ⁱ. Кроме того на первых сумматорах 12 осуществляется суммирование скорректированного значения кода группы общего количества групп SK=1К-FD первой секции и значения кода 2К общего количества групп единичных и нулевых бит второй секции и формируется код суммы групп К, который передается на соответствующую группу выходов К блока элементов 2ij. Также на третьих сумматорах 17 осуществляется суммирование групп количества (суммы) единичных бит 1U первых секций и 2U вторых секций и на выходе формируется двоичный код количества (суммы) единичных бит U, который передается на соответствующую группу выходов U блока элементов 2ij.

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

Кроме того выход группы QU количества (суммы) единичных бит с последней Z-ой ступени поступает на первую группу входов модуля 4 формирования флагов устройства, на вторую группу входов которого поступает двоичный код «N», соответствующий количеству разрядов входного двоичного числа D1, D2, …, DN. Значение кода QU количества (суммы) единичных бит поступает на первую инверсную группу входов первого слагаемого четвертого сумматора 18, а на вторую прямую группу второго слагаемого четвертого сумматора 18 поступает двоичный код «N» и на вход переноса CI которого поступает единичное значение CI=1. Таким образом, на выходе четвертого сумматора 18 формируется значение двоичного кода QZ, соответствующего количеству (сумме) нулевых бит во входном числе - QZ=N + not QU + 1 (таблица 5), которое передается на соответствующую группу выходов QZ модуля флагов 4.

Одновременно значение кода QU количества (суммы) единичных бит поступает также на первую инверсную группу входов первого слагаемого пятого сумматора 19, на вторую прямую группу второго слагаемого пятого сумматора 19 поступает значение двоичного кода QZ, соответствующего количеству (сумме) нулевых бит, и на вход переноса CI которого поступает единичное значение CI=1. При этом на выходе пятого сумматора 19 формируется значение двоичного кода ZU, соответствующего разности между количеством (суммами) нулевых QZ и единичных QU бит: ZU=QZ + not QU + 1 и формируется выходной перенос СО (таблица 5). Все выходные разряды пятого сумматора 19 поступают на соответствующие входы первого элемента ИЛИ-НЕ 20, на выходе которого формируется флаг F0 «ВСЕ НУЛИ», который принимает единичное значение F0=1 если все разряды имеют нулевое значение, что соответствует равенству слагаемых - когда количества единичных QU и нулевых QZ бит равны. Значение флага F0 «ВСЕ НУЛИ» передается на соответствующий выход устройства как выходной флаг FE «СУММА НУЛЕЙ РАВНА СУММЕ ЕДИНИЦ». Выходной перенос СО пятого сумматора 19 принимает единичное значение СО=1 когда количество (сумма) нулевых QZ бит не меньше (больше или равна) количества (суммы) единичных QU и принимает нулевое значение СО=0 когда количество (сумма) нулевых QZ бит меньше количества (суммы) единичных QU. Поэтому в соответствии с таблицей 5 формируются выходные флаги: флаг F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ» как F10=not СО и флаг F01 «НУЛЕЙ БОЛЬШЕ ЕДИНИЦ» как F01=not (not СО OR F0), значение которого формируется на втором элементе ИЛИ-НЕ 22.

Одновременно все выходные разряды пятого сумматора 19 поступают на первые входы соответствующих одноименных элементов из третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR) 21, вторые входы которых соединены между собой и подключены к инверсному выходу переноса СО пятого сумматора 19. При этом при единичном значении переноса СО=1 на выходы третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR) 21 передаются прямые значения разрядов с выходов пятого сумматора 19, а при нулевом значении переноса СО=0 инверсные значения. Далее на инкременторе (сумматоре) SI 23 при единичном значении not СО=1, которое поступает на вход переноса CI и соответствует случаю, когда количество (сумма) нулевых QZ бит меньше количества (суммы) единичных QU, значение кода ZU преобразуется, как дополнение до N, в код разности между количеством нулевых и единичных бит, а при нулевом значении not СО=0 передается без преобразования (таблица 5). Далее с выходов инкрементора (сумматора) SI 23 значение передается на соответствующую группу выходов Q01 разности между количеством (суммами) нулевых и единичных бит. В таблице 5 в подстрочных символах указана форма представления данных - двоичная (2) или десятичная (10). На фиг. 3 приведены форматы выходных данных Q на внешних выходах 24 и разрядности групп для N разрядов входных данных при QLB=D1=0 и QLB=D1=1, для N=4 при QLB=D1=0 и для N=8 при QLB=D1=1.

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

На внешние входы устройства 3 поступает N разрядов входного двоичного числа без знака D1, D2, …, DN, которые разделены на N/2 групп по два разрядов в группе. Младший разряд D1 является первым левым разрядом входного двоичного числа. Попарно входные разряды поступают на входы А1 и А2 в соответствующие N/2 одноименных блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени. Значения с входов А1 и А2 поступают на первые и вторые входы элемента «ЭКВИВАЛЕНТНОСТИ» (XNOR) 5, первого элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR) 6 и элемента И 7.

В блоках элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени для каждой пары входных разрядов A1, А2, в соответствии с таблицей 1, на выходах формируются значения двоичных кодов групп G1 и G2, соответствующих количеству подряд идущих в группе единичных или нулевых бит, а также формируются двоичный код К общего количества групп и двоичный код U общего количества единичных бит. Например, для входного числа A1 А2=00, так как левый бит LB и оба бита А1 и А2 принимают нулевые значения, то на выходах блока формируются следующие значения: LB=0, G1⁰=10₂=2₁₀, G2¹=0, К=01₂=1₁₀, U=00₂=0₁₀, а для входного числа A1 A2=10 формируются следующие значения: LB=1, G1¹=01₂=1₁₀, G2⁰=1, К=10₂=2₁₀, U=01₂=1₁₀.

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

В каждом блоке элементов 2_2j второго типа второй ступени анализируются значения входов левых разрядов 1LB первой секции и 2LB второй секции и значение младшего нулевого разряда 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции и на выходе второго элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, в соответствии с таблицей 4, формируется флаг декрементации FD. При нулевом значении флага декрементации FD=0 запрещается работа дешифратора DC (демультиплексора) 9 и на всех выходах формируются нулевые значения. При единичном значении флага декрементации FD=1 на выходах дешифратора DC (демультиплексора) 9 формируется унитарный код «1 из 2^(i-1)», по которому на выходы группы мультиплексоров MX (коммутаторов) 11 передается двоичный код старшей группы 1G первой секции, который поступает на группу входов первого слагаемого вторых сумматоров 13. Например, в соответствии с таблицей 2, для значений входов 1k0=0, 1LB=0 и 2LB=0 (нулевая строка №=0 таблицы 2 когда первая секция содержит две группы (1k0=0) и первые младшие группы первой 1G1⁰ и второй 2G1⁰ секций содержат нулевые бит) формируется флаг декрементации FD=0 (таблица 4), так как вторая группа 1G2¹ первой секции содержит единичные биты, а первая группа 2G1⁰ второй секции содержит нулевые биты. Так как сформирован нулевой флаг декрементации FD=0, то на группу входов первого слагаемого второго сумматора 13 поступает нулевой код, а на группу входов второго слагаемого которого поступает значение двоичного кода младшей группы второй секции 2G1⁰. Одновременно на выход вычитателя SB (декрементора) 10 передается значение 1К=2₁₀ без коррекции, которое передается на шину SK количества сдвигов, по которому в модуле SF сдвига групп 14 осуществляется сдвиг группы с выходов второго сумматора 13 и группы 2G второй секции в сторону старших групп на две группы.

Далее, так как с выходов дешифратора DC (демультиплексора) 9 передаются нулевые значения и две старшие группы на выходе модуля SF сдвига групп 14 также принимают нулевые значения, то первые две группы первой секции 1G1⁰ и 1G2¹ передаются через группы элементов И с одним инверсным входом 15 и группы элементов ИЛИ 16 на соответствующие группы выходов G1 и G2. При этом на группы выходов G3 и G4 передаются значения с выходов третьей и четвертой групп модуля SF сдвига групп 14. Одновременно на первом сумматоре 12 суммируются значения общего количества групп 1К и 2К без коррекции на значение флага декрементации, так как FD=0, а также на третьем сумматоре 17 суммируются значения кодов 1U и 2U количества (суммы) единичных бит в первой и второй секциях, с выходов которых поступают соответственно на группы выходов блока К и U.

Для значений входов 1k0=0, 1LB=0 и 2LB=1 (первая строка №=1 таблицы 2 когда первая секция содержит две группы (1k0=0), первая младшая группа 1G1⁰ первой секции содержит нулевые биты, а первая младшая группа 2G1¹ второй секций содержит единичные биты) формируется единичный флаг декрементации FD=1, по которому разрешается работа дешифратора DC (демультиплексора) 9 и поэтому на группу входов первого слагаемого второго сумматора 13 с выходов группы мультиплексоров MX (коммутаторов) 11 поступает двоичный код единичных бит старшей группы 1G2¹ первой секции, а на группу входов второго слагаемого которого поступает значение двоичного кода единичных бит младшей группы 2G1¹ второй секции, которые суммируются на втором сумматоре 13, так как во входных данных D1, D2, …, DN эти группы образуют общую группу единичных бит. Далее так как на выходе вычитателя SB (декрементора) 10 формируется значение 1К=1₁₀ с коррекцией кода сдвига, то в модуле SF сдвига групп 14 осуществляется сдвиг на одну группу и ввод нулевых значений в левую младшую группу. Так как на выходе дешифратора DC (демультиплексора) 9 единичное значение установлено на втором выходе соответствующем второй группе 1G2¹, то запрещается передача этой группы через соответствующие элементы И с одним инверсным входом 15, а на выход G2 блока передается значение соответствующей группы с выхода второго сумматора 13 через модуль SF сдвига групп 14. Аналогично, выше рассмотренному, формируются коды на группах выходов блока К и U.

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

Далее значения с выходов нечетных блоков элементов 2₂₁, 2₂₃, …, 2_2(N/4-1) (нч) и выходов четных блоков элементов 2₂₂, 2₂₄, …, 2_2N/4(чт) второй ступени попарно поступают на соответствующие группы одноименных входов соответственно первых и вторых секций входов соответствующих блоков 2₃₁, 2₃₂, …, 2_3N/4 третьей ступени (фиг. 1).

В каждом блоке элементов 2_3j второго типа третьей ступени аналогично анализируются значения входов левых разрядов 1LB первой секции и 2LB второй секции и значение младшего нулевого разряда 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции и на выходе второго элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, в соответствии с таблицей 4, формируется флаг декрементации FD. Далее в соответствии с таблицей 3 на вторых сумматорах 13 осуществляется суммирование соответствующих старших правых групп 1G первых секций и младших левых групп 2G вторых секций (выделены штриховкой в таблице 3), на вычитателях SB (декременторах) 10 формируются значения кода сдвига SK с учетом значения флага декрементации FD и в модуле SF сдвига групп 14 осуществляется сдвиг на код сдвига SK и ввод нулевых значений в левые младшие группы. Одновременно на первом сумматоре 12 суммируются значения кодов общего количества групп 1К и 2К с учетом значения флага декрементации FD, на третьем сумматоре 17 суммируются значения кодов 1U и 2U количества (суммы) единичных бит в первых и вторых секциях, с выходов которых поступают соответственно на группы выходов К и U соответствующих блоков.

Например, в соответствии с таблицей 3, для значений входов 1k0=1, 1LB=0 и 2LB=0 (четвертая строка №=4 таблицы 3 когда первая секция содержит нечетное количество групп (1k0=1), а первые младшие группы первой 1G1⁰ и второй 2G1⁰ секций содержат нулевые бит при 1Кнч=1 или старшая группа 1G3⁰ первой секции и младшая группа 2G1⁰ второй секции также содержат нулевые бит при 1Кнч=3) формируется флаг декрементации FD=1 (таблица 4), который указывает, что соседние группы содержат нулевые бит и их необходимо объединить в одну группу и внести коррекцию в значение кода сдвига SK и уменьшить на единицу сумму общего количества групп 1К и 2К первой и второй секций.

Далее аналогично проводится формирование значений кодов групп для третьей, четвертой, …, Z-ой ступеней. На фиг. 3 приведены форматы выходных данных Q на внешних выходах 24 и разрядность соответствующих групп.

Кроме того, выход группы QU количества (суммы) единичных бит поступает на группу входов модуля 4 формирования флагов устройства, на вторую группу входов которого поступает двоичный код «N», соответствующий количеству разрядов входного двоичного числа D1, D2, …, DN. В соответствии с таблицей 5 на выходах модуля 4 формируются: значения флага FE «СУММА НУЛЕЙ РАВНА СУММЕ ЕДИНИЦ», флага F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ», флага F01 «НУЛЕЙ БОЛЬШЕ ЕДИНИЦ», а также значение кода QZ количества (суммы) нулевых бит и значение кода Q01 разности между количеством (суммами) нулевых и единичных бит.

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

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

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

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

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

Таким образом, на выходах предлагаемого устройства формируются двоичные коды, соответствующие количеству нулевых QG⁰ и единичных QG¹ бит в группах входного двоичного числа, а также формируются общее количество групп QК, общее количество (сумма) единичных QU и нулевых QZ бит и значение кода разности Q01 между ними и соответствующие флаги FE, F01, F10. В предлагаемом устройстве пирамидальной структуры на каждой ступени вдвое увеличивается количество возможных групп нулевых QG⁰ и единичных QG¹ бит.

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

Изобретение относится к области вычислительной техники, в частности к устройствам обработки данных, и может быть использовано для построения средств автоматики и функциональных узлов систем управления, для анализа свойств генераторов псевдослучайных последовательностей двоичных чисел, а также для обработки результатов физических экспериментов. Техническим результатом является обеспечение возможности выявления групп единичных и нулевых бит в двоичных числах, а также простое увеличение разрядности входной информации при сокращении аппаратных затрат. Устройство содержит N разрядов входного двоичного числа которые разделены на N/2 групп по два разряда в группе, Z ступеней блоков элементов, где Z=]log₂N[ (] [ - большее целое), и модуль формирования флагов устройства, причем первая ступень содержит N/2 блоков элементов первого типа, а каждая i-ая ступень, начиная со второй ступени до Z-й ступени, содержит по N/2ⁱ блоков элементов второго типа. 3 ил., 5 табл.

Устройство пирамидальной структуры для детектирования групп нулевых и единичных бит и определение их количества содержит N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на N/2 групп по два разряда в группе, Z ступеней блоков элементов, где Z=]log₂N[ (] [ - большее целое), и модуль формирования флагов устройства 4,

причем первая ступень содержит N/2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа, а каждая i-ая ступень, начиная со второй ступени до Z-й ступени, содержит по N/2ⁱ блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, N/2ⁱ,

причем N разрядов входного двоичного числа D1, D2, …, DN группами по два разряда соединены с входами соответствующих одноименных входным группам блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени, выходы нечетных блоков элементов 1₁, 1₃, …, 1_(N/2-1)(нч) и выходы четных блоков элементов 1₂, 1₄, …, 1_N/2(чт) первой ступени попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2₂₁, 2₂₂, …, 2_2N/4 второго типа второй ступени, а выходы нечетных блоков элементов 2ij(нч) и выходы четных блоков элементов 2ij(чт) каждой i-й ступени, начиная со второй ступени до предпоследней (Z-1)-й ступени, попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2ij последующих ступеней, начиная с третьей ступени до последней Z-й ступени, а выходы групп блока элементов 2zj последней Z-й ступени являются соответствующими группами Q внешних одноименных выходов устройства группы QK общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, N групп QG1, QG2, …, QGN нулевых и единичных бит и выход QLB, соответствующий левому биту входного двоичного числа D1,

каждый из N/2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени содержит элемент «ЭКВИВАЛЕНТНОСТИ» 5, первый элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 и элемент И 7,

причем пары разрядов каждой из N/2 групп входного двоичного числа D1, D2, …, DN, начиная с первого разряда, соединены соответственно с входами А1 и А2 соответствующих одноименных блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени одноименных группам N/2, при этом входы А1 и А2 соединены с первыми и вторыми входами элемента «ЭКВИВАЛЕНТНОСТИ» 5, первого элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 и элемента И 7, а также первый вход А1 соединен с выходом левого бита LB блока первого типа 1, выход элемента «ЭКВИВАЛЕНТНОСТИ» 5 соединен с первым разрядом g11 первой выходной группы G1 бит и нулевым разрядом k0 выходной группы К общего количества групп единичных и нулевых бит, выход первого элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 6 соединен с нулевым разрядом g10 первой выходной группы G1 бит, с нулевым разрядом g20 второй выходной группы G2 бит, с первым разрядом k1 выходной группы К общего количества групп единичных и нулевых бит и с нулевым разрядом u0 выходной группы U количества единичных бит, выход элемента И 7 соединен с первым разрядом u1 выходной группы U количества единичных бит,

каждый блок элементов 2_ij второго типа второй, третьей, …, Z-й ступени содержит второй элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, дешифратор DC 9, вычитатель SB 10, группу мультиплексоров MX 11, первый сумматор SM 12, второй сумматор SM 13, модуль сдвига групп SF 14, группы элементов И с одним инверсным входом 15, группы элементов ИЛИ 16 и третий сумматор SM 17,

причем вход 1LB левого бита первой секции соединен с выходом левого бита LB блока второго типа 2, все 2^(i-1) входных групп первых секций, начиная с первой 1G1 группы до последней 1G(2^(i-1)) группы, соединены с первыми прямыми входами элементов соответствующих одноименных групп элементов И с одним инверсным входом 15 и также соединены с соответствующими информационными входами группы мультиплексоров MX 11, выходы которых соединены с группой входов первого слагаемого второго сумматора 13, у которого группа входов второго слагаемого соединена с первой группой 2G1 второй секции, а выход второго сумматора 13 соединен с первой группой входов модуля сдвига групп SF 14, у которого (2^(i-1)-1) входных групп, начиная со второй группы до последней группы, соединены с соответствующими одноименными группами 2G второй секции, начиная со второй 2G2 группы до последней 2G(2^(i-1)) группы, а первые 2^(i-1) выходов модуля сдвига групп SF 14, начиная с первого выхода до 2^(i-1) выхода, соединены со вторыми входами элементов соответствующих одноименных групп элементов ИЛИ 16, первые входы которых соединены с соответствующими одноименными выходами элементов групп элементов И с одним инверсным входом 15,

кроме того, в блоках 2 второго типа вход 1LB левого бита первой секции, вход 2LB левого бита второй секции и младший нулевой разряд 1k0 группы 1К общего количества групп единичных и нулевых бит первой секции соединены с соответствующими входами второго элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 8, выход которого соединен с входом разрешения работы Е дешифратора DC 9 и вторым входом вычитателя SB 10, входная группа 1К общего количества групп единичных и нулевых бит первой секции соединена с первой группой входов вычитателя SB и с группой входов дешифратора DC 9, а выходы вычитателя SB 10 соединены с шиной SK задания значения количества сдвигов, которая подключена к группе управляющих входов модуля сдвига групп SF 14 и к группе входов первого слагаемого первого сумматора SM 12, у которого группа входов второго слагаемого соединена с входной группой 2К общего количества групп единичных и нулевых бит второй секции, входные группы 1U и 2 U количества единичных бит первой и второй секций соединены с группами входов первого и второго слагаемых третьего сумматора SM 17, выходы дешифратора DC 9 соединены с соответствующими управляющими входами выборки группы мультиплексоров MX 11 и со вторыми инверсными входами элементов соответствующих одноименных групп элементов И с одним инверсным входом 15,

причем выходы групп элементов ИЛИ 16 являются первыми 2^(i-1) выходами групп блоков 2, начиная с первой G1 группы до G(2^(i-1)) группы, а выходы групп модуля сдвига групп SF 14, начиная с группы (2^(i-1)+1) выходов до группы 2ⁱ выходов, являются соответствующими одноименными выходами групп блоков 2, начиная с группы G(2^(i-1)+1) выходов до группы G2ⁱ выходов, и кроме того выходы первого сумматора SM 12 являются группой выходов К общего количества групп единичных и нулевых бит блоков 2, а выходы третьего сумматора SM 17 являются группой выходов U количества единичных бит,

модуль формирования флагов устройства 4 содержит четвертый сумматор SM с инверсной группой входов 18, пятый сумматор SM с инверсной группой входов 19, первый элемент ИЛИ-НЕ 20, третью группу элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21, второй элемент ИЛИ-НЕ 22 и инкрементор SI 23,

причем группа выходов U количества единичных бит с последней Z-й ступени соединена с первой группой входов модуля 4 формирования флагов устройства, у которого на вторую группу входов подан код двоичного числа «N», соответствующий количеству разрядов входного двоичного числа D1, D2, …, DN, при этом первая группа входов модуля 4 формирования флагов устройства соединена с первыми инверсными группами входов первых слагаемых пятого сумматора 19 и четвертого сумматора 18, при этом у четвертого сумматора 18 на вторую прямую группу входов второго слагаемого подан код двоичного числа «N» и на вход переноса CI которого подано значение логической единицы «1», а группа выходов четвертого сумматора 18 является группой внешних выходов QZ количества нулевых бит во входном двоичном числе D1, D2, …, DN и также соединена со второй прямой группой входов второго слагаемого пятого сумматора 19, у которого на вход переноса CI подано значение логической единицы «1», а разряды группы выходов пятого сумматора 19 соединена с соответствующими входами первого элемента ИЛИ-НЕ 20 и с первыми входами соответствующих одноименных элементов из третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21, вторые входы которых соединены между собой и подключены к инверсному выходу переноса СО пятого сумматора 19, который также соединен со вторым входом инкрементора SI 23, со вторым входом второго элемента ИЛИ-НЕ 22 и является внешним выходом флага F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ», выход первого элемента ИЛИ-НЕ 20 является внешним выходом флага FE «СУММА НУЛЕЙ РАВНА СУММЕ ЕДИНИЦ» и также соединен с первым входом второго элемента ИЛИ-НЕ 22, выход которого является внешним выходом флага F01 «НУЛЕЙ БОЛЬШЕ ЕДИНИЦ», выходы третьей группы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 21 соединены с соответствующими разрядами первой группы входов инкрементора SI 23, выходы которого являются группой внешних выходов Q01 разности между количеством нулевых и единичных бит,

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