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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 Н 03 M 7/04

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) з

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

50 51

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4838323/24 (22) 11.06.90 (46) 23.12.92. Бюл. ¹ 47 (71) Московский инженерна-физический институт (72) А.B.Ñîãîÿí, Н.Ю.Стунжас и B.Ñ.Ôàäîðченко (56) Патент США ¹ 3711692, кл. 364/786, опублик. 1972.

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

¹ 450160, кл. Н. 03 М 7/04, 1972.

1.1

„.,Я „„1783617 А1 (54) УСТРОЙСТВО ДЛЯ ПОДСЧЕТА КОЛИЧЕСТВА ЕДИНИЦ В и-РАЗРЯДНОМ ДВОИЧНОМ КОДЕ (57) Изобретение относится к вычислительной технике. Его использование в системах

ОбрдбОтки Цифровой информаЦии позволя" ет повысить быстродействие устройства, которое содержит несколько ярусов из трехвходовых сумматоров 2. Цель достигается благодаря введению блоков суммирования 1 со специфической структурой, что минимизйрует число последовательных ний. 1 з.п. ф-лы, 2 ил.

1783617

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

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

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

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

2 яруса, где n — разрядность входного кода.

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

12 сумматоров ((,) — ближайшее большее целое), второй — ((logz nj — 1) ярусы из первого— и (— „-+, ) — го трехвходовых сумматоров (к = „

2"

2,3, .Ä(logz и) — 1), в каждом ярусе, кроме последнего, выход суммы каждого трехвходового сумматора, кроме последнего, соединен с первым входом последующего трехвходового сумматора этого же яруса, выход переноса (2l-1)-ro и (2()-го трехвходовых сумматоров (l = 1,2,... (— „-+ ) -) каждо2 го яруса, кроме nepaoro и последнего, 55 соединен с вторым и третьим входами i-го трехвходового сумматора последующего яруса, выход суммы последних трехвходовых сумматоров каждого яруса и выход переноса трехвходового сумматора последнего яруса являются соответственно первым — (log 2 п )- м разрядами выходов устройства, введены первый †. (†)- и блои

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

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

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

1783617

30

40

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

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

Устройство для подсчета количества единиц содержит и-разрядную входную шину А, (— ) блоков суммирования 1 1.1и

6 и

1. (— ), образующих первый ярус, и (— ) + (— ) — 1 трехвходовых сумматоров и и

12 4

2 2.1- (Iоцг и ) 1, Первый-шестой входы каждого блока суммирования 1 1.1-1. и (— ) являются соответствующими инфор6 мационными входами устройства, третий выход 1-го блока суммирования 1 1.1, кроме последнего блока 1. (— ), соединен с вхои дом переноса (1+1)-го блока суммирования 1

1.(1+1), третий выход (— )- ro блока суммии

6 рования 1 1. (— ) является нулевым разряи

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

12 вующие входы трехвходовых сумматоров 2 третьего яруса 3.1 — 3. (— ); в третьем— п ((1оцгп)-1)-м ярусах выход суммы каждого

i-ro трехвходового сумматора 2 k I, кроме последнего k. (— ), где k — номер яруса, и

2 соединен с входом переноса (1+1)-го сумматора 2 того же яруса k (1+1), выходы переноса (2l-1)-го k.(21-1) и (21)-ro k.(21) трехвходовых сумматоров 2 каждого k-того яруса кроме (1оцгп)-ro соединены с вторым и третьим входами I-ro трехвходового сумматора 2 (k+1)-гО яруса (k+1) i. выход суммы последних трехвходовых сумматоров 2 второго— (1оцгп)-го ярусов и выход переноса сумматора 2 (1оцгп)-го яруса (Iоцгп) 1 являются соответственно первым — ((logan) — 1)-м разрядами выходов устройства.

Блок суммирования (фиг.2) содержит первый-третий трехвходовые сумматоры 13, первый и второй полусумматоры 4 — 5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 6, элемент НЕ

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

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

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

10, выход которого является третьим выходом блока.

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

45 Блоки суммирования первого яруса 1.11. (— ) формируют (— ) группы по три

fl и

6 6 сигнала. Сигнал младшего разряда суммы, имеющий вес 2, последовательно распро50 страняется через (— )-1 блоков суммирои

6 вания первого яруса 1.2 —,1,(— ) . Сигнал

6 младшего разряда суммы, формируемый последним блоком суммирования первого яруса 1. (— ) имеет вес 2 и является и

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

Сигналы среднего разряда суммы блоков суммирования первого яруса 1.1 — 1. и 1 (— J имеют вес 2 и поступают на входы

Выигрыш по быстродействию ставляет дт со(и ) — 1+(i

Таким образом, ТMBKc zcM (+ 1 ) +zcM log 22

6 сумматоров второго яруса2..1 — 2, (— ) . п дт

12 5

ГАС СГЬЪ Л

Сигналы переноса с сумматоров второго Так р =32 и ак, при n = выигрыш по быстродейяруса 2.1 — 2 (— ) и сигналы старших раэ- ствию д T составляет 1,6 раза, при n = 64

12 рядов сумм блоков суммирования первого д т = 2 . При этом аппа а ные ат р турные затраты

2 10 для прототипа составляют и — 1 трехвходо ðóña 1.1 — 1, (и ), имеющие вес 2, посту- вый сумматор, для предлагаемого Устройсти пают на входы сумматоров третьего яруса ва (6) блоков сУммиРованиЯ и и

3.1 — 3. (— ) . далее на входы сумматоро (" )+(п) (4 ) трехвходовых сумматоров (k+1) ro Яруса (+ 1) 1 — (k+ l) () noc » ilo аппаратурным затратам блок суммиро2 вания (фиг.2) превышает трехвходовый сум-. пают сигналы переноса только из k-то яруса, матор приблизительно в 4,5 раэ. имеющие вес 2 . Сигнал суммы, формируе- Таким образом, аппаратурные затраты мый последним сумматором k ro яруса k, при реализации предлагаемого устр

20 устроиства к-1 13

2 (— „), имеет вес 2 и является k-м разря- могут быть оценены как — „и — 1, то

12 — есть дом двоичного числа количества единиц во пРоигРыш по аппаратУРным эатРатам совходном и-разрядном коде. Ставляет менее 8%.

Использование в первом ярусе блоков Е 0 р м у л а и 3 0 б р е т е н и Я суммирования позволяет повысить быст25 1, Устройство для подсчета количества родействие без увеличения аппаратур- единиц в и Разрядном двоичном коде, соных затрат. Действительно,, держащее первый ярус из первого— максимальная задержка Тмакс от аботки сигналов прототипом равна Тмакс àKc ОтРабОтКИ (— ) трЕХВХОдОВЫХ СуММатарОВ ((.) — бЛИмакс — зс

ZcM (— 1)+Zсм 1ОЯ2n Г Е ,, и, „, жаишее большее целое), второй -((log2n)-1)(2 1 j см 92 . ДЕ -й яруСЫ из ПЕрвОГО с и т см — задеРжки сигналов сУммы и (— + ) атРехвходовых сУмматоРов (k .= и переноса в одном сумматоре (2), В то же время для рассматриваемого устройства 35 2,3,...,(!ОщпЗ, в каждом ярусе, кРоме послед1(3) и 1(2) (з) него, выход переноса соединен С первым — — 2 +zc +zо., + 6 см ВХОДОМ ПОСЛЕДУЮЩЕГО тРЕХВХОДОВОГО CYM+z« "(log г n — 1), матора этого же яруса, выходы суммы (2l — 1)ro и (2l)-ro трехвходовых сумматоров (l = где т, (1 — задержка формирования О 1,2,..., (+) ) каждого яруса, кроме пер2 младшего разряда суммы при подаче сигнала на входы блока суммироВания;

1(з) (г) третьим входами l-ro трехвходового сумма, т« — задержки форми- тора последующего яруса, выходы переноса рования младшего и среднего Разрядов сум- 45 последних трехвходовых сумматоров кажмы в блоке суммирования при подаче дого яруса и выход суммы трехвходового сигнала на вход переноса блока суммирова- сумматора последнего яруса являются соответственно первым — (log2n)-м разрядами

Для блока суммирования (фиг.2) выходов устройства, о т л и ч а ю щ e e c я

5р тем, что, с целью повышения быстродейстг см 1(г) = Г см 1(") = Z см с вия устройства, в него введены первый— п (— ) - и блоки суммирования, первый-шесХсм (=2 Тсм +2 Тсм (3) с и. тои информационные входы каждого из ко-

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

Ф

ФЛ

Составитель В.Федорченко

Техред М.Моргентал Корректор С,Юско

Редактор

Заказ 4521 Тираж Подписное

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

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 ния, первый выход (.— ) - го блока суммии б рования является нулевым разрядом выходов устройства, второй выход первого блока суммирования подключен к первому входу 5 первого трехвходового сумматора первого яруса, вторые выходы (2О-го и (21+1 -го блоков суммирования соединены с вторым и третьим входами i-ro трехвходового сумматора первого яруса, третий выход каждого 10 блока суммирования и выход суммы каждого трехвходового сумматора первого яруса подключены к вторым и третьим входам соответствующих трехвходовцх сумматоров второго яруса. 15

2. Устройство по п.1, о т л и ч. а ю щ е е с я тем, что блок суммирования содержит первый-третий трехвходовые сумматоры, первый и второй полусумматоры, элемент

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