设计快速乘法器，通常要重点处理三个关键问题：减少部分积产生、加速部分积累加和提高最终多位数相加速度。例如，用传统的乘法运算模式处理16位×16位所用的时间为t_总=t_{产生16行部分积}+_{t16行部分积累加成最终积}。若运用改进波兹(Booth)算法以后，可以减少部分积的产生。而基于改进波兹算法的乘法器设计，在后续部分积相加的过程中，无论采用哪种处理方式，如华莱氏树结构等，都不可避免地要解决符号位扩展阵列问题。本文提出了一种新的基于改进波兹算法的逻辑设计" title="逻辑设计">逻辑设计来处理符号位部分：通过简单地运用‘或门’、‘异或门’来优化乘法器的局部速度和面积两方面的性能。
1 改进波兹算法
　　改进波兹算法MBA(Modified Booth′s Algorithm)^[1]是建立在波兹算法^[2]基础上的。对乘数三位一组的划分包含了一个重叠位，每一组的三位按表1编码，并形成一个部分积。由此而产生5个系数：±1、±2、0。在部分积的累加过程中，减法也就是补码相加。经过编码以后，通过高低电平信号对符号位进行指示。n位乘数乘以m位被乘数会产生n+m位积。因此累加过程中由于对负数补码的相加，每个部分积必须把符号位扩展到最高位(第n+m-1位)，以此来保证后续运算的正确性。若以8位X×8位Y为例，产生的部分积阵列如图1所示。由于部分积含有±2X，因此其字长为9位，即A0～A8，第10位A9为符号位。在做减法补码运算时，其符号位应扩充至最高位(第15位)，再加上相应每组最高位，即y1。B、C、D、E也按此规律产生。8位×8位最终产生16位积。

　　观察图1可以发现在部分积阵列中，有相当大的一部分是符号位扩展阵列，并且随着两个相乘数的位数成倍地增加，符号位扩展阵列也不断扩大，因此考虑对这个特殊阵列的处理就相当有价值。
2 ‘或’-‘异或’快速算法处理符号位部分
　　对符号位扩展阵列单独处理，逻辑设计则按照下面顺序来进行：
　　(1)若乘数有偶数个位即2k(k=1,2……n)，那么就会产生k+1行部分积。在部分积中，有k行符号扩展位，符号扩展位阵列的最大宽度为2k-1个位；若乘数有奇数个位，即2k+1(k=0,1,2......n)，那么就会产生k+1行部分积。在部分积中，有k行符号扩展位，符号扩展位阵列的最大宽度为2k个位。
　　(2) 若编码结果为负数，那么产生该行的所有符号位都是1，否则都为0。
　　(3) 除了第0列，对符号位扩展阵列每一列进行奇偶划分，即第1、3、5……为奇数列，第2、4、6……为偶数列。
　　(4) 符号位扩展阵列和的偶数位与该列上(从上至下)最后一位相关联。该阵列和的奇数位等于该列上所涉及位的‘或’运算，偶数位等于与该位相关联的那位与低一位的奇数列的和位的‘异或’运算，第0位等于第0行的编码产生的符号信号。
　　以8位×8位的例子来说明：r0~r6是符号位阵列累加的和位，s0~s3表示阵列第0行到第3行，如图2所示。

　　当乘数有奇数个位时，符号位扩展阵列排布如图4所示。

　　求证方法类似于偶数位乘数，得到的结论为：
　　r_2i-1=sign[i-1]|…|sign^[1]|sign[0],r_2i-2=sign[i-1]^r_2i-3。
4 算法实现
　　实现这一设计很容易：根据设计规则，r₃、r₅……r_2i-1
　　位全部由‘或门’来实现，r₂、r₄、r₆……r_2i-2位全部由‘异或门’来实现，r₀、r₁用编码产生的符号指示信号表示。把8位×8位的例子用‘或门’和‘异或门’实现如图5所示，图中用了2个‘或门’和3个‘异或门’。

5 性能评估
　　该设计方案的性能评价从如下两方面考虑：
　　(1)从速度和面积两方面性能考虑，符号位扩展阵列作为一个模块单独设计。
　　首先，把原本符号位之间的累加转换成用‘或’-‘异或’进行处理，既大大降低了门的使用数量，从而减小了该硬件乘法器模块所占的面积，也避免了累加过程中的进位等待问题而提高了速度。如果不对符号位扩展阵列单独处理，而是在后续处理的过程中选择特殊压缩器来进一步解决累加的速度问题，其面积上的增加是显而易见的。
　　(2)考虑该设计结果对后续部分积处理的影响。
　　因为通过符号位扩展阵列的特性可以知道，和的位数就是以第0行部分积中的符号扩展位的位数，不产生多余的累加行。因此阵列最终产生一行和位，与现在所知的其他处理方法相比，没有多余的位与除去符号位扩展阵列的部分积进行相加。并且该行和位也不作为额外的累加行介入部分积累加。在相关文献中，对符号位扩展阵列处理有使用预求和并加上修正位的方法：先假设所有n位×n位符号位扩展阵列中每个位都是1，预算出最后的和，然后根据符号指示信号对相应行加1，并将这个1作为符号修正位^[3]。也有根据等式，对符号扩展部分做相应恒等变形处理的方法^[4]。这些方法除了产生与符号位扩展阵列宽度相同的一行位以外，还有额外的位要累加到部分积上。以8位×8位乘法用三种" title="三种">三种不同方案处理符号位部分所得部分积如图6所示。图中r₀~r₆作为符号位阵列累加的和位，作为符号修正位。