Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функций n переменных
Текст
(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ФУНДАМЕНТАЛЬНЫХ ПОЛИНОМИАЛЬНЫХ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, где 24, где 1, 2, 3, , характеризующееся тем, что содержит блок вычисления полиномиальных симметрических булевых функций четырех переменных, -й вход которого, где 1, 4 , соединен с -м входом уст 17931 1 2014. 02.28 ройства содержитгрупп логических элементов, -я из которых, где 1,, содержит четыре элемента сложения по модулю два и восемь элементов И содержитполусумматоров, -й вход -го из которых, где 1, 2, соединен с (22)-м входом устройства, а 17931 1 2014.02.28 выход суммы - с первым входом -го элемента И -й группы и первым входом первого элемента сложения по модулю два -й группы, выход переноса - с первым входом (4)-го элемента И -й группы и первым входом второго элемента сложения по модулю два -й группы, выход первого элемента И -й группы соединен со вторым входом первого элемента сложения по модулю два -й группы и первым входом четвертого элемента сложения по модулю два -й группы, выход второго элемента И -й группы соединен со вторым входом второго элемента сложения по модулю два -й группы, выход третьего элемента И-й группы соединен с первым входом третьего элемента сложения по модулю два -й группы, выход четвертого элемента И -й группы соединен со вторым входом четвертого элемента сложения по модулю два -й группы, выход пятого элемента И -й группы соединен с третьим входом первого элемента сложения по модулю два -й группы, третьим входом второго элемента сложения по модулю два -й группы и третьим входом четвертого элемента сложения по модулю два -й группы, выход шестого элемента И -й группы соединен с четвертым входом первого элемента сложения по модулю два -й группы и четвертым входом четвертого элемента сложения по модулю два -й группы, выход седьмого элемента И -й группы соединен со вторым входом третьего элемента сложения по модулю два -й группы, выход восьмого элемента И -й группы соединен с пятым входом четвертого элемента сложения по модулю два -й группы, первый выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен с пятым входом первого элемента сложения по модулю два первой группы, вторым входом второго элемента И первой группы и вторым входом седьмого элемента И первой группы,второй выход соединен с четвертым входом второго элемента сложения по модулю два первой группы, вторым входом третьего элемента И первой группы и вторым входом восьмого элемента И первой группы, третий выход соединен с третьим входом третьего элемента сложения по модулю два первой группы, вторым входом четвертого элемента И первой группы и вторым входом шестого элемента И первой группы, четвертый выход соединен с шестым входом четвертого элемента сложения по модулю два первой группы,вторым входом первого элемента И первой группы и вторым входом пятого элемента И первой группы, выход первого элемента сложения по модулю два -й группы, где 1,1 , соединен с пятым входом первого элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И -й группы и вторым входом седьмого элемента И (1)-й группы, выход второго элемента сложения по модулю два -й группы соединен с четвертым входом второго элемента сложения по модулю два (1)-й группы,вторым входом третьего элемента И (1)-й группы и вторым входом восьмого элемента И (1)-й группы, выход третьего элемента сложения по модулю два -й группы соединен с третьим входом третьего элемента сложения по модулю два (1)-й группы, вторым входом четвертого элемента И (1)-й группы и вторым входом шестого элемента И(1)-й группы, выход четвертого элемента сложения по модулю два -й группы соединен с шестым входом четвертого элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И первой группы и вторым входом пятого элемента И(1)-й группы, выход -го элемента сложения по модулю два -й группы соединен с -м выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления веса двоичных кодовых комбинаций по модулю пять, содержащее блок формирования унитарного двоичного кода, элементы ИЛИ-НЕ,элементы НЕ,входов и пять выходов 1. На выходах устройства реализуются значения фундаментальных модулярных симметрических булевых функцийпеременных при величине модуля 5. 2 17931 1 2014.02.28 Недостатком устройства является невозможность вычисления фундаментальных полиномиальных модулярных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных (27,2, 3, 4,), содержащее блок вычисления полиномиальных симметрических булевых функций семи переменных,полусумматоров игрупп логических элементов, каждая из которых содержит семь элементов сложения по модулю два и четырнадцать элементов И 2. На выходах устройства реализуются значения полиномиальных модулярных симметрических булевых функцийпеременных при величине модуля 7. Недостатком известного устройства является невозможность вычисления фундаментальных полиномиальных модулярных симметрических булевых функций. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных при величине модуля 5. Названный технический результат достигается путем использования блока вычисления полиномиальных симметрических булевых функций четырех переменных, а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, где 24, где 1, 2, 3 содержит блок вычисления полиномиальных симметрических булевых функций четырех переменных, -й вход которого, где 1, 4 , соединен с -м входом устройства. Устройство содержитгрупп логических элементов, -я из которых, где 1,, содержит четыре элемента сложения по модулю два и восемь элементов И. Устройство содержитполусумматоров,-й вход -го из которых, где 1, 2, соединен (22)-м входом устройства, а выход суммы соединен с первым входом -го элемента И -й группы и первым входом первого элемента сложения по модулю два -й группы, выход переноса - с первым входом (4)-го элемента И -й группы и первым входом второго элемента сложения по модулю два -й группы. Выход первого элемента И -й группы соединен со вторым входом первого элемента сложения по модулю два -й группы и первым входом четвертого элемента сложения по модулю два -й группы. Выход второго элемента И -й группы соединен со вторым входом второго элемента сложения по модулю два -й группы. Выход третьего элемента И -й группы соединен с первым входом третьего элемента сложения по модулю два -й группы. Выход четвертого элемента И -й группы соединен со вторым входом четвертого элемента сложения по модулю два -й группы. Выход пятого элемента И -й группы соединен с третьим входом первого элемента сложения по модулю два -й группы, третьим входом второго элемента сложения по модулю два -и группы и третьим входом четвертого элемента сложения по модулю два -й группы. Выход шестого элемента И -й группы соединен с четвертым входом первого элемента сложения по модулю два -й группы и четвертым входом четвертого элемента сложения по модулю два -й группы. Выход седьмого элемента И -й группы соединен со вторым входом третьего элемента сложения по модулю два -й группы. Выход восьмого элемента И -й группы соединен с пятым входом третьего элемента сложения по модулю два -й группы. Первый выход блока вычисления полиномиальных симметрических булевых функций четырех переменных соединен с пятым входом первого элемента сложения по модулю два первой группы, вторым входом второго элемента И первой группы и вторым входом седьмого элемента И первой группы, второй выход соединен с четвертым входом второго элемента сложения по модулю два первой группы, вторым входом третьего элемента И первой группы и вторым входом восьмого элемента И первой группы, третий выход со 3 17931 1 2014.02.28 единен с третьим входом третьего элемента сложения по модулю два первой группы, вторым входом четвертого элемента И первой группы и вторым входом шестого элемента И первой группы, четвертый выход соединен с шестым входом четвертого элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом пятого элемента И первой группы. Выход первого элемента сложения по модулю два -й группы, где 1,- 1 , соединен с пятым входом первого элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И (1)-й группы и вторым входом седьмого элемента И(1)-й группы. Выход второго элемента сложения по модулю два -й группы соединен с четвертым входом второго элемента сложения по модулю два (1)-й группы, вторым входом третьего элемента И (1)-й группы и вторым входом восьмого элемента И(1)-й группы. Выход третьего элемента сложения по модулю два -й группы соединен с третьим входом третьего элемента сложения по модулю два (1)-й группы, вторым входом четвертого элемента И (1)-й группы и вторым входом шестого элемента И(1)-й группы. Выход четвертого элемента сложения по модулю два -й группы соединен с шестым входом четвертого элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И первой группы и вторым входом пятого элемента И(1)-й группы. Выход -го элемента сложения по модулю два -й группы соединен с -м выходом устройства. На фигуре представлена схема устройства для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных при 2410 (3). Устройство содержит блок вычисления полиномиальных симметрических булевых функций четырех переменных 1,3 полусумматора 2, 3 и 4, 824 элемента И 5-28,412 элементов сложения по модулю два 29-40,2410 входов 41-50 и четыре выхода 51-54. Поясним принцип построения и работы устройства. Обозначим(, ) - некоторый кортеж длины , содержащий только элемен ты 0, 1 , и 0. Булева функция,(1, 2, , ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом Таким образом, вес двоичной кодовой комбинации 2 однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1,2 , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,(1, 2 ), называется модулярной (м.с.б.ф.), если ее значение на любом наборе переменных изоднозначно определяется весом(2)двоичной кодовой комбинации по модулю ,4(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) назовем каноническим полиномиальным модулярным локальным кодом. Можно показать, что коэффициентыполиномиального разложения (7) находятся из модулярного локального кода (Ф)(0, 1, 2, 3, 4) согласно следующим соотношениям 00 2 3 4 1 При этом модулярные локальные коды (6) функций,,иимеют вид При 4 фундаментальные полиномиальные м.с.б.ф. 4 совпадают с полиноми альными м.с.б.ф.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 определяются следующим образом Выполним полиномиальное разложение Ф по переменным 1 и 2 Ф(,1 ,2 )012 ,(12) где 00 , 11 и 22- остаточные м.с.б.ф. отпеременных 22. Отметим, что функцииимогут быть реализованы соответственно на выходах суммы и переноса полусумматора. Остаточные функции 00 , 11 и 22 в полиномиальном разложении (12) могут быть получены из остаточных функций 00, 11(Х) и 22 в дизъюнктивном разложении (10)0 ( )0 ( ) 2 ( )0 ( )2 ( ) . Из (13) непосредственно следует, что модулярные локальные коды остаточных функций в разложениях (10) и (12) связаны между собой соотношениями Выполним разложение вида (12) фундаментальных полиномиальных м.с.б.ф.(16) 0 1 2 Найдем модулярные локальные коды остаточных функций с учетом (9) и (14) 1(1 )( 02 , 13 ,24 ,30 ,41 )(0, 0, 0, 1, 1)(3 )(4 ) . 2 Поскольку при заданных значенияхим.с.б.ф. однозначно определяется своими модулярными локальными кодами, то, принимая во внимание соотношения (9), можно записать 1 11 ( )( )0 0(17)2 (,1 ,2 )( )4 ( )34 . Аналогичным образом могут быть получены разложения и для других фундаментальных полиномиальных м.с.б.ф. 1 фундаментальные полиномиальные м.с.б.ф.,1, 4 , зависящие от произвольного числапеременных для величины модуля 5. При 10 устройство (фигура) работает следующим образом. На входы 41-50 подаются двоичные переменные 1, 2 10 (в произвольном порядке),на выходах 51, 52, 53 и 54 реализуются значения фундаментальных полиномиальных м.с.б.ф. 1 1 2 2 3 3 4 4 1010, 1010, 1010 и 1010 соответственно,(1, 2 10). Достоинствами устройства для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных являются простая конструкция,однородная и регулярная структура. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.
МПК / Метки
МПК: G06F 7/00
Метки: булевых, фундаментальных, модулярных, переменных, полиномиальных, функций, симметрических, устройство, вычисления
Код ссылки
<a href="https://by.patents.su/7-17931-ustrojjstvo-dlya-vychisleniya-fundamentalnyh-polinomialnyh-modulyarnyh-simmetricheskih-bulevyh-funkcijj-n-peremennyh.html" rel="bookmark" title="База патентов Беларуси">Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функций n переменных</a>
Предыдущий патент: Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функций n переменных
Следующий патент: Эмульсол и способ его получения
Случайный патент: Передвижное конвейерное устройство для сбора, обработки и погрузки корнеплодов