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

Скачать PDF файл.

Текст

Смотреть все

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Авторы Городецкий Данила Андреевич Седун Андрей Максимович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных, содержащее элемент И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход 13809 1 2010.12.30 которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, третий вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, четвертый вход с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и пятый вход - с выходом элемента И, а выход - с выходом устройства, -й, где 1,29, информационный вход которого соединен с -м входом элемента И, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь,с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый вход которого соединен с первым настроечным входом устройства, второй настроечный вход которого соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, третий настроечный вход устройства соединен с десятым и одиннадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, четвертый настроечный вход устройства соединен с десятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, одиннадцатый и двенадцатый входы которого соединены с пятым настроечным входом устройства, шестой настроечный вход которого соединен с десятым и одиннадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, седьмой настроечный вход устройства соединен с десятым входом элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций девяти переменных. Известно устройство для вычисления симметрических булевых функцийпеременных, которое при 9 содержит девять элементов НЕ и девяносто один элемент И-НЕ 1. Недостатками известного устройства являются высокая конструктивная сложность (по числу входов логических элементов), а также низкое быстродействие, определяемое глубиной схемы. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления фундаментальных симметрических булевых функцийпеременных, содержащее при 9 три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, мажоритарный элемент с порогом шесть и мажоритарный элемент с порогом восемь 2. Устройство-прототип, как и заявляемое устройство, содержит элемент И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции девяти переменных. Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства для вычисления фундаментальных симметрических функций за счет вычисления (реализации) полиномиальных симметрических булевых функций девяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных содержит элемент И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. В отличие от прототипа устройство содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Второй вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, третий вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, четвертый вход - с выходом элемента- с выходом устройства. Причем -й, где 1,2,9, информационный вход устройства соединен с -м входом элемента И, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый вход которого соединен с первым настроечным входом устройства. Второй настроечный вход устройства соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, третий настроечный вход устройства соединен с десятым и одиннадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Четвертый настроечный вход устройства соединен с десятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, одиннадцатый и двенадцатый входы которого соединены с пятым настроечным входом устройства. Шестой настроечный вход устройства соединен с десятым и одиннадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, седьмой настроечный вход устройства соединен с десятым входом элемента И. На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций девяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять 4, элемент И 5, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6, девять информационных входов 715, семь настроечных входов 1622 и один выход 23. Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных работает следующим образом. На информационные входы устройства 715 поступают (в произвольном порядке) значения переменных 1,29, а на настроечные входы 1622 - сигналы настройки 0,16, значения которых принадлежат множеству 0,1. На выходе устройства 23 реализуется полиномиальная симметрическая булева функ ция 99 (1 ,2 9 ) , определяемая вектором настройки( 0 , 1 6 ) , где 1,29. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций девяти переменных. Известно, что произвольная симметрическая булева функцияпеременных(1,2) с рабочими числами 1,2 (0) принимает значение 1 на тех и только тех наборах значений переменных 1,2 которые содержат ровно(1,2) единиц. Такая булева функция обозначается 1 , 2 (1 ,2 ) . Ес ли 1, то симметрическая булева функция(1 ,2 ) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 , 2 ( ) называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг которых равен (1). Такая полиномиальная симметрическая булева функцияпеременных обозначается( ) . Очевидно, что полином Жегалкина функции( ) содержит(число сочетаний изпо ) элементарных конъюнкций ранга , где 13809 1 2010.12.30 Заявляемое устройство синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций девяти перемен 79 ( )97 ( ),8 ( )98 ( )99 ( ),9 ( )99 ( ). 9 9 Посредством таблицы представлена настройка устройства на вычисление полиномиальных симметрических булевых функций девяти переменных. 0 1 2 3 4 5 6 Первообразная функция устройства для вычисления полиномиальных симметрических булевых функций имеет вид 4(1 ,2 9 ,0 , 1 6 )12 (1 ,2 9 ,0 , 1 , 1 )5 811 (1 ,2 9 ,2 ,2 )12 (1 ,2 9 ,3 ,4 ,4 )911 (1 ,2 9 ,5 ,5 )1 296 . Рассмотрим пример. Допустим, что на выходе устройства требуется вычислить (реализовать) полиномиальную симметрическую булеву функцию девяти переменных 2 299 (1 ,2 9 ) , т.е. 29 ( 1 ,2 ,,9 )1213141516171819 232425262728293 43 53 63 73 83 945464748495657585 96 7686 97 8798 9. В таком случае (согласно таблице настроек) необходимо положить 0360 и 12451. Тогда первообразная функция устройства принимает вид(1 ,2 9 ,0,1,1,0,1,1,0)12 (1 ,2 9 ,0,1,1)5 811 (1 ,2 9 ,1,1)12 (1 ,2 9 ,0,1,1)9 211 (1 ,2 9 ,1,1)1 2909 (1 ,2 9 )3 6 79 (1 ,2 9 )9 (1 ,2 9 )9 (1 ,2 9 )2 3 6 7 29 ( )9 ( )9 ( )9 ( )9 ( ). Дополнительными достоинствами устройства для вычисления полиномиальных симметрических булевых функций девяти переменных являются а) низкая конструктивная сложность (по числу входов логических элементов), равная 61 б) небольшое число внешних выводов, равное 17 в) высокое быстродействие, определяемое глубиной схемы и равное 2. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.

МПК / Метки

МПК: G06F 7/00

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

Код ссылки

<a href="http://bypatents.com/5-13809-ustrojjstvo-dlya-vychisleniya-polinomialnyh-simmetricheskih-bulevyh-funkcijj.html" rel="bookmark" title="База патентов Беларуси">Устройство для вычисления полиномиальных симметрических булевых функций</a>

Похожие патенты