Booth编码在补码乘法中的应用

王超

摘 要：在数字信号处理中，乘法器是运算单元的核心部件之一，通过Booth编码减少部分积的数量，能提高乘法运算的速度。该文分析了优化乘法器的两种思路，推导了2基Booth编码及4基Booth编码，指出在实现乘法器中优先考虑4基Booth编码的原因，阐述了在应用Booth编码时注意的问题，在实际应用中验证了该方案的有效性和稳定性。

关键词：补码 Booth编码 乘法器

中图分类号：TP31 文献标识码：A 文章编号：1674-098X（2012）12（b）-00-01

在数字信号处理芯片或一般微处理器芯片中，乘法器是芯片的核心之一，是处理器中进行数据处理的关键部件。乘法器完成一次操作的周期基本上决定了处理器的主频。乘法器的速度和面积优化对于整个处理芯片的性能来说是非常重要的。为了加快乘法器的执行速度，减少乘法器的面积，有必要对乘法器的算法、结构及电路的具体实现做深入的研究。

乘法器工作的基本原理是首先生成部分积，再将这些部分积相加得到乘积，如对于补码形式N位有符号数乘法A×B来说，常规的乘法运算会产生N个部分积，这和一般手算乘法的过程没有什么区别。

从乘法器工作的基本原理可以看出，要提高乘法运算的性能，可以从两方面入手，一个是减少部分积的数量，另一个是缩短部分积的相加的运算时间。在节省部分积相加的运算方面，通常使用3：2CSA（Carry Saved Add）等压缩编码方法。而该文就是针对第一方面，就如何减少部分积的数量，着重推导Booth编码原理，并简要分析了Booth编码的算法实现中的关键点。

1 基和4基Booth编码

对于某个数A，采用n Bit的补码可以表示成以下形式：

…………（1）

可以改写成以下形式：

…………………………（2）

其中，。

由此可得：

…………………（3）

因为和只能取值0/1，故可以获得如表1所示的码表，称为2基的Booth编码表：

由（3）式结合表1可知，A和B的乘积P可以通过B/-B移位相加得到，这就称为2基Booth编码，产生n个部分积，共需n次累加，这个在实现上和普通手算乘法没有区别。

当n是偶数时，（1）式可以改写成：

……………（4）

当n为奇数时，对于一个补码形式的数，可以直接在A的最高位增加一位与符号位相同的数，就可以满足（4）式的表示形式了。

因此，

……（5）

因为、和只能取值0/1，故可以获得如表 2所示的码表，称为4基Booth编码表。

表1

0 0 0

0 1 B

1 0 -B

1 1 0

表2

0 0 0 0

0 0 1 B

0 1 0 B

0 1 1 2B

1 0 0 -2B

1 0 1 -B

1 1 0 -B

1 1 1 0

通过（5）式可以看出，A和B的乘积P，也可以通过对B/-B进行移位相加得到，这就是4基Booth编码，共产生[n/2]个部分积（[*]表示向上取整运算）。

从上面的推导过程可以看出，数A还可以进行其他基的Booth编码等，但是编码复杂度有所增加。另外，主要考虑到在芯片实现时，出现部分积不是的这种情况，使得部分积不是被乘数左移若干位的情况，这种情况下要在芯片实现增加很多难度。例如，8基的Booth编码中，将会出现-3B/3B这两种情况，不是简单的把B左移一位或者两位能够实现的。因此，在芯片实现时往往优先考虑4基的Booth编码，使部分积的数量相对原来减少一半。

2 Booth编码的应用

在补码形式的两数A、B相乘中，不管是2基Booth编码、4基Booth编码还是其他基的Booth编码，都会涉及到一个对“负”的部分积的进行取反“+1”的问题。处理手法是先取反，把“+1”放到后面的部分积当中。当然，最后一个部分积也存在是“负”数的情况，在这种情况下同样要取反“+1”，因此，在补码乘法Booth编码中，会多一个部分积出现，有区别于其他表示形式的数相乘时使用Booth编码，这点尤其值得注意。当两个相乘的数位宽不相等时，在设计中选择使用位宽较小者进行Booth编码，也就是对应上面的“A”，这样才能使部分积数量最少。

3 结语

该文简要分析了优化乘法器的两种思路，着重介绍了Booth编码法减少部分积的数量，推导了2基Booth编码及4基Booth编码，综合考虑部分积个数、产生部分积难度两种因素，指出在实现乘法器中优先考虑4基Booth编码的原因，另外阐述了在应用Booth编码时注意的问题。

参考文献

[1] 孙航.Xilinx可编程逻辑器件的高级应用与设计技巧[M].北京：电子工业出版社，2004.

[2] 朱子玉.CPU芯片逻辑设计技术[M].北京：清华大学出版社，2005.