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

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

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

Автор: Авгуль Леонид Болеславович

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

Текст

Смотреть все

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(71) Заявитель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 24, где 1, 2, 3 содержащее блок вычисления симметрических булевых функций четырех переменных,полусумматоров, -й, где 1, 2, вход -го, где 1,, из которых соединен с (22)-м информационным входом устройства, игрупп логических элементов, каждая из которых содержит пять элементов сложения по модулю два и восемь элементов И, причем первый вход -го, где 1,4 , элемента И -й группы соединен с выходом суммы -го полусумматора, выход переноса которого соединен с первым входом (4)-го элемента И -й группы, выход первого элемента И -й группы соединен с первым входом первого элемента сложения по модулю два -й группы и первым входом пятого элемента сложения по модулю два -й группы, выход (1)-го элемента И -й группы соединен с первым входом (1)-го элемента сложения по модулю два -й группы, выход четвертого элемента И -й группы соединен с первым входом четвертого элемента сложения по модулю два -й группы и вторым входом пятого элемента 18301 1 2014.06.30 сложения по модулю два -й группы, выход пятого элемента И -й группы соединен со вторым входом первого элемента сложения по модулю два -й группы и третьим входом пятого элемента сложения по модулю два -й группы, выход шестого элемента И -й группы соединен со вторым входом второго элемента сложения по модулю два -й группы,выход седьмого элемента И -й группы соединен со вторым входом третьего элемента сложения по модулю два -й группы, вторым входом четвертого элемента сложения по модулю два -й группы и четвертым входом пятого элемента сложения по модулю два -й группы, выход восьмого элемента И -й группы соединен с третьим входом четвертого элемента сложения по модулю два -й группы и пятым входом пятого элемента сложения по модулю два -й группы, первый настроечный вход устройства соединен с третьим входом первого элемента сложения по модулю два первой группы, второй настроечный вход устройства соединен с третьим входом второго элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом восьмого элемента И первой группы, третий настроечный вход устройства соединен с третьим входом третьего элемента сложения по модулю два первой группы, вторым входом второго элемента И первой группы и вторым входом пятого элемента И первой группы, четвертый настроечный вход устройства соединен с четвертым входом четвертого элемента сложения по модулю два первой группы, вторым входом третьего элемента И первой группы и вторым входом шестого элемента И первой группы, пятый настроечный вход устройства соединен с шестым входом пятого элемента сложения по модулю два первой группы, вторым входом четвертого элемента И первой группы и вторым входом седьмого элемента И первой группы, выход первого элемента сложения по модулю два -й группы, где 1,1 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы, выход второго элемента сложения по модулю два -й группы соединен с третьим входом второго элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом восьмого элемента И (1)-й группы,выход третьего элемента сложения по модулю два -й группы соединен с третьим входом третьего элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И (1)-й группы и вторым входом пятого элемента И (1)-й группы, выход четвертого элемента сложения по модулю два -й группы соединен с четвертым входом четвертого элемента сложения по модулю два (1)-й группы, вторым входом третьего элемента И (1)-й группы и вторым входом шестого элемента И (1)-й группы, выход пятого элемента сложения по модулю два -й группы соединен с шестым входом пятого элемента сложения по модулю два (1)-й группы, вторым входом четвертого элемента И(1)-й группы и вторым входом седьмого элемента И (1)-й группы, выход -го, где 1,5 , элемента сложения по модулю два -й группы соединен с -м настроечным входом блока вычисления симметрических булевых функций четырех переменных, -й информационный вход которого соединен с (4)-м информационным входом устройства, а выход соединен с выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления модулярных симметрических булевых функцийпеременных, которое содержитгрупп элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов, пять настроечных входов и один выход 1. При настройке сигналами из множества 0,1 устройство реализует тридцать две модулярные симметрических булевы функциипеременных для величины модуля 5. Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы. 2 18301 1 2014.06.30 Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функцийпеременных (2,4, 5, 6, ), содержащее 5 - 6 элементов 3-2 И-3 ИЛИ,элементов ИЛИ-НЕ,элементов сложения по модулю два,элементов И,информационных входов, пять настроечных входов и один выход 2. Недостатком известного устройства является высокая конструктивная сложность. Изобретение направлено на решение задачи упрощения конструкции устройства для вычисления модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем использования полусумматоров,элементов сложения по модулю два, элементов И, а также изменением межсоединений логических элементов в схеме устройства. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 24, где 1, 2, 3, , содержит блок вычисления симметрических булевых функций четырех переменных иполусумматоров, -й, где 1, 2, вход -го, где 1,, из которых соединен с (22)-м информационным входом устройства. Устройство содержит такжегрупп логических элементов, каждая из которых содержит пять элементов сложения по модулю два и восемь элементов И. При этом первый вход-го, где 1,4 , элемента И -й группы соединен с выходом суммы -го полусумматора,выход переноса которого соединен с первым входом (4)-го элемента И -й группы. Выход первого элемента И -й группы соединен с первым входом первого элемента сложения по модулю два -й группы и первым входом пятого элемента сложения по модулю два -й группы. Выход (1)-го элемента И -й группы соединен с первым входом (1)-го элемента сложения по модулю два -й группы. Выход четвертого элемента И -й группы соединен с первым входом четвертого элемента сложения по модулю два -й группы и вторым входом пятого элемента сложения по модулю два -й группы. Выход пятого элемента И -й группы соединен со вторым входом первого элемента сложения по модулю два -й группы и третьим входом пятого элемента сложения по модулю два -й группы. Выход шестого элемента И -й группы соединен со вторым входом второго элемента сложения по модулю два -й группы. Выход седьмого элемента И -й группы соединен со вторым входом третьего элемента сложения по модулю два -й группы, вторым входом четвертого элемента сложения по модулю два -й группы и четвертым входом пятого элемента сложения по модулю два -й группы. Выход восьмого элемента И -й группы соединен с третьим входом четвертого элемента сложения по модулю два -й группы и пятым входом пятого элемента сложения по модулю два -й группы. Первый настроечный вход устройства соединен с третьим входом первого элемента сложения по модулю два первой группы. Второй настроечный вход устройства соединен с третьим входом второго элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом восьмого элемента И первой группы. Третий настроечный вход устройства соединен с третьим входом третьего элемента сложения по модулю два первой группы, вторым входом второго элемента И первой группы и вторым входом пятого элемента И первой группы. Четвертый настроечный вход устройства соединен с четвертым входом четвертого элемента сложения по модулю два первой группы, вторым входом третьего элемента И первой группы и вторым входом шестого элемента И первой группы. Пятый настроечный вход устройства соединен с шестым входом пятого элемента сложения по модулю два первой группы, вторым входом четвертого элемента И первой группы и вторым входом седьмого элемента И первой группы. Выход первого элемента сложения по модулю два -й группы, где 1,1 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы, выход второго элемента сложения по модулю два -й группы соединен с третьим входом второго элемента сложения по модулю два(1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом 3 18301 1 2014.06.30 восьмого элемента И (1)-й группы. Выход третьего элемента сложения по модулю два-й группы соединен с третьим входом третьего элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И (1)-й группы и вторым входом пятого элемента И (1)-й группы. Выход четвертого элемента сложения по модулю два -й группы соединен с четвертым входом четвертого элемента сложения по модулю два (1)-й группы, вторым входом третьего элемента И (1)-й группы и вторым входом шестого элемента И (1)-й группы. Выход пятого элемента сложения по модулю два -й группы соединен с шестым входом пятого элемента сложения по модулю два (1)-й группы,вторым входом четвертого элемента И (1)-й группы и вторым входом седьмого элемента И (1)-й группы. Выход -го, где 1,5 , элемента сложения по модулю два -й группы соединен с -м настроечным входом блока вычисления симметрических булевых функций четырех переменных, -й информационный вход которого соединен с (4)-м информационным входом устройства, а выход соединен с выходом устройства. На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функций при 2410 (3). Устройство содержит 824 элемента И 1-24, 515 элементов сложения по модулю два 25-39,3 полусумматора 40, 41 и 42, блок вычисления симметрических булевых функций четырех переменных 43,2410 информационных входов 44-53, пять настроечных входов 54-58, выход 51. Поясним принцип построения и работы устройства. Обозначим( ,) - некоторый кортеж длины , содержащий только элемен ты(0,1, и 0. Булева функция,(1, 2, , ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1, 2, , , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,(1, 2, , ), называется модулярной (м.с.б.ф.), если ее значение на любом наборе переменных из(12)двоичной кодовой комбинации по модулю ,Ф(1,0)Ф(1 ,0) ,(3)(4) Из (1) и (3) непосредственно следует, что при выполнении условия (4) в локальном коде (Ф)(0, 1, , ) м.с.б.ф. ФФ(Х) элементы. Тогда локальный код м.с.б.ф. ФФ можно представить в виде 18301 1 2014.06.30 где(1)/. Принимая во внимание (5), м.с.б.ф. ФФ(Х) можно задавать -разрядным модулярным локальным кодом(Ф)(Ф). Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (6) может иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.п переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . Дальнейшие рассуждения будут вестись только для величины модуля р 5 и м.с.б.ф. ФФ(Х) от 5 переменных, заданных своим модулярным локальным кодом(Ф)(0, 1, 2, 3, 4). Произвольная м.с.б.ф. ФФ(Х)переменных может быть однозначно представлена в виде канонического полиномиального разложения 4 где 0,1,0,4 - коэффициенты канонического полиномиального разложения- фундаментальные полиномиальные м.с.б.ф.,1,4 . Вектор (Ф)(0, 1, 2, 3, 4) назовем каноническим полиномиальным модулярным локальным кодом. Можно показать, что коэффициентыполиномиального разложения (7) находятся из модулярного локального кода (Ф)(0, 1, 2, 3, 4) согласно следующим соотношениям 00 1 При этом модулярные локальные коды (6) функций, 2 , , 4 имеют вид 1 с полиномиальными м.с.б.ф. 4 в разложении (2), а именно 44,1,4 . Пусть ФФ(, 1, 2),(1, 2, , ), - некоторая м.с.б.ф. от 2 переменных. Выполним дизъюнктивное разложение Ф по переменным 1 и 2 Ф(,1 ,2 )120(12 )1122,(10) где 00(Х), 11 и 22 - остаточные м.с.б.ф. отпеременных. Тогда если (Ф)(0, 1, 2, 3, 4) - модулярный локальный код м.с.б.ф. Ф, то с учетом (5) модулярные локальные коды остаточных функций 0, 1 и 2 определяются следующим образом 5 Выполним полиномиальное разложение Ф по переменным 1 и 2(12) Ф(, 1, 2)012,где 00, 11 и 22 - остаточные м.с.б.ф. отпеременных 1212. Отметим, что функцииимогут быть реализованы соответственно на выходах суммы и переноса полусумматора. Остаточные функции 00, 11 и 22 в полиномиальном разложении (12) могут быть получены из остаточных функций 00, 11 и 22 в дизъюнктивном разложении (10)00 Из (13) непосредственно следует, что модулярные локальные коды остаточных функций в разложениях (10) и (12) связаны между собой соотношениями( 2 )(0 )(2 ). Здесь знакобозначает операцию поразрядного сложения по модулю два соответствующих компонентов модулярных локальных кодов. Тогда с учетом (11) можно записать( 2 )(02 , 13 , 24 , 30 , 41 , ). Принимая во внимание (8) и (14), для остаточных функций 00, 11 и 22 найдем их канонические полиномиальные модулярные локальным коды 0 0 2 2 2( 0 )( 0 , 1 ,0 ,3 ,0 ) ,(1 )(1 , 1 , 1 , 1 , 1 ) и( 2 )( 0 , 1 ,2 ,3 ,2 )0 2 4 0 1 2 3 4 2 40000 С учетом (18) представим остаточные функции 00(Х), 11(Х) и 22(Х) в виде канонического полиномиального разложения (7) 1(20)( 3414)3( 414124)4 . Выражение (20) является первообразной (порождающей функцией) предлагаемого устройства и демонстрирует способ увеличения на две единицы количества переменных реализуемых м.с.б.ф. Устройство для вычисления модулярных симметрических булевых функций при 2410 (фигура) работает следующим образом. На информационные входы 44-53 подаются двоичные переменные 1 - 10 (в произвольном порядке), на настроечные входы 54, 55 58 - соответственно компоненты 0,1, , 4 вектора (Ф)(0, 1, 2, 3, 4) коэффициентов канонического полиномиального разложения м.с.б.ф. ФФ, значения которой реализуются на выходе 59 устройства. Таким образом, предлагаемое устройство при настройке сигналами из множества 0,1 реализует 22532 модулярных симметрических булевых функцийпеременных для величины модуля 5. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются простая конструкция, регулярная и однородная структура и широкие функциональные возможности. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 7

МПК / Метки

МПК: G06F 7/00

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

Код ссылки

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

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