Устройство для определения количества единиц (нулей) в двоичном числе
Владельцы патента RU 2446442:
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ЯДЕРНЫЙ УНИВЕРСИТЕТ "МИФИ" (НИЯУ МИФИ) (RU)
Изобретение относится к вычислительной технике, в частности к устройствам обработки данных, и может быть использовано для построения средств автоматики, функциональных узлов систем управления. Техническим результатом является уменьшение аппаратных затрат, увеличение быстродействия устройства, расширение функциональных возможностей. Устройство содержит блок управляемой инверсии, состоящий из n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (n - количество разрядов входного числа), элементы ИЛИ и модули, состоящие из элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, которые объединены в группы, состоящие из ярусов, и объединены в k-каскадов (k=]log2n[), так, что каждый i-й каскад содержит g(i)=n/2i групп (i=1, …, k), каждая группа i-го каскада разделена на j ярусов (j=1, …, i), при этом первый ярус каждой группы i-го каскада содержит i модулей, а каждый j-й ярус каждой группы i-го каскада (j=2, …, i,) содержит (i-j) модулей и элемент ИЛИ. 1 ил., 3 табл.
Изобретение относится к вычислительной технике, в частности к устройствам обработки данных, и может быть использовано для построения средств автоматики, функциональных узлов систем управления.
Известно устройство для подсчета количества единиц в двоичном коде (SU №1795455 A1, МПК G06F 7/50, заявлено 29.12.1990, опубликовано 15.02.1993, Бюл. №6), содержащее n-разрядный входной регистр, выходной регистр, узел управляемой инверсии, связанный с управляющим входом, преобразователь двоичного кода в уплотненный код, модифицированную матрицу модулей, каждый из которых содержит элемент И и элемент ИЛИ, состоящую из (n+1)/2 строк модулей, преобразователь уплотненного кода в двоичный код количества единиц.
Недостатком данного устройства является то, что проводится несколько преобразований кодов - входного двоичного кода в уплотненный код, формирование итогового уплотненного кода, равного количеству единиц во входном коде, преобразование уплотненного кода в двоичный код количества единиц.
К причинам, препятствующим достижению указанного ниже технического результата, относятся большие аппаратные и временные затраты на преобразование, которые пропорциональны n-разрядам входного кода.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип параллельный счетчик единичных сигналов (RU №2260204 C1, МПК G06F 5/00, F7/50, H03K 21/10, K 21/12, K 23/00, заявлено 11.05.2004, опубликовано 10.09.2005, Бюл. №25), содержащий модули, состоящие из элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, причем первый и второй входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединены соответственно с первым и втором входами и элемента И, и определяет количество единиц во входном кортеже (Х8, …, X1).
Недостатком данного устройства является то, что двоичный код числа единичных сигналов формируется при последовательном прохождении сигналов вдоль строки через элементы ИСКЛЮЧАЮЩЕЕ ИЛИ и элементы И.
К причинам, препятствующим достижению указанного ниже технического результата, относятся большие аппаратные и временные затраты, которые пропорциональны разрядам входного кода, отсутствие средств, обеспечивающих определение количества нулей во входном коде.
Техническим результатом изобретения является уменьшение аппаратных затрат, увеличение быстродействия устройства, расширение функциональных возможностей за счет определения количества единиц или нулей во входном n-разрядном числе.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для определения количества единиц (нулей) в двоичном числе, содержащее модули, состоящие из элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, причем первые и вторые входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединены соответственно с первым и втором входами элемента И и являются соответственно первым и вторым входами модуля, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ является первым выходом модуля, выход элемента И является вторым выходом модуля, введены элементы ИЛИ и блок управляемой инверсии, состоящий из n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, где n - количество разрядов входного числа, причем первые входы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены между собой и подключены к внешнему управляющему входу, вторые входы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с соответствующими n-внешними входами входного числа, выходы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ являются соответственно первым - n-м выходами блока управляемой инверсии, модули объединены в ярусы и группы, которые объединены в k-каскадов (k=]log2n[большее целое), при этом i-й каскад содержит g(i)=n/2i групп (i=1, …, k), каждая группа i-го каскада разделена на j ярусов (j=1, …, i,), каждая группа i-го каскада имеет 2i входов группы, которые являются входами первого яруса группы, и (i+1) выходов группы (i=1, …, k), первый ярус каждой группы соответствующего i-го каскада содержит соответственно i модулей и имеет 2i входов и 2i выходов (i=1, …, k), второй - j-й ярусы каждой группы соответствующего i-го каскада (i=3, …, k, j=2, …, (i-1)) содержат (i-j) модулей и элемент ИЛИ и имеют (2(i-j)+2) входов яруса и (2(i-j)+1) выходов яруса, i-й ярус каждой группы соответствующего i-го каскада (i=2, …, k) содержит элемент ИЛИ и имеет два входа и один выход, первый и второй входы первого яруса первой - (n/2)-й групп первого каскада соединены соответственно с первым и вторым входами соответствующих модулей первого яруса первой - (n/2)-й групп первого каскада, нечетные первый, третий - (n-1)-й выходы блока управляемой инверсии соединены с первыми входами первого яруса соответственно первой - (n/2)-й групп первого каскада, четные второй, четвертый - n-й выходы блока управляемой инверсии соединены со вторыми входами первого яруса соответственно первой - (n/2)-й групп первого каскада, первый и второй выходы модулей первого яруса первой - (n/2)-й групп первого каскада являются соответственно первым и вторым выходами первого яруса соответствующих первой - (n/2)-й групп первого каскада, первый и второй входы первого - i-го модуля первого яруса каждой группы второго - i-го каскадов являются соответственно первым, вторым, третьим - (2i)-м входами первого яруса соответствующей группы второго - i-го каскадов (i=2, …, k), первый и второй выходы первого - i-го модуля первого яруса каждой группы второго - i-го каскадов являются соответственно первым, вторым, третьим - (2i)-м выходами первого яруса соответствующей группы второго - i-го каскадов (i=2, …, k), первый и второй входы первого - (i-j)-го модулей соответственно второго - j-го яруса каждой группы третьего - k-го каскада являются соответственно первым, вторым - 2(i-j)-м входами соответствующего второго - j-го яруса соответствующей группы третьего - k-го каскада (i=3, 4, …, k, j=2, 3, …, (i-1)), первый и второй выходы первого - (i-j)-го модулей соответственно второго - j-го яруса каждой группы третьего - k-го каскада являются соответственно первым, вторым - 2(i-j)-м выходами соответствующего второго - j-го яруса соответствующей группы третьего - k-го каскада (i=3, 4, …, k, j=2, 3, …, (i-1)), первый и второй входы элемента ИЛИ соответственно второго - j-го яруса каждой группы соответственно второго - k-го каскада являются соответственно (2(i-j)+1)-м и (2(i-j)+2)-м входами соответствующего второго - j-го яруса соответствующей группы соответствующего второго - k-го каскада (i=2, 3, …, k, j=2, 3, …, i), выход элемента ИЛИ соответственно второго - j-го яруса каждой группы соответственно второго - k-го каскада является соответственно ((i-j)+1)-м выходом соответствующего второго - j-го яруса соответствующей группы соответствующего второго - k-го каскада (i=2, 3, …, k, j=2, 3, …, i), второй, третий - (2(i-j)+1)-й выходы соответственно первого - j-го яруса каждой группы соответственно второго - i-го каскада соединены соответственно с первым, вторым - (2(i-j))-м входами соответствующего второго - (j+1)-го яруса соответствующей группы соответственно второго - i-го каскада (i=2, 3, …, k), j=1, 2, …, (i-1)), первые выходы соответственно первого - j-го яруса каждой группы соответствующего второго - i-го каскада являются соответственно первым, вторым - j-м выходами соответствующей группы соответственно второго - i-го каскада (i=2, 3, …, k, j=2, …, i), старший (2i)-й выход 1-го яруса каждой группы соответственно второго - i-го каскадов являются соответственно старшим (i+1)-м выходом соответствующей группы соответственно второго - i-го каскадов (i=2, 3, …, k), первый, второй -(z+1)-й выходы нечетных первой, третьей - (s-1)-й групп z-го каскада, соединены соответственно с нечетными первым, третьим - (2z-1)-м входами соответственно первой, второй - (s/2)-й групп (z+1)-го каскада (z=1, …, (k-1), s=2, 4, 6, …, n/2z), первый, второй - (z+1)-й выходы четных второй, четвертой - s-й групп z-го каскада соединены соответственно с четными вторым, четвертым - (2z)-м входами соответственно первой, второй - (s/2)-й группы (z+1)-го каскада (z=1, …, (k-1), s=2, 4, 6,…, n/2z), первый, второй - (k+1)-й выходы группы k-го каскада являются соответственно первым, вторым - (k+1)-м выходами устройства.
На фиг.1 представлена схема предлагаемого устройства для определения количества единиц (нулей) в двоичном числе при n=16.
На фиг.1 приняты следующие обозначения: первые ярусы групп в каскадах обозначены 11, 12, …, 18 (индекс указывает номер группы), вторые ярусы групп в каскадах соответственно 21, 22, …, 24, третьи ярусы групп в каскадах - 31, 32, четвертый ярус группы - 41, при этом соответствующие группы объединены в четыре каскада 51, 52, …, 54; блок управляемой инверсии 6 содержит n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ; логические модули 7j m (первая цифра индекса j соответствует j-му ярусу группы, а вторая цифра m соответствует номеру модуля в группе); элементы ИЛИ 8j (индекс j соответствует j-му ярусу группы); элемент И 9 и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 10 в составе логических модулей 7j m; внешний управляющий вход У, внешние входы входного двоичного числа X1, …, X16 (Xn при n разрядности), внешние выходы устройства В5 (B(k+1)), …, В1, на которых формируется двоичный код количества единиц (нулей), при этом В5 (B(k+1)) - старший разряд, В1 - младший разряд.
Логические модули 7 состоят из элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 10 и элемента И 9, причем первые и вторые входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 10 соединены соответственно с первым и вторым входами элемента И 9 и являются соответственно первым и вторым входами модулей 7, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 10 является первым выходом модулей 7, выход элемента И 9 является вторым выходом модуля 7. Блок 6 управляемой инверсии состоит из n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, где n - количество разрядов входного числа, причем первые входы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены между собой и подключены к внешнему управляющему входу У, а вторые входы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с соответствующими n-внешними входами входного двоичного числа X1, …, X16 (Xn при n разрядности), выходы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ являются соответственно первым - n-м выходами блока 6 управляемой инверсии,
Модули 7 и элементы ИЛИ 8 объединены в группы, которые объединены в k-каскадов 5k (где k=]log2n[). Первый каскад 51 - i-й каскад 5i содержит соответственно g(i)=n/2i групп (i=1, …, k), при этом каждая группа i-го каскада разделена на j ярусов (j=1, …, i). В таблице 1 приведено количество групп в каскадах и ярусов в группах в зависимости от разрядности n входного числа. На фиг.1 первые ярусы групп в каскадах обозначены 11, 12, …, 1n/2 i (индекс указывает номер группы), вторые ярусы групп в каскадах соответственно 21, 22, …, 2g(i), третьи ярусы групп в каскадах - 31, 32, …, 3g(i) и т.д. для других ярусов. Каждая группа i-го каскада имеет (i+1) выходов и 2i входов, которые являются входами первого яруса группы. Количество входов и выходов групп в первом 51 - k-м 5k каскадах приведено в таблице 1.
Первый ярус каждой группы i-го каскада содержит i логических модулей 7, при этом каждая группа первого каскада содержит модули 711, второго каскада соответственно модули 711 и 712, третьего каскада соответственно модули 711, 712, 713 и т.д. для других каскадов (первая цифра индекса указывает первый ярус, а вторая цифра - номер модуля). Второй - j-й ярусы каждой группы соответствующего i-го каскада (i=3, …, (k-1), j=2, …, (i-1)) содержит (i-j) логических модулей 7, в составе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 10 и элемента И 9, и один элемент ИЛИ 8, и имеет (2(i-j)+2) входов и (i-j+1) выходов. На фиг.1 второй ярус каждой группы третьего каскада содержит один модуль 721 и один элемент ИЛИ 82, второй ярус каждой группы четвертого каскада содержит модули 721, 722 и один элемент ИЛИ 82, третий ярус каждой группы четвертого каскада содержит один модуль 731 и один элемент ИЛИ 83 (первая цифра индекса указывает номер яруса, а вторая цифра - номер модуля).
Старший j-й ярус каждой группы при j=i (i=2, …, k) содержит только один элемент ИЛИ 8j (для второго каскада это 82, третьего - 83, четвертого - 84 и т.д.) и имеет два входа и один выход. Количество модулей 7 и элементов ИЛИ 8, количество входов/выходов по группам, ярусам и каскадам в зависимости от разрядности n входного числа приведено в таблице 1 (для модулей 7 введено обозначение М).
Первый и второй входы первого яруса первой - (n/2)-й групп первого каскада 51 соединены соответственно с первым и вторым входами модулей 711 первого яруса соответствующих первой - (n/2)-й групп первого каскада 51, при этом нечетные первый, третий - (n-1)-й выходы блока 6 управляемой инверсии соединены с первыми входами первого яруса соответственно первой - (n/2)-й групп первого каскада 51, а четные второй, четвертый - n-й выходы блока управляемой инверсии соединены со вторыми входами первого яруса соответственно первой - (n/2)-й групп первого каскада 51; первый и второй выходы модулей 711 первого яруса первой - (n/2)-й групп первого каскада 51 являются соответственно первым и вторым выходами первого яруса соответствующих первой - (n/2)-й групп первого каскада 51.
Первый и второй входы первого - i-го модуля 7 первого яруса каждой группы второго - i-го каскадов 5 являются соответственно первым, вторым, третьим - (2i)-м входами первого яруса соответствующей группы второго - i-го каскадов (i=2, …, k); первый и второй выходы первого - i-го модуля 7 первого яруса каждой группы второго - i-го каскадов 5 являются соответственно первым, вторым, третьим - (2i)-м выходами первого яруса соответствующей группы второго - i-го каскадов (i=2, …, k).
Первый и второй входы первого - (i-j)-го модулей 7 соответственно второго - j-го яруса каждой группы третьего - k-го каскада 5 являются соответственно первым, вторым - 2(i-j)-м входами соответствующего второго - j-го яруса соответствующей группы третьего - k-го каскада (i=3, 4, …, k, j=2, 3, …, (i-1)); первый и второй выходы первого - (i-j)-го модулей 7 соответственно второго - j-го яруса каждой группы третьего - k-го каскада 5 являются соответственно первым, вторым - 2(i-j)-м выходами соответствующего второго - j-го яруса соответствующей группы третьего -k-го каскада (i=3, 4, …, k, j=2, 3, …, (i-1)).
Первый и второй входы элемента ИЛИ 8 соответственно второго - j-го яруса каждой группы соответственно второго - k-го каскада 5 являются соответственно (2(i-j)+1)-м и (2(i-j)+2)-м входами соответствующего второго - j-го яруса соответствующей группы соответствующего второго - k-го каскада (i=2, 3, …, k, j=2, 3, …, i); выход элемента ИЛИ 8 соответственно второго - j-го яруса каждой группы соответственно второго - k-го каскада 5 является соответственно ((i-j)+1)-м выходом соответствующего второго - j-го яруса соответствующей группы соответствующего второго - k-го каскада (i=2, 3, …, k, j=2, 3, …, i).
Второй, третий - (2(i-j)+1)-й выходы соответственно первого - j-го яруса каждой группы соответственно второго - i-го каскада 5 соединены соответственно с первым, вторым - (2(i-j))-м входами соответствующего второго - (j+1)-го яруса соответствующей группы соответственно второго - i-го каскада (i=2, 3, …, k), j=1, 2, …, (i-1)).
Первые выходы соответственно первого - j-го яруса каждой группы соответствующего второго - i-го каскада 5 являются соответственно первым, вторым - j-м выходами соответствующей группы соответственно второго - i-го каскада (i=2, 3, …, k, j=2, …, i); старший (2i)-й выход первого яруса каждой группы соответственно второго - i-го каскадов 5 является соответственно старшим (i+1)-м выходом соответствующей группы соответственно второго - i-го каскадов (i=2, 3, …, k).
Первый, второй - (z+1)-й выходы нечетных первой, третьей - (s-1)-й групп z-го каскада 5z соединены соответственно с нечетными первым, третьим - (2z-1)-м входами соответственно первой, второй - (s/2)-й групп (z+1)-го каскада 5z+i, (z=1, …, (k-1), s=2, 4, 6, …, n/2z); первый, второй - (z+1)-й выходы четных второй, четвертой - s-й групп z-го каскада 5z соединены соответственно с четными вторым, четвертым - (2z)-м входами соответственно первой, второй - (s/2)-й группы (z+1)-го каскада 5z+1 (z=1, …, (k-1), s=2, 4, 6, …, n/2z).
Первый, второй - (k+1)-й выходы группы k-го каскада 5k являются соответственно первым, вторым - (k+1)-м внешними выходами В1, …, В5 (B(k+1)) устройства, на которых формируется двоичный код количества единиц (нулей) во входном двоичном числе, при этом В5 (B(k+1)) - старший разряд, В1 - младший разряд.
Предлагаемое устройство для определения количества единиц (нулей) в двоичном числе работает следующим образом. На его первый - шестнадцатый (n-й) входы подаются соответственно входные сигналы X1-Х16 (Xn). Сигнал «0» на управляющем входе У пропускает через блок 6 инверсии входную информацию без изменений (режим счета единиц). Если на управляющем входе у сигнал равен «1», то блок 6 инвертирует каждый входной разряд, обеспечивая режим счета количества нулей с помощью той же аппаратуры.
Группы 11, 12, …, 18 первого каскада 51 содержат только один ярус модулей 711 и преобразуют пары четного и следующего нечетного разрядов входного числа в код суммы единиц (нулей), так, что на выходах групп формируется двухразрядный код количества единиц (нулей) равный 00, 01 или 10.
На выходах каждой группы второго каскада 52 образуется код единиц (нулей) для четырехразрядных групп входного числа в код суммы единиц (нулей) в диапазоне 000-100. При этом группы второго каскада 52 реализуют на своих выходах сигналы в соответствии с таблицей 2 истинности для двух пар входных кодов (где x - неопределенное состояние). Входы D2, D1, А2, А1 являются выходами групп первого каскада. Входы D2 и А2 соответствуют количеству единиц, равному 2, входы D1 и A1 - равному 1, выходы F4, F2, F1 - равному соответственно 4, 2, 1 единицам. В соответствии с таблицей 2, после минимизации, на выходах групп реализуются логические функции:
первый выход F1=D1⊕A1 (младший разряд);
второй выход F2=(D2⊕А2)∨(D1&A1);
третий выход F4=D2&А2 (старший разряд).
При этом функции F1, F4 (D2⊕А2), (D1&A1) реализуются в первом ярусе второго каскада, а итоговая функция F2 на элементе ИЛИ - во втором ярусе.
На выходах каждой группы третьего каскада 53 образуется код единиц (нулей) для восьмиразрядных групп входного числа в код суммы единиц (нулей) в диапазоне 0000-1000. При этом группы третьего каскада 53 реализуют на своих выходах сигналы в соответствии с таблицей 3 истинности для двух трехразрядных входных кодов (где x - неопределенное состояние). Входы D4, D2, D1, А4, А2, A1 являются выходами групп второго каскада. Входы D4 и А4 соответствуют количеству единиц, равному 4, входы D2 и А2 - равному 2, входы D1 и A1 - равному 1, выходы F8, F4, F2, F1 - равному соответственно 8, 4, 2, 1 единицам. В соответствии с таблицей 3, после минимизации, на выходах групп реализуются логические функции:
первый выход F1=D1⊕A1 (младший разряд);
второй выход F2=(D2⊕А2)⊕(D1&А1);
третий выход F4=(D4⊕А4)∨(D2&А2)∨((D2⊕А2)&(D1&A1));
четвертый выход F8=D4&А4 (старший разряд).
При этом функции F1, F8 (D4⊕А4), (D2&А2), (D2⊕А2), (D1&A1) реализуются первым ярусом третьего каскада, а функция ИСКЛЮЩАЮЩЕЕ ИЛИ (⊕) для F2, функция ИЛИ (∨) для (D4⊕А4) ∨ (D2&А2) и функция И (&) для ((D2⊕А2)&(D1&A1)) реализуются вторым ярусом. Итоговая функция F4 на элементе ИЛИ реализуется третьим ярусом второго каскада.
На выходах четвертого 54 - k-го 5k каскадов аналогично формируются выходы F1 только на элементах ИСКЛЮЩАЮЩЕЕ ИЛИ, выходы F2-F(k-1) - на элементах ИСКЛЮЩАЮЩЕЕ ИЛИ и элементах И текущего каскада, выход Fk формируется при последовательном выполнении функции ИЛИ, а выход F(k+1) формируется на старшем 2k-м выходе первого яруса k-го каскада.
Таким образом, на выходах B(k+1), B(k), …, В1 группы k-го каскада формируется двоичный код числа единиц (нулей) во входном двоичном числе.
Оценим аппаратные затраты для определения количества единиц (нулей) при n=8: количество каскадов равно трем, с соответствующим количеством групп, ярусов и составом групп (см. таблицу 1). Общее количество элементов - 28 (без учета элементов блока 6 инверсии): в т.ч. элементов ИСКЛЮЧАЮЩЕЕ ИЛИ - 12; элементов И - 12; элементов ИЛИ - 4. В прототипе при n=8 необходимо 30 элементов. При количестве n=16 входных разрядов в предлагаемом устройстве требуется 73 элемента (с учетом элементов блока 6 инверсии - 89 элементов), а в прототипе необходимо 117 элементов. Таким образом, предлагаемое устройство обладает меньшими аппаратными затратами в сравнении с прототипом и более широкими функциональными возможностями за счет определения на том же оборудовании как количества единиц, так и количества нулей.
Оценим быстродействие предлагаемого устройства для определения количества единиц (нулей) при n=8: определим максимальное время задержки Tмакс - это время складывается из времени прохождения сигнала через шесть ярусов трех каскадов и равно:
Tмакс=2t⊕+2tи+2tили≈6τ (7τ с учетом блока 6 инверсии),
где t⊕, tи, tили - задержки соответственно элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, И, ИЛИ;
τ - средняя задержка на элемент.
В прототипе для подсчета единиц время задержки составляет:
Tмакс=7t⊕+2tи≈9τ.
Время задержки при n=16 для предлагаемого устройства составит
Tмакс=4t⊕+2tи+4tили≈10τ (11τ с учетом блока 5 инверсии), а в прототипе время задержки составит:
Tмакс=14t⊕+3tи≈17τ.
В предлагаемом устройстве время задержки меньше в сравнении с прототипом, т.к. в прототипе сигнал проходит последовательно по строке и столбцу соответственно элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и И, то время задержки при изменении разрядности n входного числа увеличивается прямо пропорционально количеству n разрядов входного числа, а в предлагаемом устройстве время задержки изменяется пропорционально логарифму log2n. Таким образом, предлагаемое устройство обладает большим быстродействием в сравнении с прототипом.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство для определения количества единиц (нулей) в двоичном числе обладает регулярностью узлов и связей и соответствует заявляемому техническому результату - расширению функциональных возможностей, сокращению аппаратных затрат и увеличению быстродействия.
| Таблица 1 | |||||
| Каскад, i | 1 | 2 | 3 | 4 | 5 |
| Количество Групп, g(i) | n/2 | n/4 | n/8 | n/16 | n/32 |
| Количество входов/выходов групп | 2/2 | 4/3 | 6/4 | 8/5 | 16/6 |
| Состав элементов групп | |||||
| 1-й ярус, j=1 | 1М | 2M | 3М | 4М | 5М |
| 2-й ярус, j=2 | - | 1ИЛИ | 1М + 1ИЛИ | 2М + 1ИЛИ | 3М + 1ИЛИ |
| 3-й ярус, j=3 | - | - | 1ИЛИ | 1М + 1ИЛИ | 2М + 1ИЛИ |
| 4-й ярус, j=4 | - | - | - | 1ИЛИ | 1М + 1ИЛИ |
| 5-й ярус, j-5 | - | - | - | - | 1ИЛИ |
| Количество входов/выходов ярусов | |||||
| 1-й ярус j=1 | 2/2 | 4/4 | 6/6 | 8/8 | 16/16 |
| 2-й ярус, j=2 | - | 2/1 | 4/3 | 6/5 | 14/13 |
| 3-й ярус, j=3 | - | - | 2/1 | 4/3 | 6/5 |
| 4-й ярус, j=4 | - | - | - | 2/1 | 4/3 |
| 5-й ярус, j=5 | - | - | - | - | 2/1 |
| Таблица 2 | ||||||
| Входы | Выходы | |||||
| D2 | D1 | А2 | А1 | F4 | F2 | F1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | x | x | x |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | x | x | x |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | x | x | x |
| 1 | 1 | 0 | 0 | x | x | x |
| 1 | 1 | 0 | 1 | x | x | x |
| 1 | 1 | 1 | 0 | x | x | x |
| 1 | 1 | 1 | 0 | x | x | x |
| Таблица 3 | |||||||||
| Входы | Выходы | ||||||||
| D4 | D2 | D1 | А4 | А2 | А1 | F8 | F4 | F2 | F1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 | x | x | x | x |
| 0 | 0 | 0 | 1 | 1 | 0 | x | x | x | x |
| 0 | 0 | 0 | 1 | 1 | 1 | x | x | x | x |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | x | x | x | x |
| 0 | 0 | 1 | 1 | 1 | 0 | x | x | x | x |
| 0 | 0 | 1 | 1 | 1 | 1 | x | x | x | x |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | x | x | x | x |
| 0 | 1 | 0 | 1 | 1 | 0 | x | x | x | x |
| 0 | 1 | 0 | 1 | 1 | 1 | x | x | x | x |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | x | x | x | x |
| 0 | 1 | 1 | 1 | 1 | 0 | x | x | x | x |
| 0 | 1 | 1 | 1 | 1 | 1 | x | x | x | x |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | x | x | x | x |
| 1 | 0 | 0 | 1 | 1 | 0 | x | x | x | x |
| 1 | 0 | 0 | 1 | 1 | 1 | x | x | x | x |
| 1 | 0 | 1 | x | x | x | x | x | x | x |
Устройство для определения количества единиц (нулей) в двоичном числе, содержащее модули, состоящие из элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, причем первые и вторые входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединены соответственно с первым и втором входами элемента И и являются соответственно первым и вторым входами модуля, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ является первым выходом модуля, выход элемента И является вторым выходом модуля, отличающееся тем, что введены элементы ИЛИ и блок управляемой инверсии, состоящий из n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, где n - количество разрядов входного числа, причем первые входы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены между собой и подключены к внешнему управляющему входу, вторые входы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с соответствующими n-внешними входами входного числа, выходы n-элементов ИСКЛЮЧАЮЩЕЕ ИЛИ являются соответственно первым - n-м выходами блока управляемой инверсии, модули объединены в ярусы и группы, которые объединены в k-каскадов (k=]log2n[большее целое), при этом i-й каскад содержит g(i)=n/2i групп (i=1, …, k), каждая группа i-го каскада разделена нa j ярусов (j=1, …, i,), каждая группа i-го каскада имеет 2i входов группы, которые являются входами первого яруса группы, и (i+1) выходов группы (i=1, …, k), первый ярус каждой группы соответствующего i-го каскада содержит соответственно i модулей и имеет 2i входов и 2i выходов (i=1, …, k), второй - j-й ярусы каждой группы соответствующего i-го каскада (i=3, …, k, j=2, …, (i-1)), содержат (i-j) модулей и элемент ИЛИ и имеют (2(i-j)+2) входов яруса и (2(i-j)+1) выходов яруса, i-й ярус каждой группы соответствующего i-го каскада (i=2, …, k), содержит элемент ИЛИ и имеет два входа и один выход, первый и второй входы первого яруса первой - (n/2)-й групп первого каскада соединены соответственно с первым и вторым входами соответствующих модулей первого яруса первой - (n/2)-й групп первого каскада, нечетные первый, третий - (n-1)-й выходы блока управляемой инверсии соединены с первыми входами первого яруса соответственно первой - (n/2)-й групп первого каскада, четные второй, четвертый - n-й выходы блока управляемой инверсии соединены со вторыми входами первого яруса соответственно первой - (n/2)-й групп первого каскада, первый и второй выходы модулей первого яруса первой - (n/2)-й групп первого каскада являются соответственно первым и вторым выходами первого яруса соответствующих первой - (n/2)-й групп первого каскада, первый и второй входы первого - i-го модуля первого яруса каждой группы второго - i-го каскадов являются соответственно первым, вторым, третьим - (2i)-м входами первого яруса соответствующей группы второго - i-го каскадов (i=2, …, k), первый и второй выходы первого - i-го модуля первого яруса каждой группы второго - i-го каскадов являются соответственно первым, вторым, третьим - (2i)-м выходами первого яруса соответствующей группы второго - i-го каскадов (i=2, …, k), первый и второй входы первого - (i-j)-го модулей соответственно второго - j-го яруса каждой группы третьего - k-го каскада являются соответственно первым, вторым - 2(i-j)-м входами соответствующего второго - j-го яруса соответствующей группы третьего - k-го каскада (i=3, 4, …, k, j=2, 3, …, (i-1)), первый и второй выходы первого - (i-j)-го модулей соответственно второго - j-го яруса каждой группы третьего - k-го каскада являются соответственно первым, вторым - 2(i-j)-м выходами соответствующего второго - j-го яруса соответствующей группы третьего - k-го каскада (i=3, 4, …, k,j=2, 3, …, (i-1)), первый и второй входы элемента ИЛИ соответственно второго - j-го яруса каждой группы соответственно второго - k-го каскада являются соответственно (2(i-j)+1)-м и (2(i-j)+2)-м входами соответствующего второго - j-го яруса соответствующей группы соответствующего второго - k-го каскада (i=2, 3, …, k, j=2, 3, …, i), выход элемента ИЛИ соответственно второго - j-го яруса каждой группы соответственно второго - k-го каскада является соответственно ((i-j)+1)-м выходом соответствующего второго - j-го яруса соответствующей группы соответствующего второго - k-го каскада (i=2, 3, …, k, j=2, 3, …, i), второй, третий - (2(i-j)+1)-й выходы соответственно первого - j-го яруса каждой группы соответственно второго - i-го каскада соединены соответственно с первым, вторым - (2(i-j))-м входами соответствующего второго - (j+1)-го яруса соответствующей группы соответственно второго - i-го каскада (i=2, 3, …, k), j=1, 2, …, (i-1)), первые выходы соответственно первого - j-го яруса каждой группы соответствующего второго - i-го каскада являются соответственно первым, вторым - j-м выходами соответствующей группы соответственно второго - i-го каскада (i=2, 3, …, k, j=2, …, i), старший (2i)-й выход 1-го яруса каждой группы соответственно второго - i-го каскадов являются соответственно старшим (i+1)-м выходом соответствующей группы соответственно второго - i-го каскадов (i=2, 3, …, k), первый, второй - (z+1)-й выходы нечетных первой, третьей - (s-1)-й групп z-го каскада соединены соответственно с нечетными первым, третьим - (2z-1)-м входами соответственно первой, второй - (s/2)-й групп (z+1)-го каскада, (z=1, …, (k-1), s=2, 4, 6, …, n/2z), первый, второй - (z+1)-й выходы четных второй, четвертой - s-й групп z-го каскада соединены соответственно с четными вторым, четвертым - (2z)-м входами соответственно первой, второй - (s/2)-й группы (z+1)-го каскада (z=1, …, (k-1), s=2, 4, 6, …, n/2z), первый, второй - (k+1)-й выходы группы k-го каскада являются соответственно первым, вторым - (k+1)-м выходами устройства.
