Устройство для вычисления симметрических булевых функций
Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении матричных арифметических устройств. Цель изобретения - упрощение устройства при реализации фундаментальных симметрических булевых функций. Поставленная цель достигается тем, что устройство для вычисления фундаментальных симметрических булевых функций содержит п (п - количество переменных реализуемых функций и ) элементов НЕ, п-1 группу элементов И, каждая из которых содержит два элемента И, г+1 линеек элементов И, г линеек элементов ИЛИ, п входов и п+1 выходов. Сложность устройства по числу входов логических элементов составляет. S 3n2+2n-4 Устройство работает следующим образом На входы устройства поступают двоичные переменные xi xn (в произвольном порядке ), а на его выходах реализуются фундаментальные симметрических булев е функции Fn°...Fnn. 1 ил.
союз соВетских
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ ПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 1 (21) 4870148/24 (22) 27.09.90 (46) 15,07.92. Бюл. М 26 (72) Л.Б.Авгуль и В.П.Супрун (53) 681.3(088.8) (56) Авторское свидетельство СССР Гч 1256012, кл. G 06 F 7/00, 1985. Авторское свидетельство СССР М 1478208, кл, 6 06 F 7/00, 1981., (,54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении матричных арифметических устройств. Цель изобретения — упрощение устройства при реализации фундаментальных симметричеИзобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении арифметических матричных устройств. Известен .;ногофункциональный логический модуль, содержащий три элемента РАВНОЗНАЧНОСТЬ и два элемента И. Модуль реализует все булевы функции двух переменных и имеет четыре выхода, на которых формируются одновременно значения четырех функций. Недостатком модуля являются низкие функциональные возможности, так как он не реализует булевы функции трех и более переменных. Наиболее близким к изобретению является устройство для вычисления симметрических булевых функций (с.б.ф.) от четырех переменных. содержащее четыре элемента НЕ и двадцать один элемент И вЂ” НЕ.. Ж 1748150 А1 2 ских булевых функций, Поставленная цель достигается тем, что устройство для вычисления фундаментальных симметрических булевых функций содержит и (n — количество переменных реализуемых функций и ri=2r+1) элементов НЕ, и 1 группу элементов И; каждая из которых содержит два элемента И, г+1 линеек элементов И, r лйнеек элементов ИЛИ, и входов и и+1 выходов. Сложность устройства по числу входов логических элементов составляет S=3n +2п-4. Устройство работает следующим образом, На входы устройства поступают двоичные переменные x1„,хп (в произвольном порядке), а íà его выходах реализуются фундаментальные симметрических булевь!е функции Fn ...1" . 1 ил. Недостатком известного устройства является высокая конструктивная-сложность, а также один выход, на котором формируются значения реализуемых с,б.ф„что в ряде случаев ограничивает область применения устройства, Цель изобретения — упрощение устройства для вычисления симметрических буле- Ql вых функций. С) Устройство для вычисления симметрических булевых функций содержит и (n — 4 количество переменных реализуемых функций и n=2r+1, где r=1,2,3,.„) элементов НЕ, и-1 группу элементов И, i-я (i=1,2„.„n — 1) из которых содержит два элемента И, r+1 линейку элементов И и r линеек элементов ИЛИ, Вход ч-ro (ч=1,2,...,n) элемента НЕ соединен с ч-ым входом устройства, J-я (j=1,2,.„,r) линейка элементов И содержит 4j-2 элементов И,(г+1)-я линейка элементов 1748150 20 35 ляется соотношением 45 лей кодов и т.д.) 55 И содержит и — 1 элементов И, j-я линейка элементов ИЛИ содержит 4) элементов ИЛИ. Выход (21-1)-й группы и первым входом 2t-ro (t=-1,2„...2J — 1) элемента И j-й линейки элементов И, вход (21т — 1)-го элемента НЕ соединен с первым входом второго элемента И (21 — 1)-й группы и первым входом (2t-1)-го элемента И j-й линейки элементов И. Выход 2j-го элемента НЕ соединен с первым входом первого элемента И 2j-й группы и первым входом (2s-1)-ro (s=1,2,..е,21) элемента ИЛИ )-й линейки элементов ИЛИ, вход 2j-го элемента НЕ соединен с первым входом второго элемента И 2j-й группы и первым входом 2s-го элемента ИЛИ j-й линейки элементов ИЛИ, Выход и-го элемента НЕ соединен с вторым входом первого эле мента И первой группы и вторым входом первого элемента И первой линейки элементов И, а вход n-ro элемента НЕ соединен с вторым входом второго элемента И первой группы и вторым входом второго элемента и первой линейки элементов И, Выход k-го (k=1,2) элемента И (21-1-)-й группы соединен со вторым входом k ro "элемента И 2)-й группы и вторым входом (4j(k-1)-k+2)-го элемента ИЛИ j-й линейки элементов ИЛИ. Выход k-ro элемента И 21-й (1=1,2,;...r — 1) группы соединен со вторым входом k-ro элемента.И (21+1)-й группы и вторым входом (41(k 1)+k) го элемента И (1+1)-й линейки элементов Ие Выход (2t — 2+k)-го элемента И j-й линейки элементов И соединен с (k+1)-м входом (2t— 1+р)-го (р=1,2) элемента ИЛИ j-й линейки элементов ИЛИ. Выход (2w — 2+k)-ro (w=1,2„„,21) элемента ИЛИ 1-й линейки элементов ИЛИ соединен с (k+1)-ым входом (2w — 1+р)-го элемента И (1+1)-й линейки элементов И. Выход k-го элемента И (n — 1)-й группы соединен с (n(k — 1)+1)-ым выходом устройства, (1+1)-й выход которого соединен с выходом 1-го элемента И (г+1) -й линейки элементов И, k-й вход которого соединен с выходом. (21+k-2)-ro элемента ИЛИ r-й линейки элементов ИЛИ. На чертеже представлена функциональная схема устройства для вычисления с.б.ф, при n=2r+1=5, Устройство содержит n=5 элементов НЕ 14...15, два элемента И первой группы 2t и 22, два элемента И второй группы 31 и 32, два элемента И третьей группы 4t и 42, два элемента И четвертой группы 51 и 52, два элемента И первой линейки элементов И 61 и 62, шесть элементов и второй линейки элементов И 71..,7s, четыре элемента И третьей линейки элементов И 8t.„84, четыре элемента ИЛИ первой линейки элементов ИЛИ 9 ...94, восемь элементов ИЛИ второй линейки элементов ИЛИ 101...10в, и--5 входов 111„,115, и+1=6 выходов 121...126, Устройства для вычисления с,б.ф, работает следующим образом. На входы 11t...11ö устройства подаются двоичные переменные х ...х5 (в произвольном порядке), на выходах 12 .„126 реализуются фундаментальные с.б.ф. Fg ...Fg5 соответственно. .Отметим, что фундаментальная с.б.ф, п переменных Fn Fn (xt,х2....;;,,хп) принимает значение логической единицы на тех и толька тех наборах переменных х1, x2,...xn, которые содержат ровно m единиц (m=0,1,...n), т.е., если xt+x2+„,+õ, = m; Fn (х1,х2,... хп) = 0- в противном случае. Для четного значения и в устройстве, построенном для нечетного п, достаточно на вход элемента НЕ первой (или последней) линейки подать константу "логический ноль", В результате этого устргйство. для 25 . нечетного п=2г+1 преобраэуетея в устройство для четного n=2ã. Достоинством устройства для вычисления с,б.ф. является простая конструкция, регулярная структура и широкая область применения. Так, сложность (no числу входов логических элементов) устройства может быть рассчитана по формуле $ =3n +2п — 4, (1) а сложность устройства-прототипа опреде$ р = Зп + 2n + 2.. (2) Результаты расчетов по формулам (1) и (2) свидетельствуют о преимуществе предлагаемого устройства перед прототипом. Кроме того, одновременное формирование на выходах устройства всех фундаментальных с.б,ф, и переменных расширяет область возможного применения устройства(например, при построении многооперандных арифметических устройств, преобразовате-. Формула изобретения Устройство для вычисления симметрических булевых функций, содержащее и элементов НЕ (п — количество переменных, n=2N+1, где N = 1,2,...), вход v-го (v=1,2...,n). из которых соединен с ч-м входом устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения при реализации фундаментальных симметрических булевых функций, оно содержит п 1 группу элементов И, 1-я (1=1, 2„.„л — 1) из которых содержит два злемента И, г+1 линейку элементов И. j-л 1748150 Составитель В. Суп рун Техред М.Моргентал Редактор Н,Швыдкая Корректор С,Черни Заказ 2505 Тираж. Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 (j=1,2,...,r) иэ которых содержит 4 J — 2 элементов И, (г+1)-я линейка содержит и-1 элементов И, и r линеек элементов ИЛИ, J-я из которых содержит 4J элементов ИЛИ, причем выход(2)-1)-го элемента НЕ соединен с первым входом первого элемента И (2j — 1)-й группы и первым входом 2t-го (t=1,2„...2j — 1) элемента И )-й линейки элементов И, вход (2)-1)-го элемента НЕ соединен с первым входом второго элемента 2 (2j-1)-й группы и первым входом (2t-1)-го элемента И j-й линейки элементов И, выход 2j-ro элемента НЕ соединен с первым входом первого элемента И 2J-й группы и первым входом (2S-1)-го (S=1,2,...,2j) элемента ИЛИ j-й линейки элементов ИЛИ, вход 2J-ro элемента НЕ соединен с первым входом второго элемента И 2J-й группы и первым входом 2S-го элемента ИЛИ)-й линейки элементов ИЛИ, выход и-го элемента НЕ соединен с вторым входом первого элемента И первой группы и вторым входом первого элемента И первой ли-нейки элементов И, а вход n-ro элемента НЕ соединен с вторым входом второго элемента И первой группы и вторым входам второго элемента И первой линейки элеМентов И, выход k-ro (k=1,2) элемента И (2j — 1)-й группы 5 соединен с вторым входом k-ro элемента И 2j-й группы и- вторым входом (4j(k-1) — k+2)-го элемента ИЛИ j-й линейки элементов ИЛИ, выход k-ro элемента И 21-й (l=1,2,...,r — 1) груп10 пы соединен с вторым входом k ro элемента И (2I+1)-й группы и вторым входом (4l(k— 1)+k)-го элемента И (I+1)-й линейки элементов И., выход (2t-2+k)-го элемента И J-й линейки элементов И соединен с (k+1)-м вхо15 дом (2t-1+р)-го (р=1.2) элемента ИЛИ j-й линейки элементов ИЛИ, выход (2w-2+k)-го (w-1,2,...,21) элемента ИЛИ Ьй линейки эле: ментов ИЛИ соединен с (k+1)-м входом (2w— 1+р)-го элемента И ((+1)-й линейки 20 элементов И, выход k-го элемента И (n — 1)-й группы соединен с (n(k-1)+1)-м выходом устройства, (I+1)-й выход которого соединен с выходом 1-го элемента.И (г+1)-й линейки элементов И, k-й вход которого соединен с вы25 ходом {2i+k-2)-ro элемента ИЛИ r-й линейки элементов ИЛИ.
