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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 22, где 1, 2, 3, , характеризующееся тем, что содержит блок вычисления симметрических булевых функций двух переменных,полусумматоров, -й,где 1, 2, вход -го, где 1,, из которых соединен с (22)-м информационным входом устройства, игрупп логических элементов, каждая из которых содержит три элемента сложения по модулю два и четыре элемента И, причем первый вход -го элемента И -й группы соединен с выходом суммы -го полусумматора, а выход соединен с первым входом -го элемента сложения по модулю два -й группы и -м входом третьего элемента сложения по модулю два -й группы, первый вход (2)-го элемента И -й группы соединен с выходом переноса -го полусумматора, а выход соединен со вторым входом-го элемента сложения по модулю два -й группы и третьим входом (1)-го элемента сложения по модулю два -й группы, первый настроечный вход устройства соединен с третьим входом первого элемента сложения по модулю два первой группы, второй настроечный вход устройства соединен с четвертым входом второго элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом четвертого элемента И первой группы, третий настроечный вход устройства соединен с четвертым входом третьего элемента сложения по модулю два первой группы,вторым входом второго элемента И первой группы и вторым входом третьего элемента И первой группы, выход первого элемента сложения по модулю два -й группы, где 1,1 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы, выход второго элемента сложения по модулю два -й группы соединен с четвертым входом второго элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом четвертого элемента И (1)-й группы, выход третьего элемента сложения по модулю два -й группы соединен с четвертым входом третьего элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И (1)-й группы и вторым входом третьего элемента И (1)-й группы, выход -го, где 1, 2, 3, элемента сложения по модулю два -й группы соединен с-м настроечным входом блока вычисления симметрических булевых функций двух переменных, -й информационный вход которого соединен с (2)-м входом устройства, а выход соединен с выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащеегрупп элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов, три настроечных входа и один выход 1. При настройке сигналами из множества 0,1 устройство реализует восемь модулярных симметрических булевых функцийпеременных (3) для величины модуля 3. Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство вычисления модулярных симметрических булевых функцийпеременных (24, 5, 6,), содержащее 95 элементов ИЛИ-НЕ,элементов ИЛИ,элементов сложения по модулю два с инверсным выходом, элементов И-НЕ,информационных входов, три настроечных входа и один выход 2. Недостатком известного устройства является высокая сложность. Изобретение направлено на решение задачи упрощения конструкции устройства при реализации модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем использования в схеме устройства элементов И, элементов сложения по модулю два, полусумматоров, а также изменением межсоединений логических элементов в схеме устройства. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 22, где 1, 2, 3 содержит блок вычисления симметрических булевых функций двух переменных иполусумматоров, -й, где 1, 2, вход -го, где 1,, из которых соединен с (22)-м информационным входом устройства. Устройство содержит такжегрупп логических элементов, каждая из которых содержит три элемента сложения по модулю два и четыре элемента И. Причем первый вход -го элемента И -й группы соединен с выходом суммы -го полусумматора, а выход соединен с первым входом -го элемента сложения по модулю два -й группы и -м входом третьего 2 18011 1 2014.02.28 элемента сложения по модулю два -й группы. Первый вход (2)-го элемента И -й группы соединен с выходом переноса -го полусумматора, а выход соединен со вторым входом-го элемента сложения по модулю два -й группы и третьим входом (1)-го элемента сложения по модулю два -й группы. Первый настроечный вход устройства соединен с третьим входом первого элемента сложения по модулю два первой группы. Второй настроечный вход устройства соединен с четвертым входом второго элемента сложения по модулю два первой группы, вторым входом первого элемента И первой группы и вторым входом четвертого элемента И первой группы. Третий настроечный вход устройства соединен с четвертым входом третьего элемента сложения по модулю два первой группы,вторым входом второго элемента И первой группы и вторым входом третьего элемента И первой группы. Выход первого элемента сложения по модулю два -й группы, где 1,1 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы. Выход второго элемента сложения по модулю два -й группы соединен с четвертым входом второго элемента сложения по модулю два (1)-й группы, вторым входом первого элемента И (1)-й группы и вторым входом четвертого элемента И (1)-й группы. Выход третьего элемента сложения по модулю два -й группы соединен с четвертым входом третьего элемента сложения по модулю два (1)-й группы, вторым входом второго элемента И (1)-й группы и вторым входом третьего элемента И (1)-й группы. Выход -го, где 1, 2, 3, элемента сложения по модулю два -й группы соединен с м настроечным входом блока вычисления симметрических булевых функций двух переменных, -й информационный вход которого соединен с (2)-м информационным входом устройства, а выход соединен с выходом устройства. На фигуре представлена схема устройства при 228 (3). Устройство содержит 412 элементов И 1-12, 39 элементов сложения по модулю два 13-21,3 полусумматора 22, 23 и 24, блок вычисления симметрических булевых функций двух переменных 25,228 информационных входов 26-33, три настроечных входа 34, 35 и 36, выход 37. Обозначим( ,) - некоторый кортеж длины , содержащий только элемен ты 0,1, и 0. Булева функция,(1, 2 ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1, 2, , , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1 ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,( 1 , 2), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,Ф(1 ,0)Ф(1 ,0) ,(Ф)(0, 1 )(Ф)(0, 1 ). Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (2) могут иметь м.с.б.ф., зависящие от различного числапеременных. Пусть 3 и ФФ,(1, 2 ), - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0, 1, 2). Несложно показать, что при выполнении условия 33, 1, 1,,(3) имеет место.(4) Из (3) и (4) непосредственно следует, что вектор (Ф)(0, 1 ) коэффициентов полиномиального разложения (1) м.с.б.ф. ФФ имеет вид(Ф)(0 , 1 ,,)(0 , 1 ,2 ,3 , 1 ,2 ,3 , , 1 ,2 ,3 , ,3 ) ,1 24 1 24 4 3 4 3 1 24 4 3 где(-3)/3. Тогда с учетом (5) м.с.б.ф. ФФ может быть однозначно задана полиномиальным локальным кодом к(Ф)(к 0, к 1, к 2, к 3)(0, 1, 2, 3),(6) элементы которого могут быть вычислены из модулярного локального кода (Ф) к 000 Очевидно, что при заданной величине модуляодин и тот же полиномиальный локальный код к(Ф) вида (6) имеют м.с.б.ф. ФФ, зависящие от различного числапеременных. При величине модуля 3 разложение (1) м.с.б.ф. ФФ примет вид(9) к 3 к 1 к 2. Тогда, принимая во внимание (9), полиномиальное разложение (8) представим в канонической форме 1 1 2 Функциииназываются фундаментальными полиномиальными м.с.б.ф., а вектор к(Ф)(к 0, к 1, к 2) - каноническим полиномиальным модулярным локальным кодом. В предлагаемом устройстве блок вычисления симметрических булевых функций 25 реализует все м.с.б.ф. двух переменных, а каждая группа логических элементов, содержащая по три элемента сложения по модулю два и по четыре элемента И, обеспечивает увеличение числа обрабатываемых переменных на две единицы. При этом вектором настройки устройства на реализацию конкретной м.с.б.ф ФФ является вектор коэффициентов ее канонического полиномиального разложения к(Ф)(к 0, к 1, к 2). Устройство при 8 (фигура) работает следующим образом. На информационные входы 26-33 подаются двоичные переменные 1-8 (в произвольном порядке), на настроечные входы 34, 35 и 36 - соответственно компоненты к 0, к 1, и к 2 вектора к(Ф)(к 0, к 1, к 2) коэффициентов канонического полиномиального разложения м.с.б.ф. ФФ, значения которой реализуются на выходе 37 устройства. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются простая конструкция, регулярная и однородная структура и широкие функциональные возможности. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5