学习日志之microelectronic(5)——Booth's algorithm

对乘法器的理解

乘法器的原理就是用二进制乘法竖式得来的如下图所示，只有在二进制位上为1时才会不为零，其结果可以表示为

 

广义化就变成了下面的式子：

根据此就可以得到一个最简单的乘法器——array multiplier：

critical path：the sequence of stages determining the minimum time needed for an operation, especially when analysed on a computer for a large organization.

booth's algorithm

假设A=010 B=00011000，那么可知

随后就可以写成以下形式：

对此段的理解如下：

---

比如说计算10100001×00111110，在这里首先将乘数00111110改写为01000000 - 00000010

即

                       01000000

               -       00000010

---------------------------------------------------

                       001111110

这样根据乘法分配律得10100001×00111110=10100001×（01000000-0000010）

类似于booth算法的重新编码形式，再将上述算式改写为

10100001×00111110=10100001×0+1 000000    +     10100001×000000 -1 0

最终再将上式合并到一起，可得由booth算法改写后的编码形式：10100001 × 0+10000-10

由此可见，乘数的数段"01"可以重新编码为“+1”,数段“10”可以重新编码为“-1”，数段“11”可重新编码为“0”

---

booth 算法步骤可以由下面的伪代码表示，其中i为B元素的下标，P为积，M为B乘数的位数

其中有一个vp，其表达式可以在一个列表中查到（当i=0时，规定b[-1]=0）

由上面可得

从而可得booth's multiplier的结构如下所示：

参考资料：https://blog.****.net/ZHjiao_1997/article/details/52475498