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

(Л

С

Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении матричных арифметических устройств. Цель изобретения - упрощение устройства при реализации фундаментальных симметрических булевых функций. Поставленная цель достигается тем, что устройство для вычисления фундаментальных симметрических булевых функций содержит п (п - количество переменных реализуемых функций и ) элементов НЕ, п-1 группу элементов И, каждая из которых содержит два элемента И, г+1 линеек элементов И, г линеек элементов ИЛИ, п входов и п+1 выходов. Сложность устройства по числу входов логических элементов составляет. S 3n2+2n-4 Устройство работает следующим образом На входы устройства поступают двоичные переменные xi xn (в произвольном порядке), а на его выходах реализуются фундаментальные симметрических булев е функции Fn°...Fnn. 1 ил.

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

Известен многофункциональный логический модуль, содержащий три элемента РАВНОЗНАЧНОСТЬ и два элемента И. Модуль реализует все булевы функции двух переменных и имеет четыре выхода, на которых формируются одновременно значения четырех функций.

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

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

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

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

Устройство для вычисления симметрических булевых функций содержит п (п - количество переменных реализуемых функций и , где ,2,3,..) элементов НЕ, п-1 группу элементов И, i-я (,2, .,п-1) из которых содержит два элемента И, г+1 линейку элементов И и г линеек элементов ИЛИ. Вход v-ro (,2п) элемента НЕ соединен с v-ым входом устройства, j-я (,2,.,,,r) линейка элементов И содержит 4j-2 элементов И,(г+1)-я линейка элементов

д М

Јь

00

ел о

И содержит п-1 элементов И, j-я линейка элементов ИЛИ содержит 4J элементов ИЛИ. Выход ()-й группы и первым входом 2i-ro (,22j-1) элемента И j-й линейки элементов И, вход (2j-1)-ro элемента НЕ соединен с первым входом второго элемента И ()-й группы и первым входом (2t-1)-ro элемента И j-й линейки элементов И. Выход 2j-ro элемента НЕ соединен с первым входом первого элемента И группы и первым входом (2s-1)-ro (,22j) элемента ИЛИ j-й линейки элементов ИЛИ, вход 2j-ro элемента НЕ соединен с первым входом второго элемента И 2J-U группы и первым входом 2s-ro элемента ИЛИ j-й линейки элементов ИЛИ, Выход n-го элемента НЕ соединен с вторым входом первого элемента И первой группы и вторым входом первого элемента И первой линейки элементов И, а вход n-го элемента НЕ соединен с вторым входом второго элемента И первой группы и вторым входом второго элемента и первой линейки элементов И. Выход k-ro (,2) элемента И (2j-1-)-n группы соединен со вторым входом k-ro элемента И группы и вторым входом (4j(k-1)-k+2)-ro элемента ИЛИ J-й линейки элементов ИЛИ. Выход k-ro элемента И 21-й (,2,...,г-1) группы соединен со вторым входом k-ro элемента И (21+1)-й группы и вторым входом (4l(k-1)+k)- го элемента И (1+1)-й линейки элементов И. Выход (2t-2+k)-ro элемента И j-й линейки элементов И соединен с (k+1)-M входом (2t- 1+р)-го (,2) элемента ИЛИ j-й линейки элементов- ИЛИ. Выход (2w-2+k)-ro (,22) элемента ИЛИ 1-й линейки элементов ИЛИ соединен с (k+1)-biM входом (2w-1+p)-ro элемента И (1+1)-й линейки элементов И. Выход k-ro элемента И (п-1)-й группы соединен с (п(к-1)+1)-ым выходом устройства, (1+1 )-й выход которого соединен с выходом 1-го элемента И (г+1)-й линейки элементов И, k-й вход которого соединен с выходом (2l+k-2)-ro элемента ИЛИ r-й линейки элементов ИЛИ.

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

Устройство содержит элементов НЕ 1i...1s, два элемента И первой группы 2i и 22, два элемента И второй группы 3i и За, два элемента И третьей группы 4т и 42, два элемента И четвертой группы 5i и 5а, два элемента И первой линейки элементов И 6i и 6з, шесть элементов И второй линейки элементов И 7i..,7е, четыре элемента И третьей линейки элементов И 8i..,84, четыре элемента ИЛИ первой линейки элементов ИЛИ 9f ...9, восемь элементов ИЛИ второй линейки элементов ИЛИ 101...10в, входов 111...11б, выходов 12i...12e.

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

На входы 111...11g устройства подаются

двоичные переменные xi,..xs (в произвольном порядке), на выходах 12i.. 12е реализуются фундаментальные с.б.ф. Fs ...Fs соответственно.

Отметим, что фундаментальная с.б.ф, п

переменных Fnm Fnm(xi,x2xn) принимает

значение логической единицы на тех и только тех наборах переменных XL X2,...xn, которые содержат ровно m единиц (,1,...n),

т.е.s

(1, если Х1+х2+...+хп гп;

РгТ(Х1,Х2ХпН

/О-в противном случае

Для четного значения п в устройстве, построенном для нечетного п, достаточно на вход элемента НЕ первой (или последней) линейки подать константу логический ноль. В результате этого устройство для

нечетного преобразуется в устройство для четного .

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

применения.

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

S 3n2 + 2n-4,(1)

а-сложность устройства-прототипа определяется соотношением 5пр Зп2 + 2п + 2.

(2)

Результаты расчетов по формулам (1) и (2) свидетельствуют о преимуществе пред0 лагаемого устройства перед прототипом. Кроме того, одновременное формирование на выходах устройства всех фундаментальных с.б.ф. п переменных расширяет область возможного применения устройства (напри5 мер, при построении многооперандных арифметических устройств, преобразователей кодов и т.д.).

Формула изобретения 0 Устройство для вычисления симметрических булевых функций, содержащее п элементов НЕ (п - количество переменных. , где N 1,2,...), вход v-ro(,2,..,n), из которых соединен с v-м входом устройст- 5 ва, отличающееся тем, что, с целью упрощения при реализации фундаментальных симметрических булевых функций, оно содержит п-1 группу элементов И, 1-я (,2,...,п-1) из которых содержит два эле- мента И, г+1 линейку элементов И. J-я

.2г) из которых содержит A J-2 элементов И, (г+1)-я линейка содержит п-1 элементов И, и г линеек элементов ИЛИ, j-я из которых содержит А элементов ИЛИ, при- чем выход (2j-1)-ro элемента НЕ соединен с первым входом первого элемента И (2j-1-)-u

группы и первым входом 2t-ro(,22j-1)

элемента И j-й линейки элементов И, вход (2j-1)-ro элемента НЕ соединен с первым входом второго элемента 2 (2j-1)-u группы и первым входом (2t-1)-ro элемента И j-й линейки элементов И, выход 2j-ro элемента Н Е соединен с первым входом первого элемен- та И 2j-u группы и первым входом (2S-1)-ro (,22j) элемента ИЛИ j-й линейки элементов ИЛИ, вход 2j-ro элемента НЕ соединен с первым входом второго элемента И 2J-H группы и первым входом 25-го элемента ИЛИ j-й линейки элементов ИЛИ, выход п-го элемента НЕ соединен с вторым входом первого элемента И первой группы и вторым входом первого элемента И первой ли- -нейки элементов И, а вход n-го элемента НЕ соединен с вторым входом второго элемента И первой группы и вторым входом второго элемента И первой линейки элементов И, выход k-ro (,2) элемента И (2j-1) группы соединен с вторым входом k-ro элемента И 2 j-й группы и вторым входом 4j(k-1) элемента ИЛИ j-й линейки элементов ИЛИ, выход k-ro элемента И 21-й(,2, .,г-1) группы соединен с вторым входом k-ro элемента И (21+1)-й группы и вторым входом 4l(k- 1) элемента И (1+1)-й линейки элементов И, выход (2t-2+k)-ro элемента И j-й линейки элементов И соединен с (k+1)-M входом (2t-1+p)-ro (,2) элемента ИЛИ J-й линейки элементов ИЛИ, выход (2w-2+k)-ro (,2,...,2l) элемента ИЛИ 1-й линейки элементов ИЛИ соединен с (k+1)-M входом (2w- 1 + р)-гр элемента И (1 + 1)-й линейки элементов И, выход k-ro элемента И (п-1)-й группы соединен с n(k-1) выходом устройства, (1+1)-й выход которого соединен с выходом 1-го элемента И (г+1)-й линейки элементов И, k-й вход которого соединен с выходом (2i+k-2)-ro элемента ИЛИ r-й линейки элементов ИЛИ