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

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

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

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

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

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

1 基本CORDIC算法

CORDIC 算法最早是由J.Volder 提出的，它是一種只需通過(guò)移位-相加運(yùn)算不斷迭代逼近目標(biāo)值的計(jì)算方法［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θ項(xiàng)，可得到向量的偽旋轉(zhuǎn)方程如式（2）：

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

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

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

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

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

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

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

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

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

低時(shí)延CORDIC 算法核心在于確定了每次迭代的旋轉(zhuǎn)方向，這樣就使合并迭代成為可能.與基本CORDIC 算法令每次旋轉(zhuǎn)角度為θ=tanh-1（2-i）不同，這里令每次旋轉(zhuǎn)角度為θ=2-i.任意角度的旋轉(zhuǎn)可通過(guò)一系列θ=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］.查找表中存儲(chǔ)對(duì)應(yīng)的以15 位二進(jìn)制數(shù)表示的值，用來(lái)作為旋轉(zhuǎn)迭代的方向.

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

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

2.3 單向旋轉(zhuǎn)

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

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

2.4 合并迭代

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 輸出誤差對(duì)比Fig.4 Error comparison of output

4 結(jié)論

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