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

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

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

1 總體設(shè)計(jì)

目前基于FPGA的FFT硬件實(shí)現(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)中占用硬件資源最少，但由于只有一個(gè)運(yùn)算單元，因此運(yùn)算時(shí)間最長(zhǎng)。流水線結(jié)構(gòu)是級(jí)聯(lián)結(jié)構(gòu)， FFT的每一級(jí)都使用一個(gè)獨(dú)立的運(yùn)算單元，前一級(jí)運(yùn)算結(jié)果可以直接用于下一級(jí)運(yùn)算而無需等到本級(jí)運(yùn)算全部完成，因此在運(yùn)算速度上有所提高，但同時(shí)占用的硬件資源也隨之增多。全并行結(jié)構(gòu)則是在FFT的每一級(jí)都設(shè)置與FFT的點(diǎn)數(shù)成正比的運(yùn)算單元數(shù)，顯然該結(jié)構(gòu)在三種結(jié)構(gòu)中運(yùn)算速度最快，硬件資源占用也最多。

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

2 基4DIT?FFT

2.1 基4DIT?FFT的運(yùn)算單元

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

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

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

2.2 基4DIT?FFT的選擇

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

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

3.1 CORDIC算法基本原理

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

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

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

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

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

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

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

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

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

選取某一級(jí)的蝶形運(yùn)算中的一個(gè)復(fù)乘運(yùn)算：

為例進(jìn)行分析，這里，下標(biāo)[m]表示第[m]級(jí)蝶形運(yùn)算，將[WkN]展開得到：[WkN=exp-j2πkN=cos-2πkN+jsin-2πkN] （10）

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

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

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

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

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

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

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

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

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

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

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

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

4.4 時(shí)序仿真結(jié)果

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

5 結(jié) 語

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

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

參考文獻(xiàn)

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

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

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

[4] PROAKIS J G， MANOLAKIS D G.數(shù)字信號(hào)處理：原理、算法與應(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.