利用矢量旋转求解平方根的算法及其FPGA实现*

—— Design and Implementation of FPGA-Based Root Square Algorithm with Vector Rotation

作者：钟花孙松林景晓军北京邮电大学信息与通信工程学院时间：2009-08-07来源：电子产品世界收藏

　　引言

本文引用地址：http://www.eepw.com.cn/article/96987.htm

　　随着电子技术的不断发展，EDA技术在数字信号处理领域得到了越来越多的应用。在FPGA中，应用VHDL语言可以进行加法、减法、乘法等运算，但却不能直接进行开平方运算。传统的开平方算法主要可以分为三大类：牛顿迭代法[1~3]，SRT-冗余算法[4~5]，非冗余算法[6~7]。

　　当直接利用牛顿迭代法进行开平方运算时，涉及到复杂的除法运算。为了避免除法运算，必须首先计算出平方根的倒数，再与被开方数相乘得到平方根。利用牛顿迭代法求根的迭代次数只和初始值与被开方数之间的误差有关，而与被开方数无关。另外，运算中还涉及到查表运算，要使迭代次数降低，必须相应地增加查找表的大小。而且在每次迭代运算中都涉及到乘法、加/减法运算，为了提高乘法运算速度，经常通过采用高速并行乘法器和进位保留加法器来辅助运算，需要较高资源。

　　经典SRT-冗余算法也是基于迭代实现的，在每次迭代中都涉及到加法、乘法、条件判断转移、数值转换等运算，为了减少电路的复杂度，所有的迭代运算都共用硬件资源，因此，该算法的效率较低。

　　非冗余算法可分为恢复余数的算法和不恢复余数的算法。与SRT算法相似，这两种算法都需要复杂的迭代运算。恢复余数的算法由于存在反馈补偿机制，存在很大延时，效率低;不恢复余数的算法[9]还要采用更多加法运算。

　　本文提出了一种基于矢量旋转求三角函数进而求得任意数平方根的算法，并用VHDL语言在Altera EP2S60开发板上加以实现。该算法相比其他传统开平方算法具有处理速度更快、计算误差更小、占用资源更少的显著优势。

　　基于矢量旋转(VR)算法实现开平方的算法

　　矢量旋转算法简介

　　如图1所示，初始向量M0(x0，y0)与x轴重合，经逆时针旋转Dq角度之后得到向量M1(x1，y1)，依此类推，逆时针旋转i次之后得到向量Mi(xi，yi)。