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

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

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

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

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

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

Устройство содержит два элемента сложения по модулю два 1 и 2, мажоритарный элемент с порогом два 3, мажоритарный элемент с порогом четыре 4, два элемента НЕ 5 и 6, пять элементов И 7, 8, 9, 10 и 11, четыре элемента ИЛИ-НЕ 12, 13, 14 и 15, шесть информационных входов 16.21, семь настроечных входов 22.28, выход 29.

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

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

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

, u₄=

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

F=F()= x₁x₂x₃x₄x₅

x₁x₂x₃x₄x₆ x₁x₂x₃x₅x₆ x₁x₂x₄x₅x₆ x₁x₃x₄x₅x₆ x₂x₃x₄x₅x₆

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

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

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

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