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

(51)5 6 0 ОСУДАРСТРЕННЫЙ КОМИТЕТПО ИЭОБГЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНГ СССР О ИЕ ИЗОБРЕТЕН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) МОДУЛЬ ДЛЯ ЛОГИЧЕСКИХ ПРЕОБРАЗОВАНИЙ БУЛЕВЫХ ФУНКЦИИ (57) Изобретение относится к цифровой вычислительной технике и может быть и 1- польэовано для аппаратной поддержки вычислений в системах анализа бинарных динамических систем и синтеза цифровых автоматов. Цель изобретения - расширение функциональных возможностей за счет обработки булевых функцийминимаксного типа. Устройство содержит регистр 1, два элемента И 2 и 3, два элемента(2) ИЛИ 4, 5, две схемы сравнения 6 и 7, суммирующий счетчик 8, вычитающий счетчик 9, узел пересчета 10, три коммутатора 11 - 13, сдвиговый регистр 14 и элемент задержки 1 б, В регистр 1 заносится значение параметра тУт а 2;т = 1,2 - 1 и его знак, В заеиси. Изобретение относится к области цифровой вычислительной техники и может бытьиспользовано для аппаратной поддержки вычислений в системах анализа, синтеза и обработки изображений, сжатия данных, анализа 5бинарных динамических систем и синтезацифровых автоматов,Целью изобретения является расшире-.ние функциональных возможностей за счетобработки булевых функций минимаксного 10типа.Суть изобретения заключается в логической обработке реализации дифференциальных операторов минимума и максимумабулевых функций на основе использования 15принципов поточной обработки данных,В основу изобретения положены следующие математические модели функционирования компонентов и устройства в целом.Пусть система из 2" булевых функции 2011 )Х = 0,2 -1) переменных представленаматрицей В 2" азмерности 2 х 2 их векторов значений М;: 2 - 1) 2 - 12 2 -30хг" - 1 х 1 хо Матрицу В 2" зададим в системе координат Х и У, где Х - ко)зрдината изменения индексазначений Х) функций на наборе 35 (Хо, Х 1, , Хп)(1.=.0,2 п -1), а У - координата изменения индекса ) векторов значений Зц. Тогда логические дифференциальные операторы системы В 2 п булевых функций в матричном виде определяются следующим образом: 40 оператор вычисления минимума по координате Х(Г 1)МФМ т) Р 2 П =В 2 ПЛ 2 П )з, (1) Фх) 45 оператор вычисления минимума по координате УМ)И УВ 2 - ГВ 2 АР 2 -2 )(ргх)50 мости от знака параметра и режима вычисления (минимума или максимума) узел пересчета 10 генерирует последовательность управляющих сигналов, обеспечивающих обработку булевых функций минимаксного типа, 3 ил., 2 табл. оператор вычисления максимума по координате Х МАХ уВ 2" =Вг"Ч.гп , (3) (АХ)оператор вычисления максимума по координате УМАХ (В 2" =(Вг"Мг" 11, (4) (1;гх)Югде .2 - матрица размерности 2 х 2, которая при т, 0(г О) имеет верхнюю(нижнюрэ) диагональ, параллельную главной и отстоящую от нее на расстоянии т элементов и формир емую согласно формуле1 т ) )Й (.1))к - кратное повторение вычислительной процедуры А означаетг 1 ц ) - 1) л )А р - 1при этом операции конъюнкции и дизъюнкции выполняются поэлементно. Соотношения (1 - 4) являются математическими моделями функционирования изобретения.Из формулы (1-4) следует, что при реализации операторов (1) и(3) вычисления по координате Х сводятся к обработке столбцов матрицы В 2 п, а при реализации операторов (2) и (4) по координате У - срок матрицы ВгпПоясним особенности организации вычислительного процесса на основе математических моделей (1-4) на конкретном примере,Пусть требуется вычислить двухкратный логический минимум (К = 2) по координате Х с параметром т = + 1 системы из восьми булевых функций 1) (Х)= 0,7), трех переменных(п =3): о(Х) = Х 2 уг Х 2 ХЗ11(Х) = Х 2 УХ 1 Х 2 ХЗтг(Х) = Х 1 Х 2)б(Х) =" Х 1 Х 2 1 Х 1 Х 2 ХЗЦХ) =- ХгИсходная матрица имеет вид:В соответствии с ( данной процедуры впишем операт)р 23) 2) раессе вычисления двтерации получим: Выделим в пр ции. В перво твляет п в соответ 15 та ма(Ъ 2 з=(х) ации пол 30 После выполнения второи итеручим искомый результат:(х) (х) (х)На фиг, 1 приведена структурная схема 3модуля для логических преобразований булевых функций; на фиг, 2 - структурная схема устройства, построенного из модулей; нафиг. 3 - операционный граф работы устройства для данного примера,Модуль (фиг. 1) содержит регистр 1, дваэлемента И 2 и 3, два элемента ИЛИ 4 и 5,две схемы 6 и 7 сравнения, суммирующийсчетчик 8, вычитающий счетчик 9, узел 10пересчета, три коммутатора 11-13, сдвиговый регистр 14, элемент 15 задержки, группу входов 16 задания параметра, дватактовых входа 17 и 18, вход 19 заданиязнака, информационный вход 20, вход 21задания режима, выход 22. Узел 10 пересчета может быть реализован с помощью многоразрядного универсального счетчика, который в зависимости от количества поступивших импульсов и значения управляющего сигнала (с входа 19 задания знака) формирует на своем двух- разрядном выходе последовательность сигналов, приведенную в табл. 1,Элемент ИЛИ 5 обеспечивает логический анализ операндов, поступающих на его первый и второй входы путем выполнения над ними операции диэъюнкции,Элемент И 3 обеспечивает логический анализ операндов, поступающих на входы первого по и - й, путем выполнения над ними операции коньюнкции.Коммутатор 12 обеспечивает передачу информации с выхода элемента И 3 (режим вычисления минимума) либо с выхода элемента ИЛИ 5 (режим вычисления максимума) под управлением сигнала с входа 21 задания режима.Коммутатор 11 осущес ередачу информации на выход 22 ствии с бл. 2.Модуль 23 функционирует следующим образом. Предварительно в регистр 1 с группы входов 16 задания параметра заносится абсолютное значение параметра т(где т 6 Л; Л, - целые числа, кроме нуля из интервала (2"-1) - (2" -1), а в(п+ 1) - й разряд регистра 1 с входа 19 задания знака - "0", если т 1 О, и единица, если т О. Суммирующий счетчик 8 устанавливается в исходное состояние (1 1), а вычитающий счетчик 9 устанавливается в начальное (нулевое) состояние (О, 0).Рассмотрим функционирование модуля при т .О. На втором входе узла 10 пересчета сигнал нулевого уровня (так как т ) 0).Узел 10 пересчета генерирует последовательность сигналов на своем выходе в соответствии с табл, 1 (2 и 3 столбца).В первом такте суммирующий счетчик 8 переходит из состояния 1 1 в состояние О, О, В результате по перепаду сигнала из "1:" в "0" на первом входе узла 10 пересчета на его выходе формируется код 00, который сохраняется в течение (т) тактов.В т-м такте на выходе первой схемы 6 сравнения в результате совпадения кодов на ее входах формируется сигнал единичного уровня, поступающий на первый вход элемента ИЛИ 4 и далее с его выхода нэ первый вход узла 10 пересчета. В результате по заднему фронту этого сигнала на выходе узла 10 пересчета формируется код 01, который сохраняется до окончания (2" - г) - го такта, 166705045 50 55 В (2 п -т )-м такте на выходе второйсхемы 7 сравнения в результате совпадениякодов на ее входах формируется сИгнал единичного уровня, поступающий нэ первыйвход элемента ИЛИ 4 и далее с его выходана первый вход узла 10 пересчета, В результате по заднему фронту этого сигнала навыходе узла 10 пересчета формируется код10, который сохраняется с (2" - т + 1)-готакта до окончания 2"-го такта,В каждом такте по сигналу с первоготактового на второй вход с входа 17 осуществляется сдвиг информации на один разряд вправо (в сторону старших разрядов)в сдвиговом регистре 14, через времяо - тос = (полтакта) в младший разряд сдви 2гового регистра 14 записывается элемент,поступающий с информационного входа 20.Одновременно по коду (значению т) на управляющих входах коммутатора 13 значение элемента из т - го разряда сдвиговогорегистра 14 подается на элемент И 3 и элемент ИЛИ 5, на вторые входы которых поступает текущий элемент обрабатываемоговектора. Результат логических преобразований в зависимости от режима поступаетчерез коммутатор 12 и 11 на выход 22.Функционирование устройства, включающего в себя однотипные модули для логических преобразований булевых функций(фиг. 2), рассмотрим на следующем примере.Пусть устройство реализует композицию операторов видаММ ( МАХ ( МАХ Кгз ) )(-Ф) (-2 (Ъ)в соответствии с операционным графом,приведенным на фиг. 3 (и .= 3). Устройствосодержит три модуля для логических преобразований булевых функций, На группы входов 16.1, 16,2, и 16.3 параметра г подаютсясоответственно значения 3, 2 и 4, а на входы19.1, 19,2 и 19.3 задания знака соответственно значения 0 (знак плюс) 1 и 1 (знакиминус), на входах 21.1 и 21.2 задания режима сигналы единичного уровня (режим вычисления максимума), а на входе 21,3задания режима сигнал нулевого уровня (режим вычисления минимума). Запись значений параметров т 1,тг,и тз и их знаков в (п+ 1) - разрядный регистр 1 стробируется сигналами с второго тактового входа 18,Функционирование устройства начинается при поступлении сигналов с первоготактового входа 17.8 первом такте на информационный вход20.1 первого модуля поступает значение перво 2" -гоэлемента Х вектора Хь(Х Х.Х( 1 5 10 15 20 25 30 35 40 системы Вг" = 0,2" - 1), сопровождаемоетактовым импульсом с первого тактовоговхода 17, Этот элемент записывается в первый разряд сдвигового регистра 14 первогомодуля, Аналогичным образом в тактах свторого по ю 1 = 3 в сдвиговый регистр 14первого модуля последовательно з(апиываются значения элементов Х .Х вектора Х,На четвертом (т 1 + 1) - м такте на выходе(0) 13)22.1 формируется значение элемента У 1((Зс)На тактах с пятого по (2" + 3)- й на выходе22.1 формируются соответственно значенияэлементов У 1( У( "вектора результата У 1.Кроме того, в четвертом такте (с началафункционирования устройства) значениепервого элемента У 1 результата У поступает на информационный вход 20,2 второгомодуля. В тактах с четвертого по (2" + 3) - йна выходе 22,2 фамирются значения элементов Уг , , Уг вектора результата( - )на выходе 22,3 третьего мууля фо(грмиуются значения элементов Уз, , Уз " вектора результата Уз = М 11 ч Уг(-) (Р)Одновременно по окончании 2" - го такта навыход первой вычислительной ячейки 21 поступает первый элемент вектора Хг системы Йг", а результат вычисленияУ = Ма (МАХ(МАХВгз( - Ф) ( - Ъ) (3системы Йг" формируется эа (2 г" +3 )такта,Формула изобретения Модуль для логических преобразований булевых функций, содержащий два коммутатора, сдвиговый регистр и регистр, причем первый информационный вход первого коммутатора соединен с информационным входом модуля, вход задания режима которого соединен с управляющим входом второго коммутатора, о т л и ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет обработки булевых функций минимаксного типа, он содержит две схемы сравнения, два элемента И, два элемента ИЛИ, суммирующий счетчик, вычитающий счетчик, узел пересчета, третий коммутатор и элемент задержки, причем10 1667050 Таблица 1 входы задания параметра группы соединены с К-ми (К = 1,п; и - количество разрядов задания параметра) информационными входами регистра и управляющими входами третьего коммутатора, информационные входы которого соединены с выходами сдвигового регистра, информационный вход которого соединен с информационным входом модуля, первыми входами первого элемента И.и первого элемента ИЛИ, вторые входы которых соединены с вторым информационным входом первого коммутатора и с выходом третьего коммутатора, первый тактовый вход модуля соединен с входом элемента задержки, входом управления сдвигом сдвигового регистра и со счетными входами суммирующего и вычитающего счетчиков, выходы последнего из которых соединены с входами первой группы первой схемы сравнения; входы второй группы которой соединены с входами первой группы второй схемы и с К-ми выходами регистра, (н +1)-й разряд выхода которого соединен с первым входом узла пересчета, второй вход которого соединен с выходом второго элемента ИЛИ, первый вход которого соединен с выходом второго элемента И, входы которого соеди нены с выходами суммирующего счетчика ивходами второй группы второй схемы сравнения, выход которой соединен с вторым входом второго элемента ИЛИ, третий вход которого соединен с выходом первой схемы 10 сравнения, выходы узла пересчета соединены с управляющими входами первого коммутатора, третий информационный вход которого соединен с выходом второго коммутатора, первый и второй информацион ные входы которого соединены с выходамисоответственно первого элемента И и первого элемента ИЛИ, выход элемента задерж ки соединен с входом управления записьюсдвигового регистра, второй тактовый вход 20 модуля соединен с тактовым входом регистра,п + 1)-й информационный вход которого соединен с входом задания знака, выход первого коммутатора является выходом модуля,(юl (о) д/ У Составитель В. Сорокинэктор О, Спесивых Техред М.Моргентал Корректор О. Кравцов при ГКНТ СССР оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101Заказ 2524 Тираж 398 Подписное ВНИИПИ Государственного комитета по изобретениям и открыт 113035. Москва, Ж, Раушская наб., 4/5