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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения матричных арифметических устройств многофункциональных цифровых преобразователей. Цель изобретения - упрощение конструкции устройства для вычисления симметрических булевых функций. Устройство для вычисления симметрических булевых функци N переменных содержит N групп элементов И и N групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, N информационных входов, N+1 настроечных входов и один выход. На информационные входы устройства подаются двоичные переменные X<SB POS="POST">1</SB>, X<SB POS="POST">2</SB>,..., X<SB POS="POST">N</SB>

на настроечные входы - сигналы настройки γ<SB POS="POST">0</SB>,γ<SB POS="POST">1</SB>,...,γ<SB POS="POST">N</SB>, значения которых принадлежат множеству {0,1}, на выходе устройства реализуется симметрическая булевая функция F=F(X<SB POS="POST">1</SB>,X<SB POS="POST">2</SB>,...,X<SB POS="POST">N</SB>), определяемая вектором настройки F<SB POS="POST">(F)</SB>(<SP POS="POST">г</SP><SB POS="POST">0</SB>,γ<SB POS="POST">1</SB>,...,γ<SB POS="POST">N</SB>). 1 ил.

ССЮЭ СОВЕТСНИХ

СОаЕЛИСТИЧЕСНИХ

РЕСПУБЛИК

ИЕ (И) А1 (gg)g G 06 F 7/00

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

Н АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

ПО И39БРЕТЕНИЯМ И ОТНР1ЫТИЯМ

ПРИ ГКНТ СССР (21) 4461457/24-24 (22) 14.06.88. (46) 23.04.90. Бюл. М 15 (72) Л.Б. Авгуль и В.П. Супрун (53) 681. 3(088.8) (56) Авторское свидетельство СССР

1» 1432500, кл. G 06 F 7/00, 07.04.87.

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

h 1478208, кл. G 06 F 7/00, 22.04.87. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения матричных арифметических устройств многофункциональных цифровых преобра/

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

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

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

Устройство содержит и = 5 элементов U 1,.,.....,,1 первой группы, и =

5 элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2

2»,...,2 первой группы, и - 1 = 4

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

Устройство для вычисления симметрических булевых функций и переменных содержит и групп элементов И и и групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2, и информационных входов, и+1 настроечных входов 1» один выход. На информационные входы устройства подаются двоич»

we переменные Х,,Х <,...,Х„, на настроечные входы - сигналы настройки /, ° ° ь значения которых принадф ° ° ° ° ф лежат мйожеству (0,1) . На выходе устройства реализуется симметрическая булевая функция F=F (X X Х„), определяемая вектором настройки й(Г) = 3

=% У„",Уп) 1И.

С: элемента U 3»,..., 3 ь второй группы, и-1 = 4 элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 4»,...,4+ второй группы, и-2 =

= 3 элемента U 5,...,5 > третьей группы, и-2 = 3 элемента СЛОЖЕНИЕ ПО

МОДУЛЮ 2 6»,...,6 третьей группы, и - 3 = 2 элемента U 7,,и 7 четвертой группы, и-3 = 2 элемента СЛОЖЕНИЕ

ПО МОДУДО 2 8» и 8д четвертой группы, и-4 = 1 элемент U 9 пятой группы, и-4 = 1 элемент СЛОЖЕНИЕ ПО МОДУЛЮ 2,В

10 пятой группы, п = 5 информационных И входов 11»,.. °,11 -, и+1=6 настроечных входов 12,...,,!?, выход 13.

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

На информационные входы 11,,..., Т1 . поступают двоичные переменные X

Х> соответственно, на настроечные входы 12„,...126 - сигналы настройки соответственно, значения которых принадпемат множеству (O,lj.

На выходе 13 реализуется с.б.ф. F =

= F (Х„, Х, Х, Х4, X ), .определяемая вектором настройки g (Р) =(о,,, ф, 3) « 3 о» 35) .

Пусть с.б.ф. F существенно зависит от n, аргументов Х, Х,..., X„ и а, а <,...,а t - рабочие числа

F где 1 а r n+1, такую с.б.ф. обоз"15 начим через F " ". ".. Если r = 1, ® и то с.б.ф. F называется элементарной /или фуйдаментальной) с.б.ф.Произвольная с.б.ф. F =F (Х„,Х,...,Х„) может быть задана двоичным вектором 20 (кодом) н (F) = (lip )i<, .. ° n), где

/н

, - значение У на (любом) наборе значений п .аргументов c i единицами (О и i « n). Очевидно, что n = 1 только тогда, когда i Е g а,, а2,..., 25

О /- 1 л И а ) и F = но Fn ×í,FgЧ...ч "nF

Следовательно, определение вектора ii (F) („, и,,..., ) некоторой с.б.m. F сводится к нахождению таких э.с.б.ф., поразрядная дизъюнкция дво- gp ичных номеров которых дает двоичный номер исходной функции.

С.б.ф. F можно представить пос- . редством (и+1)-разрядного двоичного вектоРа II (F)=(fp, g,,...,| „), где /; = 5 (1000 0000 0000. 0000 и600 0000 0000 0000); (0110 1000 1000 0000 1000 0000 0000 0000); (0001 0110 0110 1000 0110 1000 1000 0000); (0000 0001 0001 0110 0001 0110 0110 1000)р (0000 0000 0000 0001 0000 0001 0001 0110); (0000 0000 0000 0000 0000 0000 0000 0001). р о

F2 12 р г — и р

, — ьф

FР р р,имеет вид

Nr (1111 1110 1110 1001 1 110 1001 1001 0110).

Очевидно, что о 1,= 1 1,Ч 1 1,Ч Я, Ч

Ч У, Ч 5 Ч

Следовательно, сигналы логической

50 единицы должны быть поданы на первый

12, четвертый 12 < и шестой 12 наст-, роечные входы устройства, а сигналы логического нуля — на второй 12, тре2р тий 12> и пятый 12 настроечные входы.

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

Двойчный номер заданной с.б.ф.

Тогда и„(F) = (1, 1, 1, О, 1, О) ° дспользуя метод "треугольника"

В.П. Супруна преобразуем в код :" и(Г) в вектор настройки (F).

Отсюда получаем $ (F) =(1,0,0,1, 0,1) .

=1 только в том случае, когда все слагаемые ранга i входят в полином

Жегалкина данной с.б.ф. F(0 i n).

Компоненты вектора 2I (F) и являются с сот ветст вующими си r нала ми на строй ки устройства .для вычисления с.б.ф. п переменных.

Таким образом, можно выделить следующие этапы нахождения вектора настройки 2I (F) устройства на реализацию заданной с.б.ф. F = F (X,X,...,Х„).

Определяется множество э. с.б.ф., подразрядная дизъюнкция двоичных номеров которых дает двоичный номер (таблицу истинности) заданной функции.

По виду найденных э,с.б.ф. формируется вектор N (F) (р (р ° ° р p)

Вектор н (F) преобразуется в вектор, настройки g(F) .

Пример. Найти вектор настройки g(F) устройства (n=5) на реализа,(цию с. б.ф. F=F (Х ), Х 2, Х q, Х, Х )

=Х, X 2X> V.(X1Х2Х Ч Х, Х2Х>Ч Х, Х2Х ) (Х Ч ХДЧ

Ч(Х Х2Х Ч Х Х ХэЧХ Х Х>) ГХ+Х V Х Х )Y

Ч Х, Х2Х (Х+Х Ч Х Х ) .

С.h,ô. F можно представить в виде

Г(Х,Х2,Хз,Х+,X )= up F+v F>V>i2F+v

F3V/ F% F5

Прйчем двоичные номера, э.с.б.ф. для a=5 имеют следующее представление:

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

1 55933?

6 и групп (n - количество аргументов ре- ва соединен с вторым входом 1-го эле,ализуемых логических функций) эле- мента И первой группы и вторым входОм ментов И, i-я из которых содержит (1-1)-го элемента сложения по модулю

n- i+1 элементов (i=1,n), о т л и ч а.- два первой группы, (п+1)-й построечю щ е е с я тем, что, с целью упро- - ный вход устройства соединен с вторым щения устройство содержит и групп эле- входом п-го элемента сложения по модументов сложения по модулю два, i-я из лю два первой группы, выход m-го элекотоРых содервит о-i+1 элементов, при- мента словении по модулю два k-й групием i-й инФормационный вход устройст- о пы (в=1, и-k;K=1,п-1) соединен с втова соединен с первым входом 1-го эле- рым входом т-го элемента И (k+1)-й мента И i-й группы (j=1, и-i+1), вы- группы, второй вход t-го элемента слоход которого соединен с первым входом жения Ro модулю два 1-й группы (t =

j-ro элемента сложения по модулю два = 1, п-1+1) соединен с выходом (t+1)1 и группы, первый настроечный вход 1> го,элемента сложения по модулю два устройства соединен с вторым входом (1-1)-й группы, выход элемента сложепервого элемента И первой группы, - ния по модулю два и-й группы соеди1-й настроечный вход (1=2,n) устройст- нен с выходом устройства.

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

Техред И. Хода нич Корректор Л. Патай

Редактор Л. Гратилло

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

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

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

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