馬思強(qiáng)，王首斌，邵國峰

（中國電子科技集團(tuán)公司第三十六研究所，浙江嘉興314033）

CORDIC算法在數(shù)字頻率合成中的應(yīng)用研究與實(shí)現(xiàn)

馬思強(qiáng)，王首斌，邵國峰

（中國電子科技集團(tuán)公司第三十六研究所，浙江嘉興314033）

相較于傳統(tǒng)的基于ROM查找表的數(shù)字頻率合成方案，采用CORDIC算法來計(jì)算正余弦函數(shù)時，無需使用乘法器，只需要一個最小的查找表（LUT），利用簡單的移位和相加運(yùn)算，即可產(chǎn)生高精度的正余弦波形，可以有效節(jié)省存儲資源，非常適合于在FPGA上實(shí)現(xiàn)。在CORDIC算法研究的基礎(chǔ)上，合理設(shè)計(jì)了CORDIC電路的實(shí)現(xiàn)結(jié)構(gòu)，并通過Verilog HDL語言進(jìn)行了硬件描述設(shè)計(jì)，整個設(shè)計(jì)方案通過算法驗(yàn)證并最終在Altera Stratix II系列EP2S130F1020C5型FPGA上完成了布局布線，最高工作頻率為145.2MHz。

CORDIC；FPGA；三角函數(shù)

0 引言

近些年來，隨著集成電路技術(shù)的發(fā)展，坐標(biāo)旋轉(zhuǎn)數(shù)字算法（CORDIC）的優(yōu)勢越來越明顯，因此它被廣泛應(yīng)用于數(shù)字信號處理領(lǐng)域。

CORDIC算法是用于計(jì)算廣義矢量旋轉(zhuǎn)的一種迭代方法，最早由Volder于1959年提出［1］，在此基礎(chǔ)上Walther提出了統(tǒng)一的CORDIC算法［2］，并將CORDIC實(shí)現(xiàn)的三種功能：三角函數(shù)運(yùn)算、雙曲運(yùn)算和線性運(yùn)算統(tǒng)一于一個表達(dá)式中，形成了CORDIC算法的基本數(shù)學(xué)基礎(chǔ)。CORDIC算法的基本思想是通過一系列角度的旋轉(zhuǎn)來逼近目標(biāo)角度，并且這一系列的角度是預(yù)先經(jīng)過挑選設(shè)定的，這一旋轉(zhuǎn)過程可以通過移位和加減法運(yùn)算的方法實(shí)現(xiàn)。所以針對實(shí)現(xiàn)復(fù)雜功能運(yùn)算，利用CORDIC算法能夠取得較好的硬件資源節(jié)約效果。

1 CORDIC算法原理

CORDIC算法的基本原理可以通過極坐標(biāo)的形式進(jìn)行說明，已知一個目標(biāo)點(diǎn)（Xn，Yn）通過旋轉(zhuǎn)角度θn后可以達(dá)到另一個點(diǎn)，記作（Xn+1，Yn+1），這一旋轉(zhuǎn)過程可以通過矩陣的形式表示，具體為：

將cosθn提出，從而可以得到：

如果取θn=arctan（2-n），并將θn定義為每一次旋轉(zhuǎn)的角度，則所有迭代旋轉(zhuǎn)角度的總和θ可以表示為：

此時式（2）中的tanθn=Sn2-n，則式（2）可以轉(zhuǎn)換為：

式中，cosθn=cos（arctan（2-n）），隨著迭代次數(shù)的增加，該式可以收斂為一個常數(shù)：

可以暫時不考慮這個增益常數(shù)K，這時式（5）可以改寫為：

這里用Z來表示相位累加的部分和，則可以得到：

因此可以給出CORDIC算法最核心的三個迭代公式為：

如果想將Z最終旋轉(zhuǎn)到0，則Sn的取值由Zn決定，具體表現(xiàn)如下：

通過上面的分析，經(jīng)過多次旋轉(zhuǎn)之后，最終的表達(dá)式結(jié)果可以總結(jié)為：

如果取一組特殊的初始值：

通過若干次迭代旋轉(zhuǎn)之后，使得Z最終旋轉(zhuǎn)到0時，則可以得到最終結(jié)果為：

一般將這種工作模式稱為旋轉(zhuǎn)工作模式。如果取如下的初始值：

并通過不斷旋轉(zhuǎn)使得Y趨近于0，Sn的取值由Yn決定，具體表現(xiàn)如下：

通過若干次迭代旋轉(zhuǎn)之后，使得Y最終旋轉(zhuǎn)到0時，則可以得到最終結(jié)果為：

通過這種方式可以得到已知向量的幅值和相角，這種模式被稱為向量工作模式。

2 CORDIC算法的角度范圍

在具體應(yīng)用CORDIC算法時，該算法所能旋轉(zhuǎn)的角度是有界限的。這里假設(shè)算法迭代次數(shù)為N，那么通過N次旋轉(zhuǎn)之后可以得到的角度范圍為［3］：

通過進(jìn)一步的取極限運(yùn)算，這個角度范圍將收斂至［-99.88°，99.88°］。這樣如果采用CORDIC算法，并基于旋轉(zhuǎn)模式進(jìn)行求解已知角度θ的正弦和余弦值時，就要求θ的取值范圍滿足［-99.88°，99.88°］。而一般意義上來說θ的取值范圍應(yīng)該為［-π，π］，因此有必要利用三角函數(shù)特性對角度輸入信號進(jìn)行相關(guān)處理，使得其滿足CORDIC算法關(guān)于輸入角度的范圍限制。

3 CORDIC算法的硬件實(shí)現(xiàn)

基于CORDIC算法的三角函數(shù)合成方法相較傳統(tǒng)的查找表法具有高精度、低存儲資源消耗的特點(diǎn)。由于整個算法主要由基本的加、減法和移位操作組成，因此十分適合VLSI實(shí)現(xiàn)。圖1所示為本文設(shè)計(jì)的數(shù)字頻率合成器（CORDIC）模塊的端口信號示意圖。為了滿足設(shè)計(jì)電路的高速處理需要，本文確定了基于多級流水的CORDIC結(jié)構(gòu)設(shè)計(jì)方案。為了計(jì)算輸入的瞬時相位信息所對應(yīng)的正余弦函數(shù)值，CORDIC模塊將工作在旋轉(zhuǎn)模式。本文所設(shè)計(jì)的CORDIC模塊依然工作在系統(tǒng)時鐘100MHz環(huán)境下，且由系統(tǒng)復(fù)位信號rst_n對內(nèi)部寄存器進(jìn)行復(fù)位操作。

圖1 CORDIC模塊的端口信號示意圖

關(guān)于CORDIC算法迭代次數(shù)的選取及其精度分析，眾多文獻(xiàn)［4-5］給出了證明和結(jié)論?？傮w來說，CORDIC算法的迭代次數(shù)跟所表達(dá)角度值的小數(shù)位比特寬度有關(guān)。如果想要分解由b個比特小數(shù)位表示的角度值，CORDIC算法所選取的迭代次數(shù)N應(yīng)該大于或等于b+1。這是由于如果角度可以被多次分解，則其最小精度單位2-b應(yīng)該有意義。經(jīng)過CORDIC算法多次迭代操作之后，最后一次迭代中的θn-1應(yīng)該小于或等于2-b。當(dāng)θn-1足夠小時，其值可取2-（n-1）來近似，因此可以得到迭代次數(shù)N與角度小數(shù)位寬度b之間的關(guān)系。由于本文把輸入的瞬時相位的小數(shù)位寬度確定為11個比特，因此在具體設(shè)計(jì)中采用了12次迭代來實(shí)現(xiàn)CORDIC算法。

由于輸入相位θ的范圍為［-π，π］，而根據(jù)前面內(nèi)容可知，CORDIC算法輸入角度的取值范圍應(yīng)為［-99.88°，99.88°］，所以本文在進(jìn)行CORDIC模塊設(shè)計(jì)時預(yù)先采用邏輯單元將輸入角度θ進(jìn)行旋轉(zhuǎn)，使其旋轉(zhuǎn)后得到的角度φ保持在區(qū)間［-π/4，π/4］之內(nèi)。在CORDIC模塊輸出端可以利用三角函數(shù)特性，通過邏輯單元將φ對應(yīng)的三角函數(shù)輸出結(jié)果轉(zhuǎn)換為原始相位θ所對應(yīng)的正余弦值。圖2給出了本文所設(shè)計(jì)的CORDIC模塊結(jié)構(gòu)原理圖。

圖2 CORDIC模塊的結(jié)構(gòu)原理圖

為了使得本文所設(shè)計(jì)的CORDIC模塊能夠在系統(tǒng)時鐘100MHz下正常運(yùn)轉(zhuǎn)，因此有必要使得整個模塊的最大路徑延時低于10ns。經(jīng)計(jì)算，如果采用12次迭代過程，不打任何流水的整個路徑將會耗時33ns左右，如果每次迭代過程均打一次流水，則需要耗費(fèi)12個系統(tǒng)時鐘周期完成CORDIC運(yùn)算。為了降低模塊運(yùn)算時間，本文按照圖3所示在12級迭代中均勻打入了4級流水，使得最大路徑延時保持在8ns左右。這樣既滿足了系統(tǒng)速度需要，也提高了模塊的運(yùn)算效率。此外，加上模塊內(nèi)相位旋轉(zhuǎn)的1級流水，在具體運(yùn)行過程中，本文所設(shè)計(jì)的CORDIC電路只需要消耗5個系統(tǒng)時鐘周期就可以完成全部的運(yùn)算處理工作。

硬件實(shí)現(xiàn)部分，本文運(yùn)用Verilog HDL語言，采用自上而下的設(shè)計(jì)原則，對整個方案進(jìn)行了硬件描述。并利用ModelSim軟件進(jìn)行功能仿真。在設(shè)計(jì)CORDIC模塊時，為了縮短最大路徑延時進(jìn)而使得系統(tǒng)最大工作頻率高于100MHz，本文在CORDIC算法12次迭代路徑上打入了4級流水，加上對原始相位輸入進(jìn)行旋轉(zhuǎn)操作的1級流水，整個CORDIC模塊共采用5級流水結(jié)構(gòu)進(jìn)行設(shè)計(jì)。圖4所示為CORDIC模塊輸出的正余弦信號圖。可以看出，本文所設(shè)計(jì)的CORDIC模塊根據(jù)瞬時相位實(shí)時地輸出對應(yīng)的正余弦值。從波形可以看出，CORDIC模塊輸出正余弦曲線十分平滑，達(dá)到了預(yù)期的設(shè)計(jì)功能。

功能仿真驗(yàn)證后，本文運(yùn)用Synplify Pro軟件在Altera Stratix II系列EP2S130F1020C5型FPGA上對設(shè)計(jì)方案進(jìn)行了綜合和布局布線。實(shí)現(xiàn)過程所消耗FPGA資源情況如表1所示。系統(tǒng)布線后最高時鐘可達(dá)145.2MHz。

圖3 本文所設(shè)計(jì)CORDIC電路結(jié)構(gòu)圖

表l 占用硬件資源統(tǒng)計(jì)

圖4 CORDIC模塊輸出正余弦信號

4 結(jié)束語

本文針對CORDIC算法在數(shù)字頻率合成方面的應(yīng)用進(jìn)行了研究。結(jié)合算法研究，考慮高速數(shù)字電路設(shè)計(jì)原則，運(yùn)用Verilog HDL語言對本文方案進(jìn)行了寄存器傳輸級描述，并完成功能仿真。設(shè)計(jì)方案最終在FPGA上實(shí)現(xiàn)。仿真與硬件實(shí)現(xiàn)結(jié)果證明了本文所提出的設(shè)計(jì)方案具備良好的性能與可行性?！?/p>

［1］ Duhamael P，Vetterli M．Fast Fourier transforms：a tutorial review and a state of the art［J］．Signal Processing，1990（19）：259－299．

［2］ Ercegovac MD，Lang T．Implementation of fast angle calculation and rotation using on-line CORDIC［J］．IEEE International Symposium on Circuits and Systems，1988，3：2703－2706．

［3］ Brennan PV，Walkington R，Borkjak A．Performance of PLL synthesiser based on DDS feedback［J］．IEEE Electronics Letters，1998（34）：2197－2199．

［4］ 張煒，楊虎．基于CORDIC算法的直接數(shù)字頻率合成器實(shí)現(xiàn)方法［J］．重慶郵電學(xué)院學(xué)報，2006，18（5）：597－600．

［5］ Hu YH．The quantization effects of the CORDIC algorithm［J］．IEEE Trans．on Signal Processing，1992，40（4）：834－844．

Research and implementation of CORDIC algorithm on DDFS

Ma Siqiang，Wang Shoubin，Shao Guofeng
（No.36 Research Institute of CETC，Jiaxing 314033，Zhejiang，China）

CORDIC algorithm is more accurate and more feasible on FPGA implementation than conventional look-up tables，which only needs a smallest LUT.Based on the study of CORDIC algorithm，the CORDIC circuit is designed.The whole design is synthesized under Altera Stratix II EP2S130F1020C5 FPGA. Highest clock frequency after routed can reach 145.2MHz.

CORDIC；FPGA；trigonometric

TN97；TN79

A

2015-05-26；2015-07-16修回。

馬思強(qiáng)（1987-），男，工程師，博士，主要從事電子系統(tǒng)總體設(shè)計(jì)、信號處理技術(shù)等方面的研究工作。