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

Номер патента: 16358

Опубликовано: 30.10.2012

Автор: Супрун Валерий Павлович

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

Текст

Смотреть все

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полусимметрических булевых функций пяти переменных,содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с первого по одиннадцатый элементы И, выход -го из которых, где 1, 211, соединен с (1)-м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА второй настроечный вход устройства соединен с первым входом -го элемента И, где 1, 2, 3, второй вход которого соединен с -м информационным входом устройства, с-м инверсным входом четвертого элемента И, с -м входом пятого элемента И, с первым входом (6)-го элемента И, с -м инверсным входом десятого элемента И и с -м входом одиннадцатого элемента И, четвертый вход которого соединен с четвертым информационным входом устройства, со вторым входом (6)-го элемента И, с первым входом десятого элемента И и с первым входом шестого элемента И, второй вход которого соединен с 16358 1 2012.10.30 третьим настроечным входом устройства четвертый настроечный вход устройства соединен с первым входом четвертого элемента И, пятый настроечный вход устройства соединен с четвертым входом пятого элемента И, шестой настроечный вход устройства соединен с третьим входом (6)-го элемента И, седьмой настроечный вход устройства соединен со вторым входом десятого элемента И, восьмой настроечный вход устройства соединен с пятым входом одиннадцатого элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полусимметрических булевых функций пяти переменных. Известно устройство для вычисления симметрических булевых функций пяти переменных, которое содержит мажоритарный элемент с порогом два, мажоритарный элемент с порогом три, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом пять, мажоритарный элемент с порогом шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пять информационных и шесть настроечных входов, выход 1. Известное устройство, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислять (реализовать) полусимметрические булевы функции пяти переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, мажоритарный элемент с порогом три, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и выход 2. Устройство-прототип предназначено для вычисления произвольных симметрических булевых функций пяти переменных. Конструктивная сложность устройства (по числу входов логических элементов) равна 28, а быстродействие составляет 2, где- задержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять произвольные полусимметрические булевы функции пяти переменных. Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления симметрических булевых функций пяти переменных за счет реализации полусимметрических булевых функций пяти переменных. Устройство для вычисления полусимметрических булевых функций пяти переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Также устройство содержит с первого по одиннадцатый элементы И, выход -го из которых, где 1, 211, соединен с (1)-м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Второй настроечный вход устройства соединен с первым входом -го элемента И, где 1, 2, 3, второй вход которого соединен с -м информационным входом устройства, с -м инверсным входом четвертого элемента И, с -м входом пятого элемента И, с первым входом (6)-го элемента И, с -м инверсным входом десятого элемента И и с -м входом одиннадцатого элемента И. 2 16358 1 2012.10.30 Четвертый вход одиннадцатого элемента И соединен с четвертым информационным входом устройства, со вторым входом (6)-го элемента И, с первым входом десятого элемента И и с первым входом шестого элемента И, второй вход которого соединен с третьим настроечным входом устройства. Четвертый настроечный вход устройства соединен с первым входом четвертого элемента И, пятый настроечный вход устройства соединен с четвертым входом пятого элемента И. Шестой настроечный вход устройства соединен с третьим входом (6)-го элемента И, седьмой настроечный вход устройства соединен со вторым входом десятого элемента И, восьмой настроечный вход устройства соединен с пятым входом одиннадцатого элемента И. Названный технический результат достигается с помощью введения в логическую схему устройства новых элементов (элементов И) с последующим изменением соединений между логическими элементами схемы. На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций пяти переменных. Устройство для вычисления полусимметрических булевых функций пяти переменных содержит одиннадцать элементов И 111, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 12,четыре информационных входа 13, 14, 15 и 16, восемь настроечных входов 1724 и выход 25. Устройство для вычисления полусимметрических булевых функций пяти переменных работает следующим образом. На информационные входы устройства 13, 14, 15 и 16 поступают значения переменных х 1, х 2, х 3 и х 5, на настроечные входы 1724 - сигналы настройки 0, 7, значения которых принадлежат множеству 0, 1,4 ,4 . На выходе устройства 25 вычисляется полусимметрическая булева функция(1, 5), где 11, 2, 3, 4, определяемая вектором настройки(0, 1 7). Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций пяти переменных. Произвольная булева функцийпеременных(1, 2 ) называется симметрической, если она не меняет своего значения после перестановки любой пары переменныхи , гдеи ,1, 2 . Симметрическая булева функция(1, 2 ) определяется множеством рабочих чисел 1, 2 . Функцияпринимает единичные значения на тех и только тех наборах значений переменных 1, 2 , которые содержат ровноединиц, где 0, 1 и 01. Симметрическая булева функция(1, 2 ) взаимно однозначно представляется (1)-разрядным двоичным вектором (локальным кодом)(0, 1 ), гдезначение функциина (любом) наборе значенийпеременных, содержащем(0) единиц, т.е.1 тогда и только тогда, когда- рабочее число . Полином Жегалкинасимметрической булевой функции , зависящей отпеременных 1, 2 , имеет вид 01(12)2(121-1) 12,где (1)-разрядный двоичный вектор(0, 1 ) называется вектором коэффициентов полиномаи является для функции(1, 2 ) единственным. Метод преобразования локального кода(0, 1 ) в вектор коэффициентов 16358 1 2012.10.30 рических булевых функций (Известия АН СССР. Техническая кибернетика. - 1985. -4. С. 123-127). Булева функция(3) переменных(1, 2 ) называется полусимметрической, если булевы функции 0(0)0(1, 0) и 1(1)1(1, 1) являются симметрическими, зависящими от переменных 11, 2 -1. Такая булева функция обозначается через(1, ). Любая симметрическая булева функцияпеременныхявляется полусимметрической, а обратное утверждение не всегда верно. Другими словами, симметрические булевы функцииявляются частным случаем полусимметрических функций(1, ). Для булевой функции(1, ) имеет место формула дизъюнктивного разложения по переменнойвида(1,)01 . Симметрические булевы функции -1 переменных 00(1), 11(1) могут быть 0 заданы посредством -разрядных двоичных векторов (0 )0 , 1 0 1 и 0) или посредством векторов коэффициентов ( )( Если для векторов (0) и (1) выполняется условие 011 , где 1, 2 -1, то полусимметрическая булева функция(1, ) является симметрической, зависящей отпеременных. Двоичный вектор 0), (1 является локальным кодом булевой функции(1, ). Так как векторимеет 2 разрядов, то число различных функций вида(1, ) равно 224 (число симметрических булевых функцийпеременныхравно 21). Первообразная функция логической схемы (фигура) устройства для вычисления полусимметрических булевых функций пяти переменных(1, 5) имеет вид где 0 , 1 70, 1,4 ,4 . Настройка устройства на вычисление полусимметрических булевых функций(1, 5) при условии, что для симметрических булевых функций 00(1, 2, 3, 4) 0 и 11 (1, 2, 3, 4 ) известны их локальные коды (0 )(0 , 1 0 ) ,0 4(1 )1 , 1 1 , осуществляется по следующим формулам 0 1 4 16358 1 2012.10.30 Если реализуемая функция(1, 5) представлена посредством полинома Жегал 0 кина , т.е. известны вектора коэффициентов(0 )0 , 1 0 ,(1 )1 , 1 1 0 4 0 1 4 полиномов Жегалкина (0) и (1), то сигналы настройки 0, 1 7 можно вычислять по формулам. Рассмотрим три примера построения вектора(0, 17) - вектора настройки логической схемы устройства (фигура) на реализацию полусимметрических булевых функций(1, 5), а также симметрической булевой функциипяти переменных. Пример 1. Допустим, что на выходе 25 устройства (фигура) требуется вычислить полусимметрическую булеву функцию Используя формулы (3), получаем 00, 10,24 , 30, 44, 54, 64 и 71. Следовательно, для реализации на выходе 25 заданной булевой функции(1, 5) необходимо на настроечные входы 17, 18 и 20 подать значение 0, на настроечный вход 19 - значение 4 , на настроечные входы 21, 22 и 23 - значение 4 и на настроечный вход 24 - значение 1. В качестве проверки подставим найденные значения вектора настройки 0, 0,4 , 0,4 ,4 ,4 , 1 в выражение первообразной функции устройства, логическая схема которой приведена на фигуре. В таком случае выражение (2) принимает вид 16358 1 2012.10.30 Пример 2. Предположим, что на выходе 25 устройства требуется вычислить полусимметрическую булеву функцию(1, 5), заданную посредством полинома Жегалкина 0 0(0 )0 , 1 ,0 ,3 ,0(1, 0, 0, 0, 1),(1 )1 , 1 , 1 , 1 , 1(1, 1, 0, 0, 0 ). 0 2 4 0 1 2 3 4 В данном случае вектор настройки(0,17) будем вычислять по формулам(4). Тогда получим 01, 10, 20, 34, 44, 51, 60 и 74. В этой связи для реализации на выходе 25 булевой функции(1, 5) необходимо на настроечные входы 17 и 22 подать значение 1, на настроечные входы 18, 19 и 23 - значение 0 и на настроечные входы 20, 21 и 24 - значение 4. Отметим, что в данном случае первообразная функция устройства (2) принимает вид 12301234451 152 153 15123051234511234(1234 )512345 . Пример 3. Пусть требуется на выходе 25 устройства реализовать симметрическую булеву функцию ( )12345 . Так как 0 (1 )1234 и 1(1)1, то (0)(0, 1, 1, 1, 1) и (1)(1, 1, 1, 1, 1). Согласно формулам (3), получаем вектор настройки 1, 0,4 , 0, 0, 0,4 ,0 . Следовательно, для реализации на выходе 25 симметрической булевой функциинеобходимо на настроечный вход 17 подать значение 1, на настроечные входы 18, 20, 21, 22 и 24 - значение 0 и на настроечные входы 19 и 23 - значение 4 . При этом первообразная функция (2) принимает вид 1234512305112341234511234512345 . Основным достоинством заявляемого устройства являются широкие функциональные возможности. Устройство реализует любую из 1024 полусимметрических булевых функций, зависящих от переменных 1, 2, 3, 4, 5. Отметим, что устройство-прототип предназначено для вычисления симметрических булевых функций пяти переменных 1, 2, 3, 4, 5, число которых равно 64. При этом заявляемое устройство и устройство-прототип имеют одинаковое быстродействие, определяемое глубиной схемы. Кроме того, оба устройства имеют одинаковое число внешних выводов. Источники информации 1. Патент РБ 2793, МПК 06 7/00, 1999. 2. Патент РБ 11275, МПК 06 7/00, 2008 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.

МПК / Метки

МПК: G06F 7/00

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

Код ссылки

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

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