booth算法的附加位从哪里来（寄存器除法实验的原理）

本文目录

• 寄存器除法实验的原理
• 用Booth算法计算x乘以y x=0.110111,y=-0.101110 求详细的解题步骤
• booth算法 booth算法简介
• 怎么理解Booth算法
• booth算法的证明
• 补码一位算法

寄存器除法实验的原理

除法器以及booth乘法器的原理二、实验原理除法是乘法的倒数。首先我们看一下十进制数的除法。为了方便起见，我们假定十进制数的各位要么为1要么为0，例如（1001010）10 ÷（1000）：
除数
1 0 0 1 商1000）1 0 0 1 0 1 0 被除数-1 0 0 0 1 01 0 11 0 1 0- 1 0 0 01 010 余数被除数、除数、商、和余数的关系如下式所示：被除数=商×除数+余数式中，余数必须比除数小。除法中求商的基本方法是利用被除数减去除数，看结果是正还是负，来决定商的这位是1还是0。假定被除数和除数都是正的，因此商和余数都是非负的。操作数和结果都是32位的，忽略符号。
开始
比较善于节省空间的人们发现，商寄存器浪费的空间正好和余数寄存器浪费的空间一样，因此，将商寄存器和余数寄存器结合起来。下图为除法器的算法流程。
从寄存器左移一位

从余数寄存器左半部分减去除数寄存器，结果存在余数寄存器的左半部分

余数≥0
余数《0

测试余数

Yes:32
No《32

加除数到余数寄存器的左半部分已恢复原来的被除数值。商寄存器左移，第0位置0

寄存器的左半部分右移一位

循环32次
余数寄存器左移一位，第0位置1
3、实验步骤1.打开Quartus-》tools-》programmer，将booth_divider.sof下载到FPGA中。注意进行programmer时，应在program/configure下的方框中打勾，然后下载。2.在实验台上通过模式开关选择FPGA独立调试模式010。3.将短路子DZ3短接且短路子DZ4断开，使FPGA-CPU所需要的时钟使用正单脉冲时钟。4、实验现象本实验实现4位数的除法（无符号除法），输入输出规则对应如下：1、输入的4位被除数（dividend）md3～md0对应开关SD11～SD8。2、输入的4位除数（divisor）mr3～mr0对应开关SD3～SD0。3、按单脉冲按钮，输入脉冲，也即节拍。4、余数寄存器remainder（8位）r7~r0对应灯R7～R0。5、当计算结束时，ready信号为1，对应实验台上最上排最右排的标志位指示灯S，同时商和余数分别在灯A3~A0和A7~A4上体现出来。五、附录代码：LIBRARY IEEE;USE IEEE.STD_LOGIC_1164.ALL;USE IEEE.STD_LOGIC_UNSIGNED;ENTITY divider ISGENERIC(k : POSITIVE := 3); --input number word length less onePORT( dividend : IN BIT_VECTOR(k DOWNTO 0);
divisor : IN BIT_VECTOR(k DOWNTO 0); clock : IN BIT;quotient : OUT BIT_VECTOR(k DOWNTO 0);remainder_r : OUT BIT_VECTOR(k DOWNTO 0);--remainder remainder : INOUT BIT_VECTOR((2*k + 2) DOWNTO 0);--remainder REGfinish : INOUT BIT);END divider;ARCHITECTURE structural OF divider ISSIGNAL drreg : BIT_VECTOR(k DOWNTO 0);SIGNAL adderout : BIT_VECTOR(k DOWNTO 0);SIGNAL carries : BIT_VECTOR(k DOWNTO 0);SIGNAL augend : BIT_VECTOR(k DOWNTO 0);SIGNAL tcbuffout : BIT_VECTOR(k DOWNTO 0);SIGNAL adder_ovfl : BIT;SIGNAL clr_dr : BIT;SIGNAL load_dr : BIT;SIGNAL init_rem : BIT;SIGNAL load_rem : BIT;SIGNAL shift_rem : BIT;SIGNAL add_op : BIT;signal count : INTEGER RANGE 0 TO k :=0;SIGNAL count2 : INTEGER RANGE 0 TO 3 :=0;
BEGINPROCESS --main clocked process containing all sequential elementsBEGINWAIT UNTIL (clock’EVENT AND clock = ’1’);--register to hold divisor during divisionIF clr_dr = ’1’ THENdrreg 《= (OTHERS =》 ’0’);ELSIF load_dr = ’1’ THENdrreg 《= divisor;ELSEdrreg 《= drreg;END IF; --register/shifter accumulates partial remainder registerIF init_rem = ’1’ THENremainder 《= (OTHERS =》 ’0’);remainder((k+1) DOWNTO 1) 《= dividend; --initialize remainder and sll 1ELSIF load_rem = ’1’ THENremainder((2*k + 1) DOWNTO (k + 1)) 《= adderout; --load to top half remainder(2*k+2) 《= NOT remainder(2*k+1); remainder(k DOWNTO 0) 《= remainder(k DOWNTO 0); --refresh right half
ELSIF shift_rem = ’1’ THENremainder 《= remainder ROL 1; --rotate left ELSEremainder 《= remainder;END IF;END PROCESS;--adder adds/subtracts divisor to left half of the remainder registeraugend 《= remainder((2*k+1) DOWNTO (k+1));addgen : FOR i IN adderout’RANGEGENERATElsadder : IF i = 0 GENERATEadderout(i) 《= tcbuffout(i) XOR augend(i) XOR (NOT add_op);carries(i) 《= (tcbuffout(i) AND augend(i)) OR(tcbuffout(i) AND (NOT add_op)) OR((NOT add_op) AND augend(i));END GENERATE;otheradder : IF i /= 0 GENERATEadderout(i) 《= tcbuffout(i) XOR augend(i) XOR carries(i-1);
carries(i) 《= (tcbuffout(i) AND augend(i)) OR(tcbuffout(i) AND carries(i-1)) OR(carries(i-1) AND augend(i));END GENERATE;END GENERATE;adder_ovfl 《= carries(k-1) XOR carries(k);tcbuffout 《= NOT drreg WHEN (add_op=’0’) ELSE drreg;--divider state counterPROCESS(clock)BEGIN IF (clock’event AND clock=’1’) THEN IF (count=count’high AND count2=count2’high) THENcount 《= 0;count2 《= 0;finish 《=’1’; ELSIF (count2=count2’high) THENcount2 《=1;count 《= count+1;finish 《=’0’;ELSEcount2 《= count2 +1;finish 《=’0’;END IF;END IF;END PROCESS;--assign control signal values based on statePROCESS(count2)BEGIN--assign defaults, all registers refresh add_op 《=’0’;clr_dr 《= ’0’;
￥
5.9
百度文库VIP限时优惠现在开通,立享6亿+VIP内容
立即获取
除法器实验报告

计算机组成原理实验报告
题目：运算器部件实验：除法器
学 院 数学与信息学院
学科门类 工 学
专 业 12软件工程
学 号 2012436138
第 1 页
姓 名 王赛赛
指导教师 王兵
一、实验目的
1.掌握乘法器以及booth乘法器的原理
二、实验原理
除法是乘法的倒数。首先我们看一下十进制数的除法。为了方便起见，我们假定十进制数的各位要么为1要么为0，例如（1001010）10 ÷（1000）：
除数
1 0 0 1 商
第 2 页
1000）1 0 0 1 0 1 0 被除数
-1 0 0 0
1 0
1 0 1
1 0 1 0
- 1 0 0 0
1 010 余数
被除数、除数、商、和余数的关系如下式所示：
第 3 页
被除数=商×除数+余数
式中，余数必须比除数小。
除法中求商的基本方法是利用被除数减去除数，看结果是正还是负，来决定商的这位是1还是0。
假定被除数和除数都是正的，因此商和余数都是非负的。操作数和结果都是32位的，忽略符号。
开始
比较善于节省空间的人们发现，商寄存器浪费的空间正好和余数寄存器浪费的空间一样，因此，将商寄存器和余数寄存器结合起来。下图为除法器的算法流程。
第 4 页

从寄存器左移一位

从余数寄存器左半部分减去除数寄存器，结果存在余数寄存器的左半部分

第 5 页
余数≥0
余数《0

测试余数

Yes:32
No《32

加除数到余数寄存器的左半部分已恢复原来的被除数值。商寄存器左移，第0位置0

寄存器的左半部分右移一位

循环32次
余数寄存器左移一位，第0位置1
第 6 页
3、实验步骤
1.打开Quartus-》tools-》programmer，将booth_divider.sof下载到FPGA中。注意进行programmer时，应在program/configure下的方框中打勾，然后下载。
2.在实验台上通过模式开关选择FPGA独立调试模式010。
3.将短路子DZ3短接且短路子DZ4断开，使FPGA-CPU所需要的时钟使用正单脉冲时钟。
4、实验现象
第 7 页
本实验实现4位数的除法（无符号除法），
输入输出规则对应如下：
1、输入的4位被除数（dividend）md3～md0对应开关SD11～SD8。
2、输入的4位除数（divisor）mr3～mr0对应开关SD3～SD0。
3、按单脉冲按钮，输入脉冲，也即节拍。
4、余数寄存器remainder（8位）r7~r0对应灯R7～R0。
第 8 页
5、当计算结束时，ready信号为1，对应实验台上最上排最右排的标志位指示灯S，同时商和余数分别在灯A3~A0和A7~A4上体现出来。
五、附录
代码：
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
USE IEEE.STD_LOGIC_UNSIGNED;
ENTITY divider IS
第 9 页
GENERIC(k : POSITIVE := 3); --input number word length less one
PORT( dividend : IN BIT_VECTOR(k DOWNTO 0);
divisor : IN BIT_VECTOR(k DOWNTO 0);
clock : IN BIT;
quotient : OUT BIT_VECTOR(k DOWNTO 0);
remainder_r : OUT BIT_VECTOR(k DOWNTO 0);--remainder
第 10 页
remainder : INOUT BIT_VECTOR((2*k + 2) DOWNTO 0);--remainder REG
finish : INOUT BIT
);
END divider;
ARCHITECTURE structural OF divider IS
SIGNAL drreg : BIT_VECTOR(k DOWNTO 0);
SIGNAL adderout : BIT_VECTOR(k DOWNTO 0);
第 11 页
SIGNAL carries : BIT_VECTOR(k DOWNTO 0);
SIGNAL augend : BIT_VECTOR(k DOWNTO 0);
SIGNAL tcbuffout : BIT_VECTOR(k DOWNTO 0);
SIGNAL adder_ovfl : BIT;
SIGNAL clr_dr : BIT;
SIGNAL load_dr : BIT;
SIGNAL init_rem : BIT;
第 12 页
SIGNAL load_rem : BIT;
SIGNAL shift_rem : BIT;
SIGNAL add_op : BIT;
signal count : INTEGER RANGE 0 TO k :=0;
SIGNAL count2 : INTEGER RANGE 0 TO 3 :=0;
BEGIN
PROCESS --main clocked process containing all sequential elements
第 13 页
BEGIN
WAIT UNTIL (clock’EVENT AND clock = ’1’);
--register to hold divisor during division
IF clr_dr = ’1’ THEN
drreg 《= (OTHERS =》 ’0’);
ELSIF load_dr = ’1’ THEN
drreg 《= divisor;
ELSE
第 14 页
drreg 《= drreg;
END IF;
--register/shifter accumulates partial remainder register
IF init_rem = ’1’ THEN
remainder 《= (OTHERS =》 ’0’);
remainder((k+1) DOWNTO 1) 《= dividend; --initialize remainder and sll 1
ELSIF load_rem = ’1’ THEN
第 15 页
remainder((2*k + 1) DOWNTO (k + 1)) 《= adderout; --load to top half
remainder(2*k+2) 《= NOT remainder(2*k+1);
remainder(k DOWNTO 0) 《= remainder(k DOWNTO 0); --refresh right half
ELSIF shift_rem = ’1’ THEN
remainder 《= remainder ROL 1; --rotate left
ELSE
第 16 页
remainder 《= remainder;
END IF;
END PROCESS;
--adder adds/subtracts divisor to left half of the remainder register
augend 《= remainder((2*k+1) DOWNTO (k+1));
addgen : FOR i IN adderout’RANGE
GENERATE
lsadder : IF i = 0 GENERATE
第 17 页
adderout(i) 《= tcbuffout(i) XOR augend(i) XOR (NOT add_op);
carries(i) 《= (tcbuffout(i) AND augend(i)) OR
(tcbuffout(i) AND (NOT add_op)) OR
((NOT add_op) AND augend(i));
END GENERATE;
otheradder : IF i /= 0 GENERATE
adderout(i) 《= tcbuffout(i) XOR augend(i) XOR carries(i-1);
第 18 页
carries(i) 《= (tcbuffout(i) AND augend(i)) OR
(tcbuffout(i) AND carries(i-1)) OR
(carries(i-1) AND augend(i));
END GENERATE;
END GENERATE;
adder_ovfl 《= carries(k-1) XOR carries(k);
tcbuffout 《= NOT drreg WHEN (add_op=’0’) ELSE drreg;
第 19 页
--divider state counter
PROCESS(clock)
BEGIN
IF (clock’event AND clock=’1’) THEN
IF (count=count’high AND count2=count2’high) THEN
count 《= 0;
count2 《= 0;
finish 《=’1’;
第 20 页
ELSIF (count2=count2’high) THEN
count2 《=1;
count 《= count+1;
finish 《=’0’;
ELSE
count2 《= count2 +1;
finish 《=’0’;
END IF;
END IF;
END PROCESS

用Booth算法计算x乘以y x=0.110111,y=-0.101110 求详细的解题步骤

先求出补=1.0011

然后看补，得

0.0000

+ 1.0011

= 1.0011 再右移一位得0.10011

然后看补=0.10(11)，为11，所以直接右移一位得 0.010011

然后看补,得

0.010011

+ 0.1101

= 1.000111 再右移一位得0.1000111

然后看补，得

0.1000111

+ 1.0011

= 1.1011111 再右移一位得0.11011111

然后看补，得

0.11011111

+ 0.1101

= 1.10101111

因为是最后一步，所以不移位，得1.10101111

扩展资料：

Booth算法原理：

布斯算法将乘数看作从最低位开始的一串二进制数字。从最低位算起，只要这串数字为“0“，就不执行任何操作；当这串数字遇到第一个“1”时执行一次减法，即减被乘数与该位权值的乘积，而对于其后的“1”不执行任何操作；

当这串数字再变为“0”时，则遇到第一个“0”时执行一次加法，即加被乘数与该位权值的乘积，而对其后的“0”则不执行任何操作。如此一直进行到最高位   。

举例来说，假设被乘数是5，乘数是7，即进行二进制数00000101与00000111相乘。该算法将7看作为三个“1”后面跟有五个“0”的一串数字。对于第一个”1”，该算法将减去5×20，对于第二和第三个“1”，则不执行任何操作；当遇到第一个“0”时，加5×23，得到最后结果是35。

booth算法 booth算法简介

1、Booth算法是一种适合于通过硬件实现的简便算法。将乘数看作从最低位开始的一串二进制数字。Booth算法的基本思路是：对于具有连续0和1的组，需要产生的部分积较少。对于乘数中每个0，仅需要将前面的累加的部分积向右移动一位。

2、简介：利用移位和加法，可以实现二进制无符号数的乘法，在无符号数乘法的基础上，加上适当的符号处理，很容易得到带符号数的原码乘法器。但是，在计算机中，带符号数都以补码表示，若采用原码乘法器进行带符号数的乘法运算，则首先要将乘数和被乘数转换成原码，相乘后再将负的乘积转换成补码，致使运算过程比较复杂。

3、不少处理器直接采用补码相乘的方法，以避免运算过程中的码制转换，提高处理器的工作效率。然而，二进制无符号的乘法并不能直接推广到补码的乘法运算，比较普遍采用的是布斯(Booth)补码相乘算法。

怎么理解Booth算法

布思算法（booth
algorithm）的简单理解方法：
由于是第一次接触，对于其原理却一无所知，书上的解释以及网上的文章不知是自己才疏学浅还本来就是泛泛而谈，没有让我了解其本质。经过长时间的思考分析，最终找到了一种比较简单的理解方法。
举一个简单的例子，比如说计算×，在这里首先将乘数改写为 -
即
-
---------------------------------------------------
这样根据乘法分配律得×=×（0100）
类似于booth算法的重新编码形式，再将上述算式改写为
×=×0+1
+ × -1 0
最终再将上式合并到一起，可得由booth算法改写后的编码形式： × 0+10000-10
由此可见，乘数的数段"01"可以重新编码为“+1”,数段“10”可以重新编码为“-1”，数段“11”可重新编码为“0”
根据无符号二进制数乘法的过程可知，当乘数段为“00”只是对乘数进行了右移操作，故重新编码为“0”
由于上述推导过程是根据二进制数加减以及乘法分配律推导而来的，故对于由补码表示的负数乘法同样适用

booth算法的证明

比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断，根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0)，移位操作是向右移动。在上例中，第一次判断被乘数0110中的最低位0以及右边的位(辅助位0)，得00；所以只进行移位操作；第二次判断0110中的低两位，得10，所以作减法操作并移位，这个减法操作相当于减去2a的值；第三次判断被乘数的中间两位，得11，于是只作移位操作；第四次判断0110中的最高两位，得01，于是作加法操作和移位，这个加法相当于加上8a的值，因为a的值已经左移了三次。
　　一般而言，设y=y0,yly2…yn为被乘数，x为乘数，yi是a中的第i位(当前位)。根据yj与yi+1的值，Booth算法表示如下表所示，其操作流程如下图所示。在Booth算法中，操作的方式取决于表达式(yi+1-yi)的值，这个表达式的值所代表的操作为：
　　0 无操作
　　+1 加x
　　-1 减x
　　Booth算法操作表示
　　yi yi+1 操作 说明
　　0 0 无 处于0串中，不需要操作
　　0 1 加x 1串的结尾
　　1 0 减x 1串的开始
　　1 1 无 处于1串中，不需要操作
　　乘法过程中，被乘数相对于乘积的左移操作可表示为乘以2，每次循环中的运算可表示为对于x(yi+1-yi)2^31-i项的加法运算(i=3l，30，…，1，0)。这样，Booth算法所计算的结果 可表示为：
　　x×(0-y31)×2^0
　　+x×(y31-y30)×2^1
　　+x×(y30-y29)×2^2
　　…
　　　+x×(y1-y0)×2^31
　　=x×(-y0×231 +y1×2^30 +y2×2^29+y31×2^0)
　　=x×y
　　例：用Booth算法计算2×(-3)。
　　解：补=1101，在乘法开始之前，R0和R1中的初始值为0000和1101，R2中的值为0010。
　　在乘法的第一个循环中，判断R1的最低位和辅助位为10，所以进入步骤1c，将R0的值减去R2的值，结果1110送人R0，然后进入第二步，将R0和Rl右移一位，R0和R1的结果为11110110，辅助位为l。
　　在第二个循环中，首先判断Rl的最低位和辅助位为0l，所以进入步骤1b，作加法，R0+R2=1111+0010，结果0001送入R0，这时R0R1的内容为0001 0110，在第二步右移后变为0000 1011，辅助位为0。
　　在第三次循环中，判断位为10，进入步骤lc，R0减去R2，结果1110送入R0，R1不变；步骤2移位后R0和R1的内容为1111 01011，辅助位为1。
　　第四次循环时，因两个判断位为11，所以不作加减运算，向右移位后的结果为1111 1010，这就是运算结果(—6)。
　　这个乘法的过程描述如下表所示，表中乘积一栏表示的是R0、R1的内容以及一个辅助位P，黑体字表示对两个判断位的判断。
　　用Booth补码一位乘法计算2 ×(-3)的过程
　　循环
　　步骤
　　乘积（R0,R1, P）
　　0
　　初始值
　　0000 1101 0
　　第一次循环
　　1c：减0010
　　1110 1101 0
　　2：右移1位
　　1111 0110 1
　　第二次循环
　　1b：加0010
　　0001 0110 1
　　2：右移1位
　　0000 1011 0
　　第三次循环
　　1c：减0010
　　1110 1011 0
　　2：右移1位
　　1111 0101 1
　　第四次循环
　　1a：无操作
　　1111 0101 1
　　2：右移1位
　　1111 1010 1
　　4．补码两位乘
　　补码两位乘运算规则是根据补码一位乘的规则，把比较yiyi+1的状态应执行的操作和比较yi-1yi 的状态应执行的操作合并成一步，便可得出补码两位乘的运算方法。
　　补码两位乘法运算规则如下
　　判断位yi-1y iyi+1
　　操作内容
　　000
　　补
　　001
　　补}
　　010
　　补}
　　011
　　补}
　　100
　　补}
　　101
　　补}
　　110
　　补+-x}补}
　　111
　　补
　　由上表可见，操作中出现加2补，都可能因溢出而侵占双符号位，故部分积和被乘数采用三位符号位。
　　例：补。
　　解：求解过程如下表所示。其中乘数取两位符号位即11.0101,补=1.1011取三符号位为111.1011。
　　部分积
　　乘数
　　说 明
　　000.0000
　　+ 000.0101
　　1101010
　　判断位为010，加补
　　000.0101
　　000.0001
　　+ 000.0101
　　0111010
　　→2位
　　判断位为010，加补
　　000.0110
　　000.0001
　　+ 111.1011
　　01
　　1001110
　　→2位
　　判断位为110，加补
　　111.1100
　　1001
　　最后一步不移位，得补
　　故补=1.11001001
　　可见，与补码一位乘相比，补码两位乘的部分积多取一位符号位（共3位），乘数也多取一位符号位（共2位），这是由于乘数每次右移2位，且用3位判断，故采用双符号位更便于硬件实现。可见，当乘数数值位为偶数时，乘数取2位符号位，共需作n/2次移位，最多作n/2+1次加法，最后一步不移位；当n为奇数时，可补0变为偶数位，以简化逻辑操作。也可对乘数取1位符号位，此时共作n/2+1次加法和n/2+1次移位（最后一步移一位）。
　　对于整数补码乘法，其过程与小数乘法完全相同。为了区别于小数乘法，在书写上可将符号位和数值位中间的“.”改为“，”即可。
　　再补充一道例子，增加一下理解。呵呵
　　例1.37 设被乘数M=0111（7），乘数Q=0011（3），相乘过程如下：(其中的①②……是我自己加上去的)
　　A Q Q-1
　　①００００　００１１ ０ 初始值
　　②１００１ ００１１　０ A=A-M
　　③１１００　１００１　１　右移（第1次循环）
　　④１１１０　０１００　１　右移（第2次循环）
　　⑤０１０１　０１００　１　A=A+M
　　⑥００１０　１０１０　０　右移（第3次循环）
　　⑦０００１　０１０１　０　右移（第4次循环）
　　乘法运算结束后，所得结果共8位，A寄存器中是乘积的高位部分，Q寄存器中是乘积的低位部分，即乘积=0010101=(21)(十进制）
　　例１.38　设被乘数M=0111(7),乘数Q＝１１０１（－３），相乘过程如下：
　　A Ｑ　Ｑ－１
　　００００　１１０１　０　初始值
　　１００１　１１０１　０　Ａ＝Ａ－Ｍ
　　１１００　１１１０　１　右移（第１次循环）
　　００１１　１１１０　１　Ａ＝Ａ＋Ｍ
　　０００１　１１１１　０　右移（第２次循环）
　　１０１０　１１１１　０　Ａ＝Ａ－Ｍ
　　１１０１　０１１１　１　右移（第３次循环）
　　１１１０　１０１１　１　右移（第４次循环）
　　乘积=11101011=(-21)(十进制)

补码一位算法

补码一位算法中每次加法加数的值是用乘数补码的最低一位和一个附加位来确定，一位是针对乘数最低一位说的。
这种算法对小数来说得到的部分积和结果是双符号的，双符号00、01、10、11代表的意义各不相同，标出小数点更容易区分双符号是什么。