第四节
基--2按频率抽取的FFT算法Decimation-in-Frequency(DIF)(Sander-Tukey)
一、算法原理
?
M设输入序列长度为N=2(M为正整数，将该序
列的频域的输出序列X(k)(也是M点序列，按其
频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。
二、算法步骤
1.分组
DFT变换：
X(k)??x(n)Wn?0N?1knNk?0,?,N?1已证明频域上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）
2.代入DFT中X（k)??x(n)W??x(n)Wn?0N?12N?12n?0nkNN?1nkN??[x(n)Wn?0N?12nkNN??x(n?)W2n?0Nk2NN?12N?x(n?)W2N(n?)k2N]N(n?)k2NN??[x(n)?x(n?)W2n?0又?WNk2N]W?j?knkN?e2?N?j??kN2?e??k?偶数时W???k?奇数时W?Nk2NNk2N?1??13. 变量置换--1按k的奇偶将X(k)分成两部分，进行变量置换当k?偶数时，频率的偶数部分NkN?WN2?1,令k?2k'，k'?0,1,??12N/2?1NnkX(k)??[x(n)?x(n?)]WNk?0,2,4,6?N?12n?0令k?2k'代入N/2?1NN2nk'X(2k')??[x(n)?x(n?)]WNk'?0,1,??122n?0又?W2nk'N?Wnk'N/2(?e2??j?2nk'Nk?0,?,N/2?1?e2??jnk'N/2?Wnk'N/2）