文档介绍：第四节 基--2按频率抽取的FFT算法Decimation-in-Frequency(DIF) (Sander-Tukey)
一、算法原理
设输入序列长度为N=2M(M为正整数,将该序列的频域的输出序列X(k)(也是M点序列,按其频域顺序的奇偶分解为越来越短的子序列,称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。
二、算法步骤
DFT变换:
已证明频域上X(k)按k的奇偶分为两组,在时域上x(n)按n的顺序分前后两部分,现将输入x(n)按n的顺序分前后两部分:
前半子序列x(n),0≤n≤N/2-1;
后半子序列x(n+N/2),0≤n≤N/2-1;
例:N=8时,前半序列为:x(0),x(1),x(2),x(3);
后半序列为: x(4),x(5),x(6),x(7);
则由定义输出(求DFT)
3. 变量置换--1
3. 变量置换--2
3. 变量置换--3
3. 变量置换--4
一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照:
可见:如此分解,直至分到2点的DFT为止。