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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с 13666 1 2010.10.30 порогом восемь, -й, где 1,28, вход которого соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с -м информационным входом устройства, выход которого соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого с первого по четвертый соединены соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, причем первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым настроечным входом устройства, третий настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четвертый настроечный вход устройства соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, шестой настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, отличающееся тем, что устройство выполнено с шестью настроечными входами,а элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть - с девятью входами. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь, элемент И, шесть элементов ИЛИ, восемь входов и восемь выходов 1. Основным недостатком известного устройства является высокая конструктивная сложность, которая по числу входов логических элементов равна 82. Известное устройство, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных входов, семь настроечных входов и выход 2. Недостатком устройства является большое число внешних выводов, равное 16 (информационных входов - 8, настроечных входов -7 и выход). Устройство-прототип, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Изобретение направлено на решение следующей технической задачи уменьшение числа внешних выводов (уменьшение числа настроечных входов) устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. 2 13666 1 2010.10.30 Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, -й, где 1,28, вход которого соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с-м информационным входом устройства, выход которого соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Входы элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с первого по четвертый соединены соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым настроечным входом устройства, третий настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре. Четвертый настроечный вход устройства соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, шестой настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. В отличие от прототипа устройство выполнено с шестью настроечными входами, а элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть - с девятью входами. Основной технический результат изобретения заключается в уменьшении числа внешних выводов устройства (уменьшения числа настроечных входов) за счет изменения способа его настройки на реализацию (вычисление) полиномиальных симметрических булевых функций восьми переменных. На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 4, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5,восемь информационных входов 6 13, шесть настроечных входов 14 19 и выход 20. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных работает следующим образом. На информационные входы устройства 613 поступают (в произвольном порядке) значения переменных 1,28 на настроечные входы 1419 - сигналы настройки 1, 26 соответственно на выходе 20 реализуется (вычисляется) полиномиальная симметрическая булева функция восьми переменных Е 8 Е 8(1,28), определяемая вектором настройки(1,26), где 1,28. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно, что произвольная симметрическая булева функцияпеременных(1,2) с рабочими числами 1,2 (0) принимает значение 1 на тех и только тех наборах значений переменных 1,2 которые содержат ровно(1,2) единиц. Такая булева функция обозначается через 1 , 2 ( 1,2 ) . Если 1, то симметрическая булева функция(1,2) называется фундаментальной (или элементарной). 3 Симметрическая булева функцияпеременных 1 , 2 называется полиномиальной, если ее полином Жегалкина содержит(число сочетаний изпо ) различных элементарных конъюнкций ранга , где 1,2. Такая полиномиальная симметрическая булева функция обозначается через. Предлагаемое устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций Е 8 Е 8(х 1,х 2 х 8), зависящих от восьми переменных Е 81(Х)883857,8282838687,83837, 8484858687,858587, 868687,8787 и 8888. В таблице представлена настройка устройства на реализацию полиномиальных симметрических булевых функций восьми переменных. Первообразная функция предлагаемого устройства для вычисления полиномиальных симметрических булевых функций восьми переменных Е 88(1,28) имеет вид(1,28,1,26)34(1,28,1,2,2,3,3) 105(1,2 х 8,4,4)96(1,28,5)98(1,28, 6),где 1, если 12812 22 34,4 13 ( 1,2 8 , 1,2 ,2 ,3 ,3 )0 в противном случае,1, если 1282 45,5 10 ( 1,2 8 ,4 ,4 )0 в противном случае, 1, если 12856,6 9 ( 1,2 8 ,5 )0 в противном случае,1, если 12868,8 9 ( 1,2 8 ,6 )0 в противном случае,Пример Допустим, на выходе устройства требуется вычислить полиномиальную симметрическую булеву функцию восьми переменных 83(1,28)123124125126127128 134135136137138145146147 148156157158167168178234 235236237238245246247248 256257258267268278345346 347348356257358367368378 456457458467468478 567568578678. В таком случае, согласно таблице настроек (таблица), необходимо на настроечные входы устройства подать 2340 и 1561. В таком случае первообразная функция устройства принимает вид 13666 1 2010.10.3083(1,28)87(1,28)83(1,28). Дополнительным достоинством предлагаемого устройства для вычисления полиномиальных симметрических булевых функций восьми переменных является небольшая конструктивная сложность, которая (по числу входов логических элементов) равна 45. Источники информации 1. Патент РБ 11024, МПК 06 7/00, 2008. 2. Патент РБ 11785, МПК 06 7/00, 2009 (прототип). Устройство для вычисления полиномиальных симметрических булевых функций Сигналы настройки Выход 1 2 3 4 5 6 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5