基于CORDIC算法的基4DIT?FFT处理器的设计

摘 要： 随着海洋开发和信息产业的发展，高速、大容量、高可靠性的水声通信系统成为研究热点。论述了一种用于水声通信系统中的基4DIT?FFT处理器的设计。该设计利用CORDIC算法优化蝶形运算单元，将复数乘法转换为硬件易于实现的加、减、移位运算，并通过Matlab对伸缩系数与旋转系数进行预处理，大大加快了运算速度且降低了系统复杂性。在此基础上设计了一种1024点12位的基4DIT?FFT处理器。

关键词： CORDIC算法； 基4DIT?FFT； 蝶形运算单元； 流水线结构

中图分类号： TN919?34 文献标识码： A 文章编号： 1004?373X（2016）21?0095?04

Design of radix?4 DIT?FFT processor based on CORDIC algorithm

LI Xiaotong， LI Xin

（College of Information Science and Engineering， Ocean University of China， Qingdao 266100， China）

Abstract： With the development of ocean development and information industry， the high?speed， large?capacity and high?reliability underwater acoustic communication system becomes a research hotspot. The design of a radix?4 DIT?FFT processor used in underwater acoustic communication system is discussed. The CORDIC algorithm is utilized in the design to optimize the butterfly processing unit. The complex multiplication is converted into add， subtraction and shift operations easier to implement with hardware. The telescopic coefficient and rotary coefficient are preprocessed with Matlab to accelerate the computing speed greatly and reduce system complexity. On this basis， a radix?4 DIT?FFT processor with 1024 points and 12 bits was designed.

Keywords： CORDIC algorithm； radix?4 DIT?FFT； butterfly processing unit； pipeline structure

海洋环境的复杂多变使得水声信道具有信道窄、多径干扰强、信号衰减严重、时?空?频变参信道的特点[1?2]，水声通信的发展也因此远远滞后于无线电通信。实现水下高速、大容量、高可靠性的通信一直是海洋科技界多年来追求的一个目标。OFDM、扩频以及其他的一些调制方式是水声通信技术的研究热点，FFT作为时域到频域的高效转换方法，是OFDM技术以及CDMA同步方法中的核心技术。因此，本文设计了一种基4DIT?FFT高速实时硬件处理器，采用流水线结构的CORDIC算法优化了蝶形处理单元，将硬件不易实现、运算速度慢的乘法单元转换成硬件易于实现、运算速度快的加法单元。

1 总体设计

目前基于FPGA的FFT硬件实现结构主要分为递归结构、流水线结构以及全并行结构[3]。递归结构是内存共享结构，在三种结构中占用硬件资源最少，但由于只有一个运算单元，因此运算时间最长。流水线结构是级联结构， FFT的每一级都使用一个独立的运算单元，前一级运算结果可以直接用于下一级运算而无需等到本级运算全部完成，因此在运算速度上有所提高，但同时占用的硬件资源也随之增多。全并行结构则是在FFT的每一级都设置与FFT的点数成正比的运算单元数，显然该结构在三种结构中运算速度最快，硬件资源占用也最多。

综合考虑上述三种结构，本文采用流水线结构，设计了一种1024点12位的基4DIT?FFT处理器。总体结构框图如图1所示。

2 基4DIT?FFT

2.1 基4DIT?FFT的运算单元

基4DIT?FFT即基4时间抽取法FFT，设序列[x（n）]的长度为[N，]且满足[N=4M，][M]为自然数。[x（n）]的DFT可以表示为：

这里得到的是一级蝶形运算单元，同理，[a（m）～d（m）]可以继续分解，最终得到[N]个1点DFT和[M]级蝶形运算。

由式（3）可以看出，一个基4蝶形运算单元需要3个复乘和8个复加。

2.2 基4DIT?FFT的选择

对于基2DIT?FFT，运算流图有[log2N]级，每级都由[N2]个蝶形运算单元构成，每个蝶形运算单元包括1次复乘，2次复加，那么每级需要[N2]次复乘和[N]次复加，[log2N]级需要[N2log2 N]次复乘，[Nlog2N]次复加。同样根据式（3）和基4DIT?FFT的运算流图可知，基4DIT?FFT所需的复乘数为[3N8log2 N]（未计入乘以±j和1的计算），比基2DIT?FFT复乘次数减少了25%，复加次数不变。可以证明，当FFT的基大于4时，不会明显降低计算量[4]，但控制复杂度却明显增大，所以综合考虑运算速度与控制复杂度，最终选择基4DIT?FFT进行方案设计。

3 CORDIC算法与FFT复乘运算

3.1 CORDIC算法基本原理

文献[5]率先提出了CORDIC （坐标旋转数字计算机）算法，当时并没有引起人们的关注，文献[6]提出了统一的CORDIC算法，人们开始对这种旋转后逐渐逼近的近似方法进行深入研究。文献[7?8]在量化误差分析方面进行了拓展，其中文献[8?9]第一次利用FPGA实现了CORDIC算法。文献[10]在分布式算法中实现了CORDIC算法。

CORDIC算法在圆坐标系中的基本原理如图2所示，在[x?y]坐标平面内将点[（x1，y1）]旋转角度[θ]到点[（x2，y2）]，其关系可用式（4）表示：

为了方便在硬件上实现，做如下约定：[tanθi=2-i，]这时[θi=arctan（2-i），][cosθi=1（1+2-2i）；]以[δi]确定旋转方向，+1代表逆时针旋转，-1代表顺时针旋转。

这时，第[i]步旋转可以表示为：

式中：[1（1+2-2i）]是常数，称为每次旋转的伸缩系数，实际应用中，如果迭代次数[n]已知，可以预先计算出整个迭代过程中的伸缩系数[Kn=n1（1+2-2i）]，将输入数据校正后再参与运算。式（5）可以简化为只有加、减、移位的运算，如下：

根据文献[6]的结论可知：

由式（6）～（8）可知，将所需旋转角度作为[z1]输入，根据[n]次迭代输出的[xn+1，][yn+1，]就可得到旋转角度[z1]的三角函数值。

3.2 CORDIC算法与FFT复乘运算

由式（3）可知，基4DIT?FFT蝶形运算单元包含复加，复乘两种运算，复加相当于两次实数加法运算，硬件电路易于实现，而复乘包含四次实数乘法运算和两次实数加法运算，硬件实现较为复杂，因此讨论如何利用CORDIC算法简化复乘运算。

选取某一级的蝶形运算中的一个复乘运算：

为例进行分析，这里，下标[m]表示第[m]级蝶形运算，将[WkN]展开得到：[WkN=exp-j2πkN=cos-2πkN+jsin-2πkN] （10）

将式（10）代入式（9），得到：

将[Xm]和[Y]的实部和虚部分开表示，可以得到：

对比式（8），显然[Xrem]对应[x1，][Ximm]对应[y1，][-2πkN]对应旋转角度[z1。]可见复乘单元的实部虚部与CORDIC算法中的平面坐标值一一对应，因此可以利用CORDIC算法简化基4DIT?FFT中复乘单元的硬件实现。

4 FFT复乘运算的硬件实现

4.1 复乘单元的整体设计

通过3.2节的分析，利用CORDIC算法的复乘单元的整体设计框图如图3所示，输入数据的实部和虚部首先经过伸缩系数校正模块，经过校正的数据分别送入R通道和I通道，为了节约资源，提高速度，可事先通过Matlab仿真得到[δ0～δ11，]存储在ROM中，这样可以免去Z通道，节约[13]的加减法器。

4.2 伸缩系数校正模块的设计

如3.1节所述，实际应用中，迭代次数[n]已知可以预先计算出整个迭代过程中的伸缩系数，将输入数据校正后再参与运算。本设计中输入数据为12位字长，故迭代次数为12次，伸缩系数为：

如果直接乘以伸缩系数，将有悖于CORDIC算法的初衷，综合考虑硬件实现的简易程度与伸缩误差，最终选用式（14）所示的迭代近似实现：

其中[δi]根据Matlab的优化程序在-1，0，1三个值中选择最优值。优化程序得到的[δi]系数值如图4所示（从左到右依次为[δ0～δ11]）：

4.3 旋转系数的设计

根据式（7）和式（8），可通过Matlab仿真得到[δ0～][δ11，]这里仅给出第二级旋转因子[W016，W116，W216，W316]的系数[δ0～δ11，]以及利用CORDIC算法旋转的角度与实际应该旋转角度之间的误差（见图5中的[z2]）。

4.4 时序仿真结果

通过Altera公司的Quartus 9.1软件对复乘单元进行设计，并用Mentor公司的ModelSim 10.1a进行仿真验证，图6给出的是字长为12位的实部与字长为12位的虚部作为输入数据与第二级旋转因子之一[W116]进行复乘的仿真结果，图6结果显示，输入数据经过伸缩因子校正与CORDIC迭代运算共16个周期之后得到输出结果。

5 结 语

本文设计了一种1 024点12位的基4DIT?FFT处理器。详细阐述了CORDIC算法在复乘单元中的设计与FPGA实现。将复数乘法转换为硬件易于实现的加、减、移位运算，并通过Matlab对伸缩系数与旋转系数进行预处理，免去Z通道，大大加快了运算速度，节约了资源，降低了系统复杂性。除了适用于本文的基4DIT?FFT，还可用于基2FFT以及分裂基FFT等处理器中，具有很高的研究价值，值得推广应用。

蝶形运算单元的后续设计主要为复数加减，较为简单，不再赘述。整个系统受控于状态发生器从而有序工作。地址发生器可根据基4DIT?FFT数据的存取规律进行设计，这里不再详述。

参考文献

[1] 周琳.深远海环境监测水声通信仿真方法与信道估计研究[D].青岛：中国海洋大学，2011：24?28.

[2] 倪笑园.基于FH/MFSK的水声通信研究[D].杭州：浙江大学，2014：7?13.

[3] 李伟，孙进平，王俊，等.一种基于FPGA的超高速32K点FFT处理器[J].北京航空航天大学学报，2007，33（12）：1440?1443.

[4] PROAKIS J G， MANOLAKIS D G.数字信号处理：原理、算法与应用[M].张晓林，译.北京：电子工业出版社，2004.

[5] VOLDER J E. The CORDIC trigonometric computing technique [J]. IRE transactions on electronics computers， 1959， 8（3）： 330?334.

[6] WALTHER J S. A unified algorithm for elementary functions [C]// Proceedings of 1971 Spring Joint Computer Conference. New York： ACM， 1971： 379?385.

[7] HU X B， HARBER R G， BASS S C. Expanding the range of convergence of the CORDIC algorithm [J]. IEEE transactions on computer， 1991， 40（1）： 13?21.

[8] MEYER?BASE U， MEYER?BASE A， HILBERG W. Coordinate rotation digital computer （CORDIC） synthesis for FPGA [C]// Proceedings of 1994 the 44th International Workshop on Field?Programmable Logic and Applications. Prague： Springer Berlin Heidelberg， 1994： 397?408.

[9] MEYER?BASE U. The use of complex algorithm in the realization of universal sampling receiver using FPGAs [J]. VDI/Springer， 1995， 10（404）： 215?228.

[10] MA G. A systolic distributed arithmetic computing machine for digital signal processing and linear algebra applications [D]. Gainesville： University of Florida， 1989.