孩子都能学会的FPGA：第二十课——用FPGA实现定点数的开方运算

（原创声明：该文是作者的原创，面向对象是FPGA入门者，后续会有进阶的高级教程。宗旨是让每个想做FPGA的人轻松入门，作者不光让大家知其然，还要让大家知其所以然！每个工程作者都搭建了全自动化的仿真环境，只需要双击top_tb.bat文件就可以完成整个的仿真（前提是安装了modelsim），降低了初学者的门槛。如需整个工程请留言（WX：Blue23Light），不收任何费用，但是仅供参考，不建议大家获得资料后从事一些商业活动！）

前面的定点数的乘法和除法运行，至少我们还是能列竖式进行计算，所以用FPGA实现还算简单。但是对于本节要讲的开方运算，我们好像在数学书本上没有学习过如何进行计算。我们对于一些比较小的数的开方，我们可以根据乘法口诀大体推算出来，比如64=8*8，那64的平方根就是8，但是对于比较大的数，比如12345678这样的数，我们很难张口就算出了。

定点数的平方根，还是由一些算法能够实现的，我们以《基于FPGA的数字信号处理》[高亚军编著] 这本书上Restoring 算法为例进行设计。下面是书上手工计算一个定点数平方根的过程。

第一步：将被开方数由低位至高位每两位分为一组；

第二步：由高两位06开始，对应的平方根为2，即Q(2)=2。将Q(2)左移1位并与6相减获得部分余数 r2=2；

第三步：r2与D(3)D(2)合并构成 214，讲Q(2)左移1位为4，根据[4Q(1)]xQ(1)≤214，确定Q(1)=4，并获得部分余数r1=38;

第四步：r1与D(1)D(0)合并构成 3858 , [Q(2)Q(1)]左移 1 位为 48 , 根据[48Q(0)]xQ(0)≤3858确定Q(0)=7, 并获得部分余数r0，此即为最终余数R。

可见，该算法是一种迭代的过程，每次迭代获得平方根的某一位。这其实就是恢复余数(Restoring) 算法。

上面是书上的原话，大家可以理解一下，这种方法用在10进制数的开方计算上还是挺麻烦的，主要是中间有乘法运算，比如4Q(1)和48Q(0)。书上由10进制推导出2进制数据的开方运行，使用了Restoring算法和Non-Restoring 算法来求数据的平方根，中间还有一些公式的推导，看的比较眼花缭乱，有兴趣的读者可以好好的看一下。下面是Restoring算法的计算过程图。

书中还给出了被开方数为8bit 的开方运算电路结构，如下所示。

其实二进制的开方运算非常简单，根本不需要涉及乘法除法和加法，只需要减法就可以完成。将被开方数从低位到高位2位一组进行处理。二进制的2位只能是11，10，01，和00，其中11，10，01的平方根是01，00的平方根是00，从高位到低位进行判断，假如当前是第k步，用前面所有步计算的平方根结果Q[n:k+1]连接01和当前的余数进行比较，来确定当前这一步的Q(k)是0还是1，如果Q(k)是1，减去当前结果的平方值；如果Q(k)是0，保持余数不变即可。

下面我们通过FPGA来实现8位无符号整数的开方运算。由于2位数进行1次计算，所以8位无符号整数的开发运算其实只需要4次计算就可以得出结果，如下定义的开方运算次数SQUARE_CNT=4。