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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, -й, где 1,2 8, вход которого соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с -м информационным входом устройства, входы, с первого по четвертый, элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединены соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом 11785 1 2009.04.30 шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, причем первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым настроечным входом устройства, третий настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четвертый настроечный вход устройства соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, десятый вход которого соединен с шестым настроечным входом устройства, седьмой настроечный вход которого соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее четыре полусумматора, двадцать четыре элемента И, пятнадцать элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь входов и восемь выходов 1. Недостатками известного устройства являются высокая конструктивная сложность (по числу входов логических элементов) и низкое быстродействие, определяемое глубиной схемы. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций шести переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть информационных входов, четыре настроечных входа и один выход 2. Недостатком устройства является невозможность вычисления полиномиальных симметрических булевых функций восьми переменных. Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть. В отличие от прототипа устройство содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, -й, где 1, 2, , 8, вход которого соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с -м информационным входом устройства. Входы, с первого по четвертый, элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединены соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым настроечным входом устройства. 2 11785 1 2009.04.30 Третий настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четвертый настроечный вход устройства соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Пятый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, десятый вход которого соединен с шестым настроечным входом устройства, седьмой настроечный вход которого соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Основной технический результат изобретения заключается в расширении функциональных возможностей устройства для вычисления полиномиальных симметрических булевых функций шести переменных за счет реализации (вычисления) полиномиальных симметрических булевых функций восьми переменных. Названный эффект достигается путем введения в логическую схему устройства-прототипа нового логического элемента(элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь). На чертеже (фигура) 1 представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 4, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5,восемь информационных входов 613, семь настроечных входов 1420 и выход 21. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных работает следующим образом. На информационные входы устройства 6 13 поступают (в произвольном порядке) значения переменных 1, 2, , 8 на настроечные входы 1420 - сигналы настройки 1, 2, , 7 соответственно на выходе 21 реализуется (вычисляется) полиномиальная симметрическая булева функция восьми перемен ных 88 ( 1 ,2 ,,8 ) , определяемая вектором настройки(1, 2, , 7), где 1, 2, , 8. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно, что произвольная симметрическая булева функцияпеременных(1, 2, , ) с рабочими числами 1, 2, ,(0) принимает значение 1 на тех и только тех наборах значений переменных 1, 2, , , которые содержат ровно(1, 2, , ) единиц. Такая булева функция обозначается через 1, 2 (1 ,2 , ,) . Если 1, то симметрическая булева функция(1 ,2 , ,) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 , 2 называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг которых равен , где 1. Полиномиальная симметрическая булева функцияпере менных обозначается через. Очевидно, что полином Жегалкина функции, где 1, 2, , . Предлагаемое устройство (фигура) 1 синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций вось В таблице представлена настройка устройства на реализацию полиномиальных симметрических булевых функций восьми переменных. Первообразная устройства для вычисления полиномиальных симметрических булевых функций 8 8 (1 ,2 8 ) имеет вид 4(1 ,2 ,,8 ,1 ,2 ,,7 )13 (1 ,2 ,,8 ,1 ,2 ,2 ,3 ,3 )5 6 810 (1 ,2 ,,8 ,4 ,4 )10 (1 ,2 ,,8 ,5 ,6 )9 (1 ,2 ,,8 ,7 ) , где 1, если 1281222344 13 (1 ,2 , ,8 ,1 ,2 ,2 ,3 ,3 )0 в противном случае ,1, если 1282455 10 (1 ,2 ,,8 ,4 ,4 )0 в противном случае ,1, если 1285666 10 (1 ,2 ,,8 ,5 ,6 )0 в противном случае ,1, если 128788 9 (1 ,2 , ,8 ,7 )0 в противном случае. Пример Допустим, на выходе устройства требуется реализовать полиномиальную симметрическую булеву функцию 28 ( 1 ,2 ,,8 )12131415161718 23242526272 83 43 53 63 7384546474 8565 758676878. Для этого, согласно таблице настроек (таблица), необходимо 13560 и 2471. В таком случае первообразная устройства принимает следующий вид Дополнительным достоинством устройства для вычисления полиномиальных симметрических булевых функций восьми переменных является небольшая конструктивная 11785 1 2009.04.30 сложность, которая (по числу входов логических элементов) равна 46. Также отметим высокое быстродействие устройства, которое равно 2, где- усредненная задержка на один логический элемент. Источники информации 1. Патент РБ 9147, МПК 06 7/00, 2007. 2. Патент РБ 11028, МПК 06 7/00, 2008 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5