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

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

Иллюстрации

Показать все

Реферат

 

Союз Советских

Социалистических

Ресиубп н (11| 1 к лвтоескомм свидетельств (61) Дополнительное к авт. свнд-ву (22) 3asse esm 23. 09. 81 (21) 3339282/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 23.01.83. Бюллетень М 3 (5!)М. Кл.

G 06 F 5/02

Гасударстааааый камктат (53) УДК 681.3 (088. 8) ао девам вэабретаний и атхрытий

Дата опубликования описания 2),01 8 (72) Авторы изобретения

Г.П. Иитин и С.А. С тремин (7l ) Заявитель (S4) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КОЛИЧЕСТВА ЕДИНИЦ В ДВОИЧНОМ

ЧИСЛЕ

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

Известно устройство для параллель" ного счета количества единиц (нулей) в двоичном числе, которое содержит последовательно соединенные группы сумматоров, число которых 1о92п (празрядность входного кода ) и, кроме того, в каждой группе содержится по и (2k сумматоров с последовательным переносом (l < k < log n) Г1 3.

Недостатком устройства является низкое быстродействие.

Наиболее близким по технической сущности к предлагаемому является устройство для преобразования кодов, содержащее в каждом разряде элементы И и ИЛИ, причем входы каждого разряда подключены к прямому и инверсному входам данного разряда устройства соответственно, выходы i-го разряда устройства (1= 1,2,..., 2 и и, где n - число разрядов в кодо-вом слове ) подключены к входам (1+1)го устройства, выходы и-го разряда устройства подключены к одним из выходов устройства и к входам элементов ИЛИ, выходы которых подключены к другим выходам;устройства $2 ).

Недостатком известного. устройства является, невысокое быстродействие, определяемое количеством элементов, через которое входной сигнал проходит на выход (для и = 3 количество элементов, вносящих задержку " g), Целью изобретения является повыше" ние быстродействия.

Поставленная цель достигается тем, что устройство для определения коли" чества единиц в двоичном числе, со» держащее элементы И и ИЛИ, содержит щ .также элемент неравнозначности и дешифратор, причем каждый рарряд устройства содержит восемь элементов И, . ,выходы которых соответственно под;ключены к входам элемента ИЛИ данного

9914

3 разряда устройства, выход которого подключен к выходной шине данного разряда устройства, первые входы эле- . ментов И каждого разряда устройства подключены к выходам дешифратора со- S ответственно, первый выход элемента . неравноэначности подключен к вторым входам первого, второго, третьего и четвертого элементов И первого разряда устройства, вторые входы пятого, 1О шестого, седьмого и восьмого элементов И которого подключены к второму выходу элемента неравнозначности, входы которого подключены к входам входных элементов И, ИЛИ и к первой и второй входным информационным шинам устройства соответственно, прямой выход входного элемента И подключен к вторым входам первого элемента И второго разряда устройства и к 20 вторым входам первого, второго и третьего элементов И третьего разряда устройства, инверсный выход входного элемента И подключен к вторым входам второго, третьего и четвертого эле" ментов И второго разряда устройства, прямой выход входного элемента ИЛИ подключен к вторым входам пятого шестого и седьмого элементов И второго разряда устройства.и к второму ЗО входу четвертого элемента И третьего разряда устройства, второй инверсный выход входного элемента ИЛИ подключен к второму входу восьмого элемента И второго разряда устройства, вторые З входы пятого, шестого, седьмого и восьмого элементов И третьего разряда подключены к шине нулевого потенциала устройства, третья, четвертая и пятая входные шины которого подклю- щ чены к входам дешифратора соответственно, На чертеже приведена функциональная схема устройства для определвния количества единиц в двоичном числе для и =5.

Устройство содержит входную шину 1 устройства, элемент 2 неравнозначнос ти, входной элемент И 3, входной элемент ИЛИ ч,дешифратор 5,элементы И6, элементы ЙЛИ 7, выходную шину 8 устройства.

Устройство работает следующим образом

На дешифратор 5 поступают три млад-э ших разряда исходного числа ° Дешифратор преобразует двоичный код в позиционный и единичный потенциал, пояя09 4 ляющийся на одном иэ его выходов, поступает.на.первые входы одноименных элементов И 6 каждого разряда. На первом выходе элемента 2 неравнозначности единичный потенциал появляется при неравенстве четвертого и пятого разрядов исходного кода, на втором выходе - при равенстве. Первые выходы входных элементов И и ИЛИ соответствуют прямому значению выполняемой элементом функции, вторые - инверсному.

Допустим, на входную шину 1 уст" ройства поступило число ll, в двоич= иом коде 01011. Три младших разряда поступают на дешифратор 5, единичный потенциал формируется на четвертом выходе (соответствующем числу 3 ) и поступает на первые входы четвертых элементов И 6 каждого разряда. Так как старшие разряды исходного числа не равны, то единичный потенциал формируется на первом выходе элемента 2 неравнозначности и через четвертый элемент И 6 и элемент ИЛИ 7 пер» вого разряда проходит на выходную ши" ну 8 первой разрядной группы. На второй вход элемента И 6 второго разряда поступает единичный потенциал с второго выхода элемента И 3 и, следовательно, на выходе элемента ЙЛИ 7 второго разряда также присутствует единичный потенциал. На втором входе элемента И 6 третьего разряда пгисутствует нулевой уровень с первого выхода элемента И 3 и, следовательно, на выходе этого разряда также нулевой уровень.

На выходной шине 3 устройства формируется двоичный код 011, соответствующий числу единиц в исходном коде, т.е. числу 3 °

Таким образом, данное устройство при определении количества единиц в . двоичном числе при q 5 имеет преимущество по отношению к известному уст" ройству, поскольку при подсчете коли" чества единиц в пятиразрядном коде информация в известном устройстве проходит через 9 логических элементов И, ИЛИ и составляет

Т„= 9

При использовании микросхем серии

133 Т „ = 198 нс. В данном устройстве информация проходит через 3 логичес-. ких элемента, следовательно

T g 3t = 66 нс

5 : 9911 0

Особенно большой технико-эконом " ческий эффект может быть при использовании стандартных мультиплексоров, например 133 КП 5. В этом случае максимальное время определения коли- 5 чества единиц в пятиразрядном двоичном числе составляет 36 нс.

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

m = ) Popgun( где)Д(обозначает наименьшее целое число, большее чем число элементов И и-2- 15 в разряде 2

Формула и зобретения

Устройство для определения количества единиц s двоичном числе, содержащее элементы И и ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены элемент неравнозначности и

2$ . дешифратор, причем каждый разряд устройства содержит восемь элементов И, выходы которых соответственно подключены к входам элемента ИЛИ данного разряда устройства, выход кото-, 30 рого подключен к выходной шине данно«

ro. разряда устройства, первые входы элементов И каждого разряда устройства подключены к выходам дешифратора соответственно, первый выход элемен« з та неравнозначности. подключен к вторым входам первого, второго, треть" его и четвертого элементов И первого разряда устройства, вторые входы пя9 6 того, шестого, седьмогЬ и восьмого элементов И которого подключены к второму выходу элемента неравнознач-ности, входы которого подключены к входам входных элементов И, ИЛИ и к первой и второй информационным. входным шинам устройства соответственно, прямой. выход входного элемента И подключен к вторым входам первого элемента И второго разряда устройства и к вторым входам первого, второго и третьего элементов И .третьего разряда устройства, инверсный выход входного элемента И подключен к вторым входам второго, третьего и четвертого элементов И второго разряда устройства, прямой выход входного. элемента ИЛИ подключен к вторым входам пятого, шестого и седьмого элементов И второго разряда устройства и к второму входу четвертого элемента И третьего разряда устройства, второй инверсный выход входного элемента ИЛИ подключен к второму входу восьмого элемента И второ-. го разряда устройства, вторые входы пятого, шестого, седьмого и восьмого элементов И третьего разряда подклоче" ны к шине нулевого потенциала устрой;ства, третья, четвертая и пятая входные шины которого подключены к входам ешифратора соответственно. деш

Источники информации, принятые во внимание при экспертизе

Авторское свидетельство СССР

11 781811, кл. G 06 F 5/02, 1977.

2. Авторское свидетельство СССР

11 739522, кл. G 06 F 5/02, 1976 (прототип).

991409

1

Составитель В. Кайданов

Реаактоо Т. Ку»гаьшева Техоев Л Пекарь Корректор Е. Рошко

»»я««»« в « »е«ааю»««»»»»»» ю»« »»»«««««««««««««««» ««»««», «

Заказ 134/66 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035 Москва Ж-35 Рамшская наб. а. 4/5

»««» «»»»«»«»»»«««»«»»J»» въ4«»ае««»» «» е«««««»««ф», филиал ППП "Патент, r. Ужгород, ул. Проектная, 4