7.4. Алгоритмы для вычисления преобразования Хаара (ПХ)

Для осуществления преобразования Хаара требуется операций и N операций умножения, что показано на рис. 7.2а для . Этот алгоритм вычисления преобразования Хаара был предложен Эндрюсом [9].

Соответственно алгоритм для вычисления обратного преобразования Хаара изображен в виде графа на рис. 7.2б. Из рис. 7.2 видно, что алгоритм Эндрюса не является алгоритмом типа Кули — Тьюки [10]. Ниже будет показано, что преобразование Хаара можно осуществить и с помощью алгоритма типа Кули — Тьюки.

Рис. 7.2. Граф прямого и обратного преобразования Хаара, соответствующий алгоритму Эндрюса, : a — прямое преобразование; б — обратное преобразование

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

Алгоритм типа Кули — Тьюки [8, 31]. Этот алгоритм может быть наилучшим образом продемонстрирован при . Запишем снова матрицу Хаара из (7.3.2)

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

Шаг 1. Переставим столбцы в соответствии с двоичной инверсией номеров столбцов при , т. е. , что приведет к

Шаг. 2. Переставим столбцы матриц, заключенных в квадраты, в соответствии с двоичной инверсией номеров столбцов при , т. е. . Это приводит к матрице

Шаг 3. Переставим столбцы матриц, заключенных в квадраты, в соответствии с двоичной инверсией номеров столбцов при , т. е. , что приводит к матрице, совпадающей с . Таким образом, окончательно получим

(7.4.3)

Матрица в выражении (7.4.3) и матрица модифицированного ПУА в выражении (6.10.3) идентичны. Отсюда следует, что преобразование Хаара при можно вычислить с помощью графа МПУА с незначительным изменением, показанным на рис. 7.3. Этот граф фактически является упрощенным графом БПУА с упорядочением по Уолшу, приведенным на рис. 6.6.

Рис. 7.3. Граф алгоритма Куси-Тьюки для вычисления преобразования Хаарау

Создание графа, соответствующего алгоритму типа Кули — Тьюки для вычисления обратного преобразования Хаара, предлагается читателю в качестве упражнения (см. задачу 7.1).

Из приведенного описания следует, что в общем случае для вычисления преобразования Хаара с помощью алгоритма типа Кули — Тьюки требуется двоичных инверсий, и N умножений.