Устройство для вычисления веса двоичных кодовых комбинаций Советский патент 1992 года по МПК H03M7/22 

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

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

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

Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления двоичных кодовых комбинаций произвольного веса, содержащее п пороговых элементов с последовательными порогами от 1 по п, п-1 элементов ЗАПРЕТ и элемент И 2.

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

Цель изобретения - упрощение устройства.

Устройство для вычисления веса двоичных кодовых комбинаций содержит р+1 (р n - разрядность входного двоичного слова; а - наибольшее целое число, не превосходящее а) элементов НЕ, р пороговых

элементов, i-й (i 1, 2 р) из которых

имеет порог, равный 2i, сумматор по модулю два и 2п-2р элементов И. Причем j-й (j 1,2, .,., п) вход i-ro порогового элемента соединен с j-м входом устройства, выход

k-ro(k 1, 22п-2р) элемента И является

к-м выходом устройства, j-й вход которого соединен с j-м входом сумматора по модулю два, выход которого соединен с первым входом 21-го (1 1,2, ..., n-р) элемента И и входом первого элемента НЕ, выход которого соединен с первым входом (21-1)-го элемента И. Выход i-ro порогового элемента соединен с входом (i+1)-ro элемента НЕ, выход которого соединен со вторыми входами (2i-1)-ro и 2i-ro элементов И. Выход

r-го (г 1, 2 р-1) порогового элемента

соединен с третьими входами (2г+1)-го и (2г+2)-го элементов И. Выход р-го порогового элемента соединен со вторыми входами n-го и (п+1)-го элементов И, если п - нечетXION СЛ 00 Ю 00

ное, или с (п+1)-м выходом устройства, если п - четное.

На чертеже в качестве примера приведена функциональная схема устройства при п 5.

Устройство содержит сумматор по модулю два 1, р п/2 2 пороговых элементов 2i и 2а, р+1 3 элемента НЕ 3i, За и Зз, 2п-2р 6 элементов И 41„.4б, п 5 входов 5i...5s и п-М 6 выходов 6i.,.6e. При этом 1-й (1 1,2, .,,, р) пороговый элемент 2 имеет порог, равный 2i, т.е. порог элемента 2i равен 2Л порог элемента 1г равен 4.

Отметим также, что число двухвходовых элементов И равно , а число трехвходовых элементов И составляет .

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

На j-й (j 1, 2 п) вход устройства

подается двоичная переменная xj п-разрядного двоичного слова X (xi, xaхп). На

t-м (t 0, 1п) выходе устройства реализуется некоторая булева функция Fnr Рпг(х1, ха, ..., хп), которая принимает значение логической единицы тогда и только тогда, когда двоичное слово X содержит ровно t единиц, т.е.

(1, если xi + ха + ... + хп т;

0) О-в противном случае,

где t 0, 1п.

Очевидно, что функции Fnt представляют собой фундаментальные симметрические булевы функции (ф.с.б.ф) п переменных (см., например, Поспелов Д.А. Логические методы анализа и синтеза схем.- М.: Энергия, 1974-с. 125-128).

Так, для рассматриваемого примера (п 5) на входы 5i...5s подаются двоичные переменные Х1...Х5 соответственно; на выходах 6-|...6б реализуются ф.с.б.ф. Fs°...F55 соответственно, определенные согласно (1).

Устройство для вычисления веса двоичных кодовых комбинаций строится согласно следующим соотношениям:

с m .л г м r+2 f m-r гп - Мп Mn in ,

(2) 50

где m 0, 1n, r , fn xi©xa©...

0хп и fn° fn, fn1 fn.

Здесь функция Mnl порогового элемента с п входами и с порогом t определяется как

Г 0, если xi + ха + ... + xn t; Мп

11 - в противном случае,

где t 0,1п. Очевидно, что Мп° 1. Кроме

того, в (2) полагается, что Мпп+1 Мп 0. Справедливость (2) следует из того факта, что произвольная симметрическая булева функция п переменных F F(xi, xa,..., хп) принимает значение логической единицы на тех и только тех наборах переменных xi, xa,..., хп, которые содержат ровно а единиц

0 1,2к, 0 k п). Числа ai, aaak

называются рабочими и образуют множество A(F), которое однозначно определяет симметрическую булеву функцию F. Очевидно, что A(Fnm) {m}. Нетрудно установить, что

A(Mnr)r{r,r+1п},

А(МПГ42) {0, 1г+1},

A(fn) {1,32n-2 n/2 -1),

A(Q {0, .

Пусть m - четное, тогда г m и A() A(fn). Из (2) следует, что

A(Fnm) А(Мпт)ЛА(Мпт+2)ЛА(Ј)

{т, т+1, ..., п}0{0, 1т+1}Л

П{0, {т}.

Пусть m - нечетное, тогда г т-1 и A() A(fn). Из (2) имеем

A(Fnm) AfMn VtMn jnAffn)

{т-1, тп}п{0, 1т}П

П{1,32п-2 п/2 -1} {т}.

В частности, если п 5, то ф.с.б.ф. Fs0,

Fs1 Fs5 вычисляются, согласно (2), по

следующим формулам:

Р5° F51

M5°-M52f5 M52f5, M50M52f5 M52f5,

F52 M52M54f5,

F5J M52-iU54-f5,

F54 M54M56-F5 M54F5,

F55 M54M56-f5 M54f5.

Здесь учитывается, что Мб0 1 и Ms6 s sO, т.е. Ms6s1.

Достоинством устройства является простота схемы, Действительно, для своего построения устройство требует п/2 пороговых элементов, один сумматор по модулю два и элементов ЗАПРЕТ (элементы И и элементы НЕ в совокупности образуют элементы ЗАПРЕТ). Для реализации прототипа необходимо большее число элементов, а именно, п пороговых элементов, п-1 элементов ЗАПРЕТ и один элемент НЕ.

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

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

пр

гг + 2п- 1.

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

элементы НЕ, первый - (2п-2р)-й элементы И и сумматор по модулю два, входы которого подключены к соответствующим входам устройства, выход сумматора по модулю два

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

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

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

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