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

摘要：開平方運(yùn)算廣泛應(yīng)用于數(shù)值分析、調(diào)制解調(diào)、圖像處理等領(lǐng)域，而應(yīng)用坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算（Coordinate Rotation Digital Computer，CORDIC）進(jìn)行平方根運(yùn)算是一種新應(yīng)用.基本CORDIC算法精度必須用迭代次數(shù)作保證，而較多的迭代次數(shù)會導(dǎo)致時延過大等問題，通過運(yùn)用建立查找表、單向旋轉(zhuǎn)、合并迭代和免除補(bǔ)償因子等手段，提出一種能夠免去大部分迭代運(yùn)算的改進(jìn)CORDIC算法用于平方根計(jì)算.相較于基本算法計(jì)算平方根，該改進(jìn)算法使用了一半的時鐘周期便能得到輸出結(jié)果，大大減少了輸出時延，而且可以達(dá)到較高的計(jì)算精度，更加適合實(shí)時性要求高的應(yīng)用場合.

關(guān)鍵詞：坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算;平方根計(jì)算;單向旋轉(zhuǎn);合并迭代;數(shù)字計(jì)算機(jī)

中圖分類號：TN492

文獻(xiàn)標(biāo)志碼：A

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

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

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

1基本CORDIC算法

CORDIC算法最早是由J.Volder提出的，它是一種只需通過移位-相加運(yùn)算不斷迭代逼近目標(biāo)值的計(jì)算方法[10].在XY坐標(biāo)平面上將向量（x0，y0）旋轉(zhuǎn)

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

如果去除cosθ項(xiàng)，可得到向量的偽旋轉(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)的方向，ìx′1=（x0-y0·tanθ）?í?y1′=（y0+x0·tanθ）從而可以通過簡單移位來完成由tanθ引入的乘法運(yùn)-1-i算.任意角度的旋轉(zhuǎn)可通過一系列θ=tan（2）的角度旋轉(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項(xiàng)，迭代方程（2）就只有移位和加減操作.當(dāng)cosθi項(xiàng)經(jīng)過N步旋轉(zhuǎn)后可得到模校正因子Kn，當(dāng)N確定時Kn就是一個

常量，而常數(shù)項(xiàng)Kn可以在系統(tǒng)的其他地方進(jìn)行補(bǔ)償，Kn表達(dá)式∏如式（4）：∏

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

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

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

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

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

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

低時延CORDIC算法核心在于確定了每次迭代的旋轉(zhuǎn)方向，這樣就使合并迭代成為可能.與基本CORDIC算法令每次旋轉(zhuǎn)角度為θ=tanh-（12-）i不同，這里令每次旋轉(zhuǎn)角度為θ=2-i.任意角度的旋轉(zhuǎn)可通過一系列θ=2-i的角度旋轉(zhuǎn)迭代完成，總旋轉(zhuǎn)角度為tanh?y0÷，將總旋轉(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)迭代的方向.

在FPGA中不能直接求取總旋轉(zhuǎn)角度

所以通過MATLAB首先建立關(guān)于

的查找表，由于y0和x0之間的關(guān)系是x0=y0+2，所以可以通過輸入的y0值確定總旋轉(zhuǎn)角度在該查找表中的相對位置，從而在FPGA中輸出

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

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

2.3單向旋轉(zhuǎn)

由于FPGA中不能直接求取tanh（2-）i，所以這里通過移位運(yùn)算求取.首先在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)行一步合并迭代運(yùn)算便可求得平方根.

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時可直接通過移位運(yùn)算得到迭代結(jié)果.通過觀察表1中的弧度值，對于15位二進(jìn)制小數(shù)表示的弧度，當(dāng)i≥N/3即i≥5時，θi=tanh（2-）i≈2-i，印證上述推導(dǎo)結(jié)論[14].

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項(xiàng).通過表1觀察coshθi，計(jì)算知：

在不進(jìn)行模校正時（即免除縮放因子），在10以上的數(shù)量級能夠保證系統(tǒng)精度[15]

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

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

在設(shè)計(jì)實(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)行了實(shí)現(xiàn)，在ISE14.2軟件環(huán)境下利用其自帶工具XST進(jìn)行綜合，并且與基本CORDIC實(shí)現(xiàn)方法進(jìn)行了比較.在用XST工具綜合后得到電路最高工作頻率和最大時延等數(shù)據(jù)，綜合結(jié)果對比如表2.

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

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

將改進(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)計(jì)平均計(jì)算，基本算法平均誤差為2.435×10-4，改進(jìn)算法平均誤差為8.413×10-5.可見在平均誤差上改進(jìn)算法比基本算法也有所改善，主要原因在于改進(jìn)算法中di可取0值，可以避免不必要的迭代，而基本算法對輸入角度為特殊角度如θ剛好為tanh-12-i時仍進(jìn)行迭代旋轉(zhuǎn)，從而增加了算法平均誤差.

4結(jié)論

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

參考文獻(xiàn)

[1]FANG L L，XIE Y Z，LI B Y，et al.Generation scheme of chirp scaling phase functions based on floating-point CORDIC processor [J].The Journal of Engineering，2019，2019（21）：7436-7439.

[2]TIWARI V，MISHRA A.Neural network-based hardware classi?fier using CORDIC algorithm[J]. Modern Physics Letters B， 2 0 2 0 ，3 4（ 1 5 ）：2 0 5 0 1 6 1 .

[3]姚亞峰，徐洋洋，侯強(qiáng)，等.基于小容量查找表的CORDIC算法設(shè)計(jì)[J].湖南大學(xué)學(xué)報（自然科學(xué)版），2019，46（4）：80-84.

[4]MOPURI S，ACHARYYA A.Configurable rotation matrix of hy?perbolic CORDIC for any logarithm and its inverse computation [J]. Circuits，Systems，and Signal Processing，2020，39（5）： 2551-2573.

[5]DU X H. Implementation of DDS based on CORDIC Algorithm[J]. Journal of Research in Science and Engineering，2020，2（8）： 117-120.

[6]PILATO L，F(xiàn)ANUCCI L，SAPONARA S. Real-time and high- accuracy arctangent computation using CORDIC and fast magni?tude estimation[J].Electronics，2017，6（1）：22.

[7] FANG L L，LI B Y，XIE Y Z，et al. A unified re-configurable CORDIC processor for floating-point arithmetic[J].International Journal of Electronics，2020，107（9）：1436-1450.

[8] CHEN J Y，LEI Y W，PENG Y X，et al.Configurable floating- point FFT accelerator on FPGA based multiple-rotation CORDIC [J].Chinese Journal of Electronics，2016，25（6）：1063-1070.

[9] KAVITHA M S，RANGARAJAN P.An efficient FPGA architec?ture for reconfigurable FFT processor incorporating an integration of an improved CORDIC and radix-2r algorithm[J].Circuits，Sys?tems，and Signal Processing，2020，39（11）：5801-5829.

[10] CHANGELA A，ZAVERI M，VERMA D. FPGA implementation of high-performance，resource-efficient Radix-16 CORDIC rota?tor based FFT algorithm[J].Integration，2020，73：89-100. [11] NGUYEN H T，NGUYEN X T，PHAM C K.A low-latency paral?lel pipeline CORDIC[J]. IEICE Transactions on Electronics， 2 0 1 7 ，E 1 0 0 . C（ 4 ）：3 9 1 - 3 9 8 .

[12] TORRES V，VALLS J，CANET M J. Optimised CORDIC-based atan2 computation for FPGA implementations[J]. Electronics L e t t e r s ，2 0 1 7 ，5 3（ 1 9 ）：1 2 9 6 - 1 2 9 8 .

[13] SALEHI F，F(xiàn)ARSHIDI E，KAABI H. Novel design for a low- latency CORDIC algorithm for sine-cosine computation and its Implementation on FPGA[J]. Microprocessors and Microsys?t e m s ，2 0 2 0 ，7 7 ：1 0 3 1 9 7 .

[14] MEHDAOUI Y，ALAMI R.DSP implementation of the Discrete Fourier Transform using the CORDIC algorithm on fixed poin[t J]. Advances in Modelling and Analysis B，2018，61（3）：123-126.

[15] MOUNIKA K，KUMAR P P，RANI K S，et al.Implementation of rotation and vectoring-mode reconfigurable CORDIC[J].Interna?tional Journal of Trend in Scientific Research and Development， 2 0 1 8 ，2（ 4 ）：1 5 9 4 - 1 6 0 2 .