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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КАНОНИЧЕСКИХ ПОЛИНОМИАЛЬНЫХ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных, где 22, где 2, 3, 4 характеризующееся тем, что содержит 1 полусумматоров, -й, где 1, 2, вход -го, где 1,1 , из которых соединен с (2- 2)-м входом устройства, содержитгрупп логических элементов, -я, где 1,, из которых содержит два элемента сложения по модулю два и четыре элемента И, выход суммы -го полусумматора соединен с первым входом -го элемента И -й группы и первым входом первого элемента сложения по модулю два -й группы, выход переноса -го полусумматора соединен с первым входом (2)-го элемента И -й группы и первым входом второго элемента сложения по модулю два -й группы,выход первого элемента И -й группы соединен со вторым входом -го элемента сложения по модулю два -й группы, выход (1)-го элемента И -й группы соединен с третьим входом (3 - )-го элемента сложения по модулю два -й группы, выход четвертого элемента И -й группы соединен с четвертым входом -го элемента сложения по модулю два -й группы, выход суммы (1)-го полусумматора соединен с пятым входом первого элемента сложения по модулю два первой группы, вторым входом второго элемента И первой группы и вторым входом четвертого элемента И первой группы, выход переноса (1)го полусумматора соединен с пятым входом второго элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом 17904 1 2014.02.28 третьего элемента И первой группы, выход первого элемента сложения по модулю два -й,где 1,1 , группы соединен с пятым входом первого элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И (1)-й группы и вторым входом четвертого элемента И (1)-й группы, выход второго элемента сложения по модулю два -й группы соединен с пятым входом второго элемента сложения по модулю два(1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом третьего элемента И (1)-й группы, выход -го элемента сложения по модулю два -й группы соединен с -м выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных, содержащее блок вычисления полиномиальных симметрических булевых функций трех переменных и -3 группы логических элементов (5, 6, 7,),каждая из которых содержит три элемента сложения по модулю два и три элемента И 1. Недостатками устройства являются низкое быстродействие и невозможность вычисления канонических полиномиальных модулярных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных (23,2, 3, 4,), содержащее блок вычисления полиномиальных симметрических булевых функций трех переменных игрупп логических элементов, каждая из которых содержит четыре элемента сложения по модулю два и семь элементов И 2. Недостатком известного устройства является также невозможность вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации канонических полиномиальных модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем изменения межсоединений логических элементов в схеме устройства. Устройство для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных, где 22, где 2, 3, 4 содержит 1 полусумматоров, -й, где 1, 2, вход -го, где 1,1 , из которых соединен с (2- 2)-м входом устройства. Устройство содержит такжегрупп логических элементов, -я, где 1,, из которых содержит два элемента сложения по модулю два и четыре элемента И. Выход суммы -го полусумматора соединен с первым входом -го элемента И -й группы и первым входом первого элемента сложения по модулю два -й группы. Выход переноса -го полусумматора соединен с первым входом (2)-го элемента И -й группы и первым входом второго элемента сложения по модулю два -й группы. Выход первого элемента И -й группы соединен со вторым входом -го элемента сложения по модулю два -й группы. Выход (1)-го элемента И -й группы соединен с третьим входом (3-)-го элемента сложения по модулю два -й группы. Выход четвертого элемента И -й группы соединен с четвертым входом -го элемента сложения по модулю два -й группы. Выход суммы (1)-го полусумматора соединен с пятым входом первого элемента сложения по модулю два первой группы, вторым входом второго элемента И первой группы и вторым входом четвертого элемента И первой группы. Выход переноса (1)-го полусумматора соединен с пятым входом второго элемента сложения по модулю два пер 2 17904 1 2014.02.28 вой группы, вторым входом первого элемента И первой группы и вторым входом третьего элемента И первой группы. Выход первого элемента сложения по модулю два -й, где 1,1 , группы соединен с пятым входом первого элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И (1)-й группы и вторым входом четвертого элемента И(1)-й группы. Выход второго элемента сложения по модулю два -й группы соединен с пятым входом второго элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом третьего элемента И (1)-й группы. Выход -го элемента сложения по модулю два -й группы соединен с -м выходом устройства. На фигуре представлена схема устройства для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных при 228(3). Устройство содержит 14 полусумматора 1-4, 412 элементов И 5-16, 26 элементов сложения по модулю два 17-22,228 входов 23-30 и два выхода 31 и 32. Поясним принцип построения и работы устройства. Обозначим(, ) - некоторый кортеж длины , содержащий только элемен ты 0,1, и 0. Булева функция,(1, 2 ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1 ),1 0 где(,) ,0,. Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф.,, 1, представимая в виде суммы по модулю два всевозмож ных попарно различных элементарных конъюнкций ранга , составленных из переменных 1, 2 , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1 ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,(1, 2 ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,Ф(1 ,0)Ф(1 ,0) ,(Ф)(0, 1 )(Ф)(0, 1 ). Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (2) могут иметь м.с.б.ф., зависящие от различного числапеременных. 17904 1 2014.02.28 Далее будем рассматривать только модулярные симметрические булевы функциипеременных ФФ,(х 1, х 2 ), заданные своим модулярным локальным кодом(Ф)(0, 1, 2) при величине модуля р 3,4, 5, 6,При 3 полиномиальное разложение (1) м.с.б.ф. ФФ можно представить в виде ФФ 011 22 33 ,(3) Компоненты вектора (Ф)(0, 1, 2, 3) коэффициентов полиномиального разложения м.с.б.ф. ФФ могут быть определены из модулярного локального кода(5) Принимая во внимание (5), полиномиальное разложение (3) представим в канонической форме 1 Ф 0122 ,(6) где 1 1 1 2 Функциииназовем каноническими полиномиальными м.с.б.ф., а вектор(Ф)(0, 1, 2) - каноническим полиномиальным модулярным локальным кодом. Очевидно, что канонический полиномиальный модулярный локальный код 1 1(Ф)(0, 1, 2) функцийи 22 имеет только один элемент, равный единице 1( )(0, 1, 0)(7) могут быть представлены посредством полиномиальных с.б.ф. 1 1 3 4 6 7 88188888 2 3 5 6 828288888. 8 Пусть ФФ(, 1, 2),(1, 2 ), - некоторая м.с.б.ф. от 2 переменных. Выполним полиномиальное разложение Ф по переменным 1 и 2 17904 1 2014.02.281212. Отметим, что функцииимогут быть реализованы соответственно на выходах суммы и переноса полусумматора. Тогда, если (Ф)(0, 1, 2) - канонический полиномиальный модулярный локальный код м.с.б.ф. ФФ(, 1, 2) при величине модуля 3, то коды остаточных функций 0, 1 и 2 определяются следующим образом(0 )(Ф)( 0 , 1 ,2 ) В локальных кодах (1) и (2) присутствует элемент 3, который вычисляется согласно (5). 1 Выполним разложение вида (9) канонических полиномиальных м.с.б.ф.2 (,1,2 ) и 2 2 (,1,2 )12 (,1 ,2 )111 С учетом (8) и (10) представим остаточные функции в форме канонического полиномиального разложения (6). 1 Выполним разложение функции 2 (,1,2 ) . Поскольку локальный код 1(2 (,1 ,2 ) )( 0 , 1 ,2 )(0, 1, 0) , то локальные коды остаточных функций(13). Предлагаемое устройство построено в соответствии с соотношениями (12) и (13) и 1 1 реализует две канонические полиномиальных м.с.б.ф. 22 и 2222, зависящие от произвольного числапеременных для величины модуля 3. 2 17904 1 2014.02.28 Устройство для вычисления канонических полиномиальных модулярных симметрических булевых функций при 8 (фигура) работает следующим образом. На входы 23-30 подаются двоичные переменные 1, 2, , 8 (в произвольном порядке), на выходах 31 и 32 реализуются значения канонических полиномиальных м.с.б.ф. 1 1 88 и 8282 соответственно,(1, 2, , 8). Достоинствами устройства для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных являются простая конструкция, однородная и регулярная структура. Источники информации 1. Патент РБ 13176, МПК 06 7/00, 2010. 2. Патент РБ 13927, МПК 06 7/00, 2010 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 6