开方运算的硬件实现方法以及开方运算器

摘要

本发明所要提供一种新的，不用占用大量存储空间的，能够在硬件上实现开方运算的方法以及实现该方法的开方运算器。采用逐位逼近法，先开辟一个全0的寄存器作为输入数据的n次方根值的中间值寄存器，再确定一个寄存器变量i的初始值，并置中间值寄存器的第i位为1，确保初始化后的中间值寄存器的值的n次方大于原始输入数据。之后逐渐设置中间值寄存器的低位，并将设置后的值进行n次方运算，将n次方运算结果与输入数据进行比较，从而调整中间值寄存器的设置，直到i减为0或者n次方运算结果等于输入数据，开方运算结束，将此时中间值寄存器中的值作为开方运算结果。

说明书

技术领域

本发明属于硬件平台的运算和数据处理技术。

背景技术

加减乘除以及开方运算是科学计算和工程应用中最基本的运算，他们广泛应用于多次方 程求解、数学建模、误差计算、数据加密、数值分析、概率统计、图像处理以及信号处 理等许多领域。关于整数及浮点数的运算已经在VLSI(超大规模集成电路)标准中有规定。一 些计算已经在FPGA(现场可编程门阵列)中实现了。

开方运算虽然不如加减乘除使用频繁，然而它计算相对复杂，处理速度明显低于其他运算， 因此用FPGA实现快速的当n大于等于3的n次方根运算是比较困难的。目前，求解输入数据 的平方根算法(开2次方根运算)已经被提出了多种，比如牛顿迭代法、SRT-冗余算法、非 冗余算法、CORDIC算法等。这些算法已经比较成熟，并且成功地运用到硬件电路设计中，实 现方便快速。但是如果要计算一个输入数据的n次方根(n大于等于3)，运用上述算法将变 得非常复杂，硬件实现困难且相当麻烦。

当然，目前也有一些其他方法用于计算一个数据的n次方根，比如通过软件的方法来进 行计算，但是这种高级语言的计算需要取指、译码等然后进行许多次乘法和加法运算，执行 一次n次方根计算的时间很长，达不到硬件计算电路的高速率标准。另外一种常用的，就是 查表法。具体方法就是将被开n次方的数据作为地址，其n次方根的结果作为对应地址的内 容存放到ROM中。这样，当输入一个被开n次方根的数据时，以此数据作为地址对ROM进行 查询，得到的结果就是它的n次方根值。采用查表法需要事先获得n次方根表并将其存放到 ROM中，这种办法虽然不需要计算，但也存在以下缺点：(1)存储容量巨大。比如要实现一 个32bit输入数据的n次方根运算，那就需要2的32次方即4G个地址空间的ROM。(2)处 理延时较大。用于查询的时延较大，直接导致数字系统的时钟频率降低。(3)对于大容量的 查表，其维护困难。主要是因为当需要改变n次方根舍入方法时，必须更改大容量ROM的内 容，所需要的工作量巨大。(4)重用性不高。当需要n次方根结果精确到小数时，ROM的容 量和查找表内容都相应的要做出修改。

发明内容

本发明所要解决的技术问题是，提供一种新的，不用占用大量存储空间的，能够在硬件 上实现开方运算的方法以及实现该方法的开方运算器。

开方运算的硬件实现方法，包括以下步骤：

步骤1、输入数据寄存器存储待进行开n次方运算的数据，再进入步骤2，所述n为大于 等于3的正整数；

步骤2、处理模块确定中间值寄存器变量i的初始值，所述变量i为中间值寄存器的第i 比特位，初始化中间值寄存器的第i比特位为1，其余比特位为0，再进入步骤3；

步骤3、处理模块根据n的大小来控制乘法运算模块对中间值寄存器中的值进行n次方运算， 乘法运算模块将结果输出至中间结果寄存器，再进入步骤4；

步骤4、比较器比较输入数据寄存器中的值与中间结果寄存器中的值的大小，并将比较结 果反馈至处理模块，再进入步骤5；

步骤5、处理模块根据比较结果设置中间值寄存器：当输入数据寄存器中的值大于中间结 果寄存器中的值时，更新i为i-1，设置中间结果寄存器的第i比特位为1，再进入步骤7；当输 入数据寄存器中的值小于中间结果寄存器中的值时，重新设置第i比特位为0，再更新i为i-1， 设置第i比特位为1，再进入步骤7；当输入数据寄存器中的值等于中间结果寄存器中的值时， 进入步骤8；

步骤7、处理模块判断i是否为0，如是，则进入步骤8，如否，则返回步骤3；

步骤8、处理模块控制中间值寄存器将当前存储的值输入至结果寄存器中，本次开方运算 结束。

具体的，步骤2中，处理模块确定中间值寄存器变量i的初始值，应保证初始化后的中间 值寄存器的值在进行n次方运算后大于输入数据寄存器的值。

本发明采用逐位逼近法，先开辟一个全0的寄存器作为输入数据的n次方根值的中间值 寄存器，再确定一个寄存器变量i的初始值，并置中间值寄存器的第i位为1，确保初始化后 的中间值寄存器的值的n次方大于原始输入数据。之后逐渐设置中间值寄存器的低位，并将 设置后的值进行n次方运算，将n次方运算结果与输入数据进行比较，从而调整中间值寄存 器的设置，直到i减为0或者n次方运算结果等于输入数据，开方运算结束，将此时中间值 寄存器中的值作为开方运算结果。

进一步的，还能通过将结果保留几个小数位来确保实际中想要达到的精度。步骤4中， 如需要将开方运算结果精确到小数位l，则处理模块先控制比较器对输入数据寄存器中的值做 左移运算，左移l×n位得到输入数据寄存器中左移后的值；比较器再比较输入数据寄存器中 左移后的值与中间结果寄存器中的值的大小，并将比较结果反馈至处理模块，再进入步骤5。

实现上述方法的开方运算器，包括输入数据寄存器、处理模块、中间值寄存器、中间结 果寄存器、开方结果寄存器、乘法运算模块、比较器；

所述输入数据寄存器，用于存储待进行开n次方运算的数据，所述n为大于等于3的正 整数；

所述处理模块，用于初始化时，确定中间值寄存器变量i的初始值，所述变量i为中间值 寄存器的第i比特位，初始化中间值寄存器的第i比特位为1，其余比特位为0，初始化设置 完毕之后触发乘法运算模块；根据n的大小来控制乘法运算模块进行n次方运算；

根据比较结果设置中间值寄存器，当输入数据寄存器中的值大于中间结果寄存器中的值 时，更新i为i-1，设置中间结果寄存器的第i比特位为1，再判断i是否为0，如是，则控制 中间值寄存器将当前存储的值输入至结果寄存器中，如否，则触发乘法运算模块；当输入数 据寄存器中的值小于中间结果寄存器中的值时，重新设置第i比特位为0，再更新i为i-1， 设置第i比特位为1，再判断i是否为0，如是，则控制中间值寄存器将当前存储的值输入至 结果寄存器中，如否，则触发乘法运算模块；当输入数据寄存器中的值等于中间结果寄存器 中的值时，直接控制中间值寄存器将当前存储的值输出至结果寄存器中；

所述中间值寄存器，用于存储开方运算的中间值；

所述乘法运算模块，用于对中间值寄存器的值进行n次方运算，将结果输出至中间结果 寄存器，并触发比较器；

所述中间结果寄存器，用于存储中间值进行n次方运算后的结果；

所述比较器，用于比较输入数据寄存器中的值与中间结果寄存器中的值的大小，并将比 较结果反馈至处理模块；

所述结果寄存器，用于存储开方运算的结果。

进一步的，处理模块用于，当开方运算结果设置为精确到小数位l，则处理模块控制比较 器对输入数据寄存器中的值做左移运算；

所述比较器用于，对输入数据寄存器中的值做左移运算，左移l×n位得到输入数据寄存 器中左移后的值，比较输入数据寄存器中左移后的值与中间结果寄存器中的值的大小。

本发明的有益效果是，通过硬件的计算可以节省大量的计算时间，简单易行、资源占用 少而且快速准确，可以根据实际的需要将n次方根值的结果保留所需要的小数位数以确保一 定的精度。

附图说明

图1为开方运算器示意图；

图2为实施例的中间计算寄存器示意图；

图3为实施例的开方运算流程图；

图4为乘法运算模块对中间计算寄存器的值分别进行3、4、5、6次方运算的流水线电路 结构图；

图5为实施例对输入数据求三次方根的modelsim仿真。

具体实施方式

本实施基于FPGA实现，设需要计算n次方根值的输入数据均为16bit的无符号整数，n在本 实施例中为大于3的整数。虽然本发明的方法也可以适用于n为1或2的情况，但此时使用本方 案不具运算优势。输入数据与开方计算结果均存储在16bit的寄存器当中。

开方运算器如图1所示，开方运算器，包括输入数据寄存器、处理模块、中间值寄存器、 中间结果寄存器、开方结果寄存器、乘法运算模块、比较器；处理模块分别与输入数据寄存 器、中间值寄存器、乘法运算模块、比较器的控制端相连；输入数据寄存器的输出端与比较 器的一个输入端相连；中间值寄存器的一个输出端与乘法运算模块的输入端相连，中间值寄 存器的一个输出端与结果寄存器的输入端相连，乘法运算模块的输出端与中间结果寄存器的 输入端相连，中间结果寄存器的输出端连接比较器的另一个输入端；比较器的输出端与处理 模块的一个输入端相连。

存储开方运算的中间值的中间值寄存器r如图2所示，它分为整数部分和小数部分。我 们在逼近计算的过程中，先确定寄存器变量i的初始值，然后逐步确定r的第i位、i-1位… 最后到r的第0位。这样再把寄存器r的值输出到开方结果寄存器，就得到了原输入数据的 n次方根值。本实例设置n次方根值的结果保留低4位作为小数部分，高位为整数部分。开 方运算过程如图3所示：

I、输入数据寄存器接收输入的16bit数据m；

II、处理模块开辟一个16bit全0的中间值寄存器r，将其作为存储输入数据m的n次 方根值的中间计算寄存器，然后处理模块对m数值上所属范围进行简单的判断，同时根据n 次方根结果保留的小数位数确定寄存器变量i的初始值，置r的第i位r[i]＝1。比如，我们以 1023为界限，对16bit数据m进行简单划分。如需要对m开5次方根，则先判断m是否大 于1023。如果m＞1023，由于(2⁴)⁵＝2²⁰＞2¹⁶＞m，而且结果保留低4位作为小数部分，所以 我们将i初值定为4+4＝8；如果m≤1023，由于(2²)⁵＝210＝1024＞m，于是我们将i初值定为 4+2＝6。这里确定i初值的根据就是使得寄存器r第i位置1，除去小数位，将它做5次方运 算后，其值一定大于m。这样我们就可以从初始位开始从高到低，依次确定寄存器r的比特 位，直至第0位，而初始位以上的高位均为0。根据m的数值范围确定不同的i值，目的是 为了减少中间值寄存器r中需要确定的比特位数，这样就可以节省一些运算时间。

III、处理模块对寄存器r设置完成之后，将寄存器r中的值(中间值)输入至乘法运算 模块做n次方运算，并将运算结果存储在中间结果寄存器q中。乘法运算模块需要计算寄存 器r中的值n次方。图4(a)给出了对中间值进行3次方运算的流水线电路结构图，使用了 2个乘法器进行运算，先将2个相同中间值输入至第一个乘法器进行第一次乘法运算，再将 第一次乘法运算的结果以及1个中间值输入至第二个乘法器进行第二次乘法运算，第二次乘 法运算的结果为3次方运算结果；图4(b)对中间值进行4次方运算的流水线电路结构图， 需要用到2个乘法器，先将2个相同中间值输入至第一个乘法器进行第一次乘法运算，再将 第一次乘法运算的结果作为第二个乘法器的2个输入，第二次乘法运算的结果为4次方运算 结果；同理，图4(c)、(d)分别给出了对中间值进行5、6次方运算的流水线电路结构图； 其他计算中间值的多次方的电路图结构均可以依次类推得到，也可以使用其他本领域技术人 员的惯用电路结构实现。乘法运算模块在进行中间值的n次方计算的流水线电路中，所用到 的乘法器个数也根据n值来确定，n越大，所用到的乘法器也越多。但是，如果计算中间值 的n次方不用流水线工作的话，整个乘法运算模块只需一个乘法器即可，将乘法器的输出再 不断的反馈到输入端，进而同样可实现n次方运算；

IV、乘法运算模块计算出中间值的n次方值后，将结果存储到中间结果寄存器q之后， 处理模块控制比较器比较中间结果寄存器q的值与输入数据m的大小，由于寄存器r中低4 位为小数部分，而输入数据m为16bit的无符号整数，为了正确比较，处理模块首先应该将m 左移4×n位得到m’，然后把m’与中间值的n次方值(中间结果寄存器q的值)做比较，并 将比较结果返回处理模块；

V、当中间结果寄存器的值q＞m’，处理模块置r[i]＝0，更新i＝i-1，再设置r[i]＝1， 再判断当前的i是否为0，如是，处理模块将当前中间值寄存器r中的值输出到结果寄存器， 当前的中间值即为输入数据m的n次方根值，低4位为保留的小数位，如否，则返回步骤IV；

当中间结果寄存器的值q＜m’，处理模块保持r[i]＝1不变，更新i＝i-1，再设置r[i]＝1； 再判断当前的i是否为0，如是，处理模块将当前中间值寄存器r中的值输出到结果寄存器， 当前的中间值即为输入数据m的n次方根值，低4位为保留的小数位，如否，则返回步骤 III；

当中间结果寄存器的值q＝m’，处理模块将当前中间值寄存器r中的值输出到结果寄 存器，当前的中间值即为输入数据m的n次方根值，低4位为保留的小数位。

通过上述实施过程，我们就能够计算输入的16bit无符号整数的n次方根值，并将结果低 4位保留为小数位，确保了一定的精度。

图5为本实施例计算输入16bit无符号整数的3次方根值modelsim仿真图。本仿真为了节 省硬件资源，采用非流水线方式，所以乘法运算模块只用了一个乘法器来实现中间值寄存器 的n次方运算。若要采用流水线方式，则会用到多个乘法器，增大硬件开销，但开方结果会按 照每个时钟周期流水线输出。图中最后两路信号线，倒数第2行din是输入16bit无符号整数的 十进制形式，最后一行root_out是输出3次方根值的十进制形式。由于低四位为小数位，所以 将root_out的值除以16即可得到输入数据的3次方根值，确保了4个bit位的精度。由于本仿真 对输入数据m以1023为界进行了简单划分，所以对不同范围的数据求三次方根的计算延时不 同。从仿真图中可以看到，对大于1023的数据进行一次三次方根运算的计算延时为32个时钟 周期，仿真时钟为10ns，所以延时为320ns。而对小于等于1023的数据进行一次三次方根运算 的计算延时为26个时钟周期，仿真时钟为10ns，所以延时为260ns。如果根据实际需求对输入 数据m进行更为详细的划分，将会节省更多的计算时间。明显可见，相比其他的n次方根计算 方式，显然具有简单快速、资源占用少的优点。

本发明提出的开方运算方法以及开方运算器，具有硬件运算的快速准确的特点，实施起 来简单易行、资源占用少，并能按实际需求保证一定的精度，特别是在进行大数据量的n次方 根计算时，相比现有的开方运算方法有着明显的优势。