资源描述：
《FFT算法设计(含程序设计).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第6讲FFT算法设计傅立叶变换将信号从时域转换为频域，可以进行模拟信号的频率分析离散傅立叶变换(DFT)将信号从频域转换为数字(频)域，可以进行数字信号（模拟信号数字化）的频率分析为了实现DFT在计算机上的快速实现，提出了快速离散傅立叶变换(FFT)如何有傅氏变换->DFT->FFT?欧拉公式：=>令,称为旋转因子=>上式中，k对应数字域，n对应时域另有推导时需用到的公式：1）,lN为l个周期2）,N-m为加上一个周期3),其中4）周期性对称性可约性周期性推导分析若序列x(n)的长度为N，且满足N=2M,(M为自然数)按n的奇偶性把x(n)分解为两个N/2的子序列：x1(r)=x(2r
2、),r=0,1,…,N/2–1x2(r)=x(2r+1),r=0,1,…,N/2–1则x(n)的DFT为：=>，k=0,1,…,N/2-1其中X1(k)和X2(k)均以N/2为周期=>=>，k=0,1,…,N/2–1其中公式称为蝶形运算同理，可推出：，k=0,1,…,N/4-1，k=0,1,…,N/4–1……分到最后，k=0，进行蝶形运算的两个输入就是最初输入序列x(n)的其中两个。蝶形分解图示N=8点FFT运算图示N=16点FFT运算图示蝶形运算规律设序列x(n)已经经过时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入相距B个点，用原位计算（即计算结果还放在数组的原来位置），
3、则蝶形运算可表示成如下形式：<=其中：p=J*2M-L;J=0,1,…,2L-1-1L=1,2,…,M下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可由下面的算法进行：(1)(2)设：下标R表示实部下标I表示虚部X’R(J)代表上一次的实数值=>=>(3)(4)(5)(6)(7)=>=>公式(7)(8)(9)主要用于FFT的软件编程由(1)(6)式推导得出由(4)式推导得出由(2)(6)式推导得出由(4)式得出(9)(8)公式中的J就是流程图中公式的变量k，流程图中：N表示阶数，M表示总级数，L表示当前级数，B表示每个蝶形的两
4、个输入数据的间隔，P表示旋转因子指数可以看出，流程图总共有3个循环外循环：次数为级数L的变换范围中循环：为根据当前L求出各个不同的p，循环次数为p的个数2L-1内循环：为每级中每个p对应的蝶形运算个数，循环次数为2M-L内循环中k值每次变换范围(增量)为2L,这是同一级中每个相同的p对应不同蝶形运算的间隔。看图推导软件编程规则：方法一目的是求出旋转因子指数p的变化规律1.当N=8时，第L级共有2L-1个不同的旋转因子。因为N=2M，所以有L=1,2,…,M，即L的最大值为M当L=1时,p=0;(p称为旋转因子指数)当L=2时,p=0,2;k=2(k为p的增量)当L=3时,p=0,1,2
5、,3;k=1当N=16时当L=1时,p=0;当L=2时,p=0,4;k=4当L=3时,p=0,2,4,6;k=2当L=4时,p=0,1,2,3,4,5,6,7;k=12.(j=0,1,2,3,…)(归纳得出：N/k=2L)(L=1,2,3,…表当前级数)(M表总级数)(j=0,1,2…2L-1-1)=>p=j*2M-L(变量为j,L)3.每个p对应每级中的运算个数为：第L级中，每个蝶形的两个输入数据相距B=2L-1点同一旋转因子对应着间隔为2L点的2M-L个蝶形看图推导方法二：L=1L=2L=3L=4=M有1个蝶形块，pi=1有2个蝶形块pi=24个蝶形块pi=48个块pi=8pi定义
6、为p的增量反推=>=>pi=2M-L令p=J*pi=J*2M-L(其中J=0,1,2,3,…)，这样写是为了利于软件的循环编程。此时只要求出每级J的个数JTotal即可=>JTotal=2L-1得：p=J*2M-L(J=0,1,2,…,2L-1-1)J的总个数JTotal为2L-1，每一级p的总个数也为2L-1外循环次数为级数L中循环为根据当前L求出各个不同的p，循环次数为p的个数2L-1内循环为每级中每个p对应的蝶形运算个数(记为VTotal)，循环次数为2M-L=>VTotal=2M-L每个蝶形的两个输入数据间隔（记为INd）：=>INd=2L-1同一级中每个相同的p对应蝶形运算的
7、间隔（记为Vd）：=>Vd=2L可以看出，为了利于编程，所有的公式推导都往L上靠输入序列倒序的算法设计顺序倒序十进制数I二进制数二进制数十进制数J0000000010011004201001023011110641000011510110156110011371111117顺序与倒序二进制数对照表倒序规律对于N=2M，M位二进制数最高位的权值为N/2，且从左向右二进制位的权值依次为N/4,N/8,…,2,1。因此，最高位加1相当于十进制运算J+
