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

Номер патента: 17967

Опубликовано: 28.02.2014

Автор: Авгуль Леонид Болеславович

Скачать PDF файл.

Текст

Смотреть все

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 26, а 1, 2, 3, , характеризующееся тем, что содержит блок вычисления симметрических булевых функций шести переменных иполусумматоров, -й,где 1, 2, вход -го, где 1,, из которых соединен с (22)-м информационным 17967 1 2014.02.28 входом устройства, содержитгрупп логических элементов, каждая из которых содержит семь элементов сложения по модулю два и двенадцать элементов И, при этом первый вход -го, где 1, 6 , элемента И -й группы соединен с выходом суммы -го полусумматора, выход переноса которого соединен с первым входом (6)-го элемента И -й группы, выход -го элемента И -й группы соединен с первым входом -го элемента сложения по модулю два -й группы и -м входом седьмого элемента сложения по модулю два -й группы, выход (6)-го, где 1, 5 , элемента И -й группы соединен со вторым входом го элемента сложения по модулю два -й группы и (1)-м входом шестого элемента сложения по модулю два -й группы, выход двенадцатого элемента И -й группы соединен с седьмым входом (5)-го элемента сложения по модулю два -й группы, первый настроечный вход устройства соединен с третьим входом первого элемента сложения по модулю два первой группы, второй настроечный вход устройства соединен с третьим входом второго элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом двенадцатого элемента И первой группы, (2)-й, где 1, 2, 3, настроечный вход устройства соединен с третьим входом (2)-го элемента сложения по модулю два первой группы, вторым входом (1)-го элемента И первой группы и вторым входом (6)-го элемента И первой группы, (5)-й настроечный вход устройства соединен с восьмым входом (5)-го элемента сложения по модулю два первой группы, вторым входом (4)-го элемента И первой группы и вторым входом (9)-го элемента И первой группы, выход первого элемента сложения по модулю два -й группы,где 1,1 , соединен с третьим входом первого элемента сложения по модулю два(1)-й группы, выход второго элемента сложения по модулю два -й группы соединен с третьим входом второго элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом двенадцатого элемента И(1)-й группы, выход (2)-го элемента сложения по модулю два -й группы соединен с третьим входом (2)-го элемента сложения по модулю два (1)-й группы, вторым входом (1)-го элемента И (1)-й группы и вторым входом (6)-го элемента И(1)-й группы, выход (5)-го элемента сложения по модулю два -й группы соединен с восьмым входом (5)-го элемента сложения по модулю два (1)-й группы, вторым входом (4)-го элемента И (1)-й группы и вторым входом (9)-го элемента И(1)-й группы, выход -го, где 1, 7 , элемента сложения по модулю два -й группы соединен с -м настроечным входом блока вычисления симметрических булевых функций шести переменных, -й информационный вход которого соединен с (6)-м информационным входом устройства, а выход соединен с выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления симметрических булевых функцийпеременных, содержащеегрупп элементов сложения по модулю два,групп элементов И,информационных входов,1 настроечных входов и один выход 1. При настройке сигналами из множества 0, 1 устройство реализует 21 симметрических булевых функцийпеременных, в том числе и все модулярные симметрические булевы функции. Недостатком устройства является высокая конструктивная сложность при вычислении модулярных симметрических булевых функцийпеременных, а также большое количество настроечных входов. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функцийпеременных, которое при величине модуля 7 содержит 2 17967 1 2014.02.28 блок вычисления симметрических булевых функций шести переменных,6 элементов НЕ и 6 групп логических элементов, каждая из которых содержит семь элементов 2-2 И-2 ИЛИ,информационных входов, семь настроечных входов и один выход 2. Недостатком известного устройства является низкое быстродействие, определяемое большой глубиной схемы. Изобретение направлено на решение задачи повышения быстродействия устройства для вычисления модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем введения в состав устройства блока вычисления симметрических булевых функций шести переменных,полусумматоров игрупп логических элементов, каждая из которых содержит семь элементов сложения по модулю два и двенадцать элементов И (1, 2, 3,26 - число переменных реализуемых модулярных симметрических булевых функций). Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 26, где 1, 2, 3, , характеризуется тем, что содержит блок вычисления симметрических булевых функций шести переменных иполусумматоров, -й, где 1, 2, вход -го, где 1,, из которых соединен с (22)-м информационным входом устройства. Устройство содержитгрупп логических элементов, каждая из которых содержит семь элементов сложения по модулю два и двенадцать элементов И. При этом первый вход -го, где 1, 6 , элемента И -й группы соединен с выходом суммы -го полусумматора, выход переноса которого соединен с первым входом (6)-го элемента И -й группы. Выход -го элемента И -й группы соединен с первым входом -го элемента сложения по модулю два -й группы и -м входом седьмого элемента сложения по модулю два -й группы. Выход (6)-го, где 1, 5 , элемента И -й группы соединен со вторым входом го элемента сложения по модулю два -й группы и (1)-м входом шестого элемента сложения по модулю два -й группы. Выход двенадцатого элемента И -й группы соединен с седьмым входом (5)-го элемента сложения по модулю два -й группы. Первый настроечный вход устройства соединен с третьим входом первого элемента сложения по модулю два первой группы. Второй настроечный вход устройства соединен с третьим входом второго элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом двенадцатого элемента И первой группы. В устройстве (2)-й,где 1, 2, 3, настроечный вход соединен с третьим входом (2)-го элемента сложения по модулю два первой группы, вторым входом (1)-го элемента И первой группы и вторым входом (6)-го элемента И первой группы, (5)-й настроечный вход соединен с восьмым входом (5)-го элемента сложения по модулю два первой группы, вторым входом (4)-го элемента И первой группы и вторым входом (9)-го элемента И первой группы. Выход первого элемента сложения по модулю два -й группы, где 1,1 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы. Выход второго элемента сложения по модулю два -й группы соединен с третьим входом второго элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом двенадцатого элемента И (1)-й группы. Выход (2)-го элемента сложения по модулю два -й группы соединен с третьим входом(2)-го элемента сложения по модулю два (1)-й группы, вторым входом (1)-го элемента И (1)-й группы и вторым входом (6)-го элемента И (1)-й группы. Выход (5)-го элемента сложения по модулю два -й группы соединен с восьмым входом(5)-го элемента сложения по модулю два (1)-й группы, вторым входом (4)-го элемента И (1)-й группы и вторым входом (9)-го элемента И (1)-й группы. Выход -го, где 1, 7 , элемента сложения по модулю два -й группы соединен с -м настро 3 17967 1 2014.02.28 ечным входом блока вычисления симметрических булевых функций шести переменных,-й информационный вход которого соединен с (6)-м информационным входом устройства, а выход соединен с выходом устройства. На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных при 2612 (3). Устройство содержит 1236 элементов И 1-36, 721 элемент сложения по модулю два 37-57,3 полусумматора 58, 59 и 60, блок вычисления симметрических булевых функций шести переменных 61,2612 информационных входов 62-73, семь настроечных входов 74-80, выход 81. Поясним принцип построения и работы устройства. Обозначим( ,) - некоторый кортеж длины , содержащий только элемен ты 0, 1, и. Булева функция,(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) могут иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . Дальнейшее изложение будет вестись только для величины модуля 7. Пусть 7 и ФФ,(1, 2, , ), - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0, 1, , 6). Несложно показать, что при выполнении условия 4(4) Из (3) и (4) непосредственно следует, что вектор (Ф)(0, 1, , ) коэффициентов полиномиального разложения (1) м.с.б.ф. ФФ(Х) имеет вид(Ф)(0 , 1 , ,)(0 , 1 , ,7 , 1 , ,7 , ,1 , ,7 , ,7) ,1 24 1 24 4 3 4 3 1 24 4 3 где(-7)/7. Тогда с учетом (5) м.с.б.ф. ФФ может быть однозначно задана полиномиальным локальным кодом к(Ф)(к 0, к 1, , к 7)(0, 1, , 7),(6) элементы которого могут быть вычислены из модулярного локального кода (Ф) к 00 Очевидно, что при заданной величине модуляодин и тот же полиномиальный локальный код к(Ф) вида (6) имеют м.с.б.ф. ФФ, зависящие от различного числапеременных. Таким образом, при величине модуля 7 полиномиальное разложение (1) м.с.б.ф. ФФ(Х) примет вид Фк 0 к 11 к 22 к 33 к 34 к 35 к 36 к 37 ,(8)(9) к 7 к 1 к 2 к 3 к 4 к 5 к 6. Тогда, принимая во внимание (9), полиномиальное разложение (8) представим в канонической форме 1 Фк 0 к 1 к 22 к 33 к 44 к 55 к 66 ,(10) где 1 Функции, 2 , , 6 назовем каноническими полиномиальными м.с.б.ф., а вектор к(Ф)(к 0, к 1, к 2, к 3, к 4, к 5, к 6) - каноническим полиномиальным модулярным локальным кодом. 17967 1 2014.02.28 Пусть ФФФ(1, 2),(1, 2, , ), - некоторая м.с.б.ф.переменных, заданная своим каноническим полиномиальным модулярным локальным кодом к(Ф)(к 0, к 1, к 2, к 3, к 4, к 5, к 6) и Х 1(1, 2, , ), Х 2(1, 2, , ), 1. М.с.б.ф. ФФФ(1, 2) допускает полиномиальную декомпозицию по переменным кортежа 1 вида 6 где 00 ( 2 ),( 2 ),1,6 - остаточные м.с.б.ф. Канонические полиномиальные модулярные локальные коды остаточных м.с.б.ф. вычисляются согласно следующим соотношениям к(0 )к ( Ф )( к 0 , к 1 , к 2 , к 3 , к 4 , к 5 , к 6 ) Обратим внимание, что в локальных кодах к,1, 6 , присутствует элемент к 7, который вычисляется согласно (9). Пусть ФФ(,1,2),(1, 2, , ), - некоторая м.с.б.ф. от 2 переменной. Выполним полиномиальное разложение ФФ(,1,2) вида (12) по переменным из 6 Остаточные функции двух переменных(1 ,2 ),0, 6 , в (14) являются симметрическими булевыми функциями. Представим(1 ,2 ) в виде полинома Жегалкина (1)(0 , 1 ,2 ) - двоичный вектор коэффициентов полинома Жегалкина. Принимая во внимание (5), вектора ( ) с.б.ф.(1, 2) могут быть найдены из (13) с учетом (9) 0( 0 )(0 ,1 ,)(к 0 , к 1 , к 2 )0 2 Откуда полиномиальное представление (1) функций(1 ,2 ) 6 к 6 к 1 к 2 к 3 к 4 к 5 к 6 к 1 Принимая во внимание (15), запишем (14) в виде(к 6 к 1 к 2 к 3 к 4 к 5 к 6 к 1)6 . Предлагаемое устройство построено в соответствии с выражением (16) и реализует сто двадцать восемь м.с.б.ф., зависящих от произвольного числапеременных при величине модуля 7. Блок вычисления симметрических булевых функций 61 реализует все м.с.б.ф. от шести переменных, а каждая изгрупп логических элементов, содержащих по семь элементов сложения по модулю два и по двенадцать элементов И, обеспечивает увеличение числа обрабатываемых переменных на две единицы согласно (16). Из (16) непосредственно следует также, что вектором настройки устройства на реализацию конкретной м.с.б.ф ФФ является вектор коэффициентов ее канонического полиномиального разложения к(Ф)(к 0, к 1, к 2, к 3, к 4, к 5, к 6). Устройство для вычисления модулярных симметрических булевых функций при 2612 (фигура) работает следующим образом. На информационные входы 62-73 подаются двоичные переменные 1-12 (в произвольном порядке), на настроечные входы 74, 75 80 - соответственно компоненты к 0, к 1, , к 6 вектора к(Ф)(к 0, к 1, , к 6) коэффициентов канонического полиномиального разложения м.с.б.ф. ФФ, значения которой реализуются на выходе 81 устройства. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются простая конструкция, регулярная и однородная структура и широкие функциональные возможности. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.

МПК / Метки

МПК: G06F 7/00

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

Код ссылки

<a href="http://bypatents.com/7-17967-ustrojjstvo-dlya-vychisleniya-modulyarnyh-simmetricheskih-bulevyh-funkcijj-n-peremennyh.html" rel="bookmark" title="База патентов Беларуси">Устройство для вычисления модулярных симметрических булевых функций n переменных</a>

Похожие патенты