第五节快速傅里叶变换DFT是利用计算机进行信号谱分析的理论依据，但计算量太大；快速傅立叶变换是以较少计算量实现DFT的快速算法，FFT是数字信号处理中最基本的算法。本节分析直接计算的工作量及DFT的特点，最后研究基2时析型FFT（基2时间抽选法）一、DFT直接运算的工作量第29页，共59页，星期日，2025年，2月5日计算机运算时（编程实现）：N次复乘，N-1次复加N个点第30页，共59页，星期日，2025年，2月5日复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)运算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)第31页，共59页，星期日，2025年，2月5日第五节快速傅里叶变换按定义计算，需要次复数乘和(N-1)N次复数加运算，若序列为复数，则每次复数乘包括4次实数乘和2次实数加，每次复数加包含2次实数加，因此对于长度为N的序列，运算总共有4次实数乘和2+2(N-1)N次实数加。随着N的增加，实时处理就无法实现。第32页，共59页，星期日，2025年，2月5日例：计算一个N点DFT，共需N2次复乘。以做一次复乘1μs计，若N=4096，所需时间为例：石油勘探，有24个通道的记录，每通道波形记录长度为5秒，若每秒抽样500点/秒，1）每通道总抽样点数：500*5=2500点2）24通道总抽样点数：24*2500=6万点3）DFT复乘运算时间：N2=(60000)2=36*108次第33页，共59页，星期日，2025年，2月5日由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。长期以来，人们一直在寻求一种能提高DFT运算速度的方法。FFT便是CooleyTukey在1965年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。第34页，共59页，星期日，2025年，2月5日第五节快速傅里叶变换二、DFT运算的特点（从公式入手，利用自身运算特点，提出解决问题的方法）1．的周期性，即对变量n和k，均为周期函数2．的对称性利用周期性和对称性，使W中的元素许多变成相等的，从而减少计算量。除此之外，将大点数DFT转化为小点数DFT，也可以减少DFT的计算量。其中l和m为整数。第35页，共59页，星期日，2025年，2月5日第五节快速傅里叶变换二、基2时析型FFT算法（时间抽取法）输入序列的长度是2的整数次幂1.算法原理对长度为（L为正整数，若原序列的长度不满足此条件，则可用零补足）的序列x(n),按序列各项序号的奇偶将序列分成两个子序列（大点数化为小点数），有偶序号序列奇序号序列第36页，共59页，星期日，2025年，2月5日上式中分别为的N/2点DFT，即：这是前N/2点DFT第37页，共59页，星期日，2025年，2月5日对于后N/2点的DFT显然，可采用蝶式运算图来表示上述前N/2和后N/2两式，如下图所示：第38页，共59页，星期日，2025年，2月5日X(n)的DFT最后结果根据奇偶对分，最后一定能得到N个单项序列（序列长度为1），而单项序列的DFT就是其本身。计算N项序列的DFT，只需要按照碟形算法逐次合成，由N个1点长序列的DFT合成N/2个2点长序列的DFT，再由N/2个2点长序列的DFT合成N/4个4点长序列的DFT，依次进行，最后得到N点长序列的DFT。第39页，共59页，星期日，2025年，2月5日第40页，共59页，星期日，2025年，2月5日第41页，共59页，星期日，2025年，2月5日第42页，共59页，星期日，2025年，2月5日第4章离散傅里叶变换第1页，共59页，星期日，2025年，2月5日《测试信号分析与处理》课程第五节快速傅里叶变换第六节IDFT的快速算法（IFFT）第七节实序列的FFT高效算法