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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ШЕФФЕРОВСКИХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ШЕСТИ ПЕРЕМЕННЫХ Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления шефферовских симметрических булевых функций шести переменных. Устройство для вычисления шефферовских симметрических булевых функций шести переменных содержит элемент РАВНОЗНАЧНОСТЬ, два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть информационных и восемь настроечных входов,один выход. Сложность устройства по числу входов логических элементов равна 30, а его быстродействие, определяемое глубиной схемы, составляет 2, где- задержка на один логический элемент. Устройство имеет 15 внешних выводов (четырнадцать входов и выход). Устройство для вычисления шефферовских симметрических булевых функций шести переменных работает следующим образом. На информационные входы устройства поступают значения переменных х 1,х 2 х 6, на настроечные входы устройства поступают переменные u1,u2u8,значения которых принадлежат множеству 0,1,х 1,х 2. На выходе устройства вычисляется(реализуется) шефферовская симметрическая булева функция F = F(x1,x2x6), определяемая вектором настройки u(f)=(u1,u2u8). Супрун Валерий Павлович, Коробко Филипп Сергеевич (BY)(71)(73) Заявитель и патентовладелец: БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (БГУ) (BY) Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления шефферовских симметрических булевых функций шести переменных. Известно устройство для вычисления симметрических булевых функций n переменных, которое содержит n2+n+1 элементов И-НЕ, n элементов НЕ, n информационных и n+1 настроечных входов, выход[1]. Конструктивная сложность устройства (по числу входов логических элементов) равна 3n2+2n+2, а его быстродействие, определяемое глубиной схемы, составляет (n+2), где-задержка на один логический элемент. Известное устройство при n=6 содержит 43 элемента И-НЕ и 6 элементов НЕ. Основными недостатками известного устройства при n=6 являются: 1) высокая конструктивная сложность, равная 122; 2) низкое быстродействие, которое составляет 8. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления полиномиальных симметрических булевых функций шести переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть,элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть информационных и четыре настроечных входов, выход[2]. Конструктивная сложность устройства (по числу входов логических элементов) равна 27, а быстродействие, определяемое глубиной логической схемы, составляет 2, где- задержка на один логический элемент. Устройство-прототип, как и заявляемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и ЭЛЕМЕНТ СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, i-й вход которого,где i = 1, 2, , 6, соединен с i-м информационным входом устройства, седьмой и восьмой входы - с первым настроечным входом устройства. Недостатком устройства-прототипа являются низкие функциональные возможности, поскольку устройство не позволяет вычислять (реализовать) шефферовские симметрические булевых функции шести переменных. Предполагаемое изобретение направлено на решение следующей технической задачи: расширение функциональных возможностей устройства за счет реализации шефферовских симметрических булевых функций шести переменных. Устройство для вычисления шефферовских симметрических булевых функций шести переменных содержит первый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход - с выходом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Причем i-й вход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, где i = 1, 2, , 6, соединен с i-м информационным входом устройства, седьмой и восьмой входы - с первым настроечным входом устройства. В отличие от прототипа устройство содержит второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент РАВНОЗНАЧНОСТЬ, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Третий вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, j-й вход которого, где j = 1, 2, 3, 4, соединен с j-м входом элемента равнозначность и с j-м информационным входом устройства. Второй настроечный вход устройства соединен с четвертым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с пятым входом элемента РАВНОЗНАЧНОСТЬ, (k+5)-й вход которого, где k = 1, 2,соединен с (k+4)-м информационным входом устройства, (k+2)-й настроечный вход которого соединен с(k+8)-м входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Далее (l+4)-й настроечный вход устройства, где l = 1, 2, 3, соединен с (l+4)-м входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, восьмой и девятый входы которого соединены с восьмым настроечным входом устройства. Названный технический результат достигается посредством удаления из схемы устройствапрототипа элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, введения в схему элемента РАВНОЗНАЧНОСТЬ и изменения порога элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, а также путем последующего изменения соединений между элементами логической схемы. На чертеже (фиг. 1) представлена логическая схема устройства для вычисления шефферовских симметрических булевых функций шести переменных. Устройство для вычисления шефферовских симметрических булевых функций шести переменных содержит элемент РАВНОЗНАЧНОСТЬ 1, два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2 и 3,элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4, шесть информационных входов 510, восемь настроечных входов 1118 и выход 19. Устройство для вычисления шефферовских симметрических булевых функций шести переменных работает следующим образом. На информационные входы 510 устройства поступают значения переменных х 1, х 2,, х 6, на на-1 024519 строечные входы 1118 - сигналы u1, u2, , u8, значения которых принадлежат множеству 0, 1, х 1, х 2. На выходе 19 устройства вычисляется шефферовская симметрическая булева функция F = F(x1,x2 х 6), определяемая вектором настройки u(F) = (u1,u2u8). Поясним принцип построения и работы устройства для вычисления шефферовских симметрических булевых функций шести переменных. Произвольная булева функция n переменных F = F(x1,x2xn) называется симметрической, если она не меняет своего значения после перестановки любой пары переменных xl и xj где ij и i,j = 1, 2, , n. Симметрическая булева функция F характеризуется множеством рабочих чисел A(F)=al,a2ar,где 0rn+1. Функция F = F(x) принимает значение логической единицы на тех и только тех наборах значений переменных X = х 1,х 2xn, которые содержат ровно ak (k = 1, 2 r) единиц, и такая функция обозначается F = Fna1,a2ar (х 1 х 2, ,xn). Симметрическая булева функция F = F(x,x2xn) взаимно однозначно представляется (n+1)разрядным двоичным вектором (локальным кодом) (F) = (0,1 п), где 1=1 тогда и только тогда, когда i-рабочее число функции F, т.е. iA(F). Симметрическая булева функция n переменных F называется шефферовской (или функцией шефферовского типа), если она не содержится ни в одном из пяти замкнутых классов T0, T1, TL, TS, TM, т.е. где Т 0-класс булевых функций, сохраняющих константу 0, Т 1-класс булевых функций, сохраняющих константу l, TL -класс линейных булевых функций, TS-класс самодвойственных булевых функций иTM - класс монотонных булевых функций (Яблонский С.В. Введение в дискретную математику. - М.: Наука, 1986). Число шефферовских симметрических булевых функций n переменных вычисляется по формуле Отсюда следует, что NS(6) = 32, т.е. существует тридцать две шефферовские симметрические булевы функции шести переменных F0, F1,F31. Функции F0, F1, F31 имеют следующие локальные коды: Первообразная функция устройства (фиг. 1) для вычисления шефферовских симметрических булевых функций шести переменных имеет вид Настройка устройства на вычисление (реализацию) булевых функций F0,F1, ,F31 осуществляется посредством таблицы (фиг. 2). Рассмотрим пример настройки. Допустим, что на выходе 19 устрой-ства требуется вычислить шефферовскую симметрическую булеву функцию где X = х 1,х 2, ,х 6. В таком случае, согласно таблице настроек (фиг. 2), необходимо положить u1 = 1, u2 = 0, u3 = 0, u4 = 1, u5 = 1, u6 = 0, u7 = х 1, u8 = х 2, и тогда первообразная функция устройства принимает вид Основным достоинством заявляемого устройства является широкие функциональные возможности,-2 024519 поскольку устройство (при соответствующей настройке) способно вычислить (реализовать) произвольную шефферовскую симметрическую булеву функцию шести переменных. Конструктивная сложность устройства по числу входов логических элементов равно 30, а его быстродействие, определяемое глубиной логической схемы, составляет 2, где -задержка на один логический элемент. Источники информации, принятые во внимание при экспертизе: 1. Авторское свидкткльство 1478208, СССР, МПК G 06 F 7/00, БИ 17, 1989, с. 195. 2. Патент РБ 11028, МПК G 06 F 7/00, БИ 4 (63), 2008, с. 143 (прототип). ФОРМУЛА ИЗОБРЕТЕНИЯ Устройство для вычисления шефферовских симметрических булевых функций шести переменных,содержащее первый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход - с выходом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, i-й вход которого, где i=1, 2, , 6, соединен с i-м информационным входом устройства, седьмой и восьмой входы - с первым настроечным входом устройства,отличающееся тем, что содержит второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент РАВНОЗНАЧНОСТЬ, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, j-й вход которого, где j=1, 2, 3, 4, соединен с j-м входом элемента РАВНОЗНАЧНОСТЬ и с j-м информационным входом устройства, второй настроечный вход которого соединен с четвертым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с пятым входом элемента РАВНОЗНАЧНОСТЬ, (k+5)-й вход которого, где k=1, 2, соединен с (k+4)-м информационным входом устройства, (k+2)-й настроечный вход которого соединен с (k+8)-м входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,(l+4)-й настроечный вход устройства, где l=1, 2, 3, соединен с (l+4)-м входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, восьмой и девятый входы которого соединены с восьмым настроечным входом устройства. Устройство для вычисления шефферовских симметрических булевых функций шести переменных