快速傅里叶变换FFT算法-精简版解答.doc

1 一维DFT的快速算法—FFT 当序列的点数不超过时，它的点定义为 （1） 反变换定义为 （2） 二者形式相似，快速算法的原理一样，这里先就其正变换进行讨论。令，当依次取为时，可表示为如下的方程组： （3） 由上式可见，直接按照定义计算点序列的点时，每行含个复乘和个加，从而直接按定义计算点的总计算量为个复乘和个加。当较大时，很大，计算量过大不仅耗时长，还会因字长有限而产生较大的误差，甚至造成计算结果不收敛。所谓快速傅里叶变换就是能大大减少计算量而完成全部点计算的算法。下面介绍两种经典的的快速算法：频域抽取的算法和时域抽取的算法。 1.1 频域抽取的基2算法 1.1.1 正变换的计算 这里仅介绍基2算法，即是2的整次幂的情况。由定义 （4） 把分成两半，即和，代入（4）式得 （5） 由于 （5）式两项又可合并为 （6） 当为偶数时，注意到，，（6）式变为 （7） 当为奇数时， ，（6）式变为 （8） 这样就把一个点序列（）的点（）计算化成了两个点序列（和）的点（和）计算。由划分成 和的计算量为个加，即 和 和个乘，即 由于算出的点，是的点（）中为偶数的那一半，由算出的则是为偶数的那一半，故需要把偶数的抽出来放在一起作为的（）输出，同时把奇数的抽出来放在一起作为的（）输出。由于是频域变量，故这种算法称为频域抽取的算法。 接着，两个点仍可用上述方法各经个乘个加划分成两个点（同时还要做相应的频域抽取），从而共划分成4个点，总划分计算量仍是个加和个乘。这样的划分可一步步做下去，不难看出，每步的总划分计算量都是个加和个乘。 经过步的划分后就划成了个如下两点的计算问题 （9） 上式所需计算量是2个加和1个乘，于是完成个两点的总计算量仍是个加和个乘。从而完成全部点的总计算量个加和个乘，这比直接按定义计算所需的个乘和加要少得多。例如，，，用算法计算所需的乘法个数为，而直接按定义计算所需的乘法个数为，二者相差倍。若直接计算需半小时，而用计算只需9s即可完成，可见其效率之高，而且越大，的效率提高越明显。 图1 频域抽取的8点FFT计算流图 一般情况下，由于做了次分奇偶的抽取，此算法最后的个两点计算出的不是顺序抽取的。次序的变化可用二进码来说明：第一次抽取所分的奇偶是由二进码第1位是1或0来区分的，该位为0时为偶数，该位为1时为奇数，第二次抽奇偶是由二进码第2位是1或0来区分的……，每次抽取都是把偶数项放在前（左）边，把奇数项放在后（右）边，从而抽取以后数的二进码是按照二进制位从左向右依次排列的，和普通二进制数从右向左依次排列的的规律正好相反，所以称为倒位序。在计算出之后要把倒位序变成顺序。 1.1.2 逆变换的计算 所谓逆变换是指由求的计算，若直接按定义 做计算，则除了求和号和正变换相同的计算量外，每算一个都还需再多做一个乘的乘法运算。故按定义完成全部点的总计算量是个加和个乘。下面从图导出它的快速算法，先讨论第3列的2点的逆运算如何完成。由式（7）得， 由上式不难解出 （10） 图2 频域抽取的8点IFFT计算流图 此计算过程如图2所示，可以看出：左边各列的划分计算也都是由个碟形运算来完成的，只是各碟形运算所乘的相移因子不同。把每个碟形运算都用图的办法变成对应的逆运算，并把它们按输入在左、输出在右重新排列，就得到了全部点的计算流图。给出了的示例，图中先对顺序输入的做次的频域抽取，并把个乘的运算合成了一个乘的运算放在了最前边，然后就开始做求逆的碟形运算。 1.2 时域抽取的基2算法 比较正变换和反变换的定义式 可见，去掉乘的运算，把换成，交换、和、，反变换定义式就变成了正变换的定义式。对图2做这些变换，则得到图3的流程图。对图1做这些变换，则得到图4的流程图。这就是时域抽取的算法流图。进行碟形运算之前，先要对顺序的时域输入序列进行次的奇偶抽取，故称为时域抽取的算法。 图3 时域抽取的8点FFT计算流图 比较图2和图3不难看出，两种算法的计算量是完全一样的。这里先算出个两点的 （11）