大家好,又见面了,我是你们的朋友全栈君。
人们日常习惯的乘法是十进制,但计算机实现起来不方便。首先,需要记录9×9乘法表,每次相乘去表中找结果;其次,将竖式相加也不方便。
但二进制却十分方便,冯·诺伊曼在《关于ENDVAC的报告草案》中说“二进制可以极大简化乘法和除法运算。尤其是对于乘法,不再需要十进制乘法表,也不需要两轮的加法”。
二进制乘法运算过程
观察这个式子,可以发现我们并不需要乘法表,如果乘数位为0,就在中间过程中全补零,如果乘数位为1,就在中间过程补被乘数。
运算过程的进一步调整
按照上面那种计算的话,需要大量的空间来存储中间结果,还要用一个空间存储积。其实,不难发现,每个中间结果最后都加在乘积上,我们可以将中间结果保存在乘积中,每次用中间结果更新乘积,运算结束时,乘积里面放的就是正确的乘积。
上面说直接对乘积加上被乘数是不准确的,为了满足对齐要求,只需将被乘数左移。
这样,我们得到了一个适合硬件实现的乘法运算过程。
实现结构
以4-bit数为例,(1000)2 + (1001)2 = (1001000)2
具体流程
最终的结果如下:
4位的过程对N位同样有效。
N位的流程图
观察上面N位乘法器的流程图,由于每次信号要等到一个时钟上升沿才起作用,所以1a、2、3过程各用一个周期。其实这三个过程可以并列执行,就降为一个周期了。
面积优化就是指减少不必要的硬件资源。对于CPU这样的集成电路来说,它的价格的一个重要因素就是集体管的数量,或者说芯片的面积。因此,在设计各个功能部件的时候,如何减少芯片的面积也是一个重要的方向。
观察上面这个图,我们可以发现如下可以优化的地方:
我们只需逐一改进这些地方,注意,每个部件某个功能去掉,在另一个部件应加上该功能。比如”被乘数寄存器“取消了左移功能,”乘积寄存器“就相应的添加了右移功能。
优化后的图如下:
注:乘法寄存器实际应该是9位,以保存加法器的进位,但这里保持8位,以突出使用优化后的演变。
N位乘法器优化同理
参考链接:https://www.coursera.org/learn/jisuanji-zucheng/lecture/JioZX/404-cheng-fa-qi-de-you-hua-2
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/167115.html原文链接:https://javaforall.cn