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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ФУНДАМЕНТАЛЬНЫХ ПОЛИНОМИАЛЬНЫХ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, где 5, 6, 7, , характеризующееся тем, что содержит блок вычисления полиномиальных симметрических булевых функций четырех переменных, -й вход которого, где 1, 4 , соединен с -м входом устройства, содержит-4 группы логических элементов, -я из которых, где 1,4 , содержит четыре элемента сложения по модулю два и четыре элемента И, при этом выход первого элемента И-й группы соединен с первым входом первого элемента сложения по модулю два -й группы и первым входом четвертого элемента сложения по модулю два -й группы, выход(1)-го элемента И, где 1, 2, -й группы соединен с первым входом (1)-го элемента сложения по модулю два -й группы, выход четвертого элемента И -й группы соединен со 17929 1 2014.02.28 вторым входом четвертого элемента сложения по модулю два -й группы, (4)-й вход устройства соединен с первым входом -го элемента И -й группы и вторым входом первого элемента сложения по модулю два -й группы, первый выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен с третьим входом первого элемента сложения по модулю два первой группы и вторым входом второго элемента И первой группы, (1)-й выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен со вторым входом (1)-го элемента сложения по модулю два первой группы и вторым входом (2)-го элемента И первой группы, четвертый выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен с третьим входом четвертого элемента сложения по модулю два первой группы и вторым входом первого элемента И первой группы, выход первого элемента сложения по модулю два -й группы, где 1,5 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы и вторым входом второго элемента И (1)-й группы, выход (1)-го элемента сложения по модулю два -й группы соединен со вторым входом (1)-го элемента сложения по модулю два (1)-й группы и вторым входом (2)-го элемента И (1)-й группы, выход четвертого элемента сложения по модулю два -й группы соединен с третьим входом четвертого элемента сложения по модулю два (1)-й группы и вторым входом первого элемента И (1)-й группы, выход -го элемента сложения по модулю два (-4)-й группы соединен с -м выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления веса двоичных кодовых комбинаций по модулю пять, содержащее блок формирования унитарного двоичного кода, элементы ИЛИ-НЕ,элементы НЕ,входов и пять выходов 1. На выходах устройства реализуются значения фундаментальных модулярных симметрических булевых функцийпеременных при величине модуля 5. Недостатком устройства является невозможность вычисления фундаментальных, полиномиальных, модулярных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных, содержащее блок вычисления полиномиальных симметрических булевых функций семи переменных и -1 групп элементов (9, 10, 11,), каждая из которых содержит семь элементов сложения по модулю два и семь элементов И 2. Устройство имеетвходов и семь выходов, на которых реализуются значения полиномиальных модулярных симметрических булевых функцийпеременных при величине модуля 7. Недостатком известного устройства является невозможность вычисления фундаментальных полиномиальных модулярных симметрических булевых функций при величине модуля 5. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных при величине модуля 5. Названный технический результат достигается путем использования блока вычисления полиномиальных симметрических булевых функций четырех переменных, а также изменением межсоединений элементов в схеме устройства. 2 17929 1 2014.02.28 Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, где 5, 6, 7, , содержит блок вычисления полиномиальных симметрических булевых функций четырех переменных, -й вход которого, где 1,4 , соединен с -м входом устройства. Устройство содержит также -4 группы логических элементов, -я из которых, где 1,4 , содержит четыре элемента сложения по модулю два и четыре элемента И. Выход первого элемента И -й группы соединен с первым входом первого элемента сложения по модулю два -й группы и первым входом четвертого элемента сложения по модулю два -й группы. Выход (1)-го элемента И, где 1, 2, -й группы соединен с первым входом (1)го элемента сложения по модулю два -й группы. Выход четвертого элемента И -й группы соединен со вторым входом четвертого элемента сложения по модулю два -й группы. В устройстве (4)-й вход соединен с первым входом -го элемента И -й группы и вторым входом первого элемента сложения по модулю два -й группы. Первый выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен с третьим входом первого элемента сложения по модулю два первой группы и вторым входом второго элемента И первой группы. При этом (1)-й выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен со вторым входом (1)-го элемента сложения по модулю два первой группы и вторым входом (2)-го элемента И первой группы. Четвертый выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен с третьим входом четвертого элемента сложения по модулю два первой группы и вторым входом первого элемента И первой группы. Выход первого элемента сложения по модулю два -й группы, где 1,5 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы и вторым входом второго элемента И (1)-й группы. Выход (1)-го элемента сложения по модулю два -й группы соединен со вторым входом (1)-го элемента сложения по модулю два (1)-й группы и вторым входом(2)-го элемента И (1)-й группы. Выход четвертого элемента сложения по модулю два -й группы соединен с третьим входом четвертого элемента сложения по модулю два (1)-й группы и вторым входом первого элемента И (1)-й группы. Выход -го элемента сложения по модулю два (-4)-й группы соединен с -м выходом устройства. На фигуре представлена схема устройства для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных при 8. Устройство содержит блок вычисления полиномиальных симметрических булевых функций четырех переменных 1, 41616 элементов И 2-17, 41616 элементов сложения по модулю два 18-33,8 входов 34-41 и четыре выхода 42-45. Устройство реализует четыре фундаментальные полиномиальные модулярные симметрические булевы функциипеременных при величине модуля 5. Поясним принцип построения и работы устройства. Обозначим(, , , ) - некоторый кортеж длины , содержащий только элементы 0,1, и 0. Булева функция,(1, 2, , , называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом 3 где( ,-1),0,. Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1,2, , , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалкина) посредством п.с.б.ф.1 где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ(Х),(1, 2, , ), называется модулярной (м.с.б.ф.), если ее значение на любом наборе переменных изоднозначно определяется весом(12) двоичной кодовой комбинации по модулю ,Ф(1, 0-)Ф(1, 0-),(3) где, 0, 0,.(4) Из (1) и (3) непосредственно следует, что при выполнении условия (4) в локальном коде (Ф)(0, 1, ,м.с.б.ф. ФФ(Х) элементы. Тогда локальный код м.с.б.ф. ФФ(Х) можно представить в виде где(1)/. Принимая во внимание (5), м.с.б.ф. ФФ(Х) можно задавать -разрядным модулярным локальным кодом(Ф)(Ф). Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (6) может иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . Дальнейшие рассуждения будут вестись только для величины модуля 5 и модулярных симметрических булевых функций 5 переменных ФФ(Х), заданных своим модулярным локальным кодом (Ф)(0, 1, 2, 3, 4). Произвольная м.с.б.ф. ФФ(Х)переменных может быть однозначно представлена в виде канонического полиномиального разложения 4 где к 0,1,0,4 - коэффициенты канонического полиномиального разложения- фундаментальные полиномиальные м.с.б.ф.,1,4 . Вектор к(Ф)(к 0, к 1, к 2, к 3, к 4) назовем каноническим полиномиальным модулярным локальным кодом. 4 17929 1 2014.02.28 Можно показать, что коэффициенты к полиномиального разложения (7) находятся из модулярного локального кода (Ф)(0, 1, 2,3, 4) согласно следующим соотношениям к 00 При этом модулярные локальные коды (6) функций 1, 2, , 4 имеют вид 1 При 4 фундаментальные полиномиальные м.с.б.ф. 4 совпадают с полиномиальными м.с.б.ф. Е 4 в разложении (2) 44,1,4 . Пусть ФФ(, 1),(1, 2, , ) - некоторая м.с.б.ф. от 1 переменной. Выполним дизъюнктивное разложение ФФ(, 1) по переменной 1 Ф(,1 )101,(10) где 00(Х) и 11 - остаточные м.с.б.ф. отпеременных. Тогда, если (Ф)(0, 1, 2, 3, 4) - модулярный локальный код м.с.б.ф. Ф при величине модуля 5, то с учетом (5) модулярные локальные коды остаточных функций 0 и 1, определяются следующим образом(12) Ф(, 1)011. Остаточные функции 00 и 11 в разложении (12) могут быть получены из остаточных функций в дизъюнктивном разложении (10)00(1 )(01 , 12 ,23 , 34 ,40 ). Выполним разложение вида (12) фундаментальных полиномиальных м.с.б.ф,1 111 (, 1), 2121 (, 1), 3131 (, 1) и 4141 (, 1) Модулярные локальные коды ( 0) и ( 1) остаточных функций 11 находятся в соответствии с (14). Для функции 1111(, 1) согласно (15) имеем 11(, 1)10111 . Найдем локальные коды остаточных функций с учетом (9) и (14)(11)(01, 12, 23, з 4, 40)(1, 1, 1, 1, 0). Принимая во внимание соотношения (9), можно записать 1 110 0 11414 . 1 1 Откуда разложение (16) примет вид 1 11 (, 1)11 4 .(17) Аналогичным образом могут быть получены разложения и для других фундаментальных полиномиальных м.с.б.ф. 1 21 (, 1)2 (Х)1.(20) Предлагаемое устройство построено в соответствии с соотношениями (17)-(20) и реализует четыре фундаментальные полиномиальные м.с.б.ф.,1,4 , зависящие от произвольного числапеременных для величины модуля 5,При 8 устройство (фигура) работает следующим образом. На входы 34-41 подаются двоичные переменные 1, 2 8 (в произвольном порядке),на выходах 42, 43, 44 и 45 реализуются значения фундаментальных полиномиальных 1 1 м.с.б.ф. 88 , 8282 , 8383 и 8484 соответственно,(1, х 2, , 8). Достоинствами устройства для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных являются простая конструкция,однородная и регулярная структура. 41 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.