Процессор для преобразования цифровых сигналов по Хааро-подобным базисам Советский патент 1985 года по МПК G06F17/14 

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

2. Процессор по п.1, о т л и чающийся теМ| что блок синхронизации содержит (п-1) ключей, (И-1) рдновибраторов, f последовательно соединенных делителей частоты элемент задержки и генератор тактовых импульсов, выход которого подключен к входу первого делителя частоты и к первому входу i-ro ( i 1, n-1) ключа, второй вход которого подключен к выходу i-ro одновибратора, вход которого подключен к выходу ( -t-l)-го делителя частоты, выход 1-го ключа (i 1, ri-1) является (i+1)-M выходом второй группы блока синхронизации, выход (п-1)-го одновибратора является П-м выходом второй группы блока синхронизации, выход генератора тактовых импульсов является первым выходом первой группы и первым выходом блока синхронизации, выход элемента задержки является вторым выходом блок синхронизации, вход запуска генератора тактовых импульсов является входом блока синхронизации, а вход элемента задержки подключен к выходу п-го делителя частоты.

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

Изобретение относится к вы4исли.тельной технике и радиотехнике и может быть использовано в цифровых системах связи для построения устройств сжатия данных, цифровой фильт рации, обработки изображений, в системах oбpaбotки радиолокационных сигналов, основанных на алгоритме быстрого ортЬгонального преобразования по Хааро-подобным базисам, когда объем входной выборки N k, kj. .. 1(ц , - любые натураль ные числа, i 1,р. Цель изобретения - повышение точности вычислений и расширение области применения путем обработки вход-г ньгх последовательностей длиной ,,k2. ... п (где Ц- любые нату ральные числа, i 1,h) отсчетов. Процессор рассчитан на естественныА порядок входных данных, результаты вычислений также получаются в естественном порядке, т.е. упорядоченные по строкам матрицы ортогонального преобразования. В соответствии с используемым алгоритмом над входной выборкой данных, представляемой вектором f рззмера N, производится следующее преобразование: F f Н, . где F - полученное преобразование; H-NxN - матрица преобразования. Быстрое ортогональное преобразование над входными массивами размеосновано на .рекуррентном построении Хааро-подобных матриц порядка N .k2... ,kj.. Пусть Ац,() - квадратная матрица, удовлетворяющая уело.,; ,., 2) где Т - знак транспортирования матриц, 1.- вектор-строка из k единиц, А - матрица, составленная из пбследних (k; -1) строк матрицы Aj(j , 0)с, - вектор-строка из k, нулей, Условиям (2) удовлетворяют матрицы косинусного преобразования,матрицы Фурье, матрицы дискретного линейного базиса и матрицы Хаара, когда k, - любое натуральное число; матрицы Уолша и матрицы наклонного 3 . 11689 преобразования (з1ап1-преобразования) когда k 2t, t - любое натуральное число; матрицы Адамара, когда k; 4t, t - любое натуральное число. в качестве примера приведены несколько таких матриц: а) .Уолша, k; 2

где ® - кронекерово произведение.

(7)

R,

R;R,

F f

Выходной массив на i-м этапе преобраз.ования обозначим вектором f(,. ..kj,) - элементный вектор, представляющий собой произведение

(8)

f- f R/ R,

R

n

Тогда (f« . . ,) - вектор, получаемый на (i-l)-M этапе преобразования, а

(9)

R:

i-1

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

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

Первые kj k,-. ..k N(i). элементы вектора f делятся на mj

-г- групп по k элементов каждой

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

Первый элемент, получаемый при умножении второй группы входного вектора на первую строку матрицы А,, является вторым элементом выходного вектора f|. Последующие (k;-1) элементы, получаемые при умножении второй группы входного вектора на оставшиеся () строки матрицы А., являются элементами выходного вектора 66 Тогда Н являе.ся ортогональной Хааре-подобной матрицей порядка N k,...kfl, а преобразование (1) представляется следунхцим образом:

fj i-го этапа с номерами с (mv+k;) по -{mj -2k;-2) и т.д.

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

На фиг. 1 представлена блок-схема процессора доя прео0разования цифровых сигналов по Хааро-подобным базисам; на фиг. 2 и.3 - соответственно схемы коммутатора и блока синхронизации; на фит. 4 - временные диаграммы работы блока синхронизации.

Процессор имеет информационный вход 1, содержит вычислительные блоки 2,- 2, переключатели 3, две группы 4 и 5,- 5 регистров сдвига, предназначенных для упорядочения вычислительных коэффициентов по строкам матрицы преобразования, блок 6 синхронизации, осуществляющий синхронизацию работы всех блоков устройства. вычисли-.: тельный блок содержит по 2 (Ц-1) соединенных последовательно элементов 7 - 7( . задержки, коммутатор 8, k, умножителей 9,- 9(f., kj узлов 10,- 10-1 памяти и сумматор 11. Управляющий вход вычислительного блока соединен с управлякщими входами узлов 10;- 10ijj памяти и коммутатора 8. Выход переключателя 3 является информационным выходом 12 процессора. Узел lOj (, ) памяти предназначен для хранения (в виде двоичных кодов) элементов j-ro столбца матрицы А . и содержит в себе k, соединенных последовательно регистров сдвига. Информационньй выход узла 1OJ памяти соединен с информационным входом узла 10j памяти и вторым информационньм входом j-ro умножителя 9, . Управлягадие входы вычислительных блоков 13,- 13jj и переключателей 14,- 14, тактовые входы 15 и входы 16 разрешения записи второй группы, регистров сдвига подключены к. соответствующим выходам блока 6 синхронизации. Коммутатор 8 на каждый такт подключает к своим k,- выходам k, из () своих информационных входов следующим образом. На первый такт к выходам подключаются информационные входы с первого по включительно, на второй - с

второго по (k +1)-й, ..., на k,-и .такт подключаются входы с krro по (2kJ-1)-й.

5 ,На фиг. 2 приведена одна из воз-можных реализаций коммутатора 8, ,где 17|- 17. - информационные входы а 18,- 18. -выходы коммутатора 8, который содержит k| одинаковых переключателей 19,- 19,, каждый из которых имеет k информационных входов .,и один выход. Входы (с первого по

k-й) переключателя 19( соединены

с входами блока 8 с первого по kj-и

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

19

2 соединены с входами блока 8 с

второго пб ( ... . Входы последнего kj-го переключателя 19ц; соединены с входами блока 8 с k--ro по (2kj-1)-й Выходы переключателей 19,- 19|j. соединены соответственно с выходами 18,- 18. блока 8. Синхронизирукмцие входы переключателей 19k объединены и являются управляющим входом KOMi- атора 8.

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

Генератор 20 тактовых импульсов синхронизируется с частотой дискретизации по времени поступающих на вход процессора цифровых сигналов от аналого-цифрового преобразователя. Выход генератора тактовых импульсов соединен с входом первого делителя 21 частоты,.с первыми информационными входами ключей 24j- 24, с выходами 13, и 15 блока синхронизации.Выходы ключей 241-24. являются выходами I3j- 13 блока синхронизации.

Выход первого делителя 21 частоты подключен к входу второго делителя 21J частоты и выходу 14 блока синхронизации. Выход делителя частоты 21. (, п-1) соединен с входом 0 последующего делителя 21 и с выходом 14, блока синхронизации. Выход делителя 21„ частоты подключен к выходу 14 блока синхронизации через одновибратор Помимо этого выход делителя 21; (, п-1)

через одновибратор 23 соединен с вторым входом ключа 24,-.,, а выход одновибратора 23.- с вторым входом

ключа 24

Выход делителя 21

динен с входом элемента 22 задержки выход которого соединен с выходом 16 блока синхронизации.

Генератор 20 выдает тактовые импульсы (ТИ) с периодом повторений Т и длительност ю Т/2. Делитель частоты 21j ( n) делит частоту входного сигнала на k , т.е. на его выход поступают импульсы длительностью, равной длительности ТИ, и периодом в k раз большим периода входного сигнала. Одновибратор 23 (, п-1) расширяет длительность входного импульса Т/2 в 2k. раз. т .е до величины k Т. Ключ 2Д- (, п-1) пропускает на выход сигнал со своего первого входа при наличии на втором входе импульса, поступающего от одновибратора 23.. В качестве ключей 24,- 24 можно испольI п-1

зевать элементы И.

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

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

13, и 15

на выходы блока синхронизации..

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

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

С частотой тактовых импульсов на вход первого вычислительного блока поступают отсчеты дискретного сигнала. На k,-й такт на входе блок

«

и на пэрвом входе коммутатора появляется k,-й отсчет S, , на выходе первого элемента задержки и на втором входе коммутатора (k.-l)-A

а на выходе (k-l)-ro

отсчет Si

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

,r

с выходов узлов

ц памяти, а на первые входы умноS|f с выходов

жителей - отсчеты S, Т€

коммутатора. В результате на выход

сумматора первого вычислительного

V.

блока поступит сумма 21 а S.

5 Нг (k -1) такт на информационный

вход первого вычислительного блока поступает (k )-й отсчет, а на информационные входы коммутатора с второго по (kj+1)-A, с выходов элементов задержки с первого по k, -и

соответственно отсчеты S | - S. На этот такт к информационным выходам коммутатора подключены его информационные входы с второго по ()-й,

5 на первые входы ум(ожителей поступают отсчеты S,-S,c выходов коммутатора, а на вторые входы умножителей элементы второй строки матрицы А(а , выходов узлов 10,- 10,

0 памяти. Сумматор вычисляет сумму параллельно поступающих на его информационные входы произведений 1

7

v, 3

g- J

На ()-й такт первый вычисI к, .

лительный блок выдает сумму Г а ,-S-. I .

I0 -

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

0 k, первых k) отсчетов (S,-S) заканчивается. Первьй из kj вычисленных результатов через переключатель 3, , включенньй на k, -м такте на первый выход, поступает на второй вычислительный блок для последующих вычислений. На остальные (k,-1) такты переключатель 3 включен на второй выход и остальные (k.-1) вычисленные результаты, являющиеся коэффициентами преобразования по Хаароподобному базису с номерами (т,+1) по (ra,+k,-1), поступают на вход регистров 4 сдвига первой группы. Следующие k, тактов, начиная с

5 (2k,)-ro, первый вычислительный блок производит преобразование по основанию k,следующих k входных

отсчетов (S - Sj) и т.д.

На N-й такт на вход первого выНислительного блока поступает N-й

0 отсчет. Блок 2 вычисляет сумму

tf

которая через пере -MJключатель 3

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

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

Таким образом, регистры сдвига группы 4( готовы, начиная со следующего такта, принимать коэффициенты преобразования второй выборки отсчетов ПoCJ.iДyющиe вычислительные блоки 2 - 2 работают аналогичным образом.

На вход 16 второй группы регистров сдвига подается стробирующий импульс-тогда, когда полностью заполне}й 1 регистры сдвига первой группы 4j - 4, а на вход 15 подается тактовая частота, с которой коэффициенты преобразования, поступивгие в регистры сдвига второй группы 5,- 5, последовательно передаются на второй информационньй вход переключателя 3.. Переключатель 3 подключает к выходу свой первьй информационный вход в течение первых k тактов после того, как на вход устройства поступит N-й отсчет, и через него на выход 12 процессора поступают первые k коэффициенты преобразования. Следующие (N-k) такты переключатель 3 подключает к выходу второй информационный вход и через него на выход устройства поступают остальные (N-k) коэффициенты преобразования.

Фаг.З

Фиг. 2 ГИТшт JETl fL КгК2-Т.

Хг-Г

t F

5+

ляп

flii e.

я,

ллл . rLJLTLJl,, я.