引言
随着电子技术的不断发展，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)。
VR算法适于计算三角函数，在进行开平方运算时，可利用三角函数倍角之间的关系，将开平方运算转化为三角函数运算。对于t∈[-1，1]，初始向量M0(x0，y0)在[0，p]内逆时针旋转，每次旋转角度Dq，经过i次旋转后，总能使得xi=cos(i×Dq)≈t，Dq越小，近似程度越高。
先考察在[0，1]之间的任意实数。假设待开方数为s，且s∈[0，1]。有：
参数讨论
为了将该算法在FPGA上实现，需要选择合适的参数以降低实现的复杂度。在FPGA上实现加减法比较简单，而要实现乘法会比较复杂，在公式(3)中就涉及到乘法运算，要是能通过移位实现乘法将大大提高运算速度。因此Dq要尽量小，以获得更高的近似度，而且这样公式(3)中的cos(Dq)≈1，由此可简化计算;另外yi-1tan(Dq)，xi-1tan(Dq)要能通过数据移位实现。因此选择合适的Dq，使得，这样公式(3)中的迭代运算就可用右移k位实现，公式(3)可以简化为：
但如果Dq太小，会使迭代次数增多，因此选取合适的Dq是必要的。
任意数的开平方算法
直接利用VR算法只能计算[0，1]内的平方根值，有一定的局限性。因此，设待开方数T为任意正数，当T>1时，可通过对其预处理后映射到[0，1]区间内再进行开平方运算。
步骤如下：
开平方算法的FPGA实现
该开平方算法完全由移位和相加完成，很容易在硬件上实现，而且效率较高。由于FPGA具有并行处理能力，实现开方运算，速度可以比数字信号处理芯片快，以满足某些高速度处理要求。笔者采用的FPGA芯片是Altera公司的Stratix II系列EP2S60开发板。
实现方法
(1)预处理单元
要利用VR算法实现开平方运算，必须对输入进行预处理，设输入为单精度浮点数据格式，在预处理单元中将输入转化成算法可以处理的格式。
，有，所以迭代运算时寄存器中存放的上一次旋转所得的坐标值xi，yi每次右移5位。VR算法的FPGA实现架构如图2所示。
(3)后处理单元
由VR算法得到的结果需要经后处理单元处理成单精度浮点数据格式后输出。该单元需要预处理单元传递相关参数。
实验结果
在Quartus Ⅱ6.0环境下使用VHDL语言完成了上述算法，并在Stratix系列EP2S60开发板上实现。时钟频率为100MHz，综合和布局布线后，需要不到1%的ALUT和56个寄存器，因此实现该算法只需要占用很少的资源。仿真波形如图3所示。
波形图中的被开方数范围在[0，1]之间，由于以16位二进制数表示，需要对其进行归一化。如图中输入数值65000，归一化后为0.9918，实验中输出开平方值65345，归一化后为0.9971，通过计算，0.9918的理论开平方值约为0.9959，实验值和理论值之间的误差约为0.1195%。
由于迭代计算中没有复杂的乘法运算，每次迭代都只需要一次加法运算和一次移位操作。因此本文提出的算法只需要一个时钟周期就可以计算出结果，在理论上没有时延。图3所示的仿真图中有时延是因为为了仿真时间考虑，将循环过程以牺牲时间来实现的，因此该算法具有处理速度快的特点。
试验分析
在输入数据为16位宽，
的条件下进行仿真，得到实验数据。
图4是实验值与理论值的比较，由此可见，笔者提出的算法可以很好地逼近理论值，计算误差非常小。
在相同器件和相同精度的条件下，对不同的开平方算法的性能进行比较。在输入均为16位的被开方数时，对本算法、参考文献[8]采用的牛顿迭代算法和文献[9]采用的不恢复余数的开平方算法进行比较，结果见表1。
在相同精度的条件下，本文算法占用资源比采用牛顿迭代算法和不恢复余数的开平方算法分别少了9%和6%，完成一次平方根运算需要的周期明显减少，只需要1个时钟周期就可以输出运算结果，以后每个时钟输出1个运算结果。而牛顿迭代算法由于需要反馈调整，需要31个时钟周期才可以完成1次开平方运算;不恢复余数的开平方算法则需要9个时钟周期才能输出第一个结果。
在硬件速度允许的情况下，该算法可以进一步提高以获得更好的性能，这取决于迭代计算中每次旋转角度大小的选择。
结语
本文提出了一种基于矢量旋转求三角函数进而求得任意数平方根的算法，并在FPGA上加以实现。该算法没有时延，且迭代次数少;在相同的计算误差下，使用的算术逻辑单元较少，适于在FPGA上实现，满足了数据更快处理速度和芯片更少面积的要求。
参考文献：
[1] Hennessy J, Patterson D. Computer Architecture, A Quantitative Approach[M], Second Edition, Morgan Kaufmann Publishers, Inc., 1996
[2] Kabuo H, Taniguchi T, Miyoshi A. et al. Accurate Rounding Scheme for the Newton-Raphson Method Using Redundant Binary Representation[J], IEEE Transaction on Computers, Vol. 43, No. 1, 1994. pp43-51
[3] Markstein P, Computation of Elementary Functions on the IBM RISC RS6000 Processor[J]. IBM Jour. Of Res. and Dev., January, 1990. pp111-119
[4] Ercegovac M, Lang T, Radix-4 Square Root Without Initial PLA[J], IEEE Transaction on Computers, Vol. 39, No. 8, 1990. pp1016-1024
[5] Lang T, Montuschi P, Very-high Radix Combined Division and Square Root with Prescaling and Selection by Rounding[J], Proc. of 12th IEEE Symposium on Computer Arithmetic, IEEE Computer Society Press, 1995. pp124-131
[6] Bannur J, Varma A, The VLSI Implementation of A Square Root Algorithm[J], Proc. of IEEE Symposium on Computer Arithmetic, IEEE Computer Society Press, 1985. pp159-165
[7] Johnson K C, Efficient Square Root Implementation on the 68000[J], ACM Transaction on Mathematical Software, Vol. 13, No. 2, 1987. pp138-151
[8] 王艳梅,王同杰,郑成文.用VHDL实现的开方运算[J].沈阳工业学院学报,2004, 23(1): 3
[9] 林志谋，卢贵主.一种适合FPGA实现的开平方算法[J].厦门大学学报,2006，45(2):119-201
