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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ВОСЬМИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, характеризующееся тем, что содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и первый, второй, третий и четвертый элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, выполненные с порогами четыре, пять, восемь и девять соответственно, выход -го из которых, где 1, 2, 3, 4, соединен с -м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, -й информационный вход которого, где 1, 2, , 8, соединен с -м входом -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым настроечным входом устройства, третий настроечный вход которого соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять четвертый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с 16552 1 2012.12.30 порогом восемь, десятый и одиннадцатый входы которого соединены с пятым настроечным входом устройства и с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных и семь настроечных входов,выход 1. Сложность устройства (по числу входов логических элементов) равна 46, а быстродействие, определяемое глубиной логической схемы, составляет 2, где- задержка на один логический элемент. Недостатком известного устройства является большое число внешних выводов, равное 16 (информационных входов - 8, настроечных входов - 7 и выход). Известное устройство, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого соединены с выходами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами четыре, пять и восемь, а выход - с выходом устройства. Наиболее близким по функциональным возможностям и конструкции техническим решением к заявляемому устройству является устройство, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных и шесть настроечных входов, выход 2. Недостатком устройства является большое число внешних выводов, равное 15 (информационных входов - 8, настроечных входов - 6 и выход). Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и три элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами четыре, пять и восемь, причем выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены со входами элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Изобретение направлено на решение следующей технической задачи уменьшение числа внешних выводов устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных характеризуется тем, что содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и первый, второй, третий и четвертый элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, выполненные с порогами четыре, пять, восемь и девять соответственно. Выход -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, где 1, 2, 3, 4, соединен с -м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, -й информационный вход которого, где 1, 2, , 8, соединен с -м входом -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. Первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым настроечным входом устройства, третий настроечный вход которого соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. 2 16552 1 2012.12.30 Четвертый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, десятый и одиннадцатый входы которого соединены с пятым настроечным входом устройства и с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять. Основной технический результат изобретения заключается в уменьшении числа внешних выводов устройства (в уменьшении числа настроечных входов) за счет использования элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, а также посредством изменения способа его настройки на реализацию (вычисление) полиномиальных симметрических булевых функций восьми переменных. На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 3,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять 4, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5, восемь информационных входов 613, пять настроечных входов 1418 и выход 19. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных работает следующим образом. На информационные входы устройства 613 поступают (в произвольном порядке) значения переменных 1, 2, , 8, на настроечные входы 1418 - сигналы настройки 1, 2, , 5 соответственно, принимающие значения из множества 0,1, на выходе устройства 19 реализуется (вычисляется) полиномиальная симметрическая булева функция восьми переменных 8 ( 1 ,2 ,,8 ) , определяемая двоичным вектором настройки(1, 2, , 5), где 1, 2, , 8. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно, что произвольная симметрическая булева функцияпеременных(1, 2, , ) с рабочими числами 1, 2, ,(01) принимает значение 1 на тех и только тех наборах значений переменных 1, 2, , , которые содержат ровно а (1, 2, , ) единиц. Такая булева функция обозначается через 1 ,2 , ,(1 ,2 ,,) . Если 1, то симметрическая булева функция( 1 ,2 ,,) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 ,2 , ,называется полиномиальной (или полиномиально-однородной), если ее полином Жегалкина содержит ровно С(число сочетаний изпо ) различных элементарных конъюнкций ранга , где 1, 2, , . Такая симметрическая булева функция обозначается через. Заявляемое устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций 8 ( 1 ,2 ,,) восьми переменных 1 18838587,8 2882838687,3 488387,884858687,5 688587,88687,7887 и 888. 8 Посредством таблицы представлен способ настройки устройства на реализацию полиномиальных симметрических булевых функций восьми переменных. 16552 1 2012.12.30 Первообразная функция устройства для вычисления полиномиальных симметриче ских булевых функций 8 (1 ,2 8 ) имеет вид 4(1 ,2 8 ,1 ,2 5 )11 (1 ,2 8 ,1 ,2 ,2 )5 8 910 (1 ,2 8 ,3 ,3 )11 (1 ,2 8 ,4 ,5 ,5 )10 (1 ,2 8 ,5 ,5 ), где 1, если 12812 24,4 11 (1 ,2 ,,8 ,1 ,2 ,2 )0 в противном случае,1, если 1282 35,5 10 ( 1 ,2 ,,8 ,3 ,3 )0 в противном случае,1, если 12842 58,8 11 ( 1 ,2 ,,8 ,4 ,5 ,5 )0 в противном случае,1, если 1282 59,9 10 ( 1 ,2 ,,8 ,5 ,5 )0 в противном случае. Рассмотрим пример вычисления (реализации) на выходе устройства полиномиальной симметрической булевой функции восьми переменных. Пример. Допустим, на выходе 19 устройства требуется вычислить полиномиальную симметрическую булеву функцию восьми переменных 38 (1 ,2 ,,8 )1231241251261 271281 341 3 51 361 3 71 381 451 461 471 481 561 571 581 671681 7823423 523 623 723824524624724 82 5 625 72 582 6 72 682 7 83 4 53 4 63 473 4 83 5 63 5 73 583 673 683 7 84 5 635 74584 6746 84 7 85 6 75 6 85 7 86 7 8. 3 Для вычисления на выходе устройства функции 8 (1 ,2 8 ) , согласно таблице настроек (таблица), необходимо на настроечные входы устройства подать 230 и 1451. В таком случае первообразная функция устройства принимает вид 4(1 ,2 ,,8 , 1, 0, 0, 1, 1)11 ( 1 ,2 ,,8 , 1, 0, 0)5 8 910 (1 ,2 ,,8 , 0, 0)11 ( 1 ,2 ,,8 , 1, 1, 1)10 (1 ,2 ,,8 , 1, 1)83 ( 1 ,2 ,,8 )85 ( 1 ,2 ,,8 )85 (1 ,2 ,,8 )87 (1 ,2 ,,8 )83 (1 ,2 ,,8 )87 (1 ,2 ,,8 )83 (1 ,2 ,,8 )87 ( 1 ,2 ,,8 )83 ( 1 ,2 ,,8 ). Основным достоинством заявляемого устройства для вычисления полиномиальных симметрических булевых функций восьми переменных является относительно небольшое число внешних выводов, которое равно 14 (восемь информационных и пять настроечных входов, выход). Число внешних выводов устройства-прототипа равно 15. При этом устройство имеет небольшую конструктивную сложность, равную 48 (сложность устройства-прототипа равна 45). Следует отметить, что быстродействие устройства совпадает с быстродействием устройства-прототипа. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5