数字信号处理教案第4章课件

1、第四章 快速傅立叶变换（FFT） Fast Fourier Transform 数字信号处理1 4.1 引言 DFT 是数字信号处理的基础，是 一种重要变换。 快速算法的引出，使数字信号处 理技术得到广泛应用。 各种快速算法不断被采用2数字计算机N足够大.1.1 DFT提供了计算机处理的可能性 模拟信号的频谱分析 4.1.2 DFT的运算量 k=0,1,2,N1计算机运算时： 3N项 N个 计算一个 N点DFT ，共需次复乘。以做一次复乘1s计，若N =4096，所需时间为由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。4 长期以来，人们一直在寻求一种能提高DFT运算速

2、度的方法。FFT便是Cooley&Tukey 在1965 年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。4.1.3 FFT算法的设计思想 1利用的特点具有 1）周期性 52）共轭性 3）对称性 4）恒等性5）可约性2把N 点DFT化为几组点数较少的DFT运算 N点DFT运算的复乘次数为次，若将N点DFT化为2 组，则复乘次数约为次。64.2 基 2 抽取FFT 算法（the Decimation-In-Time Radix-2 FFT Algorithm）FFT分为两大类：时域抽取FFT（Decimation-In-Time FFT，简称DIT-

3、FFT）频域抽取FFT（Decimation-In-Frequency FFT， 简称DIF-FFT）7 4.2.1 直接计算DFT的问题及改进的途径 k=0, 1, , N-1n=0, 1, , N-1DFT及IDFT的定义8可见，DFT 与 IDFT 的计算成本基本相同。直接计算N点DFT 时：对应一个k需要N次复数乘和（N-1）次复数加；对所有N个k值，则需要 N复数乘和N (N-1)次复数加 。其中:一次复数乘需要4次实数乘和2次实数加方能完成。当N较大时，运算量很大。9 例如：当N=8时，DFT需要64次复数乘；当N=1024时，DFT所需复数乘为1048576次，即一百多万次复数乘

4、。为了减少运算次数，改进计算的方法：1）利用旋转因子的对称性、周期性和可约性； 旋转因子（twiddle factor）2）使长序列变短。104.2.2 基2时域抽取法原理 （库利-图基算法）设序列x（n）的长度为N，且M为自然数N-point DFT,N is even11将其一分为二，分成偶数和奇数序列项（the even-indexed and odd-indexed terms）则N/2点的序列为： even: x1(r)=x(2r) , r=0, 1, , N/2-1 odd: x2(r)=x(2r+1) , r=0, 1, , N/2-112偶数序列 the range: 02nN

5、-2 (N is even) 0n(N/2)-1奇数序列 the range: 12n+1N-1 (N is even) 02nN-2 0n(N/2)-113 则x（n）的DFT：14由于所以k=0,1,N-115上式说明,按n的奇偶性将 分解为两个N/2长的序列 和 ,则N点DFT可分解为两个N/2点的DFT来计算.16 其中 N/2-point DFT: k=0,1,N/2-1 k=0,1,N/2-117因此，可写出两个N/2点的方程:18 而19同理而20所以21表示上述算法可用蝶形结（ butterfly）22 Example : 如N=4 x(n)=x0, x1, x2, x3 ev

6、en: x0, x2 even: x0 odd: x2 odd: x1, x3 even: x1 odd: x323 bit reversal/shuffling process 混序或反序码位倒置分成四个1点的序列 24 the butterfly（蝶形运算）1点序列的DFT就是序列本身，即不用计算 -1-1-1-125 如N4，则将 x1(r) 再按r的奇偶进一步分解成两个N/4点长的子序列：2627 其中28由X3（k）和X4（k）的周期性和 的对称性，得29同理，得30 其中31 8点DIT-FFT运算流图32 4.2.3 IDFT的高效算法这样IFFT可与FFT用同一子程序实现。33

7、IDFT的运算规律34 求IFFT，也可用DIT-FFT的流程来实现。35 Example:Determine the x(n) by IDFT.X=5, -1, 1, -1 Solution: n=0,1,2,33637 所以 x(n)=1, 1, 2, 1 38%the program in MATLAB: X=input(Please input X=); N=length(X); x=fft(conj(X),N); x=conj(x/N)39 Example :用FFT算法计算下面信号的 8点DFT； x(n)=4 3 2 0 1 2 3 1然后，再用 IFFT恢复原信号。40 sol

8、ution:22222241 IFFT(X)=1/NFFT(X*)*2222222222222222乘以1/N=1/8得原序列42 4.2.4 FFT的计算成本最简单的FFT 是Cooley-Tukey法因为N点DFT有M级蝶形运算，每一级都有N/2个蝶形运算结构；每个蝶形运算结构都有1次复数乘和2次复数加；43 44所以，M级蝶形运算有复数乘M级蝶形运算有复数加45直接DFT的复数乘和复数加均近似为 。当N1时，所以DIT-FFT大大减少了运算次数。46 Example : for N=8 Solution : M= =3 stages（三级） for FFT, the total cost

9、 is （FFT的总计算成本是） MN/2=38/2=12 complex multiplications （复数乘）47 for directly DFT, the total cost is（直接计算DFT的成本是） N=8=64 (complex multiplications) The ratio is: （比值是） 实际上，当N=2048时，直接运算与 FFT算法的计算量之比为372.448 4.2.5 DIT-FFT的运算规律及编程思想1、原位运算：利用同一单元存储蝶形计算的输入、输出数据。每个蝶形的输入和输出均为相同位数。原位运算可节省大量内存，因而硬件成本低。2、旋转因子的变化

10、规律： N点DFT，共有M级蝶形运算，每级有N/2个蝶形。49 称为旋转因子，p称为旋转因子的指数。 为了编写程序，应找出旋转因子 与运算 级数的关系。 设L=1，2，M，表示从左到右的运算 级数，第L级有 个不同的旋转因子，50对于 ，各级的旋转因子表示为L=1时，L=2时，L=3时，51对于 的一般情况，第L级的旋转因子为，由于52所以通过上式，可以计算第L级运算的旋转因子。53 3、蝶形运算规律设序列x（n）经过时域倒序存入数组X如蝶形运算的两个输入数据相距B个点，应用原位运算，可得：54 4、编程思想及程序框图其它运算规律：第L级中，每个蝶形的两个输入数据相距 个点；同一旋转因子对应着

11、间隔为 点的 个蝶形（对应第几组蝶形）55 8点DIT-FFT运算流图56编程的运算方法：从输入端（第1级）开始，逐级进行，共进行M级运算。在进行第L级运算时，依次求出 个不同的旋转因子，然后计算其对应相同的旋转因子的 个蝶形。可用三重循环程序实现DIT-FFT运算。57(3)585、序列的倒置（bit reversal）倒序是有规律的。由于 ，所以顺序数可用M位二进制数（ ）表示。59用硬件电路和汇编语言程序产生倒序很容易，用高级语言倒序的规律为：倒序数是在M位二进制数最高位加1，逢2向右进位。604.2.6 频率抽取法FFT(DIF-FFT)设序列x（n）长度为 ，将其前后对半分开，得：6

12、1式中62再将X（k）分解成偶数组和奇数组 k为偶数时：63k为奇数时：64令65得66 DIF-FFT蝶形运算流图-+67N=8时，DIF-FFT蝶形运算流图68注意：DIT-FFT和DIF-FFT的算法流图不 是唯一的。 其变形运算流图见P108。69 4.3 进一步减少运算量的措施以程序的复杂度换取计算量的进一步提高。4.3.1 多类蝶形单元运算第一级旋转因子可简化：第二级旋转因子可简化：称为无关紧要的旋转因子。70其复数乘法次数可减少为： CM（2）=（M-2）*N/2当L=3时，第三级蝶形有两个无关紧要旋转因子，同一因子对应2(M-L)=N/2L级蝴蝶结,所以第三级共有(书110页)71依次类推，从L=3到L=M共可减少复数乘法次数为：DIT-FFT的复数乘法次数为：72另外，也可用实数乘法减少计算量。包含所有旋转因子称为一类蝶形单元运算；去掉 为二类；去掉 为三类；依次类推，称为多类蝶形单元运算。N=4096时，三类与一类比，仅75%。734.3.2 旋转因子的生成 直接查表，提高速度，多占