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

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

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

Устройство для вычисления симметрических булевых функций содержит мультиплексор и (п - 1}-входовый одноразрядный сумматор (п - количество аргументов реализуемых симметрических булевых функций). Выход мультиплексора соединен с выходом устройства, а 1-й (I 1,2, ..., п) вход данных соединен с l-м настроечным входом устройства. Причем, j-й 0 1. 2 п - 1) вход

сумматора соединен с j-м информационным входом устройства, а 1-й (I 1, 2k; k

1од2п) выход соединен с l-м адресным входом мультиплексора.

На чертеже представлена схема предлагаемого устройства.

Устройство для вычисления с.б.ф. п переменных содержит (п - 1)-входовый одноразрядный сумматор 1 (SMn-i), мультиплексор 2 (MUX), п -1 информационных входов 3i... Зп-1, п настроечных входов 4i... 4П, выход 5.

Сумматор 1 обеспечивает подсчет числа единиц, содержащихся во входном информационном слове X (xi,X2,... xn-i). На входы 3i ... Зп-1 поступают двоичные переменные

XL X2хп-1 (в произвольном порядке), на

k jloganf выходах сумматора реализуются

соответственно функции f0 f0 (xi, X2xn-i) ...

fk-i fk-i(xi, X2xn-i), составляющие позиционный двоичный код числа единиц в ело00 00 00 00

о о

ве X (xi, Х2xn-i), т.е. xi ха + ... + xn-i

-fo + 2fi+.4f2 + -... + 2k 1fk-l.

Выход сумматора 1, на котором реализуется булева функция fi-1 (I 1, 2к),

соединен с адресным входом мультиплексора 1, имеющим вес 21 , что и показано на чертеже.

Схемы n-входовых одноразрядных сумматоров достаточно хорошо изучены. Причем оценка их сложности SsMn 0(n logan), a быстродействие практически не зависит от п и равно 2 т или 3 г, где г - задержка на вентиль.

Мультиплексор 2 имеет k log2n адресных входов и 2 входов данных. Однако в заявляемом устройстве для вычисления с.б.ф. п -переменных используются только первые п 2k входов данных мультиплексора, которые соединены с настроечными входами 4i, ..., 4П устройства (остальные входы данных мультиплексора на чертеже не показаны).

Следовательно, 1-й (1 1,2,..., п) настроечный вход 4| устройства (1-й вход данных мультиплексора 2 - вход с номером I - 1) будет подключен к выходу 5 устройства (выходу мультиплексора 2), если на адресных входах мультиплексора двоичный код равен 1-1, или (что тоже самое) на входах 31,..., Зп-1 сумматора 1 присутствует ровно | - 1 логических единиц.

Устройство для вычисления с.б.ф. работает следующим образом. На информационные входы 3i,..., Зп-1 устройства поступают двоичные переменные xiхп-1 (в произвольном порядке), на настроечные входы 4i,..,, 4П - сигналы настройки ui ... Un, соответственно, значения которых принадлежат множеству {0, 1, хп, хп}. На выходе 5 реализуется некоторая с.б.ф. п переменных F

F(xi, X2хп), определяемая вектором н астройки U (ui, U2, ..., Un).

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

логических единиц(0 t n), т.е. F(xi, X2,..., хп) nt тогда и только тогда, когда xi + Х2 + + ... + xn t. При этом функция F однозначно задается (п +1)-разрядным двоичным кодом

n(F) (rio, niпп). Тогда сигнал настройки

ul на i-м настроечном входе 4| устройства равен

UI ПМ Хп . П|ХП,(1)

где и 1, 2, ..., п.

Пример. Найти вектор настройки U устройства на реализацию следующей с.б.ф. от шести переменных:

F(X1, Х2, ..., Хб) Х1 Х2 ХЗ Х4 Х5 Х1 Х2 ХЗ Х4 X6v XI Х2 ХЗ Х5 Хб ч Х1 Х2 Х4 Х5 Х6 N) Х1 ХЗ Х4 Х5 Х6 V Х2 ХЗ Х4 Х5 Х6 V Х1 Х2 ХЗ Х4 Х5 Хб.

Очевидно, что здесь n(F) (1, 1,0, О, О, О,

1). Отсюда с учетом (1) получаем щ 1, иа Хб, из U4 us 0 и ue Хб. Таким образом, имеем U (1, хе, О, О, О, хе). Следовательно, на настроечные входы устройства 4i, 42, 4з,

0 44, 4s и 4б должны быть поданы сигналы настройки соответственно 1, хе, О, О, О и хб (на информационные входы 3i, 32, Зз, 34 и 3s подаются двоичные переменные xi,x2, хз, Х4 и Х5 в произвольном .порядке).

5 Достоинством заявляемого устройства является простая конструкция, высокое быстродействие, использование в своем составе стандартных элементов (мультиплексор и многовходовый одноразрядный сумматор).

0 Оценка сложности прототипа (2П - канальный мультиплексор) составляет Snp. 0 (п 2П), в то время как заявляемое устройство имеет сложность, оцениваемую величиной Ззаявл. 6(п logzn). При этом

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

Быстродействие заявляемого устройства практически не зависит от п и определя0 ется глубиной схемы сумматора (2 ту известных схем многовходовых одноразрядных сумматоров) и мультиплексора (Згу классического мультиплексора). Вместе с тем известные устройства для вычисления с.б.ф.

5 имеют оценку быстродействия, определяемую глубиной схемы, равную ТИзв. 0 (п).

Кроме того, для своей реализации предлагаемое устройство требует использование стандартных элементов, входящих в

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

5 своей практической реализации требуют или разработки заказных схем, или использование схем малой степени интеграции (элементы И-НЕ, ИЛИ-НЕ, ИСКЛЮЧАЮЩЕЕ ИЛ И и др.). В первом случае необходи0

мы значительные материальные затраты

. для разработки заказных схем, а во втором - устройство будет иметь довольно-таки высокую конструктивную сложность {по числу корпусов микросхем). 5 Формула изобретения

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

которого (I 1, п; п - количество переменных) соединен с 1-м входом данных мультиплексора, отличающееся тем, что, с целью упрощения при реализации симметрических булевых функций, оно содержит п 1-входовый одноразрядный сумматор, J-й вход которого 0 t, п - 1) соединен с J-м информационным входом устройства, 1-й выход сумматора (I « 1, k; k - log2nD соединен с l-м адресным входом мультиплексора.

Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации симметрических булевых функций (с.б.ф.) п переменных. Цель изобретения - упрощение устройства для вычисления с.б.ф. Поставленная цель достигается тем, что устройство для вычисления с.б.ф. п переменных содержит (п - 1)-входовый одноразрядный сумматор и -канальный мультиплексор, где к fog2n. Устройство работает следующим образом. На информационные входы устройства поступают двоичные переменные xi,.... хп- 1(в произвольном порядке), на настроечные входы - сигналы настройки щ, ... ип, значения которых принадлежат множеству {0, 1, хп. Хп}. На выходе реализуется некоторая с.б.ф. п переменных F F(xi, X2,..., хп), определяемая вектором настройки U (ui, 112 un). 1 ил. & Ј