乘法器的布斯算法原理与verilog实现
乘法器的布斯算法原理与VERILOG实现
1 乘法器基本原理
乘法器是处理器设计过程中经常要⾯对的运算部件。⼀般情况下，乘法可以直接交由综合⼯具处理或者调⽤EDA⼚商现成的IP，这种⽅式的好处是快捷和可靠，但也有它的不⾜之处，⽐如影响同⼀设计在不同⼯具平台之间的可移植性、时序⾯积可采取的优化⼿段有限、个性化设计需求⽆法满⾜等。所以，熟悉和掌握乘法器的底层实现原理还是有必要的，技多不压⾝，总有⽤得上的时候，同时也是⼀名IC设计⼯程师扎实基本功的体现。
不采⽤任何优化算法的乘法过程，可以⽤我们⼩学就学过的列竖式乘法来说明。从乘数的低位开始，每次取⼀位与被乘数相乘，其乘积作为部分积暂存，乘数的全部有效位都乘完后，再将所有部分积根据对应乘数数位的权值错位累加，得到最后的乘积。如下图，左边为⼗进制乘法过程，基数为10，右图为⼆进制乘法过程，基数为2。PP0～PP3分别表⽰每次相乘后的部分积。可见，⼆进制乘法与⼗制乘法本质上是没有差别的。
1 2 3
1 2 3
×
3 6 9
2 4 6 1 2 3
+
1 5 1
2 9……3×12
3 PP0
……2×123 PP1
……1×123 PP2
1 1 0 1
1 0 0 1
×
1 1 0 1
0 0 0 0
0 0 0 0
1 1 0 1
+
1 1 1 0 1 0 1
……1×1101 PP0
……0×1101 PP1
……0×1101 PP2
…
…1×1101 PP3
如果表⽰成通⽤形式，则如下图所⽰（以4位乘法器为例，其它位宽类似）
这样原始的乘法在设计上是可以实现的，但在⼯程应⽤上⼏乎不会采⽤，在时延与⾯积上都需要优化。⼀个N位的乘法运算，需要产⽣N个部分积，并对它们进⾏全加处
理，位宽越⼤，部分积个数越多，需要的加法器也越多，加法器延时也越⼤，那么针对乘法运算的优化，主要也就集中在两个⽅⾯：⼀是减少部分积的个数，⼆是减少加法器带来的延时。
2 BOOTH变换
以上述1101*1001为例，可以看到产⽣的四个部分积中，有两个是⾮零值（PP0, PP3），两个为零（PP1, PP2）。零值是不影响加法结果的，在计算中可以忽略，上述四个部分积的相加，实际上可以简化成两个⾮零部分积相加，从⽽减少加法器的数⽬。这也就匹配了上节所述乘法优化的第⼀个⽅⾯，减少部分积个数，实际上是减少⾮零部分积的个数。
同时在该例中不难看出，⾮零部分积的个数等于乘数中1的个数，如果是1101*1011，那么将存在三个⾮零部分积，如果是1101*1111，则存在4个⾮零部分积。那么对于⼀个给定的乘数，有什么⽅法可以减少⾮零部分积个数呢？先以⼀个例⼦来具象地展⽰⼀下，⽐如 N*01111110, N为任意⾮零数。
上式中，乘数为 01111110，存在6个1，如果不作任何变换，将产⽣6个⾮零部分积。但如果仔细观察，可以发现01111110可以表⽰成如下形式：
01111110 = 10000000 – 00000010
通过这个等式，N*01111110可以转化成
N*10000000 – N*00000010
在这个运算式中，相当于只有两个⾮零部分积相加（减法通过补码转变成加法），⼀下就省掉了4次累加，⼤⼤简化了运算。
因为上述变换直观上看是两个数的减法算式，还是不够简练，我们将减法式计算完成，但将计算结果换⼀种表⽰⽅法：不够减时不借位，直接⽤负数表⽰该位相减的结果：
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
1 0 0 0 0 0 -1 0
即01111110 = 100000-10，-1就是数学中的负1，可以验证这两个数是相等的：
01111110 = 0*27+1*26+1*25+1*24+1*23+1*22+1*21+0*20 = 64+32+16+8+4+2 = 126
100000-10 = 1*27+0*26+0*25+0*24+0*23+0*22+(-1)*21+0*20 = 128-2 = 126
再看下⾯的通⽤表达形式。
y=?2n?1y n?1+2n?2y n?2+?22y2+2y1+y0+y?1， y?1=0【1】
式1可看成任意有符号⼆进制数的补码表达形式，多项式最⾼项为符号位,y?1为附加项，定义其值为0，不影响⼆进制数的实际值。
对式1右边多项式等价变换（红体字是关键）：
y=?2n?1y n?1+2n?2y n?2+2n?2y n?2?2n?2y n?2+2n?3y n?3+2n?3y n?3
2n3y n3++2y1+2y12y1+y0+y0y0+y1
=?2n?1y n?1+2×2n?2y n?2?2n?2y n?2+2×2n?3y n?3?2n?3y n?3+?+2×2y1?2y1+2×y0?y0+y?1
=?2n?1y n?1+2n?1y n?2?2n?2y n?2+2n?2y n?3?2n?3y n?3+?+22y1?2y1 +2y0?y0+y?1
=2n?1(?y n?1+y n?2)+2n?2(?y n?2+y n?3)+?2(?y1+y0)+(?y0+y?1)【2】
由式1等价变换到式2，观察多项式的每⼀项可知，相邻两bit的1会被抵消为零，如果原⼆进制数中存在⼀连串的1，则最低位1变换为-1（0到1跳变位置），最⾼位1的上⼀位0变换为1（1到0跳变位置），⼆者中间的1全部变换为0，套⽤上述等价变换，便不难得出上例01111110= 100000-10的结论。这种变换，就是布斯变换，或称布斯编码。布斯变换可以对连续1的位数⼤于等于3的⼆进制数起到化简作⽤，连续1的位数越多，化简效果越好。当⽤于乘法计算时，对乘式中连续1较多的乘数进⾏布斯变换后再相乘，则会减少⾮0部分积的个数，从⽽对部分积的累加过程起到优化作⽤。
但上述变换并不能在硬件乘法器电路中起到真正的优化作⽤，经过变换后的⼆进制数（式2）与原⼆进
制数（式1）相⽐，多项表达式的项数并没有变化，也就是说实际部分积个数不会减少。虽然从理论上来讲减少⾮0部分积个数就简化了累加操作，但硬件电路的结构是相对固定的，加法器个数只与部分积个数相关，与部分积的值是否全0⽆关。所以在电路设计中，⼀般采⽤改进的布斯编码⽅式，达到真正减少部分积个数，从⽽减少累加器个数的⽬的。
依旧对式1进⾏等价变形（红体字是关键）：
y=?2×2n?2y n?1+2n?2y n?2+2n?3y n?3+2n?3y n?3?2n?3y n?3+2n?4y n?4
+2n?5y n?5+2n?5y n?5?2n?5y n?5+?+23y3?23y3+22y2+2y1
+2y1?2y1+y0+y?1
=?2×2n?2y n?1+2n?2y n?2+2×2n?3y n?3?2×2n?4y n?3+2n?4y n?4
+2×2n?5y n?5?2×2n?6y n?5+??2×22y3+22y2+2×2y1?2y1
+y0+y?1
=?2×2n?2y n?1+2n?2y n?2+2n?2y n?3?2×2n?4y n?3+2n?4y n?4+2n?4y n?5?2×2n?6y n?5+??2×22y3+22y2+22y1?
2y1+y0+y?1
=2n?2(?2y n?1+y n?2+y n?3)+2n?4(?2y n?3+y n?4+y n?5)+?+22(?2y3+
y2+y1)+(?2y1+y0+y?1)【3】
通过式3的等效变形后可以发现，多项表达式的项数变成了原来的⼀半。原⼆进制数从LSB开始，以三位为⼀组（第⼀组最低位需补⼀个附加位即y?1，附加值为0），相邻组之间重叠⼀位（低位组的最⾼位与⾼位组的最低位重叠），构成新的多项式因⼦，这就是改进的布斯编码⽅式。
两个⼆进制数乘，如果对乘数进⾏式3所⽰的改进型布斯编码，则得出的部分积个数相较直接相乘可以减半。⽐如，两个32位数相乘，不做布斯编码直接相乘，则有32个部分积需要累加，⽽采⽤式3的编码⽅式对其中⼀个因数进⾏变换后，将只有16个部分积需要累加(如果兼容⽆符号数，则需要累加17个部分积，后⽂将具体描述)。
由式3可知，组成多项式因⼦的每连续三位之间的关系是完全相同的，⼆进制中每⼀位的数值⾮0即1，由此可以列出相邻三位所有取值组合下，其对应多项式因⼦的值。设某乘法运算中，被乘数为Y，乘数为X，x2i+1, x2i, x2i?1分别为X的连续三位，其中i∈N，PP i为i不同取值下对应的部分积，对X进⾏改进的布斯变换后再与Y相乘，则可以有如下推算关系。
表1 基4布斯编码查表
由此可见，根据乘数每连续三位的值，可以快速推算出其对应的部分积。且在⼆进制中，乘2操作可以通过左移⼀位来实现，不需要复杂的计算，电路实现⾮常简单，通过此⽅法，解决了硬件乘法优化的第⼀个⽅⾯，简化和减少部分积的⽣成。作为改进型布斯编码中最基础的⼀种，它被称之为基4布斯编码。基4编码相当于每次⽤乘数的两位与被乘数相乘产⽣部分积，从⽽使
部分积个数减少⼀半，也可以看成是将乘数转化为4进制表达，故称为基4(Radix-4 Booth Encoding)。采⽤基4布斯编码的乘法相较于传统乘法运算，优化效果已经很明显且易于实现，可以满⾜⼤部分应⽤要求，32位乘法器，甚⾄64位乘法器都可以采⽤，是⽐较常⽤的⼀种⽅式。当然，更⾼阶的布斯编码
可以更⼤程度地减少部分积个数，但因其部分积产⽣逻辑⽆法单纯通过移位实现，需要引⼊加法器等其它运算部件，从这⽅⾯来看⼜削弱了优化效果，需要综合考量选择。⾼阶布斯编码的实现可以⽤式3 类似的⽅法导出，本⽂对此暂不作讨论，感兴趣的读者可⾃⾏推导。
3 进位保留加法器、3-2压缩与4-2压缩
布斯编码解决了乘法优化的第⼀个⽅⾯，通过减少部分积个数从⽽减少累加器个数，但累加器本⾝的进位传递延时对电路性能依然存在⾮常⼤的影响，所以优化的第⼆个⽅⾯，就是改进部分积累加结构，提升累加性能。如果采⽤部分积直接相加的⽅式，因为全加器进位的关系，当前bit的相加结果依赖于它前⼀bit的进位输出，整个计算过程相当于串⾏化，位宽越⼤，延时越⼤，所以优化的关键就是消除进位链，使运算并⾏化。
进位保留加法器（Carry Save Adder, CSA ）是⽐较常⽤的⼀种优化⽅式，CSA 实际上就是⼀位全加器，其逻辑表达⽰如下：
S i = A i ^B i ^C i?1
booth算法乘法例题讲解
C i = A i B i + C i?1(A i +B i )
下⾯⽤⼀个例⼦对照来说明CSA 怎样起到减少加法器延时的作⽤。
假设将三个4位数相加，分别是A[3:0], B[3:0] 和 C[3:0]，先看第⼀种加法实现⽅式如下：
A[0]
B[0]A[1]
B[1]A[2]
B[2]A[3]
B[3]
上述⽅式中，第⼀级加法存在4个CSA 进位链带来的延时，如红⾊简头所⽰，显⽽易见如果计算位宽
更⼤，则延时越⼤。
同样采⽤CSA ，换⼀种组织⽅式如下，CSA 的两个输⼊端和⼀个进位输⼊端分别接⼊三个待求和加数，CSA 的进位输出作为下⼀级加法器的输⼊，如红⾊箭头所⽰。可以看出第⼀级4个CSA 是全并⾏的，⼀共只消耗⼀个CAS 的延时，并且该延时不会随着位宽的增长⽽增加。这种⽅式相当于⼀次接受3个输⼊产⽣2个输出，因此也称为3-2计数器或3-2压缩。运⽤到乘法器中，通过对若⼲个部分积按每3个为⼀组进⾏CSA 计算，然后⽤同样的⽅法运⽤到每级
CSA 产⽣的输出上，直到最后⼀级CSA 的两个输出，再⽤全加器得到最后的部分积累加结果。
A[0]B[0]A[1]B[1]A[2]B[2]A[3]B[3]C[0]
C[1]C[2]C[3]
3-2计数器由于砍断了⾏波加法进位链，从⽽可以实现部分积累加并⾏，极⼤削减了计算时延，同时由于存在输⼊到输出由3到2的压缩关系，也减少了累加级数，从⽽起到优化运算的效果。
相较于3-2压缩，还有⼀种压缩率更⾼的⽅式叫4-2压缩，或称为5-3计数器。顾名思义，就是有5个输⼊端，产⽣3个输出，运⽤到加法上，可以实现同时计算四个
加数，⽣成对应的结果与进位值。设5-3计数器的5个输⼊分别为I0、I1、I2、I3、C i，3个输出端分别为D、C、C O，则它们之间满⾜如下代数关系：
D+C×2+C O×2=I0+I1+I2+I3+C i
根据上述代数关系式，可推算出真值表：
表2 5-3计数器真值表
输出与输⼊之间的逻辑经化简最后可表达⽰为
D=I0^I1^I2^I3^C i
C=((I0^I1^I2^I3)&C i) | ~((I0^I1^I2^I3) | ~((I0&I1) | (I2&I3)))
C O=(I0 | I1) & (I2 | I3)
鉴于逻辑表达⽰看上去有⼀定复杂度，⽤更直观的逻辑图表⽰如下：
I0
I1I2I3
通过相邻两bit 的 C O 与C i 级连，便可以实现多bit 的加法，⼀次可以对四个加数进⾏运算。因为 C O 并不参与⽣成C 的逻辑运算，所以这种级连不会造成⾏波进位链，每个5-3计数器之间依然是并⾏的。
举例：A[2:0], B[2:0], C[2:0], D[2:0]为待累加的四个数，采⽤如下⽅式进⾏4-2压缩后，最终结果为 (T[2:0]<<1) + S[2:0]。