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

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

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

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

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

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

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

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

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

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

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

содержит N разрядов входного двоичного числа D1, D2, …, DN, (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 содержит два разряда,

причем N разрядов входного двоичного числа D1, D2, …, DN соединены с одноименными входами A1, А2, …, AN первого каскада 1₁,

в каждом i-м каскаде первые (N-i) входов A1, А2, …, A(N-i), кроме последнего входа A(N+1-i), также соединены со вторыми входами соответствующих одноименных элементов ИЛИ 2₁, 2₂, …, 2_(N-i) и вторыми входами одноименных элементов XOR 3₁, 3₂, …, 3_(N-i), а первые входы первых (N-i-1) элементов 2₁, 2₂, …, 2_(N-i-1) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 2₂, 2₃, …, 2_(N-i) из группы элементов ИЛИ, первый вход последнего элемента 2_(N-i) из группы элементов ИЛИ соединен с последним входом запроса A(N+1-i) i-го каскада, выходы (N-i) элементов ИЛИ 2₁, 2₂, …, 2_(N-i) соединены также с первыми входами соответствующих одноименных элементов XOR 3₁, 3₂, …, 3_(N-i), выходы которых являются группой (N-i) выходов Q1, Q2, …, Q(N-i) в следующий каскад каждого i-го каскада, а выходы всех (N-i) элементов ИЛИ 2₁, 2₂, …, 2_(N-i) являются одноименными первыми младшими (N-i) разрядами соответствующей i-й внутренней шины S_i из группы S1, S2, …, S_(N-1), а последний вход A(N+1-i) i-го каскада является старшим (N+1-i)-м разрядом соответствующей i-й внутренней шины S_i,

причем в первых (N-2) каскадах, кроме последнего (N-1)-го каскада, (N-i) выходов в следующий (i+1)-й каскад Q1, Q2, …, Q(N-i) соединены с соответствующими (N-i) одноименными входами A1, А2, …, A(N-i) следующего (i+1)-го каскада,

все разряды каждой i-й внутренней шины S_i из группы S1, S2, …, S_(N-1) соединены с входами соответствующего одноименного блока 4_i из первой группы из (N-i) блоков счета младших упорядоченных единиц, а выходы каждого i-го блока 4_i соединены с инверсной группой входов второго слагаемого i-го сумматора 5_i и первой группой прямых входов первого слагаемого (i+1)-го сумматора 5_(i+1) из группы из N сумматоров 5₁, 5₂, …, 5_N, выходы которых являются соответствующими первыми N группами выходных данных G1, G2, …, GN, а последний одноразрядный выход G(N+1) соединен с выходом Q1 последнего (N-1) каскада 1_(N-1), который также соединен со второй инверсной группой входов последнего N-го сумматора 5_N и первым прямым входом элемента ИЛИ с одним инверсным входом 6, второй инверсный вход которого соединен со старшим N-м разрядом DN входного двоичного числа,

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

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

На фиг. 1 представлена схема предлагаемого устройства для определения количества нулей и единиц по группам в двоичном числе при N=4. На фиг. 2 приведен формат выходных данных для N разрядов входных данных и для N=4 и N=8. В таблице 1 приведены примеры формирования значений количества нулей и единиц по группам G1, G1, …, G5 и общего количества групп К при N=4.

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

A1, А2, …, A(N+1-i) - входы i-го каскада (i=1, …, (N-1)) формирователя упорядоченных двоичных чисел,

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

D1, D2, …, D4 (DN) - N разрядов входного двоичного числа (при N=4),

G1, G1, …, G5 (G_N+1) - (N+1) групп выходных данных (при N=4), каждая из которых содержит ]log₂(N+3-i)[ (большее целое) разрядов,

K - выходная группа количества групп нулей и единиц, содержит ]log₂(N+1)[ (большее целое) разрядов.

Q1, Q2, …, Q(N-i) - выходы i-го каскада в следующий каскад формирователя упорядоченных двоичных чисел,

S1, S2, S3 (S_N-1) - (N-1) внутренних шин упорядоченных двоичных чисел,

SM - сумматоры,

1₁, 1₂, 1₃ (1_(N-1)) - (N-1) каскадов формирователя упорядоченных двоичных чисел,

2₁, 2₂, 2₃ (2_N-i) - группа из (N-i) элементов ИЛИ i-го каскада формирователя упорядоченных двоичных чисел,

3₁, 3₂, 3₃ (3_N-i) - группа из (N-i) элементов XOR i-го каскада формирователя упорядоченных двоичных чисел,

4₁, 4₂, 4₃ (4_N-i) - первая группа из (N-i) блоков счета младших упорядоченных единиц,

5₁, 5₂, 5₃, 5₄ (5_N) - группа из N сумматоров,

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

7 - второй блок счета младших упорядоченных единиц.

Предлагаемое устройство для определения количества нулей и единиц по группам в двоичном числе содержит 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 содержит два разряда.

Причем N разрядов входного двоичного числа D1, D2, …, DN соединены с одноименными входами A1, А2, …, AN первого каскада 1₁.

В каждом i-м каскаде первые (N-i) входов A1, А2, …, A(N-i), кроме последнего входа A(N+1-i), также соединены со вторыми входами соответствующих одноименных элементов ИЛИ 2₁, 2₂, …, 2_(N-i) и вторыми входами одноименных элементов XOR 3₁, 3₂, …, 3_(N-i), а первые входы первых (N-i-1) элементов 2₁, 2₂, …, 2_(N-i-1) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 2₂, 2₃, …, 2_(N-i) из группы элементов ИЛИ, первый вход последнего элемента 2_(N-i) из группы элементов ИЛИ соединен с последним входом запроса A(N+1-i) i-го каскада. Выходы (N-i) элементов ИЛИ 2₁, 2₂, …, 2_(N-i) соединены также с первыми входами соответствующих одноименных элементов XOR 3₁, 3₂, …, 3_(N-i), выходы которых являются группой (N-i) выходов Q1, Q2, …, Q(N-i) в следующий каскад каждого i-го каскада. Выходы всех (N-i) элементов ИЛИ 2₁, 2₂, …, 2_(N-i) являются одноименными первыми младшими (N-i) разрядами соответствующей i-й внутренней шины S_i из группы S1, S2, …, S_(N-1), а последний вход A(N+1-i) i-го каскада является старшим (N+1-i)-м разрядом соответствующей i-й внутренней шины S_i.

В первых (N-2) каскадах, кроме последнего (N-1)-го каскада, (N-i) выходов в следующий (i+1)-й каскад Q1, Q2, …, Q(N-i) соединены с соответствующими (N-i) одноименными входами A1, А2, …, A(N-i) следующего (i+1)-го каскада.

Все разряды каждой i-й внутренней шины S_i из группы S1, S2, …, S_(N-1) соединены с входами соответствующего одноименного блока 4_i из первой группы из (N-i) блоков счета младших упорядоченных единиц, а выходы каждого i-го блока 4_i соединены с инверсной группой входов второго слагаемого i-го сумматора 5_i и первой группой прямых входов первого слагаемого (i+1)-го сумматора 5_(i+1) из группы из N сумматоров 5₁, 5₂, …, 5_N.

Выходы группы из N сумматоров 5₁, 5₂, …, 5_N являются соответствующими первыми N группами выходных данных G1, G2, …, GN, а последний одноразрядный выход G(N+1) соединен с выходом Q1 последнего (N-1) каскада 1_(N-1), который также соединен со второй инверсной группой входов последнего N-го сумматора 5_N и первым прямым входом элемента ИЛИ с одним инверсным входом 6, второй инверсный вход которого соединен со старшим N-м разрядом DN входного двоичного числа.

На группу первых прямых входов первого сумматора 5₁ подано двоичное число «N», а на входы переносов CI всех N сумматоров 5₁, 5₂, …, 5_N подано значение логической единицы.

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

Выходы второго блока счета младших упорядоченных единиц 7 являются выходной группой К количества групп нулей и единиц, причем количество групп К содержит ]log₂(N+1)[ (большее целое) разрядов.

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

На входы устройства поступает входное N разрядное двоичное число без знака D1, D2, …, DN, которое поступает на входы A1, А2, …, AN первого каскада 1₁. Старший разряд DN является старшим разрядом входного двоичного числа.

На первом шаге анализируется наличие единичных значений во входных данных и в первом 1₁ каскаде N разрядное двоичное число D1, D2, …, DN на выходах группы элементов ИЛИ 2₁, 2₂, …, 2_(N-i), объединенных в цепочку, преобразуется в упорядоченный двоичный код «00…011…1» с единицами расположенными подряд, начиная с младших разрядов, где левая единица соответствует старшей единице во входном двоичном числе, который одновременно со старшим разрядом входных данных DN поступают на внутреннюю шину S₁. Количество единиц является дополнением до N к количеству нулей во входном двоичном числе и соответствует сумме всех разрядов кроме первой «нулевой» группы.

Далее в первом блоке 4₁ счета младших упорядоченных единиц проводится подсчет количества единиц. Полученное количество единиц поступает на вторую инверсную группу второго слагаемого первого сумматора 5₁ и вычитается из количества разрядов N входных данных, заданном двоичным кодом «N» на входах первого слагаемого и при единичном значении на входе переноса CI=1, что соответствует операции вычитания для чисел без знака. При этом полученная разность на выходе первого сумматора 5₁ соответствует количеству нулей в первой «нулевой» группе входного двоичного числа D1, D2, …, DN, которое поступает на внешние выходы первой группы G1_«0» устройства.

Далее младшие разряды входного двоичного числа D1, D2, …, D(N-1), соответствующие единичным значениям в упорядоченном двоичном коде «00…011…1» на выходах группы элементов ИЛИ 2₁, 2₂, …, 2_(N-i), инвертируются в группе элементов XOR 3₁, 3₂, …, 3_(N-i), которые можно рассматривать как элементы «управляемый инвертор», и поступают на выходы Q1, Q2, …, Q(N-i) первого каскада 1₁ и далее на входы A1, А2, …, A(N-i) следующего второго каскада 1₂. При этом первая «единичная» группа входного двоичного числа D1, D2, …, DN преобразуется в нулевые значения, а вторая «нулевая» группа (третья группа во входном числе) преобразуется в единичные значения и т.д.

Во втором каскаде 1₂ аналогично формируется упорядоченный двоичный код «00…011…1» который поступает на внутреннюю шину S₂, где левая единица соответствует старшей единице - началу третьей группы во входном двоичном числе D1, D2, …, DN, а количество нулей соответствует сумме двух групп - первой группе нулей и второй группе единиц во входном двоичном числе D1, D2, …, DN. Во втором блоке 4₂ счета младших упорядоченных единиц аналогично проводится подсчет количества единиц. Полученное количество единиц на втором сумматоре 5₂ вычитается из суммы разрядов всех групп кроме первой, которое поступает с выходов первого блока 4₁ счета младших упорядоченных единиц, и формируется значение, соответствующее количеству единиц во второй «единичной» группе входного двоичного числа D1, D2, …, DN, которое поступает на внешние выходы второй группы G2_«1» устройства.

Далее аналогично инвертируются младшие разряды входных данных второго каскада 1₂, которые поступают на выходы Q1, Q2, …, Q(N-i) второго каскада.

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

Выход Q1 последнего (N-1) каскада 1_(N-1) поступает на первый прямой вход элемента ИЛИ с одним инверсным входом 6, на второй инверсный вход которого поступает значение старшего N-го разряда DN входного двоичного числа.

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

В таблице 1 приведены примеры формирования значений количества нулей и единиц по группам G1, G1, …, G5 (G_N+1) и общего количества групп К при N=4.

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

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

На внешние входы устройства D1, D2, …, DN поступает N разрядное двоичное число без знака. Данные сигналы поступают на входы A1, А2, …, AN первого каскада 1₁. В первом каскаде 1₁ на выходах группы элементов ИЛИ 2₁, 2₂, …, 2_(N-i), объединенных в цепочку, N разрядное двоичное число D1, D2, …, DN преобразуется в упорядоченный двоичный код «00…011…1» с единицами расположенными подряд, начиная с младших разрядов, где левая единица соответствует старшей единице во входном двоичном числе, который поступает на внутреннюю шину S₁. Например, при N=4 для входного числа D4-D1=0010 (таблица 1) на выходах элементов ИЛИ 2₁, 2₂, 2₃ первого каскада 1₁ формируется упорядоченный двоичный код «011», который совместно со старшим разрядом D4=0 входных данных поступает на первую внутреннюю шину S1 и блоке 4₁ вычисляется код «2» суммы младших единиц. Далее этот код «2» поступает на инверсные входы первого сумматора 5₁ и вычитается из кода «4» количества разрядов N=4 входного числа (4-2). Таким образом, на выходах первой «нулевой» группы G1_«0» будет сформирован код «2» соответствующий количеству первых старших нулей во входном числе.

Далее в группе элементов XOR 3₁, 3₂, 3₃ (3_(N-i)) (при N=4) первого каскада 1₁ инвертируются два младших разряды, и формируется код «001» (для входных данных D4-D1=0010 в таблице 1), который поступает на соответствующие выходы Q1, Q2, Q3 и далее на входы A1, А2, A3 второго каскада 1₂.

Во втором каскаде 1₂ на выходах элементов ИЛИ 2₁, 2₂ формируется упорядоченный двоичный код «01», который совместно со значением старшего разряда D4=0 поступают на внутреннюю шину S₂. Затем во втором блоке 4₂ вычисляется код суммы единиц «1» и далее на втором сумматоре 5₂ формируется код «1» как разность «2-1», соответствующий количеству единиц в первой группе во входном числе, и который поступает на выходы второй «единичной» группы G2_«1». Затем в группе элементов XOR 3₁, 3₂ (3_(N-i)) (при N=4) второго каскада 1₂ инвертируются младшие разряды, и формируется код «00», который поступает на соответствующие выходы Q1, Q2 и далее на входы A1, А2 третьего каскада 1₃.

В третьем каскаде 1₃ аналогично формируется упорядоченный двоичный код «0» на выходе элемента ИЛИ 2₁, который поступает на внутреннюю шину S₃, далее в третьем блоке 4₃ вычисляется код суммы единиц «0» и далее на третьем сумматоре 5₃ формируется код «1» как разность «1-0», соответствующий количеству нулей во второй группе во входном числе. Таким образом, на выходах второй «нулевой» группы G3_«0» будет сформирован код «1» соответствующий количеству нулей в третьей группе во входном числе.

Одновременно младшие разряды внутренних шин S₁, S₂, S₃, на которых установлены значения «110», и инверсное значение старшего разряда D4 (DN) входных данных (единичное значение для входных данных 0010) с выхода элемента ИЛИ 6 поступают на входы второго блока 7 счета младших упорядоченных единиц, в котором будет сформирован код «3» соответствующий общему количеству групп нулей и единиц для входного двоичного числа D4-D1=0010, который поступает в выходную группу К=3. При этом также в группах будут установлены значения: G1_«0»=2, G2_«1»=1, G3_«0»=1.

Аналогично для входного двоичного числа D4-D1=0101, при нулевом значении старшего разряда D4=0 (DN) входных данных, формируются значения нулей и единиц G1_«0»=1, G2_«1»=1, G3_«0»=1, G4_«1»=1 и общее количество групп К=4, соответствующее максимальному количеству групп при количестве разрядов N=4 входного числа.

Для входного двоичного числа «все нули» D4-D1=0000 на выходах элементов ИЛИ 2₁, 2₂, 2₃ первого каскада 1₁ формируется также «нулевой» упорядоченный двоичный код «000», и далее также формируется «нулевой» код суммы «0» младших единиц в блоке 4₁ (при этом D4=0), который поступает на инверсные входы первого сумматора 5₁ и вычитается из кода «4» количества разрядов N=4 входного числа (4-0). Таким образом, на выходах первой «нулевой» группы G1_«0» будет сформирован код «4» (G1_«0»=4), соответствующий количеству всех нулевых разрядов во входном числе D4-D1=0000. При этом нулевые значения также будут установлены на всех внутренних шинах S1, S2, S3, в том числе, и на младших первых разрядах шин, которые поступают на входы второго блока 7 счета младших упорядоченных единиц, на который также поступает единичное значение с выхода элемента ИЛИ 6 с одним инверсным входом, который соединен со старшим разрядом входных данных D4=0, и поэтому на выходах второго блока 7 будет сформирован код «1», который поступает на выходы общего количества групп К=1.

Для входных двоичных чисел D4-D1=1XXX, при единичном значении старшего разряда D4=1 (DN) входных данных, на выходах элементов ИЛИ 2₁, 2₂, 2₃ первого каскада 1₁ всегда формируется упорядоченный двоичный код все единицы «111», для которого совместно с D4=1 вычисляется код суммы «4» младших единиц в блоке 4₁, который поступает на инверсные входы первого сумматора 5₁ и вычитается из кода «4» количества разрядов N=4 входного числа (4-4). При этом на выходах первой «нулевой» группы G1_«0» будет сформирован код «0», что соответствует входным данным, когда старший разряд имеет единичное значение D4=1.

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

Во втором каскаде 1₂ на выходах элементов ИЛИ 2₁, 2₂ формируется упорядоченный двоичный код «11», который совместно со значением старшего разряда D4=1 поступают на внутреннюю шину S₂. Затем во втором блоке 4₂ вычисляется код суммы единиц «3» и далее на втором сумматоре 5₂ формируется код «1» как разность «4-3», соответствующий количеству единиц в первой группе во входном числе, и который поступает на выходы второй «единичной» группы G2_«1»=1. Далее аналогично вычисляются последующие значения нулевых и единичных групп и на выходах групп устройства устанавливаются значения G1_«0»=0, G2_«1»=1, G3_«0»=1, G4_«1»=1, G5_«0»=1. Одновременно единичные значения с младших разрядов всех внутренних шинах S1, S2, S3 и с выхода элемента ИЛИ 6 с одним инверсным входом (так как единичное значение установлено на выходе Q1 третьего каскада 1₃) поступают на входы второго блока 7 счета младших упорядоченных единиц и формируется код «4» общего количества групп К=4.

Для входного двоичного числа «все единицы» D4-D1=1111 на выходах элементов ИЛИ 2₁, 2₂, 2₃ первого каскада 1₁ формируется также упорядоченный двоичный код «111» и на внутренней шине S1 код «все единицы» «1111», для которого формируется код суммы «4» младших единиц в блоке 4₁ (так как при этом D4=1), который поступает на инверсные входы первого сумматора 5₁ и вычитается из кода количества разрядов N=4 входного числа (4-4). Таким образом, на выходах первой «нулевой» группы G1_«0» будет сформирован код «0» (G1_«0»=0), что соответствует отсутствию «нулевой» первой группы во входном числе. Далее в группе элементов XOR 3₁, 3₂, 3₃ (при N=4) первого каскада 1₁ инвертируются все младшие разряды, и формируется код «000», который поступает на соответствующие выходы Q1, Q2, Q3 и далее на входы A1, А2, A3 второго каскада 1₂. Затем во втором каскаде 1₂ на выходах элементов ИЛИ 2₁, 2₂ формируется двоичный код «00», который поступает на внутреннюю шину S₂. Затем во втором блоке 4₂ вычисляется код суммы единиц «0», который вычитается из кода «4» с первого блока 4₁ (4-0) и формируется код «4» соответствующий количеству единиц в группе, который поступает на выходы второй «единичной» группы G2_«1»=4. Одновременно единичное значение с младшего первого разряда первой внутренней шины S₁ и нулевое значение с выхода элемента ИЛИ 6 поступают на вход второго блока 7 счета младших упорядоченных единиц и формируется код «1» общего количества групп К=1.

Таким образом, на выходах устройства G1, G1, …, G5(N+1) формируются двоичные коды, соответствующие количеству нулей и единиц в группах входного двоичного числа, при этом в нечетных группах Gнч указывается количество нулей, а в четных группах Gчт количество единиц, а также формируется общее количество групп К.

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

Изобретение относится к области вычислительной техники. Технический результат заключается в расширении арсенала средств того же назначения. Устройство для определение количества нулей или единиц по группам в двоичном числе содержит N разрядов входного двоичного числа D1, …, DN, (N+1) групп выходных данных G1, …, G(N+1), выходную группу К количества групп нулей и единиц, группу из (N-1) внутренних шин упорядоченных двоичных чисел S1, …, S_(N-1), (N-1) каскадов формирователя упорядоченных двоичных чисел 1₁, 1₂, …, 1_N, и каждый i-й каскад 1_i (i=1, …, (N-1)) содержит группу из (N-i) элементов ИЛИ 2₁,…, 2_(N-i), группу из (N-i) элементов XOR 3₁, 3₂, …, 3_(N-i), группу из (N+1-i) входов A1, …, A(N+1-i), группу из (N-i) выходов Q1, …, Q(N-i) в следующий каскад и группу из (N+1-i) выходов разрядов соответствующей i-й внутренней шины S_i, а также в устройство введены первая группа из (N-i) блоков счета младших упорядоченных единиц 4₁, …, 4_(N-i), группа из N сумматоров 5₁,…, 5_N, с инверсной группой входов второго слагаемого, элемент ИЛИ с одним инверсным входом 6 и второй блок счета младших упорядоченных единиц 7, и каждый i-й сумматор 5_i содержит ]log₂(N+3-i)[ (большее целое) разрядов, последний N-й сумматор 5_N содержит два разряда, а выходы количества групп К содержат ]log₂(N+1)[ (большее целое) разрядов. 2 ил., 1 табл.

Устройство для определения количества нулей и единиц по группам в двоичном числе содержит 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 содержит два разряда, причем N разрядов входного двоичного числа D1, D2, …, DN соединены с одноименными входами A1, А2, …, AN первого каскада 1₁, в каждом i-м каскаде первые (N-i) входов A1, А2, …, A(N-i), кроме последнего входа A(N+1-i), также соединены со вторыми входами соответствующих одноименных элементов ИЛИ 2₁, 2₂, …, 2_(N-i) и вторыми входами одноименных элементов XOR 3₁, 3₂, …, 3_(N-i), а первые входы первых (N-i-1) элементов 2₁, 2₂, …, 2_(N-i-1) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 2₂, 2₃, …, 2_(N-i) из группы элементов ИЛИ, первый вход последнего элемента 2_(N-i) из группы элементов ИЛИ соединен с последним входом запроса A(N+1-i) i-го каскада, выходы (N-i) элементов ИЛИ 2₁, 2₂, …, 2_(N-i) соединены также с первыми входами соответствующих одноименных элементов XOR 3₁, 3₂, …, 3_(N-i), выходы которых являются группой (N-i) выходов Q1, Q2, …, Q(N-i) в следующий каскад каждого i-го каскада, а выходы всех (N-i) элементов ИЛИ 2₁, 2₂, …, 2_(N-i) являются одноименными первыми младшими (N-i) разрядами соответствующей i-й внутренней шины S_i из группы S1, S2, …, S_(N-1), а последний вход A(N+1-i) i-го каскада является старшим (N+1-i)-м разрядом соответствующей i-й внутренней шины S_i, причем в первых (N-2) каскадах, кроме последнего (N-1)-го каскада, (N-i) выходов в следующий (i+1)-й каскад Q1, Q2, …, Q(N-i) соединены с соответствующими (N-i) одноименными входами A1, А2, …, A(N-i) следующего (i+1)-го каскада, все разряды каждой i-й внутренней шины S_i из группы S1, S2, …, S_(N-1) соединены с входами соответствующего одноименного блока 4_i из первой группы из (N-i) блоков счета младших упорядоченных единиц, а выходы каждого i-го блока 4_i соединены с инверсной группой входов второго слагаемого i-го сумматора 5_i и первой группой прямых входов первого слагаемого (i+1)-го сумматора 5_(i+1) из группы из N сумматоров 5₁, 5₂, …, 5_N, выходы которых являются соответствующими первыми N группами выходных данных G1, G2, …, GN, а последний одноразрядный выход G(N+1) соединен с выходом Q1 последнего (N-1) каскада 1_(N-1), который также соединен со второй инверсной группой входов последнего N-го сумматора 5_N и первым прямым входом элемента ИЛИ с одним инверсным входом 6, второй инверсный вход которого соединен со старшим N-м разрядом DN входного двоичного числа, на группу первых прямых входов первого сумматора 5₁ подано двоичное число «N», а на входы переносов CI всех N сумматоров 5₁, 5₂, …, 5_N подано значение логической единицы, младшие первые разряды всех (N-1) внутренних шин упорядоченных двоичных чисел S1, S2, …, S_(N-1) соединены с соответствующими входами второго блока счета младших упорядоченных единиц 7, а также соответствующий N-й вход которого соединен с выходом элемента ИЛИ с одним инверсным входом 6, а выходы второго блока счета младших упорядоченных единиц 7 являются выходной группой К количества групп нулей и единиц, причем количество групп К содержит ]log₂(N+l)[ (большее целое) разрядов.