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

 

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

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22) Заявлено 250880 (21) 2979335/18-24 (5$) Q. Кд.з с присоединением заявки ¹â€”

G 06 F 15/332

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

СССР по делам изобретений и открытий. (23) Приоритет (33) УДК 681.3 (088. 8) Опубликовано 3004.82. Бюллетень ¹ 16

Дата опубликования описания 3004.82 (72) Авторы изобретения

A.A. Докучаев, В.A. Зенцов и С. . Свийьин

1

Ленинградский ордена Ленина электрическйй"институт им. В.И. Ульянова, (Ленина) (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ДИСКРЕТНОГО

ПРЕОВРЛЗОВАНИЯ XAAPA

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

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

Наиболее близким по технической сущности и предлагаемому является устройство для выполнения дискретного преобразования, содержащее N групп блоков, каждая из которых состоит иэ трех сумматоров-вычислителей и трех регистров сдвига (2).

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

Хаара (Уолша) и не могут производится. двумерное преобразование дискретных сигналов.

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

Поставленная цель достигается тем, 5 что в устройстве для выполнения дискретного преобразования Хаара, содержащем N групп блоков (4" - число коэффициентов двумерного преобразования),каждая из которых состоит иэ трех сумматоров-вычитателей и трех регист(йов сдвига, причем первый и второй входы i-го сумматора-вычитателя и-й группы (=1,2,3; n =l-N) соединены соответственно со входом и выходом i-о регистра сдвига и-й груп15 пы, вход первого регистра сдвига первой группы является входом устройства, выходы суммы и разности первого сумматора-вычитателя каждой группы подключены ко входам второго

20 и третьего регистров сдвига той же группы, выход суммы второго сумматора-вычитателя н-й группы, кроме

Б-й группы, подключен ко входу первого регистра сдвига и +1-й группы, 25 выходы разности первых и вторых сумматоров-вычитателей, выходы суммы и разности третьих сумматоров-вычитателей всех групп, а также выход суммы второго сумматора-вычитателя N-ой

30 группы являются выходами устройства.

924 16

JI; фиг. 1 показаны первые шестнадцать функций Хаара двух переменных; на фиг. 2 — функциональная схема устройства для выполнения дискретного преобразования Хаара.

В предлагаемом устройстве осу- 5 ществляется последовательная дискретная обработка 4 значений входf4 нога сигнала с целью получения 4 коэффициентов дискретного разложения в базисе функций Хаара от двух пере- )0 менных или 2 коэффициентов (M=2 N) дискретного разложения в базисе функций Хаара одной переменной.

При выполнении одномерного дискретного преобразования Хаара на вход 5 устройства должны поступать последовательно 2 значений входного сигнала, а при выполнении двумерного преобразования. на вход устройства должна поступать последовательность из 4" значений входного двумерного сигнала,20 упорядоченные определенным образом.

Например, для N = 2 и М = 4 шестнадцать отсчетов двумерного входного сигнала у„- =у(„.,с1 ) должны поступать на вход в следующем порядке: у„„, у, 25

1 1

У21 y22 У13 Ул4 y23 y94 У3л

У32 y « ° У 42 ° У33 ° У34 У43 У 44 шестнадцать отсчетов одномерного. входного сигнала х; =х (t ) должны поступать на вход в естественном по- 30 рядке хл х 2 Х3р х4 х х6 х 1

Xg Xg X1g X„,, X12, X q3 X 14, х 16 . Так как две приведенные последовательности имеют одинаковое число элементов, то можно говорить 0 соот- 35 ветствии некоторого элемента первой последовательности элементу второй последовательности. Например, элемент у соответствует элементу х7, так как оба они имеют одинаковый поряд- 40 ковый номер.

Запишем с точностью до постоянного множителя явные выражения для

16-ти коэффициентов дискретного одномерного преобразования Хаара входного сигнала х; = х (t; ):

8 1Ь

a -K x.-CȀ

1=1 " 1 9

16 ,1 ;Х.

1"-1

1Ь к « к„-2»; к; =9

4 9 б = Е,х.-,»; а5

50 а4=(х„+х 2) — (х3+ х4)

5 (x<+x<) (7 8) а 6= (х9+х10) (х„„+ х„2) а.,= (хл+х, ) — (х. Ф х1 ) 55 (2) a 12=- х9- х,о

x4 G ь= xqq xq2 60 ад= х) а-= хэал0 — — х 5 а„= х,— а,4= х13- хл4 х13 х 16 хь х9 дискретное о

Hëå преобразова отогональное двумерние Хаара для сигнала 65 е

У; = у ("; q >) определим с точностью до постоянного множителя следующим образом: и hl

С„=СЕ S," Н „(6,, g.), " .1 :1 " последовательность из 4" коэффициентов двумерного дискретного преобразования

Хаара;

)=О

Н (t q)I„- система базисных не.4 -1 нормированных ортогональных трехзначных функций Хаар двух переменных.

Например, для последовательности из ,16-и значений у; входного сигнала (1) двумерное. дискретное преобразование Хаара определяется следующим образом:

4 4 (:0 C - ) (1 j1 ((У11 У12 У21 У2т (У1 3+y14+y23 У24) ) ((Y3„+y32 У41 У42) (У33 У34 У4.3 У44) )

У12 У21 У%2 (У3л У32 У4л У49) ) ((У13 У14 У23 У24) (У33 У34 У43 У 4) ) с 6 ((У1 У12 У21 У22) (y33+y34+y43+y44)

У13 у14 У23 У24 У31 У32 У41 У4 2 с, =(у„+ у„, )-(у+ у ) сУ =(У11 + У21) (УЩ+ У221

c6 =(y„, + У )-(У„2+ У2„) сТ (У13+ y„„) (У23+ y24)

8 =(Y13+ y<3) — (У„+ У ) с9 =(у + y24)-(y + y )

1< У 31 У 32 У41 У42 (4 )

11 — (У „+ У, „) (У32+ y )

1+ y42) (y32+ У4„)

13 У 33 У34 ) (y43 У44)

"4 33 43 34 У44

15 — (Y 33+ У4-4 ) (y43+ У )

Заменяя в выражениях (4) элементы у,. с двухпозиционным индексом соответствующими элементами х; с однопозиционным индексом

„- У„„, х2= У„2, х3 У х4 х16= УМ получим

4Ь Я 1Ь

G =&x„. О„=С, x.-C x1 л=1 ;=9

С х,л Х, — Х.4 Х„

4 (6 Я

Ь l3 l--5 =9

9247 16 с4 =. (х хл)- (х 3 х4) с5=- (м + x),)-(х 1 + х4) с6 (Х + Х4) (Х g + Х )

С7 (х 5+ хЬ) (х i + хц) с = (х 5 + х1) (х 6 + x()) (5) с = (х y + x()) — (х 6 + х ) с(о= (х + х ) — (х + Х1 )

chh= (х g + х+1) — (х (о+ х 1)

С„,1= (х g + х1 ) — (х о+ х1„)

С13 (М4) (15 (Ь) с(4 — (х hq+ х15) (х qg+ х ) с1 (х gq + х ) — (х 14+ х15) °

Сравнивая (2) и (5), убеждаемся, что коэффициенты с... с, С4, с, с „и с „двумерного преобразования соответствуют коэффициентам аб, а1, а, а, а, и а„одномерного преобразования Хаара. Таким образом, поступление на вход предлагаемого устройства отсчетов у„.; в определенном порядке (1) позволяет унифицировать процедуры вычисления коэффициентов

Хаара при одномерном и двумерном преобразовании.

Устройство работает следующим образом.

П1)сть на вход устройства поступают 16 значений одномерного входного сигнала х „. (N = 2, М = 4) . В регистре сдвига 1 первой группы (n = 1) 35 сигнал х„, поступивший в первом такте задерживается на один такт и на сумматор-вычитатель 2„ этой группы во втором такте поступают значения х, и х . На выходах суммы и разности сумматора-вычитателя во втором такте 40 формируются значения х + Х 1 и х „- х, второе из которых является коэффициентом одномерного преобразования Хаара а

В третьем такте на выходах сум- 45 матора-вычитателя 2 „ сформируются значения х +х и х. -х,а в четвеРтом .такте — значения х +х4,и х -х . Значение х - Х4 является коэффициентом а одномерного преобразования Хаара, этот коэффициент может быть считан в конце четвертого такта.

Аналогично работают регистры сдвига 1, 1 и сумматоры-вычитатели 2, 2 первой группы, с той лишь разницей, что регистры сдвига 1 1 и 1 задерживают сигнал на два такта. В результате на четвертом такте работы сформируются три коэффициента, соответствующие двумерному преобразованию Хаара, один из которых является 40 коэффициентом одномерного преобразо вания Хаара: а 4 с 4 (х +х )) (х +х4) с ВыхОди риэ ности блока 2,. 65 на 12-м такте: аь c„î на выходе разности блока 21; на выходе суммы блока 2,) на выходе разности блока 2>,. на 16-м такте: а„= с„ на вЫходе разности блока 2,. с1 на выходе суммы блока 2у с„ на выходе разности блока 2>.

Величина задержки в регистрах последующих групп устанавливается следующим образом: 4 ТВКТоВ в регистh- 1 ре 1, и -й группы; 2 4 тактов — в регистрах 11, 1> п -й группы.

Регистр сдвига 1, второй группы задерживает входной дискретный сигнал на 4 такта, а регистры сдвига

1) и 1 — на 8 тактов. Поэтому на выходе разности сумматора-вычитателя 2„ второй группы на 8 и 16-ом тактах формируются коэффициенты а, а одномерного преобразования Хаара. Йа

16-ом такте блоками второй группы формируются следующие коэффициенты: а = с „ на выходе разности бло1 ка 21; с1 на выходе суммы блока 2 ; с на выходе разности блоЬ

Ка 2, а p — — с на выходе суммы блока 2 .

На этом работа устройства заканчивается.

Работа устройства при N 2 принципиально ничем не отличается от только что рассмотренной. В общем случае с 5= (x„-Х1) + (х -х ) с выхода суммы блока 23 с б= (X <-х ) — (х -x4) с выхода разности блока 2>.

Значение х + х 1+ х 3+ х4 с ВыхоДИ суммы сумматора-вычитателя 2 1 первой группы (n = 1) поступает на вход регистра сдвига 1 „второй группы (n=2) .

Работа во всех блоков первой группы на последующих, вплоть до 16-го такта не отличается от рассмотренной.

На 6,8,10,12,14 и 16-м тактах работы на выходе разности сумматора вычитателя 21 первой группы формируются соответственно коэффициенты а

10 ° а )«a1(L ° a ag ° а ф и а 15одномернОГО преобразования Хаара.

На 8-ом такте блокайн первой группы формируются три коэффициента, соответствующие двумерному преобразованию Хаара, и один коэффициент одномерного преобразования:

a = cz на выходе ра3НосТН блока 21,. с на выходе суммы блока 24: с на выходе разности блока 2>., 924716

1

Aal значения всех 4 коэффициентов двумерного или одномерного преобразоваN ния Хаара вычисляются за 4 тактов работы устройства.

Таким образом предлагаемое устройство способно выполнять дискрЕтное преобразование Хаара либо в одномерной, либо в двумерной области.

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

Устройство для выполнения дискретного преобразования Хаара, содержащее н групп блоков.(4 — число коэфК фициентов двумерного преобразования), каждая из кото1их состоит из трех сумматоров-вычитателей и трех регистров сдвига, причем первый и второй входы -го сумматора-вычитателя -й группы (1--1,2,3, a = 1 - и ) соединены соответственно со входом и выходом -о регистра сдвига и-й группы, вход первого регистра сдвига первой группы является входом устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства, состоящего в возможности выполнения двумерного преобразования Хаара, в нем выходы суммы и разности первого сумматора-вычитателя каждой группы подключены к входам второго и третьего регистров сдвига той же группы, выход суммы второго сумматора-вычитателя -й груп. пы,кроме Й-й группы подключен к входу первого регистра сдвига и +1-й группы, выходы разности первых и вторых сумматоров-вычитателей, выходы суммы и разности третьих сумматоров»вычитателей всех групп, а также выход„. суммы второго сумматора-вычитателя

К-й группы являются выходами устройства.

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

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

Р 484523, кл. G 06 F 15/34) 20.02.74 °

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

Р 620974, кл. G 06 F 5/00,27.05.70. (прототип) .

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

Техред И. ГайдУ Корректор А. Гриценко

Редактор В. Пилипенко

Тираж 732 Подписное

ВНИИПИ Государственного комитета СССР

TIo делам изобретений и oTKphlTHA

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

Заказ 2820/6 7

tè èал ППП Патент, г. Ужгород, ул. Проектная, 4