booth算法(Booth算法最低位全加器)

booth算法(Booth算法最低位全加器)

1、《计算机体系结构基础第三版》定点补码乘法器。本小记几乎是对《计算机体系结构基础第三版》定点补码乘法器的个人描述，补充地方在于最后华莱士树的部分。

2、软件方式即类似我们手工计算，如计算1101*0101。这个乘法器有两个明显的特点：。

3、只能用于计算无符号数乘法，如果要计算补码乘法则必须将两者转为绝对值，运算结束后再根据原始的符号决定正负，转换为对应的相反数或本身。就第2点来看，补码加法只需要无脑加就能得出结果，然而补码乘法竟然还得根据符号做出这样的转换，显得有点麻烦并且有点不对等了。因此下面引出的解决方案，让补码乘法也能像补码加法那样，“无脑乘”，省去最后做出的转换步骤。

4、根据补码的定义，可以将乘数转换为如下形式：。可以看到除了第个部分积需要加上负号外，其余部分积可套用之前的电路来计算。因此在原来无符号乘法电路的基础上，我们只需要对最后一个部分积进行特判，就能实现补码乘法了，即最终出来的结果不用根据符号再作转换。所谓前人种树后人乘凉，有了下面的乘法器，这个无脑乘电路又略显逊色了，逊色在于这个特判需要额外的状态机来控制，增加了硬件复杂度，相比之下算法对机器更加友好，统一操作，省去特判，

5、对电路的改造依然是基于对表达式的转换：下图对乘数的表示做的一番转换，使其每一个加法项变成统一的形式：诶，这样一来，对于第个部分积就等于，也就是我们每次只需要通过乘数的最后两位确定如何将被乘数加到结果当中：。补码加，+[]补，

booth算法(Booth算法最低位全加器)

1、补码减，-[]补，这样我们就统一了部分积的计算规则，省去了特判状态机。

2、然鹅此时位乘法还是需要拍，因此可以将式子继续变换：。这个式子的结果也是一目了然了：从之前的每次移位1位，变成移位2位，并且部分积从之前的根据乘数后2位来确定变成根据乘数后3位来确定：。补码加，+[]补，

3、补码加，+[]补，补码加2，+[]补左移，补码减2，-[]补左移，补码减，-[]补，

4、补码减，-[]补，这样位乘法只需要/2-1次加法，使用/2拍完成。

5、类似地可以将式子变换成移位3位、4位等，不过这样需要的硬件就更加复杂，两位乘算法更适合硬件实现，更为实用，应该是吧，下面介绍两位乘的具体实现细节：假设[]补的二进制格式写作76543210，再假设部分积等于76543210+，那么根据上表有：。