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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления симметрических булевых функцийпеременных, содержащее первый многофункциональный логический модуль, выход которого соединен с выходом устройства, а его -й, где 1,, где 1, 2, 3, , информационный вход соединен 11757 1 2009.04.30 с -м информационным входом устройства, отличающееся тем, что содержит многофункциональные логические модули со второго по (2)-й, выход (1)-го, где 1,1 , из которых соединен с -м настроечным входом первого многофункционального логического модуля, а -й, где 1,, где- число переменных реализуемых симметрических булевых функций, информационный вход соединен с -м информационным входом устройства, -й, где 1,1 , настроечный вход (1)-го многофункционального логического модуля соединен с (1)-м настроечным входом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления симметрических булевых функцийпеременных,содержащеегрупп логических элементов, -я из которых (1,) содержит 1 элементов сложения по модулю два,1 элементов И,информационных входов и 1 настроечных входов 1. Недостатком известного устройства является низкое быстродействие, определяемое большой глубиной схемы. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является многофункциональный логический модуль (устройство для вычисления симметрических булевых функций пяти переменных), содержащий мажоритарный элемент с порогом два, мажоритарный элемент с порогом три, мажоритарный элемент с порогом четыре, пять элементов ЗАПРЕТ, два элемента ИЛИ, два элемента И, пять информационных входов и шесть настроечных входов 2. Недостатком известного многофункционального логического модуля является ограниченное число переменных реализуемых симметрических булевых функций. Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления симметрических булевых функций, зависящих от произвольного числапеременных, и использования при этом для построения устройства многофункциональных логических модулей с ограниченным числом информационных входов. Названный технический результат достигается путем использования для построения устройства многофункциональных логических модулей с ограниченным числом информационных входов, соединенных между собой по специальной схеме. Устройство для вычисления симметрических булевых функцийпеременных содержащее первый многофункциональный логический модуль, выход которого соединен с выходом устройства, а его -й, где 1,, где 1, 2, 3, , информационный вход соединен с -м информационным входом устройства. В отличие от прототипа, устройство содержит многофункциональные логические модули со второго по (2)-й, выход (1)-го из которых, где 1,1 , соединен с -м настроечным входом первого многофункционального логического модуля,-й, где 1,, где- число переменных реализуемых симметрических булевых функций,информационный вход соединен с -м информационным входом устройства. При этом -й, где 1,1 , настроечный вход -го многофункционального логического модуля соединен с (1)-м настроечным входом устройства. На фиг. 1 представлена схема устройства для вычисления симметрических булевых функцийпеременных при 9 и 4. Устройство содержит один многофункциональный логический модуль 1 с 4 информационными входами,1 многофункциональных логических модулей 2-6 с 5 11757 1 2009.04.30 информационными входами,9 информационных входов 7-15,110 настроечных входов 16-25 и один выход 26. В общем случае устройство реализует все 21 симметрические булевы функциипеременных (включая функции константа ноль и константа единицы) при настройке сигналами из множества 0,1. Поясним принцип построения и работы устройства для вычисления симметрических булевых функцийпеременных. Обозначим(, , ,) - некоторый кортеж длины , содержащий только элемен ты 0,1 и 0. Булева функция,(х 1, х 2, , х), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1, , ),где(1,0) ,0,. Очевидно, что в локальном коде ( ) ф.с.б.ф.только один элемент 1 (все остальные элементы 0, 0,). Очевидно, что произвольная с.б.ф.отпеременных может быть однозначно представлена посредством ф.с.б.ф в виде Пример 1. С.б.ф.от 9 переменных, заданная своим локальным кодом(0, 1, 2,3, 4, 5, 6, 7, 8, 9)(1, 0, 1, 0, 0, 0, 0, 1, 1, 1), согласно (1) имеет вид 0 2 7 8 999999. Определение. Первообразной функцией многофункционального логического модуля называется логическое (булево) выражение, устанавливающее связь между реализуемой на выходе модуля булевой функцией и элементами вектора входных переменных и вектора настройки. Известны многофункциональные логические модули (универсальные в классе с.б.ф.),имеющиеинформационных входов (на них подаются двоичные переменные х 1, х 2, , х) и 1 настроечных входов, на которые подаются сигналы настройки 0, 1, , , определяющие реализуемую на единственном выходе модуля с.б.ф., заданную своим локальным кодом(0, 1, , ). Многофункциональные логические модули, вектором настройки которых на реализацию конкретной с.б.ф.является ее локальный код , назовем модулями -типа. Обозначим (, ((, 0, 1, , ) - первообразная функция модуля -типа,реализующего все с.б.ф.переменных. При описании модулей -типа как черных ящиков в качестве первообразной функции (, ( может выступать выражение (1), т.е. 11757 1 2009.04.30 Первообразные функции всех модулей -типа, независимо от их конкретной структуры (схемотехнической реализации), путем тождественных преобразований могут быть сведены к виду (2), поскольку с.б.ф.однозначно определяется вектором . Пусть Х(Х 1, Х 2), Х 1(1, 2, , х), 2(1, 2, , ), 1. Дизъюнктивное разложение с.б.ф.(1, Х 2) попеременным из Х 1 представим в виде(1 ) - ф.с.б.ф., зависящие отпеременных из Х 1,0,. При этом локальные коды функций (Х 2) могут быть определены из локального кода Заметим, что привыражение (3) примет вид (1). Пример 2. Пусть 9 и- с.б.ф., заданная своим локальным кодом(0, 1, , 9). Выполним дизъюнктивное разложение (3) по 4 переменным из Х 1(1, х 2, х 3, х 4) 4 Локальные коды остаточных с.б.ф.(Х 2),0,4 , определяются согласно (4) из локального кодас.б.ф.( 4 )( 4 ,5 ,6 ,7 ,8 ,9 ).Из анализа выражений (1)-(3) следует, что произвольная с.б.ф.переменныхможет быть реализована на выходе модуля -типа, имеющегоинформационных входов(на них подаются двоичные переменные х 1, х 2, , ) инастроечных входов, на которые в качестве сигналов настройки должны подаваться значения остаточных с.б.ф. 0, 1, ,на соответствующих наборах переменных из Х 2. Следовательно, первообразную функцию модуля -типа синформационными входами можно представить посредством первообразной функции модуля -типа синформационными входами В свою очередь, каждая из с.б.ф.(Х 2),0,, может быть реализована модулем Таким образом, согласно (8) устройство для вычисления с.б.ф.переменных (модуль-типа синформационными входами) может быть построено по двухуровневой каскадной схеме, а именно первый уровень - модуль -типа синформационными входами (на них подаются переменные Х 1), выход которого соединен с выходом устройства второй уровень -модулей -типа синформационными входами (на них подаются переменные Х 2), выходы которых соединены соответственно с настроечными входами модуля первого уровня. При этом настроечные входы устройства в целом организуются путем отождествления настроечных входов модулей второго уровня в соответствии с (4) - -й настроечный вход-го модуля второго уровня соединяется с (1)-м настроечным входом устройства,вектором настройки которого является локальный кодреализуемой с.б.ф.,,,. Предлагаемое устройство для вычисления с.б.ф.переменных построено в соответствии с первообразной функцией вида (8). Пример 3. При 9 и 4 первообразная функция (8) примет вид где(1, 2), 1(1, 2, х 3, х 4), 2(х 5, х 6, х 7, х 8, х 9). Схема устройства с первообразной функцией вида (9) представлена на фиг. 1. Устройство для вычисления с.б.ф.переменных при 9 и 4 (фиг. 1) работает следующим образом. На информационные входы 7, 8, , 15 подаются двоичные переменные х 1, х 2, , х 9 (в произвольном порядке), на настроечные входы 16, 17, , 25 - соответственно компоненты 0, 1, , 9 локального кодас.б.ф., значения которой реализуются на выходе 26 устройства. Пример 4. Определим сигналы настройки устройства при 9 и 4 (фиг. 1) на реализацию заданной своим локальным кодомс.б.ф.(1, 2) из примера 1. Поскольку вектор настройки устройства совпадает с локальным кодом реализуемой функции(1, 0, 1, 0, 0, 0, 0, 1, 1, 1), то сигнал логической единицы должен быть подан на настроечные входы 16, 18, 23, 24 и 25, а сигнал логического нуля - на настроечные входы 17, 19, 20, 21 и 22. Действительно, как следует из выражения (5) и фиг. 1, локальные коды с.б.ф.(2),0,4 , реализуемых на выходах модулей 2-6, имеют вид(3)(0, 0, 0, 0, 1, 1) (4)(0, 0, 0, 1, 1, 1). Тогда согласно (1) на выходах модулей второго уровня реализуются с.б.ф. 0 на выходе модуля 200 ( 2 )5 ( 2 )52 ( 2 )1 на выходе модуля 311 ( 2 )5 ( 2 )5 на выходе модуля 422 ( 2 )50 ( 2 )5 ( 2 )5 на выходе модуля 533 ( 2 )54 ( 2 )5 ( 2 )3 5 на выходе модуля 644 ( 2 )5 ( 2 )54 ( 2 )5 ( 2 ) . В соответствии с (3) на выходе 26 модуля 1 (выходе устройства) реализуется с.б.ф. Предлагаемый принцип построения устройств для вычисления с.б.ф.переменных позволяет строить многоуровневые структуры, поскольку каждый из модулей -типа, входящих в двухуровневую структуру, может быть, в свою очередь, построен по двухуровневой схеме. При этом отождествление настроечных входов модулей на каждом уровне осуществляется аналогично, как и для двухуровневой структуры устройства. В качестве примера на фиг. 2 представлена трехуровневая структура устройства для вычисления с.б.ф. девяти переменных (9) с первообразной функцией вида 9 (,)2 (1, 4 ( 2 , 3 (3 , 0 , 1, 2 , 3 ), 3 (3 , 1, 2 , 3 , 4 ),3 (3 , 2 , 3 , 4 , 5 ), 3 (3 , 3 , 4 , 5 , 6 ), 3 (3 , 4 , 5 , 6 , 7 ,4 ( 2 , 3 (3 , 1, 2 , 3 , 4 ), 3 (3 , 2 , 3 , 4 , 5 ), 3 (3 , 3 , 4 , 5 , 6 ),3 (3 , 4 , 5 , 6 , 7 ), 3 (3 , 5 , 6 , 7 , 8 ,4 ( 2 , 3 (3 , 2 , 3 , 4 , 5 ), 3 (3 , 3 , 4 , 5 , 6 ), 3 (3 , 4 , 5 , 6 , 7 ),3 (3 , 5 , 6 , 7 , 8 ), 3 (3 , 6 , 7 , 8 , 9 , где 1( 1 ,2 ),2(3 ,4 ,5 ,6 ),3(7 ,8 ,9 ). 6 11757 1 2009.04.30 Устройство содержит один модуль 27 первого уровня с 12 информационными входами, 113 модуля 28, 29 и 30 второго уровня с 24 информационными входами,1217 модулей 31-37 третьего уровня с 3123 информационными входами,9 информационных входов 38-46,110 настроечных входов 47-56 и один выход 57. Устройство для вычисления с.б.ф.9 переменных при 12, 24, 33 (фиг. 2) работает следующим образом. На информационные входы 38, 39, , 46 подаются двоичные переменные х 1, х 2, , х 9(в произвольном порядке), на настроечные входы 47, 48, , 56 - соответственно компоненты 0, 1, , 9 локального кодас.б.ф., значения которой реализуются на выходе 57 устройства. Тогда согласно (2)-(4) на выходах модулей 27-37 реализуются с.б.ф. 3 на выходе модуля 3100 ( 3 )3 ( 3 ), ( 0 )( 0 , 1 ,2 ,3 )0 3 на выходе модуля 3211 ( 3 )13 ( 3 ), (1 )(1 ,2 ,3 ,4 )0 3 на выходе модуля 3322 ( 3 )23 ( 3 ), ( 2 )( 2 ,3 ,4 ,5 )0 на выходе модуля 3433 (3 )33 (3 ), ( 3 )(3 , 4 , 5 , 6 )0 3 на выходе модуля 3544 (3 )43 (3 ), ( 4 )( 4 , 5 , 6 , 7 )0 3 на выходе модуля 3655 ( 3 )53 ( 3 ), ( 5 )( 5 ,6 ,7 , 8 )0 3 на выходе модуля 3766 ( 3 )63 ( 3 ), ( 6 )( 6 ,7 , 8 ,9 )0 на выходе модуля 2800 ( 2 ,3 )( 3 )4 ( 2 ) ,0 на выходе модуля 2911 ( 2 ,3 )1 ( 3 )4 ( 2 ) , 0 на выходе модуля 3022 ( 2 , 3 )2 (3 )4 ( 2 ) , 0 на выходе модуля 27 (выходе 57 устройства) 9( 0 , 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ) . Достоинствами устройства являются простая конструкция и возможность вычисления симметрических булевых функций произвольного числапеременных. При этом для построения устройства могут быть использованы многофункциональные логические модули с ограниченным (независимо от величины ) числом информационных входов. 7 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 8