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

 

Изобретение-относится к вь |числительной технике и микроэлектронике и предназначено для реализации симметрических булевых функций от п аргументов, Цель изобретения - упрощение конструкции устройства для вычисления симметрических булевых функций. Поставленная цель достигается тем, что устройство для вычисления симметрических булевых функций от п аргументов содержит п элементов НЕ, п2 +п элементов 2-2И-2ИЛИ. п информационных входов, п+1 настроечных входов и выход. Устройство работает следующим образом. На информационные входы поступают значения двоичных аргументов xi, X2хп, на настроечные входы - сигналы настройки ЛаЛъ... Лп,, значения которых принадлежат множеству { 0.1}. На выходе устройства реализуется симметрическая булева функция F F (XL ), определяемая двоичным вектором настройки jr(F) ( ЛоД1...., ль.) 1 ил., 1 табл. 3 C/V С

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

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

РЕСПУБЛИК

Is»s G 06 F 7/00

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4801228/24 (22) 12;03.90 (46) 23.06.92. Бюл, № 23 (72) Л.Б.Авгуль и В,П.Супрун . (53) 681.3 (088.8) (56) Авторское свидетельство СССР

¹ 1478208, кл. G 06 F 7/00, 1987.

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

¹ 1119003, кл. G 06 F 7/00. 1983. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

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

Изобретейие относится к вычислитель.ной технике и микроэлектронике и предназ-. начено для реализации симметрических булевых функций (с.б.ф,) и:переменных.

Цель изобретения — упрощение конструкции устройства для вычисления с.б.ф.

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

i-го.элемента 2-2И вЂ” 2ИЛИ i-й группы () = 1, 2, ..., и-i+1), второй вход которого соединен с i-.è информационным входом устройства, Далее i-й настроечный вход устройства сое-. динен с третьим входом i-го элемента 2-2И Ы „1742811 А1

2 булевых функций. Поставленная цельдости- . гается тем, что устройство для вычисления симметрических булевых функций от ri аргументов содержит п элементов НЕ, n +n элементов 2-2И вЂ” 2ИЛИ, и информационных входов, и+1 настроечных входов и выход.

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

На информационные входы поступают значения двоичных аргументов х1, x2, ..., хуу, на настроечные входы — сигналы настройки т(,.)т,... л, значения которых принадлежат множеству { 0,1). На выходе устройства реализуется симметрическая булева функция

F = F (х1, x2...., х()), определяемая двоичным вектором настройки л(Р) =. (. ло,т1,..., лп.)

1 ил., 1 табл.

2ИЛИ первой группы, а (и+1)-й настроечный вход устройства соединен с четвертым входом и-го элемента 2-2И-2ИЛИ первой группы. Третий вход k-го элемента 2-2И-2ИЛИ

1-й группы (k = 1. 2, .;.; n-I+1; I = 2, 3, ..., п) соединен с выходом k-,ro. элемента 2-2И вЂ” .»

2ИЛИ (I-1)-й группы, четвертый вход (и-!+2)- CO го элемента 2-.2И вЂ” 2ИЛИ (1-1)-й группы - ° соединен с выходом (и-1+2)-го элемента 2- а

2И-2ИЛИ (1-1)-й группы. Выход влементв.2—

2И вЂ” 2ИЛИ и-и. группы соединен с выходом устроиствв. Четвертый вход (1-1)-го влемен° мЪ та 2-2И-2ИЛИ первой группы соединен с

I-м настроечным входом устройства, четвертый вход s-го элемента 2-.2И-2ИЛИ 1-й группы (s = 1, 2, ..., n-I) соединен с выходом (s+1)-ro элемента 2-2И-2ИЛИ (1-1)-й группы, Элемент 2-2И-2ИЛИ реализует, булеву функцию f = а1аз а2а4, где аь — двоичная

1742811 переменная, приписанная h-му входу элемента (11 = 1, 2, 3, 4), На чертеже представлена функциональная схема устройства для вычисления с.б.ф. при п =5. 5

Устройство содержит п = 5 элементов

2-2И-2ИЛИ первой группы 11, ..., 15, и-1 = 4 элемента 2-2И-2ИЛИ второй группы 21, ..., 24, и-2 = 3 элемента 2-2И-2ИЛИ третьей группы 31. 32 и 33, и-3 = 2 элемента 2 — 2И вЂ” 10

2ИЛИ четвертой группы 41 и 42, один элемент 2-2И-2ИЛИ пятой группы 5, n = 5 элементов HE 61, ..., 65, n = 5 информационных входов 71...„75, и+1 = 6 настроечных входов 81, ..., 85 и выход 9, 15

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

ПОДаЮтСЯ ДВОИЧНЫЕ ПЕРЕМЕННЫЕ Х1, ..., Хл, на настроечные входы — компоненты двоич- 20 ного вектора и (F) = (па, п1, .„и,), определяющего вид реализуемой устройством с.б.ф. и переменных F в соответствии со следующим выражением:

Yl 25

Г= V ntFn, t=o где Fn — элементарная с.б.ф. от и переменных с рабочим числом t (t = О, 1, ..., n).

На выходе устройства формируется зна- 30 чение с,б.ф. F на данном наборе значений переменных х1, x2, ..., хп. Для рассматриваемого примера (и = 5) на информационные входы 71..„, 75 подаются двоичные переменные x1, ..., х5(в произвольном порядке), 35 на настроечные входы 81, ..., 86 — компоненты no, ..., n5 двоичного вектора n (F) = (n, и, ..., n) реализуемой с,б.ф. F - F (x1, х2, „., х5).

На выходе 9 реализуется с.б.ф. F, заданная вектором n (F). 40

Пример. Найти вектор настройки устройства на реализацию с.б.ф. Е = F (х1, х2. ..., x5), представленной посредством следующей совершенной дизъюнктивной нормальной формы: 45

F = x1x2x3x4x5Vx)x2x3x4x5%/х1х2хЗх4х . \( I х1х2хЗх4х5@1х2хЗх4х". 6(1х2хзх4х9Й1х2хЗх4х5

Двоичный номер N (таблица истинно- 50 сти) заданной функции F имеет вид N = (1 110 1000 1000 0000.1000 0000 0000

0001).

Очевидно, что N = N1 N2 йз, где N1. N2, ЙЗ вЂ” двоичные номера элементарных с,б.ф. 55

F5, F5, F5 соответственно. а

В таком случае n(F) = (1,1,0,0,0,1). Следовательно, на настроечные входы 81, 82, 85 устройства необходимо подать сигнал логической единицы, а на настроечные входы 8з, 84 и 85 — сигнал логического нуля.

Достоинством устройства для вычисления с.б.ф. является простая конструкция.

Число элементов 2-2И-2ИЛИ, необходимых для реализации прототипа, составляет

Snp =2" — 1, . 8 то же время для построения предлагаемого устройства требуется и +и

2 (2) элементов 2-2И-2ИЛИ.

Затраты оборудования, рассчитанные по формулам (1) и (2), сведены в таблицу, Формула изобретения

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

i-й группы (i = 1, 2, ..., n-i+1), второй вход которого соединен с i-м информационным входом устройства, I-й настроечный вход устройства соединен с третьим входом (-ro элемента 2-2И-2ИЛИ первой группы, (n+1)й настроечный вход устройства соединен с четвертым входом и-го элемента 2 — 2И2ИЛИ первой группы, третий вход k-ro элемента 2 — 2И вЂ” 2ИЛИ 1-й группы (k = 1, 2, ..., и-I+1, I = 2, 3, ..., и) соединен с выходом k-го элемента 2-2И-2ИЛИ (1-1)-й группы, четвертый вход (n-1+1)-го элемента 2-2И-2ИЛИ (11)-й группы соединен с выходом (n-1+1)-ro элемента 2 — 2И-2ИЛИ (1-1)-й группы, выход элемента 2-2И-2ИЛИ и-й группы соединен с выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения, четвертый вход (I-1)-ro элемента 2-2И-2ИЛИ первой группы соединен с 1-м настроечным входом устройства, четвертый. вход s-ro элемента

2 — 2И вЂ” 2ИЛИ I-й группы (s = 1, 2, ..., и-1) соединен с выходом (в+1)-ro элемента 2-2И2ИЛИ (И)-й группы.

1742811

71

72 ч

7ф

7, Составитель Л.Авгуль

Техред М.Моргентал

Корректор M.Ïîæî

Редактор А.Мотыль

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

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

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

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