Устройство для подсчета количества единиц в @ -разрядном двоичном коде Советский патент 1992 года по МПК H03M7/04 

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

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

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

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

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

суммы через

JJ-1

сумматор первого

яруса, где п - разрядность входного кода.

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

ярус из первого - - - го трехвходовых

сумматоров (. - ближайшее большее целое), второй - (рода ) ярусы из первого I - го трехвходовых сумматоров (k

2,3,..,,1092 ), в каждом ярусе, кроме последнего, выход суммы каждого трехвходо- вого сумматора, кроме последнего, соединен с первым входом последующего трехвходового сумматора этого же яруса, выход переноса (21-1)-го и ( трехвходовых сумматоров (I 1,2,...

-т+ч 0 каждо- 2 к-м

го яруса, кроме первого и последнего, соединен с вторым и третьим входами 1-го трехвходового сумматора последующего яруса, выход суммы последних трехвходовых сумматоров каждого яруса и выход переноса трехвходового сумматора

последнего яруса являются соответственно первым - log 2 n - м разрядами выходов

устройства, введены первый - тг - и блоки суммирования, первый-шестой информационные входы каждого из которых являются соответствующими информационными входами устройства, третий выход каждого блока суммирования, кроме последнего, соединен с входом переноса последующего блока суммирования, третий

выход -Q - го блока суммирования является нулевым разрядом выходов устройства, второй выход первого блока суммирования подключен к первому входу первого трехвходового сумматора первого яруса, вторые выходы (2lj-ro и (21+1)-го блоков суммирования соединен с вторым и

третьим входами 1-го трехвходового сумматора первого яруса, первый выход каждого блока суммирования и выход переноса каждого трехвходового сумматора первого яруса подключены к вторым и третьим входам

соответствующих трехвходовых сумматоров второго яруса.

Кроме того, эта цель достигается тем, что блок суммирования содержит первый-, третий трехвходовые сумматоры, первый и

второй полусумматоры, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент НЕ и первый-тре- тий мультиплексоры, управляющие входы которых объединены и являются входом переноса блока, входы первого и второго трехвходовых сумматоров являются соответственно первым-шестым информационными входами блока, выходы суммы первого и второго трехвходовых сумматоров соединены с входами первого полусум:

матора, выход переноса которого и выходы переноса первого и второго трехвходовых сумматоров подключены к входам третьего и трехвходового сумматора, выход переноса которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первым информационным входом первого мультиплексора, выход которого является первым выходом блока, выход суммы третьего трехвходового сумматора подключен к первому

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

элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с вторым информационным входомчпервого мультиплексора; выход суммы первого полусумматора соединен с входом элемента НЕ, первым информационным входом третьего мультиплексора и

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

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

Устройство для подсчета количества единиц содержит n-разрядную входную

шину А, |И блоков суммирования 1 1.11.

J

образующих первый ярус, и

L + 4 - 1 трехвходовых сумматоров

2 2.1- 1од2 п 3 1 , Первый-шестой входы каждого блока суммирования 1 1.1-1.

«

являются соответствующими информационными входами устройства, третий выход 1-го блока суммирования 1 1.1, кроме

последнего блока 1.

Г-1 L6J

соединен с входом переноса (1+1)-го блока суммирования 1 1 .(1+1), третий выход тИ - го блока суммирования 1 1. является нулевым разрядом выходов устройства, второй выход первого блока суммирования 1 1.1 подключен к первому входу первого трехвходового сумматора 2 второго яруса 2.1, вторые выходы ( 1 .(21) и ( 1 .(21+1) блоков суммирования 1 соединены с вторым и третьим входами 1-го трехвходового сумматора 2 второго яруса 2.1, первые выходы блоков

суммирования 1 1.1-1 и выходы переноса трехвходовых сумматоров 2 второго яруса 2.1-2. ттг поступают на соответствующие входы трехвходовых сумматоров 2 третьего яруса 3.1-3. } ; в третьем (1од2п}-1)-м ярусах выход суммы каждого 1-го трехвходового сумматора 2 Ы, кроме

последнего к. -г , где к - номер яруса, 2 к

соединен с входом переноса (i+1)-ro сумматора 2 того же яруса k (i+1), выходы переноса (2i-1)-ro k.(2i-1) и (2i)-ro k.(2i) трехвходовых сумматоров 2 каждого k-того яруса кроме Iog2n ro соединены с вторым и третьим входами 1-го трехвходового сумматора 2 (k+1)-ro яруса (k+1) i. выход суммы последних

трехвходовых сумматоров 2 второго - Iog2n -ro ярусов и выход переноса сумматора 2 iog2n -ro яруса Iog2n 1 являются соот- ветственно первым - (1од2п -1)-м разрядами выходов устройства. 5Блок суммирования (фи.2) содержит

первый-третийтрехвходовые сумматоры 1- 3, первый и второй полусумматоры 4-5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 6, элемент НЕ 7 и первый-третий мультиплексоры 8-10,

0 управляющие входы которых объединены и являются входом переноса блока, входы сумматоров 1 и 2 являются информационными входами блока, выходы суммы довых сумматоров 1 и 2 соединены с

5 входами первого полусумматора 4, выход переноса которого и выходы переноса сумматоров 1 и 2 подключены к входам третьего трехвходового сумматора 3, выход переноса которого соединен с первым входом эле0 мента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 и первым информационным входом мультиплексора 8, выход которого является первым выходом блока, выход суммы трехвходового сумматора 3 подключен к первому входу второго

5 полусумматора 5 и первому информационному входу второго мультиплексора 9, выход которого является вторым выходом блока, выход переноса второго полусумматора 5 подключен к второму входу элемента

0 ИСКЛЮЧАЮЩЕЕ ИЛИ 6, выход которого соединен с вторым информационным входом мультиплексора 8; выход суммы первого полусумматора 4 соединен с входом элемента НЕ 7, первым информационным

5 входом третьего мультиплексора 10 и вторым входом полусумматора 5, выход суммы которого подключен к второму информационному входу второго мультиплексора 9, выход элемента НЕ 7 соединен с вторым

0 информационным входом мультиплексора 10, выход которого является третьим выходом блока.

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

5 Блоки суммирования первого яруса 1.11. Ј формируют группы потри

сигнала. Сигнал младшего разряда суммы, имеющий вес 2°, последовательно распространяется через блоков суммирования первого яруса 1.2- Ц-g Сигнал

младшего разряда суммы, формируемый по- 5 следним блоком суммирования первого яруса 1. Ј имеет вес 2° и является

значением младшего разряда двоичного кода количества единиц в n-разрядном коде.

Сигналы среднего разряда суммы блоков суммирования первого яруса 1.1-1.

- имеют вес 21 и поступают на входы

сумматоров второго яруса2.1-2, т Сигналы переноса с сумматоров второго яруса 2.1-2 -т и сигналы старших разрядов сумм блоков суммирования первого яруса 1.1-1. -О-, имеющие вес 22, поступают на входы сумматоров третьего яруса

Выигрыш по быстродействию д составляет

Л + 1од 2п + 2+ 1од2пГ

Так, при п 32 выигрыш по быстродействию 5 т составляет 1,6 раза, при п 64 дг 2 . При этом аппаратурные затраты для прототипа составляют п-1 трехаходо- вый сумматор, для предлагаемого устройства

16J

блоков суммирования и

Изобретение относится к вычислительной технике. Его использование в системах обработки цифровой информации позволяет повысить быстродействие устройства, которое содержит несколько ярусов из трехвходовых сумматоров 2. Цель достигается благодаря введению блоков суммирования 1 со специфической структурой, что минимизирует число последовательных суммирований. 1 з.п. ф-лы, 2 ил. - ttog, VI 00 CJ ON XI SLttyflJ-S StloyjiJ Sf

3.1-3. з 3 .. Далее на входы сумматоров г + г т -, трехвходовых сумматоров.

( яруса (k+1).1-{k+1). посту- 15

пают сигналы переноса только из k-то яруса, имеющие вес 2k. Сигнал суммы, формируемый последним сумматором k-ro яруса k.

-тг имеет вес и является k-м разря2k

дом двоичного числа количества единиц во входном n-разрядном коде.

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

7см с ( )+7См , где

7см с и Тем п - задержки сигналов суммы и переноса в одном сумматоре (2). В то же время для рассматриваемого устройства 35

(3)(Ј-2)+г„ 3) + + 7СНП(|092П -1 ),

По аппаратурным затратам блок суммирования (фиг.2) превышает трехвходовый сумматор приблизительно в 4,5 раз.

Таким образом, аппаратурные затраты при реализации предлагаемого устройства

13могут быть оценены как

12

п - 1 , то есть

проигрыш по аппаратурным затратам составляет менее 8%.

Формула изобретения . 1. Устройство для подсчета количества единиц в n-разрядном двоичном коде, содержащее первый ярус из первого - 3 трехвходовых сумматоров ff.J - ближайшее большее целое), второй - flog2n -1)- -й ярусы из первого

- тт -готрехвходовых сумматоров (k .

2,3 1092П), в каждом ярусе, кроме последнего, выход переноса соединен с первым входом последующего трехвходового сумматора этого же яруса, выходы суммы (2М)- го и (21)-го трехвходовых сумматоров (f

(з)

где 7См w - задержка формирования младшего разряда суммы при подаче сигнала на входы блока суммирования;

7см 13, 7см - задержки формирования младшего и среднего разрядов сум- мы в блоке суммирования при подаче сигнала на вход переноса блока суммирования.

Для блока суммирования (фиг.2)

1(2)

1(3),

с .

.7см Т см Гсм(3)2ГсмС+27смП;

Таким образом,

Т„акс 7СмС(Ј + 1 )+7СмП од22п

По аппаратурным затратам блок суммирования (фиг.2) превышает трехвходовый сумматор приблизительно в 4,5 раз.

Таким образом, аппаратурные затраты при реализации предлагаемого устройства

13могут быть оценены как

12

п - 1 , то есть

к n

5

0

5

0

5

проигрыш по аппаратурным затратам составляет менее 8%.

Формула изобретения . 1. Устройство для подсчета количества единиц в n-разрядном двоичном коде, содержащее первый ярус из первого - 3 трехвходовых сумматоров ff.J - ближайшее большее целое), второй - flog2n -1)- -й ярусы из первого

- тт -готрехвходовых сумматоров (k .

2,3 1092П), в каждом ярусе, кроме последнего, выход переноса соединен с первым входом последующего трехвходового сумматора этого же яруса, выходы суммы (2М)- го и (21)-го трехвходовых сумматоров (f

1,2 гум ) каждого яруса, кроме пер2 КТ

вого и последнего, соединены с вторым tf третьим входами 1-го трехвходового сумматора последующего яруса, выходы переноса последних трехвходовых сумматоров каждого яруса и выход суммы трехвходового сумматора последнего яруса являются соответственно первым - {1од2п -м разрядами выходов устройства, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены первый и блоки суммирования, первый-шестой информационные входы каждого из которых являются соответствующими информационными входами устройства, первый выход каждого блока суммирования, кроме последнего, соединен с входом переноса последующего блока суммирования, первый выход . го блока суммирования является нулевым разрядом выходов устройства, второй выход первого блоке суммирования подключен к первому входу первого трехвходового сумматора первого яруса, вторые выходы (2l)-ro и (21+1)-го блоков суммирования соединены с вторым и третьим входами 1-го трехвходового сумматора первого яруса, третий выход каждого блока суммирования и выход суммы каждого трехвходового сумматора первого яруса подключены к вторым и третьим входам соответствующих трехвходовых сумматоров второго яруса.

матора, выход переноса которого и выходы переноса первого и второго трехвходовых сумматоров подключены к входам третьего трехвходового сумматора, выход переноса которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первым ин- формационным входом первого мультиплексора, выход которого является первым выходом блока, выход суммы третьего трехвходового сумматора подключен к первому входу второго полусумматора и первому информационному входу второго мультиплексора, выход которого является вторым выходом блока, выход переноса второго полусумматора подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с вторым информационным входом первого мультиплексора, выход суммы первого полусумматора соединен с входом элемента НЕ, первым информационным входом третьего мультиплексора и вторым входом второго полусумматора, выход переноса которого подключен к второму информационному входу второго мультиплексора, выход элемента Н Е соединен с вторым информационным входом третьего мультиплексора, выход которого является третьим выходом блока.

-ДГ