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

о во ССС 1979.СССР 1979 фровой ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯ РАСПОЗНАНА ЛИНЕЙНОСТЬ БУЛЕВЫХ ФУНКЦИ(57) Изобретение относится к вычислительной технике и может бытьиспользовано для аппаратной поддержкивычислений в комплексах автоматизированного проектирования дискретныхустройств, обработки изображений,сжатия данных, в системах синтезатопологии БИС и СБИС. Целью изобретения является расвирение функциональных воэможностей за счет распознавания на линейность булевых функций,заданных в обобщенной арифметическойполиномиальной форме. Указанная цельдостигается тем, что устройство содержит коммутатор 1, блок 2 регистров, вычислительный блок 3 и блокуправления. 6 ил., 1 табл.;:огде р;=2 (12 х,хг,ц гб ггр,х х еехп.г х 11 )г 45 ХиХг,1 г1 гг 1 и Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержке вычислений в комплексах автоматизирован наго проектирования дискретных устройств, обработки изображений, сжатия данных, в системах синтеза топологии БИС и СБИС.Целью изобретения является расши рейие Функциональных врзможностей:. за счет распознавания на линейность булевых Функций, заданных в обобщенной арифметической полиномиальной форме. 15На Фиг. 1 представлена схема устройства; на Фиг, 2 - схема коммутатора; на Фиг. 3 - Функциональная схема, узла мультиплексоров; на Фиг. схема блока регистров; на Фиг. 5 - 2 О с)ема вычислительного блока; на фиг. 6 - схема блока управления.Устройство содержит коммутатор 1, блок 2 регистров, вычислительный блок 3 и блок 4 управления. Коммута тор 1 содержит 2" -,1 узлов 5 мультиплексоров, где п - цисло переменных булевых Функций. Блок 2 регистров содержит 2" регистров 6, Вычислительный блок 3 содержит 2 " вычитателей ЗО 7, 2 "- 1 элементов 8 сравнения и элемент И 9. Блок 4 управления содержит генератор 10 тактовых импульсбв элемент И 11, элемент И-НЕ 12, счетчик 13 дешифратор 14 и триггер 1 г.Арифметическая полиномиальная формюг булевой функции Г(х) имеет следующий вид: Р(х) = р + р.х+ рх,0,2 - 1),множество целых чиселтаких, цто значениеР(Х) б г 01 юэ любоюнаборе переменных, - и-разрядный двоичныйкод представления пара-метра 1.Арифметическая полиномиальная Форма Р(Х) булевой Функции й(х) определяется вектором коэффициентов Р =-г тч- Ре Ррлг.гкоторыиявляется результатом выполненияконъюнктивного преобразования надвектором значений Х =х(о 1 х(1(,ь 1х(булевой Функции Г(х),где К - матрица конъюнктивного преобразования размерностиг Рг2 х 2 . Формируемая поправилу где- символ кронекеровского произведения.Обобщенная арифметическая полиномиальная форма задает уже систему (кортеж) булевых Функций, упорядоченную пространственно, Эта система записывается в виде Г, (х)ъГ (х)+Г(х),Если д-ю Функцию кортежа (З == О,щ) представить в виде арифметической полиномиальной Формы Р (х),затем умножить на весовой множитель2 и полученные с весами полиномысложить, то результатом являетсяобобщенная арифметическая полиномиальная Форма 0(х), где Обобщенная арифметическая полиномиальная Форма системы булевых Функций 0(х) однозначно представляется вектором коэффициентов 1) = Й б 4 Рптю Й г 1Линейная обобщенная арифметическая полиномиальная Форма системы булевых Функций Г(х) (1 = О в) имеет следующий вид: Т.О(х) = 1+ 1 х+ 1 х, +1 ю169 6нейной обобщенной арифметической полиномиальной Формы содержит 2 элементов. Это свойство определяет целесообразность использования линейной обобщенной арифметической полиномиальной Формы, позволяющей сократить объем вычислений при обработке и объем памяти при хранении векторов коэффициентов. Таким образом, возникает необходимость распознава- ния на линейность обобщенных арифметицеских полиномиальных форм, заданных своими векторами значений Х .Для обобщенной арифметической полиномиальной Формы системы булевых Функций между вектором значений Хи вектором коэффициентов Э существует взаимно однозначное соответствие, ,определяемое выражением 5 1552Из (5) видно, цто обобщенная арифметическая полиномиальная Форма является линейной, если в ее состав входят только слагаемые, определяемые лишь одной булевой переменной х; (1 = 1,п).Таким образом, если коэффициенты обобщенной арифметической полиномиальной формы Л(х) удовлетворяют ус ловию Юд =О для 1 2, я= Орпр(7) 2" и Из (7) следует, цто в общем случае условие линейности обобщенной арифметической полиномиальной Формы имеет вид- х(35ратора 10 тактовых импульсов, атакже йа первый вход счетчика 13, вкоторый записывается число 2" - и,код этого числа с выходов счетчика40 13 поступает на входы дешифратора14,на выходах которого формируютсянизкие логические уровни напряженияв соответствии с таблицей.В момент времени е на выходе ге 45 нератора 10 Формируется тактовый импульс, поступающий через элементИ 11 на второй вход счетчика 1 ,Счетчик 13 переходит е состояние 2 - и 1+ 1, код с выходов счетчика 13 посту 5 п пает на входы дешифратора 14, на выходах которого Формируются сигналыв соответствии с таблицей,нты времени 4ока 4 управленияо работе в момено счетчик 13 пер2 "и+ 2 и.2венно. И Й 5 происходит времени ходит в и + 3то данная обобщенная арифметическаяполиномиальная форма системы булевыхФункций является линейной,Линейная обобщенная арифметическая полиномиальная Форма системы булевых Функций однозначно определяет-.ся вектором коэффициентов 1,0 = 10,1 а,, 11 . Характерным свойствомявляется то, цто этот вектор коэффициентов содержит всего и + 1 элемент,тогда как вектор коэффициентов нелиВычислительный .блок 3 работает следующим образом. Элементы вектора аначений Хрх" х ,хт поступают на входы вычитателей 7. в которых формируются значения, разнос-) тей поступивших элементов хХха 1. С выходов выцитателей 7 значения разностей х1 - х передаются на входы элементов 8 й й и 8 х сравнения, с выхода которых сигнал равенства операндов на входах (высокий логический уровень) посту- пает на вход элемента И 9, на выходе которого формируется высокий логицеский уровень в случае высоких логических уровней на всех его входах.Дешифратор 14 предназначен для Формирования сигналов на своих выходах в соответствии с таблицей.Блок 4 управления работает следую" щим образом. В момент времени С высокий логицеский уровень напряжения поступает на вход запуска гене(,2 а 2 е)1552В момент времени (: счетцик 13 припоступлении на его второй вход тактового импульса переходит из состояния2 - 1 в состояние 0, и с его выходасигнал переполнения поступает на 5входы элемента И-НЕ 12 и триггера 15,который переходит из нулевого в единичное состояние. С выхода элементаИ-НЕ 12 сигнал Фронта напряжения снизкого логического уровня на высокийпоступает на вход останова генератоа 10 тактовых импульсов.Рассмотрим работу устройства дляслучая и = 4 . Элементы вектора знацений Х, = х 1 х 1х("1 поступают на инФормадионные входы первойгруппы устройства. После поступления)-)а вход режима блока 4 управлениявысокого логического уровня (моментвремени) в счетчик 13 записывает 1Мся число, равное 2 - и = 8ему соотствуествует код 100, следовательно, на первом выходе блокауправления Формируются нулевые сигналы, которые передаются на управляющий вход коммутатора 1,Выработаннцй генератором 10 тактовый импульс (момент времени т)поступает на вход записи регистровЗО6 и синхронизирует запись в регистры6 элементов вектора значений Х,поступающих с выхода коммутатора 1.Под действием этого тактового импульса счетчик 13 переходит из состояния100 в состояние 101. Если выполняется х(01 - х 1 . - Х(2) х(ъ) х(4)то на выходе вычислительного блока3 остается высокий логический уровень,В момент временитактовый импульс с второго выхода блока 4 управления передается на вход записи регистров 6 и синхронизирует запись вних элементов вектора значений Хдх х(+1 х (61 х(ь) х по) х (я) х (чЭ ) Ф Ф иЭти значения записываются в регистрц6 р (р = 2,8), в остальные регистрыблока 2 регистров записывается та жеинФормация, которая была в них записа на в момент времени 1 . На выходевычислительного блока 3 остаетсявысокий логический уровень напряженияв случае выполнения х(1 - х ф)= х(ф) - х(1 = х д) - х "о) = х ") -х (1. Под действием этого же тактового импульса счетчик 13 переходитиз состояния 101 в состояние 110. 169 8В момент времени. тактовый импульс с второго выхода блока 4 управления поступает на вход записи блока 2 регистров и синхронизирует записьв его регистры 6 - 6 д значений элементов х, х, х Ж вектора хСодержимое остальных регистров блока2 регистров остается без изменения.Если вцполняется х(1 - х(41 = хй)-.х , то на выходе вычислительногоблока 3 сохраняется высокий логический уровень напряжения Счетчик 13переходит из состояния 110 в состояние 111В момент времени 6 тактовый импульс поступает на счетный входсчетчика 13, который при этом переходит из состояния 111 в состояние000 и Формирует сигнал переполнения.Сигнал переполнения поступает навход триггера 15 и переводит его вединичное состояние, а также поступает на входэлемента И-НЕ 12 и далеена вход останова генератора 10 тактовых импульсов.Таким образом, наличие единичногосостояния триггера 15 при остановленном генераторе 10 тактовых импульсов свидетельствует о линейности распознаваемой обобщенной ариФметической полиномиальной Формы,Если обобщенная ариФметическаяполиномиальная Форма не являетсялинейной, то на этапе распознавания(например, в момент времени ) невыполняется одно из равенств (7).При этом на выходе выцислительногоблока 3 Формируется низкий логический уровень напряжения, этот сигналпоступает на вход режима блока 4управления и далее на вход элементаИ-НЕ 12, с выхода которого высокийлогический уровень напряжения передается на вход останова генератора10, Таким образом, наличие нулево"го состояния триггера 15 при остановленном генераторе 10 тактовцх импульсов свидетельствует о непринад"лежности распознаваемой обобщеннойариФметической полиномиальной Формык классу линейных,Ф о р м у л а изобретенияУстройство для распознавания налинейность булевцх Функций, содержа щее коммутатор, вычислительный блок и блок управления, о т л и ч а ющ е е с я тем, что, с целью расшиМ Э Ес 1Выходы Код на Входывходе1 2 . . . и 2 п 1 1 2 3 4 5 б 7 3 . . . 2 -1 2 .2 -1 0 00 0 Х Х Х Х Х Х Х Х Х Х Х 000 1 ХХХХХХХХХХ.Х 2 -и2 -и+2 -и+2 0 1 1 0 0 О 0 01 1 11 1 1 1 1 0 1 0 0 0011 1 11 0 1 0 2 -3 2 -2 2 -1 0 0 0 О О О О 1 1 1 11 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 00 0 00 0.00 1 1 1 1 1 1 9 1 рения Функциональных возможностей за счет распознавания на линейность булевых Функций, заданных в обобщенной ариФметической полиномиальнойиФорме, оно содержит 2 регистров (где и - число переменных булевых Функций), причем входы вектора значений обобщенного ариФметического полинома устройства подключены соот" ветственно к инФормационным входам первой группы коммутатора, выходы с первого по 2 -й которого подклочены соответственно к инФормационным вхо"и дам регистров с первого по 2 -и, выходк регистров с первого по (2 -1)"й подклочены соответственно к инФормационным входам второй группы Я 2169 10коммутатора и соответственно к ин"Формационным входам первой группывычислительного блока, выходы регист"Ииров с 2 -го по 2 -й подключенысоответственно к инФормационным входам второй группы вычислительногоблока, выход которого подключен квходу режима блока управления, первый, второй и третий выходы которогоподключены соответственно к управляющему входу коммутатора, к входам записи всех регистров и к выходу приз"нака линейности распознаваемой обоб"1 В щенной ариФметической полиномиальнойФормы устройства, вход запуска которого подключен к входу запуска блокауправления,1552169 Составитель В. См Техред П,олийны н ректор Э.Лончако тор В.Петра е писн Производственно-издательский комбинат Патент", г.ужгород, ул.Гагарина, 191 Заказ 330ВНИИПИ Государств1 ного комитета по изобретения035, Москва, Ж, Раушская открытиям йри ГКНТ СССд /5