Быстрое преобразование Фурье в базисах Уолша

ДПФ в базисе дискретных экспоненциальных функций (ДЭФ) предполагает выполнение большого числа комплексных умножений, требующих существенных затрат машинного времени, что ограничивает возможность его практического применения. Существует широкий класс систем базисных функций, в которых преобразование Фурье сводится к алгебраическим преобразованиям над дискретными отсчетами. К такому классу относятся функции Уолша. Наибольшее применение нашли функции Уолша, Уолша-Адамара, Уолша-Пели.

Рассмотрим ДПФ в базисе функций Уолша-Адамара.

Базис Уолша-Адамара вводится посредством т.н. матриц Адамара, которые строятся на основании следующего рекуррентного правила

Обозначая через матрицу Адамара размерности , дискретный спектр можно записать в матричной форме следующим образом

(4.10)

где -вектор-столбец входного сигнала,

-вектор-строка дискретного спектра.

Поведем вычисления в базисе Уолша-Адамара для .

Составим матрицу Адамара

Легко убедится в том, что к матрице Адамара можно прийти полагая в дереве БПФ все весовые коэффициенты ребер графа равны 1.

Операция “бабочка” сводится к вычислениям

т.е. процессор Фурье в базисе Уолша-Адамара вычисляет дискретный спектр используя лишь простейшие арифметические операции суммирования и вычитания отсчетов сигнала.

На ряду с базисом Уолша-Адамара существуют базис Уолша-Пели и классический базис Уолша.