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

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

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

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

Устройство содержит п 5 элементов U 1 ,..., первой группы, п 5 элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2 20...,25 первой группы, п - 1 4

элемента U 3«, второй группы, п-1 4 элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 4...,44. второй группы, п-2 3 элемента U 5,,53 третьей группы, п-2 3 элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 6,...,6з третьей группы, п - 3 2 элемента и 7 и 7г четвертой группы, п-3 2 элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 8, и 82 четвертой группы, п-4 1 элемент U 9 пятой группы, п-4 1 элемент СЛОЖЕНИЕ ПО МОДУЛЮ 2 10 пятой группы, п 5 информационных входов 11,),..., 115-, п+1 6 настроечных входов 12 ,,...,126, выход 13.

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

5 ел

to

00 Од

На информационные входы 11,,..., П5 поступают двоичные переменные Х4,..., Xg соответственно, на настроечные входы 120...126- сигналы настройки У„ ,..., у, соответственно, значения которых принадлежат множеству 0,1). На выходе 13 реализуется с.б.ф. F F (X0X2,X3,X4,X5), определяемая вектором настройки J1 (F)($0, Jf, , $г,

У} 0 fl 5 t

Пусть с.б.ф. F существенно зависит от rij аргументов Х0Х, ...,Xh и а 4, ад, ... ,а г - рабочие числа

1 только в том случае, когда все слагаемые ранга i входят в полином Жегалкина данной с.б.ф. F(0 & i п). Компоненты вектора у (F) и являются соответствующими сигналами настройки устройства для вычисления с.б.ф. п переменных.

Таким образом, можно выделить сле- Ю дующие этапы нахождения вектора настройки jf (F) устройства на реализацию заданной с.б.ф. F F (X ,Х,... ,Xn) .

Определяется множество э.с.б.ф., подразрядная дизъюнкция двоичных ноF. где 1 п+1, такую с.б.ф. обоз-15меров которых дает двоичный номер

начим через Fa jO7,..o ч ЕСЛИ г 1,(таблицу истинности) заданной функции. то с.б.ф. F называется элементар-По виду найденных, с.б.ф. формируной /или фундаментальной) с.б.ф.Про-ется вектор 1T(F) (и0 ,,... ,ch) . извольная с.б.ф. F F (Х4,Ха, .. . ,Xh) Вектор н (Р) преобразуется в вектор может быть задана двоичным вектором 20 настройки )f(F). (кодом) it (F) (оЛ s ) где

/.

- значение F на (любом) наборе

И ф и м е р. Найти вектор настройки X(F) устройства () на реализа- .б.ф. (X,X,X,,X4JX5) Х,ХгХ3(Х1Х/гХ3УХ,Х2ХэУХ(ХгХз)(Х4УХ5)У

значений п аргументов с i единицами (0 Ј i Ј п) . Очевидно, что 1 только тогда, когда iЈ Ја,, а,.. а у,) и F 0 F° V,F;v...v7nFj;.

Следовательно, определение вектора 7 (F) Со

о i

п) некоторой

с.б.m. F сводится к нахождению таких э.с.б.ф., поразрядная дизъюнкция дво ичных номеров которых дает двоичный номер исходной функции.

С.б.ф. F можно представить посредством (n-М) -разрядного двоичного

вектора jf (F)-( f, , У,,. ,/fn) r«e У.1

1 только в том случае, когда все слагаемые ранга i входят в полином Жегалкина данной с.б.ф. F(0 & i п). Компоненты вектора у (F) и являются соответствующими сигналами настройки устройства для вычисления с.б.ф. п переменных.

Таким образом, можно выделить сле- дующие этапы нахождения вектора настройки jf (F) устройства на реализацию заданной с.б.ф. F F (X ,Х,... ,Xn) .

Определяется множество э.с.б.ф., подразрядная дизъюнкция двоичных но

И ф и м е р. Найти вектор настройки X(F) устройства () на реализа- .б.ф. (X,X,X,,X4JX5) Х,ХгХ3(Х1Х/гХ3УХ,Х2ХэУХ(ХгХз)(Х4УХ5)У

V lUXiV ХД4Х3 Х,Х1Х3) (X4Xf X4X5)V MX,)dX5(X+X5VXaX5).

можно представить в виде

С.б.ф. F

F(X0X1,X,,X,X5)/iroF|v «, V F F vf5F|.

Причем двоичные номера, э.с.б.ф. для 5 имеют следующее представле

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

на настроечные входы - сигналы настройки γ₀,γ₁,...,γ_N, значения которых принадлежат множеству {0,1}, на выходе устройства реализуется симметрическая булевая функция F=F(X₁,X₂,...,X_N), определяемая вектором настройки F_(F)(^г₀,γ₁,...,γ_N). 1 ил.

-N5 (1000 0000 0000 0000 utTOO 0000 0000 0000);

-N5-(0110 1000 1000 0000 1000 0000 0000 0000);

(0001 0110 0110 1000 0110 1000 1000 0000);

(0000 0001 0001 0110 0001 0110 0110 1000);

(0000 0000 0000 0001 0000 0001 0001 0110); (0000 0000 0000 0000 0000 0000 0000 0001).

Двоичный номер заданной с.б.ф.цимеет вид

Np (1111 1110 1110 1001 1110 1001 1001 0110).

Очевидно, что

NF NsN Nir V иЈ V Nj;

F F V F v F| V F4

Тогда fr(F) (1,1,1,0,1,0).

Используя метод треугольника В.П. Супруна, преобразуем в код 7(F) в вектор настройки jj1 (F) .

Отсюда получаем (F) (1,0,0,1, 0,1).

Следовательно, сигналы логической 50 единицы должны быть поданы на первый 12,, четвертый 124 и шестой 12б настроечные входы устройства, а сигналы

логического нуля - на второй тий 12.J и пятый 12,

Формула из

Ч

тренастроечные входы, обретен ия

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

15593

п групп (п - количество аргументов реализуемых логических функций) элементов И, 1-я из которых содержит n-i+1 элементов (,п), о т л и ч аг ю щ е е с я тем, что, с целью упрощения устройство содержит п групп элементов сложения по модулю два, i-я из которых содержит n-i+1 элементов, причем 1-Й Информационный ВХОД УСТРОЙСТ- JQ

ва соединен с первым входом .1-го элемента И i-й группы (, n-i+1), выход которого соединен с первым входом JTO элемента сложения по модулю два i-й группы, первый настроечный вход 15 устройства соединение вторым входом первого элемента И первой группы, - 1-й настроечный вход (,п) устройст1559337

реаглеизриТ- JQ

ва соединен с вторым входом 1-го элемента И первой группы и вторым входой (1-1)-го элемента сложения по модулю два первой группы, (п+1)-й построечный вход устройства соединен с вторым входом n-го элемента сложения по модулю два первой группы, выход m-го элемента сложения по модулю два k-й группы (, n-R,К«1,п-1) соединен с вторым входом m-го элемента И (k+1)-tf группы, второй вход t-ro элемента сло- жения по модулю два 1-й группы (t 1, п-1+1) соединен с выходом (t+1)- го- лемента сложения по модулю два (1-1)-и группы, выход элемента сложения по модулю два n-й группы соединен с выходом устройства.

tbS