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

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

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

Недостатком устройства являются низкие функциональные возможности, а также настройка сигналами на множества {0, 1, xi, XL .... Х4, Х4}, что значительно усложняет организацию электронной настройки.

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

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

XI.- 00 О Ю

XI 00

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

Поставленная цель достигается тем, что в устройство для вычисления фундаментальных симметрических булевых функций, содержащее три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и два мажоритарных элемента, k-й из которых (k 1, 2} имеет порог, равный 2k, причем первый вход 1-го элемента СЛОЖЕНИЕШ МОДУЛЮ ДВА (I - 1-2- 3) соединен с 1-м настроечным входом устройства, j-й информационный вход которого Q 1, 2, ,.., n; n - количество переменных функции) соединен с0 4 1}-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и j-м входом k-ro мажоритарного элемента, выход которого соединен с вторым входом (k + 1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, введены элемент И, р-3 элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (р n/2Q и р-3 мажоритарных элементами из которых (I 3, 4, ,.., р - 1) имеет порог, равный 21, причем m-й настроечный вход (т 4,5,..., р) устройства соединен с первым входом m-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом (т - 1)-г.о мажоритарного элемента, J-й вход которого соединен с j-м информационным входом устройства, выход которого соединен с выходом элемента И, входы которого соединены с выходами всех элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.

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

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

Устройство содержит р п/2 « 4 элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1i,

1г, 1з. 1ч, р -1 3 мажоритарных элемента 2i, 22, 2з, элемент И 3, п 7 информационных входов 4i, ... 4т, р 4 настроечных входов 5t ... 54, выход 6. При этом мажоритарные элементы 2i, 2a, 2з имеют пороги

соответственно два, четыре и шесть.

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

переменные xi... хп (в произвольном порядке); на настроечные входы 5i... 5р - сигналы настройки щ ,,. ир соответственно, значения которых принадлежат множеству {0, 1}. На выходе 6 реализуется некоторая ф.с.б.ф.

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

Известно, что произвольная симметричная булева функция n переменных F F(xi, X2, ..., хп) может быть взаимно-однозначке представлена (п + 1)- разрядным двоичным кодом n(F)- (п0, ni, ..., пп), где пв-значёние F на (любом) наборе переменных xi, X2, ..., Хп. содержащем ровно s единиц (0 s :Ј п) . Для ф.с.б.ф. Р П двоичный

код n(F n) имеет только одну единичную компоненту, а именно, щ 1. Другими словами, имеет место

35 F n(xi.x2.....xn)1, если xi+x2+... О-в противном случае.

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

F(X1,X2, ..., ХП, U1.U2, ..., 11р) (и1Фх1фх2ф ...

л- 1 фхп)& Л(М Фи ),

К -I 2k -k +1

где р - п/2 {и функция n-входового мажори- тарного элемента с порогом s (0 s п) определяется следующим образом:

11, если xi+x2+,..+xn5:s; О-в противном случае.

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

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

(п + 3).-1.(1)

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

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

устройства s, вычисленная по формуле (1) при п 5. совпадает со сложностью устройства-прототипа и равна 23.

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

Формула изобретения Устройство для вычисления фундаментальных симметрических булевых функций, содержащее три элемента СЛОЖЕНИЕ ПО МОДУЛ Ю ДВА и два мажоритарных элемента, К-й из которых (к 1, 2) имеет порог, равный 2k, причем первый вход 1-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (I - ТГз) соединен с -м настроечным входом устройства, информационный вход которого 0 I- n- n количество переменных функций) соединен с (j + 1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и j-м входом К-го мажоритарного элемента, выход которого соединен с вторым входом (k + 1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, отличающееся тем, что, с целью расширения функциональных возТаблица настроек устройства для вычисления ф.с.б.ф. при п 7

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

-3 элементу

(р (Р Г ) ) и Р 3 мажоритарных

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