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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

為實(shí)現(xiàn)OFDM信號(hào)的實(shí)數(shù)化，方便應(yīng)用于可見(jiàn)光OFDM調(diào)制解調(diào)系統(tǒng)中，令輸入序列滿足Hermi-tian對(duì)稱(chēng)，即x(N－m)=x(m)*，其中N=1 024為FFT點(diǎn)數(shù)。經(jīng)多組數(shù)據(jù)的反復(fù)驗(yàn)證，證實(shí)本文給出算法的正確性。為方便截圖，將二進(jìn)制序列用帶符號(hào)的整數(shù)表示，例如100000000000表示為－2048。分別在位置 1，93，96，99，101，104，108，111，913，916，920，923，925，928，931 的位置按 Hermitian 對(duì)稱(chēng)的規(guī)律，輸入(實(shí)部)/(虛部):－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點(diǎn)FFT的輸出結(jié)果

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

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

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

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

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

圖5 時(shí)序仿真編譯報(bào)告

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

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

圖7 64點(diǎn)－FFT波形仿真圖

4 結(jié)束語(yǔ)

本文給出了基于CORDIC的基4－IFFT/FFT算法，結(jié)果表明，該算法對(duì)于1 024點(diǎn)FFT運(yùn)算只需1 949個(gè)邏輯塊和1 229個(gè)寄存器，較級(jí)聯(lián)結(jié)構(gòu)的處理器省55%的硬件資源。對(duì)于64點(diǎn)FFT運(yùn)算與流水線結(jié)構(gòu)的處理器相比，速度依然較快。整個(gè)系統(tǒng)遞歸結(jié)構(gòu)、CORDIC算法、查表法找旋轉(zhuǎn)因子的設(shè)計(jì)應(yīng)用大大節(jié)省了硬件資源，又采用模塊化思想設(shè)計(jì)，可移植性強(qiáng)，通用好，稍作改動(dòng)，可實(shí)現(xiàn)不同精度和FFT點(diǎn)數(shù)的運(yùn)算。很適用于可見(jiàn)光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］鞠建波，杜愛(ài)國(guó).基于CORDIC算法的QDDS的FPGA實(shí)現(xiàn)及精度分析［J］.電視技術(shù)，2007，47(1):112－116.

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

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

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