DSP第四章2快速付里叶变换FFT - 图文

第四节

基--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）

3. 变量置换--2N/2?1NNnk'?X(2k')??[x(n)?x(n?)]WN/2k'?0,1,??122n?0x(n)前一半序列x(n)后一半序列NN设一个新序列：x1(n)?x(n)?x(n?),n?0,1,2??22N/2?1Nnk'则X(2k')??x1(n)]WN/2?X（k'?0,1,??11k')2n?0可见：x(n)的频域X(k)的偶数部分可以通过x1(n)序列的DFTX（1k)求得。N由于x1(n)序列只有点，所以其运算量降低一半。23. 变量置换--3同理：当k?奇数时，频率的奇数部分NkN?WN2??1,令k?2k'?1，k'?0,1,??12N/2?1NnkX(k)??[x(n)?x(n?)]WNk?1,3,5,7?N?12n?0令k?2k'?1代入N/2?1NNn（2k'?1）X(2k'?1)??[x(n)?x(n?)]WNk'?0,1,??122n?0又?W2nk'N?Wnk'N/2(?e2??j?2nk'N?e2??jnk'N/2?Wnk'N/2）3. 变量置换--4N/2?1N?nN?nk'?X(2k'?1)???x(n)?x(n?)?WN?WN/2k'?0,1,??12?2n?0?x(n)前一半序列x(n)后一半序列NNn设一个新序列：x2(n)?[x(n)?x(n?)]WN,n?0,1,2??122N/2?1Nnk'则X(2k'?1)??x2(n)WN/2?X（k'?0,1,??12k')2n?0可见：x(n)的频域X(k)的奇数部分可以通过x1(n)序列的DFTX（2k)求得。N由于x2(n)序列只有点，所以其运算量降低一半。24.结论1

?一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：

X(k)?X(2k')?X(2k'?1)???N点DFTN/2点N/2点即先求出X1(k')，X2(k')k'?0,1?N/2?1再用k?2k',k?2k'?1分别代入X(k)?X1(2k')?X2(2k'?1),k?0,1,?N?1又合成N点DFT可见：如此分解，直至分到2点的DFT为止。

4.结论2N/2?1X1(k')?N/2?1?x(n)]W1n?0nk'N/2??n?0Nnk'[x(n)?x(n?)]WN/22N/2?1n?0Nk'?0,1,??12Nk'?0,1,??12X2(k')?N/2?1?x2(n)]Wnk'N/2??n?0Nnnk'[x(n)?x(n?)]WNWN/22

三、蝶形流图表示蝶形单元：时域中，前后半部表示式用蝶形结表示。x(n)x(n)?x(n?N/2)?x1(n)x(n+N/2)WnN[x(n)?x(n?N/2)]W?x2(n)nN与时间抽取法的推演过程一样，由于N=2L,N/2仍为偶数，所以可以将N/2点DFT的输出X(k)再分为偶数组和奇数组，这样就将一个N/2点的DFT分成两个N/4点DFT的输入，也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成，直至最后为2点DFT。例子：求3N=2=8点DIF先将N=8DFT分解成2个4点DFT：（1）先按N=8-->N/2=4，做4点的DIF：Nx1(n)?x(n)?x(n?)2Nnx2(n)?[x(n)?x(n?)]WN2可知：时域上：x(0),x(1),x(2),x(3)为前半序列x(4),x(5),x(6),x(7)为后半序列产生新的子序列：x1(n)、x2(n)频域上：X(0),X(2),X(4),X(6)由x1(n)给出X(1),X(3),X(5),X(7),由x2(n)给出前半部分序列后半部分序列将N=8点分解成2个4点的DIF的信号流图x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WW8108X1(k)x1(n)X(0)X(2)4点X(4)DFTX(6)x2(n)WW8328X2(k)X(1)X(3)4点X(5)DFTX(7)如：x（?x(0)?x(4),x（）?x(1)?x(5),x（?x(2)?x(6),x（）?x(3)?x(7)10）1112）13nnx（?[x(0)?x(4)]WN,x（）?[x(1)?x(5)]WN,20）21nnx（?[x(2)?x(6)]WN,x（）?[x(3)?x(7)]WN22）23(2)N/2(4点)-->N/4(2点)FFT(a)先将4点分解成2点的DIF：?因为4点DIF还是比较麻烦，所以再继续分解。?x1(0)、x1(1)前半部分序列x1(n):??x1(2)、x1(3)后半部分序列?x2(0)、x2(1)前半部分序列同理：x2(n):??x2(2)、x2(3)后半部分序列N?x(n)?x(n?)?x(L)113?N2若设：（L?0??1），在此L?0，1?N4?[x1(n)?x1(n?)]WNn?x（4L）2?N??x2(n)?x2(n?2)?x5(L)N同理：（L?0??1），在此L?0，1?Nn4?[x2(n)?x2(n?)]WN?x（6L）2?（b)一个2点的DIF蝶形流图x3(0)x1(0)x1(1)x1(2)x1(3)2点DFTx3(1)X(0)X(4)W08x4(0)W28X(2)2点DFTx4(1)X(6)其中x3(0)?x1(0)?x1(2),x3(1)?x1(1)?x1(3)

(c)另一个2点的DIF蝶形流图x5(0)x2(0)x2(1)x2(2)x2(3)2点DFTx5(1)X(1)X(5)W08x6(0)W28X(3)2点DFTx6(1)X(7)(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取1x3(0)、x3(1)为例。nkX(k)??x(n)W2代入上面流图可知：n?0X3(0)?x(0)W?x(4)W?x(0)W?x(4)W02120202020202X3(1)?x(0)W?x(4)W?x(0)W?x(4)W这是一蝶形结这里用到对称性Wnk?N2N0?1202??W，则W??W02nkNnk?12??W，其中n?0,1;k?0,1nk2?W(b)2个1点的DFT蝶形流图x3(0)1点DFTX(0)X(4)Wx3(1)进一步简化为蝶形流图：021点DFTx3(0)X(0)Wx3(1)02X(4)(4)一个完整N=8的按频率抽取FFT的运算流图x(0)x(1)x(2)x(3)x(4)m=0m=1m=2X(0)WWW1W82W8W380808W08X(4)X(2)X(6)X(1)28WW0808x(5)x(6)x(7)X(5)X(3)W08W0其中旋转因子，共有WN?W28N/2?1NW08X(7)(5)DIF的特点

(a)输入自然顺序，输出乱序且满足码位倒置规则。

(b)根据时域、频域互换，可知：输入乱序，输出自然顺序。

（6）DIF与DIT比较1????相同之处：（1）DIF与DIT两种算法均为原位运算。（2）DIF与DIT运算量相同。它们都需要NNmF?log2次复乘2NaF?Nlog2次复加?DIF与DIT是两种等价的FFT算法（6）DIF与DIT比较2

?不同之处：

（1）DIF与DIT两种算法结构倒过来。

DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。

DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。

（2）DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。

作业

第五节IFFT运算方法

?以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算FFT的方法。

一、利用FFT计算IFFT的思路1?将下列两式进行比较1??nkx(n)?IDFT[X(k)]?X(k)W?N??Nk?0?N?1nk?X(k)?DFT[x(n)]??x(n)WN?k?0?nk?nk(1)只要把DFT运算中的每个系数WN?改成WN(2)将运算结果都除以N（3）那么以上讨论的时间抽取或频率抽取FFT算法都可以拿来运算IDFTN?1

二、利用FFT计算IFFT的思路2

?利用FFT计算IFFT时在命名上应注意：

?(1)把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k),原来按x(n)的奇、偶次序分组的时间抽取法FFT，现在就变成了按X(k)的奇偶次序抽取了。

?（2）同样，频率抽取的FFT运算用于IDFT运算时，也应改变为时间抽取的IFFT。

三、改变FFT流图系数的方法

1.思路

?在IFFT的运算中，常常把1/N分解为

m(1/2)，并且在M级运算中每一级运算都分别乘以1/2因子，就可得到IFFT的两种基本蝶形运算结构。（并不常用此方法）

2.IFFT的基本蝶形运算A1?nWN2121?nA?WNB2????A121?nWN211?A?B?2B1?nA?WNB2B2?A?B?WN?n(a)频率抽取IFFT的蝶形运算(b)时间抽取IFFT的蝶形运算四.直接利用FFT流图的方法

1.思路

?前面的两种IFFT算法，排程序很方便，但要改变FFT的程序和参数才能实现。?现介绍第三种IFFT算法，则可以完全不必改动FFT程序。

2.直接利用FFT流图方法的推导1*nk对它取共轭：x(n)?X(k)WN?Nk?0N?11*nk*?x(n)?[?X(k)WN](取共轭再取共轭）Nk?01**?{DFT[X(k)]}此为DFT可用FFT程序NN?1nk与X(k)??x(n)WN比较＊n?01x(n)?N?X(k)Wk?0N?1?nkNN?1可知：只须将频域成份一个求共轭变换，即（1）将X(k)的虚部乘以-1，即先取X(k)的共轭，得X*(k)。(2)将X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换，并乘以常数1/N，即可以求出IFFT变换的x(n)的值。

3.直接利用FFT流图方法的注意点

（1）FFT与IFFT连接应用时，注意输入输出序列的排列顺序，即应注意是自然顺序还是倒序。

（2）FFT和IFFT共用同一个程序时，也应注意利用FFT算法输入输出的排列顺序，即应注意自然顺序还是例位序

（3）当把频率抽取FFT流图用于IDFT时，应改称时间抽取IFFT流图。

（4）当把时间抽取FFT流图用于IDFT时，应改称频率抽取IFFT流图。

作业

?用C语言完成N=1024点的IDIT，IDIF。

第六节线性调频Z变换

一、引入

?以上提出FFT算法，可以很快地求出全部DFT值。即求出有限长序列x(n)的z变换X(z)在单位园上N个等间隔抽样点zk处的抽样值。它要求N为高度复合数。即N可以分解成一些因子的乘积。例N=2L

?实际上：（1）也许对其它围线上z变换取样发生兴趣。如语音处理中，常常需要知道某一围线z变换的极点所处的复频率。

?（2）只需要计算单位圆上某一段的频谱。如窄带信号，希望在窄带频率内频率抽样能够非常密集，提高分辨率，带外则不考虑。

?（3）若N是大素数时，不能加以分解，又如何有效计算这种序列DFT。例N=311，若用基2则须补N=28=512点，要补211个零点。

二、问题提出

?由上面三个问题提出：

?为了提高DFT的灵活性，须用新的方法。?线性调频z变换(CZT)就是适用这种更为一般情况下，由x(n)求X(zk)的快速变换?CZT：来自于雷达专业的专用词汇。

三、算法原理

1.定义

?Z 变换采用螺线抽样, 可适用于更一般情况下由x(n) 求X(zk) 的快速算法, 这种变换称为线性调频Z 变换( 简称CZT ).

2.CZT公式推导1

?已知x(n) ，0≤n≤N-1,则它的z变换是：

X（z)??x(n)zn?0N?1?n?为适应z可以沿平面内更一般的路径取值，故：沿z平面上的一段螺线作等分角的抽样，则z的取样点Zk可表示为：

zk?A?,k?0,1,?M?1?其中M：表示欲分析的复频谱的点数。M不一定等于N。A，?都为任意复数。

?kA?A0e?j?0,???0e?j?02.CZT公式推导2将zk代入X(z)中N?1n?0得CZT[x(n)]?X(zk)??x(n)zn?0?nnkN?1?nk??x(n)A?,k?0,1,?M?1即X(zk)就是X(z)在给定的更为一般的轨迹Zk上的取值。我们利用Bulestein布鲁斯坦所提出的等式1222nk?[n?k?(k?n)]2222N?1n?0?nnkk2N?12n?0n22n?0?(k?n)22?X(zk)??x(n)A?????x(n)A???nN?1n2?(k?n)2?k2?[x(n)A?n?]?2.CZT公式推导3n2令g(n)?x(n)A?2,n?0,1?N?1h(n)??n2?2k2N?12n?0?nn?0,1?M?1?X(zk)???g(n)h(k?n),k?0,1,?,M?1k22由上式可知：zk点的z变换值X(zk)k22可以通过g(n)与h(n)的离散卷积值并乘?得到，即：X(zk)??[g(n)?h(n)],k?0,1,?,M?1这里g(n)与h(n)的离散卷积可以用g(n)与h(n)的圆周卷积来实现。而圆周卷积可用FFT的方法来求得。3.用CZT求解DFT的流图x(n)g(n)h(n)?WA??nn22n2?2G(k)X(zk)?k22

本文来源：https://www.bwwdw.com/article/7no3.html