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 умножений.
