Устройство для подсчета числа двоичных единиц (нулей) Советский патент 1992 года по МПК G06F7/50 

s| 00 GJ СП

СЛ

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

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

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

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

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

.Цель изобретения - повышение быстродействия и выравнивание времени получения результатов по разным модулям.

Поставленная цель достигается тем, что в устройство для подсчета числа двоичных единиц (нулей), содержащее одноразрядный сумматор последнего уровня т, входную n-разрядную шину, разбитую на триады, шину управления и выходную шину, введены группы трехразрядных блоков предварительной обработки результатов по модулям два и три (далее блоки) и дешифратор управления, причем каждый блок содержит неполный дешифратор, элементы ЗИЛИ , 2ИЛИ- НЕ, 4ИЛИ- НЕ, 2И .2-2И-2ИЛИ, три инвариантных информационных входа, два входа управления блоком и два выхода, при этом информационные входы блока яв- ляются входами неполного дешифратора, входы элемента ЗИЛИ соединены с четвертым, шестым и седьмым выходами неполного дешифратора, входы элемента 2ИЛИ-НЕ Соединены с первым и восьмым выходами неполного дешифратора, входы элемента 4ИЛИ-НЕ соединены с первым, шестым и седьмым выходами неполного дешифратора, входы элемента 2И соединены с выходом элемента ЗИЛИ и вторым входом управления блоком, входы элемента 2-2И2ИЛИ соответственно соединены со вторым входом управления блоком, выходом элемента 2ИЛИ-НЕ, первым входом управления блоком, выходом элемента 4ИЛИ-НЕ, выходы элементов 2И и 2-2И-2ИЛИ образуют выходную шину блока, причем, входная n-разрядная шина, разбитая на триады, является одновременно входом устройства и инвариантными входами блоков группы первого уровня, выходы нечетных блоков и первый выход четных блоков этой группы, считая справа налево, соединены с аналогичными входами блоков группы второго уровня, выходы которых и вторые выходы четных блоков группы первого уровня соединены с блоками группы третьего уровня, аналогично объединяются выходы пар блоков между собой до группы уровня lm-2. в котором число блоков Кт-2 2, выходы нечетного блока и первый выход четного блока этой группы соединены со входами блока предпоследнего уровня lm-i. первый выход i

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

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

Устройство (см. фиг. 1) содержит трехразрядные блоки 1 предварительной обработки результата по модулям два и три, объединенные в группы блоков уровней И, l2im-1, дешифратор 2 управления, одноразрядный сумматор 3 последнего уровня im , входную п- разрядную шину 4, входную шину 5 управления и выходную двухразрядную шину 6 устройства. Дешифратор 2 управления предназначен для формирования сигналов управления мультиплексированием результатов по модулям два и три. Одноразрядный сумматор 3 предназначен для формирования конечного результата.

В устройстве соединены п-разрядная шина 4 с инвариантными информационными входами (далее по тексту - входы) блоков 1 группы первого уровня, количество которых равно К п/3, число блоков каждых двух последующих групп относительно нечетной группы равно Ki Кн-t - Км/2, где Км - количеств.0 блоков в группе нечетного уровня, Ki и Км - количество блоков в двух последующих группах, все выходы нечетных блоков и первые выходы четных блоков первой группы, считая справа налево, соединены со входами блоков второго уровня, выходы которых и вторые выходы четных блоков группы первого уровня соединены со входами блоков 1 третьего уровня, и т.д. до группы уровня т-2, число блоков 1 в которой равно Кт-2 2, выходы нечетного блока и первый выход четного блока этой группы соединены со входами блока 1 предпоследнего уровня im-i, первый выход которого соединен с входом переноса одноразрядного сумматора 3, вторые выходы блока 1 уровня im-1 и четного блока 1 группы уровня im-2 соединены со входами операндов сумматора 3, в ыходы которого являются выходами устройства, шина 5 управления является входом дешифратора 2 управления, выходы которого соединены с первыми и вторыми входами управления блоками 1 всех уровней,

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

Каждый блок 1 содержит преобразователь двоичного кода в позиционный (неполный дешифратор 7), элемент ЗИЛИ 8, элемент 2ИЛИ-НЕ 9, элемент 4ИЛИ-НЕ 10, элемент 2И 11, элемент 2-2И-2ИЛИ 12.

Неполный дешифратор 7 блока (см. фиг. 2) предназначен для идентификации входных кодов и формирования их позиционных кодов. Элементы ЗИЛИ 8 и 2ИЛИ-НЕ 9 предназначены для формирования числа двоичных единиц (нулей) по модулю три. Элемент 10 предназначен для формирования числа двоичных единиц (нулей) по модулю два в соответсвии с таблицей состояния.

Элементы 2И 11 и 2-2И-2ИЛИ 12 предназначены для мультиплексирования результатов по модулям два и три.

В каждом блоке 1 соединены: информационные входы блока с входами неполного дешифратора 7, входы элемента ЗИЛИ 8 соединены с четвертым, шестым и седьмым выходами дешифратора 7, входы элементов 2ИЛИ-НЕ 9 соединены с первым и восьмым выходами дешифратора 7, входы элемента 4ИЛИ-НЕ 10 соединены с первым, четвертым, шестым и седьмым выходами дешифратора 7, входы элемента 2И 11 соединены с выходом элемента ЗИЛИ 8 и вторым входом Х2 управления блоком, входы элемента 2-2И-2ИЛИ 12 соединены соответственно со вторым входом Х2 управления, выходом элемента 2ИЛИ-НЕ 9, первым входом Х1 управления блоком и выходом элемента

4ИЛИ-НЕ 10, выходы элементов 11 и 12 являются выходами блока 1.

Устройство работает следующим образом. Параллельный n-разрядный код двоич- 5 ного числа поступает на входы устройства, причем, для подсчета числа единиц - в прямом, а для подсчета нулей - в обратном коде. Поступая на входы устройства, двоичное число разбивается на триады и при по0 мощи блоков 1 предварительной обработки результата параллельно преобразуется в код числа двоичных единиц по модулям два либо три, причем принятая троичная система счисления соответствует процессу уплот5 нения единиц в двоичном числе.

При условии подачи на входную шину 5 управления низкого потенциала на первом выходе дешифратора 2 управления появится разрешающий высокий потенциал для

0 мультиплексирования результатов в каждом блоке 1 по модулю два, в противном случае высокий потенциал появится на втором выходе дешифратора 2 управления, что будет соответствовать разрешению мульти5 плексирования результатов по модулю три, а так как имеющаяся схема не содержит элементы памяти, то с каждым изменением входной информации наблюдается процесс отекания результата сверху вниз с окон0 чательным формированием его на одноразрядном сумматоре 3.

Работа блока 1 предварительной обработки результата (см. фиг. 2). При необходимости подсчета числа двоичных единиц

5 (нулей) по модулю два на первом входе Х1 управления появляется высокий потенциал, на втором Х2 - низкий, для подсчета по модулю три состояние входов управления изменится на противоположное, что будет

0 соответствовать нужной выборке результата мультиплексором, который образуют элементы 2И 11 и 2-2И-2ИЛИ 12. Формирование числа двоичных единиц (нулей) происходит при помощи

5 дешифрации входного числа дешифратором 7 с последующей шифрацией числа единиц (нулей) на элементах 8 и 9 по модулю три и на элементе 10 - по модулю два.

0 Таким образом за счет распаралле- ливания процесса подсчета числа двоичных единиц (нулей) по разным модулям предложенная схема имеет более высокое быстродействие, а за счет

5 исключения элементов управления из тракта вычисления результатов имеем равные критические цепочки при подсчете числа двоичных единиц (нулей) по модулям два и три, что обеспечивает

равные времена получения результатов. Формула изобретения Устройство для подсчета числа двоичных единиц (нулей), содержащее m линеек, первая из которыхтсодержит Ki n/З блоков предварительной обработки результатов по модулям два и три, где п - разрядность по- ступаемой на входы информации, m-1-я линейка содержит один блок предварительной обработки результатов по модулям два и три, а в промежуточных линейках количество блоков предварительной обработки результатов по модулям два и три составляет К2М toi-2 К21-3/2, где I 2, т-2, выходной одноразрядный сумматор линей- ки т, выходы которого соединены с выходом устройства, п информационных входов и вход управления, причем п информационных входов устройства соединены с инвариантными входами блоков предварительной обработки результатов по модулям два и три первой линейки устройства, отличающееся тем, что, с целью повышения быстро- действия и выравнивания времени получения результатов по разным модулям, в него введен дешифратор управления, а блоки предварительной обработки результатов по модулям два и три каждой предыдущей линейки произвольно соединены со свободными инвариантными входами любой из последующих линеек, оставшиеся свободные входы блоков предварительной обработки результатов обработки результатов по модулям два и три соединены с цепью логического нуля, первый выход линейки т- 1, считая справа налево, соединен с входом переноса выходного одноразрядного сумматора линейки т, первый информационный вход которого соединен со вторым выходом линейки т-1. второй информаци- онный вход выходного одноразрядного сумматора соединен с оставшимся свободным

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

Фиг. 2