Loading [MathJax]/jax/input/TeX/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >八位“Booth二位乘算法”乘法器

八位“Booth二位乘算法”乘法器

作者头像
huofo
发布于 2022-03-17 00:25:47
发布于 2022-03-17 00:25:47
1.1K00
代码可运行
举报
文章被收录于专栏:huofo's bloghuofo's blog
运行总次数:0
代码可运行

目录

八位“Booth二位乘算法”乘法器

原理

补码乘法器

之前介绍了几篇无符号乘法器或加法器的写法,当然,稍作修改也就可以改成符合有符号数的乘法器或加法器。

但是呢,我们之前写的乘法器或加法器,其实都是默认是正数来写的,而且是以正数的原码来写的,所以上面说稍作修改也就可以成为有符号数的乘法器或加法器,其实就是对我们以为的原码进行取补码,再进行乘法或加法的运算。

随着计算机硬件部件的升级,处理器技术的发展,现代处理器中的定点数(小数点位置固定)都是按照补码形式来存储的。

所以在之前写的无符号加法器中,只要利用:

\[X_补+Y_补=[X+Y]_补 \]

就可以轻易将原先的加法器改写成有符号加法器——只要对结果再取一次补码即可。

但是乘法器呢?稍作学习可以知道,补码的乘法是这样的:

\[X*Y_补=[X*Y]_补 \]

我们再考虑一下之前所说的:在现代处理器中的定点数都是按照补码形式来存储的

所以我们要想得到两个数的乘法结果,首先应该知道被乘数的原码和补码,再对最终结果取补码,即可得到我们期望的乘法结果。

那么如何求“X*Y补”呢?在处理器中,一个二进制数Y补形如y7y6y5y4y3y2y1y0,也就是表示一个数的补码,那么它的原码是多少呢?

补码的计算方法,除了“首位不变,余位取反再加一”的方式,还有一种就是“用溢出条件来减这个数”,在我们之前第一节课说二进制的时候,以钟表为例——“十二进制”,得到结论——“4-8的补码”。

我们用第二种取补码的方式:-8的补码=12-8=4(这里没有考虑符号问题,只是求了补码的值)

所以考虑一下符号的话,-8的补码=8-12=-4

同理:

十进制下,-4的补码=4-10=-6

二进制下,-101补码=1101补码=101-1000=-011=1011

这样解决求补码的方式在接下来的计算方面就更方便了,至于正数嘛,不变就好了。

回到上面的问题,一个二进制数Y补形如y7y6y5y4y3y2y1y0它的原码是多少呢?根据:

\[[X_补]_补=X \]

Y补的原码Y应该为:

\[Y=(y_7*2^7+y_6*2^6+y_5*2^5+……+y_0*2^0)-1*2^8 \]

稍微化简一下:

\[Y=-y_7*2^7+(y_6*2^6+y_5*2^5+……+y_0*2^0) \]

所以我们如果想求X*Y,可以先求其补码:

\[[X*Y]_补=[X*(-y_7*2^7)+X*(y_6*2^6+y_5*2^5+……+y_0*2^0)]_补 \]

根据补码加法“X补+Y补=[X+Y]补”再稍微化简一下:

\[[X*Y]_补=-y_7*[X*2^7]_补+y_6*[X*2^6]_补+y_5*[X*2^5]_补+……+y_0*[X*2^0]_补 \]

再引入一个定理:

\[[X*2^n]_补=X_补*2^n \]

所以上式又可以换一种写法:

\[[X*Y]_补=X_补*(-y_7*2^7+(y_6*2^6+y_5*2^5+……+y_0*2^0))=Y*X_补 \]

哦这不就是上面介绍过的补码乘法嘛:

\[[X*Y]_补=Y*X_补=X*Y_补 \]

如果令一个数Y1补=y6y6y5y4y3y2y1y0,去掉了首位,那么上式是不是可以理解为:

\[[X*Y]_补=X_补*Y1_补-y_7*X_补*2^7 \]

其中的Y1补不就刚好是Y补的后7位嘛?也就是说一个乘法可以分为两部分理解:首位的乘法和其他位的乘法。首位的乘法产生的部分积符号是减,其他位的部分积符号为加

经过上面的推导大家应该会对补码乘法的原理有了一定的概念,我们来把它写成竖式的形式,以(-6)x(-7)为例,原码乘应该是1110x1111,在计算机中是以补码的形式存储,所以补码乘是1010x1001,代入公式,令X补=1010Y补=1001,其运算过程如下:

这里可能有一些迷惑的是:为什么第一步运算得到的结果是11111010?为什么要在前面填充1111

这也就是所谓的符号填充,我们之前的设计中都没有涉及到符号位,所以默认都是填充0,现在遇到了负数问题,也就需要填充符号了,但是这样看起来是不是一点都觉得很奇怪?如果没办法理解的话,我建议你可以尝试对它求补码,看看是不是可以保持首位符号位不变,余位取反加一。惊叹于设计师的机智。

补码乘法器的原理讲明白了,具体电路实现的话,大家可以尝试一下,本节重点不在于此。

Booth一位乘

在上面已经讨论了补码乘法器的原理,那么什么是Booth乘法器呢?Booth乘法器是由英国的Booth夫妇提出的,并没有什么特殊含义,所以我们直接快进到内容。

经过补码乘法器的推导:

\[[X*Y]_补=X_补*(-y_7*2^7+(y_6*2^6+y_5*2^5+……+y_0*2^0)) \]

参考中学数学:

\[2^n=2*2^{n-1} \]

其核心计算思想是括号里的形式,也就是Y补的原码Y所以我们对括号里的内容再进行分解合并,也就是对Y分解合并。先分解:

\[Y=-y_7*2^7+((2-1)y_6*2^6+(2-1)y_5*2^5+……+(2-1)y_0*2^0) \]

这样应该挺直观了吧:

\[Y=-y_7*2^7+(y_6*2^7-y_6*2^6)+(y_5*2^6-y_5*2^5)+……+(y_0*2^1-y_0*2^0) \]

再合并:

\[Y=(y_6-y_7)*2^7+(y_5-y_6)*2^6+(y_4-y_5)*2^5+……+(0-y_0)*2^0 \]

最后有个0-y0的项,看起来有点不合群,所以令:

\[y_{-1}=0 \]

代入上式,即:

\[Y=(y_6-y_7)*2^7+(y_5-y_6)*2^6+(y_4-y_5)*2^5+……+(y_{-1}-y_0)*2^0 \]

这也就是Booth一位乘算法的原理。其优点就在于不用再像补码乘法器那样,不需要专门对最后一次部分积采用补码减法

根据上式,还可以列出Booth一位乘的规则:

y(i-1)

y(i)

y(i-1) - y(i)

操作

0

0

0

加0

0

1

-1

减X补

1

0

1

加X补

1

1

0

加0

再举个例子来计算,仍以(-6)x(-7)为例,补码乘是1010x1001,列出竖式:

可是这里为什么还是有减法呢?和常规的补码乘法器相比,简直是老和尚抹洗头膏,大可不必。甚至由于每次判断两位数字,增大了电路的复杂度,那么为什么booth乘法器如此好用呢?

其实booth一位乘算法并不常用,但是booth二位乘就不一样了,通过增加一定的空间复杂度,将运算周期减为一半!

Booth二位乘

还是根据补码乘法器,我们将Y的表达式再进行变换——先分解:

\[Y=-2*y_7*2^6+y_6*2^6+(y_5*2^6-2*y_5*2^4)+……+y_0*2^0+y_{-1}*2^0 \]

再整合:

\[Y=(y_5+y_6-2*y_7)*2^6+(y_3+y_4-2*y_5)*2^4)+……+(y_{-1}+y_0-2*y_1)*2^0 \]

好了Booth二位乘算法也完事了,类比于Booth一位乘,我们也可以列出Booth二位乘的规则:

y(i-1)

y(i)

y(i+1)

y(i-1) + y(i) - 2*y(i+1)

操作

0

0

0

0

加0

0

1

0

1

加X补

1

0

0

1

加X补

1

1

0

2

加2*X补,即X补<<1

0

0

1

-2

减2*X补,即X补<<1

0

1

1

-1

减X补

1

0

1

-1

减X补

1

1

1

0

加0

再举个例子来计算,仍以(-6)x(-7)为例,补码乘是1010x1001,列出竖式:

运算周期减半了!

好了,那Booth乘法器有没有三位乘呢?可以有,但是三位的时候就会出现加3*X补2*X补可以通过左移一位得到,而3*X补就有点麻烦了,所以不再介绍,至于四位乘、八位乘,想挑战的同学可以挑战一下。

设计思路

减法变加法

首先我们来解决一个问题,如何把减法消除?我们知道,减去一个数,等于加上这个数的相反数;减去一个数,也等于加上这个数的补码。这个过程中的减数也默认是正数,因为正数的补码还是正数,只有正数前面加一个符号再去补码才有用。那么如上面竖式所写,减去一个负补码,就应该等于加上“这个负补码的补码的相反数”,比如上面的补码乘法器竖式,就应该变换成如下形式:

再说明一下吧:11010,就相当于加11010的补码的相反数,即加10110的相反数,即00110

所以booth一位乘算法的示例应该变成这样:

booth二位乘算法的示例应该变成这样:

vivado特性

考虑到上述减法变加法的操作后,容易总结出:减法变加法,其实就是对补码的符号位取反,也就是对减数每一位取反后再加一。

再回读一边上述的理论部分,可能你会发现,在乘法运算中,只用到了补码“负补码”两种概念的数字。而在vivado中(相当于在处理器中),数字默认是以补码形式存储的,即输入的乘数默认就是补码形式,这样只需要再求出“负补码”即可。设X[3:0]表示一个乘数,默认是以补码形式存储,则其“负补码”:

\[X_{负补码}=!X + 1 \]

至于其原码:

\[X_{原码}=(X[3],!X[2:0]) + 1 \]

其实根本用不着。

有了以上知识储备,我们就可以写代码啦~

设计文件

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
//由于实力不够,没能设计成改一个数字变一个规模的程序
`define size 8
module mul_booth_signed(
    input wire [`size - 1 : 0] mul1,mul2,
    input clk,
    input wire [2:0] clk_cnt,//运算节拍,相当于状态机了,8位的话每次运算有4个拍
    output wire [2*`size - 1 : 0] res
    );

    //由于传值默认就是补码,所以只需要再计算“负补码”即可
    wire [`size - 1 : 0] bmul1,bmul2;
    assign bmul1 = (~mul1 + 1'b1) ;
    assign bmul2 = (~mul2 + 1'b1) ;//其实乘数2的负补码也没用到。
	//其实可以把状态机的开始和结束状态都写出来,我懒得写了,同学们可以尝试一下啊~
    parameter   zeroone       =   3'b00,
                twothree      =   3'b001,
                fourfive      =   3'b010,
                sixseven      =   3'b011;
    //y(i-1),y(i),y(i+1)三个数的判断寄存器,由于有多种情况,也可以看成状态机(也可以改写成状态机形式,大家自己试试吧)
    reg [2:0] temp;

    //部分积
    reg [2*`size-1 : 0] A;
	//每个节拍下把相应位置的数据传给temp寄存器
    always @ (posedge clk) begin
        case(clk_cnt)
            zeroone  : temp <= {mul2[1:0],1'b0};
            twothree : temp <= mul2[3:1];
            fourfive : temp <= mul2[5:3];
            sixseven : temp <= mul2[7:5];
            default : temp <= 0;
        endcase
    end
	
    always @(posedge clk) begin
        if (clk_cnt == 3'b100) begin//如果节拍到4就让部分积归0,此时已经完成一次计算了
            A <= 0;
        end else case (temp)
            3'b000,3'b111 :   begin//这些是从高位到低位的判断,别看反了噢
                A <= A + 0;
            end
            3'b001,3'b010 : begin//加法操作使用补码即可,倍数利用左移解决
                A <= A + ({{8{mul1[`size-1]}},mul1} << 2*(clk_cnt-1));
            end
            3'b011 : begin
                A <= A + ({{8{mul1[`size-1]}},mul1} << 2*(clk_cnt-1) + 1);
            end
            3'b100: begin//减法操作利用“负补码”改成加法操作,倍数利用左移解决
                A <= A + ({{8{bmul1[`size-1]}},bmul1} << 2*(clk_cnt-1) + 1);
            end
            3'b101,3'b110 : begin
                A <= A + ({{8{bmul1[`size-1]}},bmul1} << 2*(clk_cnt-1));
            end
            default: A <= 0;
        endcase
    end
	//当节拍到4的时候写入结果寄存器。
    assign res = (clk_cnt == 3'b100) ? A : 0;
endmodule

这是一个八位Booth二位乘算法的乘法器,至于Booth一位和Booth四位的乘法器,大家各自尝试就好。

此外在这个文件当中,我用到了clk_cnt这个寄存器,大家是不是以为我会多用一个模块用来产生clk_cnt的波形?

身为一个懒人,我直接在测试文件里写了吼吼吼~

综合电路

37个元件,36个IO口,318根线

测试文件

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
`timescale 1ns / 1ps
module mul_tb(
    );
    reg [7:0] mul1,mul2;
    wire [15:0] res;
    reg clk;
    wire clk_en;
    reg [2:0] clk_cnt;

    initial begin
        mul1 <= -8'd7;
        mul2 <= -8'd3;
        clk <= 0;
        clk_cnt <= 3'b0;
    end

    always # 10 clk = ~clk;
	//clk_cnt发生器,懒人版
    always @(posedge clk) begin
        clk_cnt <= clk_cnt + 1'b1;
        if (clk_cnt == 3'b100)
            clk_cnt <= 3'b00;
    end
	//每次运算结束后,让乘数变化,以便产生不同的数据用以观察
    assign clk_en = (clk_cnt == 3'b100) ? 1'b1 : 1'b0;
    always @ (posedge clk_en) begin
        mul2 <= mul2 + 1'b1;
    end

    mul_booth_signed try(.mul1(mul1),.mul2(mul2),.res(res),.clk(clk),.clk_cnt(clk_cnt));
endmodule

仿真波形

将其改成有符号十进制数形式显示,可以验证电路设计正确。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-11-13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
五分钟搞不定系列- 1+1=?
甄建勇,高级架构师(某国际大厂),十年以上半导体从业经验。主要研究领域:CPU/GPU/NPU架构与微架构设计。感兴趣领域:经济学、心理学、哲学。
Linux阅码场
2021/12/09
1.3K0
五分钟搞不定系列- 1+1=?
【自己动手画CPU】运算器设计
(2) 熟悉 Logisim 平台基本功能,能在 logisim 中实现多位可控加减法电路。
SarPro
2024/02/20
1.3K0
【自己动手画CPU】运算器设计
计算机组成原理:第二章 运算法和运算器
将数据分为纯整数和纯小数两类,用n+1位表示一个定点数,x_n为符号位,放在最左边,0表示正号,1表示负号。故一个数 x 可以表示为 x = x_nx_{n-1}…x_1x_0
Here_SDUT
2022/08/08
3.9K0
计算机组成原理:第二章 运算法和运算器
P2P接口Booth乘法器设计描述原理代码实现
- 描述 Booth乘法器是一种使用移位实现的乘法器,实现过程如下,对于乘法: 扩展A的位数为n+1位,添加 ,则A变为: 从i=0开始,到i=n-1结束,依次考察 的值,做如下操作:
月见樽
2018/12/12
6880
一个案例搞懂原码、反码、补码,不懂得请看过来
根据冯~诺依曼提出的经典计算机体系结构框架。一台计算机由运算器,控制器,存储器,输入和输出设备组成。其中运算器,只有加法运算器,没有减法运算器(据说一开始是有的,后来由于减法器硬件开销太大,被废了 )
用户7656790
2020/08/13
1.2K0
一个案例搞懂原码、反码、补码,不懂得请看过来
数据的表示和运算
这期本来是想写hashMap的,但是里面哈希和扩容之类的,很多都是位运算,不太熟悉的同学看着会很难受,所以先补充一些计算机组成的知识。
三哥
2020/01/17
9970
数据的表示和运算
通过Java代码来模拟乘法器
cpu中乘法器的执行流程 Java模拟乘法器代码 /** * 32 bit multiplier mock * @param a * @param b
囚兔
2018/02/08
1.1K0
通过Java代码来模拟乘法器
ROM乘法器基本算法单个ROM乘法器分时复用ROM乘法器
基本算法 ROM乘法器的算法比较简单,即使用一个ROM保存乘法的结果,在需要运算的时候直接到相应的地址去查表即可。例如计算两个4位二进制数的乘法a*b,那么需要一个八位输入八位输出的ROM存储计算结果即可,其地址与存储数据的关系为:地址{a,b}(位拼接)存储a*b(例如地址为8'b00010010存储的结果就是0001*0001=8'b00000010) 这种情况下使用的ROM比较大,所以在时序要求不严格的时候可以用时钟换面积,例如对于8位*8位的ROM乘法器,我们将其拆成乘数1高4位,低4位和乘数2高
月见樽
2018/04/27
1.3K0
Quartus II实验二 运算部件实验:并行乘法器「建议收藏」
如果很多操作步骤忘记可以参考链接: Quartus II实验一 运算部件实验:加法器
全栈程序员站长
2022/11/04
1.5K0
Quartus II实验二 运算部件实验:并行乘法器「建议收藏」
补码加、减运算规则「建议收藏」
在计算机中,通常总是用补码完成算术的加减法运算。其规则是:   [X+Y]补= [X]补 + [Y]补 ,[X-Y]补= [X]补 – [Y]补 = [X]补 + [-Y]补
全栈程序员站长
2022/08/02
4.9K0
计算机组成原理实验解析
回忆:偶校验就是为了让数里面1的个数为偶数,做法是所有数位.奇校验就是让数里面1的个数为奇数
用户7267083
2022/12/08
8500
计算机组成原理实验解析
呜呜祖啦滤波器FPGA实现
大侠好,欢迎来到FPGA技术江湖,江湖偌大,相见即是缘分。大侠可以关注FPGA技术江湖,在“闯荡江湖”、"行侠仗义"栏里获取其他感兴趣的资源,或者一起煮酒言欢。
FPGA技术江湖
2020/12/29
7830
呜呜祖啦滤波器FPGA实现
【自己动手画CPU】控制器设计(二)
(2) 熟悉 Logisim 平台基本功能,能在 logisim 中实现多位可控加减法电路。
SarPro
2024/02/20
1.9K0
【自己动手画CPU】控制器设计(二)
如何通过二进制位运算实现加减乘除
众所周知,计算机是通过 bit 位来存储数字的,因为每个 bit 位只能存储 0 或 1,因此,计算机底层的所有计算都是基于二进制来实现的。 那么,仅仅通过位运算,如何才能计算出数字的加减乘除呢?这是一个非常有意思的问题。 本文我们就来详细介绍一下。
用户3147702
2022/06/27
1.2K0
如何通过二进制位运算实现加减乘除
【计组不挂科】计算机组成第二章< 数据的表示&运算方法&运算部件 >习题库(选择题&判断题&填空题)(含答案与解析)
A.指令和数据都以十进制形式存放 B.指令和数据都以二进制形式存放 C.指令以二进制形式存放,数据以十进制形式存放 D.指令以十进制形式存放,数据以二进制形式存放
YY的秘密代码小屋
2024/11/30
2130
『计算机的组成与设计』-计算机的算数运算
要注意: 在执行立即数加法时,imm 是 16 位。而寄存器是 32 位,这就出现转换的问题。在手册中是使用 imm 的符号扩展,也就是将高 16 位采用低 16 位的最高位复制 16 次进行填充。(符号扩展不会改变原数值)。
1ess
2021/10/29
1K0
『计算机的组成与设计』-计算机的算数运算
《计算机组成原理》| 第六章 计算机的运算方法-运算器 知识梳理
             (1111…1) -2n+1 ≤x ≤2n-1 (0111…1)
Twcat_tree
2022/11/30
9700
《计算机组成原理》| 第六章 计算机的运算方法-运算器 知识梳理
流水线乘加树需求设计规划代码实现
需求 计算两个长度为2的幂次方的向量的对应位置相乘相加结果 输入为补码,输出为补码(支持负数) 输入位宽可配置,输入向量的宽度可配置,输出位宽由以上两项决定 设计规划 参数表 参数名称 说明 默认值 DIN_WIDTH 输入位宽 8 DIN_NUM_LOG 输入向量的宽度的log2值(宽度$$2^{DIN_NUM_LOG}$$) 2 注:输出位宽由以上决定,为$$DOUT_WIDTH = DIN_WIDTH \times 2 + DIN_NUM_LOG - 1$$ 端口列表 端
月见樽
2018/04/27
8380
流水线乘加树需求设计规划代码实现
~0 == -1 问题全解
小年,并非专指一个日子,由于各地风俗,被称为“小年”的日子也不尽相同。小年期间主要的民俗活动有扫尘、祭灶等。民间传统上的小年(扫尘、祭灶日)是腊月二十四,南方大部分地区,仍然保持着腊月二十四过小年的古老传统。从清朝中后期开始,帝王家就于腊月二十三举行祭天大典,为了“节省开支”,顺便把灶王爷也给拜了,因此北方地区百姓随之效仿,提前一天在腊月二十三过小年。
Jasonangel
2021/05/28
6010
机器数及特点
机器数及特点 <1> 为什么要研究机器内的数据表示 目的:组织数据,方便计算机硬件直接使用 要考虑的因素 - 支持的数据类型 - 能表示的数据范围 - 能表示的数据精度 - 存储和处理的代价 - 是否有利于软件的移植 - .... <2> 机器内的数据表示 真值:符号用 "+"、 "-" 表示的数据表示方法 机器数:符号数值化的数据表示方法,用0、1表示符号 三种常见的机器数:设定点数的形式为X<sub>0</sub>X<sub>1</sub>X<sub>2</sub>X<sub>3
ruochen
2021/05/15
6680
机器数及特点
相关推荐
五分钟搞不定系列- 1+1=?
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档