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

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

Хаара (БПХ), когда размерность входной выборки N К , где k и п любые натуральные числа.

Цель изобретения - упрощение уст ройства.

На фиг. 1 представлена схема устройства (N 3); на фиг. 2 - временные диаграммы, поясняющие его работу; на фиг. 3 - граф вычислеНИИ.

Схема устройства (Фиг, 1) содержит синхронизатор 1 тактируемый, элементы 2 и 3 задержки, сумматорывычитатели 4 и 5, тактируемый элемент 6 задержки, блоки 7-9 сдвиговьгх регистров. .

В предлагаемом примере преобразование состоит из четырех этапов, соответствующих выполнению операций умножения на матрицы R, Rg, R2, R ;Причем на первом этапе выполняетг ся умножение входного вектора f на матрицу на втором - произведение, noJiyiseHHoe на первом этапе и представляющее со.бой матрицу F , умножается на матрицу R и т.д.

Устройство спроектировано так, что конечные результаты преобразования , rpyiniaf-iH получаемые после каждого этапа, хранятся в блоках 7 и 9 до полного окончания всего процесса преобразования, промежуточные же компоненты размещаются в блоке 8, откуда они на вход устройства.

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

Исследуемые дискретные сигналы с каждым тактом последовательно поступают на вход элемента 2 задержки, являющийся также и входом устройства. С приходом второго сигнала и с подачей из синхронизатора 1 на управляющий вход сумматора-вычитателя 5 управляющего сигнала осуществляется переключение входов, вычисление разности первых двух компонентов и ее последующее размещение в блок 7, при предварительной подаче на него сигнала из синхронизатора 1. С приходом третьего сигнала осуществляется переключение

входов сумматора-вычитателя 4, который вычисляет сумму первьк трех компонентов входного сигнала, одновременно осуществляется переключение входов сумматора-вычитателя 5 который вычисляет сумму первых двух компонентов. Полученный на вькоде сумматора-вычитателя 4 результат размещается в блоке 8, а с выхода сумматора-вычитателя 5 в элемент 6 задержки. На следующем такте с приходом четвертого сиг: нала на выходе элемента 2 задержки будем иметь сдвинутый на один разряд влево третий сигнал, что соответствует его умножению на два. В это же время с выхода элемента 6 задержки на вход сумматора-вычитателя 4 поступает задержанная на один такт сумма (f + f2 происходит переключение входов сумматоравычитателя 4 и вычисление разности (fi+ f2 fg 3, которая размещается в блоке 9 при наличии синхронизатора 1 управляющего сигнала. С приходом пятого сигнала переключаются входы сумматора-вычитателя 5, вычисляется разность (f.-fg после чего при наличии управляющего сигнала синхронизатора 1 она размещается в блоке 7. Далее устройство работает аналогичньм образом вплоть до прихода последнего, 81-го компонента входного сигнала. Затем начинается второй этап преобразования, реализующий умножение F,-R-, причем в качестве входных сигналов используются промежуточные результаты преобразования, которые в первом этапе были размещены в блоке 8 и представляют суммы п три компонента исходного сигнала. По сигналу из синхронизатора 1 эти суммы последовательно с каждым тактом поступают на вход устройства. Как на этом, так и в последующих третьем и четвертом этапах устройство работает исключительно так же, как и в первом, при этом входными данными на третьем этапе служат хранимые в блоке 8 суммы компонентов исходного сигнала по девять, которые были вычислены в течение второго этапа, а входными данными н четвертом этапе - суммы компонентов исходного сигнала по 27 полученные в третьем эта пе.

На третьем этапе реализуется умножение FyR, а на четвертом F.R-. После завершения четвертого этапа конечные результаты преобразования будут находиться в блоках 7 и 9, кроме первого коэффициента, который вычисляется в конце четвертого этапа и размещается в блоке 8 Вывод коэффициентов в последователь ности, указанной матрицей преобразования F, обеспечивается расположением выходных шин блоков сдвиговых регистров в нужном порядке.

1871764

На временной диаграмме, поясняющей работу устройства (фиг. 2), через ТИ обозначены непрерывно вырабатываемые входные тактовые имг пульсы, которые следуют с частотой, равной частоте следования входных сигналов. ТИ 1, ТИ 2,...,ТИ 7 разрешающие тактовые импульсы, вырабатываемые на выходных шинах синIQ 1хронизатора 1 (фиг. 1 стрелки а,б, ...,ж). Наличие 1 в строке временной диаграммы означает наличие соответствующего разрешающего сигнала в данный момент времени.

Фиг.2

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХААРА, содержащее синхронизатор, последовательно соединенные первый и второй элементы задержки,первый,второй и третий блоки сдвиговых регистров, первый и второй сумматоры-вычитатели, причем вход первого элемента задержки является информационным входом устройства, отличающееся тем, что, с целью упрощения устройства, оно содержит тактируемый эле- . мент задержки, при этом выход первого элемента задержки подключен к первым входам первого и второго сумматоров-вычитателей, вторые входы которых подключены к выходу второго элемента задержки, выход суммы второго сумматора-вычитателя подключен к входу тактируемого элемента задержки, выход которого подключен к третьему входу первого сумматора-вычитателя, выход разности которого подключен к информационному входу первого блока сдвиговых регистро.в, информационный выход которого подключен к входу первого элемента задержки, четвертому входу первого и третьему входу второго сумматороввычитателей, выходы соответственно суммы первого и разности второго § сумматоров-вычитателёй подключены к информационным входам соответст(Л венно второго и.третьего блоков с сдвиговых регистров, первый, второй, третий, четвертый, пятый, шестой и седьмой выходы синхронизатора подключены соответственно к входам разрешения приема операндов первого и второго сумматоров-вычитателёй, 00 входам разрешения приема информации «-4 второго, первого и третьего блоков ti сдвиговьк регистров и тактовым вхо OS дам тактируемого элемента задержки и первого блока сдвиговых регистров .