Устройство для вычисления симметрических булевых функций Советский патент 1993 года по МПК G06F7/00 

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

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

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

Наиболее близким к предлагаемому по функциональным возможностями конструкции техническим решением является устройство для вычисления с.б.ф. четырех переменных, содержащее два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть эле- . ментов И, три элемента ИЛИ-НЕ и шесть элементов И-НЕ.

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

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

4 00 О ЧЭ VJ

ON

Поставленная цель достигается тем, что в устройство для вычисления симметрических булевых функций, содержащее элемент Л и первый элемент ИЛИ-НЕ, введены со второго по четвертый элементы ИЛИ-НЕ, элемент РАВНОЗНАЧНОСТЬ, элемент И- НЕ, сумматор, два элемента ЗАПРЕТ и одиннадцать элементов ИЛИ, 1-й (I 1- 2) вход первого из которых соединен с i-м ин- формациодным входом устройства, I-м входом элемента РАВНОЗНАЧНОСТЬ и 1-м входом%лем;ента И-НЕ, а выход первого элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ и первым входом О + 1}-г6 0 1,2, 3) элемента ИЛИ, выход элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом (j + 4)-го элемента ИЛИ, выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым входом О + 7)-го элемента ИЛИ, первый настроечный вход устройства соединен с вторым входом первого элемента ИЛИ-НЕ, второй настроечный вход устройства соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом второго элемента ИЛИ, третий настроечный вход устройства боединен со вторым входом третьего элемента ИЛИ-НЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого элемента ИЛИ, четвертый настроечный вход устройства соединен с вторым входом четвертого элемента ИЛИ, втбрым входом шестого элемента ИЛИ и вторым входом восьмого элемента ИЛИ, пятый настроечный вход устройства соединен с вторым входом седьмого элемента ИЛИ и вторым входом девятого элемента ИЛИ, шестой настроечный вход устройства соединен со вторым входом десятого элемента ИЛИ, (j + 2)-й информационный вход устройства соединен с j-м входом одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом элемента И, первым прямым входом первого элемента ЗАПРЕТ, инверсным входом второго элемента ЗАПРЕТ и Первым входом четвертого элемента И- НЕ, (j + 1}-й вход которого соединен с выходом j-ro элемента ИЛИ-НЕ, пятый вход четвертого элемента ИЛИ-НЕ соединен с выходом переноса одноразрядного двоичного сумматора, вторым входом элемента И, первым прямым входом второго элемента ЗАПРЕТ и инверсным входом первого элемента ЗАПРЕТ, Q + 1)-й прямой вход которого соединен с выходом (3j - 1)-го элемента ИЛИ, а выход первого элемента ЗАПРЕТ соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИНЕ, э третий вход одиннадцатого элемента ИЛИ соединен с выходом второго элемента ЗАПРЕТ, О + 1}-й прямой вход которого соединен с выходом 3j-ro элемента ИЛИ, выход (3J + 1)-го элемента ИЛИ соединен с (j + 2)-м входом элемента И, выход которого соединен с четвертым входом одиннадцатого элемента ИЛИ, выход которого является выходом устройства.

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

5 элемента ИЛИ-НЕ, два элемента ЗАПРЕТ, элемент И. Причем, 1-й (,2) вход элемента ИЛИ соединен с I-м информационным входом устройства, 1-м входом элемента РАВНОЗНАЧНОСТЬ и 1-м входом элемента

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

5 второго элемента ИЛИ-НЕ и первым входом О + 4}-го элемента ИЛИ. Выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым входом (j + 7)-го элемента ИЛИ. Первый настроечный вход

0 устройства соединен со вторым входом первого элемента ИЛИ-НЕ. Второй настроечный вход устройства соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом второго элемента ИЛИ. Третий на5 строечный вход устройства соединен со вторым входом третьего элемента ИЛИ-НЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого элемента ИЛИ. Четвертый настроечный вход устройства соеди0 иен с вторым входом четвертого элемента ИЛИ, вторым входом шестого элемента ИЛИ и вторым входом восьмого элемента ИЛИ. Пятый настроечный вход устройства соединен с вторым входом седьмого эле5 мента ИЛИ и вторым входом девятого элемента ИЛИ. Шестой настроечный вход устройства соединен с вторым входом десятого элемента ИЛИ. Далее 0 + 2)-й информационный вход устройства соединен с J-м

0 входом одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом элемента И, первым прямым входом первого элемента ЗАПРЕТ, инверсным входом второго элемента ЗАПРЕТ и

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

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

На чертеже представлена схема устройства для вычисления с.б.ф. пяти переменных.- .

Устройство содержит одиннадцать элементов ИЛИ 1 ... 11, элемент РАВНОЗНАЧНОСТЬ 12, элемент И-НЕ .одноразрядный двоичный сумматор 14, четыре элемента ИЛИ-НЕ 15 ... 18, два элемента ЗАПРЕТ 19 и 20, элемент И 21, пять информационных входов 22 ... 26, шесть настроечных входов 27 ... 32, выход 33.

.Устройство для вычисления с.б.ф. работает следующим образом. На информацией- ные входы 22 ... 26 поступают двоичные переменные xi... xs (в произвольном порядке); на настроечные входы 27... 32 подаются сигналы настройки щ ... ие соответственно, значения которых принадлежат множеству {О, 1}. На выходе 33 реализуется некоторая с.б.ф. пяти переменных F F(xi, X2, ..., xs), определяемая вектором настройки U (щ,

U2, ..., U6).

Рассмотрим алгоритм настройки устройства. Известно (см., Лупанов О.Б. Об одном подходе к синтезу управляющих систем - принципе локального кодирования // Проблемы кибернетики. - М.: Наука. 1965, вып. 14, с. 31-110), что произвольная с.б.ф. п переменных F F(xi, xa,..., хп) может быть однозначно определена (п + разрядным двоичным кодом n(F) (no, ni,..., Пп), где щ - значение функции F на (любом) наборе значений переменных xi, Х2,..., хп; содержащем ровно i единиц (| 0, 1, .... п). Другими словами, если xi + Х2 + ... хп I, то значение F на данном наборе переменных равно щ.

Тогда сигналы настройки устройства на реализацию с.б.ф. F F(xi, X2, .... xs), заданной двоичным кодом n(F) (n0, ni, .... ns), вычисляются как uj nj-i, где j 1,2, ..., 6.

Пример. Пусть требуется определить настройку устройства на реализацию с.б.ф. F F(xi, X2,.... xs), заданной таблицей истинности N(F), где

N(F) (1110 1000 1000 0001 1000 0001 00010110).

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

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

Изобретение относится к вычислительной технике и микроэлектронике и предназ- начено для реализации симметрических булевых функций пяти переменных. Цель изобретения - расширение функциональных возможностей за счет реализации симметрических булевых функций пяти переменных. Поставленная цель достигается тем, что устройство для вычисления симметрических булевых функций пяти переменных содержит одиннадцать элементов ИЛИ, элемент равнозначности, элемент И- НЕ, одноразрядный двоичный сумматор, четыре элемента ИЛИ-НЕ, элементы И и ЗАПРЕТ, пять информационных входов, шесть настроечных входов и выход. Сложность устройства по числу входов логических элементов равна 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 табл. ..... ел

Формула изобретения Устройство для вычисления симметрических булевых функций, содержащее элемент И и первый элемент ИЛИ-НЕ, отличающееся тем, что, с целью расширения функциональных возможностей за счет реализации симметрических булевых функций пяти переменных, оно содержит с второго по четвертый элементы ИЛИ-НЕ, элемент РАВНОЗНАЧНОСТЬ, элемент И-НЕ, одноразрядный двоичный сумматор, два элемента ЗАПРЕТ и одиннадцать элементов ИЛИ, 1-й (1 1,2) вход первого из которых соединен с i-м информационным входом устройства, i-м входом элемента равнозначности и i-м входом элемента И-НЕ, а выход первого элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ, и первым входом J + 1-го 0 1, 2, 3) элемента ИЛИ, выход элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом j + 4-го элемента ИЛИ, выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым входом J + 7-го элемента ИЛИ, первый настро- .ечный вход устройства соединен с вторым

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

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

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

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