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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЧАСТИЧНО СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления частично симметрических булевых функцийпеременных,характеризующееся тем, что содержит первый многофункциональный логический модуль,11756 1 2009.04.30 выход которого соединен с выходом устройства,-й, где 1,, где 1, 2, 3 информационный вход соединен с -м входом первой группы информационных входов устройства,1, где 2, 3, 4 линейку многофункциональных логических модулей,-я из которых, где 1,1 , содержитгрупп по 1 модулей в каждой группе, где(11)001, 2, 3,- количество переменных частично сим(1)-й группы информационных входов устройства, -й, где 1,11 , настроечный вход первого модуля соединен с выходом -го модуля первой линейки, -й, где 1,11 , настроечный вход -го модуля -й группы -й линейки, где 1,2 ,соединен с выходом -го модуля 1)(1)) -й группы (1)-й линейки, -1-й,где 11,1 , настроечный вход -1-го модуля -1-й группы (-1)-й линейки соединен с 11)(11)11)(1)1 ) -м настроечным входом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления бисимметрических булевых функцийпеременных, содержащее два многовходовых одноразрядных сумматора и мультиплексор 1. Недостатком известного устройства являются ограниченные функциональные возможности, поскольку оно реализует частично симметрические булевы функции, зависящие только от двух кортежей попарно симметрических переменных. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления бисимметрических булевых функцийпеременных, содержащее два блока вычисления веса двоичных кодовых комбинаций, группу элементов И и элемент ИЛИ 2. Недостатком известного устройства также являются ограниченные функциональные возможности, так как оно не реализует частично симметрические булевы функции, зависящие от трех и более кортежей попарно симметрических переменных. Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления частично симметрических булевых функций, зависящих от произвольного числа кортежей попарно симметрических переменных. Названный технический результат достигается путем использования для построения устройства многофункциональных логических модулей (устройств для вычисления симметрических булевых функций) с ограниченным числом информационных входов, соединенных между собой по специальной схеме. Устройство для вычисления частично симметрических булевых функцийпеременных содержит первый многофункциональный логический модуль, выход которого соединен с выходом устройства, а 1-й, где 11, 1 , где 11, 2, 3 информационный вход соединен с 1-м входом первой группы информационных входов устройства. Кроме того, устройство содержит 1, где 2, 3, 4 линейку многофункциональных логических модулей, -я из которых, где 1,1 , содержит р групп по 1 модулей в каждой группе, где(11)001, 2, 3,- количество переменных частично симметрических булевых функций. 2 11756 1 2009.04.30 При этом 1-й, где 11,1 , информационный вход -го, где 1,1 , модуля -й,где 1,, группы -й линейки соединен с 1-м входом (1)-й группы информационных входов устройства, -й, где 1, 11 , настроечный вход первого модуля соединен с выходом -го модуля первой линейки,-й , где 1,11 , настроечный вход- 1)(1))-й группы (1)-й линейки, -1-й, где 11,1 , настроечный вход -1 -го модуля-1 -й группы (1)-й линейки соединен с 1 - 1)(11)-11)(1)-1)-м настроечным входом устройства. На фигуре представлена схема устройства для вычисления частично симметрических булевых функцийпеременных при 7 и 12, 22, 33 (3). Устройство содержит первый многофункциональный логический модуль 1 с 12 информационными входами,12 линейки многофункциональных логических модулей (1011 одну группу из 113 модулей 2, 3 и 4 с 22 информационными входами первой линейки р 2(0)(11)3 группы по 213 модуля в каждой с 33 информационными входами второй линейки - модули первой группы 5, 6 и 7, модули второй группы 8, 9 и 10, модули третьей группы 11, 12 и 13), 12 входа 14 и 15 первой группы информационных входов устройства, 22 входа 16 и 17 второй группы информационных входов устройства, 33 входа 18, 19 и 20 третьей группы информационных входов устройства, (11)(21)(31)36 настроечных входов 21-56 устройства и один выход 57 устройства. Устройство (фигура) реализует 2(1 1)(2 1)(3 1)236 частично симметрических булевых функций 7 переменных (включая функции все 2128 симметрические булевы функции 7 переменных) при настройке сигналами из множества 0,1. Поясним принцип построения и работы устройства для вычисления частично симметрических булевых функцийпеременных. Обозначим( ,,,) - некоторый кортеж длины , содержащий только элемен ты 0,1 и 0. Булева функция,(х 1, х 2 х), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1 ),где(1 ,0) ,0,. Очевидно, что в локальном коде ( ) ф.с.б.ф.только один элемент 1 (все остальные элементы 0, 0,1). Очевидно, что произвольная с.б.ф.отпеременных может быть однозначно представлена посредством ф.с.б.ф в виде Определение. Первообразной функцией многофункционального логического модуля называется логическое (булево) выражение, устанавливающее связь между реализуемой на выходе модуля булевой функцией и элементами вектора входных переменных и вектора настройки. 11756 1 2009.04.30 Известны многофункциональные логические модули (универсальные в классе с.б.ф.),имеющиеинформационных входов (на них подаются двоичные переменные х 1, х 2 х) и 1 настроечных входов, на которые подаются сигналы настройки 0, 1 , определяющие реализуемую на единственном выходе модуля с.б.ф., заданную своим локальным кодом(0, 1 ). Многофункциональные логические модули, вектором настройки которых на реализацию конкретной с.б.ф.является ее локальный код , назовем модулями -типа. Обозначим (Х, ((Х, 0, 1 ) - первообразная функция модуля -типа,реализующего все с.б.ф.переменных. При описании модулей -типа как черных ящиков в качестве первообразной функции (, ( может выступать выражение (1), т.е. Первообразные функции всех модулей -типа, независимо от их конкретной структуры (схемотехнической реализации), путем тождественных преобразований могут быть сведены к виду (2), поскольку с.б.ф.однозначно определяется вектором . Нетривиальная частичная симметрия индуцирует разбиение вектора переменных Х(х 1, 2 х) частично симметрической булевой функции (ч.с.б.ф.)накортежей Х 1, Х 2 , 1. При этомсимметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу , 1. Тогда число классов эквивалентности ч.с.б.ф.определяется выражением Каждый класс эквивалентности характеризуется вектором(, 2 ), а 0, 1 1. Локальный код С ч.с.б.ф.есть двоичный вектор длины , каждая компонента которого равна значениюна соответствующем классе эквивалентности наборов значений ее аргументов. Упорядочивая векторы А, представим С в виде где булева константа 1 2 равна значению ч.с.б.ф.на наборах переменных из ,удовлетворяющих условию 11756 1 2009.04.301 23456712341234345346347 . Принимая во внимание (4) и (5), построим локальный код ч.с.б.ф.(000, 001, 002, 003, 010, 011, 012, 013, 020, 021, 022, 023, 100, 101, 102,103, 110, 111, 112, 113, 120, 121, 122, 123, 200, 201, 202, 203, 210, 211, 212, 213, 220,221, 222, 223)(0,0,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0). Любая ч.с.б.ф.(, Х 2 ) может быть представлена посредством ф.с.б.ф., зависящих от переменных кортежей ,1,, в виде 1 где 1 2- элементы локального кода (4),0,,1,. Преобразуем выражение (6) к виду 12111 (1 )22 ( 2 )11 (1 )1201020 10 Декомпозиционное разложение (7) по кортежам Х,1,, попарно симметрических переменных определяет -уровневую каскадную структуру устройства для вычисления частично симметрических функцийпеременных, -й уровень которой содержит многофункциональные логические модули -типа с первообразной функцией вида (2). При этом на информационные входы модулей -го уровня поступают переменные только кортежа . Предлагаемое устройство построено в соответствии с разложением (7) и реализует 2 ч.с.б.ф.переменных, где- длина локального кода ч.с.б.ф., определяемая формулой (3). Вектором настройки устройства на реализацию конкретной ч.с.б.ф.является ее локальный код С. Пример 2. Получим выражение для первообразной функции устройства при 7 и 12, 22,33 (3) через первообразные модулей -типа. Тогда (7) примет вид 223221 (1 )22 ( 2 )33 (3 )1 2 321 (1 )301020 10 3 ( 3 ,1 2 ) - первообразная функция модуля -типа с тремя информационными и четырьмя настроечными входами. Проведем дальнейшие преобразования выражения (8) Устройство для вычисления частично симметрических булевых функций семи переменных при 12, 22, 33 (фигура) построено согласно первообразной функции (9). Устройство для вычисления частично симметрических булевых функций при 7(фигура) работает следующим образом. На информационные входы 14 и 15 первой группы подаются двоичные переменные х 1 и х 2 кортежа Х 1 (в произвольном порядке), на информационные входы 16 и 17 второй группы - двоичные переменные х 3 и х 4 кортежа Х 2 (в произвольном порядке), на информационные входы 18, 19 и 20 третьей группы - двоичные переменные х 5, х 6 и х 7 кортежа Х 3 (в произвольном порядке), на настроечные входы 21, 22 56 - соответственно компоненты С 000, С 001 С 223 локального кода С ч.с.б.ф.(Х 1, Х 2, Х 3), значения которой реализуются на выходе 57 устройства. Пример 3. Определим сигналы настройки устройства (фигура) на реализацию заданной своим локальным кодом С ч.с.б.ф.(Х 1, Х 2, Х 3) из примера 1 С(0,0,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0). Поскольку вектор настройки устройства совпадает с локальным кодом С реализуемой функции , то на настроечные входы 21-24 подаются соответственно компоненты кортежа С 00(000, С 001, С 002, С 003)(0,0,0,1), на настроечные входы 25-28 - соответственно компоненты кортежа С 01(010, С 011, С 012, С 013)(0,0,0,0), на настроечные входы 29-32 соответственно компоненты кортежа С 02(020, С 021, С 022, С 023)(1,1,1,0), на настроечные входы 33-36 - соответственно компоненты кортежа С 10(100, С 101, С 102, С 103)(1,1,1,1),на настроечные входы 37-40 - соответственно компоненты кортежа С 11(110,С 111, С 112,С 113)(0,0,0,0), на настроечные входы 41-44 - соответственно компоненты кортежа С 12(С 120,С 121,С 122,С 123)(1,1,1,0), на настроечные входы 45-48 - соответственно компоненты кортежа С 20(200, С 201, С 202, С 203)(0,0,0,0), на настроечные входы 49-52 - соответственно компоненты кортежа С 21(210,С 211, С 212, С 213)(0,0,0,0), на настроечные входы 53-56 - соответственно компоненты кортежа С 22(С 220,С 221,С 222,С 223)(1,1,1,0). Тогда, в соответствии с (1) и (2), на выходах модулей второй линейки реализуются симметрические булевы функции на выходе модуля 5 - 00(3)33(3)5 х 6 х 7 на выходе модуля 6 - 11(Х 3)0 0 1 2 на выходе модуля 7 -22 (3 )3 ( 3 )3 ( 3 )3 (3 )567 на выходе модуля 8 - 33(Х 3)1 на выходе модуля 9 - 44(Х 3)0 на выходе модуля 10 -55 (3 )2 ( 3 )567 на выходе модуля 11 - 66(Х 3)0,на выходе модуля 12 - 77(3)0 на выходе модуля 13 - 88 ( 3 )2 ( 3 )5 ( 3 )567 . 6 11756 1 2009.04.30 На выходах модулей первой линейки реализуются частично симметрические булевы функции 2 1 0 на выходе модуля 2 - 00 ( 2 , 3 )02 ( 2 )12 ( 2 )22 ( 2 )2 05672 ( 2 )(567 )2 ( 2 )3 45673 4 (567 ) 2 1 0 на выходе модуля 3 - 11 ( 2 , 3 )32 ( 2 )42 ( 2 )52 ( 2 )2 02 ( 2 )(567 )2 ( 2 )3 43 4 (567 ) 2 1 0 на выходе модуля 4 - 22 ( 2 , 3 )62 ( 2 )7 2 ( 2 )82 ( 2 )2(567 )2 ( 2 )34 (567 ) . На выходе модуля 1 (выходе 57 устройства) реализуется заданная частично симметрическая булева функция 0 1 2(1 ,2 ,3 )0 2 (1 )12 (1 )2 2 (1 )0 12 (1 )(3456734 (5672 (1 )(3434 (56722 (1 )(34 (5671 2 (3456734 (567 1 2345671 2341234345346347 . Следует отметить, что устройство реализует и все 21 симметрические булевы функциипеременных. В этом случае сигналы настройки находятся из локального кода(0 ) с.б.ф.по правилу Это означает, что на настроечный вход устройства, на который подается элемент локального кода С ч.с.б.ф., должен быть подан элемент 12 ло кального кодас.б.ф.. При этом на информационные входы устройства переменные(х 1, х 2 х) реализуемой с.б.ф.подаются в произвольном порядке(без учета групп информационных входов). Пример 4. Определим вектор настройки устройства (фигура) на реализацию заданной своим локальным кодом(0, 17) некоторой с.б.ф.семи переменных. Из соотношения (10) непосредственно следует, что вектор настройки примет вид 11756 1 2009.04.30 Достоинствами устройства являются простая конструкция и возможность вычисления частично симметрических булевых функций произвольного числапеременных. При этом для построения устройства используются многофункциональные логические модули с ограниченным числом информационных входов. Источники информации Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.