快速傅里叶变换FFT概要

1、第四章快速傅里叶变换 FFT所谓的快速算法，就是根据原始变换定义算法的运算规律及其中的某些算子的特殊性 质，找出减少乘法和加法运算次数的有效途径，实现原始变换的各种高效算法。一种好的快速算法可使变换速度提高几个数量级。由于快速算法很多，而且还在不断研究和发展。较成熟的算法都有现成的程序。所以， 通过教材中介绍的四种快速算法，主要学习研究快速算法的基本思想和减少运算量的途径， 熟悉各种快速算法的特点、运算效率和适用情况。 为今后研究新的快速算法和合理选用快速算法打好基础。4.1 学习要点4.1.1 直接计算N点DFT的运算量对于N AX k 八 x n wNkn, k =0,1, ,N -1n=

2、9复数乘法次数：2Mc = N复数加法次数：Ac = N N -1当N1时，复数乘法和加法次数都接近为N2次，随着N增大非线性增大。4.1.2 减少运算量的基本途径DFT定义式中只有两种运算：X n与wNkn的乘法相加。所以， wNkn的特性对乘法运算量必有影响。（1）根据的对称性、周期性和特殊值减少乘法运算次数。k£Nk* 对称性：Wn 2 二-WNk，Wn21 k，WnN “ 二 W, 周期性：wNk1N -wNk。 wNkn的特殊值（无关紧要旋转因子）：Wn =1；Wn 4 = 一 j；WN2 - -1。对这些因子不能进行乘法运算。（2） 将较大数N点DFT分解为若干个小数点

3、DFT的组合，减少运算量。这正是FFT 能大量节省运算量的关键。四种快速算法的基本思想及特点根据上述减少运算量的途径，巧妙地在时域或频域进行不同的抽取分解与组合，得到不同的快速算法。下面简要归纳四种快速算法的基本思想和特点。1.基 2 DFT-FFT 算法（1）算法思想：时域£ kM级奇偶抽取，并利用 WN 2二-W,，将N点DFT变成M级蝶形运算。（2）运算量：复数乘法次数：NNMcMlog 2 N22复数加法次数：代=N M 二 Nlog2 N（3）特点：运算流图结构规则，可原位计算，程序简短，应用广泛。2. 基 2 DIF-FFT 算法k（1） 算法思想：频域对X k进行M级奇

4、偶抽取，并利用WN2 +1 ，将N点DFT 变成M级DIF-FFT蝶形运算。（2）运算量及特点与基 2 DIF-FFT相同3. 分裂基快速算法（1）算法思想：基2 FFT算法简单，基4FFT算法效率较高。分裂基是将基2分解和基4分解糅合在一起形成的高效新算法。具体是对每次的频域奇偶抽取的偶数输出使用基2算法（按二进制抽取）（2）运算量：，而奇数输出使用基 4算法（按四进制抽取）。复数乘法次数：122McN log2 NN -1 m399复数加法次数：Ac =N log2 N（3）特点: 在N =2M的快速算法中，分裂基算法的乘法次数最少， 接近理论最小值。比基2 FFT 减少33%，比基4减少

5、11%。 运算流图结构规则，可同址计算，程序简短，便于DSP实现。4.2教材第四章习题解答1如果通用计算机的速度为平均每次复数乘需要5，每次复数加需要 1，用来计算N=1024点DFT，问直接计算需要多少时间。用 FFT计算呢？照这样计算，用 FFT进行快 速卷积对信号进行处理时，估算可实现时处理的信号最高频率。解：当N=1O24=210时，直接计算 DFT的复数运算次数为N2=10242次复数加法计算次数为N（N -1） =1024 1023 =1047552 次直接计算所用计算时间 Td为TD =5 1010242 1047552 10“ = 6.290432s用FFT计算1024点DFT

6、所需计算时间为6 N_6TD=5 10 一 log2N N log 2N 10 一 = 35.84 ms2快速卷积时，要计算一次 N点FFT (考虑到H (k) =DFTh(n)已计算好存入内存)，一次N点IFFT和N次频率复数乘法。所以，计算1024点快速卷积的计算时间约为=2Tf 1024次 复数乘计算时间=71680 七 5 1024 s = 76800s 1024所以，每秒钟处理的采样点数(即采样频率)fs ：1024一6 = 13333.3次/秒。由采样76800如0定理知，可实时处理的信号最高频率为max空 13333.32 一 2=6666.7 HZ应当说明，实际实现时，fmax

7、还要你小一些。这是由于采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分还要计算两次。重叠部分长度与h n长度有关，而且还有存取数据指令周期等。3.已知X(k)和Y(k)是两个N点实序列x(n)和y(n)的DFT，若要从X(k)和Y(k)求x(n)和y(n),为提高运算效率，试设计用一次 N点IFFT来完成。解：因为x(n)和y(n)均为实序列，所以， X(k)和Y(k)为共轭对称序列，jY(k)为共轭反对称序列。可令 X(k)和jY(k)分别作为复序列 F(k)的共轭对称分量和共轭反对称分量,即F(k) =X(k) jY(k) = Fep(k) Fop (k)计算一次N点IFFT得到

8、f (n) =IFFT F(k)二Re f (n) j Im f (n)由DFT的共轭对称性可知，Ref(n)H IDFTFep(k)二 IDFTX(k)二 x(n) jImf(n)HIDFTFop(k)HIDFTjY(k)P jy(n)故x(n) =£ f(n) f (n)21 *y(n)肓f(n) - f (n)4.设x(n)是长度X(k)为2N的有限长实序列，X(k)为x(n)的确N点DFT。(1)试设计用一次 N点FFT完成计算X (k)的高效算法。(2)若已知X (k)，试设计用一次 N点IFFT实现求x(n)的2N点IDFT运算。解：(1)在时域分别抽取偶书点和奇数点x(

9、n)得到两个N点实序列 (n)和x2(n):%(n) =x(2n), n =0,1, N -1x2(n) =x(2n 1), n =0,1, N -1根据DIT-FFT的思想，只要求得 Xj(n)和x2(n)的N点DFT,再经过简单的一级蝶形运算就 得到X(n)的2N点DFT。因为x“(n)和x2(n)均为实序列，所以根据 DFT的共轭对称性, 可用一次N点FFT求得X1(k)和X2(k)。具体方法如下：令 y(n)二 X1(n) jx?(n)Y(k) =DFTy(n), k =0,T, N -11则 X1(k)=DFTx1(n)=Yep(k)=2Y(k) Y(Nk)jX2(k)二 DFTjx

10、2( n)二 Y°p (k) = fY(k)Y (N -k)2N 点 DFTX( n) =X(k)可由 Xjk)和 X?(k)得到X(k) =X1(k) W2kNX2(k), k =0,1, ,N -1kX(k N) =X1(k) -W2NX2(k)这样，通过一次N点IFFT计算就完成了计算 2N点DFT。当然还要进行运算量相对很少的，由 Y(k)求 X,k)，X2(k)和 X(k)的运算。(2 )和(1)相同，设xjn) = x(2n), n =0,1, N1x2(n)二 x(2n 1), n =0,1, N -1Xjk)二 DFTx1( n), k = 0,1 , N -1X2(

11、k)二 DFTX2(n), k =0,1 , N -1则应满足关系式X(k) =X1(k) W4kNX2(k), k =0,1，,N -1X(k N)二 Xk) -WX2(k)由上式可解出1X,(k)X(k) X(k N)21 丄X2(k)X(k) -X(k N)W2n2由以上分析可得到运算过程如下： 由X(k)计算出Xi(k)和X2(k)1X,(k)X(k) X(k N)21 kX2(k)X(k) X(k N)W2N"2 由X1 (k)和X2(k)构成n点频域序列Y(k)丫 (k) = X1(k) jX2(k)=Yep(k) Yop(k)其中 £p(k) ；(k)，Yop

12、(k)二 jX2(k)，进行 N 点 ifft 得到y(n) =IFFTY(k) =Rey( n) j Imy( n), n = 0,1，N -1由DFT的共轭对称性知1 屮Rey(n) y( n) y (n) = DFT Yep(k)=为(n)2jIm y(n) #y(n) 一 y (n) = DFTYop(k) jx?(n) 由x1(n)和x2(n)合成x(n)X1(n), n=偶数x(n)二三 2,0 岂 n E2N -1x2 (" -)， n 二奇数L 2X(n)的数组的偶在便成实现时，只要将存放(n)和x2(n)的两个数组的元素分别依次存放数和奇数数组元素中即可。5.按照下面的IDFT算法：1 x(n)二 IDFTX(k) DFTX (k) N编写IFFT程序，其中的FFT部分不用写出清单，可调用FFT子程序。解：通过调用FFT子程序实现题中所给IFFT算法程序框图如 题5图解所示。数组XN用于存放输入 X ( k )、中间结果及最终结果 x(n) 。用 matlab 语言编写的 IFFT 题 4.6 计算 IFFT 的程序 Xk: 被变换数据 X(k) XN:IFFTX(k) 结果 x(n) %N:x(n),X(k) 长度