Устройство для реализации быстрого преобразования хаара

 

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

СОЮЗ СОЭЕТСНИХ

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

РЕСПУБЛИК

ÄÄSUÄÄ 1187176 уц4 G 06 F 15/332

/l

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ ф

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3681994/24-24 (22) 30.12.83 (46) 23,10.85. Бюл. № 39 (71) Вычислительный центр АН АрмССР и Ереванского государственного университета (72) С.С. Агаян и А.Н. Сукиасян (53) 681.82 (088.8) (56) Авторское свидетельство СССР

¹ 681430, кл. G 06 F 15/332, 1976.

Патент США № 3981443, кл. G 06 F 15/332, 1975. (54)(57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХААРА, содержащее синхронизатор, последовательно соединенные первый и второй элементы задержки, первый, второй и третий блоки сдвиговых регистров, первый и второй сумматоры-вычитатели, причем вход первого элемента задержки является информационным входом устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит тактируемый эле- . мент задержки, при этом выход первого элемента задержки подключен к первым входам первого и второго сумматоров-вычитателей, вторые входы которых подключены к выходу второго элемента задержки, выход суммы второго сумматора-вычитателя подключен к входу тактируемого элемента задержки, выход которого подключен к третьему входу первого сумматора-вычитателя, выход разности которого подключен к информационному входу первого блока сдвиговых регистров, информационный выход которого подключен к входу первого элемента задержки, четвертому входу первого и третьему входу второго сумматороввычитателей, выходы соответственно суммы первого и разности второго сумматоров-вычитателей подключены к информационным входам соответственно второго и.третьего блоков сдвиговых регистров, первый, вто- рой, третий, четвертый, пятый, шестой и седьмой выходы синхронизатора подключены соответственно к входам разрешения приема операндов первого и второго сумматоров- вычитателей, входам разрешения приема информации второго, первого и третьего блоков сдвиговых регистров и тактовым входам тактируемого элемента задержки и первого блока сдвиговых регистров.

»87176

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

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

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

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

В предлагаемом примере преобразование состоит из четырех этапов, соответcтвующих выполнению операций умножения на матрицы 11, Rä, R, R„. Причем на первом этапе выполняет-. ся умножение входного вектора f на матрицу R, на втором — произведение, полученное на первом этапе и 30 представляющее собой матрицу F умножается на матрицу Р.» и T,д, Устройство спроектировано так, что конечные результаты преобразования,группами получаемые после 35 каждого этапа„ хранятся в блоках 7 и 9 до полного окончания всего процесса преобразования, промежуточные же компоненты размещаются в бло— ке 8, откуда они подаются на вход 40 устройства.

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

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

В это же время с выхода элемента 6 задержки на вход сумматора-вычитателя 4 поступает задержанная на один такт сумма (Е,, + f ), происходит переключение входов сумматоравычитателя 4 и вычисление разности t(f„+ f ) — 2f ), которая размещается в блоке 9 при наличии синхронизатора 1 управляющего сигнала. С приходом пятого сигнала переключаются входы сумматора †вычитателя 5, вычисляется разность (Й4-Е ), после чего при наличии управляющего сигнала синхронизатора 1 она размещается в блоке 7. Далее устройство работает аналогичным образом вплоть до прихода последнего, 81-го компонента входного сигнала. Затем начинается второй этап преобразования, реализующий умножение

1" R, причем в качестве входных сигналов используются промежуточные результаты преобразования, которые в первом этапе были размещены в блоке 8 и представляют суммы по три компонента исходного сигнала, По сигналу из синхронизатора 1 эти суммы последовательно с каждым тактом поступают на вход устройства.

Как на этом, так и в последующих третьем и четвертом этапах устройство работает исключительно так же, как и в первом, при этом входными данными на третьем этапе служат хранимые в блоке 8 суммы компонентов исходного сигнала по девять, которые были вычислены в течение второго этапа, а входными данными на четвертом этапе — суммы компонентов исходного сигнала по 27 полученные в третьем эта пе.

1187176

На третьем этапе реализуется умножение F< ° К, а на четвертом—

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

Вывод коэффициентов в последовательности, указанной матрицей преобразования F, обеспечивается расположением выходных шин блоков сдвиговых регистров в нужном поряд-! ке.

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

1 в данный момент времени.

1187176 ае

Сломка уцчита м

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

Редактор Н. Данкулич Техред Ж. Кастелевич Корректор, А Тяско

Заказ 6552/55 Тираж 709 Подписное

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

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

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