基于乘法器复用技术的FFT处理器的设计与实现

基于乘法器复用技术的FFT处理器的设计与实现

龙海南，耿双利，郑晓昆，李彩霞

摘要：提出了一种基于乘法器复用技术的FFT优化算法，该算法主要利用了旋转因子关于y轴和y=x的对称性，使用两个实数乘法器即可分时共享完成4个复数旋转因子的计算，从而减少硬件资源消耗；采用该算法采用流水线结构，设计了基2的16点IFFT处理器，使用7个实数乘法器即可完成，进一步优化可仅使用5个。 通过ALTERA Cyclone Ⅱ系列的EP2C70F896C6器件进行下载验证。 FPGA输出结果与MATLAB计算结果比较，单点最大相对误差约*** 。 关键字：FFT, 乘法器复用，FPGA

Abstract: This paper proposes an optimized FFT algorithm based on multiplier multiplexing technology, it reduces the hardware resource consumption by taking the advantage of the rotation factor symmetry on the y-axis and y=x; Only use 7 real multiplier to design a pipelined radix-2, 16-point IFFT processor, further optimization can only use 5. The verification is carried out through the downloaded ALTERA Cyclone Ⅱ series EP2C70F896C6 device．whose result is less than ***difference compared with the result from the MATLAB calculation Key Words：FFT；multiplier multiplexing；FPGA

1 引言

FFT(快速傅里叶变换)是数字信号处理中的重要模块，作为时域和频域转换的基本运算．是数字谱分析的必要前提，在信号处理、图像处理、生物信息学、计算物理、应用数学等方面都有着广泛的应用。在高速数字信号处理中，FFT的处理速度往往是整个系统设计性能的关键所在[1]。

对于FFT的硬件实现，大致可以分为3种方案：通过数字信号处理器(DSP)实现；通过专用FFT芯片实现；通过FPGA实现[2]。用DSP完成FFT运算需要占用大量DSP的运算时间，使整个系统的吞吐量降低；专用的FFT处理芯片，虽然速度较快，但其可扩展性差，且成本昂贵。FPGA不仅有大量的片内资源，而且易于组织流水和并行结构，可以大大提高FFT的处理速度。将FFT的实时性要求与FPGA的灵活性相结合，不仅可以提高处理速度，而且可以方便的移植到ASIC中。

2 FFT算法基本原理

对于N点序列x?n?，其离散傅立叶变换(DFT)变换可写为：

nk 0?k?N?1，（2-1） X?k??DFT?xn?xnW??????N??n?0N?1nk其中：WN?e?j2??nkN。

由式（2-1）分析可知，若直接计算DFT，乘法和加法次数都和N2成正比，当N很大时，运算量是很可观的。FFT算法的基本思想：可以将一个长度为N的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算，这些短序列的DFT可重新组合成原序列的DFT，而总的运算次数却比直接的DFT运算少得

多，从而达到提高速度的目的[3]。这种分解基本上可分为两类，一类是将时间序列x(n)进行逐次分解，称为按时间抽取算法(Decimation In Time)；另一类将傅立叶变换序列x(k)进行分解，称为按频率抽取算法(Decimation In Frequency)。本文主要介绍了按时间抽取基一2FFT算法。

nk我们已经知道FFT算法主要是利用WN的性质，通过把序列逐渐分解为短序nk列实现运算量的减少。WN的以下三种性质在FFT运算中得到了应用[4]：

nk?Nnk性质1：WN的周期性 WNnk?WN??

nk性质2：WN的对称性 ?WNnk??WN?n k?nknknknknk/m?Wmm性质3：WN的可约性 WNN，WN?WN/m

基2算法中，序列x?n?的长度N为2的整数次幂，即N?2M，其中M为正整数。最初通过将x?n?分解为奇数项序列和偶数项序列的形式使FFT运算分为两组。

设：x1?r??x?2r? x2?r??x?2r?1?，r?0,1,?,N/2?1

nkxrXk?DFTxr???W设X1?k??DFT?，，利用的性质可得x?n?的??????122N?????X?k??X1?k??WNkX2?k??DFT运算为：?? k?0,?1,N,? /（2-2） N?k?X?k???X1?k??WNX2?k?2???式（2-2）的运算可用下图的蝶形信号流图表示：

AkWNkC?A?WNBB-1kD?A?WNB

图1 蝶形运算流图

由此可见，一个Ｎ点DFT分解为两个N/2点的DFT，从而实现了运算量的减少，再经过逐次分解最终分解为２点的DFT，实现了FFT运算。

3 乘法器复用的FFT实现结构

文献[5]提出了一种蝶形运算的新结构：即先进行前一级4点蝶形运算，再进行本级的与旋转因子复乘运算，如图2所示。这种结构节省了一个旋转因子复乘模块。

四点蝶形运算旋转因子复乘四点蝶形运算旋转因子复乘第四级四点蝶形运算第五级第一级 图2 文献4所设计的FFT硬件实现框图

文献[2、6] 中改进的旋转因子复数乘法的原理均为：一个复数xr?jxi和旋转因子W?e?j2?/N?cosA?jsinA相乘，结果仍为复数yr?jyi，

yr?jyi?(xrcosA?xisinA)?j?xicosA?xrsinA?，可见完成一次复数乘法操作需

要进行4次实乘和2次实加运算。为减少乘法的次数，将yr?yi做以下变换：

yr??xr?xi?cosA?xi?sinA?cosA?，yi??xr?xi?cosA?xr?sinA?cosA?，从而

完成一次复乘只需进行3次实乘和5次实加，较变换前减少一次实数乘法运算，从而减少了使用面积。

本文采用原理图输入与AHDL语言相结合的方法，来完成IFFT的设计。其中原理图输入的方法主要完成实乘和实加操作，而当参加加法运算的两个数位数长度不一致时，AHDL语言将二者补齐。

本设计中，首先完成2点IFFT的设计，然后将其封装为.bsf格式的符号文件。之后多点的IFFT设计，设计流程如下图3所示。N=4点的IFFT中，旋转因子为j,j乘法运算相当于实部虚部互换操作，可以合并到蝶形运算中且不增加硬件消耗。

N点输入奇偶分离N/2点IFFTN/2点IFFT图3设计流程图

蝶形运算正序输出 N=8点的IFFT中，1与j不需要乘法器来运算，只需要2次旋转因子的复乘运算，即x1?W81与x3?W83，其中W81与W83的位置如下图4。

W82W83W810W8图4 N=8时旋转因子分布

由图4可知W81与W83关于y轴对称，若令W81?a?jb，则W83??a?jb。又因为

cos??/4??a?b?sin??/4??2/2，则有

1??x1?W8?(x1r?jx1i)?(a?ja)?3??x3?W8?(x3r?jx3i)?(?a?ja)??(x1r?jx1i)?(1?j)?(2/2)????(x3r?jx3i)?(?1?j)?(2/2)??(x1r?x1i)?j?x1r?x1i????(2/2)??????(?x3r?x1i)?j?x1r?x3i????(2/2)?? （3-1）

上式（3-1）可以看出两次复乘运算的结果均为某个复数与2/2相乘，由此可以采用时分复用的方法，将参与复乘运算的两个数的实部和虚部按照上式相加减之后，经过串并变换，依次进入乘法器运算。这样完成一个8点的IFFT运算，仅需要1个实数乘法器即可完成，大大节省了芯片的资源与面积。而文献[5]中，若完成N=8点的IFFT运算需要做两次复乘运算， 经改进后仍需4个实数乘法器；文献[6]中，则需要6个实数乘法器才能完成设计。

另外，cos以及sin 本应为-1~+1 之间的小数，为了避免浮点运算， 这里乘以256归一化为9BIT 有符号数，即令a?181，最终输出时再右移8位即可。

N=16点的IFFT中，1与j不需要乘法器来运算，共需要6次旋转因子的复

123567乘运算，这6个旋转因子分别为W16、W16、W16、W16、W16、W16，其位置关系

如下图。

5W166W167W164W163W162W161W160W16

图5 N=16时旋转因子分布