УСТРОЙСТВО КАСКАДНОЙ СТРУКТУРЫ ДЛЯ ДЕТЕКТИРОВАНИЯ ГРУПП НУЛЕВЫХ И ЕДИНИЧНЫХ БИТ, ОПРЕДЕЛЕНИЕ ИХ КОЛИЧЕСТВА И МАКСИМАЛЬНЫХ ГРУПП Российский патент 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-й внутренней шины Si из группы шин S₁, S₂, …, S_(N-i), а также в устройство введены первая группа из (N-i) блоков счета младших упорядоченных единиц 4₁, 4₂, …, 4_(N-i), группа из N сумматоров 5₁, 5₂, …, 5_N, с инверсной группой входов второго слагаемого, элемент ИЛИ с одним инверсным входом 6 и второй блок счета младших упорядоченных единиц 7, причем каждый i-й сумматор 5i содержит ]log₂(N+3-i)[(большее целое) разрядов, последний N-й сумматор 5_N содержит два разряда, а выходы количества групп К содержат]log₂(N+1)[(большее целое) разрядов.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство групповой структуры для детектирования групп нулевых и единичных бит и определение их количества (RU №2680762, МПК G06F 7/74, заявлено 13.04.2018, опубликовано 26.02.2019, Бюл. №6), содержащее N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на L групп по М разрядов в группе (N=L*M), Z ступеней блоков элементов, где Z=]log₂L[+1 (большее целое), причем первая ступень содержит L блоков элементов 1₁, 1₂, …, 1_L первого типа, а каждая i-ая ступень, содержит по L/2^(i-1) блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, …, L/2^(i-1), каждый блок элементов 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), элемент ИЛИ с одним инверсным входом 6, группу из (М-1) модулей счета младших упорядоченных единиц 7₁, 7₂, …, 7_(M-1), первую группу из М сумматоров 8₁, 8₂, …, 8_M, модуль счета единиц 9 и второй многогрупповой сумматор 10, каждый блок элементов 2ij второго типа содержит третью группу из (M*2^(i-2)+1) сумматоров 11, четвертый сумматор 12, модуль сдвига групп 13, модуль формирования кода сдвига и кода общего количества групп 14, который содержит первый 15 и второй 16 элементы И с одним инверсным входом, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, пятый 18, шестой 19 и седьмой 20 сумматоры.

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

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

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

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

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

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

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

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

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

причем первая ступень содержит 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 внешних одноименных выходов устройства группы QVG общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, групп первой QG1 и последней QG2 групп, подряд идущих нулевых или единичных бит, группы QMU максимального количества единичных бит и группы QMZ максимального количества нулевых бит, а также выходы бит QLB1 и QLB2 указателей типа первой и последней групп, бита QK четности/нечетности количества групп,

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

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

а также первый вход А1 соединен с выходом бита LB1 указателя типа первой группы блока первого типа 1, выход первого элемента «ЭКВИВАЛЕНТНОСТИ» 3 соединен с первым разрядом g11 первой выходной группы G1 бит, нулевым разрядом vg0 выходной группы VG общего количества групп единичных и нулевых бит и выходным битом К четности/нечетности количества групп, выход первого элемента И с одним инверсным входом 4 соединен с выходом бита LB2 указателя типа второй группы блока первого типа 1, выход элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5 соединен с нулевым разрядом g10 первой выходной группы G1 бит, с нулевым разрядом g20 второй выходной группы G2 бит, с первым разрядом vg1 выходной группы VG общего количества групп единичных и нулевых бит, с нулевым разрядом u0 выходной группы U количества единичных бит, с нулевым разрядом mu0 выходной группы MU количества единичных бит, с нулевым разрядом mz0 выходной группы MZ количества нулевых бит, выход второго элемента И 6 соединен с первым разрядом u1 выходной группы U количества единичных бит и с первым разрядом mu1 выходной группы MU количества единичных бит, выход третьего элемента И с инверсными входами 7 соединен с первым разрядом mz1 выходной группы MZ количества нулевых бит,

каждый блок элементов 2_ij второго типа второй, третьей, Z-ой ступени содержит третий сумматор SM 8, вычитатель SB 9, блок управления 10, первую группу элементов И 18, вторую группу элементов И 19, первую группу элементов ИЛИ 20, элемент ИЛИ 21, второй сумматор SM2 22, первый сумматор SM1 23, третью группу элементов И 24, первую группу мультиплексоров MX 25, первый компаратор СМР 26, вторую группу мультиплексоров MX 27, второй компаратор СМР 28, восьмой элемент И 29, третью группу мультиплексоров MX 30, третий компаратор СМР 31, четвертую группу мультиплексоров MX 32, четвертый компаратор СМР 33, девятый элемент И с одним инверсным входом 34, пятую группу мультиплексоров MX 35 и четвертый сумматор SM 36,

причем блок управления 10 содержит второй элемент «ЭКВИВАЛЕНТНОСТИ» 11, третий элемент «ЭКВИВАЛЕНТНОСТИ» 12, мультиплексор MX 13, четвертый элемент И с одним инверсным входом 14, пятый элемент И с одним инверсным входом 15, шестой элемент И 16 и седьмой элемент И 17, а вход бита 1LB1 указателя типа первой группы первой секции соединен со вторым входом третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12, вход бита 1LB2 указателя типа второй группы первой секции соединен с первым входом второго элемента «ЭКВИВАЛЕНТНОСТИ» 11, вход бита 2LB1 указателя типа первой группы второй секции соединен со вторым входом второго элемента «ЭКВИВАЛЕНТНОСТИ» 11 и первым входом третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12, вход бита 1К четности/нечетности первой секции соединен с первым инверсным входом пятого элемента И с одним инверсным входом 15, с первым входом шестого элемента И 16, с первым входом седьмого элемент И 17 и с адресным входом S мультиплексора 13, вход бита 2К четности/нечетности второй секции соединен со вторым прямым входом четвертого элемента И с одним инверсным входом 14, с третьим прямым входом пятого элемента И с одним инверсным входом 15 и с третьим прямым входом шестого элемента И 16, выход второго элемента «ЭКВИВАЛЕНТНОСТИ» 11 соединен со вторым прямым входом пятого элемента И с одним инверсным входом 15 и с нулевым информационным входом мультиплексора 13, выход третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12 соединен первым информационным входом мультиплексора 13, со вторым входом шестого элемента И 16 и со вторым входом седьмого элемент И 17, выход мультиплексора 13 соединен с первым инверсным входом четвертого элемента И с одним инверсным входом 14 и является флагом декрементации FD, выход четвертого элемента И с одним инверсным входом 14 является выходом первого сигнала разрешения U21, выход пятого элемента И с одним инверсным входом 15 является выходом второго сигнала разрешения US2, выход седьмого элемент И 17 является выходом третьего сигнала разрешения US1, выход шестого элемента И 16 соединен с выходом бита К четности/нечетности блока элементов 2_ij второго типа,

причем в каждом блоке элементов 2_ij второго типа группы общего количества групп единичных и нулевых бит первой секции 1VG и второй секции 2VG соединены с соответствующими группами входов третьего сумматора SM 8, группа выходов которого соединена с первой группой входов вычитателя SB 9, второй вход которого соединен с выходом флага декрементации FD блока управления 10, а выход вычитателя SB 9 является выходом группы VG общего количества групп единичных и нулевых бит блока элементов 2_ij второго типа,

разряды входов второй группы бит 2G2 второй секции соединены с первыми входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а бит 2LB2 указателя типа второй группы бит 2G2 второй секции соединен с первым входом элемента ИЛИ 21,

разряды входов первой группы бит 2G1 второй секции соединены с первыми входами одноименных элементов И из первой группы 18 элементов И, с соответствующими разрядами первой группы входов второго сумматора SM2 22 и с первыми входами одноименных элементов И из третьей группы 24 элементов И, вторые входы элементов И из третьей группы 24 элементов И соединены между собой и подключены к выходу третьего сигнала разрешения US1 блока управления 10, а бит 2LB1 указателя типа первой группы бит 2G1 второй секции соединен с первым входом соответствующего элемента И из первой группы 18 элементов И, при этом вторые входы всех элементов И из первой группы 18 элементов И соединены между собой и подключены к выходу первого сигнала разрешения U21 блока управления 10, а разряды первой группы выходов элементов И из первой группы 18 элементов И соединены соответственно со вторыми входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а второй выход элементов И из первой группы 18 элементов И соединен со вторым входом элемента ИЛИ 21,

разряды входов второй группы бит 1G2 первой секции соединены с соответствующими разрядами второй группы входов второго сумматора SM2 22, разряды выходов которого соединены с первыми входами одноименных элементов И из второй группы 19 элементов И и с соответствующими одноименными разрядами информационной нулевой группы входов первой группы мультиплексоров MX 25, а бит 1LB2 указателя типа второй группы бит 1G2 первой секции соединен с соответствующим разрядом информационной нулевой группы входов первой группы мультиплексоров MX 25 и с первым входом соответствующего элемента И из второй группы 19 элементов И, при этом вторые входы всех элементов И из второй группы 19 элементов И соединены между собой и подключены к выходу первого сигнала разрешения U21 блока управления 10, а разряды первой группы выходов элементов И из второй группы 19 элементов И соединены соответственно с третьими входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а второй выход второй группы 19 элементов И соединен с третьим входом элемента ИЛИ 21,

разряды входов первой группы бит 1G1 первой секции соединены с соответствующими разрядами второй группы входов первого сумматора SM1 23, первая группа входов которого соединена с соответствующими выходами элементов И из третьей группы 24 элементов И, а группа выходов SM1 первого сумматора 23 соединена с соответствующими одноименными разрядами информационной первой группы входов первой группы мультиплексоров MX 25, а бит 1LB1 указателя типа первой группы бит 1G1 первой секции соединен с соответствующим разрядом информационной первой группы входов первой группы мультиплексоров MX 25 и является выходом бита LB1 указателя типа первой группы блока элементов 2_ij второго типа, а группа выходов SM1 первого сумматора 23 является также группой бит G1 выходов первой группы блока элементов 2_ij второго типа,

выходы элементов ИЛИ из первой группы 20 элементов ИЛИ являются группой бит G2 выходов второй группы, а выход элемента ИЛИ 21 является выходом бита LB2 указателя типа второй группы блока элементов 2_ij второго типа,

причем у первой группы мультиплексоров MX 25 адресные входы S мультиплексоров соединены между собой и подключены к входу 1К бита четности/нечетности количества групп в первой секции блока элементов 2_ij второго типа, а входы Е разрешения работы группы мультиплексоров MX 25 соединены между собой и соединены с выходом флага декрементации FD блока управления 10,

кроме того группы максимального количества единичных бит первой секции 1MU и второй секции 2MU соединены соответственно с первыми и вторыми группами входов первого компаратора СМР 26 и информационными нулевой и первой группами второй группы мультиплексоров MX 27, у которого адресный вход S соединен с выходом первого компаратора СМР 26, а группа выходов 12MU второй группы мультиплексоров MX 27 соединена со второй группой входов второго компаратора СМР 28 и нулевой информационной группой третьей группы мультиплексоров MX 30,

кроме того группы максимального количества нулевых бит первой секции 1MZ и второй секции 2MZ соединены соответственно с первыми и вторыми группами входов третьего компаратора СМР 31 и информационными нулевой и первой группами четвертой группы мультиплексоров MX 32, у которого адресный вход S соединен с выходом третьего компаратора СМР 31, а группа выходов 12MZ четвертой группы мультиплексоров MX 32 соединена со второй группой входов четвертого компаратора СМР 33 и нулевой информационной группой пятой группы мультиплексоров MX 35,

причем вторая группа выходов GSM первой группы мультиплексоров MX 25 соединена с первыми информационными группами третьей группы мультиплексоров MX 30 и пятой группы мультиплексоров MX 35, а также соединены с первыми группами входов второго компаратора СМР 28 и четвертого компаратора СМР 33 выходы которых соединены соответственно со вторыми прямыми входами восьмого элемента И 29 и девятого элемента И 34, выходы которых соединены с адресными входами S соответственно третьей группы мультиплексоров MX 30 и пятой группы мультиплексоров MX 35, а первый выход первой группы мультиплексоров MX 25 соответствующий биту LBSM указателя типа группы соединен с первым инверсным входом восьмого элемента И 29 и первым прямым входом девятого элемента И 34,

причем группа выходов третьей группы мультиплексоров MX 30 является группой выходов MU максимального количества единичных бит, а группа выходов пятой группы мультиплексоров MX 35 является группой выходов MZ максимального количества нулевых бит блока элементов 2_ij второго типа,

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

блок формирования кода разности 37 содержит пятый сумматор SM с инверсной группой входов 38, вторую группу из (М-2) элементов ИЛИ 39, девятую группу из (М-1) элементов И 40 и группу из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 41, где M=[log₂N]+1 (меньшее целое),

причем группа выходов U количества единичных бит с последней Z-ой ступени соединена с первой группой входов блока формирования кода разности 37, у которого на вторую группу входов подан код двоичного числа «N», соответствующий количеству разрядов входного двоичного числа D1, D2,…, DN,

при этом первая группа входов блока формирования кода разности 37 соединена со второй группой входов первой инверсной группы входов первого слагаемого пятого сумматора 38, а на вход младшего разряда первой инверсной группы входов подано значение логической единицы «1», при этом у пятого сумматора 38 на первую группу входов второй прямой группы входов второго слагаемого подан код двоичного числа «N», а на вход старшего разряда второй прямой группы входов подано значение логического нуля «0», а также на вход переноса CI пятого сумматора 38 подано значение логической единицы «1»,

причем в блоке формирования кода разности 37 вторые входы элементов ИЛИ, второй группы 39 из (М-2) элементов ИЛИ, соединены с соответствующими разрядами выходов пятого сумматора 38, начиная со второго разряда до (M-1)-го разряда, а первые входы элементов ИЛИ 39, начиная со второго до последнего (М-2)-го элемента, соединены с соответствующими выходами предыдущих элементов ИЛИ 39, начиная с первого до предпоследнего (М-3)-го элемента, а первый вход первого элемента ИЛИ 39 соединен с первым разрядом выходов пятого сумматора 38,

вторые входы всех элементов И, девятой группы 40 из (М-1) элементов И, соединены между собой и соединены с инверсным выходом переноса СО пятого сумматора 38, а первый вход первого элемента И, из девятой группы 40 из (М-1) элементов И, соединен с первым разрядом выходов пятого сумматора 38, а первые входы элементов И, из девятой группы 40 из (М-1) элементов И, начиная со второго до последнего (М-1), соединены с соответствующими выходами элементов ИЛИ, второй группы 39 из (М-2) элементов ИЛИ, начиная с первого до (М-2)-го элемента ИЛИ,

выходы элементов И, из девятой группы 40 из (М-1) элементов И, соединены с соответствующими первыми входами одноименных элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», группы 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», вторые входы которых соединены с соответствующими разрядами выходов пятого сумматора 38, начиная со второго разряда до М-го разряда,

а выходы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», группы 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», являются (М-1) разрядами группы QZU внешних выходов «разность единиц и нулей», блока формирования кода разности 37, начиная со второго выхода до последнего М-го выхода группы QZU, а первый разряд внешних выходов QZU блока формирования кода разности 37 соединен с первым разрядом выходов пятого сумматора 38, а инверсный выход переноса СО пятого сумматора 38 является внешним выходом флага F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ».

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

На фиг. 1 представлена структурная схема предлагаемого устройства каскадной структуры для детектирования групп нулевых и единичных бит, определение их количества и максимальных групп. На фиг. 2 представлена функциональная схема блока 1 элементов первого типа первой ступени. На фиг. 3 представлена функциональная схема блока элементов 2_ij второго типа второй, третьей, Z-ой ступени. На фиг. 4 приведена схема блока формирования кода разности 37. В таблице 1 приведены значения выходных функций для блоков 1 первого типа первой ступени. В таблице 2 приведены примеры объединения соседних групп, подряд идущих единичных или нулевых бит, формирования флага декрементации FD и формирования бита К четности/нечетности количества групп.

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

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

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

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

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

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

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

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

LB - бит указателя типа групп (единичных или нулевых),

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

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

К - бит четности/нечетности количества групп,

GSM - группа бит от сумматоров,

LBSM - бит указателя типа групп от сумматоров,

MG1-MG4 - объединенные соседние группы,

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

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

12MU - группа максимального количества единичных бит 1-ой и 2-ой секций,

MZ - группа максимального количества нулевых бит,

12MZ - группа максимального количества нулевых бит 1 -ой и 2-ой секций,

Е - вход разрешения работы мультиплексора,

S - адресный вход мультиплексора,

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

SM - сумматор,

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

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

SM1 - выходы первого сумматора сложения первой 1G1 группы 1-ой секции и первой 2G1 группы 2-ой секции,

SM2 - выходы второго сумматора сложения второй 1G2 группы 1-ой секции и первой 2G1 группы 2-ой секции,

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

F10 - внешний флаг «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ»,

СМР - компаратор,

1LB1, 1G1, 1LB2, 1G2, 1K, 1VG, 1U, 1MU, 1MZ - группы входов первых секций

блоков элементов 2_ij второго типа,

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

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

2LB1, 2G1, 2LB2, 2G2, 2К, 2VG, 2U, 2MU, 2MZ - группы входов вторых секций

блоков элементов 2ij второго типа,

U21 - первый сигнал разрешения передачи первой 2G1 группы второй секции на выходы второй группы блока 2,

US1 - второй сигнал разрешения передачи первой 2G1 группы второй секции на входы первого сумматора SM1,

US2 - третий сигнал разрешения передачи выходов второго сумматора SM2 на выходы второй группы блока 2,

QLB1, QG1, QLB2, QG2, QK, QVG, QU, QMU, QMZ - группы выходов устройства,

QZU - группа внешних выходов «разность единиц и нулей»,

ZU - шина кода «разность единиц и нулей»,

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

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

3 - первый элемент «ЭКВИВАЛЕНТНОСТИ (РАВНОЗНАЧНОСТИ)» (XNOR),

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

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

6 - второй элемент И,

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

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

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

10 - блок управления,

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

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

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

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

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

16 - шестой элемент И,

17 - седьмой элемент И,

18 - первая группа элементов И,

19 - вторая группа элементов И,

20 - первая группа элементов ИЛИ,

21 - элемент ИЛИ,

22 - второй сумматор SM2,

23 - первый сумматор SM1,

24 - третья группа элементов И,

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

26 - первый компаратор СМР,

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

28 - второй компаратор СМР,

29 - восьмой элемент И,

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

31 - третий компаратор СМР,

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

33 - четвертый компаратор СМР,

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

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

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

37 - блок формирования кода разности,

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

39 - вторая группа элементов ИЛИ,

40 - девятая группа элементов И,

41 - группа элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ».

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

Причем первая ступень содержит 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-ой ступени (фиг. 1).

Выходы групп блока элементов 2zj последней Z-ой ступени являются соответствующими группами Q внешних одноименных выходов устройства группы QVG общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, групп первой QG1 и последней QG2 групп, подряд идущих нулевых или единичных бит, группы QMU максимального количества единичных бит и группы QMZ максимального количества нулевых бит, а также выходы бит QLB1 и QLB2 указателей типа первой и последней групп, бита QK четности/нечетности количества групп.

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

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

Выход первого элемента «ЭКВИВАЛЕНТНОСТИ» 3 соединен с первым разрядом g11 первой выходной группы G1 бит, нулевым разрядом vg0 выходной группы VG общего количества групп единичных и нулевых бит и выходным битом К четности/нечетности количества групп.

Выход первого элемента И с одним инверсным входом 4 соединен с выходом бита LB2 указателя типа второй группы блока первого типа 1.

Выход элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5 соединен с нулевым разрядом g10 первой выходной группы G1 бит, с нулевым разрядом g20 второй выходной группы G2 бит, с первым разрядом vg1 выходной группы VG общего количества групп единичных и нулевых бит, с нулевым разрядом u0 выходной группы U количества единичных бит, с нулевым разрядом mu0 выходной группы MU количества единичных бит, с нулевым разрядом mz0 выходной группы MZ количества нулевых бит.

Выход второго элемента И 6 соединен с первым разрядом u1 выходной группы U количества единичных бит и с первым разрядом mu1 выходной группы MU количества единичных бит.

Выход третьего элемента И с инверсными входами 7 соединен с первым разрядом mz1 выходной группы MZ количества нулевых бит.

Каждый блок элементов 2_ij (фиг. 3) второго типа второй, третьей, …, Z-ой ступени содержит третий сумматор SM 8, вычитатель SB 9, блок управления 10, первую группу элементов И 18, вторую группу элементов И 19, первую группу элементов ИЛИ 20, элемент ИЛИ 21, второй сумматор SM2 22, первый сумматор SM1 23, третью группу элементов И 24, первую группу мультиплексоров MX 25, первый компаратор СМР 26, вторую группу мультиплексоров MX 27, второй компаратор СМР 28, восьмой элемент И 29, третью группу мультиплексоров MX 30, третий компаратор СМР 31, четвертую группу мультиплексоров MX 32, четвертый компаратор СМР 33, девятый элемент И с одним инверсным входом 34, пятую группу мультиплексоров MX 35 и четвертый сумматор SM 36.

Причем блок управления 10 содержит второй элемент «ЭКВИВАЛЕНТНОСТИ» 11, третий элемент «ЭКВИВАЛЕНТНОСТИ» 12, мультиплексор MX 13, четвертый элемент И с одним инверсным входом 14, пятый элемент И с одним инверсным входом 15, шестой элемент И 16 и седьмой элемент И 17.

Вход бита 1LB1 указателя типа первой группы первой секции соединен со вторым входом третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12, вход бита 1LB2 указателя типа второй группы первой секции соединен с первым входом второго элемента «ЭКВИВАЛЕНТНОСТИ» 11. Вход бита 2LB1 указателя типа первой группы второй секции соединен со вторым входом второго элемента «ЭКВИВАЛЕНТНОСТИ» 11 и первым входом третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12.

Вход бита 1К четности/нечетности первой секции соединен с первым инверсным входом пятого элемента И с одним инверсным входом 15, с первым входом шестого элемента И 16, с первым входом седьмого элемент И 17 и с адресным входом S мультиплексора 13. Вход бита 2К четности/нечетности второй секции соединен со вторым прямым входом четвертого элемента И с одним инверсным входом 14, с третьим прямым входом пятого элемента И с одним инверсным входом 15 и с третьим прямым входом шестого элемента И 16.

Выход второго элемента «ЭКВИВАЛЕНТНОСТИ» 11 соединен со вторым прямым входом пятого элемента И с одним инверсным входом 15 и с нулевым информационным входом мультиплексора 13. Выход третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12соединен первым информационным входом мультиплексора 13, со вторым входом шестого элемента И 16 и со вторым входом седьмого элемент И 17.

Выход мультиплексора 13 соединен с первым инверсным входом четвертого элемента И с одним инверсным входом 14 и является флагом декрементации FD. Выход четвертого элемента И с одним инверсным входом 14 является выходом первого сигнала разрешения U21. Выход пятого элемента И с одним инверсным входом 15 является выходом второго сигнала разрешения US2. Выход седьмого элемент И 17 является выходом третьего сигнала разрешения US1 Выход шестого элемента И 16 соединен с выходом бита К четности/нечетности блока элементов 2_ij второго типа.

Причем в каждом блоке элементов 2_ij второго типа группы общего количества групп единичных и нулевых бит первой секции 1VG и второй секции 2VG соединены с соответствующими группами входов третьего сумматора SM 8, группа выходов которого соединена с первой группой входов вычитателя SB 9, второй вход которого соединен с выходом флага декрементации FD блока управления 10. Выход вычитателя SB 9 является выходом группы VG общего количества групп единичных и нулевых бит блока элементов 2_ij второго типа.

Разряды входов второй группы бит 2G2 второй секции соединены с первыми входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а бит 2LB2 указателя типа второй группы бит 2G2 второй секции соединен с первым входом элемента ИЛИ 21.

Разряды входов первой группы бит 2G1 второй секции соединены с первыми входами одноименных элементов И из первой группы 18 элементов И, с соответствующими разрядами первой группы входов второго сумматора SM2 22 и с первыми входами одноименных элементов И из третьей группы 24 элементов И. Вторые входы элементов И из третьей группы 24 элементов И соединены между собой и подключены к выходу третьего сигнала разрешения US1 блока управления 10.

Бит 2LB1 указателя типа первой группы бит 2G1 второй секции соединен с первым входом соответствующего элемента И из первой группы 18 элементов И, при этом вторые входы всех элементов И из первой группы 18 элементов И соединены между собой и подключены к выходу первого сигнала разрешения U21 блока управления 10.

Разряды первой группы выходов элементов И из первой группы 18 элементов И соединены соответственно со вторыми входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а второй выход элементов И из первой группы 18 элементов И соединен со вторым входом элемента ИЛИ 21.

Разряды входов второй группы бит 1G2 первой секции соединены с соответствующими разрядами второй группы входов второго сумматора SM2 22, разряды выходов которого соединены с первыми входами одноименных элементов И из второй группы 19 элементов И и с соответствующими одноименными разрядами информационной нулевой группы входов первой группы мультиплексоров MX 25.

Бит 1LB2 указателя типа второй группы бит 1G2 первой секции соединен с соответствующим разрядом информационной нулевой группы входов первой группы мультиплексоров MX 25 и с первым входом соответствующего элемента И из второй группы 19 элементов И. При этом вторые входы всех элементов И из второй группы 19 элементов И соединены между собой и подключены к выходу первого сигнала разрешения U21 блока управления 10. Разряды первой группы выходов элементов И из второй группы 19 элементов И соединены соответственно с третьими входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а второй выход второй группы 19 элементов И соединен с третьим входом элемента ИЛИ 21.

Разряды входов первой группы бит 1G1 первой секции соединены с соответствующими разрядами второй группы входов первого сумматора SM1 23, первая группа входов которого соединена с соответствующими выходами элементов И из третьей группы 24 элементов И. Группа выходов SM1 первого сумматора 23 соединена с соответствующими одноименными разрядами информационной первой группы входов первой группы мультиплексоров MX 25. Бит 1LB1 указателя типа первой группы бит 1G1 первой секции соединен с соответствующим разрядом информационной первой группы входов первой группы мультиплексоров MX 25 и является выходом бита LB1 указателя типа первой группы блока элементов 2_ij второго типа. Группа выходов SM1 первого сумматора 23 является также группой бит G1 выходов первой группы блока элементов 2_ij второго типа.

Выходы элементов ИЛИ из первой группы 20 элементов ИЛИ являются группой бит G2 выходов второй группы. Выход элемента ИЛИ 21 является выходом бита LB2 указателя типа второй группы блока элементов 2_ij второго типа.

Причем у первой группы мультиплексоров MX 25 адресные входы S мультиплексоров соединены между собой и подключены к входу 1К бита четности/нечетности количества групп в первой секции блока элементов 2_ij второго типа, а входы Е разрешения работы группы мультиплексоров MX 25 соединены между собой и соединены с выходом флага декрементации FD блока управления 10.

Кроме того группы максимального количества единичных бит первой секции 1MU и второй секции 2MU соединены соответственно с первыми и вторыми группами входов первого компаратора СМР 26 и информационными нулевой и первой группами второй группы мультиплексоров MX 27, у которого адресный вход S соединен с выходом первого компаратора СМР 26. Группа выходов 12MU второй группы мультиплексоров MX 27 соединена со второй группой входов второго компаратора СМР 28 и нулевой информационной группой третьей группы мультиплексоров MX 30.

Кроме того группы максимального количества нулевых бит первой секции 1MZ и второй секции 2MZ соединены соответственно с первыми и вторыми группами входов третьего компаратора СМР 31 и информационными нулевой и первой группами четвертой группы мультиплексоров MX 32, у которого адресный вход S соединен с выходом третьего компаратора СМР 31. Группа выходов 12MZ четвертой группы мультиплексоров MX 32 соединена со второй группой входов четвертого компаратора СМР 33 и нулевой информационной группой пятой группы мультиплексоров MX 35.

Причем вторая группа выходов GSM первой группы мультиплексоров MX 25 соединена с первыми информационными группами третьей группы мультиплексоров MX 30 и пятой группы мультиплексоров MX 35, а также соединены с первыми группами входов второго компаратора СМР 28 и четвертого компаратора СМР 33 выходы которых соединены соответственно со вторыми прямыми входами восьмого элемента И 29 и девятого элемента И 34, выходы которых соединены с адресными входами S соответственно третьей группы мультиплексоров MX 30 и пятой группы мультиплексоров MX 35. Первый выход первой группы мультиплексоров MX 25 соответствующий биту LBSM указателя типа группы соединен с первым инверсным входом восьмого элемента И 29 и первым прямым входом девятого элемента И 34.

Причем группа выходов третьей группы мультиплексоров MX 30 является группой выходов MU максимального количества единичных бит, а группа выходов пятой группы мультиплексоров MX 35 является группой выходов MZ максимального количества нулевых бит блока элементов 2_ij второго типа.

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

Блок формирования кода разности 37 содержит пятый сумматор SM с инверсной группой входов 38, вторую группу из (М-2) элементов ИЛИ 39, девятую группу из (М-1) элементов И 40 и группу из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 41, где M=[log₂N]+1 (меньшее целое) (фиг. 4).

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

При этом первая группа входов блока формирования кода разности 37 соединена со второй группой входов первой инверсной группы входов первого слагаемого пятого сумматора 38. На вход младшего разряда первой инверсной группы входов подано значение логической единицы «1». При этом у пятого сумматора 38 на первую группу входов второй прямой группы входов второго слагаемого подан код двоичного числа «N», а на вход старшего разряда второй прямой группы входов подано значение логического нуля «0». Также на вход переноса CI пятого сумматора 38 подано значение логической единицы «1».

Причем в блоке формирования кода разности 37 вторые входы элементов ИЛИ, второй группы 39 из (М-2) элементов ИЛИ, соединены с соответствующими разрядами выходов пятого сумматора 38, начиная со второго разряда до (M-1)-го разряда. Первые входы элементов ИЛИ 39, начиная со второго до последнего (М-2)-го элемента, соединены с соответствующими выходами предыдущих элементов ИЛИ 39, начиная с первого до предпоследнего (М-3)-го элемента. Первый вход первого элемента ИЛИ 39 соединен с первым разрядом выходов пятого сумматора 38.

Вторые входы всех элементов И, девятой группы 40 из (М-1) элементов И, соединены между собой и соединены с инверсным выходом переноса СО пятого сумматора 38. Первый вход первого элемента И, из девятой группы 40 из (М-1) элементов И, соединен с первым разрядом выходов пятого сумматора 38. Первые входы элементов И, из девятой группы 40 из (М-1) элементов И, начиная со второго до последнего (М-1), соединены с соответствующими выходами элементов ИЛИ, второй группы 39 из (М-2) элементов ИЛИ, начиная с первого до (М-2)-го элемента ИЛИ.

Выходы элементов И, из девятой группы 40 из (М-1) элементов И, соединены с соответствующими первыми входами одноименных элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», группы 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», вторые входы которых соединены с соответствующими разрядами выходов пятого сумматора 38, начиная со второго разряда до М-го разряда.

Выходы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», группы 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», являются (М-1) разрядами группы QZU внешних выходов «разность единиц и нулей», блока формирования кода разности 37, начиная со второго выхода до последнего М-го выхода группы QZU. Первый разряд внешних выходов QZU блока формирования кода разности 37 соединен с первым разрядом выходов пятого сумматора 38. Инверсный выход переноса СО пятого сумматора 38 является внешним выходом флага F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ».

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

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

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

В блоках элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени, в соответствии с таблицей 1, для каждой пары разрядов A1, А2 формируются значения двоичных кодов групп G1 и G2, соответствующих количеству подряд идущих единичных или нулевых бит в группе, а также формируются двоичный код VG общего количества групп, двоичный код U общего количества единичных бит, двоичный код MU для группы с максимальным количеством единичных бит и двоичный код MZ для группы с максимальным количеством нулевых бит.

В устройстве для указания типа группы единичных или нулевых бит вводятся указатели типа групп LB. На выходы указателя типа групп бит LB1 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени передается значение первого левого бита А1. При этом если первая группа бит содержит нулевые биты G1⁰, то LB принимает нулевое значение LB=0, а если первая группа бит содержит единичные биты G1¹, то LB принимает единичное значение LB=1. Одновременно на выходах указателя типа групп бит LB2 устанавливается аналогично единичное значение LB2=1 или нулевое значение LB2=0 соответствующее типу второй группы, или нулевое значение LB2=0 если значения бит на входах А1 и А2 одного типа, которые объединяются в одну группу. Также на выходах бит К четности/нечетности групп устанавливается единичное значение К=1, если оба бита А1 и А2 одного типа и образуют одну группу, или нулевое значение К=0, если образованы две группы, когда биты А1 и А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 представлена структурная схема объединения блоков элементов ступеней.

В каждом блоке элементов 2_jj второго типа (где i=2, 3, …, Z, j=1, 2, N/2ⁱ) проводится анализ бит 1К и 2К четности/нечетности групп в первой и второй секциях и бит LB указателей типа групп: в первых секциях для первой группы 1LB1 и для второй группы 1LB2 и во второй секции для первой группы 2LB1. В таблице 2 приведены возможные варианты объединения соседних групп секций по группам MG1-MG4. При этом на первых SM1 сумматорах 23 проводится суммирование двоичных кодов первой группы 1G1 первой секции и первой группы 2G1 второй секции при одной группе в первой секции (при нечетности бита 1К=1, строки 4 и 7 в таблице 2), которое передается через третью группу 24 элементов И при единичном разрешающем сигнале US1=1. Далее значение с выходов первого сумматора 23 передается на первые группы информационных входов первой группы 25 мультиплексоров (коммутаторов) MX (соответствует строкам 4 и 7 в таблице 2). Одновременно на вторых SM2 сумматорах 22 проводится суммирование двоичных кодов второй группы 1G2 первой секции и первой группы 2G1 второй секции и значение с выходов сумматора 22 передается на нулевые группы информационных входов первой группы 25 мультиплексоров (коммутаторов) MX (соответствует строкам 0 и 3 в таблице 2).

На выходы группы 25 мультиплексоров (коммутаторов) MX передается значение первого сумматора 23 при единичном значении бита четности/нечетности 1К=1 и передается значение второго SM2 сумматора 22 при нулевом значении бита четности/нечетности 1К=0, которые устанавливаются на адресных входах S группы 25 мультиплексоров (коммутаторов) MX. Работа первой группы 25 мультиплексоров (коммутаторов) MX разрешается при совпадении единичных или нулевых значений указателей типа групп бита 2LB1 для первой группы второй секции и бита 1LB1 для первой группы первой секции и при одной группе в первой секции (нечетности бита 1К=1, строки 4 и 7 в таблице 2) или совпадении указателей типа групп бита 2LB1 для первой группы второй секции и бита 1LB2 для второй группы первой секции и при двух группах в первой секции (четности бита 1К=0, строки 0 и 3 в таблице 2), так как при этом формируется единичное значение флага декрементации FD=1 на выходе мультиплексора (коммутатора) MX 13, которое передается на вход Е разрешения работы первой группы 25 мультиплексоров (коммутаторов) MX.

Значение с выходов первого SM1 сумматора 23 передается на группу выходов первой группы G1 бит блока 2 элементов второго типа, а значение указателя типа группы бита 1LB1 первой группы первой секции передается на выход указателя типа группы бита LB1 первой группы блока 2 элементов второго типа.

На выходы второй группы G2 бит и указателя типа групп бита LB2 второй группы блока 2 передаются соответствующие значения с выходов первой группы элементов ИЛИ 20 и элемента ИЛИ 21, на входы которых передаются соответствующие значения второй группы 2G2 и указатель типа групп бит 2LB2 второй секции или значения первой группы 2G1 и указатель типа групп бит 2LB1 второй секции через первую группу 18 элементов И при единичном значении управляющего сигнала U21=1 или значения с выходов второго SM2 сумматора 22 и указатель типа групп бит 1LB2 второй группы первой секции через вторую группу 19 элементов И при единичном значении управляющего сигнала US2=1.

Одновременно на третьем сумматоре SM 8 осуществляется суммирование групп общего количества (суммы) групп единичных и нулевых бит первых секций 1VG и вторых секций 2VG и на выходе формируется двоичный код количества (суммы) общего количества групп VG. На вычитателе (декременторе) SB 9 проводится коррекция на единицу значения общего количества групп VG при единичном значении флага декрементации FD=1, когда в соседних группах из первой и второй секций содержатся подряд идущие единичные или нулевые бит и коды этих групп суммируются, а с выхода вычитателя 9 передается значение на соответствующую группу выходов VG блока элементов 2ij.

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

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

На первом компараторе СМР 26 проводится сравнение первой 1MU и второй 2MU групп количества (суммы) единичных бит первой и второй секций и на выходы второй группы 27 мультиплексоров передается большее значение. Аналогично на третьем коммутаторе СМР 31 проводится сравнение первой 1MZ и второй 2MZ групп количества (суммы) нулевых бит первой и второй секций и на выходы четвертой группы 32 мультиплексоров передается большее значение.

В блоках 2ij при суммировании кодов соседних групп первая группа мультиплексоров (коммутаторов) MX 25 передает на вторую группу выходов GSM значения с первого SM1 сумматора 23 или второго SM2 сумматора 22 и соответствующее значение LBSM указателя типа группы бит 1LB1 первой группы или бит 1LB2 второй группы первой секции. Далее код суммы со второй группы выходов GSM первой группы мультиплексоров (коммутаторов) MX 25 поступает на второй компаратор СМР 28 и на четвертый компаратор СМР 33, на которых это значение сравнивается соответственно с максимальными значениями единичных бит 12MU и нулевых бит 12MZ с выходов второй 27 группы мультиплексоров MX и четвертой 32 группы мультиплексоров MX. На втором компараторе СМР 28 и на четвертом компараторе СМР 33 проводится анализ кодов единичных и нулевых групп и на выходах компараторов формируется единичное значение, если код с сумматоров имеет большее значение, которые передаются на прямые входы восьмого элемента И 29 и девятого элемента И 34. При этом значение указателя типа группы LBSM с соответствующего мультиплексора первой 25 группы мультиплексоров (коммутаторов) MX 25 передается на прямой вход восьмого элемента И 29 и на инверсный вход девятого элемента И 34, выходы которых поступают на адресные S входы соответственно третьей 30 группы мультиплексоров (коммутаторов) MX и четвертой 35 группы мультиплексоров (коммутаторов) MX, на выходы которых передаются большие значения групп единичных и нулевых бит, которые далее передаются на соответствующие группы выходов максимального количества единичных бит MU и максимального количества нулевых бит MZ блока элементов 2ij.

Блок управления 10 формирует управляющие сигналы разрешения, флаг декрементации FD и бит К четности/нечетности количества групп. На основе таблицы 2 получены следующие выражения:

FD=((2LB1 xnor 1LB2) and not 1K) or ((2LB1 xnor 1LB1) and 1K);

U21=not FD and 2K;

US1=(2LB1 xnor 1LB1) and 1K;

US2=not (2LB1 xnor 1LB2) and 1K and 2K;

К=(2LB1 xnor 1LB1) and 1K and 2K.

В блоке 37 формируются код QZU «разности единиц и нулей» и флаг F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ». На пятом сумматоре проводится вычитание из кода двоичного числа «N», соответствующего количеству разрядов входного двоичного числа D1, D2, …, DN, удвоенного значения инверсного кода U количества (суммы) единичных бит с последней Z-ой ступени, дополненного в младшем разряде и на входе CI переноса сумматора значением логической единицы «1». При этом на выходе пятого сумматора 38 формируется код ZU «разности единиц и нулей» в соответствии со следующим выражением:

ZU=N+not (2*U)+1.

При этом если сумма единичных бит превышает сумму нулевых бит, то на инверсном выходе СО переноса пятого сумматора 38 формируется единичное значение флага «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ» F10=1. При равенстве сумм единичных и нулевых бит или если сумма нулевых бит превышает сумму единичных бит, то формируется нулевое значение флага «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ» F10=0.

Далее по значению флага F10 на элементах второй группы 39 элементов ИЛИ, девятой группы 40 элементов И и группы 41 элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» формируется код дополнения до 2^M значения с шины ZU с выхода пятого сумматора 38, который будет соответствовать соотношению между суммами нулевых и единичных бит во входном двоичном числе D1, D2,…, DN.

Дополнение получается после изменения всех старших единиц на нули, кроме последней младшей единицы, и всех старших нулей на единицы, до последней младшей единицы, т.е. выполняется инверсия старших разрядов до последней младшей единицы. При этом самый младший разряд с шины ZU всегда остается неизменным.

Анализ единиц начинается с младшего разряда шины ZU во второй группе 39 из (М-2) элементов ИЛИ. При этом выявление единицы в одном из младших разрядов передается последовательно на все старшие разряды по цепочке последовательно соединенных элементов ИЛИ, во второй группе 39 из (М-2) элементов ИЛИ, и при единичном значении флага «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ» F10=1 через девятую группу 40 из (М-1) элементов И поступает на группу 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», которые можно рассматривать как элементы «управляемый инвертор», и на которых проводится инверсия битов старших разрядов шины ZU. При нулевом значении флага «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ» F10=0 на выходах девятой группы 40 из (М-1) элементов И формируются нулевые значения, поэтому через группу 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» передается прямое значение разрядов с шины ZU без преобразования.

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

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

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

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

В каждом блоке элементов 2_2j второго типа второй ступени в блоках управления 10 анализируются значения бит 1К и 2К четности/нечетности групп в первой и второй секциях и указателей типа групп бит LB групп - в первых секциях для первой группы бит 1LB1 и для второй группы бит 1LB2 и во вторых секциях для первой группы бит 2LB1. В блоке управления 10 в соответствии с таблицей 2 формируются значение бита К четности/нечетности количества групп в блоке, которое передается на соответствующий выход блока 2_2j и значение флага флаг FD декрементации кода суммы общего количества групп первой секции, а также формируются управляющие сигналы: U21 - первый сигнал разрешения передачи первой 2G1 группы второй секции на выходы второй группы блока 2; US1 - второй сигнал разрешения передачи первой 2G1 группы второй секции на входы первого сумматора 22; US2 - третий сигнал разрешения передачи выходов SM2 второго сумматора 23 на выходы второй группы блока 2.

Если в 1-ой секции содержится только одна группа 1К=1, а указатели типа первых групп 1LB1 в первой секции и 2LB1 во второй секции имеют одинаковые значения (1LB1=0 и 2LB1=0 или 1LB1=1 и 2LB1=1), что соответствует случаю, когда первая группа 1G1 первой секции и первая группа 2G1 второй секции являются соседними группами и в которых содержатся однотипные единичные или нулевые биты, то формируется управляющий сигнал US1=1, по которому через третью группу 24 элементов И на входы первого сумматора 23 передается двоичных код первой группы 2G1 второй секции, а на вторую группу входов первого сумматора 23 передается двоичных код первой группы 1G1 первой секции, которые суммируются. При нулевом управляющем сигнале US1=0 на выход SM1 первого сумматора 23 передается значение двоичного кода первой группы 1G1 первой секции.

Далее значение с выходов SM1 первого сумматора 23 передается на группу выходов первой группы G1 блока 2_2j, а также указатель типа групп бит 1LB1 первых групп первой секции передается на выход указателя типа групп бит LB1 первой группы блока 2_2j.

На втором сумматоре 22 всегда проводится суммирование двоичных кодов второй группы 1G2 первой секции и первой группы 2G1 второй секции. Если в первой секции содержится две группы 1К=0, во второй секции одна группа 2К=1, а указатели второй группы 1LB2 первой секции и первой группы 2LB1 второй секции имеют одинаковые значения (1LB2=0 и 2LB1=0 или 1LB2=1 и 2LB1=1), что соответствует случаю, когда вторая группа 1G2 первой секции и первая группа 2G1 второй секции являются соседними группами и в которых содержатся однотипные единичные или нулевые биты, то формируется управляющий сигнал US2=1, по которому через вторую группу 19 элементов И значение с выходов SM2 второго сумматора 22 передается на соответствующие входы элементов ИЛИ из первой группы 20 элементов ИЛИ, а также значение указателя бит вторых групп 1LB2 первой секции с соответствующего выхода элемента И из второй группы 19 элементов И передается на соответствующий вход элемента ИЛИ 21.

Если в первой секции содержится две группы 1К=0, во второй секции одна группа 2К=1, а указатели вторых групп 1LB2 первой секции и первых групп 2LB1 второй секции имеют разные значения (1LB2=0 и 2LB1=1 или 1LB2=1 и 2LB1=0) или если в первой секции содержится одна группа 1К=1, во второй секции также одна группа 2К=1, а указатели первых групп 1LB1 первой секции и первых групп 2LB1 второй секции имеют разные значения (1LB1=0 и 2LB1=1 или 1LB1=1 и 2LB1=0), то формируется управляющий сигнал U21=1, по которому значение двоичного кода первой группы 2G1 второй секции передается через первую группу 18 элементов И на соответствующие входы элементов ИЛИ из первой группы 20 элементов ИЛИ, а также значение указателя бит первых групп 2LB1 второй секции с соответствующего выхода элемента И из второй группы 19 элементов И передается на соответствующий вход элемента ИЛИ 21. Кроме того двоичный код второй группы 2G2 второй секции всегда передается на соответствующие входы элементов ИЛИ из первой группы 20 элементов ИЛИ, а также значение указателя бит первых групп 2LB1 второй секции передается на соответствующий вход элемента ИЛИ 21.

Значения с выходов группы элементов ИЛИ 20 и элемента ИЛИ 21 передаются на соответствующие выходы второй группы бит G2 и выход указателя типа группы бит LB2 второй группы блока 2_2j.

Кроме того, одновременно на третьем сумматоре SM 8 осуществляется суммирование групп общего количества (суммы) групп единичных и нулевых бит первых секций 1VG и вторых секций 2VG и на выходе формируется двоичный код количества (суммы) общего количества групп VG. Когда в соседних группах из первой и второй секций содержатся подряд идущие единичные или нулевые бит и коды этих групп суммируются, то формируется единичное значение флага декрементации FD=1, по которому на вычитателе (декременторе) SB 9 проводится коррекция на единицу значения общего количества групп VG с третьего сумматора SM 8. Значение с выхода вычитателя 9 передается на соответствующую группу выходов VG блока элементов 2ij.

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

Для выявления максимальных групп единичных и нулевых бит на первом компараторе СМР 26 проводится сравнение первой 1MU и второй 2MU групп количества (суммы) единичных бит первой и второй секций и на выходы 12MU второй группы 27 мультиплексоров передается большее значение. Аналогично на третьем коммутаторе СМР 31 проводится сравнение первой 1MZ и второй 2MZ групп количества (суммы) нулевых бит первой и второй секций и на выходы 12MZ четвертой группы 32 мультиплексоров передается большее значение. Таким образом, определяются максимальные единичные 12MU и нулевые 12MZ группы для входных кодов, которые передаются соответственно на нулевые группы третьей 30 группы мультиплексоров (коммутаторов) MX и четвертой 35 группы мультиплексоров (коммутаторов) MX, а также на входы соответственно второго компаратора СМР 28 и четвертого компаратора СМР 33.

В блоках 2ij максимальное значение бит в группе может измениться при суммировании кодов соседних групп на первом SM1 сумматоре 23 или втором SM2 сумматоре 22, значения с выходов которых передаются на соответствующие входы мультиплексоров из первой группы мультиплексоров MX 25, на которых также выбирается соответствующий указатель типа групп бит 1LB1 первой группы или бит 1LB2 второй группы первой секции. Далее код суммы GSM с выхода второй группы мультиплексоров (коммутаторов) MX 25 поступает на второй компаратор СМР 28 и на четвертый компаратор СМР 33, на которых это значение сравнивается соответственно с максимальными значениями единичных бит 12MU и нулевых бит 12MZ с выходов соответственно второй группы 27 мультиплексоров MX и четвертой группы 32 мультиплексоров MX. На втором компараторе СМР 28 проводится анализ кодов максимальных единичных групп, а на четвертом компараторе СМР 33 проводится анализ кодов максимальных нулевых групп, и на выходах формируется единичное значение, если двоичные коды с сумматоров превышают значения единичных бит 12MU или нулевых бит 12MZ.

Далее указатель типа групп бит LBSM, с соответствующего мультиплексора первой 25 группы мультиплексоров (коммутаторов) MX, управляет передачами больших кодов в третьей группе 30 мультиплексоров (коммутаторов) MX и в пятой группе 35 мультиплексоров (коммутаторов) MX. При единичном значении бита LBSM=1 разрешается передача результатов сравнения с выхода второго компаратора СМР 28 через восьмой элемент И 29 на адресные S входы соответственно третьей группы 30 мультиплексоров (коммутаторов) MX. При нулевом значении бита LBSM=0 разрешает передачу результатов сравнения с выхода четвертого компаратора СМР 33 через девятый элемент И 34 с одним инверсным входом на адресные S входы соответственно пятой группы 35 мультиплексоров (коммутаторов) MX. Далее большие значения групп единичных и нулевых бит передаются на соответствующие группы выходов максимального количества единичных бит MU и максимального количества нулевых бит MZ блока элементов 2ij.

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

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

Далее аналогично проводится формирование значений кодов групп для третьей, четвертой, …, Z-ой ступеней. Кроме того, выход группы QU количества (суммы) единичных бит поступает на первую группу входов блока 37 формирования кода разности, на вторую группу входов которого поступает двоичный код «N», соответствующий количеству разрядов входного двоичного числа D1, D2, …, DN. На выходах блока 37 формируются код QZU «разности единиц и нулей» и флаг F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ».

Таким образом, на внешних выходах устройства формируются значения:

QG1 - код первой группы подряд идущих одинаковых бит,

QLB1 - бит указателя типа первой группы (единичных или нулевых),

QG2 - код второй группы подряд идущих одинаковых бит,

QLB2 - бит указателя типа второй группы (единичных или нулевых),

QK - бит четности/нечетности количества групп в блоке,

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

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

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

QMZ - код суммы группы с максимальным количеством нулевых бит.

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

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

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

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

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

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

Изобретение относится к области вычислительной техники. Технический результат заключается в обеспечении возможности выявления групп единичных и нулевых бит в двоичных числах, определение количества групп, а также выявление максимальных групп единичных и нулевых бит и простое увеличение разрядности входной информации. Указанный результат достигается за счет того, что устройство содержит N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на N/2 групп по два разряда в группе, Z ступеней блоков элементов, где Z=] log₂N[(] [- большее целое), и блок формирования кода разности, причем первая ступень содержит N/2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа, а каждая i-ая ступень, начиная со второй ступени до Z-й ступени, содержит по N/2ⁱ блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, N/2ⁱ, каждый из N/2 блоков элементов 1₁, 1₂, …, 1_N/2 первого типа первой ступени содержит первый элемент «ЭКВИВАЛЕНТНОСТИ», первый элемент И с одним инверсным входом 4, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ», второй элемент И и третий элемент И с инверсными входами, каждый блок элементов 2_ij второго типа второй, третьей,…, Z-ой ступени содержит третий сумматор SM, вычитатель SB, блок управления, первую группу элементов И, вторую группу элементов И, первую группу элементов ИЛИ, элемент ИЛИ, второй сумматор SM2, первый сумматор SM1, третью группу элементов И, первую группу мультиплексоров MX, первый компаратор СМР, вторую группу мультиплексоров MX, второй компаратор СМР, восьмой элемент И, третью группу мультиплексоров MX, третий компаратор СМР, четвертую группу мультиплексоров MX, четвертый компаратор СМР, девятый элемент И с одним инверсным входом, пятую группу мультиплексоров MX и четвертый сумматор SM, блок формирования кода разности содержит пятый сумматор SM с инверсной группой входов, вторую группу элементов ИЛИ, девятую группу элементов И и группу элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ». 4 ил., 2 табл.

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

причем первая ступень содержит 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-i)(нч) и выходы четных блоков элементов 1₂, 1₄, …, 1_N/2(чт) первой ступени попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2_21, 2₂₂, …, 2_2N/4 второго типа второй ступени, а выходы нечетных блоков элементов 2ij(нч) и выходы четных блоков элементов 2ij(чт) каждой i-ой ступени, начиная со второй ступени до предпоследней (Z-1)-ой ступени, попарно соединены с соответствующими группами одноименных входов соответственно первых и вторых секций входов блоков элементов 2ij последующих ступеней, начиная с третьей ступени до последней Z-ой ступени,

выходы групп блока элементов 2zj последней Z-ой ступени являются соответствующими группами Q внешних одноименных выходов устройства группы QVG общего количества групп единичных и нулевых бит, группы QU количества единичных бит во входном двоичном числе D1, D2, …, DN, групп первой QG1 и последней QG2 групп, подряд идущих нулевых или единичных бит, группы QMU максимального количества единичных бит и группы QMZ максимального количества нулевых бит, а также выходы бит QLB1 и QLB2 указателей типа первой и последней групп, бита QK четности/нечетности количества групп,

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

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

а также первый вход А1 соединен с выходом бита LB1 указателя типа первой группы блока первого типа 1, выход первого элемента «ЭКВИВАЛЕНТНОСТИ» 3 соединен с первым разрядом g11 первой выходной группы G1 бит, нулевым разрядом vg0 выходной группы VG общего количества групп единичных и нулевых бит и выходным битом К четности/нечетности количества групп, выход первого элемента И с одним инверсным входом 4 соединен с выходом бита LB2 указателя типа второй группы блока первого типа 1, выход элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5 соединен с нулевым разрядом g10 первой выходной группы G1 бит, с нулевым разрядом g20 второй выходной группы G2 бит, с первым разрядом vg1 выходной группы VG общего количества групп единичных и нулевых бит, с нулевым разрядом u0 выходной группы U количества единичных бит, с нулевым разрядом mu0 выходной группы MU количества единичных бит, с нулевым разрядом mz0 выходной группы MZ количества нулевых бит, выход второго элемента И 6 соединен с первым разрядом u1 выходной группы U количества единичных бит и с первым разрядом mu1 выходной группы MU количества единичных бит, выход третьего элемента И с инверсными входами 7 соединен с первым разрядом mz1 выходной группы MZ количества нулевых бит,

каждый блок элементов 2_ij второго типа второй, третьей, …, Z-ой ступени содержит третий сумматор SM 8, вычитатель SB 9, блок управления 10, первую группу элементов И 18, вторую группу элементов И 19, первую группу элементов ИЛИ 20, элемент ИЛИ 21, второй сумматор SM2 22, первый сумматор SM1 23, третью группу элементов И 24, первую группу мультиплексоров MX 25, первый компаратор СМР 26, вторую группу мультиплексоров MX 27, второй компаратор СМР 28, восьмой элемент И 29, третью группу мультиплексоров MX 30, третий компаратор СМР 31, четвертую группу мультиплексоров MX 32, четвертый компаратор СМР 33, девятый элемент И с одним инверсным входом 34, пятую группу мультиплексоров MX 35 и четвертый сумматор SM 36,

причем блок управления 10 содержит второй элемент «ЭКВИВАЛЕНТНОСТИ» 11, третий элемент «ЭКВИВАЛЕНТНОСТИ» 12, мультиплексор MX 13, четвертый элемент И с одним инверсным входом 14, пятый элемент И с одним инверсным входом 15, шестой элемент И 16 и седьмой элемент И 17, а вход бита 1LB1 указателя типа первой группы первой секции соединен со вторым входом третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12, вход бита 1LB2 указателя типа второй группы первой секции соединен с первым входом второго элемента «ЭКВИВАЛЕНТНОСТИ» 11, вход бита 2LB1 указателя типа первой группы второй секции соединен со вторым входом второго элемента «ЭКВИВАЛЕНТНОСТИ» 11 и первым входом третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12, вход бита 1К четности/нечетности первой секции соединен с первым инверсным входом пятого элемента И с одним инверсным входом 15, с первым входом шестого элемента И 16, с первым входом седьмого элемент И 17 и с адресным входом S мультиплексора 13, вход бита 2К четности/нечетности второй секции соединен со вторым прямым входом четвертого элемента И с одним инверсным входом 14, с третьим прямым входом пятого элемента И с одним инверсным входом 15 и с третьим прямым входом шестого элемента И 16, выход второго элемента «ЭКВИВАЛЕНТНОСТИ» 11 соединен со вторым прямым входом пятого элемента И с одним инверсным входом 15 и с нулевым информационным входом мультиплексора 13, выход третьего элемента «ЭКВИВАЛЕНТНОСТИ» 12 соединен первым информационным входом мультиплексора 13, со вторым входом шестого элемента И 16 и со вторым входом седьмого элемент И 17, выход мультиплексора 13 соединен с первым инверсным входом четвертого элемента И с одним инверсным входом 14 и является флагом декрементации FD, выход четвертого элемента И с одним инверсным входом 14 является выходом первого сигнала разрешения U21, выход пятого элемента И с одним инверсным входом 15 является выходом второго сигнала разрешения US2, выход седьмого элемент И 17 является выходом третьего сигнала разрешения US1, выход шестого элемента И 16 соединен с выходом бита К четности/нечетности блока элементов 2_ij второго типа,

причем в каждом блоке элементов 2_ij второго типа группы общего количества групп единичных и нулевых бит первой секции 1VG и второй секции 2VG соединены с соответствующими группами входов третьего сумматора SM 8, группа выходов которого соединена с первой группой входов вычитателя SB 9, второй вход которого соединен с выходом флага декрементации FD блока управления 10, а выход вычитателя SB 9 является выходом группы VG общего количества групп единичных и нулевых бит блока элементов 2_ij второго типа,

разряды входов второй группы бит 2G2 второй секции соединены с первыми входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а бит 2LB2 указателя типа второй группы бит 2G2 второй секции соединен с первым входом элемента ИЛИ 21,

разряды входов первой группы бит 2G1 второй секции соединены с первыми входами одноименных элементов И из первой группы 18 элементов И, с соответствующими разрядами первой группы входов второго сумматора SM2 22 и с первыми входами одноименных элементов И из третьей группы 24 элементов И, вторые входы элементов И из третьей группы 24 элементов И соединены между собой и подключены к выходу третьего сигнала разрешения US1 блока управления 10, а бит 2LB1 указателя типа первой группы бит 2G1 второй секции соединен с первым входом соответствующего элемента И из первой группы 18 элементов И, при этом вторые входы всех элементов И из первой группы 18 элементов И соединены между собой и подключены к выходу первого сигнала разрешения U21 блока управления 10, а разряды первой группы выходов элементов И из первой группы 18 элементов И соединены соответственно со вторыми входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а второй выход элементов И из первой группы 18 элементов И соединен со вторым входом элемента ИЛИ 21,

разряды входов второй группы бит 1G2 первой секции соединены с соответствующими разрядами второй группы входов второго сумматора SM2 22, разряды выходов которого соединены с первыми входами одноименных элементов И из второй группы 19 элементов И и с соответствующими одноименными разрядами информационной нулевой группы входов первой группы мультиплексоров MX 25, а бит 1LB2 указателя типа второй группы бит 1G2 первой секции соединен с соответствующим разрядом информационной нулевой группы входов первой группы мультиплексоров MX 25 и с первым входом соответствующего элемента И из второй группы 19 элементов И, при этом вторые входы всех элементов И из второй группы 19 элементов И соединены между собой и подключены к выходу первого сигнала разрешения U21 блока управления 10, а разряды первой группы выходов элементов И из второй группы 19 элементов И соединены соответственно с третьими входами одноименных элементов ИЛИ из первой группы 20 элементов ИЛИ, а второй выход второй группы 19 элементов И соединен с третьим входом элемента ИЛИ 21,

разряды входов первой группы бит 1G1 первой секции соединены с соответствующими разрядами второй группы входов первого сумматора SM1 23, первая группа входов которого соединена с соответствующими выходами элементов И из третьей группы 24 элементов И, а группа выходов SM1 первого сумматора 23 соединена с соответствующими одноименными разрядами информационной первой группы входов первой группы мультиплексоров MX 25, а бит 1LB1 указателя типа первой группы бит 1G1 первой секции соединен с соответствующим разрядом информационной первой группы входов первой группы мультиплексоров MX 25 и является выходом бита LB1 указателя типа первой группы блока элементов 2_ij второго типа, а группа выходов SM1 первого сумматора 23 является также группой бит G1 выходов первой группы блока элементов 2_ij второго типа,

выходы элементов ИЛИ из первой группы 20 элементов ИЛИ являются группой бит G2 выходов второй группы, а выход элемента ИЛИ 21 является выходом бита LB2 указателя типа второй группы блока элементов 2_ij второго типа,

причем у первой группы мультиплексоров MX 25 адресные входы S мультиплексоров соединены между собой и подключены к входу 1К бита четности/нечетности количества групп в первой секции блока элементов 2_ij второго типа, а входы Е разрешения работы группы мультиплексоров MX 25 соединены между собой и соединены с выходом флага декрементации FD блока управления 10,

кроме того группы максимального количества единичных бит первой секции 1MU и второй секции 2MU соединены соответственно с первыми и вторыми группами входов первого компаратора СМР 26 и информационными нулевой и первой группами второй группы мультиплексоров MX 27, у которого адресный вход S соединен с выходом первого компаратора СМР 26, а группа выходов 12MU второй группы мультиплексоров MX 27 соединена со второй группой входов второго компаратора СМР 28 и нулевой информационной группой третьей группы мультиплексоров MX 30,

кроме того группы максимального количества нулевых бит первой секции 1MZ и второй секции 2MZ соединены соответственно с первыми и вторыми группами входов третьего компаратора СМР 31 и информационными нулевой и первой группами четвертой группы мультиплексоров MX 32, у которого адресный вход S соединен с выходом третьего компаратора СМР 31, а группа выходов 12MZ четвертой группы мультиплексоров MX 32 соединена со второй группой входов четвертого компаратора СМР 33 и нулевой информационной группой пятой группы мультиплексоров MX 35,

причем вторая группа выходов GSM первой группы мультиплексоров MX 25 соединена с первыми информационными группами третьей группы мультиплексоров MX 30 и пятой группы мультиплексоров MX 35, а также соединены с первыми группами входов второго компаратора СМР 28 и четвертого компаратора СМР 33 выходы которых соединены соответственно со вторыми прямыми входами восьмого элемента И 29 и девятого элемента И 34, выходы которых соединены с адресными входами S соответственно третьей группы мультиплексоров MX 30 и пятой группы мультиплексоров MX 35, а первый выход первой группы мультиплексоров MX 25 соответствующий биту LBSM указателя типа группы соединен с первым инверсным входом восьмого элемента И 29 и первым прямым входом девятого элемента И 34,

причем группа выходов третьей группы мультиплексоров MX 30 является группой выходов MU максимального количества единичных бит, а группа выходов пятой группы мультиплексоров MX 35 является группой выходов MZ максимального количества нулевых бит блока элементов 2_ij второго типа,

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

блок формирования кода разности 37 содержит пятый сумматор SM с инверсной группой входов 38, вторую группу из (М-2) элементов ИЛИ 39, девятую группу из (М-1) элементов И 40 и группу из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 41, где M=[log₂N]+1 (меньшее целое),

причем группа выходов U количества единичных бит с последней Z-ой ступени соединена с первой группой входов блока формирования кода разности 37, у которого на вторую группу входов подан код двоичного числа «N», соответствующий количеству разрядов входного двоичного числа D1, D2, …, DN,

при этом первая группа входов блока формирования кода разности 37 соединена со второй группой входов первой инверсной группы входов первого слагаемого пятого сумматора 38, а на вход младшего разряда первой инверсной группы входов подано значение логической единицы «1», при этом у пятого сумматора 38 на первую группу входов второй прямой группы входов второго слагаемого подан код двоичного числа «N», а на вход старшего разряда второй прямой группы входов подано значение логического нуля «0», а также на вход переноса CI пятого сумматора 38 подано значение логической единицы «1»,

причем в блоке формирования кода разности 37 вторые входы элементов ИЛИ, второй группы 39 из (М-2) элементов ИЛИ, соединены с соответствующими разрядами выходов пятого сумматора 38, начиная со второго разряда до (M-1)-го разряда, а первые входы элементов ИЛИ 39, начиная со второго до последнего (М-2)-го элемента, соединены с соответствующими выходами предыдущих элементов ИЛИ 39, начиная с первого до предпоследнего (М-3)-го элемента, а первый вход первого элемента ИЛИ 39 соединен с первым разрядом выходов пятого сумматора 38,

вторые входы всех элементов И, девятой группы 40 из (М-1) элементов И, соединены между собой и соединены с инверсным выходом переноса СО пятого сумматора 38, а первый вход первого элемента И, из девятой группы 40 из (М-1) элементов И, соединен с первым разрядом выходов пятого сумматора 38, а первые входы элементов И, из девятой группы 40 из (М-1) элементов И, начиная со второго до последнего (М-1), соединены с соответствующими выходами элементов ИЛИ, второй группы 39 из (М-2) элементов ИЛИ, начиная с первого до (М-2)-го элемента ИЛИ,

выходы элементов И, из девятой группы 40 из (М-1) элементов И, соединены с соответствующими первыми входами одноименных элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», группы 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», вторые входы которых соединены с соответствующими разрядами выходов пятого сумматора 38, начиная со второго разряда до М-го разряда,

а выходы элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», группы 41 из (М-1) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ», являются (М-1) разрядами группы QZU внешних выходов «разность единиц и нулей», блока формирования кода разности 37, начиная со второго выхода до последнего М-го выхода группы QZU, а первый разряд внешних выходов QZU блока формирования кода разности 37 соединен с первым разрядом выходов пятого сумматора 38, а инверсный выход переноса СО пятого сумматора 38 является внешним выходом флага F10 «ЕДИНИЦ БОЛЬШЕ НУЛЕЙ».