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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(71) Заявитель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 2 - число переменных реализуемых функций, где 4,5,6 характеризующееся тем, что содержит- 1 групп из девяти элементов ИЛИ-НЕ каждая, -ю группу из трех элементов ИЛИ-НЕ, элемент ИЛИ-НЕ,элементов ИЛИ,элементов сложения по модулю два иэлементов И-НЕ, причем (2- 2)-й, где 1,, где 1,2, информационный вход устройства соединен с -м входом -го элемента ИЛИ, -м входом -го элемента сложения по модулю два и -м входом -го элемента И-НЕ, выход го, где 1,1 , элемента ИЛИ соединен с первым входом (3 - 2)-го, где 1,2,3, элемента ИЛИ-НЕ -й группы, инверсный выход -го элемента сложения по модулю два соединен с первым входом (3 - 1)-го элемента ИЛИ-НЕ -й группы, выход -го элемента И-НЕ 13928 1 2010.12.30 соединен с первым входом 3-го элемента ИЛИ-НЕ -й группы, выход -го элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ -ой группы, инверсный выход го элемента сложения по модулю два соединен с первым входом второго элемента ИЛИНЕ -й группы, выход -го элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ -ой группы, первый настроечный вход устройства соединен со вторым входом первого элемента ИЛИ-НЕ первой группы, вторым входом шестого элемента ИЛИ-НЕ первой группы и вторым входом восьмого элемента ИЛИ-НЕ первой группы, второй настроечный вход устройства соединен со вторым входом второго элемента ИЛИ-НЕ первой группы, вторым входом четвертого элемента ИЛИ-НЕ первой группы и вторым входом девятого элемента ИЛИ-НЕ первой группы, третий настроечный вход устройства соединен со вторым входом третьего элемента ИЛИ-НЕ первой группы, вторым входом пятого элемента ИЛИ-НЕ первой группы и вторым входом седьмого элемента ИЛИ-НЕ первой группы, выход -го элемента ИЛИ-НЕ -й, где 1,2 , группы соединен с (1)м входом первого элемента ИЛИ-НЕ (1)-й группы, (1)-м входом шестого элемента ИЛИ-НЕ (1)-й группы и (1)-м входом восьмого элемента ИЛИ-НЕ (1)-й группы,выход (3)-го элемента ИЛИ-НЕ -й группы соединен с (1)-м входом второго элемента ИЛИ-НЕ (1)-й группы, (1)-м входом четвертого элемента ИЛИ-НЕ (1)-й группы и (1)-м входом девятого элемента ИЛИ-НЕ (1)-й группы, выход (6)-го элемента ИЛИ-НЕ -й группы соединен с (1)-м входом третьего элемента ИЛИ-НЕ(1)-й группы, (1)-м входом пятого элемента ИЛИ-НЕ (1)-й группы и (1)-м входом седьмого элемента ИЛИ-НЕ (1)-й группы, выход -го элемента ИЛИ-НЕ ( - 1)й группы соединен с (1)-м входом первого элемента ИЛИ-НЕ -й группы, выход(3)-го элемента ИЛИ-НЕ ( - 1)-й группы соединен с (1)-м входом второго элемента ИЛИ-НЕ -й группы, выход (6)-го элемента ИЛИ-НЕ ( - 1)-й группы соединен с(1)-м входом третьего элемента ИЛИ-НЕ -й группы, выход -го элемента ИЛИ-НЕ й группы соединен с -м входом элемента ИЛИ-НЕ, выход которого соединен с выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащееэлементов(6,7,8, - число переменных реализуемых функций),групп элементов 2-2 И-2 ИЛИ,информационных входов, пять настроечных входов и один выход 1. Устройство реализует тридцать две модулярные симметрические булевы функциипеременных для величины модуля 5. Недостатками известного устройства являются низкое быстродействие и невозможность вычисления модулярных симметрических булевых функций для величины модуля 3. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащее 3-3 элементов 2-2 И-2 ИЛИ,элементов ,информационных входов, три настроечных входа и один выход 2. Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы. 2 13928 1 2010.12.30 Изобретение направлено на решение задачи повышения быстродействия устройства для вычисления модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем использования в схеме устройства элементов ИЛИ-НЕ, И-НЕ, ИЛИ и сложения по модулю два, а также изменением связей между логическими элементами. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 2 - число переменных реализуемых функций, где 4,5,6, содержит-1 группу элементов ИЛИ-НЕ по девять элементов в каждой, -ю группу элементов ИЛИ-НЕ из трех элементов, элемент ИЛИ-НЕ,элементов ИЛИ,элементов сложения по модулю два иэлементов И-НЕ. При этом (2- 2)-й, где 1,, где 1,2, информационный вход устройства соединен с -м входом -го элемента ИЛИ, -м входом -го элемента сложения по модулю два и -м входом -го элемента И-НЕ. Выход -го, где 1,1 , элемента ИЛИ соединен с первым входом (3 - 2)-го, где 1,2,3, элемента ИЛИ-НЕ -й группы, инверсный выход -го элемента сложения по модулю два соединен с первым входом (3-1)-го элемента ИЛИ-НЕ -й группы, выход -го элемента И-НЕ соединен с первым входом 3-го элемента ИЛИ-НЕ -й группы. Выход -го элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ -й группы, инверсный выход -го элемента сложения по модулю два соединен с первым входом второго элемента ИЛИ-НЕ -й группы, выход -го элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ -й группы. Первый настроечный вход устройства соединен со вторым входом первого элемента ИЛИ-НЕ первой группы, вторым входом шестого элемента ИЛИ-НЕ первой группы и вторым входом восьмого элемента ИЛИ-НЕ первой группы, второй настроечный вход устройства соединен со вторым входом второго элемента ИЛИ-НЕ первой группы, вторым входом четвертого элемента ИЛИ-НЕ первой группы и вторым входом девятого элемента ИЛИ-НЕ первой группы, третий настроечный вход устройства соединен со вторым входом третьего элемента ИЛИ-НЕ первой группы, вторым входом пятого элемента ИЛИНЕ первой группы и вторым входом седьмого элемента ИЛИ-НЕ первой группы. Выход -го элемента ИЛИ-НЕ -й, где 1,2 , группы соединен с (1)-м входом первого элемента ИЛИ-НЕ (1)-й группы, (1)-м входом шестого элемента ИЛИ-НЕ(1)-й группы и (1)-м входом восьмого элемента ИЛИ-НЕ (1)-й группы, выход(3)-го элемента ИЛИ-НЕ -й группы соединен с (1)-м входом второго элемента ИЛИ-НЕ (1)-й группы, (1)-м входом четвертого элемента ИЛИ-НЕ (1)-й группы и (1)-м входом девятого элемента ИЛИ-НЕ (1)-й группы, выход (6)-го элемента ИЛИ-НЕ -й группы соединен с (1)-м входом третьего элемента ИЛИ-НЕ (1)-й группы, (1)-м входом пятого элемента ИЛИ-НЕ (1)-й группы и (1) -м входом седьмого элемента ИЛИ-НЕ (1)-й группы. Выход -го элемента ИЛИ-НЕ (-1)-й группы соединен с (1)-м входом первого элемента ИЛИ-НЕ -й группы, выход (3)-го элемента ИЛИ-НЕ (-1)-й группы соединен с (1)-м входом второго элемента ИЛИ-НЕ -й группы, выход (6)-го элемента ИЛИ-НЕ (-1)-й группы соединен с (1)-м входом третьего элемента ИЛИ-НЕ -й группы. Выход -го элемента ИЛИ-НЕ -й группы соединен с -м входом элемента ИЛИНЕ, выход которого соединен с выходом устройства. На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных при 10 (5). Устройство содержит 9 - 540 элементов ИЛИ-НЕ 1-40,5 элементов ИЛИ 4145,5 элементов сложения по модулю два с инверсным выходом 46-50,5 элемен 3 13928 1 2010.12.30 тов И-НЕ 51-55,210 информационных входов 56-65, три настроечных входа 66, 67 и 68, выход 69. Поясним принцип построения и работы устройства для вычисления модулярных симметрических булевых функцийпеременных. Обозначим( ,) - некоторый кортеж длины , содержащий только элемен ты 0,1, и 0. Булева функция,(1, 2, , х), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . В классе симметрических булевых функций выделяется подкласс так называемых модулярных с.б.ф. (м.с.б.ф.). С.б.ф. ФФ,(1,2, , ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(2)двоичной кодовой комбинации по модулю ,где, 0, 0, . В дальнейшем рассматриваем м.с.б.ф. ФФ только для величины модуля 3. Очевидно, что м.с.б.ф. ФФ можно задавать трехразрядным модулярным локальным кодом Один и тот же модулярный локальный код (Ф) вида (1) могут иметь м.с.б.ф., зависящие от различного числапеременных. При этом в классе с.б.ф.переменных количество (2238) различных м.с.б.ф. определяется только величиной модуля 3 и не зависит от . Пусть ФФ,(1,2 х), - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0, 1, 2). М.с.б.ф. ФФ допускает конъюнктивное разложение по паре некоторых переменныхи , 1. 1, , вида ФФ( ))0 )12 ,(2) где 0, 1, 2 - остаточные м.с.б.ф. от -2 переменных. Дизъюнктивное разложение м.с.б.ф. ФФ по переменнымиимеет вид(3) ФФ 012 ,Модулярные локальные коды м.с.б.ф. 0, 1 и 2 определяются из кода (Ф) В свою очередь, к остаточным м.с.б.ф. 0, 1 и 2 также можно применить разложения видов (2) и (3) и так далее, вплоть до получения вырожденных остаточных функций(констант нуля или единицы), которыми будут являться элементы модулярного локального кода (Ф). 4 13928 1 2010.12.30 Таблица локальных кодов м.с.б.ф. ФФ при 10 и 3 Вектор настройки (Ф)(0, 1, 2) Локальные коды реализуемых на выходе 69 м.с.б.ф. 0/66 1/67 2/68(Ф)(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) Предлагаемое устройство строится на основе чередования конъюнктивного (2) и дизъюнктивного (3) разложений м.с.б.ф. ФФ последовательно по парам переменных(1,2), (3,4), , (-1,) и группирования тождественных остаточных функций на каждом уровне разложения с учетом их модулярных локальных кодов (4). При таком чередовании разложений (2) и (3) в схеме устройства соседними будут являться уровни элементов И-ИЛИ и ИЛИ-И. В результате слияния соседних уровней логических элементов от схемы И-ИЛИ-ИЛИ-И переходим к схеме И-ИЛИ-И. Далее,применяя закон двойного отрицания, переходим от схемы с уровнями И-ИЛИ к схеме на элементах ИЛИ-НЕ. При этом вектором настройки устройства на реализацию конкретной м.с.б.ф. ФФ будет являться ее модулярный локальный код (Ф)(0, 1, 2). Устройство для вычисления модулярных симметрических булевых функций при 10 (фигура) работает следующим образом. На информационные входы 56-65 подаются двоичные переменные 1,2, , 10 (в произвольном порядке), на настроечные входы 66, 67 и 68 - соответственно компоненты 0, 1 и 2 модулярного локального кода (Ф)(0, 1, 2) м.с.б.ф. ФФ(1,2, , 10),значения которой реализуются на выходе 69 устройства. Локальные коды (Ф)(0,1, , 10) м.с.б.ф. ФФ, реализуемых устройством(фигура), представлены в таблице. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются высокое быстродействие, простая конструкция, однородная и регулярная структура. Источники информации 1. Патент РБ 11888, МПК 06 7/00, 2009. 2. Патент РБ 11758, МПК 06 7/00, 2009 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5