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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КАНОНИЧЕСКИХ ПОЛИНОМИАЛЬНЫХ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных, где 8, 9, 10 характеризующееся тем, что содержит блок вычисления полиномиальных симметрических булевых функций шести переменных, -й вход которого, где 1, 6 , соединен с -м входом устройства, содержит 6 групп логических элементов, -я из которых, где 1,6 , содержит шесть элементов сложения по модулю два и шесть элементов И, при этом выход первого элемента И -й группы соединен с первым входом -го элемента сложения по модулю два -й группы, выход (1)-го элемента И, где 1, 5 , -й группы соединен со вторым входом (1)-го элемента сложения по модулю два -й группы, (6)-й вход устройства соединен с первым входом -го элемента И -й группы и вторым входом первого элемента сложения по 17974 1 2014.02.28 модулю два -й группы, -й выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с третьим входом -го элемента сложения по модулю два первой группы и вторым входом (1)-го элемента И первой группы, а шестой выход - с третьим входом шестого элемента сложения по модулю два первой группы и вторым входом первого элемента И первой группы, выход -го элемента сложения по модулю два -й группы, где 1,7 , соединен с третьим входом -го элемента сложения по модулю два (1)-й группы и вторым входом (1)-го элемента И (1)-й группы, выход шестого элемента сложения по модулю два -й группы соединен с третьим входом шестого элемента сложения по модулю два (1)-й группы и вторым входом первого элемента И (1)-й группы, выход -го элемента сложения по модулю два (6)-й группы соединен с -м выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления полиномиальных симметрических булевых функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов 1. Недостатками устройства являются ограниченное число переменных реализуемых функций, а также невозможность вычисления канонических полиномиальных модулярных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных, содержащее блок вычисления полиномиальных симметрических булевых функций семи переменных и -7 групп элементов (9, 10, 11,), каждая из которых содержит семь элементов сложения по модулю два и семь элементов И 2. Недостатком известного устройства является невозможность вычисления канонических полиномиальных модулярных симметрических булевых функций. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации канонических полиномиальных модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем использования блока вычисления полиномиальных симметрических булевых функций шести переменных, а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных, где 8, 9, 10 содержит блок вычисления полиномиальных симметрических булевых функций шести переменных, -й вход которого,где 1, 6 , соединен с -м входом устройства. Устройство содержит также -6 групп логических элементов, -я из которых, где 1,6 , содержит шесть элементов сложения по модулю два и шесть элементов И. Выход первого элемента И -й группы соединен с первым входом -го элемента сложения по модулю два -й группы. Выход (1)-го элемента И, где 1, 5 , -й группы соединен со вторым входом (1)-го элемента сложения по модулю два -й группы. В устройстве (6)-й вход соединен с первым входом -го элемента И -й группы и вторым входом первого элемента сложения по модулю два -й группы. При этом -й выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с третьим входом -го элемента сложения по модулю два первой группы и вторым входом (1)-го элемента И первой группы, а шестой выход - с третьим входом шестого элемента сложения по модулю два первой группы и вторым вхо 2 17974 1 2014.02.28 дом первого элемента И первой группы. Выход -го элемента сложения по модулю два -й группы, где 1,7 , соединен с третьим входом -го элемента сложения по модулю два (1)-й группы и вторым входом (1)-го элемента И (1)-й группы, выход шестого элемента сложения по модулю два -й группы соединен с третьим входом шестого элемента сложения по модулю два (1)-й группы и вторым входом первого элемента И(1)-й группы. Выход -го элемента сложения по модулю два (-6)-й группы соединен с-м выходом устройства. На фигуре представлена схема устройства для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных при 10. Устройство содержит блок вычисления полиномиальных симметрических булевых функций шести переменных 1, 63624 элемента И 2-25, 63624 элемента сложения по модулю два 26-49,10 входов 50-59 и шесть выходов 60-65. Устройство реализует шесть канонических полиномиальных модулярных симметрических булевых функцийпеременных при величине модуля 7. Поясним принцип построения и работы устройства. Обозначим( ,,,) - некоторый кортеж длины , содержащий только эле менты 0,1, и 0. Булева функция,(1, 2, , ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1, , ),1 0 где(,) ,0,. Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф.( ) , 1 представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1, 2, , , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф.,(1, 2, , ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,1 ,01 ,0,(0, 1, , )(0, 1, , ). Необходимо отметить, что один и тот же модулярный локальный кодвида (2) могут иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2 ) различных м.с.б.ф. определяется только величиной модуляи не зависит от . 3 17974 1 2014.02.28 Далее будем рассматривать только модулярные симметрические булевы функцийпеременных,(1, 2, , ), заданные своим модулярным локальным кодом(0, 1, 2, 3, 4, 5, 6) при величине модуля 7,8, 9, 10,Полиномиальное разложение (1) м.с.б.ф.при 7 можно представить в виде 2 к 0 к 11 к 22 к 33 к 44 к 55 к 66 к 77 ,(3) Компоненты вектора к(к 0, к 1, к 2, к 3, к 4, к 5, к 6, к 7) коэффициентов полиномиального разложения м.с.б.ф.могут быть определены из модулярного локального кода(5) к 7 к 1 к 2 к 3 к 4 к 5 к 6. Принимая во внимание (5), полиномиальное разложение (3) представим в канонической форме 1 к 0 к 1 к 22 к 33 к 44 к 55 к 66 ,(6) где 1 2 6 Функции,, ,назовем каноническими полиномиальными м.с.б.ф., а вектор к(к 0, к 1, к 2, к 3, к 4, к 5, к 6) - каноническим полиномиальным модулярным локальным кодом. Очевидно, что канонический полиномиальный модулярный локальный код к( )(к 0 , к 1 , к 2 , к 3 , к 4 , к 5 , к 6 ) функций( ) имеет только один элемент, равный единице к 1,1, 6 . Тогда можно записать 1 к(0, 1, 0, 0, 0, 0, 0) 17974 1 2014.02.28 1 Канонические полиномиальные м.с.б.ф., 2 ,, 6 могут быть непосредственно вычислены согласно (7) посредством полиномиальных м.с.б.ф.1 ,2 ,,7 . Однако бо лее эффективным представляется использование иного способа вычисления, который и реализован в предлагаемом устройстве. Пусть(, 1),(1, 2, , ), - некоторая м.с.б.ф. от 1 переменной. Выполним полиномиальное разложениепо переменной 1(9)(, 1)011,где 00 и 11 - остаточные м.с.б.ф. отпеременных. Тогда, если к(к 0, к 1, , к 6) - канонический полиномиальный модулярный локальный код м.с.б.ф.при величине модуля 7, то коды остаточных функций 0 и 1 определяются следующим образом к(0 )к ( )(к 0 , к 1 , к 2 , к 3 , к 4 , к 5 , к 6 ) Заметим, что в локальном коде к(1) присутствует элемент к 7, который вычисляется согласно (5). Выполним разложение вида (9) канонических полиномиальных м.с.б.ф. 11 (,1 ) , 21 (,1 ) , , 61 (,1 ) С учетом (8) и (10) представим остаточные функции 0 ( ) и 1 в форме канонического полиномиального разложения (6). 1 Поскольку к( 1 (,1 ) )(к 0 , к 1 , к 2 , к 3 , к 4 , к 5 , к 6 )(0, 1, 0, 0, 0, 0, 0) , то локальные коды остаточных функций 1 ( ) и 1 ( ) имеют вид 0 1(12)( )11( ) . Заметим, что согласно (5) элементы к 71 во всех канонических полиномиальных 1 ( ) из (11), так как к 1 (,1 )кявляются унитарными двоичными кодами. 2 Для функции 1 (,1 ) имеем к(21 (,1 ) )(к 0 , к 1 , к 2 , к 3 , к 4 , к 5 , к 6 )(0, 0, 1, 0, 0, 0, 0) . Откуда 2 к(0)(к 0 , к 1 , к 2 , к 3 , к 4 , к 5 , к 6 )(0, 0, 1, 0, 0, 0, 0) 17974 1 2014.02.28 Аналогично для функций 31 (,1 ) , 41 (,1 ) , 51 (,1 ) , 61 (,1 ) , можно получить следующие аналитические выражения 31 (,1 )3 ( )12 ( )16(17) Предлагаемое устройство построено в соответствии с соотношениями (12)-(17) и реализует шесть канонических полиномиальных м.с.б.ф.( ) ,1, 6 , зависящих от произвольного числапеременных для величины модуля 7. Устройство для вычисления канонических полиномиальных модулярных симметрических булевых функций при 10 (фигура) работает следующим образом. На входы 50-59 подаются двоичные переменные 1, 2, , 10 (в произвольном порядке), на выходах 60, 61, , 65 реализуются значения канонических полиномиальных 1 1 2 2 6 6 м.с.б.ф. 1010 ( ) , 1010 ( ) , , 1010 ( ) , соответственно,(1, 2 10). Достоинствами устройства для вычисления канонических полиномиальных модулярных симметрических булевых функцийпеременных являются простая конструкция, однородная и регулярная структура. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 6