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

(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ(71) Заявитель Белорусский государственный университет (ВУ)(72) Авторы Авгуль Леонид Болеславович Супрун Валерий Павлович (ВУ)(73) Патентообладатель Белорусский государственный университет (ВУ)Устройство для вычисления бисимметрических булевых функций, содержащее два элемента сложения по модулю два, 1-й вход первого из которых (1 1,2) соединен с 1-м информационным входом устройства первой группы, 1-й вход второго элемента сложения по модулю два соединен с 1-м информационным входом устройства второй группы, отлиЧающееся тем, ЧТО содержит два элемента ИЛИ-НЕ и тринадцать элементов И-НЕ, пер вый вход Д-го из которых (3 1,9) соединен с Д-м настроечным входом устройства, выход1-го элемента И-НЕ (1 1,2,3) соединен с 1-м входом Десятого элемента И-НЕ, Четвертый вход которого соединен с выходом первого элемента ИЛИ-НЕ, выход (1 3)-го элемента И-НЕ соединен с 1-м входом одиннадцатого элемента И-НЕ, Четвертый вход которого соединен с выходом первого элемента сложения по модулю два, выход (1 6)-го элемента И-НЕ соединен с 1-м входом двенадцатого элемента И-НЕ, (1 3)-й вход которого соединен с 1-м информационным входом устройства первой группы и 1-м входом первого элемента ИЛИ-НЕ, а выход соединен с первым входом тринадцатого элемента И-НЕ, второй вход которого соединен с выходом десятого элемента И-НЕ, третий вход соединен с вь 1 ходом одиннадцатого элемента И-НЕ, а выход соединен с выходом устройства, 1-й информационный вход второй группы которого соединен с (1 1)-м входом третьего элемента И-НЕ, (1 1)-м входом шестого элемента И-НЕ, (1 1)-м входом девятого элемента И-НЕ и 1-м входом второго элемента ИЛИ-НЕ, выход которого соединен со вторым входом первого элемента И-НЕ, вторым входом четвертого элемента И-НЕ и вторым входом седьмого элемента И-НЕ, выход второго элемента сложения по модулю два соединен со вторым входом второго элемента И-НЕ, вторым входом пятого элемента И-НЕ и вторым входом восьмого элемента И-НЕ.ИЗОбрСТСНИС ОТНОСИТСЯ К ВЫЧИСЛИТСЛЬНОЙ ТСХНИКС И МИКРОЭЛСКТРОНИКС И предназна чено для вычисления бисимметрических булевых функций четырех переменных.Известно устройство для вычисления бисимметрических булевых функций шести переменных класса (3, 3), содержащее три элемента сложения по модулю два, два мажоритарных элемента с порогом два, семь элементов ЗАПРЕТ и восемь элементов И 1.Недостатком устройства является высокая конструктивная сложность.Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления бисимметрических булевых функций четырех переменных класса (2, 2), содержащее элемент сложения по модулю два, два полусумматора (каждый содержит элемент сложения по модулю два и элемент И) и восемь элементов И 2.Во многих современных интегральных технологиях схемотехнически (на транзисторном уровне) реализуются только двухвходовые элементы сложения по модулю два. Элементы с большим числом входов строятся путем пирамидального включения двухвходовых элементов, что приводит к соответственному увеличению глубины схемы. Так,например, в устройстве-прототипе для построения девятивходового элемента сложения по модулю два потребуется восемь двухвходовых элементов, включенных по пирамидальной схеме, глубина которой равна четырем. Следовательно, быстродействие устройствапрототипа, определяемое обшей глубиной схемы, составит 613, где т - задержка на вентиль.Таким образом, недостатком известного устройства для вычисления бисимметрических булевых функций является низкое быстродействие.Изобретение направлено на решение задачи повышения быстродействия устройства для вычисления бисимметрических булевых функций.Названный технический результат достигается путем введения в состав устройства элементов И-НЕ и элементов ИЛИ-НЕ.Устройство для вычисления бисимметрических булевых функций содержит два элемента сложения по модулю два, 1-й вход первого из которых (1 1, 2) соединен с 1-м информационным входом устройства первой группы, 1-й вход второго элемента сложения по модулю два соединен с 1-м информационным входом устройства второй группы.В отличие от прототипа, устройство содержит два элемента ИЛИ-НЕ и тринадцатьустройства. Выход 1-го элемента И-НЕ (1 1, 2, 3) соединен с 1-м входом десятого элемента И-НЕ, четвертый вход которого соединен с выходом первого элемента ИЛИ-НЕ.Выход (1 3)-го элемента И-НЕ соединен с 1-м входом одиннадцатого элемента И-НЕ,четвертый вход которого соединен с выходом первого элемента сложения по модулю два. Выход (1 6)-го элемента И-НЕ соединен с 1-м входом двенадцатого элемента И-НЕ,(1 3)-й вход которого соединен с 1-м информационным входом устройства первой группы и 1-м первого элемента ИЛИ-НЕ. Выход двенадцатого элемента И-НЕ соединен с первым входом тринадцатого элемента И-НЕ, второй вход которого соединен с выходом десятого элемента И-НЕ, третий вход соединен с выходом одиннадцатого элемента И-НЕ, а выход соединен с выходом устройства. В устройстве 1-й информационный вход второй группы соединен с (1 1)-м входом третьего элемента И-НЕ, (1 1)-м входом Шестого элемента И-НЕ, (1 1)-м входом девятого элемента И-НЕ и 1-м входом второго элемента ИЛИ-НЕ. Выход второго элемента ИЛИ-НЕ соединен со вторым входом первого элемента И-НЕ, вторым входом четвертого элемента И-НЕ и вторым входом седьмого элемента ИНЕ. Выход второго элемента сложения по модулю два со вторым входом второго элемента И-НЕ, вторым входом пятого элемента И-НЕ и вторым входом восьмого элемента И-НЕ.На фиг. 1 представлена схема устройства для вычисления бисимметрических булевых функций.Устройство содержит тринадцать элементов И-НЕ, два элемента ИЛИ-НЕ 14 и 15(первый элемент 15 и второй элемент 14), два элемента сложения по модулю два 16 и 17(первый элемент 17 и второй элемент 16), два информационных входа первой группы 18 и 19, два информационных входа второй группы 20 и 21, девять настроечнь 1 х входов 22-30 и выход 31.Поясним принцип работы устройства для вычисления бисимметрических булевых функций.Обозначим С (11, 11,. . ., 11) - некоторый кортеж длины 5, содержащий только элемен ты 115 О,1,и 622.Булева функция Р Р(Х), Х (х 1, х 2,, х), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из Х. С.б.ф. Р однозначно определяется своим локальным кодом 703) (по, 751,. . ., м), где 71 1463, 62 , О 5 1 5 п.Булева функция Г Г(Х) называется бисимметрической (б.с.б.ф.), если вектор ее переменных Х допускает разбиение на два кортежа Х 1 и Х 2, и при этом Г симметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу Х 1 и Х 2.Для определенности полагаем Х 1 (х 1, х 2,, хт), Х 2 (хшд, хт 2,, х), 1 шп. При Х 1 ш, Х 2 п-ш будем говорить, что б.с.б.ф. Г от п переменных принадлежит классу (ш, п-ш).Б.с.б.ф. Г Г(Х) Г(Х 1, Х 2), принадлежащая классу (ш, п-ш), однозначно определяется своим локальным кодом С(Г), который представляет собой булев вектор длины 1(ш 1)(п-ш 1) битт-п пт а Число б.с.б.ф. класса (ш, п-ш) равно 2 Ь. Предлагаемое устройство реализует 29 б.с.б.ф. Г Г(Х) Г(Х 1, Х 2), класса (2, 2), зави сящих от четырех переменных (п 4, ш 2). Первообразная функция устройства имеет видХ 1 Х 2 ив Хз УХА 17 (Хз (Эха )Ц 8 Х 3 Х 4Здесь знак л обозначает инверсию выражения, стоящего за ним. Вектором настройки П устройства на реализацию конкретной б.с.б.ф. Г, является вектор, инверсный ее локальному коду, т.е.Устройство для вычисления бисимметрических булевых функций работает следуюЩИМ образом.На информационные входы 18 и 19 первой группы поступают двоичные переменные х 1 и х (в произвольном порядке), на информационные входы 20 и 21 второй группы двоичные переменные х 3 и х 4 (в произвольном порядке). На настроечные входы 22-30 подаются сигналы настройки 110-118 соответственно. На выходе 31 реализуется б.с.б.ф. Г Г(Х 1, Х 2), определяемая вектором настройки П (110, 111,. . ., 113).Найдем вектор настройки П предлагаемого устройства на реализацию бисимметрической булевой функцииГ Г(Х 1,Х 2 х 1 х 2 х 3 х 4 /х 1 х 2 х 3 х 4 /(х 1/ х, х 3 х 4. Очевидно, локальный код заданной б.с.б.ф. Г Г(Х 1, Х 2) имеет вид си) (с,с,с 2,с 1,с 1,с,с 2,с 2,с) (1,о,1,0,о,1 о,о,1) . Поскольку П б(Г ), то вектор настройки устройства имеет видП (по 111. из) (010110110)Следовательно, для реализации рассматриваемой б.с.б.ф. необходимо подать сигналы логической единицы на настроечные входы 23, 25, 26, 28 и 29 а сигнал логического нуля на настроечные входы 22, 24, 27 и 30. Достоинствами устройства для вычисления бисимметрических булевых функций являются высокое быстродействие и простая конструкция.Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.