低時延CORDIC 算法計算平方根電路設(shè)計研究

侯強(qiáng)，彭玉龍，王育新，付東兵

（1.中國地質(zhì)大學(xué)機(jī)械與電子信息學(xué)院，湖北武漢 430074；2.中國電子科技集團(tuán)公司第24研究所模擬集成電路國家重點實驗室，重慶 400060）

開平方運算是一種應(yīng)用范圍廣泛的數(shù)學(xué)運算，比如通信信號解調(diào)時計算信號包絡(luò)需要進(jìn)行開平方運算，正交調(diào)制信號提取相位信息時也需要開平方運算，它也是很多數(shù)字校正算法如功率放大器數(shù)字預(yù)失真參數(shù)提取算法中的關(guān)鍵運算［1］.而平方根運算的精度和速度是開平方電路的主要性能指標(biāo).坐標(biāo)旋轉(zhuǎn)數(shù)字計算機(jī)（Coordinate Rotation Digital Com?puter，CORDIC）算法［2-3］是提高平方根運算精度和速度的一種新穎方法，CORDIC算法在其計算過程中只涉及移位操作和加減操作，因此非常適合硬件特別是FPGA 實現(xiàn)［4］.該方法最初用于進(jìn)行三角函數(shù)求值和產(chǎn)生正余弦波形，經(jīng)過一定推廣后也可用于計算雙曲線函數(shù)［5］，采用CORDIC 算法在雙曲線旋轉(zhuǎn)下的向量模式，可以計算平方根.

文獻(xiàn)［6，7］對基本CORDIC 算法計算平方根進(jìn)行了詳細(xì)闡述，它是一種循環(huán)迭代的計算方法，通過迭代運算不斷逼近所要旋轉(zhuǎn)的角度.但由于迭代次數(shù)過多存在時延偏大的缺陷，同時每次迭代方向必須等待上一次迭代結(jié)束，由上次迭代剩余角度符號決定本次迭代旋轉(zhuǎn)方向，限制了算法的運算速度.文獻(xiàn)［8］雖然對模校正因子進(jìn)行了簡化，但最終精度稍有損失，另外還有其他一些改進(jìn)方法求平方根.

本文在前人對CORDIC 算法進(jìn)行優(yōu)化基礎(chǔ)上提出了一種改進(jìn)算法求取平方根，將查找表法、單向旋轉(zhuǎn)、合并迭代和基本CORDIC 算法相結(jié)合，只需進(jìn)行單向迭代運算，避免了每次旋轉(zhuǎn)方向的不確定，消去了縮放因子［9］，從而有效提高了算法的工作速度.同時把迭代運算劃分為兩個階段完成：第一階段迭代通過移位運算和減法運算直接實現(xiàn)，第二階段迭代通過簡化蝶形遞歸運算一步完成.這樣大大減少了迭代運算的次數(shù)，降低了延時，特別適合實時性要求高的應(yīng)用場合.本改進(jìn)算法在XILINX 公司xc6vlx75t-3ff484 型號FPGA 芯片進(jìn)行了驗證，結(jié)果表明：在保證與基本CORDIC 算法精度相同的情況下，能夠有效計算平方根，不但顯著減少了算法迭代次數(shù)，還有效提高了算法運算速度，本改進(jìn)算法應(yīng)用在計算平方根方面的綜合性能有了較明顯提升和改善.

1 基本CORDIC算法

CORDIC 算法最早是由J.Volder 提出的，它是一種只需通過移位-相加運算不斷迭代逼近目標(biāo)值的計算方法［10］.在XY坐標(biāo)平面上將向量（x0，y0）旋轉(zhuǎn)角度θ后得到向量（x1，y1），如圖1所示.

圖1 向量旋轉(zhuǎn)示意圖Fig.1 Vector rotation diagram

兩向量間坐標(biāo)變換關(guān)系如式（1）：

如果去除cosθ項，可得到向量的偽旋轉(zhuǎn)方程如式（2）：

CORDIC 算法核心在于把旋轉(zhuǎn)θ角分解為N個遞減的小旋轉(zhuǎn)角θi進(jìn)行N步迭代旋轉(zhuǎn)，即限定旋轉(zhuǎn)角度θ，使tanθ=di·2-i，其中di=1或-1，表示旋轉(zhuǎn)的方向，從而可以通過簡單移位來完成由tanθ引入的乘法運算.任意角度的旋轉(zhuǎn)可通過一系列θ=tan-1（2-i）的角度旋轉(zhuǎn)迭代完成，在這里引入了角度累加器：zi+1=zi–di·θi用來在每次迭代過程中追蹤累加后剩余的旋轉(zhuǎn)角度，該剩余的旋轉(zhuǎn)角度確定旋轉(zhuǎn)的方向，若zi＞0，di=1；否則di=-1.那么第i+1 次角度的向量偽旋轉(zhuǎn)方程可表示為式（3）：

正如前面所述，如果消去了cosθi項，迭代方程（2）就只有移位和加減操作.當(dāng)cosθi項經(jīng)過N步旋轉(zhuǎn)后可得到模校正因子Kn，當(dāng)N確定時Kn就是一個常量，而常數(shù)項Kn可以在系統(tǒng)的其他地方進(jìn)行補(bǔ)償，Kn表達(dá)式如式（4）：

最終旋轉(zhuǎn)表達(dá)式如式（5）：

CORDIC 算法也可以用于投影計算，當(dāng)將向量（x，y）投影到x軸時，此時旋轉(zhuǎn)方向由yi確定.若yi＜0，di=1；否則di=-1.迭代的最終值為式（6）：

擴(kuò)展迭代方程式，CORDIC算法可以用于計算雙曲線方程，擴(kuò)展后的向量偽旋轉(zhuǎn)方程為式（7）：

對于平方根運算采用的是雙曲線方程，而且迭代模式為投影模式，迭代的最終值為式（8）：

如果要求值a的平方根，只需要將x、y分別賦值為a+1和a-1，帶入式（8）可得xn=，再將其除以2即為.

2 改進(jìn)的低時延CORDIC算法

2.1 確定旋轉(zhuǎn)方向

低時延CORDIC 算法核心在于確定了每次迭代的旋轉(zhuǎn)方向，這樣就使合并迭代成為可能.與基本CORDIC 算法令每次旋轉(zhuǎn)角度為θ=tanh-1（2-i）不同，這里令每次旋轉(zhuǎn)角度為θ=2-i.任意角度的旋轉(zhuǎn)可通過一系列θ=2-i的角度旋轉(zhuǎn)迭代完成，總旋轉(zhuǎn)角度為，將總旋轉(zhuǎn)角度使用二進(jìn)制表示，若二進(jìn)制數(shù)為1，則進(jìn)行tanh（2-i）的迭代旋轉(zhuǎn)；否則不進(jìn)行第i次迭代旋轉(zhuǎn).這里令x0和y0皆為正數(shù)，那么第i+1次角度的向量偽旋轉(zhuǎn)方程可表示為式（9）：

2.2 建立輸入值查找表

根據(jù)輸入的x0和y0建立反雙曲正切查找表［11］.查找表中存儲對應(yīng)的以15 位二進(jìn)制數(shù)表示的值，用來作為旋轉(zhuǎn)迭代的方向.

進(jìn)行角度編碼確定旋轉(zhuǎn)方向并不占用硬件資源，只是使每次迭代方向由輸入角二進(jìn)制表示時的各位的位值直接確定，避免了CORDIC 基本算法中迭代方向需由剩余角度計算結(jié)果決定的不足［12］，從而提高了CORDIC算法的運行速度.

基于此，可以將角度預(yù)處理后得到的二進(jìn)制補(bǔ)碼表示的15 位角度值分兩個階段處理.第一階段，使用查找表得到的旋轉(zhuǎn)方向進(jìn)行單向旋轉(zhuǎn)，通過移位運算和減法運算直接得到結(jié)果.此時未旋轉(zhuǎn)的角度只剩7 至15 位的小數(shù)部分，在第二階段直接進(jìn)行合并迭代.

2.3 單向旋轉(zhuǎn)

由于FPGA 中不能直接求取tanh（2-i），所以這里通過移位運算求取.首先在MATLAB 中求得tanh(2-i)具體值后，如表1 所示，將其轉(zhuǎn)換為二進(jìn)制.此時不需要再預(yù)先存儲θi的值，同時省去剩余角度存儲，直接根據(jù)輸入二進(jìn)制的前6 位進(jìn)行處理.可以將原來的雙向旋轉(zhuǎn)表達(dá)式化為單向旋轉(zhuǎn)，對應(yīng)輸入二進(jìn)制數(shù)的相應(yīng)位若為1 時，就取di=-1 進(jìn)行順時針旋轉(zhuǎn)，若為0，則不旋轉(zhuǎn)直接傳遞x、y的值［13］，即保證了精度要求又使得最終的剩余旋轉(zhuǎn)角為0.這樣先根據(jù)輸入角度前（N-1）/2位進(jìn)行直接旋轉(zhuǎn)，然后進(jìn)行一步合并迭代運算便可求得平方根.

表1 旋轉(zhuǎn)角度對照表Tab.1 Rotation angle comparison table

2.4 合并迭代

根據(jù)基本CORDIC算法有迭代公式（10）：

進(jìn)行兩步迭代有式（11）：

可見，當(dāng)i≥（N-1）/2 時，基本算法中的蝶形迭代結(jié)構(gòu)便可完全由一個移位-連加結(jié)構(gòu)替代.低時延算法在確定了迭代的旋轉(zhuǎn)方向后，對于輸出小數(shù)位寬為N的系統(tǒng)，根據(jù)泰勒展開式tanh（2-i）=2-i-1/3·2-3i+2/15·2-5i-…，在i≥N/3 時可作θi=tanh（2-i）≈2-i的近似前提下，可直接由圖2 所示的移位-連加的合并迭代結(jié)構(gòu)替代基本算法中的蝶形迭代結(jié)構(gòu)，而當(dāng)i＜（N-1）/2 時可直接通過移位運算得到迭代結(jié)果.通過觀察表1 中的弧度值，對于15 位二進(jìn)制小數(shù)表示的弧度，當(dāng)i≥N/3即i≥5時，θi=tanh（2-i）≈2-i，印證上述推導(dǎo)結(jié)論［14］.

圖2 合并迭代結(jié)構(gòu)圖Fig.2 Merged iteration structure diagram

2.5 免除補(bǔ)償因子

在CORDIC 算法中coshθi可由泰勒級數(shù)展開如式（12）：

則當(dāng)i≥（N-1）/2 時，在保證系統(tǒng)精度的情況下coshθi≈1.對于15 位小數(shù)系統(tǒng)，當(dāng)i≥7 時，迭代旋轉(zhuǎn)可直接消去coshθi項.通過表1 觀察coshθi，計算知：當(dāng)i≥7時，≈1.000 040≈1，所以7到15級迭代在不進(jìn)行模校正時（即免除縮放因子），在10-5以上的數(shù)量級能夠保證系統(tǒng)精度［15］.

2.6 算法的FPGA實現(xiàn)

根據(jù)以上原理描述，用Verilog HDL 語言對其進(jìn)行了實現(xiàn)，整個程序分4 個模塊，分別為查找表、CORDIC 算法單向旋轉(zhuǎn)、CORDIC 算法合并迭代、還原輸出.設(shè)計實例程序總體框圖如圖3.

圖3 設(shè)計實例總體框圖Fig.3 Overall block diagram of design example

在設(shè)計實例中，首先使用y0進(jìn)行查表，確定總旋轉(zhuǎn)角度即迭代旋轉(zhuǎn)次數(shù)，當(dāng)i＜（N-1）/2（即i＜7）時，進(jìn)行單向旋轉(zhuǎn).當(dāng)i≥（N-1）/2（即i≥7）時，進(jìn)行合并迭代.

3 仿真結(jié)果及其分析

在XILINX 公司的xc6vlx75t-3ff484 型號FPGA上對以上電路進(jìn)行了實現(xiàn)，在ISE14.2 軟件環(huán)境下利用其自帶工具XST 進(jìn)行綜合，并且與基本CORDIC實現(xiàn)方法進(jìn)行了比較.在用XST 工具綜合后得到電路最高工作頻率和最大時延等數(shù)據(jù)，綜合結(jié)果對比如表2.

表2 綜合結(jié)果對比Tab.2 Comparison of comprehensive results

從表2中可以看出：改進(jìn)的CORDIC 算法比基本CORDIC 算法的最高運行頻率提高了5.49%，其原因是改進(jìn)算法只需進(jìn)行單向迭代運算，避免了每次旋轉(zhuǎn)方向的不確定，從而有效提高了算法的工作速度.通過對比兩種算法綜合后寄存器和LUT 單元消耗量，可以看出改進(jìn)算法相比基礎(chǔ)算法寄存器有所減少，LUT 單元使用量相對較多，但平均資源消耗兩者接近.同時改進(jìn)CORDIC 算法輸出時延比基本CORDIC 算法少了8 個時鐘周期，也就是節(jié)省了50%的時鐘周期，其綜合性能有了較大提升.

使用Xpower 進(jìn)行功耗分析，在40 MHz、70 MHz和100 MHz 頻率值上進(jìn)行了測試，功率數(shù)據(jù)對比如表3.通過表3 對比得到改進(jìn)CORDIC 算法比基本CORDIC算法的功耗有所減少，并且隨著運行頻率的增加，功耗下降比率增大.

表3 功耗分析表Tab.3 Power consumption analysis table

將改進(jìn)CORDIC 算法和基本CORDIC 算法用MATLAB 語言仿真，并與理論值對比進(jìn)行誤差分析.在此處為了方便觀察比較，遍歷求取了［3，5］部分的平方根，得到求取平方根誤差的絕對值分析結(jié)果如圖4.

從圖4 中看出：基本算法誤差絕對值的最大值為8.198×10-4，改進(jìn)算法誤差絕對值的最大值為2.558×10-4，改進(jìn)算法比基本算法在精度上提高了一些.分別對誤差絕對值進(jìn)行統(tǒng)計平均計算，基本算法平均誤差為2.435×10-4，改進(jìn)算法平均誤差為8.413×10-5.可見在平均誤差上改進(jìn)算法比基本算法也有所改善，主要原因在于改進(jìn)算法中di可取0值，可以避免不必要的迭代，而基本算法對輸入角度為特殊角度如θ剛好為tanh-12-i時仍進(jìn)行迭代旋轉(zhuǎn)，從而增加了算法平均誤差.

圖4 輸出誤差對比Fig.4 Error comparison of output

4 結(jié)論

本文針對基本CORDIC 算法計算平方根中迭代次數(shù)較多，時延較長等局限提出了相應(yīng)改進(jìn)方法.在保證與基本CORDIC 算法精度數(shù)量級相同的情況下，減少了迭代次數(shù)，避免了每次旋轉(zhuǎn)方向的不確定性，消去了縮放因子，有效降低了時延，并且最高運行頻率也有所提升.用MATLAB 對該改進(jìn)算法和基本算法計算平方根建模并進(jìn)行了性能的比較和分析，同時在XILINX 公司的xc6vlx75t-3ff484 型號的FPGA 上對該改進(jìn)算法和基本算法計算平方根進(jìn)行具體的設(shè)計和實現(xiàn).仿真結(jié)果表明：改進(jìn)算法輸出時延減少了50%，最高運行頻率提高了5.49%，并且輸出精度稍優(yōu)于基本算法.和基本CORDIC 算法相比，改進(jìn)CORDIC 算法在計算平方根應(yīng)用場景下的綜合性能有了明顯提升和改善.