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

(51)06 7/00 НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Авторы Авгуль Леонид Болеславович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элементы сложения по модулю два с первого по третий и элементы И с первого по седьмой, причем выход первого элемента И соединен с первым выходом устройства, Фиг. 1 9051 1 2007.04.30 отличающееся тем, что содержит четвертый и пятый элементы сложения по модулю два,элементы И с восьмого по одиннадцатый и два одноразрядных двоичных сумматора, -й вход первого из которых (1,2,3) соединен с -м входом устройства, (3)-й вход которого соединен с -м входом второго одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом первого элемента И, первым входом второго элемента И, первым входом третьего элемента И, первым входом четвертого элемента И, первым входом пятого элемента И, первым входом шестого элемента И, первым входом седьмого элемента И и первым входом первого элемента сложения по модулю два, выход которого соединен со вторым выходом устройства, а второй вход соединен со вторым входом первого элемента И, вторым входом третьего элемента И, вторым входом четвертого элемента И, вторым входом седьмого элемента И, первым входом восьмого элемента И, первым входом девятого элемента И, первым входом десятого элемента И и выходом суммы первого одноразрядного двоичного сумматора, выход переноса которого соединен с первым входом второго элемента сложения по модулю два, первым входом одиннадцатого элемента И, вторым входом второго элемента И, вторым входом шестого элемента И, вторым входом восьмого элемента И, вторым входом десятого элемента И, третьим входом четвертого элемента И и третьим входом первого элемента И, четвертый вход которого соединен с выходом переноса второго одноразрядного двоичного сумматора, вторым входом пятого элемента И, вторым входом девятого элемента И, вторым входом одиннадцатого элемента И, третьим входом второго элемента И, третьим входом третьего элемента И, третьим входом десятого элемента И и вторым входом второго элемента сложения по модулю два, третий вход которого соединен с выходом седьмого элемента И, а выход соединен с третьим выходом устройства, четвертый выход которого соединен с выходом третьего элемента сложения по модулю два, первый вход которого соединен с выходом пятого элемента И, второй вход соединен с выходом шестого элемента И, третий вход соединен с выходом восьмого элемента И, четвертый вход соединен с выходом девятого элемента И, пятый выход устройства соединен с выходом четвертого элемента сложения по модулю два, первый вход которого соединен с выходом третьего элемента И, второй вход соединен с выходом четвертого элемента И, третий вход соединен с выходом одиннадцатого элемента И, шестой выход устройства соединен с выходом пятого элемента сложения по модулю два, первый вход которого соединен с выходом второго элемента И,второй вход соединен с выходом десятого элемента И. Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления полиномиальных симметрических булевых функций шести переменных. Известно устройство для вычисления фундаментальных симметрических булевых функцийпеременных (многовходовый логический модуль), содержащеегрупп элементов 2-2 И-2 ИЛИ,элементов НЕ и 2-2 элементов И 1. Недостатками устройства являются низкое быстродействие и невозможность вычисления полиномиальных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления веса двоичных кодовых комбинаций, которое при 6 содержит три элемента ИЛИ-НЕ, три элемента сложения по модулю, семь элементов И, четыре элемента 2-2 И-2 ИЛИ и четыре элемента 3-2 И 3 ИЛИ 2. Недостатком устройства также является невозможность вычисления полиномиальных симметрических булевых функций. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации полиномиальных симметрических булевых функций шести переменных. 2 9051 1 2007.04.30 Названный технический результат достигается путем использования новых элементов,а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления полиномиальных симметрических булевых функций, содержит элементы сложения по модулю два с первого по третий и элементы И с первого по седьмой, причем выход первого элемента И соединен с первым выходом устройства. В отличие от прототипа, устройство содержит четвертый и пятый элементы сложения по модулю два, элементы И с восьмого по одиннадцатый и два одноразрядных двоичных сумматора, -й вход первого из которых (1, 2,3) соединен с -м входом устройства,(3) -й вход которого соединен с -м входом второго одноразрядного двоичного сумматора. Выход суммы второго одноразрядного двоичного сумматора соединен с первым входом первого элемента И, первым входом второго элемента И, первым входом третьего элемента И, первым входом четвертого элемента И, первым входом пятого элемента И,первым входом шестого элемента И, первым входом седьмого элемента И и первым входом первого элемента сложения по модулю два. Выход первого элемента сложения по модулю два соединен со вторым выходом устройства, а второй вход соединен со вторым входом первого элемента И, вторым входом третьего элемента И, вторым входом четвертого элемента И, вторым входом седьмого элемента И, первым входом восьмого элемента И, первым входом девятого элемента И, первым входом десятого элемента И и выходом суммы первого одноразрядного двоичного сумматора. Выход переноса первого одноразрядного двоичного сумматора соединен с первым входом второго элемента сложения по модулю два, первым входом одиннадцатого элемента И, вторым входом второго элемента И, вторым входом шестого элемента И, вторым входом восьмого элемента И, вторым входом десятого элемента И, третьим входом четвертого элемента И и третьим входом первого элемента И. Четвертый вход первого элемента И соединен с выходом переноса второго одноразрядного двоичного сумматора, вторым входом пятого элемента И, вторым входом девятого элемента И, вторым входом одиннадцатого элемента И, третьим входом второго элемента И, третьим входом третьего элемента И, третьим входом десятого элемента И и вторым входом второго элемента сложения по модулю два, третий вход которого соединен с выходом седьмого элемента И, а выход соединен с третьим выходом устройства. Четвертый выход устройства соединен с выходом третьего элемента сложения по модулю два, первый вход которого соединен с выходом пятого элемента И, второй вход соединен с выходом шестого элемента И, третий вход соединен с выходом восьмого элемента И,четвертый вход соединен с выходом девятого элемента И. Пятый выход устройства соединен с выходом четвертого элемента сложения по модулю два, первый вход которого соединен с выходом третьего элемента И, второй вход соединен с выходом четвертого элемента И, третий вход соединен с выходом одиннадцатого элемента И. Шестой выход устройства соединен с выходом пятого элемента сложения по модулю два, первый вход которого соединен с выходом второго элемента И, второй вход соединен с выходом десятого элемента И. На фиг. 1 представлена схема устройства для вычисления полиномиальных симметрических булевых функций. Устройство содержит два одноразрядных двоичных сумматора 1 и 2, одиннадцать элементов И 3-13, пять элементов сложения по модулю два 14-18, шесть входов 19-24 и шесть выходов 25-30. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций. Обозначим( ,) - некоторый кортеж длины , содержащий только элемен ты 0,1, и 0. Булева функция,(1, 2, , ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . 9051 1 2007.04.30 С.б.ф.однозначно определяется своим локальным кодом(0, 1, , ), где(1 ,0), 0. Очевидно, что в локальном коде ( ) ф.с.б.ф.только один элемент 1 (все остальные элементы 0, 0, ). Пример 1. При 4 имеет место 0 1 2(4 )(0,0,0,1,0) (4 )(0,0,0,0,1) и 0 1 41234412341 2341234123 42 41 234123412341 2341 23412343 4 41 23412341 2341 23441 234 Произвольная с.б.ф.отпеременных может быть представлена в виде дизъюнктивного разложения посредством ф.с.б.ф С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных(х 1, х 2, , х), называется полиномиальной с.б.ф. (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п. с.б.ф. где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . Векторможет быть получен из локального кодаметодом треугольника 3. Очевидно, что в векторе коэффициентов полинома Жегалкина п. с.б.ф.только один элемент 1. Пример 2. При 4 имеет место(1 )(0,1,0,0,0),( 2 )(0,0,1,0,0),( 3 )(0,0,0,1,0),( 4 )(0,0,0,0,1) и 4 4 4 4 1123421 21 31 42324344 4 31 231 3 41 2423 441 23 4 . 4 4 Таким образом, как следует из (1) и (2), произвольная с.б.ф.отпеременных может быть однозначно представлена в виде дизъюнкции фундаментальных с.б.ф. или суммы по модулю два полиномиальных с.б.ф. Пример 3. Пусть с.б.ф.- ,(х 1,х 2,х 3,х 4) представлена в виде(1212 )3412 (3434 )123134124234 . Очевидно, что локальный код(0,1,0,1,1). Изметодом треугольника может быть найден вектор(0,1,0,0,1). Тогда согласно (1) и (2) можно записать 1 3 444414 . 4 4 Обозначим(,2),(1,2), 2(1,2), 1. Полиномиальная с.б.ф., 1, допускает декомпозиционное разложение вида Предлагаемое устройство предназначено для одновременного вычисления всех 6 полиномиальных с.б.ф.66 , Х(1 ,2 ,3 ,4 ,5 ,6 ),1,6 , зависящих от шести переменных, и построено на основе разложения (3) при 3. Пусть Х 1(х 1,х 2,х 3), Х 2(х 4,х 5,х 6) и Х(Х 1,Х 2). Тогда согласно (3) имеем 2 2 2 11 (1 )1 ( 2 )63 (1 )1 (1 )1 ( 2 )3 ( 2 ) 6 3 3 3 3 2 233 (1 )3 (1 )1 ( 2 )1 (1 )3 ( 2 )3 ( 2 ) 6 3 3 3 3 4 2 263 (1 )1 ( 2 )3 (1 )3 ( 2 )1 (1 )3 ( 2 ) 3 3 3 3 2 253 (1 )3 ( 2 )3 (1 )3 ( 2 )63 (1 )3 ( 2 ). 6 3 3 6 3 3 2 Заметим, что функции 1 и 3 , 1, 2 могут быть реализованы со 3 ответственно на выходах суммы и переноса одноразрядного двоичного сумматора, на вход которого поступают переменные из . Предлагаемое устройство для вычисления п.с.б.ф. построено в соответствии с соотношениями (4). Устройство работает следующим образом. На входы 19-24 поступают (в произвольном порядке) двоичные переменные 1-6. На выходах 25-30 реализуются соответственно Векторы коэффициентов полинома Жегалкина п.с.б.ф.6 ,1,6 , шести переменных имеют вид 2(1 ((0,1,0,0,0,0,0),( 6 ((0,0,1,0,0,0,0),( 3 ((0,0,0,1,0,0,0),6 6 4( 6 ((0,0,0,0,1,0,0),( 5 ((0,0,0,0,0,1,0),( 6 ((0,0,0,0,0,0,1). 6 6 Методом треугольника найдем их локальные коды Из локальных кодов ( 6 ( может быть построена таблица (фиг. 2), устанавливающая связь между весом (числом единиц) входной двоичной кодовой комбинации и вектором выходных сигналов устройства. Достоинствами устройства для вычисления полиномиальных симметрических булевых функций является высокое быстродействие, простая конструкция, широкие функциональные возможности. Источники информации 1. А.с. СССР 1793547, МПК Н 03 М 7/22, 1993. 2. Патент РБ 5314, МПК 067/00, 7/22, 2003 (прототип). 3. Супрун В.П. Полиномиальное разложение симметрических булевых функций // Известия АН СССР. Техническая кибернетика. - 1985. -4. - С. 123-127. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 6