来源：电子设计应用  作者：同济大学微电子中心 赵忠民
　
摘要：对Booth算法产生的部分积重新合理分组，采用CSA和4-2压缩器的混合电路结构，对传统的Wallace树型乘法器进行改进，提出一种高速的树型乘法器。该结构与传统Wallace树型乘法器相比，具有更小的延时，更规整的布局和更规则的布线，使其易于VLSI实现。

关键词：Booth算法；Wallace树；CSA；4-2压缩器；树型乘法器

引言

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

基４Booth算法与乘法器的一般结构

乘法器工作的基本原理是首先生成部分积，再将这些部分积相加得到乘积。在目前的乘法器设计中，基４Booth算法是部分积生成过程中普遍采用的算法。对于N位有符号数乘法A×B来说，常规的乘法运算会产生N个部分积。如果对乘数B进行基４Booth编码，每次需考虑3位：相邻高位、本位和相邻低位，编码后产生部分积的个数可以减少到[(N+1)/2] （[X]取值为不大于X的整数），确定运算量0、±1A、±2A。对于2A的实现，只需要将A左移一位。因此，对于符号数乘法而言，基4 Booth算法既方便又快捷。而对于无符号数来说，只需对其高位作0扩展，而其他处理方法相同。虽然扩展后可能导致部分积的个数比有符号数乘法多1，但是这种算法很好地保证了硬件上的一致性，有利于实现。对于32位乘法来说，结合指令集的设计，通常情况下需要相加的部分积不超过18个。

对部分积相加，可以采用不同的加法器阵列结构。而不同的阵列结构将直接影响完成一次乘法所需要的时间，因此，加法器阵列结构是决定乘法器性能的重要因素。重复阵列（Iterative Array，简称IA）和Wallace树型结构是最为典型的两种加法器阵列结构。IA结构规整，易于版图实现，但速度最慢且面积大；理论上，Wallace树型结构是进行乘法操作最快的加法器阵列结构，但传统的Wallace树型结构电路互连复杂，版图实现困难。为了解决这个问题，人们推出了一些连接关系较为简单的树型结构，例如ZM树和OS树。它们都是将IA树分为几段，每段称之为子树，子树内部连接采用IA结构，而子树间采用树型连接，以此来降低连接复杂度，但是这种方法降低了部分积相加的速度。

在对树型结构进行改进的同时，设计者们也尝试了对加法阵列中基本加法单元的改进。Wallace最早提出的方案中，是以CSA（进位保留加法器）作为基本单元构建加法阵列的。其基本方法是：通过CSA部件，以3∶2的压缩比对部分积进行逐级压缩，直到最后只产生两个输出为止，再通过进位传递加法器对产生的这两个伪和与局部进位相加得出真正的结果。此后，Dadda提出了一种新的加法单元，称为“（j，k）计数器”，它有j个输入和k个输出，其中j≦2k。经过研究和实践，人们发现4-2压缩器（实际上是5-3计数器）具有较好的平衡性和对称性，用其作为基本加法单元构成的乘法器在总体性能上具有一定的优势，因此4-2压缩器也就成为了目前乘法器中较多采用的加法单元。

图1中列举了乘法器中几种加法器阵列的结构，它们都采用4-2压缩器作为基本加法单元来完成对18个部分积的加和。图中每个矩形代表一组4-2压缩器，带箭头的线段表示部分积与中间结果。

（a）IA阵列 （b）Wallace树

（c）一阶OS树 （d）参考文献[5]中的树型结构

图1 对18个部分积相加所采用的加法阵列结构

如前所述，图1（a）中的IA阵列，结构最为规整，但很明显，其延时级数大大多于其他结构。（b）是Wallace树结构，由于采用4-2压缩器作为唯一的加法单元，而18不能被4整除，因此在对18个部分积的求和过程中，必然要对其中的两个部分积做额外处理。Wallace树采取的方法是：先将16个部分积通过三级4-2压缩器后产生两个结果，然后与剩下的两个部分积一起再进行一级4-2压缩。（c）中的一阶OS树结构也采用了类似的方法，只是在处理的先后顺序上有所改变。这两种结构，都破坏了树的对称性，造成路径的不等长，因此浪费了硬件资源，且增加了布局布线的复杂度。（d）是参考文献[5]中提出的一种经过改进的树型结构，其求和过程是：将18个部分积分为3组，先对每组中的6个部分积求和，各产生两个中间结果，再把这6个中间结果相加。由于对每组中的6个部分积求和，可以采用相同结构的两组4-2压缩器，这样就很好地降低了布局布线的复杂度。其缺点在于：用4-2压缩器对6个中间结果进行相加的过程中，仍不能避免路径不平衡的问题，因此，还是使关键路径的延时有不必要的增加。

CSA和4-2