Алгоритм быстрого преобразования Фурье

Дискретное преобразование Фурье довольно часто применяется при цифровой обработке информации. Поэтому важным фактором начинает выступать время реализации алгоритма ДПФ на имеющейся в распоряжении исследователя вычислительной машине. Особенно большое значение этот фактор приобретает при увеличении числа отсчетов анализируемого сигнала N. Действительно, в соответствии с формулой дискретного преобразования Фурье

для определения N значений последовательности требуется произвести примерно N² умножений и N² сложений [точнее, (N—1)² умножений и N(N—1) сложений]. Число операций возрастает пропорционально квадрату размерности ДПФ. Таким образом, с ростом N непропорционально быстро возрастает время расчета ДПФ на ЭВМ.

Идея быстрого дискретного преобразования Фурье (его обычно называют просто — быстрое преобразование Фурье — БПФ; английский термин — Fast Fourier Transform, FFT) заключается в следующем.

Если N не является простым числом и может быть разложено на множители, процесс вычислений можно ускорить, разделив анализируемый набор отсчетов на части, вычислив их ДПФ и объединив результаты. Делить исходную последовательность можно на любое количество частей. Таким образом, приведенный алгоритм позволяет уменьшить число операций в случае любого N, не являющегося простым числом. Степень ускорения вычислений зависит от числа фрагментов последовательности и является максимальной при делении на две части.

Если исходное число точек N равно целой степени числа 2, то последовательность а(п) длиной N разбивают на две последовательности а₁(п) и a₂(n) длиною N/2 каждая и находят для них ДПФ соответственно b₁(k) и b₂(k). Естественно, что число N при этом предполагается четным(обычно, но не обязательно). Затем по значениям b₁(k) и b₂(k) определяют N-точечное ДПФ b(k). Если эта последняя операция не потребует много времени, то тогда можно ожидать сокращения общей длительности вычислений. Действительно, обычным методом два ДПФ по N/2 точек можно найти заметно быстрее, чем одно N-точечное ДПФ, так как (N/2)²+(N/2)²<N². Подобным образом можно пойти и дальше: разделить пополам каждую из последовательностей а₁(п) и а₂(п), найти для них свои ДПФ и далее искать ДПФ b₁(k) и b₂(k), исходя из этих частных ДПФ. Очевидно, что такое деление можно проводить до тех пор, пока мы не получим последовательности, каждая из которых будет состоять всего из двух членов, ДПФ которых рассчитывается вообще без использования операций умножения (достаточно вычислить сумму и разность двух отсчетов). Число требуемых при этом пар операций «умножение — сложение» можно оценить как .Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы ДПФ уменьшаются в раз. При больших N это отношение становится весьма велико (например, 1024/log₂(1024) = 102,4, то есть при N=1024 достигается более чем 100-кратное ускорение).

При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления последовательности отсчетов на части (прореживание по времени либо по частоте) и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).