FFT算法设计(含程序设计).ppt
第第6讲讲 FFT算法设计算法设计v傅立叶变换将信号从时域转换为频域，可以进行傅立叶变换将信号从时域转换为频域，可以进行模拟信号的频率分析模拟信号的频率分析v离散傅立叶变换离散傅立叶变换(DFT)将信号从频域转换为数字将信号从频域转换为数字(频频)域，可以进行数字信号（模拟信号数字化）域，可以进行数字信号（模拟信号数字化）的频率分析的频率分析v为了实现为了实现DFT在计算机上的快速实现，提出了快在计算机上的快速实现，提出了快速离散傅立叶变换速离散傅立叶变换(FFT)如何有傅氏变换如何有傅氏变换-DFT-FFT?v欧拉公式：欧拉公式：v=v令令 ,称为旋转因子称为旋转因子v=v上式中，上式中，k对应数字域，对应数字域，n对应时域对应时域sincosjejdtetfdtetfdtetfFtjwtjwtjwt100)()()()(1,.,2 , 1 , 0,)()(102NkenxkXNnknNjNjNeW21,.,2 , 1 , 0,)()(10NkWnxkXNnknNv另有推导时需用到的公式：另有推导时需用到的公式：1） ,l N为为l个周期个周期 2） ,N-m为加上一个周期为加上一个周期3) ,其中其中4）lNNjmNjlNmNjlNmNeeeW22)(2*mNmNjWe2)(2)*(2mNNjmNjmNeeWmNNWjmNjNNjmNjNmNjNmNeeeeeW*22*22)2(22mNW1)sin()cos(jejmkNmkNjkmNjkmNWeeW*2/2/周期性周期性对称性对称性可约性可约性周期性周期性推导分析推导分析v若序列若序列x(n)的长度为的长度为N，且满足，且满足N=2M,(M为自然数为自然数)按按n的奇偶性把的奇偶性把x(n)分解为两个分解为两个N/2的子序列：的子序列：x1(r)=x(2r), r=0,1,N/2 1x2(r)=x(2r+1), r=0,1,N/2 1则则x(n)的的DFT为：为： 奇数偶数nknNnknNWnxWnxkX)()()(12/0)12(12/02) 12()2(NrrkNNrkrNWrxWrxkrNNrkNkrNNrWrxWWrx212/02212/01)()(v = ，k=0,1,N/2 - 1 其中其中X1(k)和和X2(k)均以均以N/2为周期为周期 = = ，k=0,1,N/2 1其中公式其中公式 krNNrkNkrNNrWrxWWrx2/12/022/12/01)()()()()(21kXWkXkXkN)2()2()2(221NkXWNkXNkXNkN)()()2(21kXWkXNkXkN)()()2()()()(2121kXWkXNkXkXWkXkXkNkN称为蝶形运算称为蝶形运算ABCA+BCA-BCv 同理，可推出：同理，可推出： ， k=0,1,N/4 - 1 ， k=0,1,N/4 1 分到最后，分到最后，k=0，进行蝶形运算的两个输入就是最初输入序，进行蝶形运算的两个输入就是最初输入序列列x(n)的其中两个。的其中两个。)()()4()()()(42/3142/31kXWkXNkXkXWkXkXkNkN)()()4()()()(62/5262/52kXWkXNkXkXWkXkXkNkN蝶形分解图示蝶形分解图示N/4点DFTN/4点DFTN/4点DFTN/4点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN/20WN/21WN/20WN/21WN0WN1WN2WN3X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)X2(0)X2(3)X2(2)X2(1)N=8点点FFT运算图示运算图示x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN2WN0WN2WN0WN1WN2WN3A(0)A(1)A(2)A(3)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)WN0WN0WN0WN0A(4)A(7)A(6)A(5)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)N=16点点FFT运算图示运算图示x(0)x(8)x(4)x(12)x(2)x(10)x(6)x(14)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN4WN0WN4WN0WN2WN4WN6A(0)A(1)A(2)A(3)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)WN0WN0WN0WN0A(4)A(7)A(6)A(5)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)x(1)x(9)x(5)x(13)x(3)x(11)x(7)x(15)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)WN0WN4WN0WN4WN0WN2WN4WN6A(8)A(9)A(10)A(11)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)WN0WN0WN0WN0A(12)A(15)A(14)A(13)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)WN0WN1WN2WN3WN4WN5WN6WN7蝶形运算规律蝶形运算规律 设序列设序列x(n)已经经过时域抽选已经经过时域抽选(倒序倒序)后，存入数组后，存入数组X中。如中。如果蝶形运算的两个输入相距果蝶形运算的两个输入相距B个点，用原位计算（即计算结果个点，用原位计算（即计算结果还放在数组的原来位置），则蝶形运算可表示成如下形式：还放在数组的原来位置），则蝶形运算可表示成如下形式： =IRpNLjTTWBJXT)(1)()()(1JjXJXJXIRL)()()(1BJjXBJXBJXIRL(3)(4)(5)pNIRpNLWBJjXBJXWBJX)()()(1)2sin2)(cos()(pNjpNBJjXBJXIR2sin)(2cos)(2sin)(2cos)(pNBJXpNBJXjpNBJXpNBJXRIIRIRjTT pNBJXpNBJXTpNBJXpNBJXTRIIIRR2sin)(2cos)(2sin)(2cos)(6)(7) =公式公式(7)(8)(9)主要用于主要用于FFT的软件编程的软件编程)()()(JjXJXJXIRLIRLjTTJX)(1由由(1)(6)式推导得出式推导得出IRIRjTTJjXJX)()(由由(4)式推导得出式推导得出IIIRRRTJXJXTJXJX)()()()()()()(1IRLLjTTJXBJX由由(2)(6)式推导得出式推导得出)()()(IRIRjTTJjXJX由由(4)式得出式得出IIIRRRTJXBJXTJXBJX)()()()(9)(8)pNBJXpNBJXTpNBJXpNBJXTRIIIRR2sin)(2cos)(2sin)(2cos)(IIIRRRTJXJXTJXJX)()()()(开始送 入 x(n), N, M输 入 序 列 倒 序L=1, MB p=j*2M-L (变量为变量为j,L)kjnpNWW*jkNW/jLW2jMLMW2*2LMMLMLjNjNjNWWW2*2/2*3.每个每个p对应每级中的运算个数为：对应每级中的运算个数为： 第第L级中，每个蝶形的两个输入数据相距级中，每个蝶形的两个输入数据相距B=2L-1点点 同一旋转因子对应着间隔为同一旋转因子对应着间隔为2L点的点的2M-L个蝶形个蝶形看图推导方法二：看图推导方法二：x(0)x(8)x(4)x(12)x(2)x(10)x(6)x(14)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN0WN4WN0WN4WN0WN2WN4WN6A(0)A(1)A(2)A(3)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)WN0WN0WN0WN0A(4)A(7)A(6)A(5)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)x(1)x(9)x(5)x(13)x(3)x(11)x(7)x(15)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)WN0WN4WN0WN4WN0WN2WN4WN6A(8)A(9)A(10)A(11)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)WN0WN0WN0WN0A(12)A(15)A(14)A(13)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)A(0)A(1)A(2)A(3)A(4)A(7)A(6)A(5)A(8)A(9)A(10)A(11)A(12)A(15)A(14)A(13)WN0WN1WN2WN3WN4WN5WN6WN7L=1L=2L=3L=4=M有有1个蝶形块，个蝶形块，pi=1有有2个蝶形块个蝶形块pi=24个蝶形块个蝶形块pi=48个块个块pi=8pi定义为定义为p的增量的增量321028pi1324pi222pi121pi时，当时，当时，当时，当MLMLMLML反推反推=123042pi12pi22pi3222pi4MMMMMMLLLL时，当时，当时，当时，当= pi = 2M-L令令p=J*pi=J*2M-L (其中其中J=0,1,2,3,)，这样写是为了利于软件，这样写是为了利于软件 的循环编程。此时只要求出每级的循环编程。此时只要求出每级J的个数的个数JTotal即可即可3Total2Total1Total0Total28J424J322J221J1时，当时，当时，当时，当LLLL= JTotal=2L-1得：得：p = J*2M-L (J=0,1,2,2L-1-1) J的总个数的总个数JTotal为为2L-1， 每一级每一级p的总个数也为的总个数也为2L-1v 外循环次数为级数外循环次数为级数Lv 中循环为根据当前中循环为根据当前L求出各个不同的求出各个不同的p，循环次，循环次 数为数为p的个的个数数2L-1v 内循环为每级中每个内循环为每级中每个p对应的蝶形运算个数对应的蝶形运算个数(记为记为VTotal)，循，循环次数为环次数为2M-L 0Total1Total2Total3Total21J422V324V228V1时，当时，当时，当时，当LLLL=VTotal = 2M-L每个蝶形的两个输入数据间隔（记为每个蝶形的两个输入数据间隔（记为INd）：）：= INd = 2L-1同一级中每个相同的同一级中每个相同的p对应蝶形运算的间隔（记为对应蝶形运算的间隔（记为Vd）：）：321028I424I322I221I1ddddNLNLNLNL时，当时，当时，当时，当4321216V428V324V222V1ddddLLLL时，当时，当时，当时，当= Vd = 2L可以看出，为了利于编程，所有的公式推导都往可以看出，为了利于编程，所有的公式推导都往L上靠上靠输入序列倒序的算法设计输入序列倒序的算法设计顺序顺序倒序倒序十进制数十进制数I二进制数二进制数 二进制数二进制数 十进制数十进制数J0000000010011004201001023011110641000011510110156110011371111117顺序与倒序二进制数对照表顺序与倒序二进制数对照表倒序规律倒序规律x(0) x(1) x(2) x(3) x(4
