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

11 б 8966 ключен к информационному входу пер 1вого регистра сдвига-й подгруппы,первой группы, при этом-й ( =1,п)выходпервой группы блока синхронизации подключен к управляющим входам1узлов памяти и коммутатора-го выФчислительного блока, -й выход второй группы блока синхронизации подключен к управляющему входу-гопереключателя, первый и второй выхо.ды блока синхронизации подключенысоответственно к тактовым входам ивходам разрешения записи регистровсдвига второй группы а вход блокасинхронизации является входом запуска процессора,2. Процессор по п.1, о т л и -ч а ю щ и й с я тем, что блок .синхронизации содержит (О) ключей,(-1) одновибраторов,последовательно соединенных делителей частоты,элемент задержки и генератор тактоИзобретение относится к вычисли.тельной технике и радиотехнике и может быть использовано в цифровых, системах связи для построения устройств сжатия данных, цифровой фильт 5 рации, обработки иэображений, в системах обработки радиолокационных сигналов, основанных на алгоритме быстрого ортбгонального преобразования но. Хааро-подобным базисам, 1 О когда объем входной выборки М1,, 1 с, где с - любые натуральные числа,Цель изобретения - повьппение точ- . ности вычислений и расширение облас ти применения путем обработки вход ных последовательностей. длиной М= 1,с . с (где 1; - любые натуральные числа,= ,) отсчетов.Процессор рассчитан на естествен 20 ный порядок входных данных, результаты вычислений также получаются в естесгвенном порядке, т.е. Упоря-. доченные по строкам матрицы ортогонального преобразования.В соответствии с используемым алгоритмом над входной выборкой данных, представляемой вектором Г раэвых импульсов, выход которого подключен к входу первого делителя частоты и к первому входу -го (= 1,и) ключа, второй вход которогоподключен к выходу-го одновибратора, вход которого подключен квыходу ( +1)-го делителя частоты,выход-го ключа (=1, и -1) является (+1)-м выходом второй группыблока синхронизации, выход (-1)-гоодновибратора является -м выходомвторой группы блока синхронизации,выход генератора тактовых импульсовявляется первым выходом первойгруппы и первым выходом блокасинхронизации, выход элемента задержки является вторым выходом блокасинхронизации, вход запуска генератора тактовых импульсов являетсявходом блока синхронизации, а входэлемента задержки подключен к выходу п -го делителя частоты. мера И, производится следующеепреобразование: Р = ЕфН,. (1) где Р - полученное преобразование; Н-г 1 хг 1 - матрица преобразования.Быстрое ортогональное преобразование над входными массивами размера И = 1 с 1 1 с , 1 с, основано на .рекуррентном построении Хааро-подобных матриц порядка Х = 1 с,1 с ,1 с.Пусть А,(1=1,п) - квадратнаяматрица, удовлетворяющая усло виям где Т - знак транспортирования матриц, 1, - вектор-строка из 1 с;единиц, А - матрица, составленная иэ последних Ос; -1) строк матрицы А , Ок; - вектор-строка из Е; нулейУсловиям (2) удовлетворяют матрицы косинусного преобразования,матрицы Фурье, матрицы дискретного линейного базиса и матрицы Хаара, когда- любое натуральное число; матрицы Уолша и матрицы наклонногоявляе.ся ортогональной Хааре-подобной матрицей порядка Н = с,Е и,а преобразование (1) представляетсяследующим образом: Выходной массив на к-м этапе преобразования обозначим векторомЕ;(Ы = с, с) - элементный век тор, представляющий собой произведе- ние(9) Г =Г К Таким образом, преобразование накаждом к-м (к=1,п) этапе сводится кумножению вектора Г,на матрицу Копределенную по формуле (4).Умножение вектора Е.,на матрицу Кпроизводится следующим образом. 1 1 1-2) ) 1/2) 1) (5/6) 1) (1/2) 2) (1/7) Первые 1 с 1 с;,1 с, М(д) элементы вектора Г, делятся на ш;.Ю)групп по с; элементов каждойс,Каждая группа элементов умножается на матрицу А . Первый элемент, получаемый при умножении первой группы. входного вектора на первую строку матрицы Ак, является первым элекментом выходного вектора. Последующие (с -1) элементы, получаемые при умножении первой группы выходного вектора на оставшиеся (1 с;-1) строкиматрицы А т.е. на матрицу А1являются элементами выходного векто" ра Г; -го этапа с номерами с (ш,+1) по (ш, +кс,-1). 1 1 1 1 М Н 1 Р Уж) косинусного 1 с = М1 2 3 Ъ 7=ехр 35 преобразования,ОО О 0адав а,.а,Пусть такжеа порядка ш,;иКч 1 кАв, 11 Первый элемент, получумножении второй группы ввектора на первую строкуявляется вторым элементомвектора Е;, Последующие (менты, получаемые при умнрой группы входного нектошиеся Ь, "1) строки матрляются элементами выходно аемый приходногоматрицы Авыходно го, с, -1) элеожении вто-ра на оставицы А явго вектора О 1; О(5 де ронекерово произве 3 1168966 преобразования (з 1 апС-преобразования) когда Е; = 2, Т - любое натуральное число; матрицы Адамара, когда4 С, 1 - любое натуральное числоВ качестве примера приведены несколько таких матриц: а) .Уолша, 1 с; = 2,-,10 б) Хаара, 1 с; = 31 1 1 (1 1 -2) (1/2) (1 -1 О) (3/2) в) Хаара, 1 с; = 4 1 1 1 1 1 1 -1 -1 (1 -1 О О) г" (О О -1 -1) 2 г) з 1 апй, 1 с; = 41 1 1 1 (3 1 - 1 -3) (1/5)1 - 1 -1 1(1 -3 3 -1) (1/5)д) дискретного линейного базиса - 25 (ДЛВ), с = 5 1, ш=О, М40К; 1-го этапа с номерами с (в;+К;) по .(ш; +21, -2) и т.д.Для вычислений на каждом 1-м этапе используются первые Б(1) элементы входного вектора Г.1, остальные эле менты этого вектора являются конечным результатом преобразования и в дальнейших вычислениях не участвуют.На фиг, 1 представлена блок-схема процессора дця преобразования циф ровых сигналов по Хааро-подобным базисам; на фиг. 2 и 3 - соответственно схемы коммутатора и блока синхронизации; на фиг. 4 - временные диаграммы работы блока синхронизации,Процессор имеет информационный вход 1, содержит вычислительные блоки 21" 2, переключатели 3- Зп, две групны 41- 4 и 5 В,регистров сдвига, предназначенных для упоря-. дочения вычислительных коэффициентов по строкам матрицы преобразования, блок 6 синхронизации, осуществляющий синхронизацию работы всех блоков устройства. Каждый вычисли- тельныйблок содержит по 2 ;.-1) соединенных последовательно элементов 7 - 7 задержки, коммутатор 8,г(.э1 с 1 умножителей 9 - 9 1 с узлов 10, - 10, памяти и сумматор 11. УправЪляющий вход вычислительного блока соединен с управляющими входами узлов 10; - 10 памяти и коммутатора 8, Выход переключателя 3 является информационным выходом 12 процессора. Узел 101 (1=1, 1 с) памяти предназначен для хранения (в виде двоичных кодов) элементов 1-го столбца матрицы А.и содержит в себе К; соединенных йоследовательио регистров сдвига. Информационный выход узла 101 памяти соединен с информационным входом узла 10 памяти и вторым информационным входом 1-го умножитела 9 .Управляющие входы вычислительных блоков 13, - 13 и переключателей 14, - 14, тактовые входы 15 и входы 16 разрешения записи второй группы. регистров сдвига подключены к соответствующим выходам блока 6синхронизации. Коммутатор 8 на каждый такт подключает к своим 1; выходам 1 с 1 из (21 с;"1) своих. информационных входов следующим образом. На первый такт к выходам подключаются информационные входы с первого по 1,-й включительно, на второй - с второго по (1 с +1)-й, , на 1 с, -й(21 т,1 -1) -й.5 , На фиг. 2 приведена одна из возможных реализаций коммутатора 8,где 171 - 17 - информационные входыгь;Ва 18, - 18; -выходы коммутатора 8,который содержит 1,1 одинаковых пере О ключателей 19, - 19 каждый из которых имеет К; информационных входов,и один выход. Входы (с первого поК -й) переключателя 191 соединеныс входами блока 8 с первого по 1-йсоответственно. Входы переключателя192 соединены с входами блока 8 свторого пд" +1)-йВходы последнего 1 с -го переключателя 19,соединены с входами блока 8 с Е -го 2 О по (21;-1)-йс Выходы переключателей19, - 19 соединены соответственно1с выходами 18 - 18 блока 8. Синхронизирующие входы переключателей 2519, - 19 объединены и являютсяуправляющим входом коммутатора 8.На фиг, 3 представлена схема блока 6 синхронизации, которая содержит генератор 20 тактовых импульсов,(а) одновибраторов 23 - 23,и (и)ключей 24 - 24.;.Генератор 20 тактовых импульсовсинхрониэируется с частотой дискре тиэации по времени поступающих навход процессора цифровых сигналов отаналого-цифрового преобразователя.Выход генератора тактовых импульсовсоединен с входом первого делителя 40 21 частоты,.с первыми информационными входами ключей 24 - 24 с выхода 11 1 Вми 13, и 15 блока синхронизации.Выходы ключей 24- 24,являются выходами 13" 13 блока синхронизации.45 Выход первого делителя 21 частотыподключен к входу второго делителя21 частоты и выходу 14 блока синхронияадии. Выход делителя частоты21 (12, л) соединен с входом 50 последующего делителя 21 и с вы+ходом 14, блока синхронизации. Выход делителя 2 1 частоты подключенк выходу 14 ц блока синхронизациичерез одновйбратор 23, Помимо этого выход делителя 21, (=2, п)через одновибратор 23; соединен свторым входом ключа 24;. а выхододновибратора 23,- с вторым входомключа 24 . Выход делителя 21 соединен с входом элемента 22 задержки,выход которого соединен с выходом16 блока синхронизации.Генератор 20 выдает тактовые импульсы (ТИ) с периодом повторений Ти длительностью Т/2. Делитель частоты 21; (1=1, и) делит частотувходного сигнала на 1 в т.е. на еговыход поступают импульсы длительностью, равной длительности ТИ, ипериодом в 1 раз большим периодавнонноросигнала Олновибратор 23(2.=1, и) расширяет длительностьвходного импульса Т/2 в 21, раз. т.е.111до величины 1 с Т . Ключ 2 4 ( 1 = 1 ,11и) пропускает на выход сигнал сосвоего первого входа при наличиина втором входе импульса, поступающего от одновибратора 23. В каче-.стве ключей 24 - 24 можно использовать элементы И.На фиг, 4 представлены диаграммы работы блока синхронизации.На диаграмме 1 представленытактовые импульсы, поступающие свыхода генератора 20 на вход делителя 212 частоты , первые входы ключей 24 - 24 и на выходы 13 и 151 и 1блока синхронизации,На диаграммых 2 и 3 представлены импульсы на выходах 14 и 14блока синхронизации соответствейно,а на диаграммах 4 и 5 - импульсына выходах одновибратора 23 и клю 1ча 24 соответственно.Процессор работает следующимобразом.С частотой тактовых импульсовна вход первого вычислительногоблока поступают отсчеты дискретногосигнала. На Е,-й такт на входе блокаи на первом входе коммутатора появляется 1-й отсчет Б , на выходепервого элемента задержки и навтором входе коммутатора Ь -1)-йотсчет Бв, а на выходе Ь -1)-гоэлемента задержки 7 1 и на Е -мк -1входе коммутатора - первый отсчетБ,. На этот такт к информационнымвыходам коммутатора 8 подключены егопервые К 1 информационные входы, навторые входы умножителей поступают,элементы первой строки матрицыАк (а - а, ) с выходов узлов 10 г -О памяти, а на первые входы умноН 1жителей - отсчеты Б, - Б, с выходовкоммутатора. В результате на выход сумматора первого вычислительногок(блока п.ступит сумма,". ;1 Я ,1)а5 Нг (к +1) такт на информационныйвход первого вычислительного блокапоступает Й,+1)-й отсчет, а на информационные входы коммутатора с вто.рого по Ь +1)-й, с выходов элемен 1 О тов задержки с первого по Е -йсоответственно отсчеты Б - Б 1. Накэтот такт к информационным выходамкоммутатора подключены его информационные входы с второго по +1)-йв15 на первые входы умножителей поступают отсчеты Б 1-Б ,с выходов коммутатора, а на вторые входы умножите -лей элементы второй строки матрицыА(а ,-а ) выходов узлов 101 в 10,20 памяти. Сумматор вычисляет суммупараллельно поступающих на его информационные входы произведенийк-аг Б,25На (21; - 1)-й такт первый вычислительный блок выдает суммуаБ11На этом преобразование по основаниюЗО 1 с первых 1 с, отсчетов (Я,-Б ) заканчивается, Первый из 11 вычисленныхрезультатов через переключатель 3включенный на 1, -м такте на первыйвыход, поступает на второй вычислительный блок для последующих вычислений. На остальные Ь -1) тактыпереключатель 3 включен на второй1выход и остальные-1) вычисленные результаты, являющиеся коэффи 40 циентами преобразования по Хаароподобному базису с номерами (ш +1)по (в+1,-1)р поступают на вход регистров 4 сдвига первой группы.(Следующие 1 тактов, начиная с45 (21 с)-го, первый вычислительныйблок производит преобразованиепо основанию Е, следующих 1, входныхотсчетов (Бк - Бг) и т.д.На И-й такт на вход первого вы 50 числительного блока поступает И-йотсчет, Блок 21 вычисляет суммука Б, которая через пере 1 к 1ключатель 3 поступает на вход второго вычислительного блока 2 г. Последующие Ьг) такты на вход блока2, поступают первые- 1) отсчетыследующей выборки, составленной изЯ отсчетов, а сумматор блока 2 вычисляет последние Ь - 1) коэффициенты преобразования предыдущей выборки с (Б+2)-го по И-й, которые через переключатель 3 поступают на вход группы 4 регистров сдвига, На следующий такт блок 21 вычисляет первую сумму преобразования от первыхотсчетов второй выборки. К этому времени блок 4 уже полностью эапол О нен коэффициентами преобразования с (ш+1) по Ч-й. Поэтому на этот такт из блока синхронизации подается стробирующий импульс на вход 16 второй группы регистров сдвига, 15 разрешающий поступление коэффициентов преобразования из блока 4 в блок 5,Таким образом, регистры сдвига группы 41 готовы, начиная со следующего такта, принимать коэффициенты 20 преобразования второй выборки отсчетов Пос,едующие вычислительные блоки 2 - 2 работают аналогичным образом. На вход 16 второй группы регистров сдвига подается стробирующий импульс тогда, когда полностью эаполнеиы регистры сдвига первой группы 4, - 4 а на вход 15 подается тактовая частота, с которой коэффициенты преобразования, поступивгие в регистры сдвига второй группы 5 - 5 последовательно передаютсян.1н а второй информационный вход переключат еля З.я . Переключатель 3подключ ает к выходу свой первый инфо рмационный вход в течение первых Ет акт ов после того , к ак н а вход устр ой ст . в а поступит М-й отсчет , и через него н а выход 1 2 процессора поступают первые 1 с 1 коэффициенты пр е обра з ов ания . Следующие ( Б-Е ) такты пер еключ атель 3подключает к выходу второй информационный вход и через него н а выход устройства поступают остал ь ные (М - 1 ) коэффициенты пр еобразования .1168966 Саста Техре тель А. Т,Фанта нов Коррек Е. Рошко Козо Редактор раз 710Под венного комитета СССР етений и открытий 35, Раушская наб., д. Т сно 5 илиал ППП "Патент", г. каз 4616/44 ВНИИП п 11303И Государ делам изо Москва, Ж город, ул. Проектная, 4