基于CORDIC的基4－IFFT/FFT算法的硬件實現(xiàn)

王玉華，溫 浩，任宏亮，覃亞麗

(浙江工業(yè)大學(xué)信息學(xué)院，浙江杭州310023)

0 引言

快速傅立葉變換是正交頻分復(fù)用(Orthogonal Frequency Division Multiplexing，OFDM)技術(shù)中重要的數(shù)字信號處理方式。在可見光通信中［1］，當(dāng)傳輸速率在100Mb/s以下時碼間干擾對通信系統(tǒng)的性能影響不大，當(dāng)速度更高時，利用OFDM可減少碼間干擾的優(yōu)勢，將本文給出的算法應(yīng)用于可見光OFDM調(diào)制系統(tǒng)中，既能實現(xiàn)高速傳輸，又能大大降低成本。近幾年來，人們不斷地對坐標(biāo)旋轉(zhuǎn)數(shù)字計算機(Coordinated Rotation Digital Computer，CORDIC)算法進行探索研究，并提出了相應(yīng)的算法和方案以適應(yīng)不同的需求［2］。FFT有基－2，基－4，基－8等多種算法，基數(shù)越高，總運算量就越少。但基數(shù)越大，實現(xiàn)起來也越復(fù)雜。Cyclone II系列器件的成本比第一代Cyclone器件低30%，邏輯容量大了3倍多，可滿足低成本大批量應(yīng)用需求。為避免使用乘法器，簡化結(jié)構(gòu)，減少處理器內(nèi)核面積，可采用CORDIC算法實現(xiàn)基4－FFT算法。

1 基4－FFT與CORDIC算法的基本原理

基4－FFT的基本原理如下:設(shè)x(n)為N點有限長序列，其DFT為:

從式2可以看出一個4點組合迭代需要進行3次復(fù)數(shù)乘法和8次復(fù)數(shù)加減法運算，與傳統(tǒng)的基2－FFT算法比較，整個基4－FFT過程中的乘法次數(shù)減少了25%。

CORDIC算法的基本原理是:設(shè)數(shù)據(jù)與旋轉(zhuǎn)因子相乘的表達式為:Xk=X0，其中設(shè)X0=x0+jy0，Xk=xk+jyk，將旋轉(zhuǎn)因子代入，令θ=－2 kn/N，結(jié)合歐拉公式可得Xk的實部和虛部分別如下式所示，復(fù)數(shù)序列和旋轉(zhuǎn)因子相乘可看作是將向量X0旋轉(zhuǎn)了θ角度，假設(shè)初始向量經(jīng)過N次旋轉(zhuǎn)后得到新向量，且每次旋轉(zhuǎn)角度δ為2的倍數(shù)，則:

第i次旋轉(zhuǎn)角度為δ(i)=arctan(2－i)，當(dāng)旋轉(zhuǎn)次數(shù)一定時會趨于一個常數(shù)。從式3也可看出，對于角度θ，只需要硬件加減法和移位器就可得出結(jié)果，其中移位器用來實現(xiàn)乘法和除法，從而減少硬件資源。

2 蝶形運算器的結(jié)構(gòu)設(shè)計

FFT蝶形單元硬件實現(xiàn)主要有4種方式:遞歸結(jié)構(gòu)、級聯(lián)結(jié)構(gòu)、并行結(jié)構(gòu)和陣列結(jié)構(gòu)。本文采用了遞歸結(jié)構(gòu)的蝶形運算，以1個基4蝶形運算單元為基本結(jié)構(gòu)，每一級運算按遞歸方式進行。蝶形運算單元一直出于忙碌狀態(tài)，直至運算結(jié)束。遞歸結(jié)構(gòu)的主要優(yōu)點就是硬件占用資源少，結(jié)構(gòu)簡單，從而使其控制邏輯單元的設(shè)計更加清晰明了，處理器的穩(wěn)定性較高。

基4－蝶形運算結(jié)構(gòu)如圖1所示。蝶形運算中每一級輸出的結(jié)果分別經(jīng)地址產(chǎn)生器到實部和虛部存儲器并按遞歸方式輸入基4運算模塊進行下一級的運算。FFT或IFFT運算的選擇，取決于標(biāo)志信號的值，它為0，則進行FFT運算;它為1，則進行IFFT運算。

圖1 基4－蝶形運算結(jié)構(gòu)

復(fù)數(shù)乘法器模塊將基4運算模塊中產(chǎn)生的數(shù)據(jù)與旋轉(zhuǎn)因子相乘，為避免使用乘法器，采用流水線結(jié)構(gòu)的CORDIC算法，只需移位和加減法即可實現(xiàn)乘法。由式δ(i)=arctan(2－i)看出知道旋轉(zhuǎn)次數(shù)i，就可知道旋轉(zhuǎn)度數(shù)。所以在編碼中設(shè)置了一個arctangent函數(shù)，它的功能是根據(jù)旋轉(zhuǎn)次數(shù)i，返回一個20bit的arctangent值。預(yù)先把旋轉(zhuǎn)次數(shù)與對應(yīng)返回值arctangent放入表中［7］，加快了運算速度。通過計算發(fā)現(xiàn)當(dāng)i大于17時，輸出結(jié)果基本為0，即與起始值重合。

3 仿真結(jié)果及硬件實現(xiàn)

本文選用Altera公司生產(chǎn)的Cyclone II系列芯片進行驗證，時鐘頻率50MHz，F(xiàn)FT點數(shù)為1 024。在VHDL語言中只能輸入整數(shù)，而FFT處理過程中會出現(xiàn)小數(shù)，所以將12位的處理序列按定點運算的方式表示，前4位為有效的整數(shù)位，后8位為小數(shù)位。同樣，14位的輸出序列中高2位為符號位，后12位定義同輸入。根據(jù)如下判斷準(zhǔn)則:當(dāng)輸出序列的符號位為“00”時，若輸出整數(shù)位=輸入整數(shù)位，則說明結(jié)果正確;若當(dāng)輸出序列的符號位為“11”時，若輸出整數(shù)位+1=輸入整數(shù)位，則說明結(jié)果正確，反之有誤。小數(shù)位可忽略。如此準(zhǔn)確地實現(xiàn)數(shù)據(jù)的發(fā)送與接收。

為實現(xiàn)OFDM信號的實數(shù)化，方便應(yīng)用于可見光OFDM調(diào)制解調(diào)系統(tǒng)中，令輸入序列滿足Hermi-tian對稱，即x(N－m)=x(m)*，其中N=1 024為FFT點數(shù)。經(jīng)多組數(shù)據(jù)的反復(fù)驗證，證實本文給出算法的正確性。為方便截圖，將二進制序列用帶符號的整數(shù)表示，例如100000000000表示為－2048。分別在位置 1，93，96，99，101，104，108，111，913，916，920，923，925，928，931 的位置按 Hermitian 對稱的規(guī)律，輸入(實部)/(虛部):－2048/0，0/256，0/512，0/768，0/1024，0/1280，0/1536，0/1792，0/－1792，0/－1536，0/－1280，0/－1024，0/－768，0/－512，0/－256，仿真結(jié)果如圖2 所示，指定位置輸出數(shù)據(jù)的放大圖如圖3、4所示。

圖2 1 024點FFT的輸出結(jié)果

圖3 第92至110位置上的輸出值

圖4 第912至933位置上的輸出值

為了便于分析，分別將輸入序列的整數(shù)位與輸出序列的符號位與整數(shù)位整理如表1所示。從劃線部分可以看出，根據(jù)判斷準(zhǔn)則，輸出序列與輸入序列完全一致。

表1 輸入/輸出序列整數(shù)位比較表

在驗證算法正確的基礎(chǔ)上單獨仿真基于CORDIC的基4－FFT算法，編譯結(jié)果如圖5所示，硬件連接圖如圖6所示。

圖5 時序仿真編譯報告

圖6 硬件實現(xiàn)連接圖

從時序仿真結(jié)果中可以看出，本文給出的算法只用了1 949個邏輯塊，1 229個專用寄存器，0個乘法器，這不僅體現(xiàn)了CORDIC算法可避免使用乘法器的優(yōu)點，而且相比于文獻［4］中1 024點級聯(lián)結(jié)構(gòu)的FFT處理消耗了4 399個邏輯單元，本算法使用的邏輯塊單元減少了55%。對于64點的FFT運算，在20MHz時鐘頻率下，本文給出的算法運行時間如圖7所示，約為13μs，與文獻5中流水線結(jié)構(gòu)的處理消耗時間 12μs相比，僅慢了1μs，同樣可達較高的速度［5］。

圖7 64點－FFT波形仿真圖

4 結(jié)束語

本文給出了基于CORDIC的基4－IFFT/FFT算法，結(jié)果表明，該算法對于1 024點FFT運算只需1 949個邏輯塊和1 229個寄存器，較級聯(lián)結(jié)構(gòu)的處理器省55%的硬件資源。對于64點FFT運算與流水線結(jié)構(gòu)的處理器相比，速度依然較快。整個系統(tǒng)遞歸結(jié)構(gòu)、CORDIC算法、查表法找旋轉(zhuǎn)因子的設(shè)計應(yīng)用大大節(jié)省了硬件資源，又采用模塊化思想設(shè)計，可移植性強，通用好，稍作改動，可實現(xiàn)不同精度和FFT點數(shù)的運算。很適用于可見光OFDM調(diào)制解調(diào)系統(tǒng)。

［1］Shinichiro Haruyama.Visible light communication using sustainable LED lights［C］.Geneva:International Telecommunication Union，2013:100 －106.

［2］鞠建波，杜愛國.基于CORDIC算法的QDDS的FPGA實現(xiàn)及精度分析［J］.電視技術(shù)，2007，47(1):112－116.

［3］鄭君里，應(yīng)啟珩，楊為理.信號與系統(tǒng)(第2版)［M］.北京:高等教育出版社，2000，136－137.

［4］張竺軍，錢建平.基于FPGA的級聯(lián)結(jié)構(gòu)FFT處理器的優(yōu)化設(shè)計［J］.計算機應(yīng)用技術(shù)，2009，26(22):141－143.

［5］蔣斌，黃華燦.64 點 FFT/IFFT 的 FPGA 實現(xiàn)［J］.電子技術(shù)，2008，8(4):37－39.