FFT是一种快速计算DFT的算法。按时间抽选的基-2FFT推导过程如下：
首先给出DFT的计算公式：
X(k)=DFT[x(n)]=∑n=0N−1x(n)WnkN X ( k ) = D F T [ x ( n ) ] = ∑ n = 0 N − 1 x ( n ) W N n k
其中 WN=e−j2πN W N = e − j 2 π N
容易证明：
WnkN=W(n+rN)kN=W(k+rN)nN，r为整数 W N n k = W N ( n + r N ) k = W N ( k + r N ) n ， r 为 整 数WnkN=WmnkmN，WnkN=Wnk/mN/m W N n k = W m N m n k ， W N n k = W N / m n k / m
因此，可以得出一些特殊值：
WN/2N=−1 W N N / 2 = − 1Wk+N2N=−WkN W N k + N 2 = − W N kW(N−k)nN=W(N−n)kN=W−nkN W N ( N − k ) n = W N ( N − n ) k = W N − n k
FFT的主要思想就是利用这些性质将DFT中的某些项合并。
设序列的长度为 N=2L N = 2 L ，将其分成奇偶两组：
{x(2r)=x1(r)x(2r+1)=x2(r)(1) (1) { x ( 2 r ) = x 1 ( r ) x ( 2 r + 1 ) = x 2 ( r )
其中
r=0,1,...,N2−1 r = 0 , 1 , . . . , N 2 − 1
则
X(k)=∑n=0(n为偶数)N−1x(n)WnkN+∑n=0(n为奇数)N−1x(n)WnkN X ( k ) = ∑ n = 0 ( n 为 偶 数 ) N − 1 x ( n ) W N n k + ∑ n = 0 ( n 为 奇 数 ) N − 1 x ( n ) W N n kX(k)=∑r=0N2−1x(2r)W2rkN+∑r=0N2−1x(2r+1)W(2r+1)kN X ( k ) = ∑ r = 0 N 2 − 1 x ( 2 r ) W N 2 r k + ∑ r = 0 N 2 − 1 x ( 2 r + 1 ) W N ( 2 r + 1 ) kX(k)=∑r=0N2−1x1(r)WrkN/2+WkN∑r=0N2−1x2(r)WrkN/2 X ( k ) = ∑ r = 0 N 2 − 1 x 1 ( r ) W N / 2 r k + W N k ∑ r = 0 N 2 − 1 x 2 ( r ) W N / 2 r k
令
X1(k)=∑r=0N2−1x1(r)WrkN/2 X 1 ( k ) = ∑ r = 0 N 2 − 1 x 1 ( r ) W N / 2 r kX2(k)=∑r=0N2−1x2(r)WrkN/2 X 2 ( k ) = ∑ r = 0 N 2 − 1 x 2 ( r ) W N / 2 r k
则
X(k)=X1(k)+WkNX2(k)(2) (2) X ( k ) = X 1 ( k ) + W N k X 2 ( k )
X1(k),X2(k) X 1 ( k ) , X 2 ( k ) 分别是 x1(r)和x2(r) x 1 ( r ) 和 x 2 ( r ) 的 N/2 N / 2 点DFT。
这样我们就可以把一个 N N 点DFT分解为两个
但是式中的
可以应用周期性求解 X(k) X ( k ) 的后一半序列。
易证：
X1(N2+k)=X1(k)X2(N2+k)=X2(k)Wk+N2N=−WkN X 1 ( N 2 + k ) = X 1 ( k ) X 2 ( N 2 + k ) = X 2 ( k ) W N k + N 2 = − W N k
因此：
X(k+N2)=X1(k)−WkNX2(k),k=0,1,...,N2−1(3) (3) X ( k + N 2 ) = X 1 ( k ) − W N k X 2 ( k ) , k = 0 , 1 , . . . , N 2 − 1
通过 (2) ( 2 ) 式和 (3) ( 3 ) 式，就可以通过两个 N/2 N / 2 点DFT序列组合出一个完整的 N N 点DFT序列。
附运算次数(序列的长度为
直接DFT：
复数乘法 N2 N 2 次
复数加法 N(N−1) N ( N − 1 ) 次
利用FFT求解DFT：
复数乘法 N2log2N N 2 l o g 2 N 次
复数加法 Nlog2N N l o g 2 N 次
