FFT实现FFT实现.doc

1.引言:离散傅立叶变换(DFT)及快速傅立叶变换(FFT) 傅立叶变换就是在以时间为自变量的信号函数和以频率为自变量的频域函数之间的一种可逆变换关系,非周期的连续时间信号x(t)与其对应频域信号X(jΩ)之间的傅氏变换关系为 (1-1) 逆变换 （1-2) 在数字信号处理系统中,时域信号和频域信号的处理都只能以离散值进行处理,这时由于时域信号的采样造成了对应频域信号的周期延拓,同样频域信号的采样也造成了时域信号的周期延拓,这种频域时域均为离散信号的变换是傅立叶变换的特殊形式,称为离散傅立叶级数变换。由于变换信号均为周期形式，不便于计算，所以在实际应用中仅取一个周期中的内容，从而得到了一个周期的时域信号和频域信号之间关系 (1-3) (1-4) 以上两式称为有限长序列的离散傅氏变换对，1-3式称为离散傅立叶变换（DFT），1-4式称为离散傅立叶逆变换（IDFT）。离散傅立叶变换不仅在理论上有着重要的意义，实际应用中，频域分析也拓展了数字信号处理的方式。 前面的离散傅立叶变换对中,而且一般x（n）和X（k）均为复值，按照复数形式展开后 (1-5) 可以看出，在N点的DFT中对于X（k）的每个k对应需要进行4N次实数乘法和（4N-2）次实数加法，对于N点来说，全部变换需要4N2次实数乘法和N（4N-2）次实数加法，因此，直接计算DFT的运算量近似正比于N2，N值增加时，运算量增加很快，这对于快速应用来说是无法接受的，所以需要改进DFT的计算方法，减少其运算量。由于权函数的周期性和对称性，我们可以将N点的DFT分解成为若干小点数的DFT的组合形式，使DFT计算过程成为一系列迭代运算，这就是快速傅立叶变换的基本思想。 在各种快速傅立叶变换中，最早出现的就是按时间抽取（DIT）的FFT算法。方法如下。设N=2m,有DFT公式1-3,其中x（n）是列长为N的输入序列，将其按照n的奇偶分成两个子序列 r=0,1,…N/2-1 (1-6) 则式1-3可以化为 (1-7) 由于 ,上式可表示为 (1-8) 其中的X1（k）和X2（k）分别是N/2点序列x1（r）和x2（r）的DFT，这样，一个N点序列的DFT就分解成为两个N/2点子序列的DFT，考虑对称性 （1-9） 则 k=0,1…N/2-1 （1-10） 可以将上面的运算用图表示出来。这就是蝶形计算结构，如图1.1 图1.1 由于N=2m,因此分解后N/2仍是偶数，可以继续分解直到最后成为两点DFT。图1.2表示了8点FFT的运算流图。图中可以看出，每一级蝶形运算的结果在序列中的位置同运算的输入位置相同，并且同其他位置数据无关。运算初值和结果都放在同一个存储器里，每次运算将取出初值计算后将结果放回原先存储器位置中，这就是原位运算。 图1.2 由于这种方法每一步分解均是按照每级输入序列在时间顺序上是奇数或偶数进行分解，所以称为时间抽取法。又由于每级分解为两部分,所以称为基2的快速傅立叶变换。同理，按照频率顺序进行分解的算法称为频率抽取法（DIF），而基数也可以是4，8等，对应算法分别为基4，基8等，对于N不是2 而是一复合数的情况，可以将其分成若干个因子的小序列傅氏变换。实际上，基2等算法只是快速傅氏变换的特例，但由于其运算流程的简单而成为最常用的FFT方法。 由基2FFT运算图可见，每一级运算由N/2个蝶形运算组成，因此每一级运算需要N/2次复数乘法和N次复数加法。总共m级运算需要复数乘法Nlog2N/2次，复数加法Nlog2N次。由此可见，在N增大的情况下，快速傅立叶变换方法需要的运算量增长速度比直接运算小的多，这样的速度改善使得使用傅立叶变换方法进行数字信号处理称为实际可能。 2．总体设计 在数字信号处理的实际应用中,实现FFT有三种方式。 （1）使用标准的计算机或通用处理器，通过软件编程实现。这种方式比较灵活，原则上适用于所有信号处理算法，修改设计比较简单。缺点是速度较慢，一般无法做到实时处理，同时由于通用计算机体系结构并不是专门为数字信号处理设计的，所以很大一部分运算系统和指令资源无法得到利用。 （2）使用数字信号处理器（DSP）实现。这种方法同第一种类似，同样采用软件编程实现FFT算法。由于处理器体系结构是专门为数字信号处理设计的，具有如内建硬件乘法器，数据存储器和指令存储器独立等特点，所以更适合实时性要求高的处理任务。同时也具有通用处理机的灵活性和可编程能力。 （3）使用专用硬件FFT处理器实现。这种方法中FFT处理的所有算法均使用硬件逻辑实现，由于系统完全为实现FFT运算设计，其功能是有限而具体的，所以资源利用率最高，运算速度快，一些