《数字信号处理》课程教学课件（2020讲稿）第四章 快速傅里叶变换 §4-4 按频率抽取（DIF）的FFT算法（Sande-Tukey算法）

可见，NDFT2按k为奇偶分解N-DFT按频率抽取NDFT2N1(n)=x(n)+x(n+(n2N1n=2N4NWNx(n+x2(n)=[x(n)-x(n+IW222

7 / 30 可见， N  DFT 按k为奇偶分解 按频率抽取 DFT N  2 DFT N  2 ) 2 ( ( ) N x n x n  n WN N x n x n x n N x n x n x n )] 2 ( ) [ ( ) ( ) 2 ( ) ( ) ( 2 1         1 2  0,1,.,  N n n WN

例：N=8，DIF的分解过程（见图4-16）[P.137]N=2v-1仍为偶数(v≥3):N=2V2(0)x(0)X(0)：上述分解过程可继续下去，(1)N/2点x(1)X(2)直至分解v次/步后变成求X(2)N/2 个 2-DFT 为止。DFTX(4)x(2)x(3)X(6)x(3)DIF-FFT算法(0)X()x(4)(1)X(3)x(5)N/2点（显然与DIT-FFT算法的分解类似）WNS5(2)x(6)DFTX(5)WN(3)(7)X()

8 / 30 例：N=8，DIF的分解过程（见图4-16）[P.137] 2 ( 3) 2 2 1       ，  仍为偶数 N N （显然与DIT-FFT算法的分解类似） N/2点 DFT N/2点 DFT DIF-FFT算法 ∴上述分解过程可继续下去， 直至分解ν次/步后变成求 N/2 个 2-DFT 为止