Процессор для преобразования цифровых сигналов по хааро- подобным базисам

 

1. ПРОЦЕССОР ДЛЯ ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХ СИГНАЛОВ ПО ХААРОПОДОБНЫМ БАЗИСАМ, содержащий п вычислительных блоков, блок синхронизации , первую и вторую группы регистров сдвига и П переключателей, отличающийся тем, что, с целью повышения точности и расширения области применения путем обработки входных последовательностей длиной N k,.|c2. .. ц ( - любые натуральные числа, д- 1,и) отсчетов, 1-й (i 1,и) вычислительный блок содержит 2(k;-1) элементов задержки, коммутатор, k умножителей, k узлов памяти и сумматор, выход j-го (j 1 , 2k;-3) элемента задержки подключен к входу (j+1)-ro элемента задержки и ()+1)-му информационному входу коммутатора,

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

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

РЕСПУБЛИК

„„SU, Ä 1168966

is>> G 06 Г 15/332

4, ОПИСАНИЕ ИЗОБРЕТЕНИЯ /! .ч

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3701246/24-24 (22) 13.02.84 (46) 23.07.85. Бюл. N - 27 (/2) К,A. Абгарян, С.С. Агаян и А.В. Мелкумян (71) Вычислительный центр АН Армянской ССР (53) 681.32(088.8) (56) Авторское свидетельство СССР

Мр 744598, кл. G 06 F 15/332, 1980.

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

1i) 1116435, кл. С 06 F 15/332, 1983. (54)(57) 1. ПРОЦЕССОР ДЛЯ ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХ СИГНАЛОВ ПО ХААРОПОДОБНЫМ БАЗИСАМ, содержащий и вычислительных блоков, блок синхронизации, первую и вторую группы регистров сдвига и >1 переключателей, о т— л и ч а ю шийся тем, чro, с целью повышения точности и расширения области применения путем обработки входных последовательностей длиной N = k, >(... k> (где, — любые натуральные числа, = 1,и ) отсчетов, 1

>-й (1 = 1,>)) вычислительный блок содержит 2(k; 1 ) элементов задержки, коммутатор, k умножителей, k узлов памяти и сумматор, выход 1-го (1, 2k; -3) элемента задержки подключен к входу (j +1)-го элемента .задержки и (}+1)-му информационному входу коммутатора, (2k; -1)-й информационный вход которого подключен к выходу 2(L;-1)-го элемента задержки, ) -й (j-1,k ) информационный выход коммутатора подключен к первому информационному входу j -го умножителя, t информационный выход 1.-ro узла памяти подключен к информационному входу

1-ro узла памяти и к второму информационному входу > -ro умножителя, выход которого подключен к j -му входу сумматора, первый информационный вход коммутатора и вход первого элемента задержки первого рычислительного блока объединены и являются информационным входом процессора, выход сумматора > -ro (1 =1, » -1) вычислительного блока подключен к информационному входу i -го переключателя ° первый информационный выход которого подключен к входу первого элемента задержки и первому информационному входу коммутатора (i +1)-ro вычислительного блока, выход сумматора >> -го вычислительного блока подключен к первому информационному входу >>--го переключателя, информационный выход которого является информационным выходом процессора, при этом первая и вторая группы регистров сдвига содержат (>>-1) подгрупп по (k, -1) ° ki ..., "n последовательно соединенных регистров сдвига в q -й () =1, » -1) подгруппе, информационный выход 1 -го ()=1, (1„ — 1) i« .... >(>) > регистра сдвига

1-й (i =1, n — 1) подгруппы первой груп. пы подключен к информационному входу ( -го регистра сдвига.1 -й подгруппы второй группы, информационный выход ((k; -1) k;„.... k )-го регистра сдвига (-й (t=l, n --2) подгруппы второй группы подключен к информационному входу первого регистра сдвига (l+1)-й подгруппы второй группы, а информационный выход ((„-1) k„ )-го регистра сдвига (» — 1) — и подгруппы второй группы подключен к второму информационному. входу » -го переключателя, второй информационный выход

i-го (=1, tt — 1) переключателя под11б8966 ключен к информационному входу пер1 вого регистра сдвига « -й подгруппы, первой группы, при этом « -й (« =1,п) выход первой группы блока синхронизации подключен к управляющим входам

1 узлов памяти и коммутатора « -ro вычислительного блока, «-й выход второй группы блока синхронизации подключен к управляющему входу « -ro переключателя, первый и второй выходы блока синхронизации подключены соответственно к тактовым входам и входам разрешения записи регистров сдвига второй группы„ а вход блока синхронизации является входом запуска процессора.

2. Процессор по п.1, о т л и— ч а ю шийся тем, что блок синхронизации содержит (««-1) ключей, (««-1) одновибраторов, «« последовательно соединенных делителей частоты, элемент задержки и генератор тактоИзобретение относится к вычислительной технике и .радиотехнике и может быть использовано в цифровых . I системах связи для построения устройств сжатия данных, цифровой фильт- 5 рации, обработки иэображений, в системах обрабоТки радиолокационных сигналов, основанных на алгоритме быстрого ортбгонального преобразования но. Хааро-подобным базисам, 1Î когда объем входной выборки М

k tq ° . k««, где « - любьи натураль.. ные числа, Цель изобретения - повьппение точ- . ности вычислений и расширение области применения путем обработки вход ных последовательностей. длиной (rye lc, — любые натуральные числа, « = 1,««) отсчетов.

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

В соответствии с используемым алгоритмом над входной выборкой данных, представляемой вектором Е развых импульсов, выход которого подключен к входу первого делителя частоты и к первому входу «-го (« = 1, и-1) ключа, второй вход которого подключен к выходу « -ro одновибратора, вход которого подключен к выходу (« +1)-ro делителя частоты, выход « -го ключа («=1, и -1) является («+1)-м выходом второй группы блока синхронизации, выход (««-1)-го одновибратора является ««-м выходом второй группы блока синхронизации, выход генератора тактовых импульсов является первым выходом первой группы и первым выходом блока синхронизации, выход элемента задержки является вторым выходом блока синхронизации, вход запуска генератора тактовых импульсов является входом блока синхронизации, а вход элемента задержки подключен к выходу и --го делителя частоты. мера N производится следующее преобразование:

F = Е Н,. (1) где F — полученное:преобразование;

Н-NxN — матрица преобразования.

Быстрое ортогональное преобразование над входными массивами размера N = k1 k< ..., Кя основано на .рекуррентном построении Хааро-подобных матриц порядка N = k,k ...,k

Пусть А (i=1,n) — квадратная

« k матр ца, удовлетворя щая усло. виям где Т вЂ” знак транспортирования матриц, 1, — вектор-строка из k;

1 единиц, А „ — матрица, составленная с из последних (k; -1) строк матрицы

А«,1, О«,; - вектор-строка из k; нулей °

Условиям (2) удовлетворяют матрицы косинусного преобразования,матрицы Фурье, матрицы дискретного линейного базиса и матрицы Хаара, когда — любое натуральное число; матрицы Уолша и матрицы наклонного

3 1168966 преобразования (slant-преобразования) когда k; = 2t, t — любое натуральное число; матрицы Адамара, когда

4, — любое натуральное число

В качестве примера приведены несколько таких матриц: а) .Уолша, k; = 2 (- ) !

О б) Хаара, k = 3

1 1 1 (1 1 -2) (1/2) (1 -1 О) (3/2) в) Хаара, k; = 4

1 1 1 1

1 1 -1 -1 (1 -! О О) г" (О О -1 -1) 2

r) slant, k; = 4

1 1 1 1 (3 1 — 1 -3) (1/5) п2

1 — 1 -1 1 (1 -3 3 — 1 ) (1/5) д) дискретного линейного базиса -. 2S (ДЛБ), k< = 5 являе.ся ортогональной Хааре-подобной матрицей порядка N = k, ...k <, а преобразование (1) представляется следующим образом:

Выходной массив на i-м этапе преобразования o6osначим вектором

f;(N = k,... k > ) — элементный век-!

5 тор, представляющий собой произведение (8) 2

2О Тогда (Е К, К ...Ri,) — вектор, получаемый на (i-1)-м этапе преобразования, а (9) f =f ° R ! 1t 1

Таким образом, преобразование на каждом i-м (i=1,n) этапе сводится к умножению вектора f<,на матрицу R .i определенную по формуле (4).

Умножение вектора fi.,на матрицу R производится следующим образом.

1 1 1 (2 1 Π— 1 (1 0 -2 0

-1 2 О -2 (2 -3 2 -3 е) Фурье, kI = 3

-2) ) 1/2)

1) (5/6)

1) (1/2)

2) (1/7) Первые k k;, ...k „ N(i) элементы вектора f, m;.

N(i) групп по 1,; элементов каждой

k, Каждая группа элементов умножается на матрицу А, . Первый элемент, по1 лучаемый при умножении первой группы. входного вектора на первую строку матрицы А„, является первым элек 1 ментом выходного вектора. Последую щие (k -1) элементы, получаемые при умножении первой группы выходного вектора на оставшиеся (Е;-1) строки

I матрицы А„., т.е. на матрицу А

1 1 являются элементами выходного векто"

1 1 1

1 W W

1 W W . ж) косинусного

k =М

Л

W=exp

35 преобразования, 00 0 0 (о а« ор j ш=О ь М 1 4О (2m+1)kx

="!2 cos k=1 Ì-1 аMo aklf ащ

Пусть также ца порядка m, N

N(i) — П 1с, m, матрицы .-. ида

Тщ — единичная матриц

1 1 1 2 .П !сс р 45 аК,, R, èÊ ра f; i-ro этапа с номерами с (m,+1) по (m, +k;-1) .,Oi

I< ®AI, (3) Первый элемент, получаемый при умножении второй группы входного вектора на первую строку матрицы А к является вторым элементом выходного, вектора f; Последующие (ki 1) элементы, получаемые при умножении вто- рой группы входного вектора на оставшиеся (k -1) строки матрицы А„,, яв1 ляются элементами выходного вектора

1 . 0 1„; 0 m; 1 . ЭА„. О н-и(!

1 (4) О и (0" 1,„ {5) где ® — кронекерово произведение.

Тогда

Н и = R(R R (6) F = f ° R„R,. ° . R„. (7) 1168966

f; i-ro этапа с номерами с (m;+k;) по -(ш;+2k;-2) и т.д.

Для вычислений на каждом i-м этапе испсльзуются первые N(i) элементы входного вектора f„, остальные эле менты этого вектора являются конечным результатом преобразования и в дальнейших вычислениях не участвуют.

На фиг, 1 представлена блок-схема процессора дця преобразования циф ровых сигналов по Хааро-подобным базисам; на фиг. 2 и 3 — соответственно схемы коммутатора и блока синхронизации; на фиг. 4 — временные диаграммы работы блока синхронизации, Процессор имеет информационный вход 1, содержит вычислительные блоки 21- 2„, переключатели 3 — Зп, две групны 41- 4 и 5<- 5„,регистров сдвига, предназначенных для упоря-. дочения вычислительных коэффициентов по строкам матрицы преобразования, блок 6 синхронизации, осуществляющий синхронизацию работы всех блоков устройства. Как,дый вычисли-.. тельный блок содержит по 2 (k;. — 1) соединенных последовательно элементов 7„ - 7< задержки, коммутатор 8, 26ц.

k; умножителей 9 — 9»., kI узлов

10, — 10, памяти и сумматор 11. Управ

Ъ ляющий вход вычислительного блока соединен с управляющими входами узлов 10; — 10„„ памяти и коммутатора

8, Выход переключателя 3 является информационным выходом 12 процессора. Узел 10j (j=1, k, ) памяти предназначен для хранения (в виде двоичных кодов) элементов 1-го столбца матрицы A и содержит в себе К; сое1 диненных йоследовательио регистров сдвига. Информационный выход узла

10j памяти соединен с информационным входом узла 10> памяти и вторым информационным входом j-ro умножители 9 .Управляющие входы вычисли1 тельных блоков 13, — 13„и переключателей 14, — 14„, тактовые входы 15 и входы 16 разрешения записи второй группы регистров сдвига подключены к соответствующим выходам блока 6 синхронизации. Коммутатор 8 на каждый такт подключает к своим k; выходам k; из (21с, -1) своих. информационных входов следующим образом.

На первый такт к выходам подключаются информационные входы с первого по k -й BKBIOBHTPJIbHo на ВТороН второго по (k +1) é, ..., на 1с, -й .такт подключаются входы с k-.ro no (21т, -1) -й.

5, На фиг. 2 приведена одна из возможных реализаций коммутатора 8, 1 где 17 — 17 — информационные входы

2(п;. )

Э а 18, — 18; - выходы коммутатора 8, который содержит 1<, одинаковых пере1О ключателей 19, — 19„,, каждый из которых имеет К; информационных входов ,и один выход. Входы (с первого по

k ° -й) переключателя 19 соединены с входами блока 8 с первого no k é

1 соответственно. Входы переключателя

192 соединены с входами блока 8 с второго пд (k, +1)-й ... . Входы последнего k -ro переключателя 19, соединены с входами блока 8 с k -ro

2О по (2k; -1) -й с Выходы переключателей

19, — 19 ° соединены соответственно

1 с выходами 18» — 18 . блока 8. Синхро1 низирующие входы переключателей

19 - 19» объединены и являются управляющим входом коммутатора 8.

На фиг. 3 представлена схема блока 6 синхронизации, которая содержит генератор 20 тактовых импульсов, . n делителей 21 — 21„ частоты, один элемент 22 задержки на (k 1) тактов, (n-1) одновибраторов 23 — 23„,и (n-1) ключей 24 — 24„;.

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

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

4п 21 частоты,.с первыми информационными входами ключей 24 - 24 с выхода{ 6.11 ми 13, и 15 блока синхронизации.Выходы ключей 24»- 24„,являются выходами 13 - 13„ блока синхронизации.

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

21 частоты и выходу 14 блока синхронияадии. Выход делителя частоты

21 (i=2, л-1) соединен с входом

50 последующего делителя 21 и с вы-!

+! ходом 14, блока синхронизации. Выход делителя 2 1„ частоты подключен к выходу 14ц блока синхронизации через одновйбратор 23„ . Помимо этого выход делителя 21, (=2, п-1) через одновибратор 23; соединен с вторым входом ключа 24;.„ а выход одновибратора 23„,- с вторым входом

1168966 ключа 24 . Выход делителя 21 сое6- 1 » динен с входом элемента 22 задержки, выход которого соединен с выходом

16 блока синхронизации.

Генератор 20 выдает тактовые импульсы (ТИ) с периодом повторений Т и длительностью Т/2. Делитель частоты 21; (iox1, и) делит частоту входного сигнала на k, т.е. »а его выход поступают импульсы длительностью, равной длительности ТИ, и периодом в k раз большим периода вхолноСо сигнала ° Оиновивратор 23 (i=1, и-1) расширяет длительность входного импульса Т/2 в 2k раз. т .е. тат до величины 1с Т . Ключ 2 4 (i = 1, ted»

1 п-1) пропускает на выход сигнал со своего первого входа при наличии на втором входе импульса, поступающего от одновибратора 23 ° . В каче-. а стве ключей 24 — 24 можно исполь1 1 зовать элементы И.

На фиг. 4 представлены диаграммы работы блока синхронизации.

На диаграмме 1 представлены тактовые импульсы, поступающие с выхода генератора 20 на вход делителя 21»частоты, первые входы ключей 24 — 24 и на выходы 13 и 15

1 и-1. 1 блок а си нхр он из ации.

На диаграммых 2 и 3 представлены импульсы на выходах 141 и 14 блока синхронизации соответствейно, а на диаграммах 4 и 5 — импульсы на выходах одновибратора 23 и клю1 ча 241 соответственно.

Процессор работает следующим образом.

С частотой тактовых импульсов на вход первого вычислительного блока поступают отсчеты дискретного сигнала. На k é такт на входе блока и на первом входе коммутатора появляется k» é отсчет S,,на выходе первого элемента задержки и на втором входе коммутатора (1 -1)-й

1 отсчет $ „..., а на выходе (k — 1)-го

1 элемента задержки 7„1 и íà k -м

К -1 входе коммутатора — первый отсчет

S,, Ha этот такт к информационным выходам коммутатора 8 подключены его первые k1 информационные входы, на вторые входы умножителей поступают ,элементы первой строки матрицы

А „(а,, — а, „) с выходов узлов 10,!

10„памяти, а на первые входы умноК1 жителей — отсчеты S — S с выходов коммутатора. В результате на выход сумматора первого вычислительного

Ка блока и. с-:óïèò сумма," а; S .

) =!

Н" (k +1) такт на информационный

1 вход первого вычислительного блока поступает (k +1)-й отсчет, а на информационные входы коммутатора с второго по (k1+1)-й, с выходов элемен1Î тов задержки с первого »»o k< -й соответственно отсчеты S — $1. На

k1 этот такт к информационным выходам коммутатора подключены его информационные входы с второго по (k»+1)-й, 15 на первые входы умножителей поступают отсчеты S»-S „,с выходов коммутатора, а на вторые входы умножите— лей элементы второй строки матрицы

А (а,-а „) выходов уз.пов 101 в 10к

2О памяти. Сумматор вычисляет сумму параллельно поступающих íà его информационные входы произведений к1 -аг,"$, тj т

На (2к; — 1)-й такт первый вычис1 к, лительный блок выдает сумму + а „S

1 )

На этом преобразование по основанию

30 k, первых k, отсчетов (S S„ ) заканчивается. Первый из k1 вычисленных результатов через переключатель 3,, включенный на k, -м такте на первый выход, поступает на второй вычислительный блок для последующих вычислений. На остальные (k -1) такты

t переключатель 3 включен на второй

1 выход и остальные (k -1) вычислен1 ные результаты, являющиеся коэффи4и циентами преобразования по Хаароподобному базису с номерами (m +i)

1 по (m1+k1 — 1), поступают на вход регистров 4 сдвига первой группы.

Следующие k1 тактов, начиная с

45 (2k )-го, первый вычислительный блок производит преобразование по основанию k, следующих k, входных отсчетов (S1, „- $г„) и т д.

На N-й такт на вход первого вы5О числительного блока поступает N-й отсчет. Блок 21 вычисляет сумму к, а< $„„, которая через пере-"»5 ключатель 31 поступает на вход второго вычислительного блока 2г. Последующие (k»-1) такты на вход блока

2 1 поступают первые (К 1 — 1) отсчеты следующей выборки, составленной из

1168966

N отсчетов, а сумматор блока 2 вычисляет последние (k -1) коэффициенты преобразования предыдущей выборки с (N-k +2)-ro no N-й, которые через переключатель 3 поступают на вход группы 4 регистров сдвига, На следующий такт блок 21 вычисляет первую сумму преобразования от первых отсчетов второй выборки. К этому времени блок 4 уже полностью эапол- 10 нен коэффициентами преобразования с (mt+1) по N-й. Поэтому на этот такт из блока синхронизации подается стробирующий импульс на вход

16 второй группы регистров сдвига, 15 разрешающий поступление коэффициентов преобразования из блока 4 в блок 5 .

Таким образом, регистры сдвига группы 41 готовы, начиная со следующего такта, принимать коэффициенты 20 преобразования второй выборки отсчетов

Пос,едующие вычислительные блоки 2 — 2 работают аналогичным образом.

На вход 16 второй группы регистров сдвига подается стробирующий импульс тогда, когда полностью эаполнеиы регистры сдвига первой группы 4, — 4,, а на вход 15 подается тактовая частота, с которой коэффициенты преобразования, поступивгие в регистры сдвига второй группы

5(— 5,, последовательно передаются и-1 н а второй информационный вход переключат еля 3 < . Переключатель 3 подключ ает к выходу свой первый инфо рмационный вход в течение первых k т акт ов после того, к ак н а вход устр ой ств а поступит М-й отсчет, и через него н а выход 1 2 процессора поступают первые k < коэффициенты пр е обра з ов ания . Следующие (N-kÄ ) такты пер еключ атель 3 „ подключает к выходу второй информационный вход и через него н а выход устройства поступают остал ь ные (N — k ) ко зффициен ты пр еобразования .

1168966

11689бб

1 I 68966

Фиа0

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

Техред Т.Фанта Корректор E. Рощко

Редактор А. Козориз

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

Заказ 4616/44 Тирам 710 Подписное

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

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