数字信号处理-第5章

学习目标理解按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解IFFT算法理解FFT算法的应用第4章快速傅里叶变换FFT:FastFourierTransform1965年，Cooley,Tukey《机器计算傅里叶级数的一种算法》一、直接计算DFT的问题及改进途径运算量复数乘法复数加法一个X(k)NN–1N个X(k)N2N(N–1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)4N22N(2N–1)【例】：对一幅N×N点的二维图像进行DFT变换，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解：直接计算DFT所需复乘次数为因此用每秒可做10万（）次复数乘法的计算机，秒）。则需要近3000小时（这对实时性很强的信号处理来说，要么提高计算速度，而这样，对计算机速度的要求太高了。所以，只能通过改进对DFT的计算方法，以大大减少运算次数。FFT算法分类:时间抽选法 DIT:Decimation-In-Time频率抽选法 DIF:Decimation-In-Frequency§4.2按时间抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。若不满足，则补零将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。则x(n)的DFT:再利用周期性求X(k)的后半部分蝶形运算符号8点DFT一次时域抽取分解运算流图分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半N/2仍为偶数，进一步分解：N/2N/4由两个N/4点的DFT组合成一个N/2点的DFT同理：其中：8点DFT二次时域抽取分解运算流图这样逐级分解，直到2点DFT当N=8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1

8点DIT-FFT运算流图2、运算量当N=2M时，共有M级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DFT【例】：用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？

解：当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为：次仅为直接计算DFT（次）所需时间的10万分之一。

即原需要3000小时，现在只需要不到2分钟。3、算法特点1）原位计算m表示第m级迭代，k，j表示数据所在的行数2）倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n200011011001101变址处理方法倒位序实现

反序二进制数N=8时的自然顺序二进制数和相应的倒位序二进制数0426153700010001011000110101111100000101001110010111011101234567倒位序（J）二进制数自然顺序（I）3）蝶形运算的碟距即：两输入节点间“距离”对N=2M点FFT，输入倒位序，输出自然序，第m级运算每个蝶形的两节点距离为2m–1例如N=8=23,第一级(列)距离为21-1=1,第二级(列)距离为22-1=2，第三级(列)距离为23-1=4。L表示从左到右的运算级数（L=1，2，…，M）。第L级共有2L–1个不同的旋转因子。对N=2M的一般情况，第L级的旋转因子为：WNP=W2LJJ=0，1，2，…，2L-1-14）旋转因子的确定

5）存储单元存输入序列x(n):N个存储单元(n=0,1,,N-1)存系数：N/2个存储单元[P=0,1,,（N/2）-1,]共计(N+N/2)个存储单元三、按频率抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：按k的奇偶将X(k)分成两部分：令则X(2r)和X(2r+1)分别是x1(n)和x2(n)的N/2点DFT，记为X1(k)和X2(k)DIF-FFT第一次分解运算流图（N=8）N/2仍为偶数，进一步分解：N/2N/4同理：其中：逐级分解，直到2点DFT当N=8时，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1DIF-FFT运算流图（N=8）2、算法特点1）原位计算-1L级蝶形运算，每级N/2个蝶形，每个蝶形结构：

m表示第m级迭代，k，j表示数据所在的行数2）蝶形运算对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-m=N/2m例如N=23=8(1)m=1时的距离为8/2=4；(2)m=2时的距离为8/4=2;(3)m=3时的距离为8/8=13、DIT与DIF的异同基本蝶形不同DIT:先复乘后加减DIF:先减后复乘运算量相同都可原位运算DIT和DIF的基本蝶形互为转置四、IFFT算法比较：IDFT:DFT:由DIF-FFT运算流图改成的DIT-IFFT运算流图如下所示：共轭FFT共轭乘1/N直接调用FFT子程序计算IFFT的方法：§4.3实序列的FFT算法问题的提出在实际工作中，数据x(n)常常是实数序列。如果直接按FFT运算流图计算，就是把x(n)看成一个虚部为零的复序列进行计算，这就增加了存储量和运算时间。处理该问题的方法有两种。一、一个N点FFT同时计算两个N点实序列的FFT

设x1(n)，x2(n)是两个N点实序列，它们的离散傅里叶变换分别为:构造一个新的复序列其对应的DFT变换为

根据第三章中有关复数序列的共轭（奇偶）对称特性二、一个N点FFT运算一个2N点实序列设x(n)是2N点的实序列，我们人为地将x(n)分为