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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и микроэлектронике и предназначено для реализации симметрических булевых функций пяти переменных. Цель изобретения - расширение функциональных возможностей за счет реализации симметрических булевых функций пяти переменных. Поставленная цель достигается тем, что устройство для вычисления симметрических булевых функций пяти переменных содержит одиннадцать элементов ИЛИ, элемент равнозначности, элемент И- НЕ, одноразрядный двоичный сумматор, четыре элемента ИЛИ-НЕ, элементы И и ЗАПРЕТ, пять информационных входов, шесть настроечных входов и выход. Сложность устройства по числу входов логических элементов равна 60, быстродействие, определяемое глубиной схемы, составляет 4 г, где гзадержка на вентиль. На информационные входы поступают двоичные переменные XL Х2, з, Х4, Х5 (в произвольном порядке), на. настроечные входы - сигналы настройки Ui, Ua, Ua, Ito. Us, Ue, значения которых принадлежат множеству {0, 1). На выходе устройства реализуется симметрическая булева функция F F(xi, ха. хз, Х4, xs), определяемая вектором настройки U (Ui, U2, Us, Щ, Us, Ue). 1 ил, 1 табл. ..... ел

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

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

РЕСПУБЛИК (51)5 G 06 F 7/00

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

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4810554/24 (22) 06.04,90 (46) 23.01.93, Бюл. М 3 (72) Л.Б.Авгуль, В.П,Супрун, В.И.Костеневич и В.В.Торбунов (56) Авторское свидетельство СССР

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

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

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

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

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

„„. Ж, „1789976 Al метрических булевых функций пяти переменных содержит одиннадцать элементов

ИЛИ, элемент равнозначности, элемент ИН Е, одноразрядный двоичный сумматор, четыре элемента ИЛИ-НЕ, элементы И и

ЗАПРЕТ, пять информационных входов, шесть настроечных входов и выход, Сложность устройства по числу входов логических элементов равна 60, быстродействие, определяемое глубиной схемы, составляет 4 г, где r — задержка на вентиль, На информационные входы поступают двоичные переменHbI8 Х1, Х2, Хз, Х4, Х5 (В ПРОИЗВОЛЬНОМ порядке), на, настроечные входы — сигналы настройки.01, Uz, Оз, 0< ОБ, Оа, значения которых принадлежат множеству (О, 1). На выходе устройства реализуется симметрическая булева функция F = F (х1, хъ хз, х4, ХБ), определяемая вектором настройки U = (01, tjl

02, Оз, 04, ОБ, ОБ). 1 ил, 1 табл, 00

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

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть еле- . )ле ментов И, три элемента ИЛИ-НЕ и шесть а элементов И-НЕ.

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

Цель изобретения — расширение функциональных возможностей устройства за счет реализации с.б,ф, пяти переменных.

1789976

Поставлднйая цель достигается тем, что в устройство для вычисления симметрических булевых функций, содержащее элемент И и первый элемент ИЛИ-НЕ, введены со второго по четвертый элементы ИЛИ-НЕ, 5 элемент РАВНОЗНАЧНОСТЬ, элемент ИНЕ, сумматор, два элемента ЗАПРЕТ и одиннадцать элементов ИЛИ, 1-й (! = 1- 2) вход первого из которых соединен с i-u информационным входом устройства, i-м вхо- 1О дом элемента РАВНОЗНАЧНОСТЬ и i-м входоМзлемента И-НЕ, а выход первого элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ и первым входом (j + 1)-го O = 1, 2, 3) элемента ИЛИ, выход 15 элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом (j + 4)-го элемента ИЛИ, выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым 20 входом (j + 7)-ro элемента ИЛИ, первый настроечный вход устройства соединен с вторым входом первого элемента ИЛИ-НЕ, второй настроечный вход устройства соединен с вторым входом второго элемента

ИЛИ-НЕ и вторым входом второго элемента

ИЛИ, третий настроечный вход устройства

Соединен со вторым входом третьего элемента ИЛИ-НЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого зле- N мента ИЛИ, четвертый настроечный вход. устройства соединен с вторым входом четвертого элемента ИЛИ, вторым входом шестого элемента ИЛИ и вторым входом восьмого элемента ИЛИ, пятый настроечный вход устройства соединен с вторым входом седьмого элемента ИЛИ и вторым входом девятого элемента ИЛИ, шестой настроечный вход устройства соединен со вторым входом десятого элемента MilM, (j+ 2)-й 4О информационный вход устройства соединен с j-м входом одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом элемента И, первым прямым входом первого элемента ЗАПРЕТ, ин- 45 версным входом второго элемента ЗАПРЕТ и первым входом четвертого элемента ИНЕ, (j + 1)-й вход которого соединен с выходом j-ro элемента ИЛИ-НЕ, пятый вход четвертого элемента ИЛИ-НЕ соединен с 0 выходом переноса одноразрядного двоичного сумматора, вторым входом элемента И, первым прямым входом второго элемента

ЗАПРЕТ и инверсным входом первого элемента ЗАПРЕТ, (j + 1)-й прямой вход которо- 55 го соединен с выходом (3j - 1)-го элемента

ИЛИ, а выход первого элемента ЗАПРЕТ соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИНЕ, а третий вход одиннадцатого элемента

ИЛИ соединен с выходом второго элемента

ЗАПРЕТ, (j + 1)-й прямой вход которого соединен с выходом 3j-ro элемента ИЛИ, выход (3) + 1)-ro элемента ИЛИ соединен с (j + 2)-м входом элемента И, выход которого соединен с четвертым входом одиннадцатого элемента ИЛИ, выход которого является выходом устройства.

Устройство для вычисления симметрических булевых функций пяти переменных содержит одиннадцать элементов Mill элемент РАВНОЗНАЧНОСТЬ, элемент И-НЕ, одноразрядный двоичный сумматор, четыре элемента ИЛИ-НЕ, два элемента ЗАПРЕТ, элемент И, Причем, i-й (! = 1, 2) вход элемента ИЛИ соединен с i-м информационным входом устройства, i-м входом элемента

РАВНОЗНАЧНОСТЬ и i-м входом элемента

И-НЕ. Выход первого элемента ИЛИ соединен с первым входом первого элемента

ИЛИ-НЕ и первым входом (j + 1)го (j = 1, 2, 3) элемента ИЛИ, Выход элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом (j + 4)-го элемента ИЛИ. Выход элемента

И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым входом (j+ 7)го элемента ИЛИ. Первый настроечный вход устройства соединен со вторым входом первого элемента ИЛИ-НЕ. Второй настроечный вход устройства соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом второго элемента ИЛИ. Третий настроечный вход устройства соединен со вторым входом третьего элемента ИЛИ-НЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого элемента ИЛИ. Четвертый настроечный вход устройства соединен с вторым входом четвертого элемента

ИЛИ. вторым входом шестого элемента

ИЛИ и вторым входом восьмого элемента

ИЛИ. Пятый настроечный вход устройства соединен с вторым входом седьмого элемента ИЛИ и вторым входом девятого элемента ИЛИ, Шестой настроечный вход устройства соединен с вторым входом десятого элемента ИЛИ. Далее (j+ 2}-й информационный вход устройства соединен с )-м входом одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом элемента И, первым прямым входом первого элемента ЗАПРЕТ, инверсным входом второго элемента ЗАПРЕТ и первым входом четвертого элемента ИЛИНЕ, (j + 1)-й вход которого соединен с выходом j-ro элемента ИЛИ-НЕ. Пятый вход четвертого элемента ИЛИ-НЕ соединен с выходом переноса одноразрядного двоичного сумматора, вторым входом элемента И, 1789976

20

40, первым прямым входом второго элемента

ЗАПРЕТ и инверсным входом первого элемента ЗАПРЕТ, (j+ 1)-й прямой вход которого соединен с выходом (3j - 1)-го элемента

ИЛИ. Выход первого элемента ЗАПРЕТ соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИНЕ. Третий вход одиннадцатого элемента

ИЛИ соединен с выходом второго элемента

ЗАПРЕТ, (j + 1)-й прямой вход которого соединен с выходом 3J-го элемента ИЛИ.

Выход (3) + 1)-го элемента ИЛИ соединен с (j+ 2)-м вхпдом элемента И, выход которого соединен с четвертым входом одиннадцатого элемента ИЛИ, выход которого является выходом устройства, На чертеже представлена схема устройства для вычисления с.б,ф, пяти переменных.

Устройство содержит одиннадцать элементов ИЛИ 1 ... 11, элемент РАВНОЗНАЧНОСТЬ 12, элемент И-НЕ 13, одноразрядный двоичный сумматор 14, четыре элемента ИЛИ-НЕ 15 .„18, два элемента

ЗАПРЕТ 19 и 20, элемент И 21, пять информационных входов 22 ... 26, шесть настроечных входов 27 ... 32, выхсд 33. ,Устройство для вычисления с.б,ф. работает следующим образом. На инфо рмационные входы 22 ... 26 поступают двоичные переменные x> ... xs (a произвольном порядке); на настроечные входы 27 ... 32 подаются сигналы настройки ut „, u6 соответственно, значения которых принадлежат множеству (О, 1). На выходе 33 реализуется некоторая с.б.ф, пяти переменных F = F(x<, xz, ..., xs), определяемая вектором настройки U = (u>, uz .", ue).

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

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

РАВНОЗНАЧНОСТЬ, элемент И-НЕ, одноразрядный двоичный сумматор, два элемента ЗАПРЕТ и одиннадцать элементов ИЛИ, 1-й (i = 1, 2) вход первого из которых соедиРассмотрим алгоритм настройки устройства, Известно (см„Лупанов О.Б, Об одном подходе к синтезу управляющих систем — принципе локального кодирования

// Проблемы кибернетики. — M,: Наука, 1965, вып. 14, с. 31 — 1 i0), что произвольная с.б.ф. и переменных F = F(x<, xz, ..., х, ) может быть однозначно определена (и + 1)-разрядным двоичным кодом n(F) = (n>, ni, ..., и,), где

n< — значение функции F на (любом) наборе значений переменных х1, xz, ..., хп; содержащем ровно i единиц (i = О, 1, ..., и). Другими

СЛОВаМИ, ЕСЛИ Х1+ XZ+ „. Хл = i; тО ЗНаЧЕНИЕ

F на данном наборе переменных равно пь

Тогда сигналы настройки устройства на реализацию с.б,ф. F = F(x>, xz...„х5), заданной Двоичным кОДОм n(F) = (п0, п1, ...,. n5), вычисляются как ш = ni-1, где j = 1, 2, „„6.

Пример. Пусть требуется onределить настройку устройства на реализацию с.б,ф.

F = F(x>, xz, ..., х5), заданной таблицей истинности N(F), где

М(Р) — — (1110 1000 1000 0001 1000 0001

0001 0110).

Нетрудно видеть, что имеет место

n(F) = (1, 1, О, О, 1, О). Следовательно, для реализации функции F необходимо на настроечные входы 29, 30 и 32 подать сигнал логического нуля, а на настроечные входы

27, 28 и 31 — сигнал логической единицы, . Достоинством устройства являются широкие функциональные возможности. По сравнению с прототипом устройство реализует в два раза больше с.б.ф. (64 с.б.ф, пяти переменных против 32 с.б.ф. четырех переменных), Отметим, что быстродействие устройства, определяемое глубиной схемы, совпадает с быстродействием прототипа и составляет 4 т, где г — задержка на вентиль, нен с i-м информационным входом устройства, i-м входом элемента равнозначности и

i-м входом элемента И-НЕ, а выход первого элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ, и первым входом j + 1-го (j = 1, 2, 3) элемента ИЛИ, выход элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом J+4-го элемента ИЛИ, выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым входом J+ 7-го элемента ИЛИ, первый настро.ечный вход устройства соединен с вторым

1789976 входом первого элемента ИЛИ-HF., второй настроечный вход устройства соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом второго элемента ИЛИ, третий настроечный вход устройства соединен с вторым входом третьего элемента ИЛИНЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого элемента ИЛИ, четвертый настроечный вход устройства соединен с вторым входом четвертого элемента

ИЛИ, вторым входом шестого элемента

ИЛИ и вторым входом восьмого элемента

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

Таблица двоичных номеров реализуемых функций, 27

29

32

33

F(K1,Х2,X3,Х4,Х5) 2 3

00000000000000000000000000000001

00000000000000010000000100010111

00000Î01000l01l00001011001101001

00000001000101110001011101111111

000I01100II0i0D001IО1ООО1ООООООО

0001011001l010000110l00010000001

000101100110100101 10100110010111

000l01110I1111100l1111101il01000

00010111Î1111l1ÎÎ111111Î111Î1001

00010111011111110111111111111111

0110l00010000000I000000000000000

01101000100000001000000000000001

01101000100000011000000100010111

01101001100l01101001011001101000

0ll010011Î0l0ll0100101100l101001

0110100110010l l1001011101llll11

0111l11011l01000li101000l0000000

01111110111010001110100010000001

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

1

1

1

1

О

О

О

О

О

О

О

1

1

1

1

О

О

О

О

О

О

О

О

0

О

О

О

1

1

О

О

1

1

Î

О

О

О

1

1

О

0

О

1

О

1

0

О

1

О.

1

О

1

О

0

О

О

О

О

О

О

О

0

0

0

О

1 второго элемента ЗАПРЕТ и первым входом четвертого элемента ИЛИ-НЕ, j + 1-й вход которого соединен с выходом j-го элемента

ИЛИ-НЕ, пятый вход четвертого элемента

ИЛИ-НЕ соединен с выходом переноса одноразрядного двоичного сумматора., вторым входом элемента И, первым прямым входом второго элемента ЗАПРЕТ и инвер-. сным входом. первого элемента ЗАПРЕТ, )+ 1-й прямой вход которого соединен с выходом 3j - 1-ro элемента ИЛИ, а выход первого элемента ЗАПРЕТ соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИ-НЕ, а третий вход одиннадцатого элемента ИЛИ соединен с выходом второго элемента ЗАПРЕТ, j + 1-й прямой вход которого соединен с выходом

3)-го элемента ИЛИ, выход 3j + 1-го элемента ИЛИ соединен с ) + 2-м входом элемента

И, выход которого соединен с четвертым входом одиннадцатого элемента ИЛИ, выход которого является выходом устройства, 1789976

1

1

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0 о

0 0

0

0

0

0

1

1

1

1

1

1

1

1

1 .1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

Продолжение таблицы

01112210121010012lloi001100i.olii

01111111111I1II0111111l01110i000

O111111Il11i111011ll1i1O111O1001

0I111111l1111llllll11111111i2110

011111111I111111l111111Il2l11111

10000000000000000000000000000001

iO00OO0000OO000I000000Oi0001Oi10

10O0000O0OO0OO01000000O10O0l0li1

IOOOOOO2OOOiOiiOOOOlO22OOI1O1OOO

10000001000101100001011001101001

10O00OO1OOO1O1l10O010l110E111110

10000001000101110001011101111111

100lO1iOO1i0i0OO01i0lOOOi0O000OO

10010110OllOi00OO11O1O0O1O000001

100101100.11010010110100110010110 10Oi01i001I01O01OII01O01l0010111

10020112011112100121111022101000

I001OI1l011122IO0IlI2I10I1202001

10OiOi1lOiIii11iOI11111111l11110

10010111012221 10111111111111211

l11O1OO0iO000OOO1O000O00000000OO

11101000200000001000000000000001

1l1O1OOOiOOO0OO11OOOO0O10O010120

221O1O0O10OO0O0I1O0O0O010OO2OIII

11101001100101101001011001101001

IIIOIO012OO1O21I2O0l01110I121110 11iOi0Oii0OiOl112OOlOl11O1111111

11112110111020001110100010000001

I22i2IIO2 IIOIOOI22IOIOO22OOIO2i1111111 1111111101111111011101000

12lI11liI.ii1l11O1i1l113.О111О10О1

1111 11121112111111111111li111111

1789976

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

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

Редактор Т; Шэгова

Корректор Н, Король

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

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

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