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

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ, содержащее два элемента ИЛИ НЕ, элемент ИЛИ, элемент И и элемент сложения по модулю два, выход которого соединен с первым входом элемента И, второй вход которого соединен с первым настроечным входом устройства, второй настроечный вход которого соединен с первым входом первого элемента ИЛИ НЕ, второй вход которого соединен с выходом элемента И, i-й вход которого соединен с i-м входом элемента сложения по модулю два и i-м информационным входом устройства, отличающееся тем, что содержит пять элементов ЗАПРЕТ, мажоритарный элемент с порогом три и мажоритарный элемент с порогом пять, j-й вход которого соединен с j-м информационным входом устройства и j-м входом мажоритарного элемента с порогом три, выход элемента ИЛИ соединен с первым прямым входом первого элемента ЗАПРЕТ, второй прямой вход которого соединен с третьим настроечным входом устройства, первый инверсный вход первого элемента ЗАПРЕТ соединен с выходом мажоритарного элемента с порогом три, инверсным входом второго элемента ЗАПРЕТ, первым входом третьего элемента ЗАПРЕТ и первым прямым входом четвертого элемента ЗАПРЕТ, второй инверсный вход первого элемента ЗАПРЕТ соединен с первым прямым входом второго элемента ЗАПРЕТ, первым инверсным входом третьего элемента ЗАПРЕТ, вторым прямым входом четвертого элемента ЗАПРЕТ, инверсным входом пятого элемента ЗАПРЕТ и выходом элемента сложения по модулю два, третий вход элемента И соединен с выходом мажоритарного элемента с порогом пять, вторым инверсным входом третьего элемента "запрет", инверсным входом четвертого элемента ЗАПРЕТ и первым прямым входом пятого элемента ЗАПРЕТ, второй прямой вход которого соединен с четвертым настроечным входом устройства, пятый настроечный вход которого соединен с вторым прямым входом второго элемента ЗАПРЕТ, шестой настроечный вход соединен с вторым прямым входом третьего элемента ЗАПРЕТ, седьмой настроечный вход соединен с третьим прямым входом четвертого элемента ЗАПРЕТ, выход которого соединен с первым входом второго элемента ИЛИ НЕ, второй вход которого соединен с выходом первого элемента ИЛИ НЕ, выходы первого, второго, третьего, четвертого и пятого элементов ЗАПРЕТ соединены с третьим по шестой входами второго элемента ИЛИ НЕ, седьмой вход которого соединен с выходом элемента И, выход второго элемента ИЛИ НЕ является выходом устройства, пятый и шестой информационные входы которого соединены с пятыми и шестыми входами элемента сложения по модулю два и элемента И.

Описание изобретения к патенту

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

Известно устройство для вычисления симметрических булевых функций n переменных, которое при n=6 содержит 21 элемент сложения по модулю два и 21 элемент И [1]

Недостатком устройства является низкое быстродействие, определяемое глубиной схемы и равное 12t, где t задержка на вентиль.

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

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

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

Устройство содержит элемент ИЛИ 1, мажоритарный элемент с порогом три 2, мажоритарный элемент с порогом пять 3, элемент сложения по модулю два 4, два элемента ИЛИ-НЕ 5 и 6, пять элементов ЗАПРЕТ 7, 8, 9, 10 и 11, элемент И 12, шесть информационных входов 13-18, семь настроечных входов 19-25, выход 26.

В устройстве i-й (i=) вход элемента ИЛИ 1 соединен с i-м информационным входом устройства, i-м входом мажоритарного элемента с порогом три 2, i-м входом мажоритарного элемента с порогом пять 3 и i-м входом элемента сложения по модулю два 4. Выход элемента сложения по модулю два 4 соединен с первым входом элемента И 12, второй вход которого соединен с первым настроечным входом 25 устройства. Второй настроечный вход устройства 19 соединен с первым входом первого элемента ИЛИ-НЕ 5. Выход элемента ИЛИ 1 соединен со вторым входом первого элемента ИЛИ-НЕ 5 и первым прямым входом первого элемента ЗАПРЕТ 7, второй прямой вход которого соединен с третьим настроечным входом устройства 20. Первый вход запрета первого элемента ЗАПРЕТ 7 соединен с выходом мажоритарного элемента с порогом три 2, входом запрета второго элемента ЗАПРЕТ 8, первым прямым входом третьего элемента ЗАПРЕТ 9 и первым прямым входом четвертого элемента ЗАПРЕТ 10, второй вход запрета соединен с первым прямым входом второго элемента ЗАПРЕТ 8, первым входом запрета третьего элемента ЗАПРЕТ 9, вторым прямым входом четвертого элемента ЗАПРЕТ 10, входом запрета пятого элемента ЗАПРЕТ 11 и первым входом элемента И 12. Третий вход элемента И 12 соединен с выходом мажоритарного элемента с порогом пять 3, вторым входом запрета третьего элемента ЗАПРЕТ 9, входом запрета четвертого элемента ЗАПРЕТ 10 и первым прямым входом пятого элемента ЗАПРЕТ 11, второй прямой вход которого соединен с четвертым настроечным входом 24 устройства, пятый настроечный вход 21 которого соединен со вторым прямым входом второго элемента ЗАПРЕТ 8, шестой настроечный вход 22 соединен со вторым прямым входом третьего элемента ЗАПРЕТ 9, седьмой настроечный вход 23 соединен с третьим прямым входом четвертого элемента ЗАПРЕТ 10, выход которого соединен с первым входом второго элемента ИЛИ-НЕ 6. Второй вход элемента ИЛИ-НЕ 6 соединен с выходом первого элемента ИЛИ-НЕ 5, третий вход которого соединен с выходом первого элемента ЗАПРЕТ 7, четвертый вход соединен с выходом второго элемента ЗАПРЕТ 8, пятый вход соединен с выходом третьего ЗАПРЕТ 9, шестой вход соединен с выходом пятого запрет 11, седьмой вход соединен с выходом элемента И 12, а выход соединен с выходом 26 устройства.

Устройство для вычисления симметрических булевых функций работает следующим образом. На информационные входы 13-18 поступают двоичные переменные х₁-х₆ (в произвольном порядке), на настроечные входы 19-25 сигналы настройки u₁-u₇ соответственно, значения которых принадлежат множеству0, 1} На выходе 26 реализуется некоторая симметрическая булева функция F=F(), определяемая вектором настройки U=(u₁, u₂,u₆).

Рассмотрим алгоритм настройки. Пусть P_s значение F на наборе аргументов х₁, х₂, х₆, содержащем ровно s единиц, т.е. F=F()p_s при х₁+х₂+х₃+х₄+х₅+х₆=s, s .

Компоненты вектора настройки U определяются следующим образом:

т.е.

П р и м е р. Определим вектор настройки U устройства на реализацию функции

F=F() x

Решение. Очевидно, что р(F)=(р₀, р₁, р₂, р₃, р₄, р₅, р₆)=(1, 0, 0, 0, 0, 1, 1). Тогда U=(0, 0, 0, 0, 0, 1, 1).

Следовательно, сигнал логического нуля должен быть подан на настроечные входы 19, 20, 21, 22 и 23, а сигнал логической единицы на настроечные входы 24 и 25.

Таким образом, устройство реализует все 128 симметрических булевых функций шести переменных.

Сложность (по числу входов логических элементов) предлагаемого устройства равна 55, а быстродействие, определяемое глубиной схемы, 3t, где t задержка на вентиль.

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