4.3. Алгоритмы быстрых преобразований Уолша (БПУ)

Матрица Адамара — кронекеровская матрица, и, пользуясь теоремой 3 § 4.1, для нее нетрудно получить

Граф преобразования, соответствующий (4.34), показан на. рис. 4.3 для . Его важной особенностью по сравнению, скажем, с графом быстрого преобразования Хаара, показанным на рис. 4.2, является то, что он дает так называемое преобразование «с замещением»: на каждом этапе преобразования вычисления производятся над парами величин и результат помещается в узлы на том же уровне, что и исходные величины. Так как узлам на графе соответствуют ячейки памяти процессора, то это значит, что на вычисление не требуется дополнительная емкость памяти.

Матрица Адамара является симметрической, т. е. не изменяется при транспонировании. Матрицы-сомножители в ее факторизованном представлении (4.34) также являются симметрическими. Поэтому, транспонировав матрицы в формуле (4.34), можно получить обращенный вариант факторизованного представления:

Матрица преобразования Уолша — Пэли может быть получена умножением матрицы на матрицу двоичной инверсии [см. (3.121 а)], т. е.

С другой стороны, из представления матрицы в виде суммы кронекеровских матриц в табл. 3.5

можно, подобно тому, как это было сделано в § 4.2 для матрицы Хаара, получить факторизованное представление

(кликните для просмотра скана)

матрицы не требующее двоичной инверсии на последней стадии преобразования (сравним с (4.34)):

Граф, соответствующий такому представлению для показан на рис. 4.4 (см. для сравнения рис. 4.2).

Формула (4.37) дает возможность получить факторизованное представление матрицы двоичной инверсии. Действительно, обозначив

(4.37) аналогично с (4.23) -(4.25) можно переписать так:

Применим теперь теорему 4 из § 4.1:

По определению прямого произведения матриц матрицу можно вынести из первой матрицы (4.40). Поскольку остающаяся после этого матрица согласно (3.135) равна то

или по теореме 3 из § 4.1

Эта формула является рекуррентным выражением для матрицы (сравним с (4.25)). Воспользовавшись ею

и преобразуя с помощью (4.10) получающееся на шаге итерации произведение матриц

получим

Сравнив это выражение с (4.35) и (3.121 в), можно заключить, что второе произведение в (4.44) является факторизованным представлением матрицы двоичной инверсии:

Граф двоичной инверсии в соответствии с (4.45) показан на рис. 4.5 для Такое факторизованное представление матрицы двоичной инверсии можно использовать в тех случаях, когда в системе команд процессора нет удобных команд работы с отдельными двоичными разрядами, которые необходимы для непосредственной организации перестановок.

Это же соображение относится к матрице перестановки из кода Грея в простой двоичный код, необходимой для перехода от матрицы Адамара к матрице Уолша:

(кликните для просмотра скана)

(кликните для просмотра скана)

Формула (4.49) является рекуррентным выражением матрицы (сравним с 4.25)). Преобразуя (4.49) так же, как (4.43), (4.44), получаем

Учитывая связь между матрицами по формулам (3.121), можно заключить, что

Таким образом, формула (4.51) дает факторизованноэ представление матрицы перестановки Соответствующий граф перестановки показан на рис. 4.6 для

Матрицу можно совместить с матрицами, составляющими факторизованное представление матрицы и получить факторизованное представление матрицы преобразования Уолша, не требующее перестановок:

Граф преобразования Уолша, соответствующий. (4.52), показан на рис. 4.7 для