基于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.