УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КОЛИЧЕСТВА СТАРШИХ ЕДИНИЦ (НУЛЕЙ) В ДВОИЧНОМ ЧИСЛЕ

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

Известен 8-входовой приоритетный шифратор, в котором содержится семь инверторов, формируются восемь промежуточных переменных Н0-Н7 на двенадцати двух - восьмивходовых логических элементах И, а затем на трех четырехвходовых логических элементах ИЛИ формируется трехразрядный выходной код, а также приведено каскадное включение для обработки 32-входных запросов (Дж. Ф. Уэйкерли. Проектирование цифровых устройств. В 2-х томах. - М.: Постмаркет, 2002. - 1088 с., рис. 5.50 и рис. 5.51, с. 440-445).

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

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

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

Известно устройство для определения количества единиц (нулей) в двоичном числе (RU №2446442, МПК G06F 7/50, H03K 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 №2522875, МПК H03K 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 буферов с тремя состояниями с прямым входом разрешения, причем в каждой i-й ступени и в выходном блоке информационные входы буферов с тремя состояниями с инверсным входом разрешения образуют первую группу входов, информационные входы буферов с тремя состояниями с прямым входом разрешения образуют вторую группу входов, а прямые и инверсные входы разрешения буферов с тремя состояниями в которых соединены между собой и являются входами управления соответственно i-й ступени и выходного блока, выходы одноименных буферов с тремя состояниями с прямым и инверсным входами разрешения соединены между собой в каждой i-й ступени и в выходном блоке и являются соответственно их выходами, при этом с первого по k-й разряды второй группы входов выходного блока соединены с логическим нулем, с первого по k-й разряды выходов выходного блока являются соответственно с первого по k-й разрядами выходного двоичного кода.

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для определения количества старших единиц (нулей) в двоичном числе, содержащее буферы с тремя состояниями с прямым 5 и инверсным 4 входами разрешения, n разрядов входного двоичного числа D1, D2, …, Dn, (k+1) разрядов выходного двоичного кода (k=[log₂n] меньшее целое) В0, В1, …, Bk, причем буферы с тремя состояниями объединены в пирамидальную структуру, состоящую из (m-1) ступеней (m=]log₂n[ большее целое), и в выходной блок 3, содержащий k буферов с тремя состояниями с инверсным входом разрешения 4 и k буферов с тремя состояниями с прямым входом разрешения 5, при этом каждая i-я ступень 2_i(i=1, …, (m-1)) содержит (2ⁱ-1) буферов с тремя состояниями с инверсным входом разрешения 4 и (2ⁱ-1) буферов с тремя состояниями с прямым входом разрешения 5,

причем в каждой i-й ступени 2_i и в выходном блоке 3 информационные входы буферов с тремя состояниями с инверсным входом разрешения 4 образуют первую группу входов, информационные входы буферов с тремя состояниями с прямым входом разрешения 5 образуют вторую группу входов, а прямые и инверсные входы разрешения буферов с тремя состояниями в которых соединены между собой и являются входами управления А соответственно каждой i-й ступени 2_i и выходного блока 3,

выходы одноименных буферов с тремя состояниями с прямым 5 и инверсным 4 входами разрешения соединены между собой в каждой i-й ступени 2_i и в выходном блоке 3 и являются соответственно их информационными выходами, при этом с первого по k-й разряды второй группы входов выходного блока 3 соединены с логическим нулем, а с первого по k-й разряды выходов выходного блока 3 являются соответственно с первого по k-й разрядами выходного двоичного кода В0, В1, …, B(k-1),

дополнительно введены

входной блок 1, первый элемент И 8, второй элемент И 9, внешний вход знака двоичного числа Sign, n разрядов внутренней шины X1, Х2, …, Xn, а в каждую i-ю ступень 2_i введены логические элементы И 7,

причем входной блок 1 содержит n буферов с тремя состояниями с инверсным входом разрешения 4 и n буферов с тремя состояниями с прямым входом разрешения и инверсным информационным входом 6, у которых прямые и инверсные входы разрешения буферов с тремя состояниями соединены между собой и подключены к внешнему входу знака двоичного числа Sign,

при этом во входном блоке 1 информационные входы буферов с тремя состояниями с инверсным входом разрешения 4 соединены с соответствующими одноименными инверсными входами буферов с тремя состояниями с прямым входом разрешения и инверсным информационным входом 6 и соединены с соответствующими одноименными n разрядами входного двоичного числа D1, D2, …, Dn, выходы одноименных буферов с тремя состояниями с прямым входом разрешения и инверсным информационным входом 6 и буферов с тремя состояниями с инверсными входами разрешения 4 соединены между собой во входном блоке 1 и являются соответствующими n разрядами внутренней шины X1, Х2, …, Xn,

при этом младшие с 2^m-1- по второй разряды X2^m-1, …, Х2 и старшие с n-го по (2^m-1+2) разряды Xn, …, Х(2^m+2) внутренней шины соединены с соответствующими разрядами второй и первой групп входов (m-1)-й ступени 2_(m-1), в которой старшие с n-го по (2^m-1+1) разряды Xn, …, Х(2^m-1+1) внутренней шины соединены с входами логического элемента И 7, выход которого соединен с управляющим входом А (m-1)-й ступени 2_(m-1), а также соединен с k-м разрядом первой группы входов выходного блока 3 и с первым входом второго логического элемента И 9, выход которого соединен с входом управления А выходного блока 3 и является (k+1)-м разрядом выходного двоичного кода В(k+1),

второй вход второго логического элемента И 9 соединен с выходом первого логического элемента И 8, входы которого соединены с младшими с 2^m-1- по первый разряды X2^m-1, …, X1 внутренней шины,

старшие с (2^j-1) по (2^j-1+1) разряды и младшие с (2^j-1-1) по первый разряды информационных выходов каждой j-й ступени 2_j соединены с соответствующими разрядами первой и второй групп входов (j-1)-й ступени 2_(j-1) (j=(m-1), …, 2), а старшие с (2^j-1) по (2^j-1) разряды информационных выходов каждой j-й ступени 2_j также соединены входами логического элемента И 7 (j-1)-й ступени 2_(j-1), выход которого соединен с входом управления A (j-1)-й ступени и (j-1)-й разрядом первой группы входов выходного блока 3,

информационный выход первой ступени 2₁ соединен с первым разрядом первой группы входов выходного блока.

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

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

D1, D2, …, D16 (Dn) - n разрядов входного двоичного числа (при n=16),

X1, Х2, …, X16 (Xn) - n разрядов внутренней шины,

В0, В1, …, В4 (Bk+1) - (k+1) разрядов выходного двоичного кода (при к=4),

Sign - знак входного числа,

А - входы управления ступеней,

1 - входной блок,

2₁, 2₂, 2₃ - первая, вторая и третья ступени пирамидальной структуры,

3 - выходной блок,

4 - буфер с тремя состояниями с инверсным входом разрешения,

5 - буфер с тремя состояниями с прямым входом разрешения,

6 - буфер с тремя состояниями с прямым входом разрешения и инверсным информационным входом,

7 - элемент И каждой ступени,

8 - первый элемент И,

9 - второй элемент И.

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

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

Выходной блок 3 содержит четыре буфера с тремя состояниями с инверсным входом разрешения 4 и четыре буфера с тремя состояниями с прямым входом разрешения 5 (при k=4).

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

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

У выходного блока 3 с первого по k-й разряды второй группы входов соединены с логическим нулем, а с первого по k-й разряды выходов выходного блока 3 являются соответственно с первого по k-й разрядами выходного двоичного кода В0, В1, …, B(k-1).

Входной блок 1 содержит n буферов с тремя состояниями с инверсным входом разрешения 4 и n буферов с тремя состояниями с прямым входом разрешения и инверсным информационным входом 6, у которых прямые и инверсные входы разрешения буферов с тремя состояниями соединены между собой и подключены к внешнему входу знака двоичного числа Sign. При этом информационные входы буферов с тремя состояниями с инверсным входом разрешения 4 соединены с соответствующими одноименными инверсными входами буферов с тремя состояниями с прямым входом разрешения и инверсным информационным входом 6 и соединены с соответствующими одноименными n разрядами входного двоичного числа D1, D2, …, Dn. Выходы одноименных буферов с тремя состояниями с прямым входом разрешения и инверсным информационным входом 6 и буферов с тремя состояниями с инверсным входами разрешения 4 соединены между собой во входном блоке 1 и являются соответствующими n разрядами внутренней шины X1, Х2, …, Xn.

Младшие с восьмого по второй разряды Х8, …, Х2 и старшие с шестнадцатого по десятый разряды X16, …, X10 внутренней шины X (при n=16) соединены с соответствующими разрядами второй и первой групп входов третьей ступени 2₃, в которой старшие с шестнадцатого по девятый разряды X16, …, Х9 внутренней шины X соединены с входами логического элемента И 7, выход которого соединен с управляющим входом А третьей ступени 2₃. Кроме того, выход элемента И 7 третьей ступени 2₃ соединен с четвертым разрядом первой группы входов выходного блока 3 и с первым входом второго логического элемента И 9, выход которого соединен с входом управления А выходного блока 3 и является пятым разрядом выходного двоичного кода В4. Второй вход второго логического элемента И 9 соединен с выходом первого логического элемента И 8, входы которого соединены с младшими с восьмого по первый разряды Х8, …, X1 внутренней шины X.

Во второй ступени 2₂ первая группа входов соединена с соответствующими старшими с седьмого по пятый информационными выходами третьей ступени 2₃, а вторая группа входов соединена с соответствующими младшими с третьего по первый выходами третьей ступени 2₃. Кроме того, старшие с седьмого по четвертый информационные выходы третьей ступени 2₃ соединены с входами элемента И 7 второй ступени 2₂, выход которого соединен с входом управления А второй ступени 2₂ и третьим разрядом первой группы входов выходного блока 3.

Младший первый и старший третий разряды информационных выходов второй ступени 2₂ соединены с соответствующими разрядами второй и первой групп входов первой ступени 2₁. Кроме того, старшие третий и второй информационные выходы второй ступени 2₂ соединены с входами элемента И 7 первой ступени 2₁, выход которого соединен с входом управления А первой ступени 2₁ и вторым разрядом первой группы входов выходного блока 3.

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

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

На входы устройства поступает n разрядов входного двоичного числа D1, …, D16 (Dn) и знак числа Sign, представленные в дополнительном или обратном коде. Для положительных чисел значение знака Sign=0, а для отрицательных Sign=1. Старший разряд D16 (Dn) является старшим разрядом входного двоичного числа.

Во входном блоке 1 разряды входного числа D1, …, D16 (Dn) не изменяются для отрицательных чисел при значении знака Sign=1, или все разряды инвертируются для положительных чисел при значении знака Sign=0. Таким образом в старших разрядах на внутренней шине X1, Х2, …, X16 (Xn) будут сформированы единичные значения, соответствующие количеству нулей во входном двоичном числе. Далее определяется количество единиц в старших разрядах.

Для определения количества единиц проводится анализ по группам разрядов с внутренней шины X, начиная со старших разрядов, при этом в группы включается количество разрядов кратное степени 2 (при n=16 группы содержат по восемь, четыре, два или один разряды). Распределение разрядов по группам приведено в таблице 1. Последовательность проверки групп представлена в виде графа и приведена на фиг. 2, а также приведены формируемые разряды выходного двоичного кода В0, В1, …, В4. В вершинах графа на фиг. 2 указаны группы проверяемых разрядов внутренней шины X. На дугах, связывающих вершины графа, отмечены логические условия, при которых происходит выборка следующей группы разрядов.

На первом шаге анализируется наличие единичных значений во всех восьми старших разрядах X16, X15, …, Х9 (элемент И 7 в (m-1)-й ступени 2_(m-1)) и в зависимости от этого формируется значение разряда В3 выходного кода. Если на выходе элемента И 7 установлено единичное значение, то анализируются восемь младших разрядов Х8, Х7, …, X1 (первый элемент И 8) и при единичном значении формируется выходной двоичный код 10000 на выходах устройства В4, В3, …, В0, соответствующий тому, что все 16 разрядов внутренней шины равны единице, а следовательно, во входном числе в зависимости от знака все разряды равны единице (Sign=1) или нулю (Sign=0). При этом устанавливаются нулевые значения на выходах разрядов В3, В2, В1, В0 выходного блока 3.

Если в старших восьми разрядах, хотя бы в одном разряде нулевое значение, то анализируются четыре старших разряда Х16, Х15, Х14, Х13, а если все старшие разряды единичные, то анализируются четыре разряда Х8, Х7, Х6, Х5. При этом формируется значение разряда В2 выходного кода.

Далее в зависимости от анализа соответствующих восьми и четырех разрядов, проводится анализ соответствующих двух соседних последовательных старших нечетного и соответствующего четного из четырех разрядов (3 и 4 разряды, или 7 и 8 разряды, или 11 и 12 разряды, или 15 и 16 разряды) и формируется значение разряда В1 выходного кода.

Из графа следует, что нечетные разряды Х15, Х13, …, X1 анализируются только в группах, содержащих не менее двух разрядов, поэтому младшие разряды из соответствующих групп не передаются для анализа на следующие ступени и каждая i-я ступень 2_i (i=1, …, (m-1)) содержит (2ⁱ-1) буферов с тремя состояниями с инверсным входом разрешения 4 и (2ⁱ-1) буферов с тремя состояниями с прямым входом разрешения 5. Значение младшего разряда В0 выходного кода формируется в зависимости от значения соответствующего четного разряда X16, X14, …, Х2.

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

Двоичное число, представленное в дополнительном или обратном коде, подается на входы D1, …, D16 и знак числа на вход Sign. Во входном блоке 1 двоичное число в зависимости от значения знака Sign преобразуется в разряды внутренней шины X так, что количество единиц в старших разрядах соответствует количеству старших нулей для положительных чисел или старших единиц для отрицательных чисел.

В зависимости от значения на выходе элемента И 7 в 3-ей ступени 2₃ на ее выход передаются семь младших разряды Х2, …, Х8 (при единичном значении на выходе элемента И 7) или семь старших разрядов Х9, …, X16 (при нулевом значении на выходе элемента И 7). Единичное значение на выходе элемента И 7 указывает на то, что количество единиц равно или больше восьми, а нулевое значение - меньше восьми. Значение с выхода элемента И 7 3-ей ступени 2₃ поступает также на четвертый вход первой группы выходного блока 3 и формирует разряд В3.

Во второй ступени 2₂ на элементе И 7 формируется значение, соответствующее четырем старшим разрядам 7-4 с выходов третьей ступени 2₃: единичное значение указывает на то, что количество единиц в данных четырех разрядах равно четырем, а нулевое значение - менее четырех. В зависимости от значения на выходе элемента И 7 во 2-й ступени 2₂ на ее выход с выходов 3-ей ступени 2₃ передаются три младших выхода 1-3 (при единичном значении на выходе элемента И 7) или три старших выхода 4-7 (при нулевом значении на выходе элемента И 7). Значение с выхода элемента И 7 2-й ступени 2₂ поступает также на третий вход первой группы выходного блока 3 и формирует разряд В2.

В первой ступени 2₁ на элементе И 7 формируется значение, соответствующее двум старшим выходам 3 и 2 второй ступени 2₂: единичное значение указывает на то, что количество единиц в данных двух разрядах равно двум, а нулевое значение - менее двух. В зависимости от значения на выходе элемента И 7 в 1-й ступени 2₁ на ее выход с выходов 2-й ступени 2₂ передаются младший выход 1 (при единичном значении на выходе элемента И 7) или старший выход 3 (при нулевом значении на выходе элемента И 7). Значение с выхода элемента И 7 1-й ступени 2₁ поступает также на второй вход первой группы выходного блока 3 и формирует разряд В1.

На выходе первой ступени 2₁ формируется сигнал, поступающий на первый вход первой группы выходного блока 3, на выходе которого формируется разряд В0. Значение разряда В0 указывает на четное количество старших единиц (нулевое значение) или нечетное количество старших единиц (единичное значение) в исходном двоичном числе D.

Если в исходном двоичном числе D количество старших единиц равно шестнадцати, то на выходе элементы И 7 третьей ступени 2₃ и на выходе первого элемента И 8 будут сформированы единичные значения, которые поступают на входы второго элемента И 9, на выходе которого также будет сформировано единичное значение, которое поступает на пятый разряд В4 выходного блока. Одновременно на входах первой группы выходного блока 3 также будут сформированы единичные значения. Для обнуления значений всех разрядов выходного кода В, единичный сигнал с выхода элемента И 9 поступает на вход управления А выходного блока 3, который устанавливает на выходах блока 3 нулевые значения, так как при этом на его выходы передается значение со второй группы входов блока 3, на которых установлен логический ноль.

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

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