设计快速乘法器,通常要重点处理三个关键问题:减少部分积产生、加速部分积累加和提高最终多位数相加速度。例如,用传统的乘法运算模式处理16位×16位所用的时间为t总=t产生16行部分积+t16行部分积累加成最终积。若运用改进波兹(Booth)算法以后,可以减少部分积的产生。而基于改进波兹算法的乘法器设计,在后续部分积相加的过程中,无论采用哪种处理方式,如华莱氏树结构等,都不可避免地要解决符号位扩展阵列问题。本文提出了一种新的基于改进波兹算法的逻辑设计来处理符号位部分:通过简单地运用‘或门’、‘异或门’来优化乘法器的局部速度和面积两方面的性能。
改进波兹算法
改进波兹算法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)若乘数有偶数个位即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所示。
改进波兹算法
改进波兹算法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)若乘数有偶数个位即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所示。