Генератор функций хаара

 

Союэ Советских

Социалистических

Республик

ОП ИСАНИ Е

ИЗОБРЕТЕНИЯ

I (iii783 778

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 17.01.79(21) 2714726/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 3р.118р Бюллетень ¹ 44

Дата опубликования описания 30, 11. 80 (5()М. Кл.

G 06 F 1/02

Государственный комитет

СССР ио делам изобретений и открытий (53) УДК 681. 3 (088. 8) (72) Авторы изобретения

A.A. Докучаев и В.A. Эенцов

Ленинградский ордена Ленина эгектротехнический институт имени B. И. Ульянова (Ленина) (73) Заявитель

" и" 1(е т ь . ,Ч и (54) ГЕНЕРАТОР 4УНКЦИЙ XAAPA

Изобретение относится к области автоматики и вычислительной техники.

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

Известен генератор функций Хаара (1), содержащий генератор знаков, элементы взвешивания, ключи, фаэоин- 10 верторы, коммутаторы. Его недостатком является сложность и невозможность генерирования функций от двух аргументов.

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

Недостатком известного генератора функций Хаара является невозможность генерирования функций от двух аргументов. 25

Цельк изобретения является расширение функционагьных возможностей генератора функций Хаара, Ноставгенная цель достигается тем, что генератор функций Хаара, содержа- 30 щий сдвиговый регистр номера функции, сдвиговый регистр первого аргумента, первый и второй триггеры, сумматор по модулю два и блок формирования пачек импульсов, причем входы синхронизации регистра номера функции и регистра первого аргумента подклкчены к соответствующим выходам блока формирования пачек импульсов, управляющий вход которого подключен к выходу первого триггера, выход сумматора по модулю два подключен к установочному входу второго триггера, выход которого является первым выходом генератора функций Хаара, содержит сдвиговый регистр второго аргумента, двухразрядный сдвиговый регистр, дополнительный сумматор по модулю два, элемент НЕ, элемент ИЛИ и четыре элемента И, причем выход регистра номера функции подключен ко входу двухразрядного сдвигового регистра, к установочному входу первого триггера и первому входу первого элемента И, вход синхронизации регистра номера функции н первый дополнительный выход блока формирования пачек импугьсов через второй эгемент И подклкчены ко входу синхронизации сдвигового регистра, первый лополнитель783778 е „

"-eЛ, „ ае.Г„

"Р1

1 ,если ,если

Р ) ,если о .. если и Чб р, ичко,$

Р9 иЧЕ,С . ичеЮ (3) (х,ч) е (4) ) (И= Ь „.(1 ный выход блока формирования пачек импульсов, через элемент НЕ подключЕн ко второму входу первого элемента И, выход которого, а также вход элемента ИЛИ подключены ко входам сумматора по модулю два, второй дополнительный выход блока формирования пачек импульсов подключен ко входу синхронизации регистра второго аргумента, выходы регистров первого и второго аргументов подключены ко вхо- 10 дам элемента ИЛИ и к первым входам соответственно третьего и четвертого элементов И, вторые входы которых подключены к выходам соответственно перacro и второго разрядов двухразрядного сдвигового регистра, а выходы — 15 ко входам дополнительного сумматора по модулю два, выход которого является вторым выходом генератора функций

Хаара.

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

3,4 служат для иллюстрации первых

Шестнадцати функций Хаара от двух переменных.

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

+ г л 21+" и и ХЮ,р = Р g ii 2 Р /

Р1 2Р (1) 2(+(4+»

-" Ф хе (2 2Р-")

У (1

О «ф Х Р.1 29 1 2Р-1) где P — номер группы функций (порядок функции) р = 1,2,...;

1 - номер функции внутри группы функций с номером р, 1 = 0,1, 2" сквозной номер функции Хаара (.= 2Р " +

- двоичные отрезки, получаемйе делением отрезка f0;1) на

2Р равных частей.

Построим систему Н,((4,3)) о функ- 5О ций Хаара двух переменных по аналогии с определением (1).

Функции Хаара Н, (х, y) двух переменных определены йа единичном:квадрате О х а 1, и О с 1 и при- 55 нимают три значения: -1, О и +1. Квад. рат Qp;, получаемый делением единичного квадрата на 4 Р равных частей, где р = 1,2,...п, назовем двоичным квадратом. Точка (х,у) принад" @ лежит двоичному квацрату Qpqjt если ее координаты лежат на соответствующих двоичных отрезках х Ю(-и ye f.о и*и (2" » 1Р- (Чи 2Ð r y, 2P-4 ) где i,j = 0,1. .. 2Р " — 1, р = 1, 2 ... n„

В двоичном квадрате Qpq> будем различать четыре равные его части, которые тоже являются двоичными квадратами, Точка (х,у) принадлежит одному из этих квадратов при следующих условиях

На двоичном квадрате () „ определим три ортогональные и линейно независимые функции xp„ - (х,y) для

1, 2, 3, принимающие лишь два значения -1 и +1 (фиг. 3):

-1 ври. y. ср„.

„",(" ч) =х Р, (х t „

Р1 р» (1 р ч Г

Х Р, 2(Х>3 - X P (3),,„„Ч Е Р) (.х s) E Q »> a (x чМQ

Р1) ъ -1 tp и. (у„ч)я я,. и,(и (y,чч 4

Теперь определим двумерные функции Хаара:

Нс (хг у) где О(.= 2 - (2 ) + j ) + Ъ . В rPynпе с номером р содержится 3 4 к " функций, а все семейство при Р, „ = и насчитывает 4" функций Хаара двух переменных.

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

В предлагаемом устройстве аргументы х и у задаются двоичными кодами

Ъ х = хях х< и y = y

Т а б л н ц a l

О наЦию 01, 10 или ll. Порядковый номер такой пары при счете справа налево и есть порядок р данной функции

Хаара. Конкретное значение выделенной пары разрядов указывает значение номера модификации ; 01 = 1, 10

= 2, 11 = 3. Следующие за выделенной парой р — 1 разрядов являются кодом номера i, а оставшиеся р - 1 разрядбв являются кодом 3 номера

Таким образом, код номера, имеет следующую стРуктуру 19

+1 Ь т p q), f р- код Д, 2n...2p+< 2>2р< 2 >z...ð р-1 .......1

Например, код 00011001 номера с(.= 25 обозначает функцию Хаара с порядком р = 3, номером модификации = Ol — 1, номерами 1 = 10 = 2 и j = 01 =

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

Y фикации по (4) выбирается одна из трехЯО функций х „. (x,у) и значение функции

Хаара.

Сформулируем алгоритм вычисления одного значения функции Хаара.

1. По ф.определяются порядок р, 35 номера i и 3, модификация . Для этого просмотром -кода слева направо фиксируется номер q разряда О,, где обнаружена первая встретившаяся единица. Если с четно, то, следовательно f 01. Если с нечетно, то для определения кода модификации необходимо рассмотреть значение следующего (q + 1)-ого разряда, так как в этом случае код равен либо 10, либо 11.

Обозначим 45 (, если ф четно, pic,åñëè q нечетно..

Тогда 4 + р — 1 + p — 1 = 2n или

p — 1 = и — $/2. (6) щ

Для выделения 1 и j необходимо оставшиеся эа с(. разряды разбить на две группы по р — 1 разрядов каждая. В значения всех индексов этих функций, а для сквозного номера o(. приведены двоичные значения, функция с номером (. О находится вне системы „

Код . номера i функции Хаара по о-4 оси х является кодом значения 1 /2 левой границы отрезка Рр,, а код j номера j функции является значением

3 /2 P нижней гРаницы отрезка fp> по оси у. Следовательно, по кодам номеров i u j можно определить принадлежность точки (х,у) к двоичному квадрату Яр.(на основании (2). Если первые Р— f разрядов х совпадают с разг% рядами и первые р — 1 разрядов у совпадают с разрядами 3, то точка (х, у) 6 Я ><> и по (5) Н „ (х, у) ) О, Для определения ненулевого значения функции Хаара по (3) необходимо анализировать р-ый разряд х и р-ый разряд у, значения которых приведены

В табл. 1. ляется дополнением до п значения

6/2 и может быть вычислено с помощью счетчика; имеющего не.менее ) о

h+ 4 t. Разрядов.

Если единица в не обнаружена, то < . = 0 Н (х,у) = 1 и вычисления прекращаются.

2. Если единица была обнаружена, то вычисляется логическое значение о scarc p= ( х, (=) „ч хЯ д ... хр,Э Р- чч„&чч О+) ч.. ()) ® р-, при (P < A

Анализируется значение : если 6 = 1, то (х, у) Я Q< Н, (х, у) = О и вычисления заканчиваются. Если 9 = О, то (x у) е. Я,(1. и Н,, (х,у) у О.

3. В случае 9= О анализируются разряды х > н у кодов х и у соотР ветственно. значения этих разрядов с учетом номера модификации определяют ."ыачение функции Хаара; эта зависимость показана в табл. 2, причем значения функции Хаара расположены внутри таблицы.

Т а блица 2

783778

Генератор функций Хаара содержкт сдвиговый регистр 1 номера функций, сдвиговые регистры .2 и 3 аргументов х и у соответственно, двухразрядный сдвиговый регистр 4 модификации, триггеры 5 и 6, элементы И 7-10, И31И

11, НЕ 12, сумматоры по модулю два

13,14, блок формирования пачек импульсов 15 с управляющим входом 16 и выходами 17 — 20, выходы 21, 22 генератора функций Хаара.

Генератор функций Хаара работает

cëåäóKùHì образом. В исходном состоянии в регистрах 1,2,3 записаны соответственно 2п-разрядный код номера функции с, п-разрядный код аргумента х, п-разрядный код аргумента у. 35

Триггеры 5,6 установлены в нулевое состояние, На выходе 17 блока 15 формируется пачка из 2п упранляющих импульсов, а на выходе 18 — потенциал единичного значения. Эти импульсы 2О поступают на синхрониэирующий вход регистра 1 и через открытый элемент

И 7 на синхрониэирующий вход регистра 4, вызывая сдвиг содержимого регистров влево. При этом информация на вход младшего разряда регистра. 4 поступает с выхода старшего разряда регистра 1. При появлении первого единичного разряда с выхода регистра

1 срабатывает триггер 5, возбуждая управляющий вход блока 15. этот сигнал является указанием блоку 15 на смену состояния по выходу 18 и отработку пачек импульсов на выходах

19,20. Окончание действия сигнала на выходе 18 соответствует четному номеру (Я ) импульса в последовательности, формируемой на выходе 17.

В результате в регистре 4 оказывается код модификации,, 3 . В дальнейшем элемент И 7 оказывается закрытым, До а элемент И8 открывается сигналом с выхода элемента НЕ 12.

На выходе 19 блока 15 появляется пачка, содержащая р — 1 импульс. После ее окончания такая же пачка появляется на выходе 20. Для отработки такой функции в состав блока 15 может быть включен, например, счетчик импульсов, содержимое которого определяет число импульсов в пачке. Эти пачки, поступая на синхронизирующие входы регистров 2,3, вызывают сперва сдвиг содержимого регистра 2, а затем содержимого регистра 3. Предполагается, что единичный сигнал на выходе регистра 2 или 3 может появиться только в момент действия соотвЕтствующего синхронизирующего импульса, Элементы И 8, ИЛИ 11 и сумматор по модулю два 13 реализуют функцию gQ (7), значение которой фиксируется триггером 6.

Для анализа разрядов с номером р первого и второго аргументов на синхроllизирукх,-,ие входы регистров 2, 3 65 подается еще один (2n + 1) -ый импульс.

Значение функции Хаара в соответствии с табл. 2 реализуется элементами И

9, 10, сумматором по модулю два )4 и снимается с выхода 22.

Вычисленное значение функции Хаара считывается с выхода генератора в следующем порядке. На 2п-ом такте работы генератора опрашивается выход

21 триггера 6. Если сигнал на этом выходе отсутствует, то значение функции Хаара равно нулю. Если сигнал на выходе 21 имеется, то на (2n +

+1)-ом такте опрашивается выход 22 сумматора 14: сигнал 0 кодирует значение +1 функции Хаара, à сигнал 1 кодирует значение -1 функции

Хаара.

Вазможно, что в течение сдвига содержимого регистра 1 единица в коде номера функции не будет обнаружена (номер M функции Хаара равен нулю).

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

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

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

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

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

Фиг. 1 гистр второго аргумента, двухразрядный сдвиговый регистр, дополнительный сумматор по модулю два, элемент НЕ, элементы ИЛИ и четыре элемента И, причем выход регистра номера функции подключен ко входу двухразрядного 5 сдвигового регистра, к установочному входу первого триггера и первому входу первого элемента И, вход синхронизации регистра номера функции и первый дополнительный выход блока формирования пачек импульсов через второй элемент И подключены ко входу синхронизации двухразрядного сдвигового регистра, первый дополнительный выход блока формирования пачек импульсов через элемент НЕ подключен ко вто- рому входу первого элемента И, выход которого, а также выход элемента ИЛИ подключены ко входам сумматора по модулю два, второй дополнительный выход блока формирования пачек импульсов подключен ко входу синхронизации регистра второго аргумента, выходы регистров первого и второго аргументов подключены ко входам элемента ИЛИ и к первым входам соответственно третьего и четвертого элементов И, вторые входы которых подключены к выходам соответственно первого и второго разрядов двухразрядного сдвигового регистра; а выходы — ко входам допол— нительного сумматора по модулю два, выход которого явлется вторым выходом генератора функций Хаара.

Источники информации, принятые во внимание при экспертизе

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

Р 596932, кл. G Об F 1/02,24.12.75.

2. Авторское свидетельство СССР по заявке Р 2675351/18-24,кл. G 06 F 1/02р

1978.

783778 хн хк внИИни Заказ 8549! 51 Тираж 751 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная,4

О 1

e = попо=о

9g х„х„

Фий.3

"и хн