ГЛАВА 7. Различные ортогональные преобразования

Кроме ДПФ, ПУА с упорядочением по Уолшу и по Адамару и модифицированного ПУА существуют и другие дискретные ортогональные преобразования. Из них в данной главе рассматриваются: обобщенное преобразование, преобразование Хаара, пилообразное преобразование и дискретное косинусное преобразование. Будет показано, что для данной входной последовательности , в качестве обобщенного преобразования , можно определить класс ортогональных преобразований. Преобразование соответствует ПУА с упорядочением по Адамару, соответствует ДПФ. Таким образом, обобщенное преобразование позволяет осуществлять переход от ПУА с упорядочением по Адаь мару к ДПФ.

Исследование преобразования Хаара, пилообразного и дискретного косинусного преобразований оправдывается их применением в системах с сжатием данных, описываемых в гл. 9. Кроме того, в гл. 9 будет рассмотрено преобразование Карунена—Лоэва (КЛП). Причина, по которой обсуждение КЛП несколько отодвигается, заключается в необходимости изложения вспомогательного материала, который будет приведен в гл. 8.

7.1. Факторизация матриц

Основным понятием, связанным с определением обобщенного преобразования, является факторизация матриц, некоторые аспекты которой рассматриваются в данном параграфе. Из определения ДПФ следует, что

(7.1.1)

где —вектор входных данных: - вектор коэффициентов ДПФ и

где .

Пусть и — вектор и матрица, полученные в результате перестановки строк и в соответствии с двоичной инверсией их номеров. Например, если

то

.

Таким образом, в соответствии с (7.1.1) получаем

(7.1.2)

Из решения задачи 4.3 следует, что можно выразить в виде произведения п разреженных матриц, что можно записать как

(7.1.3)

При выражение (7.1.3) принимает вид

где

— единичная матрица размером . Рассмотрение приведенных выше матриц , приводит к выводу, что можно задать следующие четыре ортогональных преобразования:

i) Положим все . Это соответствует ПУА с упорядочением по Адамару, которое обозначим как

(7.1.4)

где - вектор коэффициентов ПУА и . Следовательно, элементы .

ii) Положим и равными 1. Это приводит к комплексному преобразованию Уолша — Адамара или комплексному BIFORE преобразованию [1—3], которое определяется как

(7.1.5)

где — вектор коэффициентов преобразования, — соответствующая матрица преобразования, содержащая элементы .

Положим и равны 1 и получаемые при этом коэффициенты преобразования обозначим через . Соответствующая матрица преобразования содержит элементы , а само преобразование записывается как

Рис. 7.1. Граф, соответствующий формулам (7.1.4) — (7.1.7),

Таблица 7.1.1. Множители для сигнального графа на рис. 7.1

(7.1.6)

iv) Не будем приравнивать ни один из элементов W к 1. При этом получаем преобразование

(7.1.7)

где — вектор коэффициентов преобразования и . Таким образом, связаны с коэффициентами ДПФ операцией двоичной инверсии, т. е.

(7.1.8)

где -десятичное число, полученное в результате двоичной инверсии четырехразрядного двоичного представления .

Граф, соответствующий описанным выше четырем преобразованиям, приведен на рис. 7.1, а соответствующие множители указаны в табл. 7.1.1. За исключением ДПФ, алгоритм, соответствующий графу, изображенному на рис. 7.1, дает коэффициенты преобразования , в естественном порядке.