booth算法

2023-10-26

1、booth算法定义

乘数看作从最低位开始的一串二进制数字。Booth算法的基本思路是:对于具有连续0和1的组,需要产生的部分积较少。对于乘数中每个0,仅需要将前面的累加的部分积向右移动一位。
布斯编码采用相加和相减的操作计算补码数据的乘积,可以减少部分积的数目,用来计算有符号乘法,提高乘法运算的速度。

2、二进制乘法过程

二进制乘法过程可仿照十进制数乘法进行。由低位到高位,用乘数的每一位去乘被乘数,若乘数的某一位为1,则该次部分积为被乘数;若乘数的某一位为0,则该次部分积为0。某次部分积的最低位必须和本位乘数对齐,所有部分积相加的结果则为相乘得到的乘积。
在这里插入图片描述
在这里插入图片描述
上诉例子我们知道乘数和被乘数的位数都是4,那么如果计算结果超过2n(n)为二进制表示位数,那么我们将2n高位的其他位省略。

3、二进制乘法转换成 booth乘法运算

例如假设有一个8位乘数(Multiplier):0011_1110,它将产生6行非零的部分积。如果把该数字记成另一种形式,0100_00(-1)0(可以验证是同一个数字,-1是负1)

二进制化为十进制
0011_1110 = 0*2^7 + 0*2^6 + 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 0*2^0 = 62
0100_00(-1)0 = 0*2^7 + 1*2^6 + 0*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + (-1)*2^1 + 0*2^0 = 64 -2 = 62:64=2^6   2=2^1
0011_1110 = 0100_00(-1)0 = 2^6-2^1=0100_0000 - 0000_0010

计算0010_0001×0011_1110,在这里可以首先将乘数0011_1110改写为0100_0000 - 0000_0010,即根据乘法分配律得:

  0010_0001×0011_1110
= 0010_0001×(0100_0000 - 0000_0010)

此时,对于乘数,我们需要计算6次的部分积,变成了计算两次部分积。

4、Radix-2 Booth乘法器

Radix-2 Booth乘法器,即是基2 Booth乘法器,基为2的一次方。

2 = 2^1

数的表示方法:
在这里插入图片描述
N比特数B,将其展开,在N比特数B的最后一位B0后添加一个辅助位B(-1),且B(-1)=0:
在这里插入图片描述
从上式中得出,其基系数为:
在这里插入图片描述
将A与B相乘,则:
在这里插入图片描述
对于B的第n位和第n-1位,从上式可以发现,B可以通过相邻比特位的减法和2的n次方相乘而得。如果AB两数相乘,从B的-1和0位逐次向高位检查,累积A*B的结果。
根据 基2 Booth乘法器的基系数 表达式,得出以下Booth4编码:

相邻两个数据位,进行公式(第0位)-(第1位)计算,得到两位的编码(相邻居两位,从后面像前面减)
00         0-0= 0 转化成二进制编码 0
01         1-0= 1 转化成二进制编码 1
10         0-1=-1 转化成二进制编码-1     
11         1-1= 0 转化成二进制编码 0
根据两个数据位的编码决定进行加法、减法还是仅仅移位操作。

以下是基2 Booth编码表,根据两个数据位的编码决定进行加法、减法还是仅仅移位操作。
在这里插入图片描述

5、Radix-4 Booth乘法器

Radix-4 Booth乘法器,即是基4 Booth乘法器。基为2的二次方。

4 = 2^2

数的表示方法:
在这里插入图片描述
从上式中得出,基4 Booth乘法器的基系数为:
在这里插入图片描述
将A与B相乘,则:
在这里插入图片描述
根据 基4 Booth乘法器的基系数 表达式,得出以下Booth4编码:

相邻3位数,进行公式-2*(第3位)+(第2位)+(第1位)计算,得到两位的编码(相邻居两位,从后面像前面减)
000         (-2)*0+0+0= 0 转化成二进制编码 00,即 +0
001         (-2)*0+0+1= 1 转化成二进制编码 01,即 +1
010         (-2)*0+1+0= 1 转化成二进制编码 01,即 +1     
011         (-2)*0+1+1= 2 转化成二进制编码 10,即 +2
100         (-2)*1+0+0=-2 转化成二进制编码-10,即 -2
101         (-2)*1+0+1=-1 转化成二进制编码-01,即 -1
110         (-2)*1+1+0=-1 转化成二进制编码-01,即 -1
111         (-2)*1+1+1= 0 转化成二进制编码 00,即 -0

以下是基4 Booth编码表,其中A为被乘数,B为乘数。
在这里插入图片描述

6、Booth乘法器计算实例

在这里插入图片描述
下面展示一些 内联代码片

从二进制看9:(共6步)
9 = 0*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0

从基29:(共6步)
9 = 0*2^4 + 1*2^4 + (-1)*2^3 + 0*2^2 + 1*2^1 + (-1)*2^0

从基49:(共3步)
9 = 1*4^2 + (-2)*4^1 + 1*4^0
  = 1*2^4 + (-2)*2^2 + 1*2^0

其阵列表示如下:
在这里插入图片描述

注意:算式绿色部分的计算

(-2)*A*4^1
步骤1 		4^1 = 2^2(转化成2的偶次方)表示结果算术左移两位
步骤2 		(-2)*A=[(-1)*A]*2^1
步骤2.1   	2^1表示在基2中表示结果向左移1位
步骤2.2   	(-1)*A表示加上(-A);此例题中A=000111,(-A)=~(100111)+1=111000+1=111001
所以将结果11_1001在基2中表示结果向左移1位,得到111_0010,乘积的位数为2*6位,前面符号位补齐

此处引用 https://zhuanlan.zhihu.com/p/143802580.

例如第2章节的例题:计算0010_0001×0011_1110(即为33×62=2046),分别按照基2和基4展开运算

在这里可以首先将乘数0011_1110按照基2展开为
0011_1110——0 相邻两位 首位分组为 0(0)*2^0 + 1(0)*2^1 + 1(1)*2^2 + 1(1)*2^3 + 1(1)*2^4 + 1(1)*2^5 + 0(1)*2^6 + 0(0)*2^7
括号中的后一位减去前一位
0011_1110 = (0-0)*2^0 + (0-1)*2^1 + (1-1)*2^2 + (1-1)*2^3 + (1-1)*2^4 + (1-1)*2^5 + (1-0)*2^6 + (0-0)*2^7 
		  = (-1)*2^1 + 1*2^6 //= (-2) + 64 = 62
		  = (-1)*0000_0010 + 0100_0000 
		  
0010_0001*0011_1110	= 0010_0001*(0100_0000 - 0000_0010)
					= 0010_0001*0100_0000 -0010_0001*0000_0010	//进行移位计算,-0010_0001的补码为1101_1111,8*8位宽度为16位,前面符号为补齐
					= 00_0010_0001_000000 + 1101_1111*0000_0010  //进行移位计算
					= 0000_1000_0100_0000 + 1111_111_1101_1111_0
					= 0000_1000_0100_0000 + 1111_1111_1011_1110
					= 1_0000_0111_1111_1110 //因为两个8位数相乘,结果为16位,超出位舍去
所以,最后结果为:   111_1111_1110=2046
在这里可以首先将乘数0011_1110按照基4展开为
0011_1110——0 相邻三位 首位分组为 10(0)*4^0 + 11(1)*4^1 + 11(1)*4^2 + 00(1)*4^3 
相邻3位数,进行公式-2*(第3位)+(第2位)+(第1位)计算
0011_1110 = (-2)*4^0 + (-0)*4^1 + (-0)*4^2 + (1)*4^3 
		  = (-2)*4^0 + (1)*4^3 
		  = (-1)*2^1 + 1*2^6 //= (-2) + 64 = 62 
		  = (-1)*0000_0010 + 0100_0000 
		  	  
0010_0001*0011_1110	= 0010_0001*(0100_0000 - 0000_0010)
					= 0010_0001*0100_0000 -0010_0001*0000_0010	//进行移位计算,-0010_0001的补码为1101_1111,8*8位宽度为16位,前面符号为补齐
					= 00_0010_0001_000000 + 1101_1111*0000_0010  //进行移位计算
					= 0000_1000_0100_0000 + 1111_111_1101_1111_0
					= 0000_1000_0100_0000 + 1111_1111_1011_1110
					= 1_0000_0111_1111_1110 //因为两个8位数相乘,结果为16位,超出位舍去
所以,最后结果为:   111_1111_1110=2046


乘法器的布斯算法原理与VERILOG实现
booth4与csa4:2等见: https://zhuanlan.zhihu.com/p/127164011.

Verilog编程之乘法器的实现: https://blog.csdn.net/weixin_43074474/article/details/90473709.

备注:该内容为读书笔记,部分内容与图片收集来源于网络,如有侵权或错误,请联系我整改,谢谢!

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

booth算法 的相关文章

  • 学生正版Altium Designer许可证到期怎么再申请

    学生如何使用正版Altium Designer软件 适用于老师 学生 校友等等 目录 一 前情提要 二 许可证延期步骤 2 1 重要前提 2 2 许可证申请 2 3 申请完成 一 前情提要 如果不知道怎么安装学生版AD 可点击以下链接学生如
  • 补码加减运算及判断溢出方法

    一 补码加减运算 二 判断溢出方法 1 符号位判溢出方法 对于加减运算 两个异号数相加或者两个同号数相减 结果的绝对值一定比任何一个数的绝对值要小 不会发生上溢出 两个异号数相减或者两个同号数相加的绝对值肯定比任何一个数要大 可能发生溢出
  • 硬件学习——I2C

    I2C简单来讲就是2线的串行总线 由SDA Serial Data Line 和SCL Serial Clock Line 构成 它遵循主从结构 允许多主多从 主设备 发起 停止数据输出 并且通过控制时钟来控制数据传输过程 从设备 响应主设
  • AD中如何对圆形PCB板进行铺铜

    因为之前做了一块圆形的PCB板子 所以在铺铜时候发现圆形铺铜我该怎么快速去铺 于是查了一下网上 大部分人是推荐先圈出一个圆弧 然后在通过快捷键TVG或者是按下 shift 空格 但是我发现不适合我 于是我分享一下自己的方法 我们如果要对圆形
  • UPF与低功耗设计实现实例 -- 附UPF与DC综合脚本

    原文链接 https www eefocus com industrial electronics 473034 本文摘自 数字集成电路低功耗物理实现技术与 UPF 孙轶群 sun yiqun nationz com cn 国民技术股份有限
  • AD20铺铜显示和隐藏的设置

    如果只想隐藏当前选中的铜皮 那么就选中对应需要隐藏的铜 然后鼠标右击 在弹出的对话框中选择 铺铜操作 隐藏选中铺铜 需要隐藏一部分铜皮 即打开铺铜管理器 选择菜单栏中 工具 铺铜 铺铜管理器 在弹出的铺铜管理器对话框中 想将哪些铜皮去进行隐
  • (电赛电源方向)怎么样从零开始准备全国大学生电子设计竞赛

    提示 文章写完后 目录可以自动生成 如何生成可参考右边的帮助文档 文章目录 前言 一 电赛是什么 二 电源方向是什么 三 该怎么去学习电源方向的知识 1 博主的劝诫 2 硬件该准备些什么 3 软件该准备些什么 总结 前言 我建了一个群 分享
  • 磁盘数据线接触不良的故障排查

    手头有个小型主机 运行centos 发现工作很不稳定 经常启动不起来 就算启动起来也会在几分钟内出现各种IO错误 可能出现以下几种报错 1 只读文件系统 Read only file system 尝试对磁盘写入的时候可能出现这个错误 2
  • USB匹配电阻

    做过USB的人都或许有一个纠结 那就是D 和D 上到底要串多大的电阻 串在源端还是终端 我想说 网络上的说法都不完全正确 首先USB有低速 全速和高速之分 在低速和全速模式下是电压驱动的 驱动电压为3 3V 但在高速模式下是电流驱动的 驱动
  • 第一章 计算机系统概论

    一 计算机系统简介 1 计算机软硬件概念 计算机是一种能够执行指令的电子设备 它由硬件和软件两部分组成 计算机硬件是指计算机系统中的物理组件 包括中央处理器 CPU 内存 硬盘 输入设备 如键盘 鼠标 输出设备 如显示器 打印机 等 这些硬
  • 最详细的Vivado安装教程

    V i v a d o 安 装
  • 第三章 总线

    一 系统总线概念 系统总线是计算机内部各个组件之间传输数据和控制信息的通信线路 连接中央处理器 内存 输入输出设备 扩展插槽等各个组件 是计算机系统中最重要的硬件组成部分之一 具有数据传输 控制信号传输和总线协议等功能 系统总线的性能对计算
  • 硬件工程师-三极管

    目录 一 机械开关 二 三极管的种类 三 NPN型三极管 N型三极管 四 PNP型三极管 编辑 五 三极管公式 NPN型三极管 PNP型三极管 六 NPN管的继续讲解 三极管的导通电压 PNP管也是一样 三极管的三种状态 判断三极管是放大还
  • CTLE均衡器的使用问题

    CTLE是一种高速数字通信中很常见的均衡器 有别于其他常用的FFE和DFE等数字滤波器 它是一种模拟滤波器 一般通过传递函数的方式表征 以USB3 1 Gen2的公式举例 在其峰值增益 第一极点和第二极点均为定值的前提下 幅频响应曲线将通过
  • 学习区分dB、dBm、dBuV、dBi

    dB 对于分贝的概念 很多朋友最早接触这个概念 是用 分贝 评估声音的大小 声音的大小用分贝 dB 表示 是一种对数单位 用来描述声音的强度或功率比例 如果P是我们需要测试的声压级或声功率级 P0是参考值 通常取为标准听觉阈限的声压级 X
  • 计算机组成原理——数制与编码

    1 在以下编码中 零的表示唯一的是 C A 反码 B 原码 C 补码 D 原码和移码 2 假设某数的真值为 100 1010B 在计算机内部表示为1011 0110B 该数采用的编码为 D A 移码 B 原码 C 反码 D 补码 3 考虑以
  • 计算机组成原理综合1

    1 完整的 计算机系统 应包括 D A 运算器 存储器和控制器 B 外部设备和主机 C 主机和实用程序 D 配套的硬件设备和软件系统 2 计算机系统中的存储器系统是指 D A RAM存储器 B ROM存储器 C 主存储器 D 主存储器和外存
  • 1.69寸SPI接口240*280TFT液晶显示模块使用中碰到的问题

    1 69寸SPI接口240 280TFT液晶显示模块使用中碰到的问题说明并记录一下 在网上买了1 69寸液晶显示模块 使用spi接口 分辨率240 280 给的参考程序是GPIO模拟的SPI接口 打算先移植到FreeRtos测试 再慢慢使用
  • 1.69寸SPI接口240*280TFT液晶显示模块使用中碰到的问题

    1 69寸SPI接口240 280TFT液晶显示模块使用中碰到的问题说明并记录一下 在网上买了1 69寸液晶显示模块 使用spi接口 分辨率240 280 给的参考程序是GPIO模拟的SPI接口 打算先移植到FreeRtos测试 再慢慢使用
  • 有效降低EMI干扰的PCB设计原则

    降低EMI干扰的一些PCB设计建议 1 通过在所有信号下提供低阻抗 连续的返回路径来减少地面反弹 尤其是在表层布线时 2 保持所有走线距离板的边缘至少5倍信号线宽 3 对于关键信号 尽量采用带状线布局 4 将高速率 大电流的组件尽可能远离I

随机推荐