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

　　引言

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

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

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

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

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

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

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

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