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

 

Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления фундаментальных (элементарных) симметрических булевых функций. Цель изобретения - расширение функциональных возможностей за счет реализации фундаментальных симметрических булевых функций п переменных. Поставленная цель достигается тем, что устройство для вычисления фундаментальных симметричных булевых функций п переменных содержит Р(Р n/2Q элементов сложение по модулю 2, Р - 1 мажоритарных элементов, К-й(К 1,2,..,, Р -1) из которых имеет порог, равный 2К, элемент И, п информационных входов, Р настроечных входов и один выход. Сложность устройства по числу входов логических элементов равна -л- (п + 3) - 1. На информационные входы поступают двоичные переменные хь ... хп (в произвольном порядке); на настроечные входы -сигналы настройки Ui... Up, значения которых принадлежат множеству {0, 1}; на выходе устройства реализуется фундаментальная симметрическая булевая функция F F(xi, Х2, .... Хп), определяемая вектором настройки U (Ui, U2. .... Up). 1 ил„ 1 табл. СО С

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

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

РЕСПУБЛИК г (я)я G 06 F 7/00

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

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4829130/24 (22) 29.05.90 (46) 23,01,93. Бюл, ¹ 3 (72) Л,Б.Авгуль, В.П.Супрун, Э,Г.Лазаревич и Ю.Э,Лазаревич (56) Авторское свидетельство СССР

¹ 1396137, кл, G 06 F 7/00, 1987.

Авторское свидетельство СССР

¹ 1730616, кл. G 06 F 7/00, 1990. (54) УСТРОЙСТВО ДЛЯ ВЪ|ЧИСЛЕНИЯ

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

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

Известно устройство для вычисления ф,с.б,ф. четырех переменных, содержащее два элемента СЛОЖЕНИЕ ПО МОДУЛЮ

ДВА, элемент РАВ,103НАЧHOCTb, элемент ИЛИ-HE и элемент И (1), Недостатком устройства являются низкие функциональные возможности, а также настройка сигналами на множества (О, 1, х1, x>..... х4. х4}, что значительно усложняет организацию электронной настройки, „„SU„„1789978 А1 для вычисления фундаментальных симметричных булевых функций и переменных содержит Р(Р = )n/2() элементов "сложение по модулю 2", P - 1 мажоритарных элементов, К-й (К = 1, 2, . „Р - 1) из которых имеет порог, равный 2К, элемент И, и информационных входов, Р настроечных входов и один выход:

Сложность устройства по числ входов логических элементов равна -2- (и + 3) - 1. На и информационные входы поступают двоичные переменные x>, ... x> (в произвольном порядке); на настроечные входы.— сигналы настройки U> „. Up. значения которых принадлежат множеству {О, 1); на выходе устройства реализуется фундаментальная симметрическая булевая функция F = F(xt, x2, ..., хл), определяемая вектором настройки U = (U>, 02...., ОР). 1 ил., 1 табл.

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

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, элемент

ИЛИ-НЕ, пять информационных входов, три настроечных входа и выход (2).

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

10

Цель изобретения — повышение функциональных возможностей устройства за счет реализации ф.с.б,ф, и переменных, Поставленная цель достигается тем, что в устройство для вычисления фундаментальнмх симметрических булевых функций, содержащее три элемента СЛОЖЕНИЕ ПО

МОДУЛЮ ДВА и два мажоритарных элемента, k-й из которых (k = 1, 2) имеет порог, равный 2k, причем первый вход i-го элеменte СЛОЖЕНИЕПО МОДУЛЮ ДВА(i = 1-2-3) соединен с 1-м настроечным входом устройства, )-й информационный вход которого (j = 1, 2, ..., n; и — количество. переменных функции) соединен с(j+1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и

j-м входом k-ro мажоритарного элемента, выход которого соединен с вторым входом (k+ 1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, введены элемент И, р-3 элемента

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (р = )п/2() и р-3 мажоритарных элемента,1-й из которых (l = 3, 4...;, р - 1) имеет nopor, равный 21, причем m-й настроечный вход (rn = 4, 5, „„р) устройства соединен с первым входом m-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом (m - 1)-ro мажоритарного элемента, j-й вход которого соединен с )-м информационным входом устройства, выход которого соединен с выходом элемента И, входы которого соединены с выходами всех элементов

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.

Устройство для вычисления фундаментальных симметрических булевых функций п переменных содержит р =)n/2(элементов

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р - 1 мажо) ритарных элементов и элемент И, Причем

t-й мажоритарный элемент (t = 1, 2...„р - 1) имеет порог, равный 2t, а первый вход i-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (1

= 1, 2, 3) соединен с i-M настроечным входом устройства, j-й информационный вход которого() = 1, 2...„n) соединен с О+ 1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и j-м входом k-ro мажоритарного элемента (k = 1, 2). Выход k-ro мажоритарного элемента соединен с вторым входом (k + 1)-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, à m-й настроечный вход (m = 4, 5, ..., р) устройства сбединен с первым входом

m-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ

ДВА, второй вход которого соединен с выходом (m -1)-го мажоритарного элемента, j-й вход которого соединен с j-м информационным входом устройства. Выход устройства соединен с выходом элемента И, входы которого соединены с выходами всех элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.

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

Устройство содержит р = )n/2(4 элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 11, 12, 1з, 14, p - 1 = 3 мажоритарных элемента

21, 22, 2з, элемент И 3, n = 7 информационных входов 41..., 47, р =- 4 настроечных входов 51 „, 54. выход 6. При этом мажоритарные элементы 21, 22, 2з имеют пороги соответственно два, четыре и шесть.

Устройство для вычисления ф.с.б.ф. работает следующим образом, На информационные входы 41 „, 4п поступают двоичные

ПЕРЕМЕННЫЕ Х1.„Xn(В ПРОИЗВОЛЬНОМ ПОРЯД-. ке); на настроечные входы 51 „. 5p — сигналы настройки u1 „. up соответственно, значения которых принадлежат множеству {О, 1}. На выходе 6 реализуется некоторая ф.с.б.ф.

Fn = Fn (X1. X2 „., Xn) ОПРЕДЕЛЯЕМаЯ ВЕКтОI ром настройки U = (u1, 02...., 01,), Известно; что произвольная симметричная булева функция и переменных F =

=F(X1, X2, ..., Хл) МОжЕт бЫтЬ ВЗаИМНО-ОДНОзначно представлена (и + 1)- разрядным двоичным кодом n(F) - (и,, п1, ..., и,), где

n< — значение F на(любом) наборе переменНЫХ Х1, Х2, ..., Xn, СОДЕРжаЩЕМ РОВНО S ЕДИниц (О s n) >. Для ф.с,б.ф. F < двоичный код n(F л) имеет только одну единичную

i компсненту, а именно. nI =- 1. Другими словами, имеет место

1, если х1+х2+.„+хп=1;

F р(Х1, X2, ..., Xn) =

Π— в противном случае.

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

F(X1. X2 ", Хл 01 02. " Up) = (01 9Х1 9Х29 г — 1

9хп) 8 A(M ®u ), к =1 2к ++1 где р = )n/2(и функция и-входовогомажори-тарного элемента с порогом s (О s п) определяется следующим образом:

1. ЕСЛИ Xt+x2+...+Xn+S;

Мв(Х1, Х2, .„, Xn)

0 — в противном случае.

В таблице представлены настройки устройства на реализацию ф,с.б,ф, при и = 7.

Отметим, что сложность устройства s no числу входов логических элементов может быть рассчитана по формуле

s - )n(2((n + 3) - 1, (1)

Достоинством устройства являются широкие функциональные возможности, так как его применение позволяет вычислять и+ 1 ф.с.б.ф., зависящих от п переменных.

1789978

Таблица настроек устройства для вычисления ф.с.б.ф. при n = 7

В то время, как устройство-прототип ориентировано на вычисление только 6 ф.с.б.ф. пяти переменных. Кроме того, сложность

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

Устройство для вычисления фундаментальных симметрических булевых функций, содержащее три элемента СЛОЖЕНИЕ ПО

МОДУЛЮ ДВА и два мажоритарных элемента. К-й из которых (k = 1, 2) имеет порог, равный 2k, причем первый вход i-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (i = Т, 3}) соединен с i-м настроечным входом устроиства, и информационный вход которого (J = 1, „. n,.n — количество переменных функций) соединен с (J + 1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и

j-м входом K-ro мажоритарного элемента, выход которого соединен с вторым входом (k + 1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэустройства s, вычисленная по формуле (1) при п =- 5, совпадает со сложностью устройства-прототипа и равна 23. можностей за счет реализации фундаментальных симметрических булевых функций ппеременных,,в него введены элемент И, р

-3 элемент СЛ ЖЕНИЕ ПО МОДУЛЮ ДВА

ll (р - (р = -ж- ) ) и р - 3 мажоритарных элемента, -й из которых (! = 3, р - 1) имеет порог, равные 2l, причем m-й настроечный вход (m = 4.р) устройства соединен с первым входом m-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом (m -1)-го мажоритарного элемента, J-й вход которого соединен с J-м информационным входом устройства, выход которого соединен с выходом элемента И. входы которого соединены с выходами всех элементов СЛОЖЕНИЕ ПО МОДУЛЮ

ДВА.

1789978

Составитель В, Супрун

Техред M.Ìoðãåíòàë

Редактор Т. Шагова

Корректор H. Король

П оизводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 101

pÎè в

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

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

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