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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 2 46 АНИЕ ИЗОБРЕТЕНИЯГ л нСР 4,фрожетй под) д Н Н = р ю"а С 11 1 2,и; ГОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СМ 1124281, кл, С 06 Р 5/00, 19Авторское свидетельство СССК 1001107, кл. С 06 Р 15/332,(54) УСТРОЙСТВО ДЛЯ ПРЕОБРЛЗОВАБУЛЕВЬХ ФУНКЦИЙ(57) Изобретение относится к цивой вычислительной технике и мобыть использовано для аппаратно,Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки вычислений в комплексах автоматизированного проектирования дискретных устройств, обработки изображений, сжатия данных, в системах синтеза топологии БИС и СБИС, фильтров на поверхностных акустических волнах.Цель изобретения - расширение класса решаемых задач за счет реализации преобразования булевых Функций в арифметическую полиноминальную Форму Хаара.В основу изобретения положены следующие математические модели компонентов устройств и их взаимодействияв процессе Функционирования.Спектр Хаара Н =Ь(О)булевой Функции п переменных Е(х х) ".Е(х) определяется в виде 51)4 С 06 Г 15/332, 7/О держки вычислений в комплексах автоматизированного проектирования дискретных устройств, обработки изображений, сжатия данных, в системах синтеза топологии БИС и СБИС, Фильтровна поверхностных акустических волнах.Цель изобретения - расширение классарешаемых задач эа счет реализациипреобразования булевых Функций варифметическую полиномиальную ФормуХаара. Поставленная цель достигаетсяэа счет того, что в состав устройствавведены коммутатор, блок нормировки,блок синхронизации и иблоков коньюнктивного преобразования (и - числопеременных Функций). 2 з.п. Ф-лы,11 ил., 5 табл. 2 к н х1(1 хф х )1- вектор размерности 2 , элементами которого являются значения булевой Функции Е(х) наупорядоценных в лексикографицеском порядке наборах переменных (значения таблицы истинности) 1 матрица преобразования Хаа ра, формируемая по рекуррентному соотнощению1532946 20 э еРееееааааа аеа,тркт;Ннфорфмац.вход 1 Блок Зв коньонктианого нреобразоааннва ееа еее е еКонму- Регистр 9 твтор 8эааааааааааа 7 еЕеэеэ ееКомму-Информационныд аход етатор 8е э аее ееай ае э э а ММааХ н -Хр-й+Ха йьа Хьь Х-Х,Х.-Х-Х+Х,+Х Х -Ха Х-йа -х +х,ХХа аи Ха Хе сф-Х,ь+Х,Ха Хн Х+Х, Х-ХьХнййм 7 йь Х Х аа йй йа йЕХВГ "Х-Х-ййе-Х ф+й,а+Х Хв 22 23 9 2 ф Регистр Э 1 Комну- Регистр 9 1 татор 8153294 б ЬюР гюрзою ра лактюх имаужа Н Ьаа 7 Я Баса ррвЬении 4 6 к 63 Г Йучвитксвра Г 2р д ригггр Я игггр 85ачбаЙка1532916 Юаф , ам фф ФфСФ.Пчо ррек ЕэевивЕЕЗаказ 8ВНИКНИВе аеею аО 1/54 Тираж 668 венного комитета по иэоб 113035, Москва, Ж, Ра исное и открытиям при ГКНТ СССРаб., д. 4/5 етен осуда а тент", г, Ужгород, ул. Гагарина льский комбина оиэводственно-иэ 11 ЯкСЗ11 Ф Ф с ф + 3 ь е Ъ 7,Сф з, + юее Ю е(о 1 Х, (л) ГХ 1л:Йхх 11 "х ,где 1 - г-й разряд двоичного представления параметра(нумерация разрядов начиная состарших, т.е. слева направо) 12=1,п- параметр, соответствующийномеру группы строк матрицыХаара (Фиг.120 Х б(0,1) - 1-я булева переменная булевой Функции й(х).Особенностью выражения (3) явля"ется то, что Н(х) ь (0,1) на любых наборах логических переменных (х 1 х, , х). Причем на одинаковых ,наборах значения Н(х) и Х совпадают. Это означает, цто выражение (3) , является арифметико-логическим пред, ставлением булевой функции 1(х), по- ,30скольку в нем содержатся арифметичес-кие и логические операции. Другой , важной особенностью .выражения (3) является его взаимоодноэначная связь с булевой Функцией й(х). Другими сло- З 5 вами, любую булеву функцию й(х) можно единственным образом представить в виде (3), а по выражению (3) можно однозначно восстановить булеву функ цию 1(х). 40Рассмотрим пример. Пусть булева Функция Е(хх).задана своим вектором значений Х, т.е, таблицей истин-ности на наборах х хф 2:т 45Х = 0110.1 .Определим ее спектр Хаара Н 1 л 1 и+ ил 2 1 2 лЛ И Ь 1 х+ а., хлл лО- символ кронекеровского произведения:Т - символ транспонирования, и-(1 - единичная матрица порядка2 А" Запивем Форму Хаара Нт(х) булевойФункции согласно (3)55Н(х) ц 1 + 2(-1) (-х, + х,)1.1В табл. 2 представлены спектрыХаара Н некоторых булевых функций Используя свойства преобразования Хаара, можно показать, что спектр Хаара Н 1 булевой Функцией Г(х) записывается в аналитической форме следующим образом:= О,Г(х), заданных в табл. 1 своими векторами значений Х 1. Выражение (3) есть интерпретация спектра Хаара булевой функцией, причем такая интерпретация, что булева функция й(х) представлена в новой арифметико-логической форме. В схемо-техническом плане это реализуется посредством известных устройств, выполняющих дискретное преобразование Хаара или быстрое дискретное преобразование Хаара с последующей интерпретацией результата (спектра) согласно выражению (3),Новая арифметико"логицеская Форма булевых Функций (3) обладает рядом достоинств арифметического и логицес" кого свойств спектра Хаара,обеспечивающих выявление поведения функции на отдельных или группах наборов, одна" ко имеет и недостатки, Основной из них связан с неполиномиальным представлением, что существенно при анализе и синтезе, например, линейных форм булевых Функций.Полиномиальную Форму Хаара РН(х) булевой Функции Г(х) определим в виде:Рн (х) - - (1,ф) + У,р 1 +Уф ь-л(6) 35 40 Г(х) представляет собой взвешеннуюсумму спектральных коэффициентов Хаара Ь) и Ь 1 и арифметических полиномов А;(х, х;) (3. = 1,п).пределим Функцию нормировкиВ,(Ь":я(ь") - о, ь":0 (5)1, ь) 0, )= 2,2 -1,Эта запись означает, что каждомуспектральному коэффициенту Хаара Ь 2,представленному и)-разрядным числомсо знаком, ставится в соответствие 2двухразрядное число со знаком 3(Ь), 15Формируемое по правилу (5). Таким образом, спектральные коэффициенты Хаара Ь 2) номируются по признаку знака,т.е. приводятся к величине Бу(Ь ),принймающей только три значения-1, О, 1.Тогда с учетом нормировки в матричной записи связь коэффициентов полиномов А (х), , А )2-(х, ,хи- )со спектральными коэффициентами Хаара булевой Функции определяется через конъюнктивное преобразованиеА, =К, Я(Ь );6Поясним математическую модель (8)на конкретном примере.Пусть задана булевая функция Е(х)своим вектором ЗначенийХ 10011110 ЯВ результате преобразования Хааравектора Х получают вектор коэффициентов спектра Хаара Нн 21(9-)О(2 2-20211тНаходят полиномиальную Форму Хаа"ра (РН-Форму) этой булевой Функции.Записывают векторы В(ьнф 1) из(ь 1"д):з (ь") - 10 11;,В,(ь(") - Г 1-1 о Л,и выполняют конъюнктивное преобразоние каждого из них Следовательно, в полиномиальнуюФорму Хаара РН(х) булевой функцииК(х) входят полиномыА(х,) = х,А,(х,х) =4 - 2 х - х, + 3 ххи ее окончательный вид согласно (8): РНС(х) = - (5 у+ 2:ух, +1 г+ 22 у(1 - 2 х - х+ ЗххД.Для булевых Функций К(х), заданных своими векторами значенийХ, = (10000110111000113,Х 1, = 00001110111011011 т,х010001110111000 Ят .РН-форма имеет вид1 р 2,п. (7)С учетом принятых обозначений математическая модель предлагаемого устройства (4) принимает вид: 55 1е 1 )-РН(х) = -рь +2 у 1 КО. х2 (В (ЬЯ") )10 32946: 9 15ческий уровень), а на его вход, передается значение элемента Я (Ьи) свыхода регистра 9, Значение разностиэлементов Яу(Ь(Ь) - Я(Ь(4) с выходавычитателя 7 поступает на вход регистра 9.Кроме того, значение элемента8(Ь(4) передается на выход первоговычислительного узла и далее на входвычитателя 7 второго вычислительногоузла (фиг.4). С выхода вычитателя 7значение элемента 8(Ь") поступаетна вход регистра 9 (на другом входе .вычитателя 7 - значение нуля). Счетчик 10 переходит из состояния 10 всостояние 11.На восьмом такте значение элементаЯ(Ь(т) поступает на вход вычитате"ля 7, на другой вход последнего с выхода коммутатора 8 передается значение элемента Я(Ь(ф) (на втором (управляющем) вхоре коммутатора 8 - высокий логический уровень). С выхода вычитателя 7 значение разности Я(Ь)8(Ь ) поступает на вход регистра 9.(5При этом значение элемента Я(Ь )с выхода регистра 9 передается навход второго вычислительного узла идалее на вход вычитателя 7. На другойвход вычитателя 7 с выхода коммутатора 8 поступает значение элементаЯ(ЬИ) (на втором (управляющем) входе коммутатора 8 - высокий логическийуровень, а на первом - значение эле- .мента 8(Ь" с выхода регистра 9,С выхода еычитателя 7 значение разности 8(Ьф) - 8(Ь) поступает на.вход .регистра 9. При этом значениеэлемента Я(Ь(4), являющееся коэффициентом а полинома А(хх), свыхода регистра 9 передается на выход устройства. Счетчик 1 О переходитиз состояния 11 е состояние 00.В результате на девятом такте на.вход еычитателя 7 с выхода первоговычислительного узла поступает значение разности 8(Ь ь) - Яу(Ь) (надругом входе вычитателя 7 - значениенуля). С выхода вычитателя 7 значениеразности 8(Ьь) - 8(Ьф) передаетсяна вход регистра 9. При этом коэффициент еф 8 (Ь) - Я (Ь 4) с выхо 5 9да регистра 9 поступает на выход устройства. Счетчик 10 переходит из состояния 00 е состояние 01,На десятом такте на вход вычитателя 7 с выхода первого вычислительногоузла,поступает значение разности8(Ь ) - 8(Ь . На другой вход вы. 5 1 О 15 20 25 30 35 40 45 50 55 читателя 7 йоступает с выхода коммутатора 8 разность 8(Ьф) - 8 (Ьф)(на втором (управляющем) входе коммутатора 8 - высокий логический уровень). С выхода вычитателя 7 разность Я (Ь(47) Я (ЬО) 8(Ь(й) - 8 (Ьф)3 поступает на вход регист-. ра 9, с выхода которого коэффициент(Ь(ь) 8 (Ь) поступает на выход устройства. Счетчик 10 перехо" дит из состояния 01 в состояние 1 О.На одиннадцатом такте с выхода регистра 9 коэффициент а8(Ь(т) - Яд(Ьд) " (Яу(Ьф) - 8(Ьф) передается на выход устройства.Таким образом, на выход устройства в тактах с восьмого по одиннадцатый поступают значения коэффициентов а , вф, аф, аф (табл. 4).Блок синхронизации 4 (фиг,74 для и = 4) содержит генератор 11 тактовых импульсов, демультиплексор 12, регистр сдвига 13, первый 14, второй 15, третий 16 элементы ИЛН, счетчик 17, первый 18, второй 19, третий 20, четвертый 21 элементы И, первый 22 и второй 23 триггеры.Рассмотрим работу блока 4 синхронизации для а4. Первоначально регистр 13 сдвига, счетчик 17, первый 22 и второй 23 триггеры установлены в нулевое состояние.На первом такте импульс с выхода генератора 11 тактовых импульсов пос" тупает на первый (информационный) вход демультиплексора 12. С первого выхода демультиплексора 12 сигнал (высокий логический уровень) поступает на регистр 13 сдвига и записывается в его первом разряде (на втором (управляющем) входе демультиплексора 12 низкий логический уровень). Первый 20 и второй 21 триггеры находятся в нулевом состЬянии и на первом выходе блока синхронизации сформирован адресный код 00. На втором выходе блока 4 синхронизации находится низкий логический уровень, так как на первом входе четвертого элемента И 21 имеется низкий логический уровень.На втором такте импульс с выхода генератора 11 тактовых импульсов поступает на первый (индюомационный) вход демультиплексора 12. С первого выхода демультиплексора 12 (на его втором (управляющем) входе - низкий логический уровень) высокий логический уровень сигнала поступает на регистр 13 сдвига, в котором произво153294612ческий уровень). С выхода второго элемента ИЛИ 15 сигнал поступает на пер-вый вход первого триггера 22. Р ре 5зультате триггер переходит в единичное состояние. Таким образом, на первом выходе блока 4 синхронизации формируется адресный код 01, Кроме того,в регистре 13 сдвига производитсясдвиг информации, с второго выходарегистра 13 сдвига высокий логический уровень поступает на первый входцетвертого элемента И 21, На первыйвход последнего с выхода генератора11 тактовых импульсов передается сиг 15з- нал, который далее с выхода четвертого элемента И 21 поступает на второй21 выход блока. 4 синхронизации. Такимобразом, на первом выходе блока 4синхронизации Формируется последовательность тактовых импульсов; отстающая на два такта от последовательности на выходе генератора 11 тактовыхимпульсов (Фиг.9),На семнадцатом такте блок 4 сина хронизации переходит в исходное состояние. Этот период происходит поддействием сигнала переполнения счетчика 17. Сигнал переполнения с четвертого выхода счетчика 17 поступаетна вторые входы (входы установки внуль) первого 22 и второго 23 триггеем ров, а также регистра 13 сдвига.од Рассмотрим Функционирование устн- ройства в совокупности составляющих8 - Зб его компонентов на конкретном приа мере,н = о. о Го 1 о ч - о о г о о омТ о оГ оЯ -г 1 о 2 о о 1,дится сдвиг в сторону старших разрядов. С первого выхода регистра 13 сдвига высокий логический уровень сигнала передается на второй (управляющий) вход демультиплексора 12 и на второй вход первого элемента ИЛИ 14, С выхода последнего сигнал посту пает на счетный вход счетчика 17, в результате счетчик 17 переходит из состояния 0000 в состояние 0001. Та ким образом, триггеры 22 и 23 остаются в исходном состоянии и на первом выходе блока синхронизации 4 име ется адресный код 00, На втором выхо де блока управления присутствует ни кий логический уровень, так как на первом входе четвертого элемента И находится низкий логический уровеньНа третьем такте импульс с выхода генератора 11 тактовых импульсов по ступает на информационный вход демультиплексора 12. С второго выхода демультиплексора 12 (на его втором (управляющем) входе - высокий логический уровень) сигнал передается н первый вход первого элемента ИЛИ 14 с выхода которого сигнал поступает на счетный вход счетчика 17, послед ний переходит из состояния 0001 в состояние 0010. Сигнал с первого вы хода счетчика 17 передается на первый вход первого элемента 18, а зат поступает с его выхода на первый вх второго элемента И 19 (на втором (и версном) входе первого элемента И. 1 низкий логический уровень). С выход второго элемента И 19 сигнал передается на первый вход второго элемента ИЛИ 15 (на втором (инверсном) входе второго элемента И 19 - низкий логиПусть необходимо представить булеву функцию Гх) четырех переменных, заданную своим спектром Хаара Н 1в полиномиальной форме Хаара Р 11(х).На первом такте значение спектрального коэффициента Хаара 11 ф = 8поступает на первый (информационный)вход коммутатора 1 (на втором (управляющем) входе которого - адресныйкод 00). С первого выхода коммутатора 1 значение Мо = 8 поступает напервый выход устройства (Фиг,1),На втором такте значение спектрального коэффициента Ьф = 2 аналогично значению ЬЖ = 8 передается напервЫй выход устройства,На тактах с 3-го по 16-й включительно значения спектральных коэффициентов Хаара с ЬЖ по Ьф поступаютна первый (информационный) вход коммутатора 1 и в соответствии с адреснымкодом на втором (управляющем) входепоследнего передаются на входы блока2 нормировки, причем так, что на первый вход блока 2 нормировки поступаютзначения коэффициентов Ь = 2 иЬ ф = .2 т. На второй вход блока 2 нормировки передаются значения коэффициентов ЬН = 4, Ь"1 = -2, Ьь) = 0 иЬ) = 2 и на третий вход блока 2 нормировки поступают значения коэффициентов Ьф = О, Ьв) = О, Ьфо = 22,) коэффициентов аф)а" а ) аь) аэ ф ф ф э 1математической м ледовэтель т вид: А (В третье реобразова ю аэ, а тветст 6): ного ения ль 0 О 0 0 О 0 1 О О, 10: 0 0 1 О 0-1 1 0-1 1-1 1 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0След хз) име Аэ (х- 2 хахэ Табл тельный третьем образовразованияе первый Ь") = О, Ьцц = 21 Т, Ьэ = 2.2Ь("41 = 242 и Ь" = 0В блоке 2 нормировки Формируются значения х ( 1 = 2, 15) функции Б (ЬЮ) в соответствии с математической моделью (5):(1) ) 31, Ь)О,т.е. формируются следующие х=1, хэфф 1, Х 4 1, х 6 = О, х = 1, х = О, ху х, =1,хн =О,хд=1, Х 4 1,Хэ =О Следовательно, полином А 4(х) имеетвид: А (х) = 1Во втором блоке 3 конъюнктивногопреобразования Формируются значения1 о, полином Ад(ххх) =1+хблоке 3 конъюнктиия Формируются знаА = К,ь З(Ь 4 яэ овательно, полином Аь(ххет вид:+ хх - 2 х,ххэ.и 5 иллюстрируют вычислпроцесс в первом, втором иблоках 3 конъюнктивного прания. ормула изобретения 1, Устройство для пребулевых Функций, содержа С первого выхода блока 2 нормировки значения х и х передаются на вход первого блока 3 конъюнктивного преобразования 3, с второго выхода блока 2 нормировки значения х 4, х -, хь и х т поступают на вход второго блока 3 конъюнктивного преобразования и с третьего выхода блока 2 нормировки значения хЭ, х, х 4 Э, Х 4 х, , х, , х,4 и х,в поступают на третий блок 3 конъюнктивного преобразования (табл. 5).В первом блоке .конъюнктивного преобразования 3 Формируются значения коэФФициентов аф 1 и а) в соответствии с математической моделью (6)коэффициентов а), а , а и ап)в соответствии с математической моделью (6):25-,тхх р х и ххэ х 4 х 10 О блок конъюнктивного преобразования и блок синхронизации, о т л и ч а ющ е е с я тем, что, с целью расширения класса решаемых задач за счет реализации преобразования булевых Функций в арифметическую полиноминальную Форму Хаара,.б него введены п(и - число переменных Функции) блоков конъюнктивного преобразования, блок нормировки, коммутатор и первый выход блока синхронизации подключен к управляющему входу коммутатора, первый выхоД которого является перТаблица 2 ееееЙ(х) КоэФФициенты спектра Хаара Н-Форма записи Функциито 1 1,о) 1,се) 1,(ь)3 -1 1 -12 2 2 О 2 0 2 О 1 1 3х,чхе х, Лхе х хе х,Эхе х д хе хФ хе х,1 хе ым инФормационным выходом устройства, инФормационным входом которого является инФормационный вход коммутаТора, -й (д2,п) выход которого йодключен к (д)-му инФормационномуходу блока нормировки, (1-1)-й вы"од которого подключен к информационому входу (-1)-го блока конъюнктивого преобразования, выход которого 10вляется -м инФормационным выходомстройства, а второй выход блока синронизации подключен к тактовым вхо"ам блока нормировки (д)-го блока конъюнктивного преобразования . 152. Устройство по п.1, о т л и ч ащ е е с я тем, что блок нормировки содержит ирегистр и и"1 элемент ЙЛИ, выход 1-го (1 2,ш; ш - разряд ,ность) разряда (х)-го регистра под,ключен к (1-1)-му входу (ь)-го элемента ИЛИ, выход которого объединен с выходом первого разряда (1-1)- ;го регистра и образуют (-1)-й выход 25 блока нормировки, (-1)-м инФормационным входом которого является инФор-. мационный вход (-1)-го регистра, тактовый вход которого подключен к тактовому входу блока нормировки. 3, Устройство по п.1, о т л и ч а. ю щ е е с я тем, что (-1)-й блок конъюнктивного преобразования содержит счетчик и (-1) вычислительный модуль, причем выход 1-го (1 = 1,-1 разряда счетчика подключен к управляющему входу 1-го вычислительного узла, выход 1-го Ь = 1,1-2) вычислительного узла подключен к инФормационному входу Ь+1)-го вычислительного узла, выход (-1)-го вычислительного узла является выходом блока конъюнктивного преобразования, тактовым и инФормационным входами которого являются соответственно счетный вход счетчика и инФормационный вход первого вычислительного узла, причем 1"й вычислительный узел содержит вычитатель, регистр и коммутатор, выход которого подключен к первому входу вычитателя, выход которого подключен к инФормационному входу регистра., выход которого является выходомвычислительного узла и подключен к инФормационному входу коммутатора, управляющий вход которого соединен с тактовым входом регистра и подключен к управляющему входу вычислительного узла.1532946 Т а б л и ц а 3 Я (Ь Ч Ь 3) Разряды Ь (Ь) 1 ей 2-й Ь)0 -1 Ь) =0 О Ь 0 1 1 0 0 1 О 1 Таблица% Блок 39 конъюнктивного преобразованил Блок 3 ъкомъюнкБлок 3, конъюнктивного преобразоваиил Инфориа ционный вы"ходТакт Информационныйвход Регистр9 Иифорив цнонный выход 3 Комму.татор8 Регистр 9- ха-х 9свХ -Х 9- - хъ+х,Хв-Хв Х,еХ 9 Х 9 Хв Х, -,Хв- Х,еХ, Хтехв л, л х х, Х 9 Хи Х Хв хъ 2 Х П Е н н е н е н н е. 1 Пе(П 2 (2 2 2 22. Таблм ц5 блок 39 конъюнктивного преобразованив Информа ц евходТакт 33 ХтеХн