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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(71) Заявитель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 5, содержащее блок вычисления симметрических булевых функций четырех переменных и 4 группы логических элементов, каждая из которых содержит пять элементов сложения по модулю два и четыре элемента И, при этом первый вход -го элемента И -й группы, где 1, 4 , где 1,4 , соединен с -м информационным входом устройства, а выход соединен с первым входом -го элемента сложения по модулю два -й группы, выход первого элемента И -й группы соединен со вторым входом пятого элемента сложения по модулю два -й группы, третий вход которого соединен с выходом четвертого элемента И -й группы, второй вход первого элемента сложения по модулю два первой группы соединен с первым настроечным входом устройства, второй вход (1)-го,где 1, 2, 3, элемента сложения по модулю два первой группы соединен с (1)-м настроечным входом устройства и вторым входом -го элемента И первой группы, первый вход пятого элемента сложения по модулю два первой группы соединен с пятым настроечным входом устройства и вторым входом четвертого элемента И первой группы, второй 18249 1 2014.06.30 вход первого элемента сложения по модулю два (1)-й группы, где 1,5 , соединен с выходом первого элемента сложения по модулю два -й группы, второй вход (1)-го элемента сложения по модулю два (1)-й группы соединен с выходом (1)-го элемента сложения по модулю два -й группы и вторым входом -го элемента И -й группы,первый вход пятого элемента сложения по модулю два (1)-й группы соединен с выходом пятого элемента сложения по модулю два -й группы и вторым входом четвертого элемента И -й группы, выход -го, где 1, 5 , элемента сложения по модулю два (4)-й группы соединен с -м настроечным входом блока вычисления симметрических булевых функций четырех переменных, -й информационный вход которого соединен с (4)м входом устройства, а выход соединен с выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления модулярных симметрических булевых функцийпеременных, которое содержитгрупп элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов, пять настроечных входов и один выход 1. При настройке сигналами из множества 0,1 устройство реализует тридцать две модулярные симметрические булевые функциипеременных для величины модуля 5. Недостатком устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления симметрических булевых функцийпеременных, содержащеегрупп элементов сложения по модулю два,групп элементов И,информационных входов,1 настроечных входов и один выход 2. При настройке сигналами из множества 0,1 устройство реализует 21 симметрических булевых функцийпеременных, в том числе и тридцать две модулярные симметрические булевы функций для величины модуля 5. Недостатком известного устройства является высокая конструктивная сложность при вычислении модулярных симметрических булевых функцийпеременных, а также большое количество настроечных входов. Изобретение направлено на решение задачи упрощения конструкции устройства при реализации модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем изменения межсоединений логических элементов в схеме устройства. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 5, содержит блок вычисления симметрических булевых функций четырех переменных и 4 группы логических элементов, каждая из которых содержит пять элементов сложения по модулю два и четыре элемента И. При этом первый вход -го элемента И -й группы, где 1, 4 , где 1,4 , соединен с -м информационным входом устройства, а выход соединен с первым входом -го элемента сложения по модулю два -й группы. Второй вход первого элемента сложения по модулю два первой группы соединен с первым настроечным входом устройства. Второй вход (1)-го, где 1, 2, 3, элемента сложения по модулю два первой группы соединен с (1)-м настроечным входом устройства и вторым входом -го элемента И первой группы. Первый вход пятого элемента сложения по модулю два первой группы соединен с пятым настроечным входом устройства и вторым входом четвертого элемента И первой группы. Второй вход первого элемента сложения по модулю два (1)-й группы, где 1,5 , соединен с выходом первого элемента сложения по модулю два -й группы. Второй вход (1)-го элемента сложения по модулю два (1)-й группы соединен с выходом (1)-го элемента сложе 2 18249 1 2014.06.30 ния по модулю два -й группы и вторым входом -го элемента И -й группы. Первый вход пятого элемента сложения по модулю два (1)-й группы соединен с выходом пятого элемента сложения по модулю два -й группы и вторым входом четвертого элемента И-й группы. Выход -го, где 1, 5 , элемента сложения по модулю два (4)-й группы соединен с -м настроечным входом блока вычисления симметрических булевых функций четырех переменных, -й информационный вход которого соединен с (4)-м информационным входом устройства, а выход соединен с выходом устройства. В устройстве выход первого элемента И -й группы соединен со вторым входом пятого элемента сложения по модулю два -й группы, третий вход которого соединен с выходом четвертого элемента И -й группы На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных при 8. Устройство содержит 41616 элементов И 1-16, 52020 элементов сложения по модулю два 17-36, блок вычисления симметрических булевых функций четырех переменных 37,8 информационных входов 38-45, пять настроечных входов 46-50, выход 51. Поясним принцип построения и работы устройства. Обозначим( , , ,) - некоторый кортеж длины , содержащий только эле менты 0, 1, и 0. Булева функция,(1, 2, , ) называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1, , ),1 0 где(,),0,. Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1, 2, , , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,(1, 2, , ) называется модулярной (м.с.б.ф.), если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,(4) Из (1) и (3) непосредственно следует, что при выполнении условия (4) в локальном коде (Ф)(0, 1, , ) м.с.б.ф. ФФ элементы. Тогда локальный код м.с.б.ф. ФФ можно представить в виде 18249 1 2014.06.30 Принимая во внимание (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 2 4 При этом модулярные локальные коды (6) функций,, ,имеют вид 1( )(0, 1, 0, 1, 0) с полиномиальными м.с.б.ф.4 в разложении (2), а именно 44,1, 4 . Пусть ФФ(, 1),(1, 2, , ) - некоторая м.с.б.ф. от 1 переменной. Выполним дизъюнктивное разложение ФФ(, 1) по переменной 1 18249 1 2014.06.30 Тогда, если (Ф)(0, 1, 2, 3, 4) - модулярный локальный код м.с.б.ф. Ф при величине модуля 5, то с учетом (5) модулярные локальные коды остаточных функций 0 и 1 определяются следующим образом(12) Ф(, 1)011 . Остаточные функции 00 и 11 в разложении (12) могут быть получены из остаточных функций в дизъюнктивном разложении (10)00 101 . Из (13) непосредственно следует, что (0)(0) и (1)(0)(1). Здесь знакобозначает операцию поразрядного сложения по модулю два соответствующих компонентов модулярных локальных кодов. Тогда с учетом 11 можно записать(1 )(01 , 12 ,23 ,34 ,40 ) . Принимая во внимание (8) и (14), для остаточных функций 00(Х) и 11 найдем их канонические полиномиальные модулярные локальным коды 0 0 к( 0 )(к 0 , к 1 , к 0 , к 3 , к 0 ) и к(1 )(к 1 , к 1 , к 1 , к 1 , к 1 )0 2 4 0 1 2 3 4 С учетом (17) представим остаточные функции 00 и 11 в виде канонического полиномиального разложения (7) 1 2 3 4 Выражение (19) является первообразной (порождающей функцией) предлагаемого устройства и демонстрирует способ увеличения на единицу количества переменных реализуемых м.с.б.ф. Устройство для вычисления модулярных симметрических булевых функций при 8(фигура) работает следующим образом. На информационные входы 38-45 подаются двоичные переменные 18 (в произвольном порядке), на настроечные входы 46, 47, , 50 - соответственно компоненты к 0, к 1, , к 4 вектора к(Ф)(к 0, к 1, к 2, к 3, к 4) коэффициентов канонического полиномиального разложения м.с.б.ф. ФФ, значения которой реализуются на выходе 51 устройства. Таким образом, предлагаемое устройство при настройке сигналами из множества 0,1 реализует 22532 модулярные симметрические булевые функцийпеременных для величины модуля 5. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются простая конструкция, регулярная и однородная структура и широкие функциональные возможности. Источники информации 1. Патент РБ 11888, МПК 06 7/00, 2009. 2. А.с. СССР 1559337, МПК 06 7/00, 1990 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 6