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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 4, 5, 6 содержащее блок вычисления модулярных симметрических булевых функцийпеременных, где 22, выход которого соединен с выходом устройства, а -й информационный вход, где 1,, соединен с -м информационным входом устройства, отличающееся тем, что содержит три блока вычисления модулярных симметрических булевых функцийпеременных, выход -го из которых, где 1, 2, 3,соединен с -м настроечным входом блока вычисления модулярных симметрических булевых функцийпеременных,-й информационный вход, где 1,, соединен с-м информационным входом устройства, первый настроечный вход которого соединен с первым настроечным входом первого блока вычисления модулярных симметрических булевых функцийпеременных, третьим настроечным входом второго блока вычисления модулярных симметрических булевых функцийпеременных и вторым настроечным входом третьего блока вычисления модулярных симметрических булевых функцийпеременных, второй настроечный вход устройства соединен со вторым настроечным входом первого блока вычисления модулярных симметрических булевых функцийпеременных, первым настроечным входом второго блока вычисления модулярных симметрических булевых функцийпеременных и третьим настроечным входом третьего блока вычисления модулярных симметрических булевых функцийпеременных, третий настроечный вход устройства соединен с третьим настроечным входом первого блока вычисления модулярных симметрических булевых функций - переменных, вторым настроечным входом второго блока вычисления модулярных симметрических булевых функцийпеременных и первым настроечным входом третьего блока вычисления модулярных симметрических булевых функцийпеременных. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления симметрических булевых функцийпеременных, содержащее многофункциональный логический модуль синформационными входами (1, 2, 3,), и 1 многофункциональных логических модулей синформационными входами 1. Устройство реализует симметрические булевы функциипеременных, включая модулярные симметрические булевы функции. Недостатком устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащее 33 элементов 2-2 И-2 ИЛИ иэлементов НЕ 2. Устройство реализует восемь модулярных симметрических булевых функцийпеременных для величины модуля 3. Недостатком известного устройства является низкое быстродействие. Изобретение направлено на решение задачи повышения быстродействия устройства для вычисления модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем введения в состав устройства трех блоков для вычисления модулярных симметрических булевых функций, а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 4, 5, 6 содержит блок вычисления модулярных симметрических булевых функцийпеременных, где 22, выход которого соединен с выходом устройства, а-й информационный вход, где 1,, соединен с -м информационным входом устройства. В отличие от прототипа, устройство содержит три блока вычисления модулярных симметрических булевых функцийпеременных, выход -го из которых, где 1, 2, 3, соединен с -м настроечным входом блока вычисления модулярных симметрических булевых функцийпеременных, а -й информационный вход, где 1,, соединен с-м информационным входом устройства. Первый настроечный вход устройства соединен с первым настроечным входом первого блока вычисления модулярных симметрических булевых функцийпеременных,третьим настроечным входом второго блока вычисления модулярных симметрических бу 2 15642 1 2012.04.30 левых функцийпеременных и вторым настроечным входом третьего блока вычисления модулярных симметрических булевых функцийпеременных. Второй настроечный вход устройства соединен со вторым настроечным входом первого блока вычисления модулярных симметрических булевых функцийпеременных,первым настроечным входом второго блока вычисления модулярных симметрических булевых функцийпеременных и третьим настроечным входом третьего блока вычисления модулярных симметрических булевых функцийпеременных. Третий настроечный вход устройства соединен с третьим настроечным входом первого блока вычисления модулярных симметрических булевых функцийпеременных,вторым настроечным входом второго блока вычисления модулярных симметрических булевых функцийпеременных и первым настроечным входом третьего блока вычисления модулярных симметрических булевых функцийпеременных. На фиг. 1 представлена схема предлагаемого устройства для вычисления модулярных симметрических булевых функцийпеременных. Устройство содержит три блока вычисления модулярных симметрических булевых функцийпеременных 1, 2 и 3, блок вычисления модулярных симметрических булевых функцийпеременных 4,информационных входов 515, три настроечных входа 6, 7 и 8, выход 9. Поясним принцип построения и работы предлагаемого устройства. Пусть( ,) - некоторый кортеж длины , содержащий только элементы 0, 1, и 0. Булева функция,(1, 2 ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф. ФФ,(1, 2 ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12) двоичной кодовой комбинации по модулю ,Ф 1 ,0 Ф 1 ,0,где, 0, 0,. М.с.б.ф. ФФ может быть задана -разрядным модулярным локальным кодом(Ф)(0, 1 -1),1 0 гдеФ(,),, 0,0,1 . Один и тот же модулярный локальный код (Ф) могут иметь м.с.б.ф., зависящие от различного числапеременных. Количество различных м.с.б.ф.переменных не зависит от , а определяется только величиной модуляи равно 2. Модулярная симметрическая булева функцияпеременных ФФ( ),0,1 ,называется фундаментальной (ф.м.с.б.ф.), если 1, если ( 12) ФФ( )0, если ( 12),где- величина модуля. В дальнейшем будем рассматривать м.с.б.ф. ФФ, заданные своим модулярным локальным кодом (Ф)(0, 1, 2) только для величины модуля 3. Произвольная м.с.б.ф. ФФпеременных может быть однозначно представлена посредством ф.м.с.б.ф в виде Ф( )0 Ф 0 ( )1 Ф 1 ( )2 Ф 2 ( ) . Ф(1 ) - ф.м.с.б.ф. отпеременных. Локальные коды функций(2) могут быть определены из локального кода Первообразной функцией многофункционального логического модуля называется логическое (булево) выражение, устанавливающее связь между реализуемой на выходе модуля булевой функцией и элементами вектора входных переменных и вектора настройки. Многофункциональные логические модули, реализующие только все 2 м.с.б.ф.переменных (для рассматриваемой величины модуля ) назовем модулярными. Такие модули являются универсальными в классе м.с.б.ф. и имеютинформационных входов инастроечных входов. Модулярные логические модули, вектором настройки которых на реализацию конкретной м.с.б.ф. ФФ является ее локальный код (Ф)(0, 1 -1), назовем модулями -типа. Пусть (, ((, 0, 1, 2) - первообразная функция модуля -типа, реализующего все м.с.б.ф.переменных при 3. При описании модулей -типа как черных ящиков в качестве первообразной функции (, ( может выступать выражение (1), т.е.(, (0 Ф 0 ( )1 Ф 1 ( )2 Ф 2 ( ) . Первообразные функции всех модулей -типа, независимо от их конкретной структуры (схемотехнической реализации), путем тождественных преобразований могут быть сведены к виду (4), поскольку м.с.б.ф. ФФ однозначно определяется вектором (Ф). Из анализа выражений (1), (2) и (4) следует, что произвольная м.с.б.ф.переменных ФФ может быть реализована на выходе модуля -типа, имеющегоинформационных входов (на них подаются двоичные переменные 1 из 1) и три настроечных входа,на которые в качестве сигналов настройки должны подаваться значения остаточных м.с.б.ф. 0(2), 1(2) и 2(2) на соответствующих наборах переменных из 2. В связи с этим первообразную функцию модуля -типа синформационными входами можно представить посредством первообразной функции модуля -типа синформационными входами(, ((1, 0(2), 1(2), 2(2. Тогда, принимая во внимание (3), каждую м.с.б.ф.(2),0, 1, 2, можно реализовать модулем -типа синформационными входами, а именно( 2 , ( 0( 2 ,0 , 1 ,2 )0 Ф 0( 2 )1 Ф 1( 2 )2 Ф 2( 2 ) Следовательно, с учетом (5) первообразная функция примет вид(, (Ф(1, -(2, (0, -(2, (1), -(2, (2. Таким образом, согласно (6) устройство для вычисления м.с.б.ф.переменных (модулярный логический модуль -типа синформационными входами) может быть построено по двухуровневой каскадной схеме, а именно 15642 1 2012.04.30 первый уровень - модулярный логический модуль -типа синформационными входами (на них подаются переменные кортежа 1), выход которого соединен с выходом устройства второй уровень - три модулярных логических модуля -типа синформационными входами (на них подаются переменные кортежа 2), выходы которых соединены соответственно с настроечными входами модуля первого уровня. При этом настроечные входы устройства в целом организуются путем отождествления настроечных входов модулей второго уровня в соответствии с (3). Устройство для вычисления м.с.б.ф.переменных построено в соответствии с первообразной функцией вида (6) и при настройке сигналами из множества 0, 1 реализует восемь модулярных симметрических булевых функцийпеременных для величины модуля 3. Вектором настройки устройства на реализацию конкретной м.с.б.ф ФФ является ее модулярный локальный код (Ф). Устройство для вычисления модулярных симметрических булевых функций (фиг. 1) работает следующим образом. На информационные входы 51-5 подаются двоичные переменные 1- (в произвольном порядке), на настроечные входы 6, 7 и 8 - соответственно компоненты 0, 1 и 2 модулярного локального кода (Ф)(0, 1, 2) м.с.б.ф. ФФ, значения которой реализуются на выходе 9 устройства. Рассмотренный принцип построения устройств для вычисления м.с.б.ф.переменных позволяет строить многоуровневые структуры модулярных логических модулей -типа. Следует особо отметить, что количество модулей на каждом уровне структуры постоянно и равно величине модуля 3. При этом отождествление настроечных входов модулей на каждом уровне осуществляется аналогично, как и для двухуровневой структуры устройства. В качестве примера на фиг. 2 представлена трехуровневая структура устройства для вычисления м.с.б.ф.9 переменных с первообразной функцией вида 9(, (Ф 3(1, 3(2, 3(3, 0, 1, 2), 3(3, 1, 2, 0), 3(3, 2, 0, 1,3(2, 3(3, 1, 2, 0), 3(3, 2, 0, 1), 3(3, 0, 1, 2,3(2, 3(3, 2, 0, 1), 3(3, 0, 1, 2), 3(3, 1, 2, 0. где 1(1,2,3), 2(4,5,6), 3(7,8,9). Устройство содержит семь модулей -типа с тремя информационными входами 10-16,9 информационных входов 17-25, три настроечных входа 26, 27 и 28, выход 29. Устройство для вычисления модулярных симметрических булевых функций 9 переменных (фиг. 2) работает следующим образом. На информационные входы 10-16 подаются двоичные переменные 1-9 (в произвольном порядке), на настроечные входы 26, 27 и 28 - соответственно компоненты 0,и 2 модулярного локального кода (Ф)(0, 1, 2) м.с.б.ф. ФФ(1, х 2 х 9), значения которой реализуются на выходе 29 устройства. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются высокое быстродействие, простая конструкция, возможность увеличения числа переменных, реализуемых функций. Источники информации 1. Патент РБ 11757, МПК 06 7/00, 2009. 2. Патент РБ 11758, МПК 06 7/00, 2009 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 6