三、按频率抽选的基-2FFT算法
1、算法原理
设序列点数N=2L,L为整数。
将X(k)按k的奇偶分组前,先将输入x(n)按n的顺序分成前后两半:
按k的奇偶将X(k)分成两部分:
令
则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N / 2点DFT,记为X1(k)和X2(k)
x1(0)
x1(1)
-1
x1(2)
x1(3)
-1
x2(0)
x2(1)
-1
x2(2)
x2(3)
-1
N/2点
DFT
N/2点
DFT
x(0)
x(7)
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
X1(0)=X(0)
X2(0)=X(1)
X1(1)=X(2)
X1(2)=X(4)
X1(3)=X(6)
X2(1)=X(3)
X2(2)=X(5)
X2(3)=X(7)
N /2仍为偶数,进一步分解:N /2 N /4
x3(0)
x3(1)
-1
-1
x4(0)
x4(1)
N/4点
DFT
N/4点
DFT
x1(0)
x1(1)
x1(2)
x1(3)
X3(0)=X1(0)=X(0)
X4(0)=X1(1)=X(2)
X3(1)=X1(2)=X(4)
X4(1)=X1(3)=X(6)
同理:
其中:
逐级分解,直到2点DFT
当N=8时,即分解到x3(n),x4(n),x5(n),x6(n),n=0,1
DSP第四章快速傅里叶变换3 来自淘豆网m.daumloan.com转载请标明出处.
