БПФ Алгоритм Кьюли-Тьюки

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

Основная идея БПФ лежит в разложении последовательности f(n), с N значениями на несколько меньших подмножеств, которые преобразовываются затем отдельно, особенно эффективно если N является степенью с базисом 2. Входная последовательность сначала разделяется на 2 подмножества, элементы которых имеют временной интервал 2Т. Эти множества в свою очередь делятся пополам и т.д. пока не останется только 2 элемента в каждой последовательности по отношению к которым применяется ДПФ. На каждом шаге интервал дискретизации удваивается для элементов, которые принадлежат к одному подмножеству.

А К-Т: исходной является дискретная выборка равноудаленных отсчетов, число которых составляет 2ⁿ. Основными операциями является сложение и вычитание. Количество итераций равно n. На последней итерации получаем спектр. Рассмотрим алгоритм для N=8.

Результаты после первой итерации получаются следующим образом:

x₁(k₀m₁m₀)=x(0m₁m₀)+x(1m₁m₀)A^k0₂, где x- исходная выборка, числа k₀ m₁ m₀-представлены в двоичной системе.

x₁(0)=x(0)+x(4) x₁(1)=x(1)+x(5)

x₁(2)=x(2)+x(6) x₁(3)=x(3)+x(7)

x₁(0)=x(0)-x(4) x₁(1)=x(1)-x(5)

x₁(2)=x(2)-x(6) x₁(3)=x(3)-x(7)

А₂=-1

Результаты после второй итерации получаются следующим образом:

X₂(k₀k₁m₀)=x₁(k₀0m₀)+x₁(k₀1m₀)A^k0+2k1₄. А₄=-j.

x₂(0)=x₁(0)+x₁(2) x₂(1)=x₁(1)+x₁(3)

x₂(2)=x₁(0)-x₁(2) x₂(3)=x₁(1)-x₁(3)

x₂(4)=x₁(4)-jx₁(6) x₂(5)=x₁(5)-jx₁(7)

x₂(6)=x₁(4)+jx₁(6) x₂(7)=x₁(5)+jx₁(7)

Результаты после третьей итерации получаются следующим образом:

x₃(k₀k₁k₂)=x₂(k₀k₁0)+x₂(k₀k₁1)A^k0+2k1+4k2₈,

x₃(0)=x₂(0)+x₂(2) x₃(1)=x₂(0)+A⁴₈x₂(1)

x₃(2)=x₂(2)+A²₈x₂(3) x₃(3)=x₂(2)+A⁶₈x₂(3)

x₃(4)=x₂(4)+A¹₈x₂(5) x₃(5)=x₂(4)+A⁵₈x₂(5)

x₃(6)=x₂(6)+A³₈x₂(7) x₃(7)=x₂(6)+A⁷₈x₂(7)

Спектр получается следующим образом: 8Cx(k₂k₁k₀)=x₃(k₀k₁k₂). Блок схема алгоритма