基于一種改進(jìn)的CORDIC 算法的FFT 芯片設(shè)計

孔令甲

（中國電子科技集團(tuán)公司第十三研究所 河北省石家莊市 050000）

快速傅里葉變換算法實現(xiàn)了信號從時域到頻域的變換，運算速度快，在數(shù)字信號處理系統(tǒng)中應(yīng)用廣泛。FFT 算法利用DFT 運算旋轉(zhuǎn)因子的對稱性、周期性、可壓縮、擴(kuò)展性的特征來減少計算量，完成快速計算頻譜的目的。FFT算法的硬件實現(xiàn)其硬件消耗主要集中在數(shù)據(jù)緩存和復(fù)數(shù)乘法碟形運算中，復(fù)數(shù)乘法運算算法是在單個或多個周期完成一次復(fù)數(shù)運算，運算量較大，復(fù)數(shù)乘法選擇的運算的復(fù)雜性也會限制硬件的工作速度。

目前，為提高FFT 的精度和降低硬件消耗，一些研究者提出混合基等高基算法、可配置點數(shù)位寬、精度可調(diào)結(jié)構(gòu)等方案來改進(jìn)傳統(tǒng)的radix-2FFT 算法和結(jié)構(gòu)。但這些算法結(jié)構(gòu)復(fù)雜，只是在精度或者速度等單個指標(biāo)性能較優(yōu)，沒有在硬件面積、速度、精度等方面達(dá)到一個比較均衡的結(jié)果。FFT 處理器每一級運算需要進(jìn)行一次碟形運算，傳統(tǒng)的FFT 實現(xiàn)方式是提前把碟形運算的旋轉(zhuǎn)因子存儲在內(nèi)部存儲空間ROM 中，之后通過讀取ROM 模塊，完成復(fù)數(shù)乘法運算，這需要消耗一定的硬件面積。

CORDIC 算法通過簡單的多次加法與移位運算，可以完成復(fù)數(shù)乘法、模計算、三角函數(shù)計算等，硬件結(jié)構(gòu)實現(xiàn)簡單，在工程中應(yīng)用廣泛。但是在需要完成較高運算精度的情況下，傳統(tǒng)的CORDIC 迭代次數(shù)較高，會影響FFT 的實時處理速度。當(dāng)FFT 運算點數(shù)越多，運算級數(shù)越多的情況下，CORDIC 迭代運算帶來的時間消耗成倍增加。

本文提出了一種改進(jìn)的CORDIC 算法實現(xiàn)復(fù)數(shù)乘法運算，通過改進(jìn)單次迭代角度和旋轉(zhuǎn)方程式，改進(jìn)當(dāng)前選擇角度判斷方程，在實現(xiàn)同樣計算精度的情況下可以將迭代次數(shù)減半，減少蝶形運算時間，提高FFT 運算速度。蝶形運算的旋轉(zhuǎn)因子的旋轉(zhuǎn)系數(shù)通過控制模塊內(nèi)部實時產(chǎn)生，從而減少ROM 開銷，減小FFT 硬件面積。通過合理的設(shè)置CORDIC 算法迭代次數(shù)和每次運算的數(shù)據(jù)截斷位數(shù)，可以實現(xiàn)較高的FFT 運算精度。

1 原理分析及設(shè)計

1.1 CORDIC算法原理

坐標(biāo)旋轉(zhuǎn)數(shù)字計算CORDIC 算法是由Jack E. Volder于1959 年提出來的，當(dāng)時主要用于實時飛行計算，此后CORDIC 算法在各個領(lǐng)域獲得廣泛的應(yīng)用。

CORDIC 算法分為矢量方式（Vector Mode）和旋轉(zhuǎn)方式（Rotation Mode）兩種旋轉(zhuǎn)方式。矢量方式是給定一個矢量的X、Y 坐標(biāo)，計算該矢量的大?。ㄆ椒胶偷钠椒礁┖徒嵌?；旋轉(zhuǎn)方式是給定初始矢量的X、Y 坐標(biāo)以及要旋轉(zhuǎn)的角度，計算旋轉(zhuǎn)后矢量的大小和角度。

矢量方式是由旋轉(zhuǎn)方式派生出來的，在旋轉(zhuǎn)方式中，將初始矢量旋轉(zhuǎn)到角度為0，則轉(zhuǎn)過的角度即為初始矢量的角度的負(fù)數(shù)，而新的X 坐標(biāo)與初始矢量的大小成正比。該比例系數(shù)為常數(shù)K。對于矢量模式、旋轉(zhuǎn)模式和圓旋轉(zhuǎn)、線旋轉(zhuǎn)的四種不同組合，可以分別完成不同的運算。具體來說，在笛卡爾坐標(biāo)平面上將點P(x,y)逆時針旋轉(zhuǎn)θ 角度得到P(x,y)，CORDIC 算法的基本思想是將旋轉(zhuǎn)角度θ 分解成一系列小角度θ，逐漸逼近θ。規(guī)定單次旋轉(zhuǎn)的小角度θ正切值為tanθ=2，則小角度旋轉(zhuǎn)角度正切值和坐標(biāo)值乘法可以通過移位完成。

點P(x,y)，逆時針旋轉(zhuǎn)θ 角度到P(x,y)。

經(jīng)過多次旋轉(zhuǎn)角度迭代，偽旋轉(zhuǎn)的幅度偏差可以近似為一個固定值：

表1：判決因子

經(jīng)過偽旋轉(zhuǎn)，P(x,y)旋轉(zhuǎn)到正確的角度，但模值增加1/cosθ 倍，伸縮因子可以通過查表得到。

從而坐標(biāo)旋轉(zhuǎn)轉(zhuǎn)換成簡單的加減法和移位操作。

1.2 改進(jìn)的CORDIC算法

根據(jù)以上的推導(dǎo)分析，CORDIC 算法的旋轉(zhuǎn)次數(shù)選多，越逼近真實的目標(biāo)值，得到的計算精度越高。但是，越多的迭代次數(shù)也意味著更大的延時和硬件消耗。本文提出改進(jìn)的CORDIC 算法，增加每次的迭代角度選擇判定，減小迭代次數(shù)，從而減少計算時間。由式（6）可得：

根據(jù)新的偽旋轉(zhuǎn)方程式和角度累加方程式，新的 歷次迭代角度如表2 所示。

表2：改進(jìn)的CORDIC 算法歷次旋轉(zhuǎn)角度

則改進(jìn)的方程式只需傳統(tǒng)的CORDIC 算法的一半迭代次數(shù)，即可以達(dá)到相同的計算精度，從而減少了迭代運算帶來的計算延時，提高FFT 實時處理能力。

1.3 改進(jìn)的CORDIC算法在FFT硬件實現(xiàn)中的應(yīng)用

1.3.1 復(fù)數(shù)乘法

本文采用基4-FFT 算法完成芯片設(shè)計。設(shè)輸入序列長度為N=4M（M 為正整數(shù)）。

當(dāng)序列點數(shù)滿足N=4時，可以將x(n)分解抽取，n 分為4m、4m+1、4m+2、4m+3，將該序列按時間順序的奇偶分解為4 個子序列有：

基4 FFT 運算在每次碟形運算之前先進(jìn)行復(fù)數(shù)乘法運算（），包含四次乘法兩次加法，運算量較大。

基4 FFT 算法單個碟形運算流圖如圖1 所示。

圖1：基4 碟形運算

每一次碟形運算完成之后需要進(jìn)行3 次復(fù)數(shù)乘法，而單次復(fù)數(shù)乘法需要完成如下運算：

式（9）、（10）分別代表復(fù)數(shù)運算結(jié)果的實部和虛部。因此，復(fù)數(shù)運算可以看作是數(shù)據(jù)旋轉(zhuǎn)-2nkπ/N 角度。利用CORDIC 算法，多次累計迭代標(biāo)定z角度，累加θ(n)無限逼近目標(biāo)旋轉(zhuǎn)角度值z(0)（-2nkπ/N），如果前一次累積旋轉(zhuǎn)級數(shù)角度z大于目標(biāo)旋轉(zhuǎn)角度z(0)，則當(dāng)前累積旋轉(zhuǎn)角度z減去θ(n)，為此次順時針旋轉(zhuǎn)角度θ(n)。如果前一次累積旋轉(zhuǎn)級數(shù)角度z小于目標(biāo)旋轉(zhuǎn)角度z(0)，則當(dāng)前累積旋轉(zhuǎn)角度加上θ(n)，為此次逆時針旋轉(zhuǎn)角度θ(n)。迭代次數(shù)越多，幅度偏差K 值近似為常數(shù)0.60725。

CORDIC 算法實現(xiàn)復(fù)數(shù)乘法結(jié)構(gòu)框圖如圖2 所示。

圖2：CORDIC 算法實現(xiàn)復(fù)數(shù)乘法結(jié)構(gòu)框圖

數(shù)據(jù)傳輸給復(fù)數(shù)乘法模塊前首先進(jìn)行預(yù)處理，根據(jù)z(0)初始值將初始數(shù)據(jù)做取反和符號位預(yù)處理，操作預(yù)旋轉(zhuǎn)π/2或π，后面的CORDIC 迭代旋轉(zhuǎn)角度在[π/2, π]區(qū)間，之后通過CORDIC 算法迭代使z(k)逼近0，完成復(fù)數(shù)乘法運算。旋轉(zhuǎn)因子不需要預(yù)先計算存放在ROM 表中，F(xiàn)FT 處理器根據(jù)當(dāng)前運算的級數(shù)和數(shù)據(jù)位置由內(nèi)部狀態(tài)機(jī)實時產(chǎn)生旋轉(zhuǎn)因子的系數(shù)nk，之后給串行流水線結(jié)構(gòu)完成復(fù)數(shù)乘法和其他運算，這樣節(jié)約了選擇因子ROM 存儲表帶來的硬件消耗。

1.3.2 基于CORDIC 算法的FFT 硬件設(shè)計

FFT 設(shè)計采用串行流水線單路延時置換結(jié)構(gòu)。1024 點FFT 由5 級流水線完成，，第一級碟形單元包含深度為256的3 塊RAM 進(jìn)行數(shù)據(jù)緩存，后面級數(shù)依此類推，各級數(shù)據(jù)緩存寄存器數(shù)量消耗為64..4/1，后四級數(shù)據(jù)緩存數(shù)量少，直接用寄存器代替RAM。

每一級碟形單元調(diào)用CORDIC_BF 單元進(jìn)行一次復(fù)數(shù)運算。控制模塊內(nèi)部計數(shù)器根據(jù)當(dāng)前每一級運算數(shù)據(jù)序列位置實時產(chǎn)生旋轉(zhuǎn)因子系數(shù)給CORDIC_BF 單元。FFT 運算完成，運算結(jié)果輸出實部和虛部給CORDIC 幅值運算單元完成模值運算?？刂颇K內(nèi)部計數(shù)器根據(jù)當(dāng)前每一級運算數(shù)據(jù)序列位置實時產(chǎn)生旋轉(zhuǎn)因子系數(shù)給CORDIC_BF 單元。

FFT 硬件實現(xiàn)結(jié)構(gòu)框圖如圖3 所示。

圖3：FFT 硬件實現(xiàn)結(jié)構(gòu)框圖

數(shù)據(jù)采用定點運算，輸入數(shù)據(jù)為12bit，為提高計算精度減少截斷誤差，選擇因子系數(shù)為12bit ，選擇CORDIC 運算迭代次數(shù)為12 次。在數(shù)據(jù)輸入時首先進(jìn)行零值檢驗判定，減少計算誤差。采用上述結(jié)構(gòu)，用VERILOG 語言完成1024點FFT 運算模塊設(shè)計，通過VCS 進(jìn)行仿真驗證，利用MATLAB 內(nèi)部FFT 算法作為標(biāo)準(zhǔn)參考輸出驗證設(shè)計。

2 結(jié)果分析

采用0.18um 工藝對設(shè)計進(jìn)行時序綜合和后端版圖設(shè)計并流片。搭建芯片測試平臺，驗證FFT功能，圖4為測試結(jié)果。

圖4：芯片測試結(jié)果

表3 為本設(shè)計和部分參考文獻(xiàn)的設(shè)計結(jié)果對比。

表3：結(jié)果對比

本設(shè)計的測試結(jié)果SNQR 有一定優(yōu)勢，信號量化噪聲是數(shù)據(jù)位寬、截斷誤差等多方面的影響，結(jié)果可以說明基于改進(jìn)的CORDIC 算法完成的FFT 處理器具有較高的運算精度。同時，基于CORDIC 算法采用流水線型SDF 結(jié)構(gòu)完成的FFT 模塊與通用復(fù)數(shù)乘法方案面積優(yōu)勢較大。綜合面積、精度、計算時間幾個指標(biāo)，本設(shè)計方案具有一定的優(yōu)勢。

3 結(jié)論

基于改進(jìn)的CORDIC 算法完成的FFT 復(fù)數(shù)運算模塊通過多次迭代完成碟形運算，可以減少通用復(fù)數(shù)乘法運算時間，提高FFT 實時處理能力。同時，CORDIC 算法模塊可以復(fù)用在FFT 的復(fù)數(shù)求模運算中，在相同的運算精度的情況下減少CORDIC 算法迭代次數(shù)。FFT 運算旋轉(zhuǎn)因子的旋轉(zhuǎn)系數(shù)通過控制模塊處理器內(nèi)部實時產(chǎn)生，不需要提前存儲旋轉(zhuǎn)因子，減少了ROM 開銷。同時通過合理的硬件結(jié)構(gòu)和數(shù)據(jù)位數(shù)、截斷位數(shù)分配，此方案可以實現(xiàn)較高的計算精度和計算速度，在工程應(yīng)用中具有一定的優(yōu)勢。