基于CORDIC算法的基4DIT?FFT處理器的設(shè)計

摘 要： 隨著海洋開發(fā)和信息產(chǎn)業(yè)的發(fā)展，高速、大容量、高可靠性的水聲通信系統(tǒng)成為研究熱點。論述了一種用于水聲通信系統(tǒng)中的基4DIT?FFT處理器的設(shè)計。該設(shè)計利用CORDIC算法優(yōu)化蝶形運算單元，將復(fù)數(shù)乘法轉(zhuǎn)換為硬件易于實現(xiàn)的加、減、移位運算，并通過Matlab對伸縮系數(shù)與旋轉(zhuǎn)系數(shù)進行預(yù)處理，大大加快了運算速度且降低了系統(tǒng)復(fù)雜性。在此基礎(chǔ)上設(shè)計了一種1024點12位的基4DIT?FFT處理器。

關(guān)鍵詞： CORDIC算法； 基4DIT?FFT； 蝶形運算單元； 流水線結(jié)構(gòu)

中圖分類號： 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

海洋環(huán)境的復(fù)雜多變使得水聲信道具有信道窄、多徑干擾強、信號衰減嚴重、時?空?頻變參信道的特點[1?2]，水聲通信的發(fā)展也因此遠遠滯后于無線電通信。實現(xiàn)水下高速、大容量、高可靠性的通信一直是海洋科技界多年來追求的一個目標。OFDM、擴頻以及其他的一些調(diào)制方式是水聲通信技術(shù)的研究熱點，F(xiàn)FT作為時域到頻域的高效轉(zhuǎn)換方法，是OFDM技術(shù)以及CDMA同步方法中的核心技術(shù)。因此，本文設(shè)計了一種基4DIT?FFT高速實時硬件處理器，采用流水線結(jié)構(gòu)的CORDIC算法優(yōu)化了蝶形處理單元，將硬件不易實現(xiàn)、運算速度慢的乘法單元轉(zhuǎn)換成硬件易于實現(xiàn)、運算速度快的加法單元。

1 總體設(shè)計

目前基于FPGA的FFT硬件實現(xiàn)結(jié)構(gòu)主要分為遞歸結(jié)構(gòu)、流水線結(jié)構(gòu)以及全并行結(jié)構(gòu)[3]。遞歸結(jié)構(gòu)是內(nèi)存共享結(jié)構(gòu)，在三種結(jié)構(gòu)中占用硬件資源最少，但由于只有一個運算單元，因此運算時間最長。流水線結(jié)構(gòu)是級聯(lián)結(jié)構(gòu)， FFT的每一級都使用一個獨立的運算單元，前一級運算結(jié)果可以直接用于下一級運算而無需等到本級運算全部完成，因此在運算速度上有所提高，但同時占用的硬件資源也隨之增多。全并行結(jié)構(gòu)則是在FFT的每一級都設(shè)置與FFT的點數(shù)成正比的運算單元數(shù)，顯然該結(jié)構(gòu)在三種結(jié)構(gòu)中運算速度最快，硬件資源占用也最多。

綜合考慮上述三種結(jié)構(gòu)，本文采用流水線結(jié)構(gòu)，設(shè)計了一種1024點12位的基4DIT?FFT處理器?？傮w結(jié)構(gòu)框圖如圖1所示。

2 基4DIT?FFT

2.1 基4DIT?FFT的運算單元

基4DIT?FFT即基4時間抽取法FFT，設(shè)序列[x（n）]的長度為[N，]且滿足[N=4M，][M]為自然數(shù)。[x（n）]的DFT可以表示為：

這里得到的是一級蝶形運算單元，同理，[a（m）～d（m）]可以繼續(xù)分解，最終得到[N]個1點DFT和[M]級蝶形運算。

由式（3）可以看出，一個基4蝶形運算單元需要3個復(fù)乘和8個復(fù)加。

2.2 基4DIT?FFT的選擇

對于基2DIT?FFT，運算流圖有[log2N]級，每級都由[N2]個蝶形運算單元構(gòu)成，每個蝶形運算單元包括1次復(fù)乘，2次復(fù)加，那么每級需要[N2]次復(fù)乘和[N]次復(fù)加，[log2N]級需要[N2log2 N]次復(fù)乘，[Nlog2N]次復(fù)加。同樣根據(jù)式（3）和基4DIT?FFT的運算流圖可知，基4DIT?FFT所需的復(fù)乘數(shù)為[3N8log2 N]（未計入乘以±j和1的計算），比基2DIT?FFT復(fù)乘次數(shù)減少了25%，復(fù)加次數(shù)不變。可以證明，當FFT的基大于4時，不會明顯降低計算量[4]，但控制復(fù)雜度卻明顯增大，所以綜合考慮運算速度與控制復(fù)雜度，最終選擇基4DIT?FFT進行方案設(shè)計。

3 CORDIC算法與FFT復(fù)乘運算

3.1 CORDIC算法基本原理

文獻[5]率先提出了CORDIC （坐標旋轉(zhuǎn)數(shù)字計算機）算法，當時并沒有引起人們的關(guān)注，文獻[6]提出了統(tǒng)一的CORDIC算法，人們開始對這種旋轉(zhuǎn)后逐漸逼近的近似方法進行深入研究。文獻[7?8]在量化誤差分析方面進行了拓展，其中文獻[8?9]第一次利用FPGA實現(xiàn)了CORDIC算法。文獻[10]在分布式算法中實現(xiàn)了CORDIC算法。

CORDIC算法在圓坐標系中的基本原理如圖2所示，在[x?y]坐標平面內(nèi)將點[（x1，y1）]旋轉(zhuǎn)角度[θ]到點[（x2，y2）]，其關(guān)系可用式（4）表示：

為了方便在硬件上實現(xiàn)，做如下約定：[tanθi=2-i，]這時[θi=arctan（2-i），][cosθi=1（1+2-2i）；]以[δi]確定旋轉(zhuǎn)方向，+1代表逆時針旋轉(zhuǎn)，-1代表順時針旋轉(zhuǎn)。

這時，第[i]步旋轉(zhuǎn)可以表示為：

式中：[1（1+2-2i）]是常數(shù)，稱為每次旋轉(zhuǎn)的伸縮系數(shù)，實際應(yīng)用中，如果迭代次數(shù)[n]已知，可以預(yù)先計算出整個迭代過程中的伸縮系數(shù)[Kn=n1（1+2-2i）]，將輸入數(shù)據(jù)校正后再參與運算。式（5）可以簡化為只有加、減、移位的運算，如下：

根據(jù)文獻[6]的結(jié)論可知：

由式（6）～（8）可知，將所需旋轉(zhuǎn)角度作為[z1]輸入，根據(jù)[n]次迭代輸出的[xn+1，][yn+1，]就可得到旋轉(zhuǎn)角度[z1]的三角函數(shù)值。

3.2 CORDIC算法與FFT復(fù)乘運算

由式（3）可知，基4DIT?FFT蝶形運算單元包含復(fù)加，復(fù)乘兩種運算，復(fù)加相當于兩次實數(shù)加法運算，硬件電路易于實現(xiàn)，而復(fù)乘包含四次實數(shù)乘法運算和兩次實數(shù)加法運算，硬件實現(xiàn)較為復(fù)雜，因此討論如何利用CORDIC算法簡化復(fù)乘運算。

選取某一級的蝶形運算中的一個復(fù)乘運算：

為例進行分析，這里，下標[m]表示第[m]級蝶形運算，將[WkN]展開得到：[WkN=exp-j2πkN=cos-2πkN+jsin-2πkN] （10）

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

將[Xm]和[Y]的實部和虛部分開表示，可以得到：

對比式（8），顯然[Xrem]對應(yīng)[x1，][Ximm]對應(yīng)[y1，][-2πkN]對應(yīng)旋轉(zhuǎn)角度[z1。]可見復(fù)乘單元的實部虛部與CORDIC算法中的平面坐標值一一對應(yīng)，因此可以利用CORDIC算法簡化基4DIT?FFT中復(fù)乘單元的硬件實現(xiàn)。

4 FFT復(fù)乘運算的硬件實現(xiàn)

4.1 復(fù)乘單元的整體設(shè)計

通過3.2節(jié)的分析，利用CORDIC算法的復(fù)乘單元的整體設(shè)計框圖如圖3所示，輸入數(shù)據(jù)的實部和虛部首先經(jīng)過伸縮系數(shù)校正模塊，經(jīng)過校正的數(shù)據(jù)分別送入R通道和I通道，為了節(jié)約資源，提高速度，可事先通過Matlab仿真得到[δ0～δ11，]存儲在ROM中，這樣可以免去Z通道，節(jié)約[13]的加減法器。

4.2 伸縮系數(shù)校正模塊的設(shè)計

如3.1節(jié)所述，實際應(yīng)用中，迭代次數(shù)[n]已知可以預(yù)先計算出整個迭代過程中的伸縮系數(shù)，將輸入數(shù)據(jù)校正后再參與運算。本設(shè)計中輸入數(shù)據(jù)為12位字長，故迭代次數(shù)為12次，伸縮系數(shù)為：

如果直接乘以伸縮系數(shù)，將有悖于CORDIC算法的初衷，綜合考慮硬件實現(xiàn)的簡易程度與伸縮誤差，最終選用式（14）所示的迭代近似實現(xiàn)：

其中[δi]根據(jù)Matlab的優(yōu)化程序在-1，0，1三個值中選擇最優(yōu)值。優(yōu)化程序得到的[δi]系數(shù)值如圖4所示（從左到右依次為[δ0～δ11]）：

4.3 旋轉(zhuǎn)系數(shù)的設(shè)計

根據(jù)式（7）和式（8），可通過Matlab仿真得到[δ0～][δ11，]這里僅給出第二級旋轉(zhuǎn)因子[W016，W116，W216，W316]的系數(shù)[δ0～δ11，]以及利用CORDIC算法旋轉(zhuǎn)的角度與實際應(yīng)該旋轉(zhuǎn)角度之間的誤差（見圖5中的[z2]）。

4.4 時序仿真結(jié)果

通過Altera公司的Quartus 9.1軟件對復(fù)乘單元進行設(shè)計，并用Mentor公司的ModelSim 10.1a進行仿真驗證，圖6給出的是字長為12位的實部與字長為12位的虛部作為輸入數(shù)據(jù)與第二級旋轉(zhuǎn)因子之一[W116]進行復(fù)乘的仿真結(jié)果，圖6結(jié)果顯示，輸入數(shù)據(jù)經(jīng)過伸縮因子校正與CORDIC迭代運算共16個周期之后得到輸出結(jié)果。

5 結(jié) 語

本文設(shè)計了一種1 024點12位的基4DIT?FFT處理器。詳細闡述了CORDIC算法在復(fù)乘單元中的設(shè)計與FPGA實現(xiàn)。將復(fù)數(shù)乘法轉(zhuǎn)換為硬件易于實現(xiàn)的加、減、移位運算，并通過Matlab對伸縮系數(shù)與旋轉(zhuǎn)系數(shù)進行預(yù)處理，免去Z通道，大大加快了運算速度，節(jié)約了資源，降低了系統(tǒng)復(fù)雜性。除了適用于本文的基4DIT?FFT，還可用于基2FFT以及分裂基FFT等處理器中，具有很高的研究價值，值得推廣應(yīng)用。

蝶形運算單元的后續(xù)設(shè)計主要為復(fù)數(shù)加減，較為簡單，不再贅述。整個系統(tǒng)受控于狀態(tài)發(fā)生器從而有序工作。地址發(fā)生器可根據(jù)基4DIT?FFT數(shù)據(jù)的存取規(guī)律進行設(shè)計，這里不再詳述。

參考文獻

[1] 周琳.深遠海環(huán)境監(jiān)測水聲通信仿真方法與信道估計研究[D].青島：中國海洋大學(xué)，2011：24?28.

[2] 倪笑園.基于FH/MFSK的水聲通信研究[D].杭州：浙江大學(xué)，2014：7?13.

[3] 李偉，孫進平，王俊，等.一種基于FPGA的超高速32K點FFT處理器[J].北京航空航天大學(xué)學(xué)報，2007，33（12）：1440?1443.

[4] PROAKIS J G， MANOLAKIS D G.數(shù)字信號處理：原理、算法與應(yīng)用[M].張曉林，譯.北京：電子工業(yè)出版社，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.