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

(51)06 7/00 НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Авторы Авгуль Леонид Болеславович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элементы сложения по модулю два с первого по четвертый и элементы И с первого по десятый, причем выход первого элемента И соединен с первым входом второго элемента И, выход которого соединен с первым входом третьего элемента И, выход которого соединен с первым выходом устройства, отличающееся тем, что содержит элементы 9147 1 2007.04.30 сложения по модулю два с пятого по пятнадцатый, элементы И с одиннадцатого по двадцать четвертый и четыре полусумматора, -й вход первого из которых (1,2) соединен с-м входом устройства, (2)-й вход которого соединен с -м входом второго полусумматора, (4)-й вход соединен с -м входом третьего полусумматора, (6)-й вход соединен с -м входом четвертого полусумматора, выход суммы первого полусумматора соединен с первым входом первого элемента сложения по модулю два, первым входом четвертого элемента И и первым входом пятого элемента И, выход которого соединен с первым входом второго элемента сложения по модулю два, а второй вход соединен с выходом переноса второго полусумматора, первым входом первого элемента И и первым входом третьего элемента сложения по модулю два, второй вход которого соединен с выходом четвертого элемента И, третий вход соединен с выходом переноса первого полусумматора, вторым входом первого элемента И и первым входом шестого элемента И, выход которого соединен со вторым входом второго элемента сложения по модулю два, а второй вход соединен с выходом суммы второго полусумматора, вторым входом четвертого элемента И и вторым входом первого элемента сложения по модулю два, выход которого соединен с первым входом седьмого элемента И, первым входом восьмого элемента И и первым входом четвертого элемента сложения по модулю два, второй вход которого соединен со вторым входом седьмого элемента И, первым входом девятого элемента И, первым входом десятого элемента И, первым входом одиннадцатого элемента И и выходом суммы третьего полусумматора, выход переноса которого соединен со вторым входом второго элемента И, вторым входом восьмого элемента И, первым входом двенадцатого элемента И, первым входом тринадцатого элемента И и первым входом пятого элемента сложения по модулю два, второй вход которого соединен с выходом седьмого элемента И,третий вход соединен с выходом третьего элемента сложения по модулю два, вторым входом двенадцатого элемента И и вторым входом девятого элемента И, выход которого соединен с первым входом шестого элемента сложения по модулю два, второй вход которого соединен с выходом восьмого элемента И, третий вход соединен с выходом второго элемента сложения по модулю два, вторым входом тринадцатого элемента И и вторым входом десятого элемента И, выход которого соединен с первым входом седьмого элемента сложения по модулю два, второй вход которого соединен с выходом двенадцатого элемента И, третий вход соединен с выходом первого элемента И и вторым входом одиннадцатого элемента И, выход которого соединен с первым входом восьмого элемента сложения по модулю два, второй вход которого соединен с выходом тринадцатого элемента И, выход четвертого элемента сложения по модулю два соединен с первым входом четырнадцатого элемента И, первым входом пятнадцатого элемента И и первым входом девятого элемента сложения по модулю два, выход которого соединен со вторым выходом устройства, а второй вход соединен со вторым входом четырнадцатого элемента И, первым входом шестнадцатого элемента И, первым входом семнадцатого элемента И, первым входом восемнадцатого элемента И, первым входом девятнадцатого элемента И, первым входом двадцатого элемента И и выходом суммы четвертого полусумматора, выход переноса которого соединен со вторым входом третьего элемента И, вторым входом пятнадцатого элемента И, первым входом двадцать первого элемента И, первым входом двадцать второго элемента И, первым входом двадцать третьего элемента И, первым входом двадцать четвертого элемента И и первым входом десятого элемента сложения по модулю два, выход которого соединен с третьим выходом устройства, а второй вход соединен с выходом четырнадцатого элемента И, третий вход соединен с выходом пятого элемента сложения по модулю два, вторым входом двадцать первого элемента И и вторым входом шестнадцатого элемента И, выход которого соединен с первым входом одиннадцатого элемента сложения по модулю два, выход которого соединен с четвертым выходом устройства, а второй вход соединен с выходом пятнадцатого элемента И, третий вход соединен с выходом шестого элемента сложения по модулю два, вторым входом двадцать 2 9147 1 2007.04.30 второго элемента И и вторым входом семнадцатого элемента И, выход которого соединен с первым входом двенадцатого элемента сложения по модулю два, выход которого соединен с пятым выходом устройства, а второй вход соединен с выходом двадцать первого элемента И, третий вход соединен с выходом седьмого элемента сложения по модулю два,вторым входом двадцать третьего элемента И и вторым входом восемнадцатого элемента И, выход которого соединен с первым входом тринадцатого элемента сложения по модулю два, выход которого соединен с шестым выходом устройства, а второй вход соединен с выходом двадцать второго элемента И, третий вход соединен с выходом восьмого элемента сложения по модулю два, вторым входом двадцать четвертого элемента И и вторым входом девятнадцатого элемента И, выход которого соединен с первым входом четырнадцатого элемента сложения по модулю два, выход которого соединен с седьмым выходом устройства, а второй вход соединен с выходом двадцать третьего элемента И, третий вход соединен с выходом второго элемента И и вторым входом двадцатого элемента И, выход которого соединен с первым входом пятнадцатого элемента сложения по модулю два,второй вход которого соединен с выходом двадцать четвертого элемента И, а выход соединен с восьмым выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно устройство для вычисления фундаментальных симметрических булевых функцийпеременных (многовходовый логический модуль), содержащеегрупп элементов 2-2 И-2 ИЛИ,элементов НЕ и 2-2 элементов И 1. Недостатками устройства являются низкое быстродействие и невозможность вычисления полиномиальных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления веса двоичных кодовых комбинаций, которое при 8 содержит четыре элемента ИЛИ-НЕ, четыре элемента сложения по модулю, десять элементов И, шесть элементов 2-2 И-2 ИЛИ и девять элементов 32 И-3 ИЛИ 2. Недостатком устройства также является невозможность вычисления полиномиальных симметрических булевых функций. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации полиномиальных симметрических булевых функций восьми переменных. Названный технический результат достигается путем использования новых элементов,а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления полиномиальных симметрических булевых функций содержит элементы сложения по модулю два с первого по четвертый и элементы И с первого по десятый, причем выход первого элемента И соединен с первым входом второго элемента И, выход которого соединен с первым входом третьего элемента И, выход которого соединен с первым выходом устройства. В отличие от прототипа устройство содержит элементы сложения по модулю два с пятого по пятнадцатый, элементы И с одиннадцатого по двадцать четвертый и четыре полусумматора. В устройстве -й вход первого полусумматора (1,2) соединен с -м входом устройства, (2)-й вход которого соединен с -м входом второго полусумматора, (4)-й вход соединен с -м входом третьего полусумматора, (6)-й вход соединен с -м входом четвертого полусумматора. 9147 1 2007.04.30 Выход суммы первого полусумматора соединен с первым входом первого элемента сложения по модулю два, первым входом четвертого элемента И и первым входом пятого элемента И, выход которого соединен с первым входом второго элемента сложения по модулю два, а второй вход соединен с выходом переноса второго полусумматора, первым входом первого элемента И и первым входом третьего элемента сложения по модулю два. Второй вход третьего элемента сложения по модулю два соединен с выходом четвертого элемента И, третий вход соединен с выходом переноса первого полусумматора, вторым входом первого элемента И и первым входом шестого элемента И, выход которого соединен со вторым входом второго элемента сложения по модулю два, а второй вход соединен с выходом суммы второго полусумматора, вторым входом четвертого элемента И и вторым входом первого элемента сложения по модулю два. Выход первого элемента сложения по модулю два соединен с первым входом седьмого элемента И, первым входом восьмого элемента И и первым входом четвертого элемента сложения по модулю два, второй вход которого соединен со вторым входом седьмого элемента И, первым входом девятого элемента И, первым входом десятого элемента И,первым входом одиннадцатого элемента И и выходом суммы третьего полусумматора. Выход переноса третьего полусумматора соединен со вторым входом второго элемента И, вторым входом восьмого элемента И, первым входом двенадцатого элемента И, первым входом тринадцатого элемента И и первым входом пятого элемента сложения по модулю два, второй вход которого соединен с выходом седьмого элемента И, третий вход соединен с выходом третьего элемента сложения по модулю два, вторым входом двенадцатого элемента И и вторым входом девятого элемента И, выход которого соединен с первым входом шестого элемента сложения по модулю два. Второй вход шестого элемента сложения по модулю два соединен с выходом восьмого элемента И, третий вход соединен с выходом второго элемента сложения по модулю два,вторым входом тринадцатого элемента И и вторым входом десятого элемента И, выход которого соединен с первым входом седьмого элемента сложения по модулю два, второй вход которого соединен с выходом двенадцатого элемента И, третий вход соединен с выходом первого элемента И и вторым входом одиннадцатого элемента И, выход которого соединен с первым входом восьмого элемента сложения по модулю два, второй вход которого соединен с выходом тринадцатого элемента И. Выход четвертого элемента сложения по модулю два соединен с первым входом четырнадцатого элемента И, первым входом пятнадцатого элемента И и первым входом девятого элемента сложения по модулю два, выход которого соединен со вторым выходом устройства, а второй вход соединен со вторым входом четырнадцатого элемента И, первым входом шестнадцатого элемента И, первым входом семнадцатого элемента И, первым входом восемнадцатого элемента И, первым входом девятнадцатого элемента И, первым входом двадцатого элемента И и выходом суммы четвертого полусумматора. Выход переноса четвертого полусумматора соединен со вторым входом третьего элемента И, вторым входом пятнадцатого элемента И, первым входом двадцать первого элемента И, первым входом двадцать второго элемента И, первым входом двадцать третьего элемента И, первым входом двадцать четвертого элемента И и первым входом десятого элемента сложения по модулю два. Выход десятого элемента сложения по модулю два соединен с третьим выходом устройства, а второй вход соединен с выходом четырнадцатого элемента И, третий вход соединен с выходом пятого элемента сложения по модулю два, вторым входом двадцать первого элемента И и вторым входом шестнадцатого элемента И, выход которого соединен с первым входом одиннадцатого элемента сложения по модулю два, выход которого соединен с четвертым выходом устройства. Второй вход одиннадцатого элемента сложения по модулю два соединен с выходом пятнадцатого элемента И, третий вход соединен с выходом шестого элемента сложения по 4 9147 1 2007.04.30 модулю два, вторым входом двадцать второго элемента И и вторым входом семнадцатого элемента И, выход которого соединен с первым входом двенадцатого элемента сложения по модулю два. Выход двенадцатого элемента сложения по модулю два соединен с пятым выходом устройства, а второй вход соединен с выходом двадцать первого элемента И, третий вход соединен с выходом седьмого элемента сложения по модулю два, вторым входом двадцать третьего элемента И и вторым входом восемнадцатого элемента И, выход которого соединен с первым входом тринадцатого элемента сложения по модулю два, выход которого соединен с шестым выходом устройства. Второй вход тринадцатого элемента сложения по модулю два соединен с выходом двадцать второго элемента И, третий вход соединен с выходом восьмого элемента сложения по модулю два, вторым входом двадцать четвертого элемента И и вторым входом девятнадцатого элемента И, выход которого соединен с первым входом четырнадцатого элемента сложения по модулю два. Выход четырнадцатого элемента сложения по модулю два соединен с седьмым выходом устройства, а второй вход соединен с выходом двадцать третьего элемента И, третий вход соединен с выходом второго элемента И и вторым входом двадцатого элемента И,выход которого соединен с первым входом пятнадцатого элемента сложения по модулю два, второй вход которого соединен с выходом двадцать четвертого элемента И, а выход соединен с восьмым выходом устройства. На фиг. 1 представлена схема устройства для вычисления полиномиальных симметрических булевых функций. Устройство содержит четыре полусумматора 1-4, двадцать четыре элемента И 5-28,пятнадцать элементов сложения по модулю два 29-43, восемь входов 44-51 и восемь выходов 52-59. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций. Обозначим - некоторый кортеж длины , содержащий только элементы 0,1, и 0. Булева функция,(1,2), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(о,1), где( 1 ,0,), 0. Очевидно, что в локальном коде ф.с.б.ф.только один элемент 1 (все остальные элементы 0, 0,). 9147 1 2007.04.30 Произвольная с.б.ф.отпеременных может быть представлена в виде дизъюнктивного разложения посредством ф.с.б.ф С.б.ф.(Х), 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1,2 х, называется полиномиальной (п.с.б.ф.) Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . Векторможет быть получен из локального кодаметодом треугольника(Супрун В.П. Полиномиальное разложение симметрических булевых функций / Известия АН СССР. Техническая кибернетика. - 1985. -4. - С. 123-127). Очевидно, что в векторе (Е) коэффициентов полинома Жегалкина п.с.б.ф. Е только один элемент 1. Пример 2. При 4 имеет место 1123421 21 31 423243 44 431 231 341 2423441 234 . 4 4 Таким образом, как следует из (1) и (2), произвольная с.б.ф.отпеременных может быть однозначно представлена в виде дизъюнкции фундаментальных с.б.ф. или суммы по модулю два полиномиальных с.б.ф. Пример 3. Пусть с.б.ф.Е(Х),(1,2,3,4) представлена в виде( 1 21 2 )3 41 2 (3 43 4 )1 231 3 41 2423 4 . Очевидно, что локальный код(0,1,0,1,1). Изметодом треугольника может быть найден вектор(0,1,0,0,1). Тогда, согласно (1) и (2), можно записать 1 3 444414 . 4 4 Обозначим Х(Х 1,Х 2), Х 1(х 1,2 х), Х 2(х 1,х 2 х), 1. Полиномиальная с.б.ф.(Х), 1, допускает декомпозиционное разложение вида Предлагаемое устройство предназначено для одновременного вычисления всех 8 полиномиальных с.б.ф. 88 (Х),(,2,3,4),(,2), Х 2(х 3,х 4), Х 3(х 5,х 6), Х 4(х 7,8),1,8 , зависящих от восьми переменных. Устройство построено на основе разложения п.с.б.ф. 88 согласно (3) последовательно по парам переменных Х 1, Х 2, Х 3, 4. Обозначим 121221 (2)3422 (2)342 2 2 2 2 86 (1,2,3)4. 8 6 Заметим, что функции 1 и 2,1,4 , могут быть реализованы со 2 2 ответственно на выходе суммы и выходе переноса полусумматора, на вход которого поступают переменные из Х. Устройство для вычисления полиномиальных симметрических булевых функций работает следующим образом. На входы 44-51 поступают (в произвольном порядке) двоичные переменные х 1-х 8. На выходах 52-59 реализуются соответственно полиномиальные с.б.ф. 1 -8 ,(х 1,х 2 х 8). 8 8 Векторы коэффициентов полинома Жегалкина п.с.б.ф. 8 (Х),1,8 , восьми переменных имеют вид 2 3 Методом треугольника могут быть также найдены локальные коды 82 3 Из локальных кодов ( 8 ( может быть построена таблица (фиг. 2), устанавливающая связь между весом (числом единиц) входной двоичной кодовой комбинации и вектором выходных сигналов устройства. Достоинствами устройства для вычисления полиномиальных симметрических булевых функций является простая конструкция, однородная и регулярная структура, широкие функциональные возможности. Таблица работы устройства для вычисления полиномиальных симметричных булевых функций Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.