4.4. Алгоритм быстрого дискретного преобразования Фурье (БПФ)

В соответствии с табл. 3.5 матрица может быть записана так:

или

где обозначено

Выделим в (4.54) последнее слагаемое и преобразуем оставшуюся сумму:

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

или благодаря (4.5),

По определению прямого произведения матриц подматрицу в последнем сомножителе можно вынести за знак матрицы:

Подставив теперь сюда вместо аналогичную формулу с заменой на получим

или, представив первую слева матрицу 12 в кронекеровском произведении в фигурных скобках (4.60) в виде и воспользовавшись (4.10), запишем

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

и соответственно матрицы

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

Умножение на матрицу требует выполнения операций сложения (по одной на каждую строку матрицы), т. е. общее количество операций сложения на всю матрицу равно

Если же не производить факторизацию матрицы ДПФ, то для вычисления ДПФ требуется выполнить операций умножения и сложения. Граф преобразования, соответствующий (4.63) для показан на рис. 4.8. Числа в узлах графа являются показателями степени экспоненты

Сравнив (4.63) с (4.34), а также рис. 4.8 с 4.3, нетрудно заметить сходство между факторизованными представлениями матрицы Адамара и матрицы ДПФ со строками, переставленными по закону двоичной инверсии: они отличаются только наличием в каждом сомножителе

жителе в (4.63) диагональной матрицы. Транспонировав (4.63), можно получить представление матрицы ДПФ

аналогичное (4.35).

Рис. 4.8.

Отмеченную аналогию можно обнаружить для всего многообразия представлений ДПФ и преобразования Уолша — Адамара, которые можно построить из (4.63) и (4.34), применяя правила матричной алгебры. Некоторые примеры таких преобразований для матрицы ДПФ даны в [74]. Эта аналогия говорит также о том, что любой алгоритм БПУ можно превратить в алгоритм БПФ и наоборот, добавив или соответственно изъяв диагональные матрицы, содержащие комплексные экспоненциальные множители.

Описанные в этом параграфе алгоритмы БПФ требуют либо двоичной инверсии порядка отсчетов спектра, как в (4.63), либо двоичной инверсии элементов исходной преобразуемой последовательности. Как и в случае матрицы можно построить алгоритм, не требующий двоичной инверсии, но при этом нельзя будет производить преобразование с замещением, как по (4.63) (см. также рис 4.8). Следует отметить, что во многих задачах обработки изображений, особенно когда ДПФ используется для фильтрации сигналов в частотной области, двоичная инверсия отсчетов дискретного спектра после БПФ не обязательна, так как после прямого преобразования в этих случаях следует обратное преобразование, которое может выполняться по схеме (4.66).