2.2.3. Быстрое преобразование Фурье (бпф)

Применим выше изложенную идею для случая N = 2^r.

Представим числа k и j в двоичной записи:

- двоичная запись числа k,

- двоичная запись числа j, .

Аргументов экспоненты всякий раз является число :

Все целочисленные слагаемые в данной сумме можно отбросить, т.к. они добавят целое число периодов к аргументу и не повиляют на значение exp(2i)

Целое число, не влияющие на значение exp(-2i). Его можно отбросить

Учтём, что, когда j пробегает все значения от 0 до N-1, индексы j₁ … j_r меняются независимым образом, принимая значения либо 0 либо 1.

Суммирование по m распишем подробно и каждую соответствующую компоненту заносим в соответствующую сумму.

.

Преобразование Фурье можно вычислять по следующей формуле (2.4):

)=

где s = 0,…,r-1. (2.4)

Итак, необходимо выполнить r шагов, постепенно переходя по формуле (2.4) от массива А⁽⁰⁾ к массиву А^(S)_.

Данную формулу можно переписать в виде рекуррентной последовательности:

и т.д.

.

Трудоемкость вычисления каждого коэффициента по формуле (2.4) равна const (при условии, что заранее уже заполнен массив частичных сумм разрядов всех числе от 0 до N-1). Размер массива N*r.

Итого, трудоемкость БПФ по формуле (2.4) составляет:

C · 2^r · r = C N logN, где 2^r – N элементов в каждом массиве,

r – число шагов.

Трудоемкость преобразования Фурье по формулам (2.4) существенно меньше. Чем у ранее изученных методов с трудоемкостями C n² и C n^3/2.

Аналогичные формулы можно вывести не только лишь в случае N = 2^r (как в классическом БПФ), но и в случае N = k₁·k₂·…·k_r. В этом случае трудоемкость составит:

T(n) = N(k₁ + k₂ + … + k_r).

Заметим, что и для полубыстрого и для быстрого преобразования Фурье обратное преобразование вычисляется по тем же формулам, что и прямое только в exp нет знака « – » и отсутствуют множители ивполубыстром и ½ в быстром преобразовании Фурье.

Домашнее задание №2

Выразить А³(1, 0, 1, 1) через А² и экспоненту по формуле быстрого преобразования Фурье. N = 2⁴.