logo
tsvpis

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

Попробуем найти алгоритм, который реализует преобразование Фурье несколько быстрее.

Идея, наводящая на алгоритм быстрого преобразования Фурье (БПФ):

Рассмотрим случай, когда N = p1·p2

Представим k и j в виде: k = k1 + p1k2 0 ≤ kN – 1

j = j2 + p2j1 0 ≤ jN – 1

Здесь k1 – остаток от деления k на p1 k1 = k mod p1

k2 – частное от деления k на p1 k1 = k div p1

0 ≤ k1 ≤ p1 – 1

0 ≤ k2 ≤ p2 – 1

аналогично

­j­1 – частное от деления j на p2 j1 = j div p2

­j­2 – частное от деления j на p2 j2 = j mod p2

0 ≤ j1 ≤ p1 - 1

0 ≤ j2 ≤ p2 - 1

Когда число j меняется от 0 до N, то j1 и j2 пробегают независимым образом все возможные значения в своих диапазонах. Поэтому, вместо однократного суммирования можно применить двукратное:

Можно игнорировать, т.к. оно добавляет к exp() = cos + i·sin целое число периодов и сама exp не меняется

A(0)(k1,k2)

A(1)(k1,j2)

A(2)(k1,k2)

Заметим, что:

Итак, мы будем вычислять преобразование Фурье не по (2.1), а по формулам (2.3а) и (2.3б):

0 k1 p1 – 1

0 ≤ j2 ≤ p2 – 1

0 k1 p1 – 1

0 ≤ j2 ≤ p2 – 1

(2.3a)

(2.3б)

Оценим трудоемкость вычисления преобразования Фурье по формулам 2.3:

Массив А(0) переходит в А(1), а оттуда в А(2):

Этот переход осуществляется в 2 этапа.

В формуле (2.3а) имеем р1 • р­2 коэффициентов, каждый их которых есть сумма р1 слагаемых – итого р1 • р­2 • р1 действий. В (2.3б) соответственно р1 • р­2 • р2 действий. Итого

T(n) = p1·p2·p1 + p1·pp2 = p1·p2·(p1 + p2) = N(p1+p2).

по (2.3а) по (2.3б)

Если , то трудоемкость будет , что существенно меньше трудоемкости при обычном преобразовании Фурье. Т.е. получаем метод, позволяющий реализовать преобразование Фурье значительно быстрее. Этот метод названполубыстрым преобразованием Фурье.

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4