N4点 DET N2点 N4点 DET N点 DFT I DET N点N4点 DFT DET N4点 复乘: 2 N 2 2 4 N N 2
N 点 DFT N/2 点 DFT N/2 点 DFT N/4 点 DFT N/4 点 DFT N/4 点 DFT N/4 点 DFT ……. 复乘： 2 N 2 2 2 2 + N N 22 N 2 2 2 2 4 4 4 4 + + + N N N N 42 N
FFT算法的基本思想: 利用DFT系数的特性,合并DFT运算中的某些项 把长序列DFT→短序列DFT,从而减少运算量。 FFT算法分类 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency
FFT算法的基本思想： ➢ 利用DFT系数的特性，合并DFT运算中的某些项 ➢ 把长序列DFT→短序列DFT，从而减少运算量。 FFT算法分类: 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency
第三节按时间抽选的基2-FFT算法 1、算法原理 设输入序列长度为N=2(M为正整数,将该序列 按时间顺序的奇偶分解为越来越短的子序列,称为 基2按时间抽取的FFT算法。也称为 Coolkey-Tukey 算法。 其中基2表示:N=2M,M为整数若不满足这个 条件,可以人为地加上若干零值(加零补长)使其 达到N=2M
第三节 按时间抽选的基2-FFT算法 1、算法原理 设输入序列长度为N=2M(M为正整数，将该序列 按时间顺序的奇偶分解为越来越短的子序列，称为 基2按时间抽取的FFT算法。也称为Coolkey-Tukey 算法。 其中基2表示：N=2M ，M为整数.若不满足这个 条件，可以人为地加上若干零值（加零补长）使其 达到 N=2M
2、算法步骤 分组,变量置换 X(k)=DFx(m=∑x(n)W0≤k≤N-1 H=0 先将x(m)按n的奇偶分为两组,作变量置换: 当n=偶数时,令n=2r 当n=奇数时,令n=2r+1; 得到: x(2n)=x() =0,,%-1 x(2r+1)=x2
先将x(n)按n的奇偶分为两组，作变量置换: 当n=偶数时，令n=2r; 当n=奇数时，令n=2r+1; ➢ 分组，变量置换 2、算法步骤 ( ) [ ( )] ( ) 0 1 1 0 = = − − = X k DFT x n x n W k N N n nk N 得到： 0,..., 1 (2 1) ( ) (2 ) ( ) 2 2 1 = − + = = N r x r x r x r x r
带入DFT中 X(k=DFTx(n) Ex(nWN n=0 =∑x(m)形+∑x(m n=0 n=0 n为偶数 n为奇数 N/2 N/2-1 ∑ ark (zr)N +∑x(2r+1)wx r=0 N/2-1 N/2-1 ∑x()W2+W∑x() 0 0
➢ 带入DFT中 − = = = 1 0 ( ) ( ) [ ( )] N n nk x n WN X k DFT x n − = + − = = + + / 2 1 0 (2 1) / 2 1 0 2 (2 ) (2 1) N r r k N N r r k x r WN x r W − = − = = + 1 0 1 0 ( ) ( ) N n nk N N n nk N n n x n W x n W 为偶数 为奇数 − = − = = + / 2 1 0 2 2 / 2 1 0 2 1 ( ) ( ) N r r k N k N N r r k x r WN W x r W