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

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

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

рого подключен к входу дешифратора, выход которого подключен к первому входу j-го (., п-1) ключа, второй вход которого подключен к выходу 1-го одновибратора, вход которого подключен к выходу {.l + i)-ro делителя частоты, выход i-ro (, (1-1) ключа является (i+1)-M выходом первой группы блока синхронизации, выход :i-ro (i 1,n -1) делителя частоты является 1-м выходом второй группы блока синхронизации, выход (-n-D-ro одновибратора является Г1-М выходом второй группы блока синхронизации, выход дешифратора является первым выходом первой группы блока синхронизации, выходы генератора тактовых импульсов и элемента задержки являются соответственно первым и вторым выходами блока синхронизации, вход запуска генератора тактовых импульсов которого является входом блока синхронизации, а вход элемента задержки подключен к выходу я-го делителя частоты.

1. УСТРОЙСТВО ДЛЯ ОРТОГОНАЛЬНОГО ПРЕОБРАЗОВАНИЯ ЦИФРОВЫХ СИГНАЛОВ ПО ФУНКЦШМ ХААРА, содержащее П вычислительных блоков, блок синхронизации, первую и вторую группы регистров сдвига, отличающее-с я тем, что, с целью упрощения устройства и расширения области его применения за счет обработки входных последовательностей длиной N К(где 1с, И - любые натуральные числа) отсчетов , оно содержитп переключателей и узел задержки, причем i-й (,n ) вычислительный блок содержит 2

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

Известны,устройства, содержащие регистры сдвига, группы элементов И, группы сумматоров, цифровой генератор, аналого-цифровой преобразователь, блок управления и группы регисров числа и вычисляющие восьмиточечное преобразование по функциям Хаара т.е. производящие БПХ над входными выборками, составленными из восьми значений СОи 2.

Эти устройства содержат много элементов, сложны и позволяютпроизводить БПХ только в случаях, когда объем входной выборки .

Наиболее близким к предлагаемому является устройство, содержащее соединенные последовательно модули единичного преобразования по основанию два, каждый из которых содержит по два регистра сдвига, арифметический блок, имеющий два входа, причем каждый вход соединен с единственным выходом одного из двух соединеннь1к по входам регистров сдвига. Арифметический блок имеет суммирующий и вычитающий выходы, причем первый из них соединен с двумя регистрами сдвига последующего модуля, а на втором выходе арифметического блока каждого модуля появляютсякоэффициенты преобразования. Для упорядочения вычисленных коэффициентов и преобразования их в последовательный поток устройство содержит г группу регистров, каждый из которых подсоединен к одному из модулей. Работу всего устройства синхронизирует блок управления, состоящий из Счетчика и матрицы постоянного запоминающего устройства З J.. .

Однако при использовании такого устройства могут возникнуть затруднения в том, что выбор размера входной выборки ограничен лишь- числами, равными степеням двойки, и нет возможности перехода к более высоким -основаниям, тогда как такой переход приводит к сокращению числа модулей преобразования, повышению параллелиз ма обработки в каждом из них и упрощению устройства. Кроме того, сложна реализация арифметических блоков, так как они одновременно должны вычислять две суммы. Цель изобретения - упрощение устройства и расширение области примене ния за счет обработки входных последовательностей длиной (где k,n любые натуральные числа) отсчетов. Указанная цель достигается тем, что устройство для ортогонального преобразования цифровых сигналов по функциям Хаара, содержащее п вычислительных блоков, блок синхронизации первую и вторую группы регистров сдвига, содержит п переюпючателей и узел задержки, причем i-й (,n) вы числительный блок содержит 2(ic.-1) элементов задержки, коммутатор и сум матор, выход j-ro (j 1,2k-3) элемен та задержки подключен к входу (j+1)го элемента задержки и (j+1)-My информационному входу коммутатора, ()-й информационный вход которого подключен к выходу 2(jc-1)-ro элемента задержки, j-й (J--1 ,k) информационный выход коммутатора подключен к j-му входу сумматора, первый инфор мационный вход коммутатора и вход первого элемента задержки первого вычислительного блока объединены и являются информационным входом уст.ройства, выход сумматора i-ro (, h-1) вычислительного блока подключен к информационному входу i-ro переклю чателя, первый информационный выход которого подключен к входу первого элемента задержки и первому информационному входу коммутатора (i+1)-ro вычислительного блока, выход суммато ра вычислительного блока подклк чен к входу узла задержки, выход которого подключен к первому информационному входу п-го переключателя, информационный выход которого являет ся информационным выходом устройства при этом первая и -вторая группы регистров сдвига содержат п-1 подгруп по (k-1) последовательно соединенных регистров сдвига в i-й (i 1,п-1) подгруппе, информационный выхо j-ro I 1, (k-1 Ж) регистра сдвига 1-й(, г-1) подгруппы первой группы подключен к информационному входу j-ro регистра сдвига i-й подгруппы второй группы,информационный выход (k-1) регистра сдвига i-й (i 1,n-2) подгруппы второй группы подключен к информационному входу первого регистра сдвига (У+1)-й подгруппы второй группы, а информационный выход (i-l)V-ro регистра сдвига (h-1)-и подгруппы второй группы подключен к второму информационному входу п-го ,переключателя, второй информацион ный выход i-ro (, п-1) переключа- , теля подключен к информационному входу первого регистра сдвига -й подгруппы.первой группы,при этом i-й (,ri) вькод первой группы блока синхронизации подключен к управляющему, входу коммутатора i-ro вычислительного блока, i-й выход второй группы блока синхронизации подключен к управляющему входу -го переключателя, первый и второй выходы блока синхронизации - соответственно к тактовым входам и входам, разрешения записи регистров сдви.га второй группы, а вход блока синхронизации является входом запуска устройства. При этом блок синхронизации содержит п-1 ключей, п-1 одновибраторов, п последовательно соединенных делителей частоты, элемент задержки, с.четчик, дешифратор и генератор тактовых импульсов, выход которого подключен к входу первого делителя частоты и счетному входу счетчика, информационный выход которого подключен к. входу дешифратора, выход которого подключен к первому входу -го (,h -1) ключа, второй вход которого подключен к выходу i-ro одновибратора, вход которого подключен к выходу (.1+1)-го делителя частоты, выход 1-го (i 1, h-1) ключа является (i+1)-M выходом первой группы блока синхронизации, выход i-ro (i 1, ri-1) делителя частоты является i-м выходом второй группы блока синхронизации, выход (n-l)-ro одновибратора является п-м выходом второй группы синхронизации, выход дешифраTopa, является первым выходом первой группы блока синхронизации,иыходы генератора тактовых импульсов и элемента задержки являются соответственно первым и вторым выходами блока синхро- низацйи, вход запуска генератора та товых импульсов которого является входом блока синхронизации, а вход элемента задержки подключен к выход И-го делителя частоты. Устройство рассчитано на естественный порядок входных данных, результаты вычислений также получаютс в естественном порядке, т.е. упоряд ченные по строкам матрицы Хаара. В соответствии с используемым ал горитмом над входной выборкой данны представляемой вектором размера N производится преобразование F fH,(1 где F - полученное преобразова ние; -матрица Хаара. Построение БПХ (быстрого преобра зования Хаара) входными массива ми размера основано на методе построения ортогональных матриц Хаара порядка Пусть А , - квадратная k-k матри ца, удовлетворяющая условиям (здесь Т - знак траспонирования матоиц) 31. . Ч к-Vi . где е - вектор-строка из k единиц; АЛ - матрица, составленная из последних k-1 строк матрицы , Ол - вектор-строка из k нулей. Для , , k-4 Aj будет иметь . 1 1 -1 -1 О О V2 (4) единичная матрица порядка k единичная .матрица порядка а R, и матрицы вида 0|с1-1 ,, 4-Jci-,®Ai где® - кронекерово произведение. Тогда H(,...(7) является матрицей Хаара порядка }, а преобразование (1) представляется ...R , , . (8) Выходной массив на этапе преобразования обозначим векторомf.( элементный вектор), представляюпщм собой произведение г RnRn-i;--Rn.i-(Mt.iH Заметим, что (f п п-у n-n-(i-i)) вектор, получаемый на (1-1)-м этапе преобразования, тогда на 1-м этапе f/.,.,Rn.-,.. . 10) и на п-м этапе, т.е. на выходе всего устройства (ц) Таким образом, преобразование на каядом 1-м этапе (,n) сводится к умножению входного вектора -, данного этапа на матрицуR, определенную по формуле (6), где для i-го этапа ) + 1-1. Умножение вектора f . на матрицу ( производится следующим образом. Первые Т. элементы вектора f делятся на k групп по k элементов в каждой. Каждая групда элементов умножается на матрицу А, (умножение на матрицу сводится к сложению, так как используются матрицы А., строки которых с точностью до постоянного нормировочного коэффициента состоят из ±1 и О, а умножение на два сводится к сдвигу.влево на один разряд). Первый элемент, получаемый при умножении первой группы входного вектора на первую строку матрицы А (первой строкой матрицы А является вектор-строка из k единиц), является первым элементомвыходного вектора. Последующие 1с-1 элементы, получаемые при умножении первой группы входного вектора на оставшиеся k-1 строки матрицы А. (т.е. на матрицу Aj) , являются элементами выходного вектора fj i-ro этапа с номерами с по . Первый элемент, получаемый при умножении второй группы входного вектора на первую строку матрицы А является вторым элементом выходного вектора. Последукицие 1с-1 элементы, получаемые при умножении второй группы входного вектора на оставшиеся строки матрицы А,являются элементами выходного ветора f i-ro эта па с номерами с k -fk+l по и т.д. Для вычислений на каждом I-M этапе испольэуются первые элемен ты входногс вектора f-, остальные элементы этого вектора являются конечным результатом преобразования и в дальнейших вычислениях не участвуют. На фиг.1 представлена блок-схема предлагаемого устройства; на фиг.2 и 3 - соответственно схемы арифметического узла и коммутатора арифметического узла; на фиг. 4 - схема блока синхронизации; на фиг. 5 и 6 временные диаграммы работы блока син хронизации; на фиг. 7 и 8 - графы последовательности вычислений БПХ пр и соответственно. Устройство для ортогонального пре образования входной выборки цифровых сигналов порядка N по функциям Хаара имеет информационный вход 1 (фиг. 1), содержит вычислительные блоки (преобразования по функциям Хаара по основанию 1), переключатели 3ц-3, две группы регистров и . сдвига, предназна 1 П-1 ченньк для упорядочения вычисленных коэффициентов преобразования по стро кам матрицы Хаара, узел 6 задержки, блок 7 синхронизации, осуществляющий синхронизацию работы всех блоков уст ройства. Каждый вычислительный блок содержит по 2 (1.-1) соединенных последова тельно элементов 8.,-82(.1 задержки, арифметический узел 9. Выход п-го переключателя 3,, явля ется информационным выходом 10 устройства. Управляющие входы арифметических узлов 11--1. и переключателей подключены к соответствующим выходам блока 7 .синхронизации. Тактовые входы и выходы 13 и 14 разрешения записи второй группы регистров сдвига подключены к соответствующим выходам блока 7 синхронизации. Арифметический узел 9 каждого вычислительного блока содержит сумматор 15, имеющий k информационных вхо дов, и коммутатор 16, имеющий 2 информационных входов и k выходов. подключенных к информационным входам сумматора 15 (фиг. 2). Управляющий вход 111 (, 2,..., n) арифметического узла подключен к управляющему входу коммутатора 16. На фиг.2 показан также выход 17 арифметического узла. Сумматор 15 вычисляет сумму k tftiсел. Поступающих параллельно на его информационные входы. Коммутатор 16 на каждый такт подключает к своим k выходам k из 2k-1 своих информационных входов следующим образом. На первый такт к выходам подключаются информационные входы с первого по k-й включительно, на второй - с второго по (k+1)-й, на третий такт с третьего по (k+2)-й,..., на k-й с k-ro по (2k-1)-й. Нафиг. 3 приведена одна из возможных реализаций коммутатора 16, где изображены информационные входы и выходы , коммутаTopa 16, который содержит также одинаковых переключателей 19.,19-jj, каждьй из которых имеет V информационных входов и один выход. Входы (с первого по k-й) переключателя 19 соединены с входами блока 16 с первого по k-й соответственно. Входы переключателя 192 соединены с входами блока 16 с второго по ()--й, т.е. первый, второй,..., V-й входы каждого i-ro переключателя 19 соединены соответственно с входами блока 16 с i-ro по (i+k-1)-й. Входы последнего переключателя 19 соединены с входами блока 16 с по ()-и. Выходы переключателей 19 -19:| соедивыходами 18 нены соответственно с 18 блока 16. Синхронизирующие входы переключателей соединены параллельно с синхронизирующим входом блока 16, который представляет собой шину из k параллельных линий, куда поступает многофазный тактовый сигнал от блока синхронизации, На фиг. 4 представлена схема бло ка 7 синхронизации устройства для ортогонального преобразования выбор, ки цифровых сигналов порядка . Блок синхронизации содержит генератор 20 тактовых импульсов, счетчик 21, дешифратор 22,ш делителей частоты на 1;, один элемент 24 задержки на lir-1 тактов, и-1 одновибг ратор 25, -25о., и п-1 ключей 26. -26г,.,, Генератор 20 тактовых импульсов синхронизируется с частотой дискрети зации по времени поступающих на вход устройства цифровых сигналов от аналого-цифрового преобразователя. Выход генератора тактовых импульсов соединен с входом счетчика 21, входом первого делителя 23, частоты на , выход счетчика 21 подключен к входу дешифратора 22, выход которого подключен к первому выходу 11 перво группы блока синхронизации и через i-й ключ 26,- (, п-1) - к (1+1)-му выходу первой группы блока. Выход первого делителя 23 частоты подключен к входу второго делителя 23 частоты и выходу 12 блока синхронизации. Выход каждого i-ro (, n-1) делителя 23 частоты соединен с входом последующего делителя частоты 23;j. и с выходом 12 второй группы блока синхронизации. Выход последнего делителя 23 f, частоты подключен к выходу 12, блока синхронизации через одновйбратор 25, . , расширяющий входной импульс длительностью Т/2 до (т.е. в раз). Помимо этого, выходы делителей 232- через одновибраторы 25 25,- подключены к управляющим входа ключей ,j , а выход одновибратора 25 подключен к управляющему входу ключа 26 .„. Выход п-го делите ля 23 подключен к элементу 24 задержки, выход которого подключен к выходу 14 блока синхронизации. На вход тактового гене.ратора 20 поступают синхроимпульсы от аналогоцифрового преобразователя. На выходе образуются тактовые импульсы (ТИ) с периодом повторения Т и длительностью Т/2. Эти ТИ поступают на выход 13 блока синхронизации. С частотой ТИ коэффициенты преобразования, поступившие в регистры 5-,, сдвига втррой группы (фиг. 1).последовательно передаются на выход 10 всего устройства через второй информацион ный вход переключателя 3,. ТИ от генератора 20 поступают та же на входы делителя 23 и счетчика 21. Каждый из делителей частоты делит частоту входного сигнала на 1 , т.е. на выход каждого из этих делителей поступают импульсы длительностью Т/2 (т.е. равной длительности ТИ и периодом, вk раз большим периода входного сигнала каждого из делителей . Каждый из одновибраторов ,-,, расширяет длительность входного импульса Т/2 в k раз, т.е. до величины k-T/2 (фиг. 6, здесь 1,2 - соответственно входной и выходной импульсы одновибратора 25). Импульсы, поступающие с выходов делителей ,„ на выходы .2ij второй группы и с выхода делителя 23,т, через одновйбратор 25..,- на выход 12;р второй группы, управляют работой переключателей Зг)-3 и 3;, соответственно (фиг. 1). Переключате-i ли в отсутствие синхронизирующего импульса подключены на нижние по схеме положения (фиг. 1), а на время появления управляющего импульса переключаются - на верхние. Выход последнего делителя подключен к входу элемента 24 задержки, выход которого подключен квыходу 14 блока синхронизации. Импульсы, поступающие на этот выход, являются стробирующими, разрешающими поступление коэффициентов Хаара из регистров . сдвига первой группы в регистры 5,,-5,„ сдвига второй группы. Счетчик 21 является двоичным по модулю k (от О до k-1), считает поступающие на его вход ТИ. Выходы счетчика соединены с дешифратором 22 наk выходов. Счетчик 21 и дешифратор 22 распределяют входную последовательность тактовых импульсов на k выход ных линий, образуя многофазный (или точнее k-фазный) тактовый сигнал (фиг.5, здесь ТИ - тактовые импульсы на входе счетчика 21, и 1, 2, 3,... k - импульсы на выходах дешифратора). Этот сигнал упр-авляет работой коммутатора 16 (фиг. 2). Выход дешифратора представляет собой шину на It параллельных линий (показаны одной линией, фиг. 4). Импульсы с выхода дешифратора 22 поступают на выход 11 блока синхронизации и через , на выходы соответственно. Каждый ;1-й ключ 26 (J 1,.. ., ь-1) пропускает на свой выход сигнал с выхода дешифратора при наличии на своем управляющем входе импульса, поступающего от V-ro одновибратора 27j. В качестве ключей 26,-26 можно использовать элементы И. Рассмотрим работу устройства, на примере устройства для ортогонально го преобразования входной выборки порядка N 27. С частотой тактовых импульсов на вход первого вычислительного блока поступают отсчеты дискретного сигнала. На третий такт на входе блока и на первом входе арифметического узла появляется третий отсчет а,. В это время второй отсчет а будет на выхо де первого элемента задержки и на втором входе арифметического узла, а первый отсчет а., - на выходе второго элемента задержки и на третьем входе арифметического узла. На этот такт арифметический блок вычисляет сумму отсчетов, поступающих на пе вый, второй и третий входы арифметического узла, что соответствует первой строке А На четвертый такт на вход вычисли тельного блока поступает четвертый отсчет, а на выходах первого, второго и третьего элементов задержки и на втором, третьем и четвертом входах арифметического узла появляются третий, второй и первый отсчеты соот ветственно. На этот такт арифметичес кий узел вычисляет сумму, соответствующую второй строке матрицы Aj. На пятый такт на вход вычислитель ного блока поступает пятый отсчет, четвертый поступает на выход первого элемента задержки, а третий, второй и первьш отсчеты поступают на третий четвертый и пятый входы арифметического узла соответственно. На этот такт арифметический узел вычисляет сумму, соответствующую третьей строке матрицы А-. На этом преобразование по основанию три первых трех отсчетов заканчивается. Первый из трехfвычисленных результатов через переключатель, включенный на третьем такте на первый выход, поступает на второй вычис лительный блок для последующих вычис лений. На четвертый и пятый такты переключатель 3 включен на второй выход, и второй и третий вычисленные результаты, являющиеся десятым и одиннадцатым коэффициентами Хаара, поступают на вход.регистра 4 сдвига первой группы. Следующие три такта, начиная с шестого, первый вы шслительный блок производит преобразование по основанию три следующих трех входных отсче тов (четвертого, пятого и шестого) и т.д. На двадцать седьмой такт на вход первого блока 2 поступает двадцать седьмой отсчет. Арифметический узел вычисляет сумму , которая через переключатель 3 поступает на вход второго блока 2 . Последующие, два такта на вход первого блока 2 поступают первые два отсчета следующей выборки, состоящей из двадцати семи отсчетов, а арифметический узел блока 2 вычисляет последние два коэффициента Хаара предыдущей выборки - двадцать шестой и двадцать седьмой. Через переключатель 3 они поступают на вход группы регистров 4. сдвига. На следующий такт арифметический узел вычисляет первую сумму трехточечного преобразования от первых трех отсчетов второй выборки. К этому времени блок 4 уже полностью заполнен коэффициентами Хаара с десятого по двадцать седьмой (блок 4 состоит из восемнадцати регистров) . Поэтому на этот такт из блока 7 синхронизации подается стробирующий импульс на вход 14 второй группы регистров сдвига, разрешающий поступление коэффициентов Хаара из блока 4 в блок 5. Таким образом, регистры 4 сдвига готовы, начиная со следующего такта, принимать коэффициенты преобразования Хаара второй выборки отсчетов. Второй и третий вычислительные блоки работают аналогичным образом. С поступлением третьего отсчета на вход второго блока 2у арифметический узел вычисляет первую сумму трехточечного преобразования, последующие два такта - вторую и третью суммы трехточечного преобразования. Через шесть тактов, когда на вход второго вычислительного блока поступают следующие три отсчета, работа блока преобразования повторяется и т.д. На вход 14 второй группы регистров сдвига подается стробирующий импульс тогда, когда полностью заполнены регистры 4 и 4, сдвига первой группы, на вход 13 подается тактовая частота, с которой коэффициенты преобразования, поступившие в регистры 5 и 5, сдвига второй группы, последовательно передаются на второй инфор ма191онный вход переключателя 3}, который подключает к выходу свой первый информационный вход в течение первых трех тактов после того, как на вход устройства поступил двадцать седьмой отсчет, и через него на выход 10 устройства .поступают первые три коэффициента Хаара. Следующие двадцать четыре такта переключатель Зл .подключает к выходу второй информационный вход, и через него на выход 10 устройства поступают осталь ные двадцать четьфе коэффициента Хаа pa. Таким образом, устройство вычисля ет коэффициенты ортогонального преоб разования цифровых сигналов по функциям Хаара непрерывно, т.е. на вход устройства последовательно поступают отсчеты, а на вькоде устройства с задержкой в N тактов с частотой так товых импульсов появляются коэффициенты преобразования, При сравнении примера выполнения данного устройства для (т.е. при ) с прототипом видно, что устрой,ство упрощено, поскольку арифметичес кие узлы в блоках преобразования содержат один сумматор и вычисляют каждый раз или сумму, или разность двух цифровых отсчетов, а арифметические блоки базового объекта должны вычислять каждьй раз одновременно и сумму и разность двух чисел, т.е. содержат в cg6e фактически два сумматора . Особенно существенным это преимущество становится при применении уст ройства для обработки больших порядков N. Например, для наиболее употре 111 14 бительного значения предлагаемое устройство содержит 2065 сдвиговых регистров и десять арифметических узлов, включающих в себя десять сумматоров, а известное устройство для того же N используют 2068 сдвиговых регистров и десять арифметических блоков, содержащих двадцать сумматоров. За счет такого сокращения числа сумматоров (в 2 раза) предлагаемое устройство значительно проще прототипа и имеет меньшие габариты, вес и потребляемую мощность питания, что очень важно при его использовании в бортовых радиотехнических системах летательных аппаратов. Кроме того, предлагаемое устройство осуществляет БПХ для порядков , когда k - натуральное число. Это расширяет область применения устройства для различных задач, так как оно реализует быстрое преобразование по системам функций, которые являются полными базисами в пространстве размерности 2WT сигналов, ограниченных по полосе частотой W и по длительности интервалом Т, для широкого класса размерностей 2WT и, в частнос1ти, для пространств размерностью 2. , Кроме того, при в устройстве при том же порядке N и общем объеме оборудования сокращается число блоков преобразования, что приводит к упрощению блока синхронизации и повышению надехсности устройства.

ZH-I

16

фиг. г

Фаг.З

/7

15

/5 /A

Фс/а. 4

|ЖЯ.-.Д

:Ln

фиг. 5

о J

t

р

Фае. 6

at. а,

Ог a, азооая arrepai i/

5 CTf-az

Фи8. 7

азоёал операция

ai - dz ue. 8