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

 

Изобретение относится к области автоматики и вычислительной технике и может быть использовано в цифровых системах связи, для построения устройств цифровой фильтрации, сжатия изображений и выделения контуров, основанных на алгоритме быстрого преобразования Хаара, в аппроксимирующих устройствах кусочно-линейного типа. Цель изобретения - расширение функциСЛ a-t фиг I

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

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

РЕСПУБЛИК (19) (l1) (511 4 С 06 F 15/332

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

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ

c*t

Фиг. (ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4031227/24-24 (22) 27.02.86 (46) 07.07.87. Бюл. И 25 (71) Институт технической кибернетики АН БССР (72) P Х.Садыхов, С.А.Золотой, А.В.Шаренков и Н.H.Ëåãîíèí (53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 1104528, кл. С 06 F 15/332, 1983.

Патент США Ф 3792355, кл. G 06 F 15/332, 1974. (54) УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ !!О ФУНКЦИЯМ ХААРА (57) Изобретение относится к области автоматики и вычислительной технике и может быть использовано в цифровых системах связи, для построения устройств цифровой фильтрации, сжатия изображений и выделения контуров, основанных на алгоритме быстрого преобразования Хаара, в аппроксимирующих устройствах кусочно-линейного типа.

Цель изобретения — расширение функци1322310

11111111

1111111

111111

1 1 1 1 1

1 1 1 1

1 1 1

0 1 1

1 (2) I в

11111111

1-.1 1-1+ 1 — 1+1- 1

10-1010-10

0 1 0-1 0 1 0-1

1000-1000

01000-100

001000-10

0001000-1

Н в

0101

10-1 0

010-1

00010001

1000-1000

01000-100

001000-10

0001000-1 (3) X=CHIt

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

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

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

На фиг.l представлена функциональ-ная схема устройства, на фиг.2 — граф быстрого алгоритма преобразования в базисе Õààðà.

Устройство содержит блоки 1 и 2 задержки, сумматоры-вычитатели 3, коммутаторы 4, триггеры 5, накапливающий сумматор 6, одновибратор 7 и установочный вход 8. Все блоки устройства сгруппированы в п- 1 ярусов. Каждый иэ блоков 1 задержки осуществляет эадерж25 ку информации на один такт, блок 2 задержки в i-м ярусе (i=1 — п- 1, 2" =

=N-размерность преобразования) осуществляет задержку íà 2i- 1 тактов.

Триггеры 5 соединены по схеме двоичного счетчика.

Работа устройства основывается на следующих положениях.

Произвольный вектор Х представля- 35 ется линейной комбинацией и базисных интегральных функций Хаара: где С вЂ” вектор-строка коэффициентов, Н вЂ” матрица преобразования Хаара, оператор интегрирования. матор 6, одновибратор 7, установочный вход 8. Введение коммутаторов, накапливающего сумматора, триггеров и одновибратора обеспечивает возможность обратного преобразования по интегральным функциям Хаара. 2 ил.

Для N=8 оператор имеет вид

Матрица Н факторизуется и позволяет построить быструю вычислительную процедуру, которая для N=8 имеет вид

Восстановление сигнала в базисе кусочно-линейных функций Хаара может быть реализовано в два этапа. На пер13223«! ном этапе к массиву из >Ч кп >ффициентон С; применяют преобразование Хаара согласно (3). На втором этапе к

ПОЛУЧЕННОМУ МгаССИНУ (Х ПрИМЕ}}ЛЮт оператор интегрирования Т согласно (2) °

В исходном состоянии и-й триггер

5 установлен в "1" и осуществляет блокировку накапливающего сумматора !р

6. Триггеры 5 с перного по (n-1)-й установлены в "0". Начальная ycTaflo13ка производится по сигналу на входе

8 одновибратора 7.

На вход блока 1 задержки (i=1) по-!5 ступают коэффйциенты разложения по интегральным функциям Хаара С Г,C ...

С „, и задерживаются на один такт, таким образом, н первом такте на выходах суммы (+) и разности (†) сумматора-вычитателя 3(i=1) будут сформированы С +С, и С,-С, соответственно, во втором такте — С, +С„ и С, -С,, в третьем — С +С и С.-С и т.д. Разности поступают в блок 2 зад»ржки (i=1) H s ep>KH1< }<>TcfI «а один такт.

Коммутатор 4 (i=1) упранляе тся триг— гером 5 (i=1), делящим 1>xnpf}y}3> так— товую частоту на дна, таким обра}3ом, коммутатора 4 последовательно проходят (С, +С, ), (1:,.-C ), (С,+С,), (С,-С,),...(С„, +С„), (С„,—

-С„) . Эта последонательнс>стl,, поступив на вход блока 1 задержки второго яруса (i=2), задерживается такя.» на один такт. В результате н третьем такте на выходе блока 1 запер.:. ки (i=

=2) (C,+С, ), на второй вход сумматора- вычитателя 1 (1=-2) поступает С, следовательно На ныхп1}е 4}> суммы (+) сформировано значение (С„+

+С,+Cz). Последнее число поступает через коммутатор 4 (i=2) на нхпд следующего яруса, на выходе разности (-) сумматора-вычитателя 3 (1=2) сфпрмн- 45 руется (C +C С ) и поступает н блок

2 задержки (1=2). По четвертому такту на выход коммутатора 4 (i=2) поступает (С,-C, +C ), по пятому — (C +C

-С ), а по шестому — (С,-С, -Сз) q скольку коммутатор 4 второго яруса управляется триггером второго яруса, делящим входную тактовую частоту на четыре.

В третьем ярусе (1=3) по четвертому55 такту на выходе блока 1 задержки сформируется (С +С,+С ), на втором входе сумматора-вычитателя 3 (i=3) — С, а на выходе — значение С,+C,+С,+С,, по пятому такту — (С„-С<+С +С,) и т ° д. согласно графу (фиг.->). Аналогично работают блоки остальных ярусон с тсй лишь разницей, что в блоке 2 saдержки i-ro яруса сигнал задерживается на 2 тактов, а коммутатор 4

i-го яруса управляется i-м триггером 5, делящим частоту тактонь}х импульсон на

2 . Таким образом, через N/2 тактов на нь}ходе суммы сумматора-нычитателя

3 последнего и-1-го яруса сформирован

> I > с тсчет Х,, далее Х,, Х, ° ° ° «Х><» . a > на выходе разности формируются отс>}»ты Х,, „ ..., Х,, По N/2-му такту триггер 5 (и-1)-rn яруса устана>>лн}ается н "1", что приводит к

c6pc,cу и-ro триггера 5 н "0". Происхпд}}г разблокирование накапливающего сумматора }>, и на его выходе последс н;! T льнс <1>с>1>11}ру}с>те я частные сум,.1}, Х. ., (Х„+ Х, ), (Х, + Х, + Х,),..., (\ +... + Х,), чтп соответствует

Ог}с ратору интс грирпвания (2). По (N/2+

+Ч)-му такту и-й триггер 7 опять усTc) I} 1}линзе т ся 13 . Это озн ачае т, чтп закончилос.ь формирование ординаTfl Х . При этом на выходе однонибр;1 } i>p;1 7 формируется импульс начальной установки.

1 с 11 на н} с>г} блока 1 задержки пер—

13<> ГО Я P yCС} IIO CT>>>II>110т КПЭф1фнЦИС(Н TI>f ра-злпжения 1 ряд и по фун};циям Хмара, на },}I>}ñдс коммутатора 4 последнего яруса формиру}нтся с>р;1}п}ать} 13псстанонн fl}}i>ГО сигнала 13 6 lslfcc куcс>чно пп стоянных функций.

>1> с> р м у л а и э и 6 р с т е н и я

Устройстг>О для прс образ»на}}ия пп функциям Хаара, сод< ржа:>}ее (и — 1) сум» .<аторон-вычитателей (? — размерность преi!6ðësàflàíèÿ) и 2(п-1) блоков зад ржки, вход первого блока задержки янг}яется информационным входом уст-ройства, выход (2i 1) † блока задержки (i=1 .. и 1) подключен к входу первого операнда i ãî сумматора-f!fl— читателя, выход разности i-го сумматора-вычитателя подключен к входу

2i-го блока задержки, о т л и ч а ю<— щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет выполнения обратного преобразования по интегральным функциям Хаара, оно содержит накапливающий сумматор, п триггеров, (и- 1) коммутаторов и одновибратор, причем входы второго операнда всех суммато1322310

I "2

co+ +Ct с, Фиг. 2

Составитель В. Байков

Техред Л. Олийнык

Корректор С,Щекмар

Редактор Н.Рогулич

Тираж 672

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Заказ 2867/47

Подписное

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная;4 ров"вычитателей подключены к информационному входу устройства, выход суммы 1-го сумматора-вычитателя и выход 2 -го блока задержки подключены к информационным входам i-ro коммутатора, выход i-ro (кроме (n-1)-ro) коммутатора подключен к входу (2i+

+1)-го блока задержки, выход (п-1)-го коммутатора подключен к информационному входу накапливающего сумматора, счетный вход первого триггера является тактовым входом устройства, выход

i-го триггера подключен к управляющему входу i"ro коммутатора и к счетному входу (i+1)-ro триггера, выход п-ro триггера подключен к установоч5 ному входу накапливающего сумматора, и входу запуска одновибратора, выход одновибратора подключен к установочным входам триггеров с первого по (n- 1)-й, вход сброса одновибратора является установочным входом устройства, выход накапливающего сумматора является выходом устройства.