基于DSP的FFT变换

并行之美基于DSP的FFT算法摘要：在数字技术领域中，有限长序列的频域可以离散化,即可以进行离散傅立叶变换(DFT)。离散傅里叶变换（DFT）在离散时间信号处理算法和系统的分析，设计和实现中起着十分重要的作用，但传统的DFT算法算数乘加次数太多使其运算冗长和繁杂,在很长时间里没有得到真正的运用。FFT的出现使DFT运算大大简化,使得DFT的运算得以简化，计算效率比其他高出几个数量级，在数字信号处理领域,大量使用到快速傅立叶变换运算。为了进一步提高运算速度,提出使用DSP并行处理器与PC组建实验系统。通过与传统FFT计算平台的比较实验,表明该系统拥有更加快速的FFT计算能力,并且还可以通过扩展进一步提高这种运算能力。关键词:DSP;FFT;并行处理1．引言1.1DSP在数字信号处理中的运用随着信息技术革命的不断深入和计算机技术的飞速发展,数字信号处理技术逐渐发展成为一门十分重要的技术学科。集成化的数字信号处理器DSP(DigitalSignalProcessor)的出现,为各种数字信号处理算法的实现提供了可能。这一方面极大地促进了数字信号处理技术的进一步发展;另一方面也使数字信号处理的应用领域不断地拓展。如今,DSP已经广泛地应用于通用数字信号处理、通信、控制、仪器、医学电子、消费电子、计算机、军事等各个领域。随着DSP器件性能的不断改善,DSP用于信号处理特别是实时信号处理已成为当今和未来技术发展的一个新热点。1.2DSP用于数字信号处理的优势(1)可程控用DSP设计的信号处理系统,可以设计各种软件来执行多种多样的信号处理任务。例如,给DSP载入数据采集相关程序使之成为数据采集处理器,而给DSP载入调制、解调相关程序它又成为调制解调处理器。一个数字滤波器可以通过编程来实现低通、高通、带通、带阻等不同的滤波任务,而不需要改变硬件。DSP用于信号处理系统的这种可程控性,提供了多种信号处理算法的灵活应用,对信号处理算法的研究也具有重要的意义。(2)高速的数据处理能力DSP的独特的芯片结构使得它具有高速的数据处理能力。不同于普通的微处理器,DSP放弃了冯诺依曼结构,采用了哈佛结构,将程序与数据的存储空间分开,各有自己的地址总线与数据总线。这使处理指令和数据可以同时进行,从而大大提高了处理效率。同时,DSP设置了硬件乘法/累加器,能在单个指令周期内完成乘法/累加运算。高速的数据传输能力是DSP作高速实时处理的关键之一。现在的DSP大多设置了单独的DMA总线及其控制器,在不影响或基本不影响DSP处理速度的情况下,作并行的数据传输,传输速率可以达到每秒数百兆字节。OSP这种高速的数据运算和传输能力,使许多复杂的信号处理算法得到了实现。(3)DSP集成度高,系统化好DSP器件是基于超大规模集成电路技术和计算机技术发展起来的高速高位单片计算机。它体积小,功能强,功耗小,系统化好,使用方便,性价比很高,得到了广泛的应用。2.FFT算法的理论快速傅立叶变换(FFT)是运算DFT时的一种高效运算方法。FFT的出现使DFT运算大大简化,使得DFT的运算才真正在实际中得到了广泛的使用。2.1离散傅立叶变换(DFT)简介2.1.1DFT的定义离散傅立叶变换(DFT)是一种离散时间、离散频率的傅立叶变换。周期性离散时间信号可以由各种傅立叶变换对推断:周期性时间信号可以产生频谱是离散的;离散时间信号可以产生频谱是周期性的。总之,一个域的离散化必然造成另一个域的周期延拓。DFT定义如下:正变换：反变换：2.1.2频域采样理论先看一下z变换和DFT的关系。有限长序列x(n)的离散傅立叶变换X(k)序列的各点值,等于对x(n)进行Z变换后在单位圆上N等分抽样的各点处所得的Z变换值。即:对于有限长序列补零加长N增加,发现其频谱包络不变,只是抽样点更密。(l)频域采样理论x(n)的离散傅立叶变换X(k)序列值和x(n)的z变换在单位圆上N等分的抽样值相等,实现了频域的抽样。将x(n)的频域函数X(jwe)按周期N点抽样,得到一周期序列~)(kX,再反变换回时域得到变换结果~)(nxN,是一周期延拓的序列,且与原序列x(n)有如下的关系为：rNrNnxnx)()(~公式（2.4）即频域按每周期N点抽样,时域按N点周期延拓。因此,长度为M的有限长序列,频域抽样不失真的条件为:频域抽样点数N要大于或等于序列长度M,即满足NM。2.2快速傅里叶变换（FFT）有限长序列通过离散傅立叶变换(DFT)将其频域离散化成有限长序列。但是其计算量太大,很难实时地处理。因此引入了快速傅立叶变换(FFT)。FFT只是DFT的一种快速算法,并且根据对序列分解与选取方法的不同而产生了FFT的多种算法。由前面DFT定义不难发现,求出一点X(k)需要N次复数乘法,（N-1）次复数加法。N点的X(k)需要（N*N）次复数乘法、N*（N-1）次复数加法。当N很大时,计算量非常可观。然而,利用蝶形因子的对称性和周期性,即:;;2KNNkNKNNkN公式（2.5）2.2.1基2按时间抽取(DIT)FFT算法设输入序列长度为MN2(M为正整数),将该序列按时间顺序的奇偶分解为越来越短的子序列,称为基2按时间抽取的FFT算法。其中基数2、4…MN2M为整数。若不满足这个条件,可以人为地加上若干零值,使其达到MN2。首先将x(n)按n的奇偶分成两组,当n为偶数时,令n=2r;当n为奇数时,令n=2r+1则DFT变换10)()(NnnkNWnxkx可以分解为:)()()()(212120221201kXWkXWWrxWrxkXkNkNrkNNrrkNNr）（公式（2.6）其中,)12()(,)2()(2120221201rkNNrrkNNrWrxkXWrxkX公式（2.7）再应用w系数的周期性,求出表达的后半部分X(k+N/2)的值。可以推出后半部分的表达式为:kNWkXKXKX)()()(21公式（2.8）表达式可以用蝶形流图表示：图2.1蝶形运算流图符号若N=8的按时间抽取FFT蝶形运算图为：图2.2N=8的DITFFT运算图2.2.2基2按频率抽取(DIF)FFT算法设输入序列长度MN2(M为正整数),将该序列的频域的输出序列X(k)(也是N点序列)按其频域顺序的奇偶分解为越来越短的子序列,称为基2按频率抽取的FFT算法。首先,将输入的时域序列x(tt)按n的顺序分为前半部分和后半部分,即:前半部分子序列:120);(Nnnx;前半部分子序列:120),2(NnNnx；则，)(kX可以表示为：nkNNkNNnnkNNnWWNnxnxWnxkX212010)2()([)()(公式（2.9）x(n)的频域X(k)的奇数部分,可以通过)(1nx序列的)(1kDFTX求得。由于)(1nx序列只有N/2点,所以其运算量降低一半。x(n)的频域X(k)的偶数部分,可以通过)(2nx序列的)(2kDFTX求得。由于序列)(2nx只有N/2点,所以其运算量降低一半。则按频率抽取法的蝶形运算流图可表示为：图2.3DIF的FFT蝶形图当N=8时，按频率抽取的FFT运算流图表示为：图2.4N=8的DIFFFT运算流图2.2.3对于两种算法的对比DIFFFT和DITFFT作为最常用的快速傅立叶变换,它们既有相同的地方,也有不同之处。(l)相同之处DIF与DIT两种算法均为原位运算,两者运算量也相同。它们都需要NNm2lg2复数乘法,NNa2lg复数加法,因此DIT与DIF是两种等价的FFT算法。(2)不同之处DIF与DIT两种算法结构倒过来。DIF的输入顺序,输出为乱序,运算完毕再运行“二进制倒读”程序。DIT的输入为乱序,输出顺序,先运行“二进制倒读”程序,再进行DFT。DIF与DIT的根本区别在于蝶形结构不同。DIT的复数相乘出现在减法之前,DIF的复数相乘出现在减法之后。3.基于DSP的FFT算法的并行实现并行运算可分为时间上的并行和空间上的并行，时间上的并行就是指流水线技术，而空间上的并行则是指用多个子系统并发的执行计算。3.1空间上并行-FFT算法选择及DSP子系统的确定数字信号处理中心单元主要完成数值分析运算、存储、传输几大功能。它是系统的核心单元,为了充分利用DSP处理板的运算资源优势，结合快速傅立叶变换算法的特性,将数据处理分解为2步进行。第一步在DSP子系统中的基-2DIFFFT变换，根据不同DSP芯片在一个核心周期同时并行的加法和乘法特性，可知该芯片可以同时进行几个蝶形运算。且DSP子系统之间不涉及任何数据交换。根据：NNm2lg2；NNa2lg可以算出DSP子系统的个数。例如DM642芯片可以在一个核心周期内并行6个加法和2个乘法的特性,在DSP子系统中基2-按频域抽取算法同时进行2个碟形运算第二步，找出不包含任何旋转英子的蝶形变换中间英子，将其代入不包含任何旋转因子的蝶形变换中进行一次计算就得到了最终的输出向量。3.2时间上并行-DSP子系统中的并行处理数据处理的主要任务是由并行的N个DSP子系统承担。在DSP子系统中算法的改进直接影响整个系统的运行效率,其核心运算资源由功能单元和寄存器组成。3.2.1功能单元并行最终算法实现由汇编代码编译,由于不同芯片内核内拥有数据通路数量不同设为Q，每条数据通路上存在的功能单元也不同设为W。在这W个一组的功能单元中,只有M单元可以进行乘法操作,因此需要对算法核心循环体做适当展开示,使每个指令周期内8个功能单元并行工作达到并保持流水线完全充满状态。3.2.2寄存器复用DSP芯片的三级流水线架构需要耗用有限的延时间隙在数据存储指令上,并且算法中使用的输入数据存储位置确定,不存在预测命中问题,因此在芯片内二级缓存层次上的任何优化,都不具有提高运算速度的关键意义,只有提高芯片核心内64个32位寄存器的使用效率、减少存取指令的使用,才能大幅度减少数据处理的时间。而C编译器或线性汇编编译器主要针对功能单元并行运算进行优化,涉及寄存器储优化甚微。基于完全相同的基4-按频域抽取快速傅立叶变换算法结构,使用汇编编写、线性汇编编写和C编写的数据吞吐量越来越大。3.3实验并行系统结构在实验并行系统中DSP子系统中CPU完成计算数据输入以及最终计算结果输出,其PCI接口使用主模式并使用EDMA辅助技术。输入数据在被分解为2部分,并通过PCI总线分配到DSP子系统A和DSP子系统B中,在每个DSP系统中分别同时完成数据的基2-按频域抽取快速傅立叶变换并通过PCI总线返回计算结果给子系统。在CPU中重整2部分结果形成一个新的向量,并针对此向量再进行2次蝶形运算,且不包含任何乘法因素,充分利用CPU高速主频的优势。最终由X86子系统输出数据处理结果。4.FFT算法实现的对比分析这部分通过对实时信号及计算机模拟数据作不同的FFT运算,将结果同Matlab仿真结果进行对比,来验证系统作频谱运算的性能。同时对多组数据做普通的FFT变换及基于DSP并行的FFT变换。分析比较运算速度等性能。结果分析：基于DSP的FFT计算通过时间上利用流水线技术，一次可执行多个指令的算法，可以提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。而空间上的利用DSP芯片的子系统之间并行且数据互不干扰可以使用多个子系统并发的执行计算提高了运算速度。但是并行运算对于器件的性能稳定性等等要求高。对于数据的拆分有赖于具体的实现，前几级的蝶形运算为小点数的FFT，可以使用高度并行性的汇编程序T1，，对于大点数N的数据，只能编写程序，不可直接调用，而且运算完成后数据可能有定点向浮点转化，数据类型可能发生变化。5.结论科学研究中大量使用到的快速傅立叶变换算法随着计算数据量的增长其包含的乘法运算也随之爆发式增长。如果需要FFT速度更快的运算能力,可以整合更多的高效乘法运算芯片并行计算,优化数据处理的流水线可以提高运算能力，而此系统的处理能力仅受到数据传输总线的传输能