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

 

Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки вычислений в комплексах автоматизированного проектирования дискретных устройств, обработки изображений, сжатия данных, в системах синтеза топологии БИС и СБИС, фильтров на поверхностных акустических волнах. Цель изобретения - расширение класса решаемых задач за счет реализации преобразования булевых функций в арифметическую полиномиальную форму Хаара. Поставленная цель достигается за счет того, что в состав устройства введены коммутатор, блок нормировки, блок синхронизации и N-1 блоков конъюнктивного преобразования (N - число переменных функции). 2 з.п. ф-лы, 11 ил., 4 табл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) 2 46 А1 (51)4 G 06 F 15/332, 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 1

1 -1 (2) где k 2,п;

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) . 4408885/24-24 (22) 12.04.88 (46) 30.12.89. Бюл, V 48 (71) Минский радиотехнический институт (72) B.M.Äàøåíêoâ, Д.В.Кузьмицкий, В.П.шмерко и С.Н.Янушкевич (53) 681.32(088.8) (56) Авторское свидетельство СССР

М 1124281, кл, G 06 F 5/00, t984.

Авторское свидетельство СССР

И 1001107, хп. С 06 Г 15/332, 1983. (54) УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ

БУЛЕВЬ Х ФУНКЦИЙ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной под,Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки вычислений в комплексах автоматизированного проектирования дискретных устройств, обработки изображений, сжатия данных, в системах синтеза топологии БИС и СБИС, фильтров на поверхностных акустических волнах.

Цель изобретения - расширение класса решаемых задач за счет реализации преобразования булевых Функций в арифметическую полиноминальную Форму Хаара.

В основу изобретения положены следующие математические молели компонентов устройств и их взаимодействия в процессе Функционирования.

Спектр.Хаара Н = (h ... h

«О) булевой функции п переменных f(x«,..., xn) .f(x). определяется в виде

2 держки вычислений в комплексах автоматизированного проектирования дискретных устройств, обработки изображений, сжатия данных, в системах синтеза топологии БИС и СБИС, фильтров на поверхностных акустических волнах.

Цель изобретения - расширение класса решаемых задач эа счет реализации преобразования булевых Функций в арифметическую полиномиальную Форму

Хаара. Поставленная цель достигается эа счет того, что в состав устройства введены коммутатор, блок нормировки, блок синхронизации и и-1 блоков коньюнктивного преобразования (n — число переменных функций). 2 з.п. Ф-лы, 11 ил., 5 табл.

Н = - ° Н Х, 2 (1) 2 где Х« = f x« «... х «) j„- вектор размерности 2, элементами которого являются значения булево«1 Функции Е(х) на упорядоченных в лексико графическом порядке наборах переменных (значения таблицы истинности) 1 ©1

Н вЂ” матрица преобразования Хаара, Формируемая по рекуррентному соотношению

15329}}6

Используя свойства преобразования, Хаара, можно показать, что спектр

Хаара Н булевой функцией f(x) запи5 сывается в аналитической форме следующим образом:

2.+ 1

Н (х) „(h +(-1) h +...т-)}2 (-1) Г h (0} Х1 (1) Г X 7yq

1=2 х} в 1г

txl) х}, 1

,где 1 — r-й разряд двоичного представления параметра i (нумерация разрядов начиная со старших, т.е. слева напра1 во), 2=1,п-1 - параметр, соответствующий номеру группы строк матрицы

Хаара (Фиг.1)1 20 ,Х 6(0,1) - j-я булева переменная бу1 J левой функции f (х) .

Особенностью выражения (3) явля ется то, что Н (х) (0,1) на любых наборах логических переменных (х1,,,хо, ..., x„). Причем на одинаковых

,наборах значения Н (х) и Хг совпада ют. Это означает, что выражение (3) ., является арифметико-логическим пред,ставлением булевой функции f(x) no- 30, скольку в нем содержатся арифметичес кие и логические операции. Другой, важной особенностью выражения (3) является его взаимоодноэначная связь с булевой функцией f(x). Другими сло- З5 вами, любую булеву функцию f(x) можно единственным образом представить в виде (3), а по выражению (3) можно .однозначно восстановить булеву функ цию f(x). 40

Рассмотрим пример. Пусть булева

Функция Е(х,,хо).задана своим вектором значений Х2, т.е. таблицей истин-I ности на наборах х } х ®2:

Т : 45

Х = (011OJ .

Определим ее спектр Хаара Н

0

-)2

Н - «2-, Н < Х =

+ а„, х„ i+

}i}

Запишем форму Хаара Н (x) булевой

Функции согласно (3)

55 н < ) - (г + г(-1) (-х + х,)).

1 К2

В табл. 2 представлены спектры

Xaapa H некоторых булевых функций

® — символ кронекеровского произведения:

Т вЂ” символ транспонирования, И-1

I — единичная матрица порядка

1 2" (11 11)-2+1 1П-212 1 2+1

И И

= О, f(x), заданных в табл. 1 своими векторами значений Х .

Выражение (3) есть интерпретация спектра Хаара булевой функцией, причем такая интерпретация, что булева Функция f(x) представлена в новой арифметико-логической форме. В схемо-техническом плане это реализуется посредством известных устройств, выполняющих дискретное преобразование Хаара или быстрое дискретное преобразование

Хаара с последующей интерпретацией результата (спектра) согласно выражению (3), Новая арифметико-логическая форма булевых Функций (3) обладает рядом достоинств арифметического и логического свойств спектра Хаара, обеспечивающих выявление поведения Функции на отдельных или группах наборов, одна" ко имеет и недостатки. (}сновной из них связан с неполиномиальным представлением, что существенно при анализе и синтезе, например, линейных форм булевых Функций.

Полиномиальную Форму Хаара РЕ (х) булевой Функции f(x) определим в виде:

И () - --(h " + „ ° „ж

2п Уг ° + ° °, +

})-<

+2 у„д„,(x „,х, °,х „, ), где у- (-1) }, к

t0} C1}

А}(х ) а1 + a q х}, о)}

А„., (х<, ...,х„,) = а„, Ф"-}}, + +a.„. " x< x„.} °

Ка к видно иэ (ч ) ПОлинОмиал ьная форма Хаара РН (х) булевой функции

1532946

А»

-1

3 (6) 35

55 (8) f(x) представляет собой взвешенную сумму спектральных коэффициентов Хаара h и h (1 и арифметических полиномов А; (х,...х;) (i = l,n-l) . ()пределим Функцию нормировки

S>(h" ):

sÄ(h") - о, 1"=о; (5)

1, h<) 0, i= 2,2 -1, Эта запись означает, что каждому спектральному коэффициенту Хаара h 1, представленному m-разрядным числом

I со знаком, ставится в соответствие двухразрядное число со знаком Sg (h "), 15

Формируемое по правилу {5). Таким образом, спектральные коэффициенты Хаара Ь(0 номируются по признаку знака, т.е. приводятся к величине Sq(h ), принймающей только три значения -1, О, 1 .

Тогда с учетом нормировки в матричной записи связь коэффициентов полиномов А»(х()...., А„, (х», ...,х » ) со спектральными коэффициентами Хаара булевой функции определяется через конъюнктивное преобразование

A» = К » Sg(h ) (н»1

4 (9()»- )

Ал-» = K2»-» $у(Ь ), где

А, =(а, а, );

Г (»>) (») (Я»»- () „T

А»»-» = L R <) - » а»- » ° ° °

S,(Ь " ) = ($ (1 ") Sg(h ")1

9 <ь " " >> - (в»<» >... 9»<ь" >1 .

К р — матрица конъюнктивного пре- 45 образования, определяемая рекуррентным соотношением:

1 О

K»9) = К» »®.Ka(>-»; К»»,,1 р 2 п-1. (7)

С учетом принятых обозначений математическая модель предлагаемого устройства (4) принимает вид:

1 » (е1 »)-»

РН (х) -ajh + ... 2 y„К»»» х

2 (х Sg(h " ) 6

Поясним математическую модель (8) на конкретном примере.

Пусть задана булевая функция f(x) своим вектором Значений

Х - flO0»»of .

В результате преобразования Хаара вектора Х получают вектор коэффициентов спектра Хаара Н

Н» 2з(9 < 0 (2 2 2 О 21

1 т

Находят полиномиальную форму Хаара (PH-Форму) этой булевой функции.

Записывают векторы $ (Ь "»1) и

$ (Ь1 " ):

Sq (1 " ) - (О 1) (11 (я 1) 1 «1 о 1)т и выполняют конъюнктивное преобразоние каждого из них

Следовательно, в полиномиальную форму Хаара РН (х) булевой функции

f (x) входят полиномы

А (х») = х (Az(x,,x()) =1 — 2Х вЂ” х(+ 3х,х» и ее окончательный вид согласно (8):

РН (х) 2з15 - У + 2:У х +

1 г »

+ 2 у (1 — 2Х9 - X» + Зх»х )) .

Для булевых функций f(x), заданных своими векторами значений

Х, = (10000 101»000»3

X1 = (000011101110» 01), Х - (01000111О1110001) т .

РН-форма имеет вид гн,, <х) - -, (8 - г(->)" - (-») +

+ (-1) > (1 - х < — х.,х ) + (-1) "(1

- х — х»х - х + 2х,х — х(х х ));

Рн(,<х> - д(9 - 3(-))" + (->)" +

+ (-1) (х, + х„- х,х,) + (-1)" х

)(Х (Х х + Х»хф Х»X /)) 9

РН,(x) - -, (В -.(-1) x, + (-1) х х (1 - 2х» - 2х» - 2Х»х ) + (-1)

1 + х — 2х + 2х хз + х»х» — 2х, х»х )) .

Те же функции в Форме полинома Же- галкина ийеют вид

1532946 хЪЕ x® Х, Х ХРХ4, 1® x4® хэО+ x,,x4(9 х<

О< Х,<Х4 ® Х< Х Х4(В X<%gXy<

Р1 (х) = хд® х х х4 9 х< 0+ Х4хзх

4® зх4Я: <руЯ х<х О

Результатом реализации математической модели (8) является арифметическая полиномиальная форма Хаара

РНу,(х) булевой функции Е(х), характерная 10

- однозначным описанием исходной булевой функции, - арифметическими операциями типа сложения и вычитания над ее членами (умножение на переменную у = (-1) > 15, 1 есть операция модуляции знака, так ка к у g1,1, -1, а умножение на конJ станты вйла 2+ реализуется посредством сдвигов); композицией полиномов от булевых 20 переменных, которые определяются через знаки коэффициентов Хаара.

Последнее обстоятельство является определяющим в пользу полиномиальной формы Хаара булевой Функции, посколь- 25 ку позволяет описать и численно опре-, делить локальные свойства булевой функции с помощью полиномиальных моделей: упрощает описание и вычисление булевых функций линейных по Хаару, что представляет новый класс булевых функций, имеющих удобное в представлении и реализации линейное описание (линейных в особом смысле), расширяющий множество булевых функций, пред" З5 ставимых в том или ичом смысле линейными формами, обеспечивает на этой основе представление систем булевых функций.

На фиг.1 представлена структурная 40 схема устройства, на фиг.2 - схема блока нормировки, на фиг.3 - структурная схема i-го блока конъюнктивного преобразования, на фиг.4 и 5структурная схема и временная диа- 15 грамма работы i-ro блока конъюнктивного преобразования для i = 2; на фиг.6 и 7 - граф алгоритма и схема конъюнктивного преобразования в блоке конъюнктивного преобразования, на фиг.8 и 9 - -структурная схема и временная диаграмма работы блока синхронизации; на фиг. 10 - временная диаграмма работы коммутатора, на фиг.11процесс формирования устройстЬом

РН-формы .булевой функции f(х) четырех переменных.

Устройство содержит коммутатор 1, блок 2 нормировки, и-1 блоков 3 коньХ, ХР4. юнктивного преобразования и блок 4 синхронизации.

Блок 2 нормировки обеспечивает преобразование спектральных коэффициентов Хаара h(i) (1 = 2,2"-1) в соответствии с математической моделью (5) его функционирования, т.е. преобразует m-разрядный спектральный коэффициент Хаара h ) в двухразрядное значение функции нормировки S (Ь ") в соответствии с табл. 3.

Блок 2 нормировки содержит и-1 регистров 5 и и-1 элементов ИЛИ 6.

Первый блок 3 конъюнктивного преобразования содержит i вычислительных узлов, каждый из которых состоит из вычитателя 7, коммутатора 8 и регистра 9, и счетчик 10.

Рассмотрим работу и-1 блоков коньюнктивного преобразования 3 на приме" ре i-го блока конъюнктивного преобразования 3 (i = 2) (табл. 4). Предварительно счетчик 10 установлен в состояние 00. Введем обозначение х<

= S (h )) (j = 2,2""1).

Первь<м рабочим тактом блока 3 конъюнктивного преобразования является пятый такт работы устройства (табл. 4). На пятом такте значение элемента S q(h(4)) поступает на информационный вход первого вычислительного узла, т.е. на вход вычитателя 7.

С выхода вычитателя 7 (на другом входе вычитателя 7 - значение нуля), значение элемента $< (h()) поступает на вход регистра 9. Счетчик 10 переходит иэ состояния 00 в счетчике 01.

На шестом такте на вход вычитателя 7 поступает значение элемента

Sq(h @} (на другом входе вычитате(Я ля 7 - значение нуля), с выхода вычитателя 7 значение элемента Ь1(Ь )) поступает на вход регистра 9. Счетчик 10 переходит из состояния 01 в состояние 10. Таким образом, по окончании шестого такта в регистре 9 о азываются записанными значения S(h i).

На седьмом такте на вход вычитателя 7 поступает элемент Sq(h @), на другой вход вычитателя поступает с выхода коммутатора 8 значение элемента S (Ы4)) (на втором (управляющем) входе коммутатора 8 - высокий логи10

32946:

9 15 ческий уровень), а на его вход, передается значение элемента $ (Ьи ) с

3 выхода регистра 9, Значение разности элементов $у(Ь(Ь) — $ (М4)) с выхода вычитателя 7 поступает на вход регистра 9.

Кроме того, значение элемента

Sq(h(+) передается на выход первого вычислительного узла и далее на вход вычитателя 7 второго вычислительного узла (фиг.4). С выхода вычитателя 7 значение элемента Sg(h " ) поступает на вход регистра 9 (на другом входе . вычитателя 7 - значение нуля). Счетчик 10 переходит из состояния 10 в состояние 11.

На восьмом такте значение элемента

Sq(h(т ) поступает на вход вычитателя 7; на другой вход последнего с выхода коммутатора 8 передается значение элемента Sg(h() {на втором (управляющем) вхоре коммутатора 8 - высо кий логический уровень). С выхода вычитателя 7 значение разности Sq(h ))Sg(h 1) поступает на вход регистра 9. (51

При этом значение элемента Sq(h ) с выхода регистра 9 передается на вход второго вычислительного узла и далее на вход вычитателя 7. На другой вход вычитателя 7 с выхода коммутатора 8 поступает значение элемента

Sq(h ) (на втором (управляющем) входе коммутатора 8 — высокий логический уровень, а на первом - значение эле- . мента $в(h">)) с выхода регистра 9

С выхода вычитателя 7 значение разности $ (Ь ") — $ (Ь ) поступает на. вход .регистра 9. При этом значение элемента Sg(h(4>), являющееся коэффициентом а® полинома А (х,,х ), с выхода регистра 9 передается на выход устройства. Счетчик 10 переходит из состояния 11 в состояние 00.

В результате на девятом такте на .вход вычитателя 7 с выхода первого вычислительного узла поступает значение разности $ (Ь (ь)) — Sy(h 1) (на другом входе вычитателя 7 — значение нуля). С выхода вычитателя 7 значение разности Sg(h ь1) — $ (Ь 1 ) передается на вход регистра 9. При этом коэффициент a(4) $ (h (5)) — S (Ь (4)) c a xo»

Я да регистра 9 поступает на выход устройства. Счетчик 10 переходит из состояния 00 в состояние 01.

Ка десятом такте на вход вычитателя 7 с выхода первого вычислительного узла поступает значение разности

S :(Ь } — $ (Ь )). На другой вход вы. 5

55 читателя 7 йоступает с выхода коммутатора 8 разность Sq(h 1) — $д(Ь )) (на втором (управляющем) входе коммутатора 8 - высокий логический уровень). С выхода вычитателя. 7 разность

$ (1 Щ ) — $ (ЬО) ) — ($ (Ь(ь) ) — S<(hen)) поступает на вход регист-. ра 9, с выхода которого коэффициент а > Sq(h(1) - Sq(h14>) поступает на выход устройства. Счетчик 10 перехо" дит из состояния Ol в состояние 10.

На одиннадцатом такте с выхода регистра 9 коэффициент а $ (Ь ") (S (he 1) S (hid) пере дается на выход устройства.

Таким образом, на выход устройства в тактах с восьмого по одиннадцатый поступают значения коэффициентов а, в ", а >, аф (табл. 4).

Блок синхронизации 4 (фиг. 73, для

n = 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 сдвига, в котором произво1532946

l2 ческий уровень) . С выхода второго элемента ИЛИ 15 сигнал поступает на пер- вый вход первого триггера 22. Р ре5 зультате триггер переходит в единичное состояние. Таким образом, на первом выходе блока 4 синхронизации формируется адресный код 01. Кроме того, в регистре 13 сдвига производится сдвиг информации, с второго выхода регистра 13 сдвига высокий логический уровень поступает на первый вход четвертого элемента И 21. На первый вход последнего с выхода генератора

11 тактовых импульсов передается cur l5 з- нал, который далее с выхода четвертого элемента И 21 поступает на второй

21 выход блока. 4 синхронизации. Таким образом, на первом выходе блока 4 синхронизации Формируется последовательность тактовых импульсов; отстающая на два такта от последовательности на выходе генератора 11 тактовых импульсов (фиг.9).

На семнадцатом такте блок 4 сина хронизации переходит в исходное состояние. Этот период происходит под действием сигнала переполнения счетчика 17. Сигнал переполнения с четвертого выхода счетчика 17 поступает на вторые входы (входы установки в нуль) первого 22 и второго 23 триггеем ров, а также регистра 13 сдвига. од Рассмотрим функционирование устн- ройства в совокупности составляющих

8 - З5 его компонентов на конкретном приа мере, 40

H+ = UI. 2 2!2 4 - . "о 2 о о 22Т о 2Г оЮ -г»г 2Г2 о7, дится сдвиг в сторону старших разрядов. С первого выхода регистра 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 - низкий логиПусть необходимо представить булеву функцию f(x) четырех переменных, заданную своим спектром Хаара Н1 в полиномиальной форме Хаара Р11 (х).

На первом такте значение спектрального коэффициента Хаара 1Р = 8 поступает на первый (информационный) вход коммутатора 1 (на втором (управляющем) входе которого — адресный код 00). C первого выхода коммутатора 1 значение М о! = 8 поступает на первый выход устройства (Фиг,1), На втором такте значение спектрального коэффициента h »" = 2 аналогично значению h» 2 = 8 передается на первый выход устройства.

На тактах с 3-ro по 16-й включительно значения спектральных коэффи45

55 циентов Хаара с Ь< по Ы @ поступают на первый (информационный) вход коммутатора и в соответствии с адресным кодом на втором (управляющем) входе последнего передаются на входы блока

2 нормировки, причем так, что на первый вход блока 2 нормировки поступают значения коэффициентов h»+! = 2 и

h <+! = -(2т. На второй вход блока 2 нормировки передаются значения коэффициентов Ь " = 4, h") = -2 1 ь) = 0 и

h» ) = 2 и на третий вход блока 2 нормировки поступают значения коэффици-. ентов h» = 0, 1 Р> = 0, h» > = Я2, 14!

532946

ЬУ<) = О, Ььц = 2Г, Ь(> = 2 2

h(" = 212 и h(< = О.

В блоке 2 нормировки Формируются значения х (j = 2, 15) функции

S (Ь!М) в соответствии с математической моделью (5):

-1, h I) < О;

S (h ) = О, h <)0, 3

1, Ь ) -. О, т.е. формируются слелуюцие

1, хэ 1, х<(1, х(, = О, хт = 1, х(. = О, xg х=1x«=Охл=1 х<4 1 < х<з — О, значения

= -1

О, х,> -1, 1 О

А

-1 1

О коэффициентов а ), а ), а и аф

«,) в соответствии с математической мо.делью (6):

Следовательно, полином А((х„) имеет вид: А (х(, = 1 !

Во втором блоке 3 коньюнктивного преобразования Формируртся значения

1 О О 0

-1 1 О О

"1 0 0

1 1

-1 О °

О -1

1- -1

А = Кg (Sg(h ) = К ((х4хзхбхт3

Следовательно, полином A (х,,х ) имеет вид: Ал(х,,х ) = 1 + х, — х,х °

В третьем блоке 3 конъюнктивного преобразования формиру<отся значения коэффициентов ave а<эЗ) ° аэл), а а) а э", аф, а >, а") в соответствии с математической моделью (6):

-,т

x <<(х,э х <4 х< !

-1

1

О

О

О

О

О

О

О

"!

2

-2 блок конъюнктивного преобразования и блок синхронизации, о т л и ч а ю(ц е е с я тем, что, с целью расширения класса решаемых задач за счет реализации преобразования булевых

Функций в арифметическую полиноминальную форму Хаара,.в него введены п-2 (n — число переменных функции) блоков конъюнктивного преобразования, блок нормировки, коммутатор и первый выход блока синхронизации подключен к управляю(цему входу коммутатора, первый выхоД которого является перСледовательно, полином Аь(х,,х <, хз) имеет вид:

Аэ(х,,х д,x ) = х — хлхэ + х, — 2х<хэ + х<х(- 2х<хлхэ.

Табл. 4 и 5 иллюстрируют вычислительный процесс в первом, втором и третьем блоках 3 конъюнктивного преобразования. формула и з о б р е т е н и я

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

Клъ S

О О

1 О

О 1

-1 -1

О О

О -1

1 1 (h (Hs) )

О О

0 О

О О, 1 О:

О 1

О -1

О -1

-1 1

= Клэ

О О

0 0

О О

О О

О О

1 0

0 1

С первого выхода блока 2 нормировки значения х и х передаются на вход первого блока 3 коньюнктивного преобразования 3, с второго выхода блока 2 нормировки значения х4, х -, хь и x g поступают на вход второго блока 3 конъюнктивного преобразования и с третьего выхода блока 2 нормировки значения хл, х, x(y х4,, х,, х,, х,4 и х<в поступают на третий блок 3 конъюнктивного преобразования (табл. 5).

В первом блоке конъюнктивного преобразования 3 формируются значения коэффициентов а((О1 и а (> в соответствии с математической моделью (6)

3 х<0 х

О

О

О

-1

О!

1532146

Табли ца1

° ò

Х» ЛХ Х Х Х ® Хе Х< Х Х ф

Х, Х, Х«Х, . Х«

f (х), Х„Ч

Хл Х

Х,Х, Х«

1

О

О 0 О

О

1 О 1

1 1 1

О 1

О 1 О

О 0

1 0 -0

1 о

О

Таблица2

Й (х) Коэффициенты спектра

Хаара

Н-форма записи функции, (о) о) (ю) 1, (ъ) - Гг 0 1!4Ь

О 42 1/4 11

О Я 1/2 Р

Г2 "1 2 1/2 (!

- Г2 4 2 1/2 (1

Г2 -f2 1/2 )1 2 О 1/4 «1

0 2 1/4 f3

3 -1

1 -1

2 2

2 О

2 О

2 О

1 !

x

x,Лх, х, х х,Юх х х х х х,! х

Вым информационным выходом устройства, информационным входом которого является информационный вход коммутаТора, i-й (i 2,n} выход которого подключен к (-1) -му информационному ходу блока нормировки, (i-l)-й выод которого подключен к информационому входу (i-1)-го блока конъюнктивого преобразования, выход которого 10 вляется i-м информационным выходом стройства, а второй выход блока синронизации подключен к тактовым вхо" ам блока нормировки (i-1)-го блока конъюнктивного пре браэования . 15

2. Устройство по п.l, о т л и ч ащ е е с я тем, что блок нормиров ки содержит и-1 регистр и и-1 элемент йЛИ, выход j"ãî (j 2,m; ш - разряд, ность) разряда (i-1)-го регистра под, ключен к (j-1)-му входу (i-l)-ro элемента ИЛИ, выход которого объединен с выходом первого разряда (1-1);го регистра и образуют (i-1)-" выход 2 блока нормировки, (i-1)-м информационным входом которого является инфор-. мационный вход (i-1)-ro регистра, тактовый вход которого подключен к тактовому входу блока нормировки.

3, Устройство по п.l, о т л и ч аю щ е е с я тем, что (i-l)-й блок конъюнктивного преобразования содержит счетчик и (i-1) вычислительный модуль, причем выход 1-го (1 = l,i-1 разряда счетчика подключен к управляющему входу 1-ro вычислительного узла, выход k-ro (k = 1, i-2) вычислительного узла подключен к информационному входу (k+1)-го вычислительного узла, выход (i-1)-го вычислительного узла является выходом блока конъюнктивного преобразования, тактовым и информационным входами которого являются соответственно счетный вход счетчика и информационный вход первого вычислительного узла, причем 1"й вычислительный узел содержит вычитатель, регистр и коммутатор, выход которого подключен к первому входу вычитателя, выход которого подключен к информационному входу регистра., выход которого является выходом вычислительного узла и подключен к информационному входу коммутатора, управляющий вход которого соединен с тактовым входом регистра и подключен к управляющему входу вычислительного . узла.

- (-1) - 2 (-1) хД (-l) - 2 (-1) +х(хД

)1 )

+ ("1) (x + х,х )j

+ (-1)" (-х + х х,Я

+ (-1) (х - х х )»

+ (l)х4 + (1РЯх)

+ (-1)" + 2 (-1)"< х(хД

1532946

Таблица 3

S (h ")

Разря,1ы S (1! ) 1-й 2-й

h t> 0 -1

Ф! =0 0

h 31 0 1

0

0

Таблмца4

Блок 3, конъюнктивного преобразованил

Блок 3> комъюнкБлок 3. конъюнктивного преобразоваиил

Информа ционный выход !

Такт

Информационный вход

Регистр

Ииформа цмонный выход 3

Коммутатор

Регистр

Коммутатор

8 тивного преобразованил

Информационный выход 2

Ре гистр 9

Коммутатор

Регистр 9! !» !

<4! Ьв

2 !("

3 Х9 х, 5 Хо

Х9

Xs-hi

X9 a, Х, в(п

- х -х х, х х, х-х

Хв х,-х, х;-х

6 Хв

2 х х х

8 х, 9 х, ° ах

Nl а (е

e X ° -Xo

4((4 P Хз- Х9 гв

-X -Х4- хъ+х, х,-х, Х -Х9 х

Хв! е х, x, -.х - х,-х, -Хт ОХ9 х х>

Х» х

Х9

Хи

Х» х, хъ х!

2 Х((ПР .1 бд(() () 2,2.().

Табл» ц ° S

Блок 3> конъюнктнвного преобразование

Такт Информа ц ° вход !

33 Xoo х, -х

Xн х» х, х„-х, Х,т -Xi х» хч

x« -x» х„-х, Х(т -Х9

X(l

Х (4 "X(( х„-х„

Х -Х9

X„9-Х4 хм-х

x, --x„ х„-х, Х». хн х, -х»

Х, Хв х1

94 х х

I9.Х» -Х9

Х»!

5 х, Х,. Хз х„-x, х>

x» xl! б х» хе а"99 s sХз

Х Хв х, Хм-Хт аз Х -Х и

I х»-х

Х»-Х9 as - Х„-Х

Х9

У 9-Х °

X„„-Х9X „-Х,-x +х (а

Регистр 9 Комму- !Регистр 9 Комму- Регистр 9 Комму- Информационный выход 4 татор Sj татор 8 тагор 8

1532946

ФФЕ г»»ее««еее»»Ф.

Блок 3в е » т» ее »»» ii» е

Комиу- Информационный амход е татор 8(Ф е» е» I е

l Комму- Per ctp 9 твтор 8

»»

Регистр 91Комму- Регистр 9

1твтор 8

1,— х +х x1& хь

«»е е

<М

& 4 и Х ц «Хфх «+ХВ х„-x„„ х„-х, х1ь -ха

-х „+х, Х4В +хь

-хн+хе х «-хь

-х, +х

Х! ° "XI &| и ХФЕ-ХФ (« ьа)

- х « хе-a„+xþ х„-х

-х,т+х, x«s-хн -x„„+x,-x„„=x„« х "х .х х! -х„+хВ&|. Хм-х!а-х«+хю.

& ь" ™ ю -Хть -Хц, ехе«Х и +Х & +Х ««ХВ

22 23 ® f

} тркт; Мнфоре мац.. вход 1, 19

j20 х,-х, x„„-х, х, .-х„

x«-x« х, -х, конъвиктивиого нреобрааованив

Продолжение табл.5.

)532946

1532946

Вычииаеельнае йюсгиюгьюю ячейка 1 ячейгаE

Ужж

1532946

keu8 гМрию ра лактажх

uPmgnbPSd Н

Жал 2 Люка рраЮцио 4 бх63 Г ktynbаииаксща 12 яиц 2 йхаУ

1риггрр 22

ТРипер Г5

gg 01 Ю Риг. N

1532946

II Я

%с ф

«»»

<:в

» «»сц . » с, Ф . ф Ф;З У

Составитель А.Баранов

Редактор Л.Пчолинская Техред Q.Ходани Корректор СЛ1екмар

Ьй

«»еа»

:-Ьказ 8101/54 Тираж 668 Подписное

ВНИИПИ Государственного комитета ло изобретениям и открьггиям лри ГКНТ СССР

Ъ

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. ужгород, ул. Гагарина, 101

«Г»

«» ф ф >Ъ

Ф, ъ Ф ° ф РЗЯ

«Фь « Ф у

Ф с Э

Юф +

)ь Феэ

% ф к ъ, + »

«»

»р

Ф

° с

) ф »

@э

1- +

В»,Ъ „

1 у % @

+ e +