Генератор функций хаара Советский патент 1980 года по МПК G06F1/02 

Изобретение относится к области автоматики и вычислительной техники Оно может быть использовано в аппара туре сжатия информации при передаче данных, для анализа и обработки видеосигналов, для спектрального анализа случайных полей и т.д. Известен генератор функций Хаара , содержащий генератор знаков элементы взвешивания, ключи, фазоин верторы, коммутаторы. Его недостатком является сложность и невозможность генерирования функций от двух аргументов. Наиболее близким техническим решением к данному изобретению являет ся генератор функций Хаара t, содержащий регистры сдвига номера фун ции и аргумента, два триггера, сумматор по модулю два и блок формирования пачек импульсов. Недостатком известного генератор функций Хаара является невозможност генерирования функций от двух аргументов. Целью изобретения является расши рение функциональных возможностей генератора функций Хаара, Поставленная цель достигается те что генератор функций Хаара, содерж щий сдвиговый регистр номера функции, сдвиговый регистр первого аргумента, первый и второй триггеры, сумматор по модулю два и блок формирования пачек импульсов, причем входы синхронизации регистра номера функции и регистра первого аргумента подключены к соответствующим выходам блока формирования пачек импульсов, управляющий вход которого подключен к выходу первого триггера, выход сумматора по модулю два подключен к установочному входу второго триггера, выход которого является первым выходом генератора функций Хаара, содержит сдвиговый регистр второго аргумента, двухраэрядный СДВИГОВЕЛЙ регистр, дополнительный сумматор по модулю два, элемент НЕ, элемент ИЛИ и четыре элемента И, причем выход регистра номера функции подк.пючен ко входу двухразрядного сдвигового регистра, к установочному входу первого триггера и первому входу первого элемента И, вход синхронизации регистра номера функции и первый дополнительный выход блока формирования пачек импульсов через второй элемент И подключены ко входу синхронизации сдвигового регистра, первый лополнительный выход блока формирования пачек импульсов, через элемент НЕ подключён ко второму входу первого элемента И, выход которого, а также вход элемента ИЛИ подключены ко входам сумматора по модулю два, второй дополнительный выход блока формировани пачек импульсов подключен ко входу синхронизации регистра второго аргумента, выходы регистров первого и второго аргументов подключены ко входМм элемента ИЛИ и к первым входам сЬответственно третьего и четвертого э 1ементов И, вторые входы которых поключены к выходам соответственно первЬго и второго разрядов двухразрядногЬ сдвигового регистра, а выходы кр входам дополнительного сумматора пЬ ь/1одул1с два, выход которого является вторым выходом генератора функций Хаара,

Функциональная схема генератора функций Хаара и его временные диаграммы представлены на фиг.1,2;фиг. 3,4 служат для иллюстрации первых шестнадцати функций Хаара от двух переменных.

Система функций Хаара двух независимых переменных является естественным расширением функций Хаара от с|дной переменной, определенных при Отрезке (О;1) следующим образом:

11о(Л--(г+1 яри 2-14-1 ill. V)tip,(M - uf-u. хеЕр,-- . FTJ Л .i±l О n/3-u. X t , где Р - номер группы, функций (порядок функции) р 1,2,...; . i - номер функции внутри группы функций с номером р, i 0,1, ,..., 2 - 1; cL- сквозной номер функции Хаара Ot 2/-- + i; Sp-i fp-i, pi двоичные отрезки получаемые делением отрезка (0;1) на 2 равных частей. Построим систему Н Cit,V).Q функ ций Хаара двух переменных по аналоги с определением (1). Функции .Хаара H(x,s) двух переменных определены на единичном квад рате 0$х 1, принимают три значения: -1, О и +1. Кв рат Qp.j,j, получаемый делением единичного квадрата на равных час тей, где р 1,2,...п, назовем двоичным квадратом. Точка (х,у) принад лежит двоичному ква.црату Qp.j, если ее координаты лежат на соответствую щих двоичных отрезках ye tp.i 1)-Ьг i,j 0,1,..., 2 - 1, р 1, 2 ... п.

В ДВОИЧНОМ квадрате будем различать четыре равные его части, которые тоже являются двоичными квадратами. Точка (х,у) принадлежит одному из этих квадратов при следующих условиях

JQ.j ,если хб-Гр. .;

Qpi}

На двоичном квадрате определим три ортогональные и линейно независимые функции pi-j-y- (У) для У 1, 2, 3, принимающие лишь два значения -1 и +1 {фиг. 3):

( tip-u, леС.рн

,V)) 1-1 -Hfjixxee-p

pi

(4) (--i n/3-u. t-1 Hp-u. jeTp

(f,

f-ln

pt U,) ь или cx,j)eQ

... pi или u,4)eQp,-j tt/j a,ie Q3Q Теперь определим двумерные функции Хаара:

НО(Х,У) 1, . -«:, (.,.U.),N)eQp,-,j,16) где оС ( л ) +Т. В группе с номером р содержится функций, а все семейство при Р,д п насчитывает 4 функций Хаара двух переменных. Введенная система функций является полной, ортогональной системой линейно независимых функций с интегрируемым в смысле Лебега квадратом. Норма функций этой системы выражается числом //Hj (х,у)// . В предлагаемом устройстве аргументы X и у задаются двоичными, кодеили х г У - -У пятой, фиксированной перед крайним левым разрядом. Номер dL функций Хаара коодируется целым двоичным числом .....dzn а номер 3 модификации функции - целым двоичным двухзначным числом;у 31 i- Принятый способ кодирования номера функции позволяет легко выдел15ть из cL двоичные значения индексов it iiii . . .-гр,., . ip- г номера модификации 7 значение порядка р функции. Разобьем ( п разрядов. Просмотрим эти пары слева направо, отыщем первую пару с ненулевыми значениями разрядов, т.е. первую комбинаЦию 01, 10 или 11. Порядковый номер такой пары при счете справа налев9 и есть порядок р данной функции Хаара. Конкретное значение выделенной пары разрядов указывает значение номера модификации f: 01- 1, 2 2, llj 3. Следующие за выделенной парой р - 1 разрядов являются кодом 1 номера 1, а оставшиеся р - : разркдЪЬ являются кодом 5 номера j . Таким образом, код номера ot, имеет следующую структуру

О О ...О riraiiivip-iJiJz ---ip-i

- кодоС

2п. . . 2р 2р2 p,f 2 р.2 . .р р-1 1

Например, код 00011001 номера ci 25 обозначает функцию Хаара с порядком р 3, номером модификации ТГ z. 1, номерами 1.

На фиг. 4 показаны первые 16 функций Хаара для Ру„д п 2. Указаны;

значения всех индексов этих функций, а для сквозного номера ot приведены двоичные значения, функция с номером с6 О находится вне системы .

Код Т номера i функции Хаара по оси X является кодом значения i /2 левой границы отрезка 6р , а код j номера j функции является значением j /2 Р нижней границы отрезка 6р по оси у. Следовательно, по кодам номеров i и j можно определить принадOлежность точки (к,у) к двоичному квадрату Qpti на основании (2) . Если первые Р - 1 разрядов JC совпадают с разрящами i и первые р-1 разрядов у совпадают с разрядами 5 то точка

5 (х,у) еОр,| и по (5) Н (х,у) j 0.

Для определения ненулевого значения функции Хаара по (3) необходимо анализировать р-ый разряд ic и р-ый разряд у, значения которых приведены

0 .в табл. 1.

Таблица Значение р-го разряда кода у

Далее в зависимости от номера моди фикации по (4) выбирается одна из тр функций х„;.- (к,у) и значение функц Хаара. Сформулируем алгоритм вычисления одного значения функции Хаара. 1. По оС определяются порядок р, номера i и j, модификация . Для это го просмотром-кода ЗГслева направо фиксируется номер с разряда ,, где обнаружена первая встретившаяся единица. Если четно, то, следовательно - 01. Если с нечетно, то для определения кода модификации необходимо рассмотреть значение следующего (q + 1)-ого разряда, так как в этом случае код равен либо 10, либо 11. Обозначим { (, если ( четно, i ,если а нечетно. Тогда t + р - 1 + р -. - 1 2п р - 1 п - е/2. . Для выделения i и j необходимо ос тавшиеся за oi.c разряды разбить на дв группы по р - 1 разрядов каждая. В

1 О 1

Код модификации У с t) значение р-1 является дополнением до п значения /2 и может быть вычислено с помощью счетчика, имеющего не. менее j 600 разрядов. Если единица в не обнаружена, то оС О, Н(Х,У) 1 и вычисления прекращаются. 2.Если единица была обнаружена, то вычисляется логическое значение ок/«х.рм. Р, ( - РМ ЭР- 1®1 2®,М..(У) --VA® P-. при Анёшизируется значение в: если , то (х,у) е (x,y) О и вычисления заканчиваются. Если в О, то (х, у) е Qp4 j. и Н (х,у) jt 0. 3.В случае 9 О анализируются разряды X р и Ур кодов х и у соответственно. Значения этих разрядов с учетом номера модификации определяют значение функции Хаара; эта заBjicHMOcTb показана в табл. 2, причем значения функции Хаара расположены внутри таблицы. Таблица2

Генератор функций Хаара содержит сдвиговый регистр 1 номера функций, сдвиговые регистры 2 к 3 аргументов X и у соответственно, двухразрядный сдвиговый регистр 4 модификации, тр.иггеры 5 и 6, элементы И 7-10, ИЛИ 11, Hh 12, сумматоры по модулю дна 13,14, блок формирования пачек импульсов 15 с управляющим входом 16 и выходами 17 - 20, выходы 21, 22 генератора функций Хаара.

Генератор функций Хаара работает следующим образом, В исходном состояHi H в регистрах 1,2,3 записаны соотвётствеьто 2п-разрядный код номера функции, п-разрядный код аргумента X, п-разрядный код аргумента у .

Триперы 5,6 установлены в нулево состояние. На выходе 17 блока 15 формируется пачка из 2п управляющих импульсов, а на выходе 18 - потенциал единичного значения. Эти импульсы поступают на синхронизирующий вход регистра 1 и через открытый элемент И 7 на синхронизирующий вход регистра 4, вызывая сдвиг содержимого регистров влево. При этом информация на вход младшего разряда регистра 4 поступает с выхода старшего разряда регистра 1, При появлении первого единичного разряда с выхода регистра 1 срабатывает триггер 5, возбуждая управляющий вход блока 15. Этот сигнал является указанием блоку 15 на смену состояния по выходу 18 и отработку пачек импульсов на выходах 19,20. Окончание действия сигнала на выходе 18 соответствует четному номеру ( ) импульса в последовательности, формируемой на выходе 17. В результате в регистре4 оказывается код модификации У у. В дальнейшем элемент И 7 оказывается закрытым а элемент ИВ открывается сигналом с выхода элемента НЕ 12.

На выходе 19 блока 15 появляется пачка, содержащая р - 1 импульс. После ее окончания такая же пачка появляется на выходе 20. Для отработки: такой фу.|кции в состав блока 15 може быть включен, например, счетчик импульсов , содержимое которого определяет число импульсов в пачке. Эти пачки, поступая на синхронизирующие входы регистров 2,3, вызывают сперва сдвиг содержимого регистра 2, а затем содержимого регистра 3. Предполагается, что единичный сигнал на выходе регистра 2 или 3 может появиться только в момент действия соответствующего синхронизирующего импулса.

Элементы И 8, ИЛИ 11 и сумматор по модулю два 13 реализуют функцию (7), значение которой фиксируется триггером 6.

Для анализа разрядов с номером р первого и второго аргументов на синхрон и/1ирую1ине входы регистров 2,3

подается еще один (2п + 1)-ый импульс Значение функции Хаара в соответствии с табл, 2 реализуется элементами И 9, 10, сумматором по модулю два 34 и снимается с выхода 22.

Вычисленное значение функции Хаара считывается с выхода генератора в следующем порядке. На 2п-ом такте работы генератора опрашивается выход 21 триггера 6. Если сигнал на этом выходе отсутствует, то значение функции Хаара равно нулю. Если сигнал на выходе 21 имеется, то на {2п + +1)-ом такте опрашивается выход 22 сумматора 14: сигнал О кодирует значение +1 функции Хаара, а сигнал кодирует значение -1 функции Хаара.

Вазможно, что в течение сдвига содержимого регистра 1 единица в коде номера функции не будет обнаружена {номер of. функции Хаара равен нулю) . В этом случае после окончания сдвига содержимого регистра 1 все элементы схемы генератора сохраняют свои исходные состояния. Следовательно значение функции Хаара равно +1, так как на выходе 21 триггера б действует сигнал, а на выходе 22 сумматора 14 сигнал отсутствует.

При увеличении длины обрабатываемых кодов номера функций и аргументов в схеме генератора изменяются только длины соответствующих регистров 1,2 и 3, а остальная часть схемы остается неизменной.

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

Формула изобретения

Генератор функций Хаара,содержащий сдвиговый регистр номера функции, сдвиговый регистр первого аргумента, первый и второй триггеры, сумматор по модулю два и блок формирования пачек импульсов, причем входы синхрОнизации регистра номера функции и ре.гистра первого аргутчента подключены к соответствующим выходам блока формирования пачек импульсов, управляющий вход которого подключен к выходу первого триггера, выход сумматора по модулю два подключен к установочному входу первого триггера, выход которого является первым выходом

Q генератора функций Хаара, отличающийся тем, что, с целью расширения функциональных возможностей, состоящего в возможности генерирования функций Хаара от двух аргументов, он содержит сдвиговый регистр второго аргумента, двухразряднь сдвиговый регистр, дополнительный сумматор по модулю два, элемент НЕ, элементы ИЛИ и четыре элемента И, причем выход регистра номера функции подключен ко входу двухразрядного сдвигового регистра, к установочному входу первого триггера и первому входу первого элемента И, вход синхронизации регистра номера функции и первый дополнительный выход блока формирования пачек импульсов через второй элемент И подключены ко входу синхронизации двухразряйного сдвигового регистра, первый дополнительный выход блока формирования пачек импульсов через элемент НЕ подключен ко вто рому входу первого элемента И, выход которого, а также выход элемента ИЛИ подключены ко входам сумматора пс5 модулю два, второй дополнительный выход блока формирования пачек импульсов подключен ко входу синхронизации регистра второго аргумента, выходы регистров первого и второго аргументов подключены ко входам элемента ИЛИ и к первкм входам соответственно третьего и четвертого элементов И, вторые входы которых подключены к выходам соответственно первого и второго разрядов двухразрядного сдвигового регистра-, а выходы - ко входам дополнительного сумматора по модулю два, выход которого явлется вторым выходом генератора функций.Хаара. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 596932, кл, G Об F 1/02,24.12.75. 2.Авторское свидетельство СССР по заявке 2675351/18-24,кл. & 06 F 1/02,

-f 1

XHX«

.З