补码的乘法-布斯乘法

发布时间:2024年01月04日

前言

本篇文章讲解如何通过逻辑门的形式来实现补码的乘法操作

布斯乘法

A.D.Booth提出了一种补码相乘算法,可以将符号位与数值位合在一起参与运算,直接得出用补码表示的乘积,且正数和负数同等对待。这种算法被称之为Booth (布斯)乘法
下面有两个变量值 X X X Y Y Y
Y Y Y用二进制表示为
Y = y n ? 1 y n ? 2 … y 2 y 1 y 0 Y = y_{n-1}y_{n-2}\ldots y_2y_1y_0 Y=yn?1?yn?2?y2?y1?y0?
因为Y是用补码表示的,所以Y的值可以通过下面的公式计算:
Y = ? y n ? 1 2 n ? 1 + y n ? 2 2 n ? 2 + … + y 1 2 1 + y 0 2 0 = ? y n ? 1 2 n ? 1 + ∑ i = 0 n ? 2 y i 2 i = ? y n ? 1 2 n ? 1 + y n ? 2 2 n ? 1 ? y n ? 2 2 n ? 2 + … + y 1 2 2 ? y 1 2 1 + y 0 2 1 ? y 0 = ( y n ? 2 ? y n ? 1 ) 2 n ? 1 + ( y n ? 3 ? y n ? 2 ) 2 n ? 2 + … + ( y 0 ? y 1 ) 2 1 + ( 0 ? y 0 ) = ∑ i = 0 n ? 1 ( y i ? 1 ? y i ) 2 i \begin{aligned} Y &= -y_{n-1}2^{n-1} + y_{n-2}2^{n-2} + \ldots+y_12^1+ y_02^0\\ &=-y_{n-1}2^{n-1} + \sum_{i=0}^{n-2}y_i2^i \\ &=-y_{n-1}2^{n-1} + y_{n-2}2^{n-1}-y_{n-2}2^{n-2}+\ldots+y_12^{2}-y_{1}2^{1}+y_02^{1}-y_0\\ &=(y_{n-2}-y_{n-1})2^{n-1}+(y_{n-3}-y_{n-2})2^{n-2}+\ldots+(y_0-y_1)2^1+(0-y_0)\\ &=\sum_{i=0}^{n-1}(y_{i-1}-y_{i})2^{i} \end{aligned} Y?=?yn?1?2n?1+yn?2?2n?2++y1?21+y0?20=?yn?1?2n?1+i=0n?2?yi?2i=?yn?1?2n?1+yn?2?2n?1?yn?2?2n?2++y1?22?y1?21+y0?21?y0?=(yn?2??yn?1?)2n?1+(yn?3??yn?2?)2n?2++(y0??y1?)21+(0?y0?)=i=0n?1?(yi?1??yi?)2i?
因为 X X X Y Y Y都是n位数据,所以 X × Y X\times Y X×Y可能占用2n位。
我们先假设 Y Y Y乘以 2 ? n 2^{-n} 2?n
X × Y × 2 ? n = X × ∑ i = 0 n ? 1 ( y i ? 1 ? y i ) 2 i × 2 ? n = X × ∑ i = 0 n ? 1 ( y i ? 1 ? y i ) 2 ? ( n ? i ) = P n \begin{aligned} X\times Y\times2^{-n} &= X\times \sum_{i=0}^{n-1}(y_{i-1}-y_{i})2^{i}\times2^{-n}\\ &=X\times \sum_{i=0}^{n-1}(y_{i-1}-y_{i})2^{-(n-i)}\\ &=P_{n} \end{aligned} X×Y×2?n?=X×i=0n?1?(yi?1??yi?)2i×2?n=X×i=0n?1?(yi?1??yi?)2?(n?i)=Pn??
即然我们假设这个值等于 P n P_{n} Pn?了,那么我们可以推测 P n ? 1 P_{n-1} Pn?1?的值
P n ? 1 = X × ∑ i = 0 n ? 2 ( y i ? 1 ? y i ) 2 ? ( n ? 1 ? i ) P_{n-1} = X\times \sum_{i=0}^{n-2}(y_{i-1}-y_{i})2^{-(n-1-i)} Pn?1?=X×i=0n?2?(yi?1??yi?)2?(n?1?i)
然后我们能得出两个挨着的一般性公式 P i P_{i} Pi? P i ? 1 P_{i-1} Pi?1?的关系
P i = 2 ? 1 ( P i ? 1 + ( y i ? 2 ? y i ? 1 ) X ) , i = 1 , 2 … , n ? 1 P_{i} = 2^{-1}(P_{i-1} + (y_{i-2}-y_{i-1})X),i = 1,2\ldots,n-1 Pi?=2?1(Pi?1?+(yi?2??yi?1?)X)i=1,2,n?1

根据上面的公式,我们发现,可以先计算 P 0 P_{0} P0?,然后通过 P 0 P_{0} P0?计算 P 1 P_{1} P1?,然后通过 P 1 P_{1} P1?计算 P 2 P_{2} P2?,然后就可以依次往后计算出 P n P_{n} Pn?,如果计算 X × Y X\times Y X×Y,我们可以按照下面的步骤进行:

  1. 假设 P 0 = 0 P_{0}=0 P0?=0,假设 y ? 1 = 0 y_{-1}=0 y?1?=0
  2. 从y的最右侧位开始,先比较 y 0 y_0 y0? y ? 1 y_{-1} y?1?
  3. 如果 y 0 y ? 1 = = 00 y_0y_{-1}==00 y0?y?1?==00 P 0 P_0 P0?右移一位
  4. 如果 y 0 y ? 1 = = 01 y_0y_{-1}==01 y0?y?1?==01 P 0 + X P_0+X P0?+X然后,右移一位
  5. 如果 y 0 y ? 1 = = 10 y_0y_{-1}==10 y0?y?1?==10 P 0 ? X P_0-X P0??X然后,右移一位
  6. 如果 y 0 y ? 1 = = 11 y_0y_{-1}==11 y0?y?1?==11 P 0 P_0 P0?右移一位
  7. 右移后得到 P 1 P_{1} P1?,比较位向左移动一位,如果没有超过最大位,跳转到2
  8. 如果超过最高位了, P n P_n Pn?就是结果

注意:在此之前,其实 P n = X × Y × 2 ? n P_n =X\times Y\times2^{-n} Pn?=X×Y×2?n,并且我们发现在上述步骤中结果一直在向右移,所以,我们可以把初始结果放在高n位上,这样向右移动不会丢失数据,并且也相当于乘了 2 n 2^{n} 2n,结果刚好是想要的值。

通过上面的步骤可以看出,乘法被分解成一系列加减和移位操作的顺序集合,我们之前已经实现了串行进位加法器并行进位加法器,并且实现了一个桶形移位器

下面看一个实际的例子:
假设X = 100,Y = 120;
用二进制表示为X = 01100100,Y= 01111000,即然8位能够放下数据,为了书写方便,我们假设XY都为8位,结果为16位数据,假设结果为R = 0;

  1. 比较 y 0 y_0 y0? y ? 1 y_{-1} y?1?, y 0 y ? 1 = 00 y_0y_{-1}=00 y0?y?1?=00,R=00000000 00000000,右移后值不变
  2. 比较 y 1 y_1 y1? y 0 y_0 y0?, y 1 y 0 = 00 y_1y_0=00 y1?y0?=00,R=00000000 00000000,右移后值不变
  3. 比较 y 2 y_2 y2? y 1 y_1 y1?, y 2 y 1 = 00 y_2y_1=00 y2?y1?=00,R=00000000 00000000,右移后值不变
  4. 比较 y 3 y_3 y3? y 2 y_2 y2?, y 3 y 2 = 10 y_3y_2=10 y3?y2?=10,R=00000000 00000000,R-X后右移
    R-X = R(高位) + (~X) + 1= 10011100 00000000,右移后为11001110 00000000
    注意:是在R的高位上操作,并且右移为算数右移,补符号位
  5. 比较 y 4 y_4 y4? y 3 y_3 y3?, y 4 y 3 = 11 y_4y_3=11 y4?y3?=11,R=11001110 00000000,右移后为11100111 00000000
  6. 比较 y 5 y_5 y5? y 4 y_4 y4?, y 5 y 4 = 11 y_5y_4=11 y5?y4?=11,R=11100111 00000000,右移后为11110011 10000000
  7. 比较 y 6 y_6 y6? y 5 y_5 y5?, y 6 y 5 = 11 y_6y_5=11 y6?y5?=11,R=11110011 10000000,右移后为11111001 11000000
  8. 比较 y 7 y_7 y7? y 6 y_6 y6?, y 7 y 6 = 01 y_7y_6=01 y7?y6?=01,R=11111001 11000000,R+X后右移,R+X = 01011101 11000000, 右移后为00101110 11100000

计算完成,00101110 11100000 = 12000,与结果相符

布斯乘法在电路的实现

我们在前面讲述算法执行过程的时候,把结果数据放在了高n位,这样有两个好处:

  • 正好抵消了之前公式中乘的 2 ? n 2^{-n} 2?n
  • 在算法执行过程中结果数据总要右移,把结果数据放在高位,右移的时候不会丢失数据

并且每一步我们都会从右往左比较Y的位值,相当于我们每步都右移Y,然后比较Y的最低两位,但是第一步的时候我们还有一个 y ? 1 = 0 y_{-1}=0 y?1?=0,所以我们可以这么设计:

  • 假设Y有n位,我们设计的电路有n+1根线,Y的值放在 n ~ 1 n~1 n1位, y ? 1 y_{-1} y?1?的值放在0位
  • 这样,每一步的比较操作我们只需要右移电路一位,然后比较最低的两位值即可

即然结果数据和Y的值都右移,并且每步骤都右移1位,那么我们可以设计一个通用的电路:

  • 假设Y有n位,我们设计的电路有2n+1位,数据结果保存到 2 n ~ n + 1 2n~n+1 2nn+1位,Y的值放在 n ~ 1 n~1 n1位, y ? 1 y_{-1} y?1?的值放在0位
  • 最终的结果就是高2n位的数据

下面给出电路图:
在这里插入图片描述

图中表示的是32位的布斯乘法电路图,电路的执行步骤如下:

  • 我们假设乘积寄存器P+乘数寄存器Y+最右边保存 y ? 1 y_{-1} y?1?的值统称为R。
  • 默认乘积寄存器P的值为0,最右边保存 y ? 1 y_{-1} y?1?的值为0,乘数寄存器Y的值和被乘数寄存器X的值被输入,计数器为0,时钟用来增加计数器的值
  • 每一步时钟,检查R的第两位,根据值的不同执行不同的电路逻辑
    • 00或者11,R右移,执行下一步
    • 01,执行加法操作,结果保存到乘积寄存器P,R右移,执行下一步
    • 10,执行减法操作,结果保存到乘积寄存器P,R右移,执行下一步
  • 计数器等于32,输出结果乘积寄存器P+乘数寄存器Y,结束

算术一位右移

虽然我们实现了桶形移位器,但是在当前的乘法运算中,有点大材小用,如果我们仅仅实现一个一位的右移操作,电路将变得很简单,我们直接给出C语言描述git地址

/**
 * 单位右移操作,为了实现布斯乘法专门定义的右移电路,支持129位
 * in_1:128~65位,用于存放乘积寄存器P
 * in_2:64~1位,用于存放乘数寄存器Y
 * in_1:0位,用于存放临时比较的值
 * isLogic:是否是逻辑右移
 */
extern void alu_shift_right_1(long* in_1,long*  in_2,long*  in_3,long isLogic);

void alu_shift_right_1(long* in_1,long* in_2,long*  in_3,long isLogic)
{
    // 先赋值最低位
    *in_3 = (*in_2)&1;
    // in_1的最低位给in_2的最高位
    unsigned long a = *in_2;
    *in_2 = (a>>1)| ((*in_1)&1)<<(sizeof(long)*8-1);
    // in_1右移1位
    if(isLogic)
    {
        unsigned long b = *in_1;
        *in_1 = b>>1;
    }
    else
    {
        *in_1 = (*in_1)>>1;
    }
}

布斯乘法的C语言描述

最后给出布斯乘法的C语言描述,我们把结果存在两个long类型的数值中,out_1保存高位,out_2保存低位。git地址

/**
 * 使用布斯乘法算法计算两个数相乘
 * in_1:输入1
 * in_2:输入2
 * out_1:输出高位
 * out_2:输出低位
 */
extern void alu_booth_times(long in_1, long in_2,long* out_1, long* out_2);

void alu_booth_times(long in_1, long in_2,long* out_1, long* out_2)
{
    // y-1位,默认为0
    long lastBit = 0;
    // 保存结果的高位
    *out_1 = 0;
    long c = 0;
    // 计数器
    for(int i = 0; i<sizeof(long)*8;i++)
    {
        long temp = in_2&1;
        if(temp == lastBit)// 直接右移
        {
            alu_shift_right_1(out_1,&in_2,&lastBit,0);
        }
        else if(lastBit==1)// 01,相加,然后右移
        {
            c = 0;
            *out_1 = alu_add_bcla_64(*out_1,in_1,sizeof(long)*8,&c);
            alu_shift_right_1(out_1,&in_2,&lastBit,0);
        }
        else// 10,相减,然后右移
        {
            *out_1 = alu_sub_bcla_64(*out_1,in_1,sizeof(long)*8);
            alu_shift_right_1(out_1,&in_2,&lastBit,0);
        }
    }
    *out_2 = in_2;
}
文章来源:https://blog.csdn.net/b1049112625/article/details/135386431
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。