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

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

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

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

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

Текст

Смотреть все

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ СЕМИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления бисимметрических булевых функций семи переменных,характеризующееся тем, что содержит с первого по седьмой элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре и с первого по одиннадцатый элементы И, выход -го из которых, где 1, 2 6,соединен с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, седьмой вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства первый вход -го элемента И, где 2, 3 6, соединен с выходом -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, причем -й информационный вход устройства,16667 1 2012.12.30 где 1, 2, 3, 4, 5, соединен с -м входом седьмого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с -м входом мажоритарного элемента с порогом два и с -м входом мажоритарного элемента с порогом четыре, выход которого соединен со вторым входом пятого и шестого элементов И и с инверсным входом третьего и четвертого элементов И, второй вход которых соединен с выходом мажоритарного элемента с порогом два, а третий вход четвертого элемента И соединен со вторым входом второго элемента И, с третьим входом шестого элемента И и с выходом седьмого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА второй и третий настроечные входы устройства соединены с первым и вторым входами первого элемента И, четвертый настроечный вход устройства соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом седьмого элемента И, первый и второй входы которого соединены с пятым и шестым настроечными входами устройства седьмой настроечный вход устройства соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом восьмого элемента И, первый и второй входы которого соединены с восьмым и девятым настроечными входами устройства десятый настроечный вход устройства соединен с первым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом девятого элемента И, первый и второй входы которого соединены с одиннадцатым и двенадцатым настроечными входами устройства тринадцатый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом десятого элемента И, первый и второй входы которого соединены с четырнадцатым и пятнадцатым настроечными входами устройства, шестнадцатый настроечный вход устройства соединен с первым входом шестого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом одиннадцатого элемента И, первый и второй входы которого соединены с семнадцатым и восемнадцатым настроечными входами устройства. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления бисимметрических булевых функций семи переменных. Известно устройство для вычисления бисимметрических булевых функцийпеременных(, 2), где, 2, ,и 21, , , которое содержит два блока вычисления веса двоичных комбинацийи - переменных,(1)(-1) элементов И, элемент ИЛИ,информационных инастроечных входов, выход 1. Известное устройство при 7 и 5 содержит два блока вычисления веса двоичных комбинаций двух и пяти переменных, восемнадцать элементов И, элемент ИЛИ, семь информационных и восемнадцать настроечных входов, выход. Известное устройство, как и заявляемое устройство, содержит одиннадцать элементов И. Недостатком известного устройства является высокая конструктивная сложность (по числу входов логических элементов). Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления бисимметрических булевых функцийпеременных (1, 2), где , 2, ,и 21, , ,которое содержит два блока вычисления полиномиальных симметрических булевых функцийи - переменных, -1 элементов И, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,информационных инастроечных входов, выход, где(1)(-) 2. Устройство-прототип при 7 и 5 содержит два блока вычисления полиномиальных симметрических булевых функций двух и пяти переменных, семнадцать элементов И,элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, семь информационных и восемнадцать настроечных входов, выход. 16667 1 2012.12.30 Устройство-прототип, как и заявляемое устройство, содержит одиннадцать элементов И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Недостатком устройства-прототипа является высокая конструктивная сложность (по числу входов логических элементов). Изобретение направлено на решение технической задачи понижения конструктивной сложности устройства для вычисления бисимметрических булевых функций семи переменных(1, 2), где 1, 2, 3, 4, 5 и 26, 7. Устройство для вычисления бисимметрических булевых функций семи переменных характеризуется тем, что содержит с первого по седьмой элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре и с первого по одиннадцатый элементы И. Выход -го элемента И, где 1, 2, , 6, соединен с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, седьмой вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства. Первый вход -го элемента И, где 2, 3, , 6, соединен с выходом -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Причем -й информационный вход устройства, где 1, 2, 3, 4, 5, соединен с -м входом седьмого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с -м входом мажоритарного элемента с порогом два и с -м входом мажоритарного элемента с порогом четыре. Выход мажоритарного элемента с порогом четыре соединен со вторым входом пятого и шестого элементов И и с инверсным входом третьего и четвертого элементов И, второй вход которых соединен с выходом мажоритарного элемента с порогом два. Третий вход четвертого элемента И соединен со вторым входом второго элемента И, с третьим входом шестого элемента И и с выходом седьмого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Второй и третий настроечные входы устройства соединены с первым и вторым входами первого элемента И. Четвертый настроечный вход устройства соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом седьмого элемента И, первый и второй входы которого соединены с пятым и шестым настроечными входами устройства. Седьмой настроечный вход устройства соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом восьмого элемента И, первый и второй входы которого соединены с восьмым и девятым настроечными входами устройства. Десятый настроечный вход устройства соединен с первым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом девятого элемента И, первый и второй входы которого соединены с одиннадцатым и двенадцатым настроечными входами устройства. Тринадцатый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом десятого элемента И, первый и второй входы которого соединены с четырнадцатым и пятнадцатым настроечными входами устройства. Шестнадцатый настроечный вход устройства соединен с первым входом шестого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом одиннадцатого элемента И, первый и второй входы которого соединены с семнадцатым и восемнадцатым настроечными входами устройства. Названный технический результат достигается с помощью введения в логическую схему устройства для вычисления бисимметрических булевых функций семи переменных новых логических элементов (мажоритарных элементов с порогами два и четыре) и по 3 16667 1 2012.12.30 средством последующего изменения соединений между логическими элементами устройства. На фигуре представлена логическая схема устройства для вычисления бисимметрических булевых функций семи переменных. Устройство для вычисления бисимметрических булевых функций содержит одиннадцать элементов И 111, мажоритарный элемент с порогом два 12, мажоритарный элемент с порогом четыре 13, семь элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1420, пять информационных входов 2125, восемнадцать настроечных входов 2643 и выход 44. Устройство для вычисления бисимметрических булевых функций семи переменных работает следующим образом. На информационные входы устройства 2125 поступают (в произвольном порядке) значения переменных , 2, 3, 4, 5, на настроечные входы 2643 - сигналы настройки 0, 1, , 17, значения которых принадлежат множеству 0,1,6 ,6 ,7 ,7 . На выходе устройства 44 вычисляется (реализуется) бисимметрическая булева функция(, 2), где 1, 2, 3, 4, 5 и 26, 7, определяемая вектором настройки(0, 1, , 17). Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций семи переменных. Произвольная симметрическая булева функцияпеременных(1, 2 ) характеризуется множеством своих рабочих чисел, 2 . Функцияпринимает единичные значения на тех и только тех наборах значений переменных , 2 ,которые содержат ровноединиц, где 0, 1 и 01. Такая функция обозначается как 1, 2 , где 1, 2 . Если 1, то функцияназывается фундаментальной (или элементарной) симметрической булевой функцией. Произвольная симметрическая булева функция(1, 2 ) взаимно однозначно представляется (1)-разрядным двоичным (локальным) кодом(0,1), где- значение функциина (любом) наборе значенийпеременных, содержащем(0) единиц. Другими словами,1 тогда и только тогда, когда- рабочее число функции . Симметрическая булева функция(1, 2 ) называется полиномиальнооднородной (или полиномиальной), если полином Жегалкина функциисодержит только(все) элементарные конъюнкции ранга , где 0. Такая булева функция обозначается через(1,2 ) . Если произвольная булева функцияпеременныхне меняет своего значения после перестановки любой пары переменныхи(гдеи ,1, 2, , ), то функцияявляется симметрической. В противном случае говорят, что булева функцияобладает (или не обладает) свойством частичной симметрии переменных. Известно, что отношение частичной симметрии разбивает (единственным образом) множество переменных 1, 2 на классы симметрии , 2 , где 1. 4 16667 1 2012.12.30 Если 1, то функцияявляется (полностью) симметрической если 2, то- бисимметрическая булева функция если, то функцияне обладает свойством частичной симметрии переменных. Бисимметрическая булева функция обозначается(, 2), где 1, 2 - классы симметрии. Заявляемое устройство предназначено для вычисления (реализации) бисимметрических булевых функций(1, 2) в случае, когда 1, 2, 3, 4, 5 и 26,7. Для функции(, 2) имеет место формула дизъюнктивного разложения по переменным множества 1 вида 1(2)54 (1 )4 ( 2 )55 (1 )5 ( 2 ),где 00(2), 11(2), 22(2), 33(2), 44(2) и 55(2) - симметрические булевы функции от двух переменных 6, 7. Двоичный вектор 0), (1), (2), (3), (4), (5(0, 1, , 17) называется двоичным (локальным) кодом бисимметрической булевой функции(1,2). Наряду с формулой (2), существует формула полиномиального разложения функции(, 2) по переменным множества 1, которая имеет вид 2(3) 4 55 (1 )4 ( 2 )5 (1 )5 ( 2 ),2 2 4 4 где 11 (1 ),55 (1 ),33 (1 ),55 (1 ),55 (1 ) - полиномиально-одно 5 5 5 5 5 5 родные симметрические булевы функции (1), зависящие от переменных множества 1. Преобразование формулы (2) в формулу (3) описано в статье Супруна В.П. и Городецкого Д.А. Реализация бисимметрических булевых функций логическими схемами // Известия вузов. Приборостроение. - 2010. -5. - С. 17-25. Там же приведены формулы, по которым вычисляются симметрические булевы функцииН(Х 2), где 1, 2 5. Имеет место 0(2)0(2),1(2)0(2)1(2),2(2)0(2)2(2),(4) 3(2)0(2)1(2)2(2)3(2),4(2)0(2)4(2),5(2)0(2)1(2)4(2)5(2),где функции(2) приведены в формуле (2), которая называется формулой дизъюнктивного разложения функции(1, 2). Введем в рассмотрение двоичный вектор 0), (1), (2), (3), (4), (5(0, 1 17). Из формул (4) следует, что компоненты двоичных векторовисвязаны между собой следующими соотношениями, 33, 66,(5) 9369, 1212,1531215,где 0, 1, 2. Поясним метод построения вектора(0, 1 17) - вектора настройки заявляемого устройства (фигура) на вычисление произвольной бисимметрической булевой функции(1, 2), где 11, 2, 3, 4, 5 и 26, 7. 16667 1 2012.12.30 С помощью локальных кодов (0)(0, 1, 2), (1)(1, 4, 5), (2)(6, 7, 8),(3)(9, 10, 11), (4)(12, 13, 14), (5)(15, 16, 17) из таблицы настройки (таблица), получаем значения фрагментов (0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11), (12, 13,14) и (15, 16, 17) вектора настройки(0, 1 17). Устройство для вычисления бисимметрических булевых функций семи переменных Локальный код симметрической булевой Вектор настройки(0, 1 17) функции(6, 7) (0, 15 ) 3 31 32 Пример. Предположим, что на выходе 44 устройства требуется реализовать бисимметрическую булеву функцию семи переменных(1 ,2 )1234512345(67 ). Так как для заданной функцииформула (2) принимает вид 1(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0). Принимая во внимание описанную выше процедуру построения вектора настройки(0, 1 17), находим 01, 10, 20, 31, 40, 50, 61, 70, 80,91, 100, 110, 121, 130, 140, 150, 166 и 177 . Следовательно,для реализации на выходе 44 устройства функции(1 ,2 )123451 2345(67 ) необходимо на настроечные входы 27,28, 30, 31, 33, 34, 36, 37, 39, 40, 41 подать значение 0, на настроечные входы 26, 29, 32,35, 38 - значение 1, на настроечный вход 42 - значение 6 и на настроечный вход 43 значение 7 . Первообразная функция устройства для вычисления бисимметрических булевых функций семи переменных (фигура) имеет вид 16667 1 2012.12.30 где 1(1 )5 ,3,5 (1 ,2 ,3 ,4 ,5 ),(1 )52,3, 4,5 (1 ,2 ,3 ,4 ,5 ), (1 )54,5 (1 ,2 ,3 ,4 ,5 ),Выражение (6) для первообразной функции устройства равносильно следующей формуле 1 54,5 (1 )(121314 )55 (1 )(1516 17 ). С целью проверки правильности работы заявляемого устройства подставим в выражение (7) значения разрядов вектора настройки(1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,6 ,7 ). В таком случае первообразная функция устройства принимает вид 1 50 (1 )55 (1 )(167 )50 (1 )55 (1 )(67 )123451 2345(67 ). Основным достоинством заявляемого устройства для вычисления бисимметрических булевых функций семи переменных является низкая конструктивная сложность, равная 58. Дополнительным достоинством устройства является небольшое число внешних выводов (пять информационных и восемнадцать настроечных входов, выход). Число внешних выводов устройства-прототипа при 7 и 5 равно 26 (семь информационных и восемнадцать настроечных входов, выход). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.

МПК / Метки

МПК: G06F 7/00

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

Код ссылки

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

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