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

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

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

Устройство для вычисления с.б.ф. от п переменных содержит п элементов НЕ и п групп элементов 2-2И-2ИЛИ. имеет п информационных и п+1 настроечных входов и один выход. Причем каждая ;я группа.О 1.

2 п) содержит п+ 1 элементов 2-2И 2ИЛИ, а 1-й информационный вход устройства соединен с входом 1-го элемента НЕ, выход которого соединен с первым входом 1-го элемента 2-2И-2ИЛИ i-й группы .

2n-i+1), второй вход которого соединен

с i-м информационным входом устройства. Далее i-й настроечный вход устройства сое-, динен с третьим входом i-ro элемента 2-2И2ИЛИ первой группы, а (п+1 )-й настроечный вход устройства соединен с четвертым входом п-го элемента 2-2И-2ИЛИ первой группы. Третий вход k-ro элемента 2-2И-2ИЛИ

1-й группы (к 1. 2 n-l+1; I 2, 3п)

соединен с выходом k-ro элемента 2-2И- 2ИЛИ (1-1 )-й группы, четвертый вход (n-l+2)- го элемента 2-2И-2ЙЛИ (1-1)-й группы соединен с выходом (n-l+2)-ro элемента 2- 2И-2ИЛИ (1-1)-й группы. Выход элемента 2- 2И-2ИЛИ n-й группы соединен с выходом устройства. Четвертый вход (М)-го элемента 2-2И-2ИЛИ первой группы соединен с I-м настроечным входом устройства, четвертый вход s-ro элемента 2-2И-2ИЛИ 1-й группы (s 1. 2 n-l) соединен с выходом

(s+1)-ro элемента 2-2И-2ИЛИ (1-1)-й группы.

Элемент 2-2И-2ИЛИ реализует булеву функцию f ai33 3234, где ан - двоичная

00

переменная, приписанная h-му входу элемента (h 1, 2, 3, 4),

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

Устройство содержит п 5 элементов

2-2И-2ИЛИ первой группы ИIs, n-1 A

элемента 2-2И-2ИЛИ второй группы 2i

24, п-2 3 элемента 2-2И-2ИЛИ третьей группы 3i. За и Зз. п-3 2 элемента 2-2И- 2ИЛИ четвертой группы 4i и 42, один элемент 2-2И-2ИЛИ пятой группы 5, п 5 элементов НЕ 6i65, п 5 информационных входов 7i7s, n+1 6 настроечных

входов 8i8е и выход 9.

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

На информационные входы устройства

подаются двоичные переменные xi хп,

на настроечные входы - компоненты двоич- ного вектора n (F) (no, гипп), определяющего вид реализуемой устройством с.б.ф. п переменных F в соответствии со следующим выражением:

t

F V Hpn , tsO

где Fnl - элементарная с.б.ф. от п переменных с рабочим числом t (t 0, 1п).

На выходе устройства формируется зна- чение с.б.ф. F на данном наборе значений переменных xi, X2хп. Для рассматриваемого примера (п 5) на информационные входы 7i, .... 7s подаются двоичные переменные xiХ5 (в произвольном порядке),

на настроечные входы 8186 - компоненты поП5 двоичного вектора n (F) (п, п,

.... п) реализуемой с.б.ф. F F (xi, X2xs).

На выходе 9 реализуется с.б.ф. F, заданная вектором n (F).

Пример. Найти вектор настройки устройства на реализацию с.б.ф. F F (х i, X2. .... xs). представленной посредством следующей совершенной дизъюнктивной нормальной формы:

F X1X2X3X4X5VxiX2X3X4X5VxiX2X3X4X X1X2X3X4X5&1X2X3X4X$tf 1X2X3X4X5VX1X2X3X4X5.

Двоичный номер N (таблица истинно- сти) заданной функции F имеет вид

N (1110 1000 1000 0000 1000 0000 0000 0001).

Очевидно, что N NI N2 N3, где NL N2. N3 - двоичные номера элементарных с.б.ф. PS . Fg , FS соответственно.

В таком случае n(F) (1,1,0.0,0,1). Следовательно, на настроечные входы 8i, 82, 85 устройства необходимо подать сигнал логической единицы, а на настроечные входы 8з, 84 и 8s - сигнал логического нуля.

Достоинством устройства для вычисления с.б.ф. является простая конструкция. Число элементов 2-2И-2ИЛИ, необходимых для реализации прототипа, составляет

Snp 2n-1.

(1)

В то же время для построения предлагаемого устройства требуется

S

п2 +п

(2)

элементов 2-2И-2ИЛИ.

Затраты оборудования, рассчитанные по формулам (1) и (2), сведены в таблицу.

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

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

n-i+1 элементов, причем i-й информационный вход устройства соединен с входом 1-го элемента НЕ, выход которого соединен с первым входом j-ro элемента 2-2И-2ИЛИ

i-й группы (i 1,2 n-l+1), второй вход

которого соединен с i-м информационным входом устройства, 1-й настроечный вход устройства соединен с третьим входом 1-го элемента 2-2И-2ИЛИ первой группы, (п+1)- й настроечный вход устройства соединен с четвертым входом п-го элемента 2-2И- 2ИЛИ первой группы, третий вход k-ro элемента 2-2И-2ИЛИ 1-й группы (k 1, 2

n-l+1,1 2,3п) соединен с выходом k-ro

элемента 2-2И-2ИЛИ (1-1)-й группы, четвертый вход (п-1+1)-го элемента 2-2И-2ИЛИ (I- 1)-й группы йоединен с выходом (п-1+1)-го элемента 2-2И-2ИЛИ (1-1)-й группы, выход элемента 2-2И-2ИЛИ n-й группы соединен с выходом устройства, отличающееся тем, что, с целью упрощения, четвертый вход (И)-го элемента 2-2И-2ИЛИ первой группы соединен с I-м настроечным входом устройства, четвертый вход s-ro элемента 2-2И-2ИЛИ 1-й группы (s 1, 2n-l) соединен с выходом (s+1)-ro элемента 2-2И- 2ИЛИ (И)-й группы.

Изобретение-относится к вь |числитель- ной технике и микроэлектронике и предназначено для реализации симметрических булевых функций от п аргументов, Цель изо- бретения - упрощение конструкции устройства для вычисления симметрических булевых функций. Поставленная цель достигается тем, что устройство для вычисления симметрических булевых функций от п аргументов содержит п элементов НЕ, п2 +п элементов 2-2И-2ИЛИ. п информационных входов, п+1 настроечных входов и выход. Устройство работает следующим образом. На информационные входы поступают значения двоичных аргументов xi, X2хп, на настроечные входы - сигналы настройки ЛаЛъ... Лп,, значения которых принадлежат множеству { 0.1}. На выходе устройства реализуется симметрическая булева функция F F (XL ), определяемая двоичным вектором настройки jr(F) ( ЛоД1...., ль.) 1 ил., 1 табл. 3 C/V С