利用矢量旋轉(zhuǎn)求解平方根的算法及其FPGA實現(xiàn)*

　　引言

　　隨著電子技術(shù)的不斷發(fā)展，EDA技術(shù)在數(shù)字信號處理領(lǐng)域得到了越來越多的應(yīng)用。在FPGA中，應(yīng)用VHDL語言可以進行加法、減法、乘法等運算，但卻不能直接進行開平方運算。傳統(tǒng)的開平方算法主要可以分為三大類：牛頓迭代法[1~3]，SRT-冗余算法[4~5]，非冗余算法[6~7]。

　　當(dāng)直接利用牛頓迭代法進行開平方運算時，涉及到復(fù)雜的除法運算。為了避免除法運算，必須首先計算出平方根的倒數(shù)，再與被開方數(shù)相乘得到平方根。利用牛頓迭代法求根的迭代次數(shù)只和初始值與被開方數(shù)之間的誤差有關(guān)，而與被開方數(shù)無關(guān)。另外，運算中還涉及到查表運算，要使迭代次數(shù)降低，必須相應(yīng)地增加查找表的大小。而且在每次迭代運算中都涉及到乘法、加/減法運算，為了提高乘法運算速度，經(jīng)常通過采用高速并行乘法器和進位保留加法器來輔助運算，需要較高資源。

　　經(jīng)典SRT-冗余算法也是基于迭代實現(xiàn)的，在每次迭代中都涉及到加法、乘法、條件判斷轉(zhuǎn)移、數(shù)值轉(zhuǎn)換等運算，為了減少電路的復(fù)雜度，所有的迭代運算都共用硬件資源，因此，該算法的效率較低。

　　非冗余算法可分為恢復(fù)余數(shù)的算法和不恢復(fù)余數(shù)的算法。與SRT算法相似，這兩種算法都需要復(fù)雜的迭代運算?；謴?fù)余數(shù)的算法由于存在反饋補償機制，存在很大延時，效率低;不恢復(fù)余數(shù)的算法[9]還要采用更多加法運算。

　　本文提出了一種基于矢量旋轉(zhuǎn)求三角函數(shù)進而求得任意數(shù)平方根的算法，并用VHDL語言在Altera EP2S60開發(fā)板上加以實現(xiàn)。該算法相比其他傳統(tǒng)開平方算法具有處理速度更快、計算誤差更小、占用資源更少的顯著優(yōu)勢。

　　基于矢量旋轉(zhuǎn)(VR)算法實現(xiàn)開平方的算法

　　矢量旋轉(zhuǎn)算法簡介

　　如圖1所示，初始向量M0(x0，y0)與x軸重合，經(jīng)逆時針旋轉(zhuǎn)Dq角度之后得到向量M1(x1，y1)，依此類推，逆時針旋轉(zhuǎn)i次之后得到向量Mi(xi，yi)。