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

基于乘法器复用技术的FFT 处理器的设计与实现龙海南，耿双利，郑晓昆，李彩霞摘要：提出了一种基于乘法器复用技术的FFT 优化算法，该算法主要利用了旋转因子关于y 轴和y=x 的对称性，使用两个实数乘法器即可分时共享完成4个复数旋转因子的计算，从而减少硬件资源消耗；采用该算法采用流水线结构，设计了基2的16点IFFT 处理器，使用7个实数乘法器即可完成，进一步优化可仅使用5个。

通过ALTERA Cyclone Ⅱ系列的EP2C70F896C6器件进行下载验证。

F PGA 输出结果与MATLAB 计算结果比较，单点最大相对误差约*** 。

关键字：FFT, 乘法器复用，FPGAAbstract: 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 ；FPGA1 引言FFT(快速傅里叶变换)是数字信号处理中的重要模块，作为时域和频域转换的基本运算．是数字谱分析的必要前提，在信号处理、图像处理、生物信息学、计算物理、应用数学等方面都有着广泛的应用。

在高速数字信号处理中，FFT 的处理速度往往是整个系统设计性能的关键所在[1]。

对于FFT 的硬件实现，大致可以分为3种方案：通过数字信号处理器(DSP)实现；通过专用FFT 芯片实现；通过FPGA 实现[2]。

用DSP 完成FFT 运算需要占用大量DSP 的运算时间，使整个系统的吞吐量降低；专用的FFT 处理芯片，虽然速度较快，但其可扩展性差，且成本昂贵。

FPGA 不仅有大量的片内资源，而且易于组织流水和并行结构，可以大大提高FFT 的处理速度。

将FFT 的实时性要求与FPGA 的灵活性相结合，不仅可以提高处理速度，而且可以方便的移植到ASIC 中。

2 FFT 算法基本原理对于N 点序列()x n ，其离散傅立叶变换(DFT)变换可写为：()()()10N nkN n X k DFT x n x n W -===⎡⎤⎣⎦∑ 01k N ≤≤-，（2-1） 其中：2jnk nkNN W eπ-⋅=。

由式（2-1）分析可知，若直接计算DFT ，乘法和加法次数都和N 2成正比，当N 很大时，运算量是很可观的。

FFT 算法的基本思想：可以将一个长度为N 的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算，这些短序列的DFT 可重新组合成原序列的DFT ，而总的运算次数却比直接的DFT 运算少得多，从而达到提高速度的目的[3]。

这种分解基本上可分为两类，一类是将时间序列x(n)进行逐次分解，称为按时间抽取算法(Decimation In Time)；另一类将傅立叶变换序列x(k)进行分解，称为按频率抽取算法(Decimation In Frequency)。

本文主要介绍了按时间抽取基一2FFT 算法。

我们已经知道FFT 算法主要是利用nkN W 的性质，通过把序列逐渐分解为短序列实现运算量的减少。

nkN W 的以下三种性质在FFT 运算中得到了应用[4]：性质1：nkN W 的周期性 ()n k N nk N N W W +=性质2：nk N W 的对称性 ()n k n kN N W W *-= 性质3：nk N W 的可约性 n k m n k N m N W W =，//nk nk mN N m W W =基2算法中，序列()x n 的长度N 为2的整数次幂，即2M N =，其中M 为正整数。

最初通过将()x n 分解为奇数项序列和偶数项序列的形式使FFT 运算分为两组。

设：()()12x r x r = ()()221x r x r =+，0,1,,/21r N =-设()()11X k DFT x r =⎡⎤⎣⎦，()()22X k DFT x r =⎡⎤⎣⎦，利用nkN W 的性质可得()x n 的DFT 运算为：()()()()()12122k N kN X k X k W X k N X k X k W X k ⎧=+⎪⎨⎛⎫+=-⎪ ⎪⎝⎭⎩ 0,1,,/k N =- （2-2） 式（2-2）的运算可用下图的蝶形信号流图表示：ABkN A W B=+k N D A W B=-图1 蝶形运算流图由此可见，一个Ｎ点DFT 分解为两个N/2点的DFT ，从而实现了运算量的减少，再经过逐次分解最终分解为２点的DFT ，实现了FFT 运算。

3 乘法器复用的FFT 实现结构文献[5]提出了一种蝶形运算的新结构：即先进行前一级4点蝶形运算，再进行本级的与旋转因子复乘运算，如图2所示。

这种结构节省了一个旋转因子复乘模块。

第一级第四级第五级图2 文献4所设计的FFT 硬件实现框图文献[2、6] 中改进的旋转因子复数乘法的原理均为：一个复数r i x jx +和旋转因子2/cos sin j N W e A j A π-==-相乘，结果仍为复数r i y jy +，()(cos sin )cos sin r i r i i r y jy x A x A j x A x A +=-++，可见完成一次复数乘法操作需要进行4次实乘和2次实加运算。

为减少乘法的次数，将r i y y +做以下变换：()()cos sin cos r r i i y x x A x A A =+-+，()()cos sin cos i r i r y x x A x A A =++-，从而完成一次复乘只需进行3次实乘和5次实加，较变换前减少一次实数乘法运算，从而减少了使用面积。

本文采用原理图输入与AHDL 语言相结合的方法，来完成IFFT 的设计。

其中原理图输入的方法主要完成实乘和实加操作，而当参加加法运算的两个数位数长度不一致时，AHDL 语言将二者补齐。

本设计中，首先完成2点IFFT 的设计，然后将其封装为.bsf 格式的符号文件。

之后多点的IFFT 设计，设计流程如下图3所示。

N=4点的IFFT 中，旋转因子为j ,j 乘法运算相当于实部虚部互换操作，可以合并到蝶形运算中且不增加硬件消耗。

图3设计流程图N=8点的IFFT 中，1与j 不需要乘法器来运算，只需要2次旋转因子的复乘运算，即181x W ⋅与383x W ⋅，其中18W 与38W 的位置如下图4。

08W 18W 28W 38W图4 N=8时旋转因子分布由图4可知18W 与38W 关于y 轴对称，若令18W a jb =+，则38W a jb =-+。

又因为()()cos /4sin /42a b ππ====，则有()()18381(11)()3(33)()(11)(1)2)(33)(1)2)(11)112)(31)132)x W x r jx i a ja x W x r jx i a ja x r jx i j x r jx i j x r x i j x r x i x r x i j x r x i ⎧⋅=+⋅+⎪⎨⋅=+⋅-+⎪⎩⎧+⋅+⋅⎪=⎨+⋅-+⋅⎪⎩⎧-++⋅⎡⎤⎪⎣⎦=⎨--+-⋅⎡⎤⎪⎣⎦⎩ （3-1）上式（3-1）2相乘，由此可以采用时分复用的方法，将参与复乘运算的两个数的实部和虚部按照上式相加减之后，经过串并变换，依次进入乘法器运算。

这样完成一个8点的IFFT 运算，仅需要1个实数乘法器即可完成，大大节省了芯片的资源与面积。

而文献[5]中，若完成N=8点的IFFT 运算需要做两次复乘运算， 经改进后仍需4个实数乘法器；文献[6]中，则需要6个实数乘法器才能完成设计。

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

N=16点的IFFT 中，1与j 不需要乘法器来运算，共需要6次旋转因子的复乘运算，这6个旋转因子分别为116W 、216W 、316W 、516W 、616W 、716W ，其位置关系如下图。

016W 116W 216W 316W 416W 516W 616W 716W图5 N=16时旋转因子分布利用旋转因子关于y 轴以及直线y x =的对称性质，令116W c jd =+，则316W d jc =+，516W d jc =-+，716W c jd =-+，其中()c o s /8*256237c π==，()sin /8*25698d π==，则有()()()()()()()()()()()()()()()()11*111177*777733*333355*5555x r jx i c jd x r c x i d j x i c x r d x r jx i c jd x r c x i d j x i c x r d x r jx i d jc x i c x r d j x r c x i d x r jx i d jc x i c x r d j x r c x i d++=⋅-⋅+⋅+⋅⎧⎪+-+=-⋅-⋅+-⋅+⋅⎪⎨++=-⋅+⋅+⋅+⋅⎪⎪+-+=-⋅-⋅+⋅-⋅⎩ （3-2） 由上式可以看出，等式右侧均为1111777733335555x x x x x x x x c d j c d x x x x x x x x ⎡⎤⎡⎤⎛⎫⎛⎫⎛⎫⎛⎫⎢⎥⎢⎥ ⎪ ⎪ ⎪ ⎪⎢⎥⎢⎥ ⎪ ⎪ ⎪ ⎪⋅+⋅+⋅+⋅⎢⎥⎢⎥ ⎪ ⎪ ⎪ ⎪⎢⎥⎢⎥ ⎪ ⎪ ⎪ ⎪⎢⎥⎢⎥⎝⎭⎝⎭⎝⎭⎝⎭⎣⎦⎣⎦（3-3） 因此与N=8点的IFFT 相同，将乘法器时分复用，经过串并变换，将4路串为1路，这样在流程图的蝶形单元中采仅需要5个实数乘法器（实现式（3-3）需要4个实数乘法器，216W 与616W 还需要额外的1个实数乘法器来实现），在流程图的两个N/2点（4点）的IFFT 中还需要2个实数乘法器。