在线刊号(2278-8875)印刷版(2320-3765)
Sukhmeet考尔1, Suman2Manpreet Singh Manna3., Rajeev Agarwal4
|
有关文章载于Pubmed,谷歌学者 |
更多相关文章请访问国际电气、电子和仪器工程高级研究杂志
二进制除法基本上是确定除数D除以被除数B的次数从而得到商q的一个过程。在这个过程的每一步中,除数D要么把B分成一组位,要么不。当除数的值小于或等于一组位的值时,除数对这些位进行除数。因此,商不是1就是0。除法算法根据除数和部分余数的符号进行加法或减法运算。有许多二进制除法算法,如数字递归算法恢复,非恢复和SRT除法(Sweeney, Robertson和Tocher),乘法算法,近似算法,CORDIC算法和连续积算法。本文主要研究了数字递归式非恢复除法算法,采用高速减法器和加法器设计了非恢复除法算法。采用高速加减法,加快除法运算速度。该除法算法采用VHDL语言进行设计,并采用Xilinx ISE 8.1i软件进行仿真,在FPGA xc3s100e-5vq100上实现。
关键字 |
恢复除法算法,非恢复除法算法,高速加法器,高速减法 |
介绍 |
计算机自诞生以来发展迅速。然而,有一件事没有改变:计算机的主要目的是做算术来运行程序和应用程序。基本上,计算机处理大量数字是基于加法、乘法和除法这三种基本算术运算。与加法和乘法相比,除法是使用最少的运算。然而,如果忽略除法,计算机的性能将会下降[I, 2,3]。Oberman和Flynn[9]给出了在硬件中实现除法的主要算法。面向硬件的除法算法主要有三类:数字递归、函数迭代和基于表的方法。 |
每种方法都有自己的优点[I],但数字递归除法是许多浮点单位除法和开方最常用的算法,因为它简单,复杂度比收敛除法低[2,4,5]。恢复、非恢复和SRT除法是数字递归除法的代表性算法。除法相当于在被除数上重复减去除数,直到剩下的数的大小小于除数。减去的数就是商,剩下的数就是余数。这个过程,如果直接进行,是非常耗时的。如果在第一次减法之前,除数和被除数的最有效数位对齐,然后在移位之前,当部分余数小于除数时,除数就向右移动,则可以大大加快计算速度。如果初始对齐使除数大于被除数,则在做减法之前可能需要做一次移位。”在二进制中,移位之间最多只能做一次减法,以下情况除外。有两种传统的方法可以避免在每次减法之后比较余数和除数。在恢复除法时,继续减法,直到部分余数的符号发生变化;在右移之前,这个变化会导致除数的立即增加和累加商的相应减量。 In non restoring division, the sign change causes a shift followed by one or more additions until the sign changes back. |
2恢复分区 |
在还原除法中,商数用非冗余数系统表示,这是“纸笔”常用算法。它的主要特点是推导出新的商数字[6]所需的全宽比较。在恢复除法时,除数移位,并从被除数中减去。如果除数的减法在相对于被除数的任何位位置产生负的结果,则在该位位置的操作是不成功的,并且在商的相应位置放置0。除数被加回(恢复)到除法运算的结果中,然后被除数的下一位高位被移到结果的左位位置。当红利的每一位从右向左移动时,商就从左向右递增。移位n次后,其中n表示被除数中的位数,除法运算完成。完整的恢复划分硬件如图1所示。在这个图中,在操作开始时,一个n位的正除数被装入寄存器M, n位的被除数被装入寄存器Q。除法完成后,n位商在寄存器Q中,余数在寄存器a中。最后一次恢复操作后的结果就是余数。 |
![]() |
恢复除法算法与手动执行长除法非常相似。下面介绍恢复除法的算法,流程图如图2所示。 |
•将Count设置为0,并在A寄存器中输入0。 |
•启动循环n次 |
•将A和Q向左移动一个二进制位置 |
•a减去M,把答案放回a |
•如果A的符号< 0,将Q0设为0,并将M加回A(恢复A); |
•否则,将q0设置为1 |
•检查count,当count = n-1时停止循环。 |
![]() |
3不复原的部门 |
非还原除法算法(Non-restoring Division Algorithm, NrDA)来自于还原除法。还原算法通过连续从分子中减去移位的分母来计算余数,直到余数在适当的范围内。每一步的操作取决于上一步的结果。非还原除法有一个商数字集{I, - I},而不是传统的二进制数字集[7,9]。通过非还原除法,我们发现商位的-1可以简单地设置为0,而商就是我们想要找到的[8]的实际商。我们把Q分解成小块。 |
下面介绍恢复除法的算法,流程图如图3所示。 |
1.从被除数的最有效位(MSB)减去除数。 |
2.“取下”除数的下一个MSB,并将其附加到步骤1的结果。 |
3.检查步骤2的结果的符号。如果第2步的结果为正: |
a.设置商的下一个MSB为1。 |
b.从结果中减去除数得到一个新的结果。 |
如果第2步的结果为负: |
a.设置商的下一个MSB为0。 |
b.对结果加除数,得到新的结果。 |
4.重复步骤2和3,直到商数的所有位都确定。 |
![]() |
四、高速加/减器 |
二进制数的并行加法意味着加数和加数的所有位都可以同时计算。在并行加法器中,每一级的进位输出都连接到下一级的进位输入(纹波进位)。因此,在输入进位发生之前,任何阶段的和输出和进位都不能产生。这将导致加法过程中的时间延迟。这种延迟被称为“携带传播延迟”。由于输出和的每一位都取决于输入进位的值,因此只有在输入进位到该阶段的传播之后,加法器中任何给定阶段的“Si”的值才会处于稳态最终值。为了提高加器的速度,可以采用以下几种方法:— |
1.减少携带传播延迟时间的一种方法是采用更快的门,减少延迟。 |
2.最广泛使用的技巧是“前瞻进位”原则。该方法利用逻辑门来查看增数的低阶位,并加成以查看是否将生成高阶进位。它使用两个函数:进位生成和进位传播。 |
最终进位不取决于中间进位,只取决于输入位 |
超前进位算法是一种快速加法器,其设计目的是减小基本加法器中进位传播引起的延迟。它利用了这样一个事实,即在加法的每个位位置,可以确定是否在该位生成进位,或者是否将通过该位传播进位。带进位产生和进位传播的全加法器逻辑图如图4所示。 |
![]() |
![]() |
![]() |
在上面的计算中,我们可以看到C1, C2, C3和C4只依赖于Co (Carry In),而不依赖于之前的进位。高速加减法电路与高速加减法电路没有太大区别。唯一不同的是加法器的第二个输入将被反向,然后使用加法器电路添加。因此,我们可以使用相同的电路,但稍作修改,如图5所示。 |
![]() |
五、逐步计算29除以11。 |
在这个例子中,我们将29作为被除数,并以二进制形式存储在寄存器Dnd中,9作为除数,并将其二进制值存储在寄存器d中。我们使用另外两个寄存器AD和ZD进行计算并临时存储结果,如图6所示。 |
除法输入: |
DND(股息)= 000011101 = (01DH) = (+29) |
D(除数)= 000001011 = (00BH) = (+11) |
除法输出: |
余数(10位)= 0000000111= (007H) |
商(9位)= 000000011= (002H) |
![]() |
VI.SIMULATION结果 |
整个体系结构使用VHDL建模。编码是在Spartan 3上的Xilinx ISE 8.1i上完成的,使用目标设备:xc3s100e -5vq100,速度等级为-5。可以使用ModelSim SE 6.3f模拟器进行仿真。DIV_HSA的仿真结果分别如图7和图8所示。图7显示了划分电路的顶部RTL视图。在这个图中,我们可以看到除法硬件有两个输入和两个输出。除数存储在寄存器D中,被数存储在寄存器Dnd中。除法算法的商和提醒分别存储在寄存器商和提醒寄存器中。 |
![]() |
图8所示。显示除法算法的最终RTL视图。在这张图中,我们可以看到有各种各样的块,它们正在进行各种运算,如偏除法的计算和余数的计算等。 |
![]() |
图9所示。显示了29/11的模拟结果。我们可以看到,29存储在寄存器Dnd中,它是被除数,而11存储在寄存器D中,它是除数。两个值都是十进制。在模拟29/11后,商存储在商中,提醒存储在提醒寄存器中,我们可以在图8中看到。 |
![]() |
![]() |
7结论 |
传统的除法器由于硬件实现的复杂性和成本,被DSP算法设计者所避免。本文采用VHDL语言设计非恢复除法程序,并在FPGA上实现,其结果硬件总利用率如图10所示。实践证明,该系统的硬件实现不仅简单,而且具有成本效益。 |
参考文献 |
|