Устройство для определения количества единиц в упорядоченном двоичном числе

Устройство для определения количества единиц в упорядоченном двоичном числе

Иллюстрации

Показать все

Реферат

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

Известен шифратор (RU №2023345 С1, МПК Н03М 7/00, G06F 7/38, заявлен 03.07.1991, опубликован 15.11.1994), содержащий первый и второй дешифраторы границы нулей, блок шифрации прямого кода, узел сравнения, блок элементов НЕ, блок элементов И, элемент И-НЕ.

Недостатком данного устройства является отсутствие средств для наращивания разрядности входного числа.

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

Известно устройство для упорядочения единиц (SU №1751746 А1, МПК G06F 7/38, 7/06, заявлено 26.11.1990, опубликовано 30.07.1992, Бюл. №28), содержащее по (n-1)-й группе элементов И и ИЛИ (где n - четное число, разрядность операнда, n=2K), две группы К-разрядных входов упорядоченных единиц и n-разрядный выход упорядоченных единиц.

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

Известно устройство для подсчета количества единиц в двоичном числе (SU №1751749 А1, МПК G06F 7/52, заявлено 10.12.1990, опубликовано 30.07.1992, Бюл. №28), содержащее 2К-1 разрядов входного двоичного числа, блок подсчета количества единиц, формирующий по входному коду упорядоченный код единиц, коммутатор, выходы которого являются выходами остатка устройства, первая и вторая группы информационных входов коммутатора соединены с выходами разрядов с первого по (К-1)-й и с (К+1)-го по (2К-1)-й соответственно блока подсчета количества единиц, выход К-го разряда блока подсчета количества единиц соединен с управляющим входом коммутатора и является выходом частного устройства.

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

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

Известно устройство для определения количества единиц (нулей) в двоичном числе (заявка RU №2011114163/08, МПК G06F 7/50, Н03K 21/00, заявлено 11.04.2011), содержащее блок управляемой инверсии, состоящий из 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 разрядов входного двоичного числа, (k+1) разрядов выходного двоичного кода (k=[log₂n] меньшее целое), причем буферы с тремя состояниями объединены в пирамидальную структуру, состоящую из (m-1) ступеней (m=]log₂n[большее целое), и в выходной блок, содержащий k буферов с тремя состояниями с инверсным входом разрешения и k буферов с тремя состояниями с прямым входом разрешения, при этом каждая i-я ступень (i=1, (m-1)) содержит 2ⁱ-1 буферов с тремя состояниями с инверсным входом разрешения и 2ⁱ-1 буферов с тремя состояниями с прямым входом разрешения, причем в каждой i-й ступени и в выходном блоке информационные входы буферов с тремя состояниями с инверсным входом разрешения образуют первую группу входов, информационные входы буферов с тремя состояниями с прямым входом разрешения образуют вторую группу входов, а прямые и инверсные входы разрешения буферов с тремя состояниями, в которых соединены между собой, и являются входами управления соответственно i-й ступени и выходного блока, выходы одноименных буферов с тремя состояниями с прямым и инверсным входами разрешения соединены между собой в каждой i-й ступени и в выходном блоке и являются соответственно их выходами, младшие с первого по (2^m-1-1) и старшие с (2^m-1+1) по (n-1) разряды входного двоичного числа соединены с соответствующими разрядами первой и второй групп входов (m-1)-й ступени, а (2^m-1)-й разряд входного двоичного числа соединен с входом управления (m-1)-й ступени и k-м разрядом первой группы входов выходного блока, младшие с первого по (2^j-1-1) и старшие с (2^j+1+1) по (2^j-1) разряды выходов каждой j-й ступени соединены с соответствующими разрядами первой и второй групп входов (j-1)-й ступени (j=(m-1),…,), а (2^j-1)-й разряд выхода каждой j-й ступени соединен с входом управления (j-1)-й ступени и (j-1)-м разрядом первой группы входов выходного блока, выход первой ступени соединен с первым разрядом первой группы входов выходного блока, с первого по k-й разряды второй группы входов выходного блока соединены с логическим нулем, n-й разряд входного двоичного числа соединен с входом управления выходного блока и является (k+1)-м разрядом выходного двоичного кода, с первого по k-й разряды выходов выходного блока являются соответственно с первого по k-й разрядами выходного двоичного кода.

На фиг.1 представлена схема предлагаемого устройства для определения количества единиц в упорядоченном двоичном числе при n=16. На фиг.2 приведен граф проверки разрядов и формирование выходного двоичного кода В4,…, В0.

На фиг.1 приняты следующие обозначения: пирамидальная структура устройства содержит первую 1, вторую 2 и третью 3 ступени, выходной блок 4, n разрядов D1,…, D16 (при n=16) входного двоичного числа 5, (k+1) разрядов В0,…, В4 выходного двоичного кода 6, буферы с тремя состояниями с инверсным входом разрешения 7, буферы с тремя состояниями с прямым входом разрешения 8, входы управления ступеней обозначены А.

Устройство для определения количества единиц в упорядоченном двоичном числе содержит буферы с тремя состояниями с инверсным 7 и прямым 8 входами разрешения, n разрядов D1,…, D16 (при n=16) входного двоичного числа, (k+1) разрядов В0,…, В4 (при k=4) выходного двоичного кода (k=[log₂n] меньшее целое).

Буферы с тремя состояниями объединены в пирамидальную структуру, состоящую из (m-1) ступеней (m=]log₂n[большее целое) - первой 1, второй 2 и третьей 3 ступеней при (m-1)=3. Выходной блок 4 содержит четыре буфера с тремя состояниями с инверсным входом разрешения 7 и четыре буфера с тремя состояниями с прямым входом разрешения 8 (при k=4). Первая ступень 1 содержит один буфер 7 с тремя состояниями с инверсным входом разрешения и один буфер 8 с тремя состояниями с прямым входом разрешения. Вторая ступень 2 содержит три буфера 7 с тремя состояниями с инверсным входом разрешения и три буфера 8 с тремя состояниями с прямым входом разрешения. Третья ступень 3 содержит семь буферов 7 с тремя состояниями с инверсным входом разрешения и семь буферов 8 с тремя состояниями с прямым входом разрешения. Каждая следующая i-я ступень (i=4,…, (m-1)) содержит 2ⁱ-1 буферов 7 с тремя состояниями с инверсным входом разрешения и 2ⁱ-1 буферов 8 с тремя состояниями с прямым входом разрешения.

В первой 1, второй 2, третьей 3 и каждой следующей i-й ступени и в выходном блоке 4 информационные входы буферов 7 с тремя состояниями с инверсным входом разрешения образуют первую группу входов, информационные входы буферов 8 с тремя состояниями с прямым входом разрешения образуют вторую группу входов, а прямые и инверсные входы разрешения буферов с тремя состояниями в которых соединены между собой и являются входами управления А соответственно первой 1, второй 2, третьей 3 и каждой i-й ступени и выходного блока 4.

Выходы одноименных буферов с тремя состояниями с прямым 8 и инверсным 7 входами разрешения соединены между собой в каждой i-й ступени и в выходном блоке 4 и являются соответственно их выходами.

Младшие с первого по седьмой D1,…, D7 и старшие с девятого по пятнадцатый D9,…, D15 разряды входного двоичного числа 5 (при n=16) соединены с соответствующими разрядами первой и второй групп входов самой старшей третьей ступени 3, а восьмой D8 разряд входного двоичного числа 5 соединен с входом управления А третьей ступени 3 и четвертым разрядом первой группы входов выходного блока 4.

Младший первый и старший третий разряды выходов второй ступени 2 соединены с соответствующими разрядами первой и второй групп входов первой ступени 1, а второй разряд выхода второй ступени 2 соединен с входом управления А первой ступени 1 и вторым разрядом первой группы входов выходного блока 4. Выход первой ступени 1 соединен с первым разрядом первой группы входов выходного блока 4.

Младшие с первого по третий и старшие с пятого по седьмой разряды выходов третьей ступени 3 соединены с соответствующими разрядами первой и второй групп входов второй ступени 2, а четвертый разряд выхода третьей ступени 3 соединен с входом управления А второй ступени 2 и третьим разрядом первой группы входов выходного блока 4.

Для следующих старших ступеней младшие с первого по (2^j-1-1) и старшие с (2^j-1+1) по (2^j-1) разряды выходов каждой j-й ступени соединены с соответствующими разрядами первой и второй групп входов (j-1)-M ступени (j=(m-1),…, 3)), а (2^j-1)-й разряд выхода каждой j-й ступени соединен с входом управления (j-1)-и ступени и (j-1)-M разрядом первой группы входов выходного блока 4.

С первого по k-й разряды второй группы входов выходного блока 4 соединены с логическим нулем. Шестнадцатый D16 (n-й) разряд входного двоичного числа 5 соединен с входом управления А выходного блока 4 и является пятым ((k+1)-м) разрядом выходного двоичного кода 6, с первого по четвертый (k-й) разряды выходов выходного блока 4 являются соответственно с первого по четвертый (k-й) разрядами выходного двоичного кода 6.

В вершинах графа на фиг.2 указаны проверяемые разряды входного упорядоченного числа 5. На дугах, связывающих вершины графа, отмечены логические условия, при которых происходит выборка следующего разряда.

Предлагаемое устройство для определения количества единиц в упорядоченном двоичном числе работает следующим образом. На его первый - шестнадцатый разряды входного двоичного числа 5 подаются входные сигналы D1,…, D16 упорядоченного двоичного числа с единицами расположенными подряд, начиная с младших разрядов D1. В зависимости от значения восьмого разряда D8 на выход третьей ступени 3 передаются семь младших разряды D1,…, D7 (при D8=0) или семь старших разрядов D9,…, D15 (при D8=1). Значение разряда D8=0 указывает на то, что количество единиц меньше восьми, а значение D8=1 равно или больше восьми. Значение разряда D8 поступает также на четвертый вход первой группы выходного блока 4 и формирует разряд В3.

Значение четвертого выхода третьей ступени 3 указывает на то, что количество единиц меньше четырех (при нулевом значении выбранных разрядов D12 или D4) и равно или больше четырех (при единичном значении D12 или D4), в выделенных третьей ступенью 3 соответствующих семи разрядах. Этот четвертый выход третей ступени 3 поступает на третий вход первой группы выходного блока 4 и формирует разряд В2, а также поступает на вход управления А второй ступени 2. В зависимости от значения этого сигнала на выходы второй ступени 2 передаются три младших или три старших разряда.

Значение второго выхода второй ступени 2 указывает на то, что количество единиц равно одной (при нулевом значении выбранного разряда D14 или D10 или D6 или D2) и равно или больше двух (при единичном значении D14 или D10 или D6 или D2), в выделенных второй ступенью 2 соответствующих трех разрядах. Этот второй выход поступает на второй вход первой группы выходного блока 4 и формирует разряд В1, а также поступает на вход управления А первой ступени 1. В зависимости от значения этого сигнала на выход первой ступени 1 передается младший первый или старший третий разряд (разряды D15 или D13 или D11 или D9 или D7 или D5 или D3 или D1 входного двоичного числа 5). На выходе первой ступени 1 формируется сигнал В0, поступающий на первый вход первой группы выходного блока 4, значение этого сигнала указывает на четное количество единиц (нулевое единичное значение) или нечетное количество единиц (единичное значение) в исходном упорядоченном двоичном числе 5.

Если в исходном двоичном числе 5 количество единиц равно шестнадцати, то разряд D16=1. При этом на всех выходах всех ступеней устройства будут также сформированы единичные значения. Для обнуления значений всех разрядов выходного кода В сигнал D16=1 поступает на вход управления А выходного блока 4, который устанавливает на выходах блока 4 нулевые значения, так как при этом на его выходы передается значение со второй группы входов блока 4, на которых установлен логический ноль. Шестнадцатый разряд D16 входного упорядоченного двоичного числа 5 является старшим разрядом В4 выходного двоичного кода 6.

Таким образом, на выходах 6 выходного блока 4 формируется двоичный код В4, В3, В2, В1, В0 числа единиц во входном упорядоченном двоичном числе 5.

Если количество n разрядов D входного упорядоченного двоичного числа 5 не кратно степени 2, то старшие разряды дополняются нулевыми значениями. В таблице 1 приведены значения количества ступеней (m-1) и количества выходных разрядов (k+1) в устройстве в зависимости от количества n входных разрядов.

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

Таблица 1
Устройство для определения количества единиц в упорядоченном двоичном числе
Количество разрядов, n	4	8	12	16	24	32
Меньшее целое, k=[log2n]	2	3	3	4	4	5
Большее целое, m=]log2n[	2	3	4	4	5	5
Количество ступеней, m-1	1	2	3	3	4	4
Количество разрядов выхода, k+1	3	4	4	5	5	6

Устройство для определения количества единиц в упорядоченном двоичном числе, содержащее буферы с тремя состояниями с прямым и инверсным входами разрешения, n разрядов входного двоичного числа, (k+1) разрядов выходного двоичного кода (k=[log₂n] меньшее целое), причем буферы с тремя состояниями объединены в пирамидальную структуру, состоящую из (m-1) ступеней (m=]log₂n[большее целое), и в выходной блок, содержащий k буферов с тремя состояниями с инверсным входом разрешения и k буферов с тремя состояниями с прямым входом разрешения, при этом каждая i-я ступень (i=l,…, (m-1)) содержит 2ⁱ-1 буферов с тремя состояниями с инверсным входом разрешения и 2ⁱ-1 буферов с тремя состояниями с прямым входом разрешения, причем в каждой i-й ступени и в выходном блоке информационные входы буферов с тремя состояниями с инверсным входом разрешения образуют первую группу входов, информационные входы буферов с тремя состояниями с прямым входом разрешения образуют вторую группу входов, а прямые и инверсные входы разрешения буферов с тремя состояниями в которых соединены между собой и являются входами управления соответственно i-й ступени и выходного блока, выходы одноименных буферов с тремя состояниями с прямым и инверсным входами разрешения соединены между собой в каждой i-й ступени и в выходном блоке и являются соответственно их выходами, младшие с первого по (2^m-1-1) и старшие с (2^m-1+1) по (n-1) разряды входного двоичного числа соединены с соответствующими разрядами первой и второй групп входов (m-1)-й ступени, а (2^m-1)-й разряд входного двоичного числа соединен с входом управления (m-1)-й ступени и k-м разрядом первой группы входов выходного блока, младшие с первого по (2^j-1-1) и старшие с (2^j-1+1) по (2^j-1) разряды выходов каждой j-й ступени соединены с соответствующими разрядами первой и второй групп входов (j-1)-й ступени (j=(m-l),…, 2)), a (2^j-1)-й разряд выхода каждой j-й ступени соединен с входом управления (j-1)-й ступени и (j-1)-м разрядом первой группы входов выходного блока, выход первой ступени соединен с первым разрядом первой группы входов выходного блока, с первого по k-й разряды второй группы входов выходного блока соединены с логическим нулем, n-й разряд входного двоичного числа соединен с входом управления выходного блока и является (k+1)-м разрядом выходного двоичного кода, с первого по k-й разряды выходов выходного блока являются соответственно с первого по k-й разрядами выходного двоичного кода.