并行之美基于DSP的FFT算法并行分析.doc

《并行之美基于DSP的FFT算法并行分析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行之美——基于DSP的FFT算法并行分析摘要—快速傅里叶变换FFT是一种应用广泛的实现离散傅里叶变换DFT的快速算法，研究FFT的高速实现有着非常重要的意义和价值。采用通用DSP来实现FFT，可以满足高速实时处理的要求,但在高速信号处理系统中，一些复杂的信号算法通常需要多次FFT运算才能求得结果，因此缩短FFT运算时间具有实际意义。本文讨论了FFT算法的内在并行性，如何将FFT算法进行并行化，需要对算法的基本结构进行分析，这里主要以频率抽取基2算法为例，对FFT的并行性和串行性进行分析。关键字—并行处理技术，基于DSP,FFT变换I.引言离散傅里叶变换(DF

2、T)是数字信号处理中最基本、最重要的运算，许多算法，例如卷积、滤波、波谱分析等都可以化为DFT来实现。[1]但是DFT的计算量相当大，1965年Cooley和Tukey提出了快速傅里叶变换算法(FFT)，大大提高了DFT的计算速度。快速傅立叶变换算法主要是利用了旋转因子的对称性、周期性和还原性，从而将N点的有限长序列的DFT分解成几个较小点数的DFT。[2]由于DFT的计算量与N平方成正比，所以长度N越小的序列其DFT的运算量越少，从而提高了运算速度。快速傅里叶变换FFT广泛应用于雷达、数字通信、图象处理、语音信号处理和生物医学等领域，且在高速信号处理系统中，

3、FFT运算已成为一个基本运算，一些复杂的信号（如小波变换）算法通常需要多次FFT运算才能求得结果，所以研究FFT算法的并行性，缩短FFT算法运算时间具有很大的现实意义。[3]本文主要以频率抽取基2为例分析FFT的串行性与并行性，研究基于4TS201DSP硬件平台的并行FFT算法设计。II.FFT的并行化A.频率抽取FFT算法的并行性对于一个N点DFT(离散时间傅立叶变换)，其变换定义为（1-1）FFT算法的本身，即是将N点DFT进行分组，以基2FFT算法为例，先将点DFT分成两个N/2点DFT，再分为四个N/4点DFT，进而八个N/8点DFT，至分为N/2个两

4、个DFT。例如频率抽取(DIF)基二FFT算法，是将DFT定义公式中的x(n)按序号分为上下两部分:（1-2）式中，分别令k=2r,k=2r+1，而r=0,1,...,N/2-1。再令，，即可得到由输入数据进行分组的迭代公式:（1-3）从上述分析可知，对于频率抽取基2类FFT算法，其算法本身的思想即是将输入数据在每一级蝶形运算是按照序号将输入数据按照上下两部分进行分组。因此，可以按照分而治之优化原则对蝶形运算的输入数据进行分割，将运算量分配到多个计算节点。同时，将N点DFT分为相互独立的N/2点DFT并向下细分成N/2个两点蝶形运算，每一个蝶形运算和DFT都是

5、相互独立的，可以并行计算。B.时间抽取FFT算法的并行性和频率抽取FFT算法相比，时间抽取FFT算法的数据分割原则有所不同。首先按照x(n)的序号的奇偶进行分组，有:（1-4）令，则有(1-5)其中A(k)和B(k)都是N/2点DFT，而X(k)则是N点DFT。按照奇偶分割原则继续往下划分，即可得到完整的时间抽取FFT运算蝶形图。按照以上分析，无论频率抽取FFT基2算法还是时间抽取基2算法，其基本思想都是对输入数据进行分割，类似的，基4算法和分裂基算法，都是在数据分割方法上对于最基本的基二算法进行的改进。这一类的FFT算法现在均有非常成熟的串行程序，利用分治原

6、则和算法内部数据的可分割性，可以方便将输入数据进行分割处理，将运算量分摊到多个计算节点，从而设计出相应的并行算法。从理论上将，除了数据的分割需要耗费处理器一定计算量以外，剩余的计算量是将串行算法的计算量进行平均分配而无需额外的开销，因此按照输入数据分割方法设计的并行算法拥有优异的加速性能。C.FFT算法的串行性上文分析了FFT算法内在的并行性，可以通过分治策略将属于数据进行分割，从而达到在多片DSP中的并行算的运算负载分配。[4]虽然FFT算法天然地具备了这一并行特性，但是算法内部流程也具有无法并行化的部分，在算法的流程层面上具备固有的串行性。在FFT算法当中

7、，旋转因子是蝶形运算中的重要内容。因此，在蝶形运算之前必须先得到旋转因子。根据实际应用需求，旋转因子可以通过查表或者实时计算生成。此外对于频率抽取基2FFT算法，输入数据为顺序排列，蝶形运算后输出数据为变序输出，因此需要进行码元翻转才能成为正常的输出序列，因此计算顺序可分为3步:图1-1FFT算法串行流程示意图由上图可以看到，FFT算法在流程层面上具有很强的依赖性，旋转因子是蝶形运算的必要输入数据，蝶形运算的实质是将两个时域点数据依旋转因子加权之和。[5]对于DIFFFT算法而蝶形运算的输出则是逆序的，需要通过码元翻转才能得到正确排序的频域数据，因此这三个流程

8、以上一级流程的输出作为输入，具有不可改