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

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

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

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

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

Текст

Смотреть все

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полусимметрических булевых функций пяти переменных,характеризующееся тем, что содержит с первого по пятый элементы И, мажоритарный элемент с порогом два, первый и второй элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,(1)-й вход которого, где 1, 2, 3, 4, соединен с выходом -го элемента И, первый вход которого соединен с (1)-м настроечным входом устройства, -й информационный вход которого соединен с -м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, -м входом мажоритарного элемента с порогом два и с -м входом пятого элемента И, выход которого соединен с инверсным входом второго элемента И и со вторым входом четвертого элемента И, выход мажоритарного элемента с порогом два соединен со вторым входом второго элемента И и со вторым входом третьего элемента И, третий вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и со вторым входом первого элемента И. 16715 1 2012.12.30 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полусимметрических булевых функций пяти переменных. Известно устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, мажоритарный элемент с порогом три, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и выход 1. Известное устройство, как и изобретение, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком известного устройства являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полусимметрические булевы функции пяти переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к заявляемому устройству является устройство для вычисления полусимметрических булевых функций пяти переменных, которое содержит одиннадцать элементов И,элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четыре информационных и восемь настроечных входов, выход 2. Устройство-прототип предназначено для вычисления полусимметрических булевых функций пяти переменных(1, 5), где 11, 2, 3, 4. Конструктивная сложность устройства (по числу входов логических элементов) равна 47, а быстродействие составляет 2, где- задержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит с первого по четвертый элементы И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход - с первым настроечным входом устройства, (1)-й настроечный вход которого, где 1, 2, 3, 4, соединен с первым входом -го элемента И,выход которого соединен с (1)-м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа является высокая конструктивная сложность, равная 47. Изобретение направлено на решение следующей технической задачи уменьшение конструктивной сложности устройства для вычисления полусимметрических булевых функций пяти переменных. Устройство для вычисления полусимметрических булевых функций пяти переменных характеризуется тем, что содержит с первого по пятый элементы И, мажоритарный элемент с порогом два, первый и второй элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, (1)-й вход которого, где 1, 2, 3, 4, соединен с выходом -го элемента И, первый вход которого соединен с (1)-м настроечным входом устройства. Причем -й информационный вход устройства соединен с -м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с -м входом мажоритарного элемента с порогом два и с -м входом пятого элемента И. Выход пятого элемента И соединен с инверсным входом второго элемента И и со вторым входом четвертого элемента И. Выход мажоритарного элемента с порогом два соединен со вторым входом второго элемента И и со вторым входом третьего элемента И. Третий вход третьего элемента И соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и со вторым входом первого элемента И. Названный технический результат достигается посредством введения в логическую схему устройства мажоритарного элемента с порогом два и второго элемента СЛОЖЕ 2 16715 1 2012.12.30 НИЕ ПО МОДУЛЮ ДВА с последующим изменением соединений между логическими элементами схемы. На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций пяти переменных. Устройство для вычисления полусимметрических булевых функций пяти переменных содержит два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1 и 2, мажоритарный элемент с порогом два 3, пять элементов И 48, четыре информационных входа 9, 10, 11 и 12, пять настроечных входов 1317, выход 18. Устройство для вычисления полусимметрических булевых функций пяти переменных работает следующим образом. На информационные входы 9, 10, 11 и 12 устройства поступают (в произвольном порядке) значения переменных 1, 2, 3 и 4, на настроечные входы 1317 - сигналы настройки 0, 1, 2, 3, 4, значения которых принадлежат множеству 0, 1,5 ,5. На выходе 18 устройства вычисляется (реализуется) полусимметрическая булева функция(1, 5), где 11, 2, 3, 4, определяемая вектором настройки(0, 1, 2, 3, 4). Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций пяти переменных. Произвольная булева функцияпеременных(1, 2 ) называется симметрической, если она не меняет своего значения после перестановки любой пары переменныхи , гдеи ,1, 2 . Симметрическая булева функция(1, 2 ) определяется множеством рабочих чисел 1, 2 . Функцияпринимает единичные значения на тех и только тех наборах значений переменных , 2 , которые содержат ровноединиц, где 0, 1 и 01. Такая функция обозначается как 1 ,2 (,2 ) . Если 1, то функция(1 ,2 ) называется фундаментальной (элементарной) симметрической булевой функциейпеременных с рабочим числом, равным . Симметрическая булева функция(,2) взаимно однозначно представляется(1)-разрядным двоичным вектором (локальным кодом)(0, 1 ), гдезначение функциина (любом) наборе значенийпеременных, содержащем(0) единиц, т.е.1 тогда и только тогда, когда- рабочее число функции . Булева функцияпеременных(1, 2 ) называется полусимметрической, если булевы функции 0(0) и 1(1) являются симметрическими, зависящими от переменных 1, 2 -1, где 3. Такая булева функция обозначается как(1, ). Формула дизъюнктивного разложения функции(1, ) по переменным множества 1 имеет вид 1(1,)01 (1 )0 1 (1 )1 11 (1 )1 ,(1) где 11 (1 ) - фундаментальные симметрические булевы функции -1 переменных, а булевы функциизависят только от одной переменной . Здесь 0, 1 -1. Двоичный 2-разрядный вектор 0), (1) (-1 называется локальным кодом полусимметрической булевой функции(1, ). Наряду с дизъюнктивным разложением (1) существует полиномиальное разложение функции(1, ) по -1 переменным вида 1 где 11 (1 ) - полиномиально-однородные симметрические булевы функции -1 переменных и 0 1 (1 )1 , а функциизависят от функций, где 0, 1 -1, и вычисляются по формулам, приведенным в статье Супруна В.П. и Городецко 3 16715 1 2012.12.30 го Д.А. Реализация бисимметрических булевых функций логическими схемами // Известия вузов. Приборостроение. - 2010. -5. - С. 17-25. В частности, если 8, то 0 0 , 1 0 1 ,2 0 2 , 3 0 1 2 3 , 4 0 4 ,(3)5 0 1 4 5 , 6 0 2 4 6 , 7 0 1 2 7 . Отметим, что локальные кодыибулевых функцийН(х) и(х) связаны между собой, согласно формулам (3), где 0, 1 7. Если 5, то формулы (1)-(3) принимают вид 1 3 (1 )3 (5 )4 (1 )4 (5 ),4 4 где (0)(0), (1 )( 0 )(1 ) , ( 2 )( 0 )( 2 ) ,(3 )( 0 )(1 )( 2 )( 3 ) и ( 4 )( 0 )( 4 ) . Логическая схема устройства для вычисления полусимметрических булевых функций пяти переменных, синтезированная на основе применения полиномиального разложения(4), приведена на фигуре. Первообразная функция устройства имеет вид Если обозначить ( )(0 , 1 ) , то значения разрядов вектора настройки(0, 1, 2, 3, 4) устройства на реализацию полусимметрической функции(1, 5) вычисляются по формуле(6)0515 ,где 0, 1, 2, 3, 4. Рассмотрим пример вычисления (реализации) на выходе 18 устройства (фигура) заданной булевой функции(1, 5). Допустим, что на выходе 18 устройства требуется вычислить полусимметрическую булеву функцию( 1 ,2 ,3 ,4 ,5 )123412345 . В таком случае формулы (4) принимают вид 1(0)(1, 1), (1)(2)(3)(0, 0), (4)(1, 0),(0)(0)(1, 1), (1 )( 0 )(1 )(1, 1) ,( 2 )( 0 )( 2 )(1,1) , (3 )( 0 )(1 )( 2 )( 3 )(1,1) ,( 4 )( 0 )( 4 )(0,1) . Принимая во внимание формулу (6), получаем 01, 11, 21, 31 и 45. Следовательно, для реализации на выходе 18 заявляемого устройства полусимметрической булевой функции( 1 ,2 ,3 ,4 ,5 )123412345 необходимо на его настроечные входы 1317 подать значения компонент вектора настройки(1, 1, 1, 1, 5). Для проверки правильности функционирования устройства подставим в выражение( 1 ,2 ,3 ,4 ,1, 1, 1, 1,5 )11( 1234 )1( 1 21 31 4232434 )1( 1 231 241 34234 )1 2345112341 21 31 42324341 231 241 342341 2341 234512341 234512341 2345 . Основным достоинством заявляемого устройства является низкая конструктивная сложность, равная 27 (сложность устройства-прототипа равна 47). Кроме того, устройство имеет всего 10 внешних выводов (четыре информационных и пять настроечных входов, выход). Устройство-прототип имеет 13 внешних выводов (четыре информационных и восемь настроечных входов, выход). 1. Патент РБ 11275, МПК 06 7/00, 2008. 2. Заявка на Патент РБ 20101240, МПК 06 7/00, 2011 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.

МПК / Метки

МПК: G06F 7/00

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

Код ссылки

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

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