X ( k ) = ∑ n = 0 N x ( n ) W N n k X(k)=\sum_{n=0}^Nx(n)W_N^{nk} X(k)=∑n=0Nx(n)WNnk
其中
W N = e − j 2 π N W_N=e^{-j\frac{2\pi}{N}} WN=e−jN2π
k = 0 , 1 , . . . , N − 1 k=0,1,...,N-1 k=0,1,...,N−1
离散傅立叶变换为
X ( k ) = ∑ n = 0 N x ( n ) W N n k X(k)=\sum_{n=0}^Nx(n)W_N^{nk} X(k)=∑n=0Nx(n)WNnk
可分解为
X ( k ) = ∑ n = 0 N 2 − 1 ( x ( 2 n ) W N 2 n k + x ( 2 n + 1 ) W N ( 2 n + 1 ) k ) X(k)=\sum_{n=0}^{\frac{N}{2}-1}(x(2n)W_N^{2nk}+x(2n+1)W_N^{(2n+1)k}) X(k)=∑n=02N−1(x(2n)WN2nk+x(2n+1)WN(2n+1)k)
= ∑ n = 0 N 2 − 1 x ( 2 n ) W N 2 n k + ∑ n = 0 N 2 − 1 x ( 2 n + 1 ) W N ( 2 n + 1 ) k \quad = \sum_{n=0}^{\frac{N}{2}-1}x(2n)W_N^{2nk}+\sum_{n=0}^{\frac{N}{2}-1}x(2n+1)W_N^{(2n+1)k} =∑n=02N−1x(2n)WN2nk+∑n=02N−1x(2n+1)WN(2n+1)k
= ∑ n = 0 N 2 − 1 x ( 2 n ) W N 2 n k + W N k ∑ n = 0 N 2 − 1 x ( 2 n + 1 ) W N ( 2 n ) k ( E Q . 1 ) \quad = \sum_{n=0}^{\frac{N}{2}-1}x(2n)W_N^{2nk}+W_N^{k}\sum_{n=0}^{\frac{N}{2}-1}x(2n+1)W_N^{(2n)k}\quad(EQ.1) =∑n=02N−1x(2n)WN2nk+WNk∑n=02N−1x(2n+1)WN(2n)k(EQ.1)
序列x(n)分解
偶 数 项 x 1 ( n ) = x ( 2 n ) , 其 中 n = 0 , 1 , . . . , N 2 − 1 偶数项x1(n)=x(2n),其中n=0,1,...,\frac{N}{2}-1 偶数项x1(n)=x(2n),其中n=0,1,...,2N−1
奇 数 项 x 2 ( n ) = x ( 2 n + 1 ) , 其 中 n = 0 , 1 , . . . , N 2 − 1 奇数项x2(n)=x(2n+1),其中n=0,1,...,\frac{N}{2}-1 奇数项x2(n)=x(2n+1),其中n=0,1,...,2N−1
则相应DFT
X 1 ( k ) = ∑ n = 0 N 2 − 1 x 1 ( n ) W N 2 n k , 其 中 k = 0 , 1 , . . . , N 2 − 1 X_1(k)=\sum_{n=0}^{\frac{N}{2}-1}x1(n)W_{\frac{N}{2}}^{nk},其中k=0,1,...,\frac{N}{2}-1 X1(k)=∑n=02N−1x1(n)W2Nnk,其中k=0,1,...,2N−1
X 2 ( k ) = ∑ n = 0 N 2 − 1 x 2 ( n ) W N 2 n k , 其 中 k = 0 , 1 , . . . , N 2 − 1 X_2(k)=\sum_{n=0}^{\frac{N}{2}-1}x2(n)W_{\frac{N}{2}}^{nk},其中k=0,1,...,\frac{N}{2}-1 X2(k)=∑n=02N−1x2(n)W2Nnk,其中k=0,1,...,2N−1
其中
W N 2 n k = e − j 2 π n k N 2 W_{\frac{N}{2}}^{nk} = e^{-j\frac{2\pi nk}{\frac{N}{2}}} W2Nnk=e−j2N2πnk
= e − j 2 π 2 n k N \quad = e^{-j\frac{2\pi 2nk}{N}} =e−jN2π2nk
= W N 2 n k \quad = W_{N}^{2nk} =WN2nk
= W N 2 n ( k + N 2 ) \quad = W_{N}^{2n(k+\frac{N}{2})} =WN2n(k+2N)
所以EQ.1可以转换为,而且 X 1 ( k ) 及 X 2 ( k ) X_1(k)及X_2(k) X1(k)及X2(k)都是以 N 2 \frac{N}{2} 2N为周期的
X ( k ) = X 1 ( k ) + W N k X 2 ( k ) X(k)=X_1(k)+W_{N}^{k}X_2(k) X(k)=X1(k)+WNkX2(k)
而
W N k = − W N ( k + N 2 ) W_{N}^{k}=-W_{N}^{(k+\frac{N}{2})} WNk=−WN(k+2N)
则
X ( k + N 2 ) = X 1 ( k + N 2 ) + W N k + N 2 X 2 ( k + N 2 ) X(k+\frac{N}{2})=X_1(k+\frac{N}{2})+W_{N}^{k+\frac{N}{2}}X_2(k+\frac{N}{2}) X(k+2N)=X1(k+2N)+WNk+2NX2(k+2N)
= X 1 ( k + N 2 ) − W N k X 2 ( k + N 2 ) \quad =X_1(k+\frac{N}{2})-W_{N}^{k}X_2(k+\frac{N}{2}) =X1(k+2N)−WNkX2(k+2N)
由 X 1 ( k ) 及 X 2 ( k ) X_1(k)及X_2(k) X1(k)及X2(k)周期性得：
X ( k + N 2 ) = X 1 ( k ) − W N k X 2 ( k ) X(k+\frac{N}{2})=X_1(k)-W_{N}^{k}X_2(k) X(k+2N)=X1(k)−WNkX2(k)
最终基2-FFT使用的公式
X ( k ) = X 1 ( k ) + W N k X 2 ( k ) X(k)=X_1(k)+W_{N}^{k}X_2(k) X(k)=X1(k)+WNkX2(k)
X ( k + N 2 ) = X 1 ( k ) − W N k X 2 ( k ) X(k+\frac{N}{2})=X_1(k)-W_{N}^{k}X_2(k) X(k+2N)=X1(k)−WNkX2(k)
离散傅立叶变换为
X ( k ) = ∑ n = 0 N x ( n ) W N n k X(k)=\sum_{n=0}^Nx(n)W_N^{nk} X(k)=∑n=0Nx(n)WNnk
X(k)亦可分解为奇数项和偶数项的和
X ( k ) = X ( 2 r ) + X ( 2 r + 1 ) , 其 中 r = 0 , 1 , . . . . , N 2 X(k)=X(2r)+X(2r+1),其中 r=0,1,....,\frac{N}{2} X(k)=X(2r)+X(2r+1),其中r=0,1,....,2N
X ( 2 r ) = ∑ n = 0 N − 1 x [ n ] W N 2 n r X(2r)=\sum_{n=0}^{{N}-1}x[n]W_N^{2nr} X(2r)=∑n=0N−1x[n]WN2nr
= ∑ n = 0 N 2 − 1 x [ n ] W N 2 n r + ∑ N 2 N − 1 x [ n ] W N 2 n r \quad =\sum_{n=0}^{\frac{N}{2}-1}x[n]W_N^{2nr} + \sum_{\frac{N}{2}}^{N-1}x[n]W_N^{2nr} =∑n=02N−1x[n]WN2nr+∑2NN−1x[n]WN2nr
= ∑ n = 0 N 2 − 1 x [ n ] W N 2 n r + ∑ N N 2 − 1 x [ n + N 2 ] W N 2 ( n + N 2 ) r \quad =\sum_{n=0}^{\frac{N}{2}-1}x[n]W_N^{2nr} + \sum_{N}^{\frac{N}{2}-1}x[n+\frac{N}{2}]W_N^{2(n+\frac{N}{2})r} =∑n=02N−1x[n]WN2nr+∑N2N−1x[n+2N]WN2(n+2N)r
= ∑ n = 0 N 2 − 1 x [ n ] W N 2 n r + ∑ N N 2 − 1 x [ n + N 2 ] W N 2 n r \quad =\sum_{n=0}^{\frac{N}{2}-1}x[n]W_N^{2nr} + \sum_{N}^{\frac{N}{2}-1}x[n+\frac{N}{2}]W_N^{2nr} =∑n=02N−1x[n]WN2nr+∑N2N−1x[n+2N]WN2nr
r = 0 , 1 , 2 , . . . , N 2 \quad r=0,1,2,...,\frac{N}{2} r=0,1,2,...,2N
同样
X ( 2 r + 1 ) = ∑ n = 0 N − 1 x ( n ) W N n ( 2 r + 1 ) X(2r+1)=\sum_{n=0}^{{N}-1}x(n)W_N^{n(2r+1)} X(2r+1)=∑n=0N−1x(n)WNn(2r+1)
= ∑ n = 0 N 2 − 1 ( x [ n ] − x [ n + N 2 ] ) W N n ( 2 r + 1 ) \quad =\sum_{n=0}^{\frac{N}{2}-1}(x[n] - x[n+\frac{N}{2}])W_N^{n(2r+1)} =∑n=02N−1(x[n]−x[n+2N])WNn(2r+1)
r = 0 , 1 , 2 , . . . , N 2 \quad r=0,1,2,...,\frac{N}{2} r=0,1,2,...,2N
X ( k ) = ∑ n = 0 N − 1 x ( n ) W N n k X(k)=\sum_{n=0}^{N-1}x(n)W_N^{nk} X(k)=∑n=0N−1x(n)WNnk
= ∑ n = 0 N 4 − 1 ( x ( n ) W N n k + x ( n + N 4 ) W N ( n + N 4 ) k + x ( n + N 2 ) W N ( n + N 2 ) k + x ( n + 3 N 4 ) W N ( n + 3 N 4 ) k ) \quad = \sum_{n=0}^{\frac{N}{4}-1}(x(n)W_N^{nk}+x(n+\frac{N}{4})W_N^{(n+\frac{N}{4})k}+x(n+\frac{N}{2})W_N^{(n+\frac{N}{2})k}+x(n+\frac{3N}{4})W_N^{(n+\frac{3N}{4})k}) =∑n=04N−1(x(n)WNnk+x(n+4N)WN(n+4N)k+x(n+2N)WN(n+2N)k+x(n+43N)WN(n+43N)k)
= ∑ n = 0 N 4 − 1 ( x ( n ) + x ( n + N 4 ) W N ( N 4 ) k + x ( n + N 2 ) W N ( N 2 ) k + x ( n + 3 N 4 ) W N ( 3 N 4 ) k ) W N n k ( E Q . 2 ) \quad = \sum_{n=0}^{\frac{N}{4}-1}(x(n)+x(n+\frac{N}{4})W_N^{(\frac{N}{4})k}+x(n+\frac{N}{2})W_N^{(\frac{N}{2})k}+x(n+\frac{3N}{4})W_N^{(\frac{3N}{4})k})W_N^{nk}\quad (EQ.2) =∑n=04N−1(x(n)+x(n+4N)WN(4N)k+x(n+2N)WN(2N)k+x(n+43N)WN(43N)k)WNnk(EQ.2)
其中：
W N N 4 = − j W_N^{\frac{N}{4}}=-j WN4N=−j
W N N 2 = − 1 W_N^{\frac{N}{2}}=-1 WN2N=−1
W N N 3 = j W_N^{\frac{N}{3}}=j WN3N=j
所以EQ.2可以改写为
X ( k ) = ∑ n = 0 N 4 − 1 [ x ( n ) + x ( n + N 4 ) ( − j ) k + x ( n + N 2 ) ( − 1 ) k + x ( n + 3 N 4 ) ( j ) k ] W N n k ( E Q . 3 ) X(k) = \sum_{n=0}^{\frac{N}{4}-1}[x(n)+x(n+\frac{N}{4}){(-j)^k}+x(n+\frac{N}{2}){(-1)^k}+x(n+\frac{3N}{4}){(j)^k}]W_N^{nk}\quad (EQ.3) X(k)=∑n=04N−1[x(n)+x(n+4N)(−j)k+x(n+2N)(−1)k+x(n+43N)(j)k]WNnk(EQ.3)
X ( 4 k ) = ∑ n = 0 N 4 − 1 [ x ( n ) + x ( n + N 4 ) + x ( n + N 2 ) + x ( n + 3 N 4 ) ] W N 4 n k X(4k) = \sum_{n=0}^{\frac{N}{4}-1}[x(n)+x(n+\frac{N}{4})+x(n+\frac{N}{2})+x(n+\frac{3N}{4})]W_N^{4nk} X(4k)=∑n=04N−1[x(n)+x(n+4N)+x(n+2N)+x(n+43N)]WN4nk
∑ n = 0 N 4 − 1 [ x ( n ) + x ( n + N 4 ) + x ( n + N 2 ) + x ( n + 3 N 4 ) ] W N 4 n k \quad \sum_{n=0}^{\frac{N}{4}-1}[x(n)+x(n+\frac{N}{4})+x(n+\frac{N}{2})+x(n+\frac{3N}{4})]W_{\frac{N}{4}}^{nk} ∑n=04N−1[x(n)+x(n+4N)+x(n+2N)+x(n+43N)]W4Nnk
X ( 4 k + 1 ) = ∑ n = 0 N 4 − 1 [ x ( n ) − j x ( n + N 4 ) − x ( n + N 2 ) + j x ( n + 3 N 4 ) ] W N n ( 4 k + 1 ) X(4k+1) = \sum_{n=0}^{\frac{N}{4}-1}[x(n)-jx(n+\frac{N}{4})-x(n+\frac{N}{2})+jx(n+\frac{3N}{4})]W_N^{n(4k+1)} X(4k+1)=∑n=04N−1[x(n)−jx(n+4N)−x(n+2N)+jx(n+43N)]WNn(4k+1)
= ∑ n = 0 N 4 − 1 [ x ( n ) − j x ( n + N 4 ) − x ( n + N 2 ) + j x ( n + 3 N 4 ) ] W N 4 n k W N n \quad = \sum_{n=0}^{\frac{N}{4}-1}[x(n)-jx(n+\frac{N}{4})-x(n+\frac{N}{2})+jx(n+\frac{3N}{4})]W_{\frac{N}{4}}^{nk}W_N^{n} =∑n=04N−1[x(n)−jx(n+4N)−x(n+2N)+jx(n+43N)]W4NnkWNn
X ( 4 k + 2 ) = ∑ n = 0 N 4 − 1 [ x ( n ) − x ( n + N 4 ) + x ( n + N 2 ) − x ( n + 3 N 4 ) ] W N n ( 4 k + 2 ) X(4k+2) = \sum_{n=0}^{\frac{N}{4}-1}[x(n)-x(n+\frac{N}{4})+x(n+\frac{N}{2})-x(n+\frac{3N}{4})]W_N^{n(4k+2)} X(4k+2)=∑n=04N−1[x(n)−x(n+4N)+x(n+2N)−x(n+43N)]WNn(4k+2)
= ∑ n = 0 N 4 − 1 [ x ( n ) − x ( n + N 4 ) + x ( n + N 2 ) − x ( n + 3 N 4 ) ] W N 4 n k W N 2 n \quad = \sum_{n=0}^{\frac{N}{4}-1}[x(n)-x(n+\frac{N}{4})+x(n+\frac{N}{2})-x(n+\frac{3N}{4})]W_{\frac{N}{4}}^{nk}W_N^{2n} =∑n=04N−1[x(n)−x(n+4N)+x(n+2N)−x(n+43N)]W4NnkWN2n
X ( 4 k + 3 ) = ∑ n = 0 N 4 − 1 [ x ( n ) + j x ( n + N 4 ) − x ( n + N 2 ) − j ( n + 3 N 4 ) ] W N n ( 4 k + 3 ) X(4k+3) = \sum_{n=0}^{\frac{N}{4}-1}[x(n)+jx(n+\frac{N}{4})-x(n+\frac{N}{2})-j(n+\frac{3N}{4})]W_N^{n(4k+3)} X(4k+3)=∑n=04N−1[x(n)+jx(n+4N)−x(n+2N)−j(n+43N)]WNn(4k+3)
= ∑ n = 0 N 4 − 1 [ x ( n ) + j x ( n + N 4 ) − x ( n + N 2 ) − j ( n + 3 N 4 ) ] W N 4 n k W N 3 n \quad = \sum_{n=0}^{\frac{N}{4}-1}[x(n)+jx(n+\frac{N}{4})-x(n+\frac{N}{2})-j(n+\frac{3N}{4})]W_{\frac{N}{4}}^{nk}W_N^{3n} =∑n=04N−1[x(n)+jx(n+4N)−x(n+2N)−j(n+43N)]W4NnkWN3n
其 中 k = 0 , 1 , . . . , N 4 − 1 其中 k=0,1,...,\frac{N}{4}-1 其中k=0,1,...,4N−1
