[工学]数字信号处理[第四章_快速傅里叶变换FFT.ppt

1、第四章 快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,离散傅里叶变换（DFT）,N次复数乘法，N1次复数加法,N,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,时域抽取法FFT（DIT-FFT）,频域抽取法FFT（DIF-FFT）,基2快速傅里叶算法,IDFT的高效算法,运算流图,以 N4为例,快速傅里叶变换（FFT）,时域抽取法FFT（DIT-FFT）,快速傅里叶变换（FFT）,蝶形运算,试画出N8的DFT的一次时域抽取分解图,快速傅里叶变换（FFT）,-1,-1,-1,-1,2个N/2点DFT运算,N/2个蝶形运算,快速傅里叶变换（FFT）,快速傅里叶

2、变换（FFT）,-1,-1,-1,-1,-1,-1,-1,-1,快速傅里叶变换（FFT）,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,快速傅里叶变换（FFT）,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,快速傅里叶变换（FFT）,DIT-FFT算法与直接计算DFT运算量的比较,快速傅里叶变换（FFT）,DIT-FFT的运算规律及编程思想,蝶形运算的规律和通式,旋转因子 的规律性,的存储问题,快速傅里叶变换（FFT）,一、原位计算,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,快速傅里叶变换（FFT）,二、旋转因子

3、,快速傅里叶变换（FFT）,三、蝶形运算规律,快速傅里叶变换（FFT）,四、编程思想及程序框图,开始,送入x(n),M,N=2M,倒序,L=1，M,J=0，B-1,B=2L-1,P=2M-LJ,输出,结束,k=J,N-1,2L,快速傅里叶变换（FFT）,四、序列的倒序,输出是自然序列，输入称为倒位序列，即二进制数倒位,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7

4、1 1 1 1 1 1 7,自然顺序n 二进制n2n1n0 倒位序二进制n0n1n2 倒位顺序n,倒序数则是在M位二进制数最高位加1，逢2向右进位,快速傅里叶变换（FFT）,LH=N/2 J=LH N1=N-2,I=1，N1,I=J,T=X(I) A(I)=X(J) A(J)=T,K=LH,N,JK,Y,J=J+K,J=J-K K=K/2,N,Y,快速傅里叶变换（FFT）,频域抽取法FFT（DIF-FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,-1,-1,-1,-1,快速傅里叶变换（FFT）,-1,-1,-1,-1,-1,-1,-1,-1,快速傅里叶变换（FFT）,-1,-1,

5、-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,快速傅里叶变换（FFT）,比较DIF-FFT算法与DIT-FFT算法的异同点：,1.运算次数相同,2.公式、图形类似,1.DIF-FFT：输入是自然序列，输出是到位序列； DIT-FFT：输入是到位序列，输出是自然序列。,2.DIF-FFT：蝶形运算是先乘后加减； DIT-FFT：蝶形运算是先加减后乘。,快速傅里叶变换（FFT）,FFT的变形运算,支路传输比不变，改变输入点，输出点以及中间节点的排列,快速傅里叶变换（FFT）,IDFT的高效算法,乘法次数增加了（N/2)(M-1）次,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,

6、1.多类蝶形运算,N=2M点FFT共需MN/2次复乘,快速傅里叶变换（FFT）,1.多类蝶形运算,快速傅里叶变换（FFT）,1.多类蝶形运算,快速傅里叶变换（FFT）,1.多类蝶形运算,快速傅里叶变换（FFT）,2.旋转因子的生成,快速傅里叶变换（FFT）,3.实序列的FFT算法,例1：设x(n)是长度为2N的有限长实序列，X(k)为x(n)的2N点 DFT。要求：试设计用一次N点FFT完成计算X(k)的高效算法。,解： 本题的解题思路是DITFFT思想； 在时域分别抽取偶数点和奇数点x(n)，得到两个N点实序列x1(n)和x2(n)： x1(n) = x(2n) , n = 0, 1, ,

7、N-1x2(n) = x(2n+1) , n = 0, 1, , N-1 根据DITFFT的思想，只要求得x1(n)和x2(n)的N点DFT，再经过简单的一级蝶形运算就可得到x(n)的2N点DFT。 因为x1(n)和x2(n)均为实序列，所以根据DFT的共轭对称性，可用一次N点FFT求得X1(k)和X2(k)。做法如下：,令y(n) = x1(n) + jx2(n) Y(k) = DFTy(n) 则 X1(k)=DFTx1(n)=Yep(k)=Y(k)+Y*(N-k)/2 jX2(k)=DFTx2(n)=Yop(k)=Y(k)-Y*(N-k)/2 2N点DFTx(n) = X(k)可由X1(k

8、)和X2(k)得到： X(k) = X1(k) + W2NkX2(k) X(k+N) = X1(k) - W2NkX2(k) , k=0, 1, , N-1 这样，通过一次N点FFT计算完成了计算2N点DFT。,例2： 设x(n)是长度为2N的有限长实序列，X(k)为x(n)的2N点DFT。若已知X(k)，要求：试设计用一次N点IFFT完成计算x(n )的高效算法。,解：设 x1(n) = x(2n) , n = 0, 1, , N-1 x2(n) = x(2n+1) , n = 0, 1, , N-1 X1(k) = DFTx1(n) , k = 1, 1, , N-1 X2(k) = DF

9、Tx2(n) , k = 1, 1, , N-1 由DITFFT的算法，有以下关系式： X(k) = X1(k) + W2NkX2(k) , k = 1, 1, , N-1 X(k+N) = X1(k) - W2NkX2(k) 由以上两可解出X1(k)和X2(k) 。,X1(k) = X(k) + X(k+N)/2 X2(k) = W2N-kX(k) X(k+N)/2 由上面分析可得出运算过程如下： （1）由X(k)计算出X1(k)和X2(k)； （2）由X1(k)和X2(k)构成N点频域序列Y(k)： Y(k) = X1(k) + jX2(k) = Yep(k) + Yop(k) 其中Yep

10、(k) = X1(k)，Yop(k) = jX2(k)，进行N点IFFT运算，得到 y(n) = IFFTY(k) = Rey(n) + jImy(n) , n = 0, 1, , N-1 由DFT的共轭对称性 Rey(n) = y(n)+y*(n)/2 = DFTYep(k) = x1(n) jImy(n) = y(n)-y*(n)/2 = DFTYop(k) = jx2(n) 由x1(n)和x2(n)合成x(n)： 当n = 偶数（n = 0 , 1 , , 2N-1）时 x(n) = x1(n/2) 当n = 奇数（n = 0 , 1 , , 2N-1）时 x(n) = x2(n-1)/

11、2),快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,L形蝶形图,一个N点DFT可分解成一个N/2点DFT和两个N/4点DFT,快速傅里叶变换（FFT）,-1,-1,-j,-1,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,计算出X(k)的前N/2个值，则后N/2个值可求,快速傅里叶变换（FFT）,证明：,快速傅里叶变换（FFT）,证明：,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,快速傅里叶变换（FFT）,1.DHT是实值变换,2.DHT的正反变换具有相同形式,DHT的主要优点：,3.DHT与DFT间的关系简单,快速傅里叶变换（FFT）,1.DFT的线性,快速傅里叶变换（FFT）,2.X(N-n）的DHT,快速傅里叶变换（FFT）,证明：,快速傅里叶变换（FFT）,3.循环移位性质,快速傅里叶变换（FFT）,证明：,快速傅里叶变换（FFT）,4.奇偶性,快速傅里叶变换（FFT）,5.循环卷积定理,快速傅里叶变换（FF