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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(72) Авторы Авгуль Леонид Болеславович Булаш Юрий Леонидович Петроченко Андрей Сергеевич Терешко Сергей Михайлович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления полиномиальных симметрических булевых функций, содержащее блок вычисления полиномиальных симметрических булевых функций восьми переменных, -й вход которого, где 1,8 , соединен с -м входом устройства, отличающееся тем, что содержит тридцать два элемента И, одиннадцать элементов сложения по 13243 1 2010.06.30 модулю два и блок вычисления полиномиальных симметрических булевых функций четырех переменных, -й вход которого, где 1,4 , соединен с (8)-м входом устройства,а первый выход - с первым входом первого элемента сложения по модулю два и первым входом -го элемента И, второй выходс первым входом второго элемента сложения по модулю два и первым входом (8)-го элемента И, третий выход - с первым входом третьего элемента сложения по модулю два и первым входом (16)-го элемента И, четвертый выход - с первым входом четвертого элемента сложения по модулю два и первым входом (24)-го элемента И, -й выход блока вычисления полиномиальных симметрических булевых функций восьми переменных соединен со вторым входом -го элемента сложения по модулю два, вторым входом -го элемента И, вторым входом (8)-го элемента И, вторым входом (16)-го элемента И и вторым входом (24)-го элемента И,(4)-й выход блока вычисления полиномиальных симметрических булевых функций восьми переменных соединен с первым входом (4)-го элемента сложения по модулю два, вторым входом (4)-го элемента И, вторым входом (12)-го элемента И, вторым входом (20)-го элемента И и вторым входом (28)-го элемента И, выход -го элемента сложения по модулю два соединен с -м выходом устройства, выход первого элемента И соединен с третьим входом второго элемента сложения по модулю два, выход второго элемента И соединен с третьим входом третьего элемента сложения по модулю два, четвертый вход которого соединен с выходом девятого элемента И, выход третьего элемента И соединен с третьим входом четвертого элемента сложения по модулю два, четвертый вход которого соединен с выходом десятого элемента И, а пятый вход - с выходом семнадцатого элемента И, выход четвертого элемента И соединен со вторым входом пятого элемента сложения по модулю два, третий вход которого соединен с выходом одиннадцатого элемента И, а четвертый вход - с выходом восемнадцатого элемента И, пятый вход - с выходом двадцать пятого элемента И, выход пятого элемента И соединен со вторым входом шестого элемента сложения по модулю два, третий вход которого соединен с выходом двенадцатого элемента И, а четвертый вход - с выходом девятнадцатого элемента И,пятый вход - с выходом двадцать шестого элемента И, выход шестого элемента И соединен со вторым входом седьмого элемента сложения по модулю два, третий вход которого соединен с выходом тринадцатого элемента И, а четвертый вход - с выходом двадцатого элемента И, пятый вход - с выходом двадцать седьмого элемента И, выход седьмого элемента И соединен со вторым входом восьмого элемента сложения по модулю два, третий вход которого соединен с выходом четырнадцатого элемента И, а четвертый вход - с выходом двадцать первого элемента И, пятый вход - с выходом двадцать восьмого элемента И, выход восьмого элемента И соединен с первым входом девятого элемента сложения по модулю два, выход которого соединен с девятым выходом устройства, а второй вход - с выходом пятнадцатого элемента И, третий вход - с выходом двадцать второго элемента И,четвертый вход - с выходом двадцать девятого элемента И, выход шестнадцатого элемента И соединен с первым входом десятого элемента сложения по модулю два, выход которого соединен с десятым выходом устройства, а второй вход - с выходом двадцать третьего элемента И, третий вход - с выходом тридцатого элемента И, выход двадцать четвертого элемента И соединен с первым входом одиннадцатого элемента сложения по модулю два, второй вход которого соединен с выходом тридцать первого элемента И, а выход - с одиннадцатым выходом устройства, двенадцатый выход которого соединен с выходом тридцать второго элемента И. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. 2 13243 1 2010.06.30 Известно устройство для вычисления полиномиальных симметрических булевых функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов 1. Недостатком устройства является ограниченное число переменных реализуемых полиномиальных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее четыре полусумматора,двадцать четыре элемента И, пятнадцать элементов сложения по модулю два, восемь входов и восемь выходов 2. Недостатком устройства также является ограниченное число переменных реализуемых полиномиальных симметрических булевых функций. Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет реализации полиномиальных симметрических булевых функций,зависящих от двенадцати переменных. Названный технический результат достигается путем введения в состав устройства блока вычисления полиномиальных симметрических булевых функций четырех переменных, одиннадцати элементов сложения по модулю и тридцати двух элементов И. Устройство для вычисления полиномиальных симметрических булевых функций содержит блок вычисления полиномиальных симметрических булевых функций восьми переменных, -й вход которого, где 1,8 , соединен с -м входом устройства. В отличие от прототипа устройство содержит тридцать два элемента И, одиннадцать элементов сложения по модулю два и блок вычисления полиномиальных симметрических булевых функций четырех переменных, -й вход которого, где 1,4 , соединен с (8)-м входом устройства. Первый выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен с первым входом первого элемента сложения по модулю два и первым входом -го элемента И, второй выход соединен с первым входом второго элемента сложения по модулю два и первым входом (8)-го элемента И, третий выход соединен с первым входом третьего элемента сложения по модулю два и первым входом(16)-го элемента И, четвертый выход соединен с первым входом четвертого элемента сложения по модулю два и первым входом (24) -го элемента И. При этом -й выход блока вычисления полиномиальных симметрических булевых функций восьми переменных соединен со вторым входом -го элемента сложения по модулю два, вторым входом -го элемента И, вторым входом (8)-го элемента И, вторым входом (16)-го элемента И и вторым входом (24)-го элемента И, (4)-й выход блока вычисления полиномиальных симметрических булевых функций восьми переменных соединен с первым входом (4)-го элемента сложения по модулю два, вторым входом(4)-го элемента И, вторым входом (12)-го элемента И, вторым входом (20)-го элемента И и вторым входом (28)-го элемента И. Выход -го элемента сложения по модулю два соединен с -м выходом устройства. Выход первого элемента И соединен с третьим входом второго элемента сложения по модулю два. Выход второго элемента И соединен с третьим входом третьего элемента сложения по модулю два, четвертый вход которого соединен с выходом девятого элемента И. Выход третьего элемента И соединен с третьим входом четвертого элемента сложения по модулю два, четвертый вход которого соединен с выходом десятого элемента И, а пятый вход соединен с выходом семнадцатого элемента И. 13243 1 2010.06.30 Выход четвертого элемента И соединен со вторым входом пятого элемента сложения по модулю два, третий вход которого соединен с выходом одиннадцатого элемента И, а четвертый вход соединен с выходом восемнадцатого элемента И, пятый вход соединен с выходом двадцать пятого элемента И. Выход пятого элемента И соединен со вторым входом шестого элемента сложения по модулю два, третий вход которого соединен с выходом двенадцатого элемента И, а четвертый вход соединен с выходом девятнадцатого элемента И, пятый вход соединен с выходом двадцать шестого элемента И. Выход шестого элемента И соединен со вторым входом седьмого элемента сложения по модулю два, третий вход которого соединен с выходом тринадцатого элемента И, а четвертый вход соединен с выходом двадцатого элемента И, пятый вход соединен с выходом двадцать седьмого элемента И. Выход седьмого элемента И соединен со вторым входом восьмого элемента сложения по модулю два, третий вход которого соединен с выходом четырнадцатого элемента И, а четвертый вход соединен с выходом двадцать первого элемента И, пятый вход соединен с выходом двадцать восьмого элемента И. Выход восьмого элемента И соединен с первым входом девятого элемента сложения по модулю два, выход которого соединен с девятым выходом устройства, а второй вход соединен с выходом пятнадцатого элемента И, третий вход соединен с выходом двадцать второго элемента И, четвертый вход соединен с выходом двадцать девятого элемента И. Выход шестнадцатого элемента И соединен с первым входом десятого элемента сложения по модулю два, выход которого соединен с десятым выходом устройства, а второй вход соединен с выходом двадцать третьего элемента И, третий вход соединен с выходом тридцатого элемента И. Выход двадцать четвертого элемента И соединен с первым входом одиннадцатого элемента сложения по модулю два, второй вход которого соединен с выходом тридцать первого элемента И, а выход соединен с одиннадцатым выходом устройства, двенадцатый выход которого соединен с выходом тридцать второго элемента И. На фигуре представлена схема устройства для вычисления полиномиальных симметрических булевых функций. Устройство содержит блок вычисления полиномиальных симметрических булевых функций восьми переменных 1, блок вычисления полиномиальных симметрических булевых функций четырех переменных 2, тридцать два элемента И 3-34, одиннадцать элементов сложения по модулю два 35-45, двенадцать входов 46-57 и двенадцать выходов 58-69. Булева функция,(х 1,х 2 х) называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1, х 2 х, называется полиномиальной (п.с.б.ф.). Пример 1 При 4 имеет место 1 х 1 х 2 х 3 х 42 х 1 х 2 х 1 х 3 х 1 х 4 х 2 х 3 х 2 х 4 х 3 х 4 4 4 3412313412423441234. 4 Обозначим(Х 1,Х 2), Х 1(х 1,х 2), 2(1,2 х), 1. Полиномиальная с.б.ф., 1, допускает декомпозиционное разложение вида 13243 1 2010.06.30 Пример 2 Выполним декомпозиционное разложение (1) полиномиальных с.б.ф. 121212 (1,2) при 12 и 8 Х 1(х 1, х 2 х 8), Х 2(х 9, х 10, х 11, х 12),Х(Х 1,Х 2),1,12 . Согласно (1) имеем 11218(1)14(2) 21228(1)18(1)14(2)24(2) 31238(1)28(1)14(2)18(1)24(2)34(2) 41248(1)38(1)14(2)28(1)24(2)18(1)34(2)44(2) 51258(1)48(1)14(2)38(1)24(2)28(1)34(2)18(1)44(2) 61268(1)58(1)14(2)48(1)24(2)38(1)34(2)28(1)44(2) 71278(1)68(1)14(2)58(1)24(2)48(1)34(2)38(1)44(2) 81288(1)78(1)14(2)68(1)24(2)58(1)34(2)48(1)44(2) 91288(1)14(2)78(1)24(2)68(1)34(2)58(1)44(2) 101288(1)24(2)78(1)34(2)68(1)44(2) 111288(1)34(2)78(1)44(2) 121288(1)44(2). Предлагаемое устройство предназначено для одновременного вычисления двенадцати полиномиальных с.б.ф. 1212 (Х),(х 1,х 2 х 12),1,12 , зависящих от двенадцати переменных, и построено согласно соотношениям из примера 2. В устройстве блок вычисления полиномиальных симметрических булевых функций восьми переменных 1 реализует на своих выходах полиномиальные с.б.ф. 1 (Х 1)- 8 (Х 1),8 8 а блок вычисления полиномиальных симметрических булевых функций четырех переменных 2 - полиномиальные с.б.ф. 1 (Х 2)-4 (Х 2). Элементы И 3-34 и элементы сложения по 4 4 модулю два 35-45 обеспечивают непосредственную реализацию полиномиальных с.б.ф. 1212 (Х) посредством функций 1 (1)- 8 (1) и 1 (2)-4 (2),1,12 . 8 8 4 4 Устройство для вычисления полиномиальных симметрических булевых функций работает следующим образом. На входы 46-57 поступают (в произвольном порядке) двоичные переменные х 1-х 12. На выходах 58, 59 69 реализуются соответственно 2 полиномиальные с.б.ф. 1 (Х), 12 (Х) 12 (Х),(х 1,х 2 х 12). 12 12 Достоинствами устройства для вычисления полиномиальных симметрических булевых функций являются высокое быстродействие, простая конструкция и широкие функциональные возможности. Источники информации 1. Патент РБ 9051, МПК 06 7/00, 2007. 2. Патент РБ 9147, МПК 06 7/00, 2007 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5