孔令甲

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

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

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

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

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

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

1.1 CORDIC算法原理

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

CORDIC 算法分為矢量方式（Vector Mode）和旋轉(zhuǎn)方式（Rotation Mode）兩種旋轉(zhuǎn)方式。矢量方式是給定一個(gè)矢量的X、Y 坐標(biāo)，計(jì)算該矢量的大?。ㄆ椒胶偷钠椒礁┖徒嵌?；旋轉(zhuǎn)方式是給定初始矢量的X、Y 坐標(biāo)以及要旋轉(zhuǎn)的角度，計(jì)算旋轉(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)的四種不同組合，可以分別完成不同的運(yùn)算。具體來說，在笛卡爾坐標(biāo)平面上將點(diǎn)P(x,y)逆時(shí)針旋轉(zhuǎn)θ 角度得到P(x,y)，CORDIC 算法的基本思想是將旋轉(zhuǎn)角度θ 分解成一系列小角度θ，逐漸逼近θ。規(guī)定單次旋轉(zhuǎn)的小角度θ正切值為tanθ=2，則小角度旋轉(zhuǎn)角度正切值和坐標(biāo)值乘法可以通過移位完成。

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

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

表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ù)選多，越逼近真實(shí)的目標(biāo)值，得到的計(jì)算精度越高。但是，越多的迭代次數(shù)也意味著更大的延時(shí)和硬件消耗。本文提出改進(jìn)的CORDIC 算法，增加每次的迭代角度選擇判定，減小迭代次數(shù)，從而減少計(jì)算時(shí)間。由式（6）可得：

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

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

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

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

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

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

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

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

基4 FFT 算法單個(gè)碟形運(yùn)算流圖如圖1 所示。

圖1：基4 碟形運(yùn)算

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

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

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

圖2：CORDIC 算法實(shí)現(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ù)乘法運(yùn)算。旋轉(zhuǎn)因子不需要預(yù)先計(jì)算存放在ROM 表中，F(xiàn)FT 處理器根據(jù)當(dāng)前運(yùn)算的級數(shù)和數(shù)據(jù)位置由內(nèi)部狀態(tài)機(jī)實(shí)時(shí)產(chǎn)生旋轉(zhuǎn)因子的系數(shù)nk，之后給串行流水線結(jié)構(gòu)完成復(fù)數(shù)乘法和其他運(yùn)算，這樣節(jié)約了選擇因子ROM 存儲表帶來的硬件消耗。

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

FFT 設(shè)計(jì)采用串行流水線單路延時(shí)置換結(jié)構(gòu)。1024 點(diǎn)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ù)運(yùn)算。控制模塊內(nèi)部計(jì)數(shù)器根據(jù)當(dāng)前每一級運(yùn)算數(shù)據(jù)序列位置實(shí)時(shí)產(chǎn)生旋轉(zhuǎn)因子系數(shù)給CORDIC_BF 單元。FFT 運(yùn)算完成，運(yùn)算結(jié)果輸出實(shí)部和虛部給CORDIC 幅值運(yùn)算單元完成模值運(yùn)算?？刂颇K內(nèi)部計(jì)數(shù)器根據(jù)當(dāng)前每一級運(yùn)算數(shù)據(jù)序列位置實(shí)時(shí)產(chǎn)生旋轉(zhuǎn)因子系數(shù)給CORDIC_BF 單元。

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

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

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

2 結(jié)果分析

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

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

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

表3：結(jié)果對比

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

3 結(jié)論

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