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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных, содержащее первый и второй элементы ИСКЛЮЧАЮЩЕЕ ИЛИ и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а -й,где 1, 2, вход соединен с выходом -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, -й, где 1,25, вход которого соединен с -м информационным входом устройства, -й настроечный вход которого соединен с шестым и седьмым входами -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а третий настроечный вход соединен с восьмым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, отличающееся тем, что первый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ выполнен с порогом четыре, второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ выполнен с порогом пять содержит элемент И, -й вход которого соединен с -м информационным входом устройства, третий настроечный вход которого соединен с шестым входом элемента И, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. 13818 1 2010.12.30 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций пяти переменных. Известно устройство для вычисления симметрических булевых функций пяти переменных, содержащее мажоритарный элемент с порогом два, мажоритарный элемент с порогом три, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом пять, мажоритарный элемент с порогом шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,пять информационных входов, шесть настроечных входов и выход 1. Конструктивная сложность устройства (по числу входов логических элементов) равна 36, а его быстродействие, определяемое глубиной схемы, составляет 2, где- усредненная задержка на один логический элемент. Недостатком известного устройства является большая конструктивная сложность (по числу входов логических элементов), равная 36. Устройство, предназначенное для вычисления произвольных симметрических булевых функций пяти переменных, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, мажоритарный элемент с порогом три, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и выход 2. Конструктивная сложность устройства (по числу входов логических элементов) равна 28, а быстродействие составляет 2, где- задержка на один логический элемент. Недостатком устройства-прототипа является большое число внешних выводов (12 входов и выход). Как и предлагаемое изобретение, устройство-прототип содержит два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а входы соединены с выходами первого и второго элементов ИСКЛЮЧАЮЩЕЕ ИЛИ. Изобретение направлено на решение следующей технической задачи - уменьшение числа внешних выводов устройства для вычисления полиномиальных симметрических булевых функций пяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных содержит первый и второй элементы ИСКЛЮЧАЮЩЕЕ ИЛИ и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а -й,где 1,2, вход соединен с выходом -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, -й, где 1,25, вход которого соединен с -м информационным входом устройства. Причем -й настроечный вход устройства соединен с шестым и седьмым входами -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а третий настроечный вход соединен с восьмым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. В отличие от прототипа первый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ выполнен с порогом четыре, второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ выполнен с порогом пять и устройство содержит элемент И, -й вход которого соединен с -м информационным входом устройства. Третий настроечный вход устройства соединен с шестым входом элемента И, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Названный технический результат достигается с помощью 1) введения в логическую схему устройства информационных входов 2) изменения порога элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3) использования нового логического элемента (элемента И). На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций. 13818 1 2010.12.30 Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент И 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 3, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4, пять информационных входов 5 9, три настроечных входа 10, 11 и 12, выход 13. Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных работает следующим образом. На входы устройства 59 поступают (в произвольном порядке) значения переменных 1,25, на настроечные входы 10, 11, 12 сигналы настройки 1, 2, 3, значения которых принадлежат множеству 0,1. На выходе устройства 13 вычисляется (реализуется) полиномиальная симметрическая булева функция(1,2,3,4,5), определяемая вектором настройки(1,2,3). Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций пяти переменных. Известно, что произвольная симметрическая булева функцияпеременных(1,2) с рабочими числами 1,2 (0) принимает значение 1 на тех и только тех наборах значений переменных 1,2 которые содержат ровно(1,2) единиц. Такая булева функция обозначается через 1 , 2 ( 1,2 ) . Если 1, то симметрическая булева функция( 1 ,2 ) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 , 2 называется полиномиальной, если ее полином Жегалкина содержит всевозможные элементарные конъюнкции, ранг которых равен , где 1. Такая полиномиальная симметрическая булева функцияпеременных обозначается через( ) . Очевидно, что полином Жегалкина функции( ) содержит(число сочетаний из по ) элементарных конъюнкций ранга , где 1,2. Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных (фигура) синтезировано на основе применения следующих аналитических представлений булевых функций 5 ( )5 (1 ,2 5 ) , где 1,25 1 2 1 ( )5 ( )53 ( )55 ( ),5 ( )52 ( )53 ( ),5 43 ( )53 ( ),5 ( )54 ( )55 ( ) и 5 ( )55 ( ). 5 5 Первообразная функция заявляемого устройства имеет вид 4 58 (1 ,2 ,3 ,4 ,5 , 1 ,2 ,2 )7 (1 ,2 ,3 ,4 ,5 ,3 ,3 ). Рассмотрим пример настройки устройства. Предположим, что на выходе устройства 13 требуется реализовать полиномиальную симметрическую функцию 3 43 545 . В таком случае, согласно таблице настроек (см. таблицу), необходимо на настроечные входы 10, 11 и 12 устройства подать значения 10 и 231 соответственно. Тогда первообразная функция будет иметь вид 5 1 0 1 5 Основным достоинством предлагаемого устройства для вычисления полиномиальных симметрических булевых функций пяти переменных является небольшое число внешних выводов (пять информационных и три настроечных входов, выход). Отметим, что три настроечных входа являются оптимальными при условии простой настройки устройства на вычисление пяти полиномиальных симметрических булевых функций пяти переменных. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.