快速傅里叶变换FFT

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

2、性增大。 减少运算量的基本途径DFT定义式中只有两种运算：与的乘法相加。所以，的特性对乘法运算量必有影响。（1）根据的对称性、周期性和特殊值减少乘法运算次数。对称性：，周期性：。的特殊值(无关紧要旋转因子)：。对这些因子不能进行乘法运算。（2）将较大数点DFT分解为若干个小数点DFT的组合，减少运算量。这正是FFT能大量节省运算量的关键。 四种快速算法的基本思想及特点根据上述减少运算量的途径，巧妙地在时域或频域进行不同的抽取分解与组合，得到不同的快速算法。下面简要归纳四种快速算法的基本思想和特点。1. 基2 DFT-FFT算法（1）算法思想：时域级奇偶抽取，并利用，将点DFT变成级蝶形运算。（

3、2）运算量：复数乘法次数： 复数加法次数： （3）特点：运算流图结构规则，可原位计算，程序简短，应用广泛。2. 基2 DIF-FFT算法（1）算法思想：频域对进行级奇偶抽取，并利用，将点DFT变成级DIF-FFT蝶形运算。（2）运算量及特点与基2 DIF-FFT相同3. 分裂基快速算法（1）算法思想：基2 FFT算法简单，基4FFT算法效率较高。分裂基是将基2分解和基4分解糅合在一起形成的高效新算法。具体是对每次的频域奇偶抽取的偶数输出使用基2算法（按二进制抽取），而奇数输出使用基4算法（按四进制抽取）。（2）运算量：复数乘法次数： 复数加法次数： （3）特点：在的快速算法中，分裂基算法的乘法

4、次数最少，接近理论最小值。比基2 FFT减少33%，比基4减少11%。运算流图结构规则，可同址计算，程序简短，便于DSP实现。4.2 教材第四章习题解答1. 如果通用计算机的速度为平均每次复数乘需要5，每次复数加需要1，用来计算N=1024点DFT，问直接计算需要多少时间。用FFT计算呢？照这样计算，用FFT进行快速卷积对信号进行处理时，估算可实现时处理的信号最高频率。解：当N=1024=210时，直接计算DFT的复数运算次数为N2=10242次复数加法计算次数为次直接计算所用计算时间TD为用FFT计算1024点DFT所需计算时间为快速卷积时，要计算一次N点FFT（考虑到已计算好存入内存），一

5、次N点IFFT和N次频率复数乘法。所以，计算1024点快速卷积的计算时间约为所以，每秒钟处理的采样点数（即采样频率）/秒。由采样定理知，可实时处理的信号最高频率为应当说明，实际实现时，还要你小一些。这是由于采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分还要计算两次。重叠部分长度与长度有关，而且还有存取数据指令周期等。3. 已知和是两个N点实序列和的DFT，若要从和求和，为提高运算效率，试设计用一次N点IFFT来完成。解：因为和均为实序列，所以，和为共轭对称序列，j为共轭反对称序列。可令和j分别作为复序列的共轭对称分量和共轭反对称分量，即计算一次N点IFFT得到由DFT的共轭对称性可

6、知，故4. 设是长度为2N的有限长实序列，为的确N点DFT。（1）试设计用一次N点FFT完成计算的高效算法。（2）若已知，试设计用一次N点IFFT实现求的2N点IDFT运算。解：（1）在时域分别抽取偶书点和奇数点得到两个N点实序列和：根据DIT-FFT的思想，只要求得和的N点DFT,再经过简单的一级蝶形运算就得到的2N点DFT。因为和均为实序列，所以根据DFT的共轭对称性，可用一次N点FFT求得和。具体方法如下：令 则 2N点可由和得到这样，通过一次N点IFFT计算就完成了计算2N点DFT。当然还要进行运算量相对很少的，由求，和的运算。（2）和（1）相同，设则应满足关系式由上式可解出由以上分析

7、可得到运算过程如下： 由计算出和 由和构成N点频域序列其中，进行N点IFFT得到由DFT的共轭对称性知 由和合成在便成实现时，只要将存放和的两个数组的元素分别依次存放的数组的偶数和奇数数组元素中即可。5. 按照下面的IDFT算法：编写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)长度XkX(0) X(1) X(N-1);n=size(Xk);N=n(2); %取得X（k）的长度Xkconj(Xk); %取复共轭XN=fft(X