《FFT算法分析》word版.doc

FFT算法分析FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。基2、DIT-FFT（按时间抽取）：令，则有：蝶形运算单元如下所示：基2、DIF-FFT（按频率抽取）：则有：蝶形运算单元如下所示：由前面的分析可知，DIT（按时间抽取）算法与DIF（按频率抽取）算法没有本质上的区别，只是复数加减法与旋转因子乘法的次序有区别，两种方法的运算量是一样的。在基2算法中，每个蝶形运算单元都包括1次复数乘法、2次复数加法。N（N= ）点序列的运算流图应有M级蝶形，每一级都由N/2个蝶形运算组成，所以N点序列的基2FFT算法，总的运算量为次复数乘法，次复数加法。直接DFT运算量为次复数乘法、次复数加法。可见，FFT算法大大减少了运算量，当N越大时，FFT算法的优越性越明显。基4、DIF-FFT(按频率抽取)令：则有：蝶形运算单元如下所示：由上图可知每个基4蝶形运算单元包括3次复数乘法、8次复数加法。N（N= ，M为偶数）点序列的FFT运算若采用基4算法则有M/2级蝶形，每级由N/4个蝶形运算构成。采用基4算法计算N点序列的FFT共需要次复数乘法、次复数加法。由于主要的运算时间集中在乘法上面，可见基4算法的运算量较基2算法减少了25%，但运算量的减少是以硬件的复杂性及使用更多资源为代价的。FFT算法的FPGA实现以8点（复数点，包括实部与虚部）、基2、DIF-FFT为例来考虑FFT算法的FPGA实现。整个运算流图应由3级蝶形构成，每级中有4个蝶形运算。若DIF的输入序列为顺序输入，则得到倒序输出。完整的运算流图如下所示：考虑采用流水线结构，系统可采用3级基2蝶形运算单元构成，系统总体结构如下所示：总体结构说明输入数据为串行的数据流，故在第一级蝶形运算模块前加入串并转换模块，将串行数据流转换为并行的两列数据流以适应基2蝶形运算模块的输入信号要求。由于每级蝶形运算一次处理的两个输入数据不能直接由前一级蝶形运算一次性输出，故在两个蝶形运算单元之间插入延时对齐模块，将前一级蝶形运算的结果（两列并行的数据流）作适当的延时并通过转接器对齐，形成后一级蝶形运算模块所需要的2列输入序列。在最后一级蝶形运算后加入串并转换模块，将2列并行的数据流合成为1列。最后加入倒序模块将DIF-FFT得到的倒序输出序列整理为顺序输出。旋转因子产生模块产生各级基2蝶形运算所需的旋转因子。由运算流图可以看出最后一级的旋转因子其实是1，故可省略最后一级蝶形运算单元中的旋转因子乘法器。因此用一个双口ROM将两组数据分别输出到第一级和第二级的蝶形运算单元即可。基2蝶形运算模块由两个复数加法器和一个复数乘法器构成。旋转因子由ROM产生后，作为复数乘法器的输入之一，与前面复数加法器得到的结果相乘完成一次蝶形运算。为提高系统的运行速度可在蝶形运算单元中插入流水线寄存中间结果。若输入序列的标号为0、1、2、3、4、5、6、7，则在A、B、C、D、E处的信号标号如下图所示：串并转换模块完成A序列到B序列的转换；两个延时对齐模块分别完成B序列到C序列、C序列到D序列的转换；并串转换模块完成D序列到E序列的转换。各模块框图串并转换模块：串并转换模块可用单输入、双输出的RAM来实现，同时控制输入信号的时钟频率为输出信号时钟频率的两倍。这里要用到乒乓操作，即读写操作分开，故8点序列要用到16个存储单元。写入地址在写入时钟控制下按顺序递增。两个读出地址的最高位都为写入地址最高位的求反结果。两个读出地址的次高位固定，一个为0，一个为1，其它位在读出时钟的控制下递增。延时对齐模块：用单输入、单输出的RAM，适当控制读、写地址可实现数据的延时，转接器可用数据选择器构成。以最后一个蝶形运算单元前的延时对齐模块为例，可由如下方案实现：转接器两种状态分别为两个输出端与输入端直接相连和交叉相连，控制转接器的状态每1个clk改变一次，即控制转接器的状态持续时间与延时单元的延时时间相同。经过分析可知，若采用相同的处理方式，则倒数第n个蝶型运算单元前的延时单元的延时clk个数为个。延时单元可直接用RAM实现，控制读写地址之间的间隔即可实现输出与输入之间的延时。整个延时对齐模块的连接图如下：旋转因子产生模块：用双口ROM产生旋转因子。按照各级蝶形运算模块中所需的旋转因子的变化规律控制两个读出地址的变化，产生相应的旋转因子到各级蝶形运算模块。并串转换和倒序模块：先将用数据选择器将两路数据合成为一路写入RAM中，然后从RAM中读出数据，适当控制读地址可实现倒序序列的整序。这里也要用到乒乓操作，读写操作分开。输出数据的时钟频率为输入数据时钟频率的两倍，sel信号的变化频率与输出信号频率相同。RAM中用到的时钟信号是输出数据的时钟。控制RAM的写入地址按输出时钟递增，读出地址最高位为写入地址最高位求反的结果。读出地址中的其它位按如下规则产生：若将余下的地址位看成一个完整的地址，则最高位与写入地址最低位相同、次高位与写入地址次低位相同、依此类推。基2蝶形运算模块：基2蝶形运算单元中要完成两个复数加法和一个复数乘法。一个复数加法器可由两个实数加法器构成。下图是基2蝶形运算单元的结构图：复数乘法的运算为：X为输入信号的实部，Y为输入信号的虚部，C为旋转因子的实部，S为旋转因子的虚部，R为运算结果的实部，I为输出结果的虚部。若按上述运算直接构成复数乘法器需4个实数乘法器和3个实数加法器。考虑简化计算为：与旋转因子有关的数据都可预先计算，即C、C+S、C-S可预先计算存放在ROM中。这样可将旋转因子乘法器简化为3个实数乘法器和3个实数加法器。结构如下：对中间结果可用寄存器寄存以提高运算速度。FFTFFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就