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

 

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

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

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

PЕСПУБЛИК (19) (11) (s1)s Н 03 М 7/22

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4869781/24 (22) 27,09,90 (46) 30,09.92. Бюл. ¹ 36 (72) Л,Б.Авгуль и В.П.Супрун (56) Авторское свидетельство СССР

¹864277,,кл,,Н 03 М 7/22, 1980.

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

¹ 1589400, кл, Н 03 М 7/22, 1988.

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

Известно устройство для вычисления двоичных кодовых комбинаций, содержащее сумматор по модулю два, элемент НЕ, и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (срабатывающих на кодовых комбинациях с соседними весами) и 4п элементов И (1).

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

Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления двоичных кодовых комбинаций произвольного веса, содержащее и пороговых элементов с последовательными порогами от 1 по n, n — 1 элементов

ЗАПРЕТ и элемент И (2).

Недостатком известного устройства также является высокая конструктивная сложность, Цель изобретения — упрощение устройства, (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ BECA ДВОИЧНЫХ КОДОВЫХ КОМБИНАЦИЙ (57) Изобретение относится к вычислительной технике и микроэлектронике. Его использование для построения матричных арифметических устройств позволяет упростить устройство, содержащее пороговые элементы и один элемент НЕ. Упрощение достигается благодаря введению сумматора по модулю два, элементов НЕ и элементов И. 1 ил.

Устройство для вычисления веса двоичных кодовых комбинаций содержит р+1 (р = (n/2); n — разрядность входного двоичного слова; (а) — наибольшее целое число, не и ревосходящее а) элементов НЕ, р пороговых элементов, i-й (i = 1, 2...„р) из которых имеет порог, равный 2i, сумматор по модулю два и 2п — 2р элементов И. Причем j-й (j

= 1, 2, .„, n) вход i-го порогового элемента соединен с j-м входом устройства, выход

k-го (k = 1, 2, ..., 2п — 2р) элемента И является

k-м выходом устройства, )-й вход которого соединен с j-м входом сумматора по модулю два, выход которого соединен с первым входом 2I-го (I = 1, 2, ..., и — р) элемента И и входом первого элемента НЕ, выход которого соединен с первым входом (2I — 1)-го элемента И. Выход i-ro порогового элемента соединен с входом (i+1)-го элемента НЕ, выход которого соединен со вторыми входами (2i — 1)-го и 2i-го элементов И. Выход г-го (г = 1, 2, ..., р — 1) порогового элемента соединен с третьими входами (2г+1)-ro u (2r+2)-ro элементов И. Выход р-го порогового элемента соединен со вторыми входами и-го и (n+1)-ro элементов И, если и — нечет1765898 ное, или с (п+1)-м выходом устройства, если гдето=О, 1, ..., и. Очевидно, что Мп =1. К оме

n — четное, того, в (2) полагается, что М " 1 = М "+ = 0

На чертеже в качестве примера приве- Справедливость (2) следует из того факдена функциональная схема устройства при та, что произвольная симметрическая б леп =5. кая уле5 ва функция и переменных F = F(xl, x2, ..., xn)

Устройство содержит сумматор по мо- принимает значение логической единицы дулю два 1, р = (n/2) = 2 пороговых элемен- на тех и только тех наборах переменных х1, тов 21 и 22, Р+1 = 3 элемента НЕ 31 32 и 33 х2, ..., хп, котоРые соДеРжат Ровно а еДиниЦ

2n — 2р = 6 элементов И 41...46, и = 5 входов (i = 1, 2, „., К О < k < п). Числа а1, а2, „„а

51...55 и п+1 = 6 выходов 61„,66, При этом i-й 10 называются рабочими и образуют множест(i = 1, 2...„р) пороговый элемент 2i имеет во A(F), которое однозначно определяет порог, равный 2ь т,е. порог элемента 21 ра- симметрическую булеву функцию F. ОчевидвЕн 2„параг ЭлЕмЕнта 22 равЕн 4, но, что A(Fnm) = (m} Нетрудно установить, Отметим также, что число двухвходовых что элементов И равно 2п — 4(n/2)+2, а число 15 трехвходовых элементов И составляет А(Мп ) = (r,r+1, ..., n}, 2(n/2) — 2. А(Мп" ) =(О, 1, „г+1}, Устройство для вычисления веса двоич- A(fn) = (1, 3, ..., 2n — 2(n/2) — 1}, ных кодовых комбинаций работает следую- А(Г) = (О. 2, ..., 2(п/2)}. щим образом. 20

На /-й (j = 1, 2, ..., n) вход устройства подается двоичная переменная х; и-разрядНОГО ДВОИЧНОГО СЛОВа X = (X1, X2, ..., Xn). На с-м (t = О, 1, ..., и) выходе устройства реали- A(F. ) = А(Мп ")ПА(М.")nA(f„) = зуется некоторая булева функция Fnt = 25 =(m, п1+1, ..., п}ЩО, 1, „„m+1}A

=Fn (Х1, X2, .„, Xn), КОтОРаЯ ПРИНИМаЕт ЗНаЧЕ- f1(0, 2, „„2(n/2)} = (m}. ние логической единицы тогда и только тогда, когда двоичное слово X содержит ровно Пусть m — нечетное, тогда г = п1 — 1 и

t единиц, т,е. A(fn ") = A(fn). Из (2) имеем

1, если х1+ х2+ „, + х, = t; 30

Fn (1)

Π— в противном случае, гдето=0,1, ..., n, Очевидно, что функции Fnt представляют собой фундаментальные симметрические 35 В частности если и = 5 то ф.,б.ф. F

1 5 булевы функции(ф,с.б,ф) и переменных(см., - F5, ..., F5 вычисляются, согласно (2), по например, Поспелов Д.А, Логические мето- следующим формулам: ды анализа и синтеза схем.— М.: Энергия, 1974.— с, 125 — 128), Так, для рассматриваемого примера 40 F5 = М5О М52 f5 = М5 -f5, (n = 5) на входы 51...55 подаются двоичные переменные х1...х5 соответственно; на выходах 61...66 реализуются ф,с.б.ф, F5 ...F5 соответственно, on ределенные согласно Р М M 6f М 4 (1). 45

Устройство для вычисления веса двоич- Здесь учитывается что M =- 1 М

5 = и 5 ных кодовых комбинаций строится согласно =0, т.е, M5 = 1. следующим соотношениям; Достоинством устройства является простота схемы, Действительно, для своего (2) 50 построения устройство требует (n/2) пороговых элементОв, один сумматор по модулю где m = О, 1, ..., n, r = 2(m/2), fn = х19х29... два и 2п — 2(n/2) элементов ЗАПРЕТ (эле8хп И fn = тп, fn = f и и =. п. менты И и элементы НЕ в совокупности

Здесь функция Мп порогового элемен- образуют элементы 3AflPET). Для реалита с и входами и с порогом t определяется 55 зации прототипа необходимо большее как число элементов, а именно, и пороговых

О, если x1+ x2+ ... + xn < t; элементов; и — 1 элементов ЗАПРЕТ и один элемент НЕ.

1 — в противном случае, Устройство имеет меньшую конструктивную сложность не только по числу логиПусть m — четное, тогда r = m и A(fnm ") =

А(т"и), Из (2) следует, что

A(Fnm) = A(Mnm )AA(Mnm )AA(fn) =

=(m — 1, m, ..., n}n(0, 1, „„m} П п(1, 3, ..., 2п — 2(n/2) — 1} = (m}.

Гm М rм r+21mr!

Mn =

1765898 ческих элементов, но и по числу их входов.

Так, его сложность по числу входов логических элементов равна

S = (и — 2) (и/2) + 5n — 2, в то время, как сложность прототипа по числу входов логических элементов вычисляется как

Snp. = и + 2n — 1.

Составитель В. Супрун

Редактор Т. Орловская Техред М.Моргентал Корректор И, Шмакова

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

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

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

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

Устройство для вычисления веса двоичных кодовых комбинаций, содержащее первый элемент НЕ и первый — р-й пороговые элементы (р = (и/2), п — разрядность входной кодовой комбинации, (а) — наибольшее целое число, не превосходящее а), i-й из которых имеет порог 2i, входы всех пороговых элементов соответственно объединены и являются входами устройства, о т л и ч аю щ е е с я тем, что, с целью упрощения устройства, в него введены второй — (р+1)-й элементы НЕ, первый — (2п — 2р)-й элементы

И и сумматор по модулю два, входы которого подключены к соответствующим входам устройства, выход сумматора па модулю два

5 соединен с первым входом (21)-го элемента

И (I = 1,n — р) и входом первого элемента НЕ, выход которого подключен к первому входу (21 — 1)-го элемента И, выход г-го порогового элемента (r = р — 1) соединен с вторыми вхо10 дами (2г+1)-го и (2г+2)-ro элементов И и входом (г+1)-го элемента НЕ, выходы (i+1)-го элемента НЕ подключены к соответствующим входам (2i — 1)-го и 2i-го элементов И, выходы первого — 2(n — 2р)-го элементов И

15 являются соответственно первым — (2п — 2р)м выходами устройства, выход р-го порогового элемента соединен с входом (р+1)-го элемента НЕ и при и нечетном — c вторыми входами (2п — 2р — 1)-го и (2п — 2р)-го элементов

20 И, а при и четйом является (2n — 2р+1)-м выходом устройства.