对BOOTH乘法器的理解

矫情吗；* 2022-07-18 00:15 160阅读 0赞

### reference : http://chengcheng198897.blog.163.com/blog/static/198067355201263033911246/    ###

booth乘法器是一种位操作乘法器，与传统乘法器不同的是直接操作位。传统乘法器依靠加法，不断累加，在这里就不说了。

\------------------------------------------------------------------------------------------------------------------------------------------------------------

1951 年,A.D Booth 在其论文“A Signed binary multiplication technique”中提出一种快  
速乘法算法, Booth 算法,  
即  
是为了解决有符号乘法运算中复杂的符号修正问题而提出一种  
乘法算法。乘法器中若乘数为有符号数,扩展其最高位;若是无符号数,则做一位 0 扩展。  
Booth 算法的基础基于二进制数加法的特性,其基本思想为当 x 乘以一个二进制数时可  
以将乘数中连续的 1 序列变换为(2i-2j),其中 i>j,然后利用二进制数乘法的特性等于将 2i  
乘以 x 向左移 i 位,只需一个加法器和一个移位寄存器便可实现该段数据的(2i-2j)乘以 x  
乘法运算,i>j,从而有效减少总体需要的加法运算次数。

**假设乘数和被乘数均为 n 位,那么 Booth 算法的具体执行过程以下六个步骤:  
(1) 设置一个 2n+1 位的 p 空间,并将初始化为 0;  
(2) 将乘数填入 p\[n:1\]中;  
(3) 从 p 空间的最低位依次开始向左扫描,每次扫描两位,并判断所扫描的两位二进制  
数为表 1 中的何种情况;**

booth乘法器有个重要的加码运算。来看一下

![BOOTH乘法器——看到别人讲解的booth乘法器，可以作为booth，借鉴下 - 成 - 学海泛舟][BOOTH_booth_booth_ - _ -]

B\[-1\]就是B的零位右边的位，是假想的位。如0010 0 B\[-1\]就是0。

做booth乘法器又引入了p空间。

![BOOTH乘法器——看到别人讲解的booth乘法器，可以作为booth，借鉴下 - 成 - 学海泛舟][BOOTH_booth_booth_ - _ - 1]  
  
  
**(4) 判断 p\[2n\]位,如果是逻辑 0 右移一位补 0,如果是逻辑 1 就右移一位补 1;  
(5) 重复步骤(3) ,循环 n 次;  
(6) 最终 p 空间的 p\[2n:1\]就是乘数和被乘数的乘积。**

上图的左移一位或者右移一位指的是p空间。什么是p空间呢？我们以7（0111）和2（0010）相乘为例。他们位数n均为4位。所以p空间大小为n\*2+1=9。

p空间是如何做乘法运算的呢？

![BOOTH乘法器——看到别人讲解的booth乘法器，可以作为booth，借鉴下 - 成 - 学海泛舟][BOOTH_booth_booth_ - _ - 2]

![BOOTH乘法器——看到别人讲解的booth乘法器，可以作为booth，借鉴下 - 成 - 学海泛舟][BOOTH_booth_booth_ - _ - 3]

reference : http://baike.baidu.com/link?url=FY-ZMR7cood3GgRS2tN8e4n\_43UW7ZwTuxpVIv4VcIP-4NSvPFuKfYg7Has4M-nhIQkU\_8bWaKXZBNhX1StaMa

例1.38　设 [被乘数][Link 1]M=0111(7),乘数Q=1101（－3），相乘过程如下：

A 　Q　Q－1

0000　1101　0　初始值

1001　1101　0　A=A－M

1100　1110　1　右移（第1次循环）

0011　1110　1　A=A+M

0001　1111　0　右移（第2次循环）

1010　1111　0　A=A－M

1101　0111　1　右移（第3次循环）

1110　1011　1　右移（第4次循环）

乘积=11101011=(-21)( [十进制][Link 2])

其中的移位是算数移位.

reference : http://wenku.baidu.com/link?url=YqTY7l5TbcQipZ18sGkdbiiWzpB9Bti4TXC-NvH1LO8ntqvFn72HS45JBHreQexXVemm4iMzr9BwFa28pMDRPvYw1ggknfYRYyMyHdEgZRW

module booth( start\_sig, a, b, done\_sig , product)

wire \[1:0\] start\_sig;

wire \[7:0\] a;

wire \[7:0\] b;

wire \[15:0\] product;

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
reg\[3:0\] i;  
reg\[7:0\] ra;  
reg\[7:0\] rs;  
reg\[16:0\] rp;  
reg\[3:0\] x;  
reg isdone;  
always @(posedge clk or negedge rst\_n)  
if(!rst\_n)  
begin  
i<=4'd0;  
ra<=8'd0;  
rs<=8'd0;  
rp<=17'd0;  
x<=4'd0;  
isdone<=1'b0;  
end  
else if(start\_sig)  
case(i)  
0:  
begin  
ra<=a;  
rs<=(~a+1);  
rp<=\{8'd0,b,1'b0\};  
i<=i+1;  
end  
1:  
if(x==8)  
begin  
x<=4'd0;  
i<=i+2;  
end  
else if(rp\[1:0\]==2'b01)  
begin  
rp<=\{rp\[16:9\]+ra,rp\[8:0\]\};  
i<=i+1;  
end  
else if(rp\[1:0\]==2'b10)  
begin  
rp<=\{rp\[16:9\]+rs,rp\[8:0\]\};  
i<=i+1;  
end  
else  
i<=i+1;  
2:  
begin  
rp<=\{rp\[16\],rp\[16:1\]\};  
x<=x+1;  
i<=i-1;  
end  
3:  
begin  
isdone<=1'b1;  
i<=i+1;  
end  
4:  
begin  
isdone<=1'b0;  
i<=4'd0;  
end  
endcase  
assign product=rp\[16:1\];  
assign done\_sig=isdone;

endmodule

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

代码如下：

module product
    (
    input CLK,
    input RSTn, input Start_Sig,
    input [7:0]A,
    input [7:0]B, output Done_Sig,
    output [15:0]Product, output [7:0]SQ_a,
    output [7:0]SQ_s,
    output [16:0]SQ_p
    ); /*************************/ reg [3:0]i;
    reg [7:0]a; // a的寄存器
    reg [7:0]s; // a的补码加1 a非
    reg [16:0]p; // p空间存储器
    reg [3:0]X;   //操作次数
    reg isDone; always @ ( posedge CLK or negedge RSTn )
     if( !RSTn )
      begin
       
       i <= 4'd0;
       a <= 8'd0;
       s <= 8'd0;
       p <= 17'd0;
       X <= 4'd0;
       isDone <= 1'b0;
      end
     else if( Start_Sig )
      case( i )
       
       0:
        begin a <= A; s <= ( ~A + 1'b1 ); p <= { 8'd0 , B , 1'b0 }; i <= i + 1'b1; end
       
       1:
        if( X == 8 ) begin X <= 4'd0; i <= i + 4'd2; end
        else if( p[1:0] == 2'b01 ) begin p <= { p[16:9] + a , p[8:0] }; i <= i + 1'b1; end
        else if( p[1:0] == 2'b10 ) begin p <= { p[16:9] + s , p[8:0] }; i <= i + 1'b1; end
        else i <= i + 1'b1;
       
       2:
        begin p <= { p[16] , p[16:1] }; X <= X + 1'b1; i <= i - 1'b1; end
       
       3:
        begin isDone <= 1'b1; i <= i + 1'b1; end
       
       4:
        begin isDone <= 1'b0; i <= 4'd0; end
       
      endcase /*************************/ assign Done_Sig = isDone;
    assign Product = p[16:1]; /*************************/ assign SQ_a = a;
    assign SQ_s = s;
    assign SQ_p = p;
    /**************************/
    endmodule

[BOOTH_booth_booth_ - _ -]: http://img1.ph.126.net/4paL3QnpuDdOq7JQ7_sKag==/6597251186075252001.jpg
[BOOTH_booth_booth_ - _ - 1]: http://img3.ph.126.net/qhmWQ3NA67vvEd5GEY5YJw==/6597405117703006393.jpg
[BOOTH_booth_booth_ - _ - 2]: http://img7.ph.126.net/1jqwZflmqKmoekar9hnXWA==/6597141234912478097.jpg
[BOOTH_booth_booth_ - _ - 3]: http://img5.ph.126.net/zkHO0lrD4UOQ7eS0ZSqwuA==/1079175060726428765.jpg
[Link 1]: http://baike.baidu.com/view/2106226.htm
[Link 2]: http://baike.baidu.com/view/359301.htm