Быстрым преобразованием Фурье (БПФ) называют дискретное преобразование Фурье (ДПФ), при котором достигается существенное уменьшение объема вычислений по сравнению с классическим ДПФ.
Пусть ДПФ представлено в виде
X(k) = x(n)*exp(-j2πkn/N), k= 0,1,2,...N-1,
где N — число отсчетов на одном периоде входного периодического сигнала x, n- номер отсчета, k — номер гармоники.
Если разбить N отсчетов сигнала x(n) на две более короткие последовательности отсчетов и соответствующим образом скомбинировать их ДПФ, то можно получить ДПФ исходного сигнала с меньшими вычислительными затратами.
Так, если N-отсчетный сигнал разбить на два N/2-отсчетных сигнала, то для вычисления ДПФ каждого из них потребуется около 2(N/2)2 комплексных умножений вместо N2комплексных умножений, требующхся для ДПФ N-отсчетного сигнала. В свою очередь, разбивая последовательности из N/2 отсчетов на последовательности из N/4 отсчетов и т.д., можно продолжить сокращение вычислительной сложности ДПФ.
Одним из популярных алгоритмов БПФ является алгоритм с прореживанием по времени.
Пусть N выбрано равным 2m, а две N/2-отсчетные последовательности, обозначенные x1(n)= x(2n) и x2(n)= x(2n+1), n= 0,1,2,...N/2-1, составлены из отсчетов сигнала x(n) соответственно с четными и нечетными номерами.
ДПФ сигнала x(n) можно выразить через x1(n) , x2(n) следующим образом:
X(k) = x1(n) WNnk + x2(n) WNnk= x(2n) WN 2nk + x(2n+1) WN (2n+1)k =
x1(2n) WN/2nk + WNk x2(2n+1) WN/2nk= X1(k) + WNKX2(k),
где WN = exp(-j2π/N) — так называемый поворачивающий множитель. Здесь учтено, что
WN2 = WN/2.
Таким образом, N-точечное ДПФ X(k) может быть представлено двумя N/2-точечными ДПФ.
Так как X(k) определено при 0kN-1, а X1(k) и X2(k) — при 0kN/2-1, то необходимо доопределить преобразование X(k) для k N/2. Учитывая, что X1(k) и X2(k) – периодические функции с периодом N/2, имеем
X(k+N/2) = X1(k+N/2) + WNK+N/2X2(k+N/2) = X1(k) + WNKX2(k)
Таким образом, N-точечное ДПФ есть
X(k) = X1(k) + WNKX2(k) при 0kN/2-1
X(k) = X1(k-N/2) + WNKX2(k-N/2) при N/2kN-1.
Далее аналогичным образом на последовательности, состоящие из четных и нечетных отсчетов, разбиваются каждый из сигналов x1(n) и x2(n)
Поскольку на каждом этапе БПФ необходимо выполнить N комплексных умножений, а общее количество этапов равно log2N, то число комплексных умножений, необходимое для нахождения N-точечного ДПФ, приблизительно равно N*log2N.