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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (з1) 6 06 F 7/00

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4941765/24 (22) 03,06.91 (46) 15.08.93. Бюл, N 30 (72) Л.Б.Авгуль, В.П.Супрун, Н.А.Егоров и

В.И. Гри шанович (56) Авторское свидетельство СССР М 1559337, кл. G 06 F 7/00, 1988.

Лухальский Г,И., Новосельцева Т.Я. . Проектирование дискретных устройств на интегральных схемах. Справочник. M,: Радио и связь, 1990, с. 105, рис. 310. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации симметриИзобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации симметрических булевых функций (с.б.ф.) п переменных, Цель изобретения — упрощение устройства для вычисления симметрических булевых функций.

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

Выход мультиплексора соединен с выходом устройства, а i-й (i - 1, 2, ..., n) вход данных соединен с l-м настроечным входом устройства. Причем, j-й (j 1, 2, ..., n - 1) вход сумматора соединен с j-м информационным входом устройства, а 1-й (l - 1, 2, .... k; k =

„„Я2„, 1833860 А1 ческих булевых функций (с.б.ф.) и переменных. Цель изобретения — упрощение устройства для вычисления с.б,ф. Поставленная цель достигается тем, что устройство для вычисления с.б.ф. и переменных содержит (и - 1)-входовый одноразрядный сумматор и

2 -канальный мультиплексор, где k = )togznf.

Устройство работает следующим образом.

На информационные входы устройства поступают двоичные переменные x1, .„, хп -1(в произвольном порядке), на настроечные входы — сигналы настройки u1, ... un, значения которых принадлежат множеству (О, 1, х, х }. На выходе реализуется некоторая с.б.ф. и переменных F = F(x1, х2, ..., хл), определяемая вектором настройки U = (u1, о2, ..., u ). 1 ил.

=)logan() выход соединен с I-м адресным входом мультиплексора.

° еееЬ

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

Устройство для вычисления с.б.ф. и пе- (р ременных содержит (п - 1)-входовый одно- 0р разрядный сумматор 1 (ЯМп-1), мультиплексор 2 (МОХ), n - 1 информационных входов 31 ... 3n-1i п настроечных входов 41 ... 4п, выход 5.

Сумматор 1 обеспечивает подсчет числа единиц, содержащихся во входном инфор- и мационном слове Х = (х1, х2, ... х -1), На входы

31 ... 3>-1 поступают двоичные переменные х1, xz, ..., хд-1 (в произвольном порядке), на

k - )logan(выходах сумматора реализуются соответственно функции fo = 1„(х1, хг, ..., xn-1) ...

fk-1- fk-1(х1. ха, ..., хп-1), составляющие позиционный двоичный код числа единиц в сло1833860

Поясним алгоритм настройки. Пусть и!— значение с,б,ф. F на (любом) наборе пере45

МЕННЫХ Х1, Х2, ..., Хв, СОДЕРжаЩЕМ РОВНО логических единиц(0 t и), т.е, F(x1, х2, ..., Xn) = !lt тОГДа И ТОЛЬКО тОГДа, КОГДа Х1+ Х2+

+ ... + Хв = t. При этом функция F однозначно задается (и+1)-разрядным двоичным кодом

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

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

UI = Ill-1 Xn. nl Xn (1) где u=1, 2,. „п, 55

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

ВЕ Х = (X1, X2 „., Xn-1), т.Е. X1+ X2+ ... + Xn-1 =

fp + 211 + 4f2 + ... + 2 fk-1. k- 1

Выход сумматора 1, на котором реализуется булева функция fi-1 (1 = 1, 2...„k), соединен с адресным входом мультиплексора 1, имеющим вес 2, что и показано на . чертеже.

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

Мультиплексор 2 имеет k =)! оц2п(адресных входов и 2 входов данных. Однако в

/ заявляемом устройстве для вычисления с.б.ф. п.переменных используются только первые п 2 входов данных мультиплексора, которые соединены с настроечными входами 41, .", 4п устройства {остальные входы данных мультиплексора на чертеже не показаны).

Следовательно, I-A (I = 1, 2, ..., n) настроечный вход 4I устройства (I-й вход данных мультиплексора 2 — вход с номером 1- 1) 25 будет подключен к выходу 5 устройства (вы ходу мультиплексора 2), если на адресных входах мультиплексора двоичный код равен

i 1, или (что тоже самое) на входах 3 1, ..., Зв-1 сумматора 1 присутствует ровно i - 1 логиче- 30 ских единиц.

Устройство для вычисления с.б.ф. работает следующим образом. На информационные входы 31, .„, 3П-! устройства поступают двоичные переменные x1, „., xn-! (в произ- 35 вольном порядке), на настроечные входы

41, ..., 4П вЂ” сигналы настройки U! ... un, соответственно, значения которых принадлежат множеству (О, 1, xn, xn). На выходе 5 реализуется некоторая с.б,ф. и переменных F = 40

=F(X1, X2 ..., Xn), ОПрЕдЕЛяЕМая ВЕКтОрОМ На

СтРОйКИ U = (U1, U2, ..., Un).

F(x1, х2,;... хб) = х! х2 х3 х4 x5 v

Х1 Х2 ХЗ Х4 XGV К! Х2 ХЗ Х5 Хб ч х1 х2 х4 х5 хб 1 х1 хз х4 х5 хб 4 х2 хз х4 х5 хб 3 х! х2 хз х4 х5 хб.

Очевидно, что здесь n(F) =(1, 1, О, О, О, О, 1). Отсюда с учетом (1) получаем u1 = 1, U2 =

= хб, U3 = 04 = v5 = О и 06 = хб. Таким образом, имеем О = (1, хб, О, О, О, x6). Следовательно, на настроечные входы устройства 41, 42, 4з, 44, 46 и 46 должны быть поданы сигналы настройки соответственно 1, хб, О, О, О и х6 (на информационные входы 31, 32, Зз, 34 и 36 подаются двоичные переменные х1, х2, хз, х4 и хб в произвольном порядке).

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

Оценка сложности прототипа (2" — канальный мультиплексор) составляет Snp.=O {n 2"), в то время как заявляемое устройство имеет сложность, оцениваемую веЛИЧИНОЙ Язаявл, = 0(П !ОЯ2П). ПРИ ЭТОМ известные устройства для вычисления с.б.ф. и переменных имеют оценку сложности вида S 38. = 0(п2).

Быстродействие заявляемого устройства практически не зависит от и и определяется глубиной схемы сумматора (2 ту известных схем многовходовых одноразрядных сумматоров) и мультиплексора (3 t y классического мультиплексора). Вместе с тем известные устройства для вычисления с,б,ф. имеют оценку быстродействия, определяемую глубиной схемы, равную Тизв. = О (и), Кроме того, для своей реализации предлагаемое устройство требует использование стандартных элементов, входящих в состав большинства серий интегральных микросхем средней степени интеграции (мультиплексоры, многовходовые одноразрядные сумматоры). В то же время известные устройства для вычисления с.б,ф. для своей практической реализации требуют или разработки заказных схем, или использование схем малой степени интеграции (элементы И-Н Е, ИЛИ-Н Е, ИСКЛ ЮЧАЮЩЕ Е ИЛИ и др,). В первом случае необходимы значительные материальные затраты для разработки заказных схем, а во втором — устройство будет иметь довольно-таки высокую конструктивную сложность (по числу корпусов микросхем).

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

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

1833860

Составитель Л.Авгуль

Техред M.Ìîðãåíòàë Корректор M.Têà÷

Редактор

Заказ 2686 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС

СР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент, г. Ужгород, ул.Гагарина, 101 которого (l = 1, и; и — количество переменных) соединен с 1-м входом данных мультиплексора, о т л и ч а ю ще е с я тем, что, с целью упрощения при реализации симмет- . рических булевых функций, оно содержит и - 5

1-входовый одноразрядный сумматор, )-й вход которого 0 - Г; п=1т соединен с I м информационным входом устройства, I-й выход сумматора (i - 1, k; k -)og2nP соединен с l-м адресным входом мультиплексора.