计算机组成原理第4讲_乘法

1、1计算机组成原理Principles of Computer Organization广义双语教学课程09/skyclass25/青岛理工大学 校级精品课程http:/ 运算方法和运算部件运算方法和运算部件( 3 )A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. It is built using binary adders.Until the late 1

2、970s, most minicomputers did not have a multiply instruction, and so programmers used a multiply routine” which repeatedly shifts and accumulates partial results, often written using loop unwinding. Early microprocessors also had no multiply instruction.原码一位乘法原码一位乘法补码一位乘法补码一位乘法补码两位乘法补码两位乘法原码两位乘法原码两位

3、乘法Unsigned Binary Multiplication 无符号数乘法无符号数乘法两个尾数为两个尾数为n位的数相乘，乘积的尾数为位的数相乘，乘积的尾数为2n位位。手算乘法的过程：1011 被乘数 1101 乘数101100001011101110001111位积乘积需要需要n个寄存器保存位积个寄存器保存位积对应于乘数的位，将被乘数逐次左移一位加在左下方。最后将n个位积相加，得到乘积。计算机不能照搬手算的算法。运算器一次只能完成两数的求和操作。运算器一次只能完成两数的求和操作。需要需要2n位的加法器位的加法器3. 3 二进制乘法运算二进制乘法运算 Binary Multiplicatio

4、n Binary (Fixed-Point) Multiplication Arithmetic被乘数左移，根据乘数每个位做不同运算，都不便于计算机实现计算机的算法： 只能把每一个新位积与部分积（部分积的初值为零）相加，只能把每一个新位积与部分积（部分积的初值为零）相加，总共做总共做n次加法（累加）。次加法（累加）。 部分积与位积相加时，只有n位与位积相加，其余部分并不参加运算。因此用n位的加法器就可完成乘法了。被乘数左移一位的操作改为部分积右移一位后与被乘数相加。只需用1个n位的寄存器存放部分积的高位，部分积的低位与乘数共用一个n位的寄存器，在乘数右移一位（计算该位位积后自动丢失）的同时将部

5、分积最低一位移入。乘法完成后，原来存放乘数的寄存器中是乘积的低n位，乘数全部丢失，而硬件则节省了一个寄存器。被乘数10111101 乘数0000部分积+ 10111011+ 000001011+ 101101011 110 右移一位001011 11 右移一位设计乘法逻辑&计数器A 部分积 AFBFF/2ACdC 乘数B 被乘数 F 加法器 移位电路 C/2C无符号数乘法无符号数乘法逻辑原理图逻辑原理图运算前，先将被乘数送寄存器B，乘数送寄存器C，计数器的初值为N，部分积寄存器A清零。若乘数末位Yi1，部分积与被乘数在加法器相加。若乘数末位Yi0，则加法器输出的是部分积与0的和。寄存器

6、A和C中的部分积和乘数都右移一位形成新的部分积，部分积的最低位移入C空出的最高位。如此重复N次，乘法计算完毕。乘积的高N位在A中，低N位在C中，原来在C中的乘数在移位中丢失。CPA例1 X+0.1011B，Y0.1101B，解：乘积的符号位110SSYX用原码一位乘法计算XYX原 =|X|=Y原 =|Y|=0.10111.11010.10110.1101原码运算，必须把符号位与数值部分分开进行。符号位做异或运算，数值部分做无符号数相乘。Most computers use a shift and add algorithm for multiplying small integers.|X|=

7、 0.1011， |Y|= 0.1101高位部分积 0 0 0 0 0低位部分积 / 乘数 1 1 0 1初始状态|XY|=0.10001111右移 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1右移 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1+) 0 1 0 1 1右移 0 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0+) 0 0 0 0 0右移 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1+) 0 1 0 1 1+) 0 1 0 1 1XY0.10001111BXY原=1.10001111乘

8、数最低位为1，加|X|乘数最低位为0，加0乘数最低位为1，加|X|乘数最低位为1，加|X|原码一位乘法流程图YY开始结束A0，CdnBX，CYCn=1?A(A)+(B)(A),(C)右移一位Cd(Cd)1Cd=0?SSSYXPNNFlowchart如果乘数的数值部分是N位，则共需做N次加法，N次右移。乘积的数值部分是2N位。原码乘法做的是绝对值相乘，相当于无符号数相乘。右移按逻辑右移进行。缺点：需做N次加法，N次右移，时间太长。计数器乘数被乘数部分积乘积的符号位乘积的符号位SSYX 原码运算，必须把符号位与数值部分分开进行。原码运算，必须把符号位与数值部分分开进行。符号位做异或运算，数值部分做

9、无符号数相乘。符号位做异或运算，数值部分做无符号数相乘。 两个原码表示的数（无论小数或整数）相乘，乘积的值是两数绝对值之积，符号是相乘两数符号位的异或值。两个尾数为n位的数相乘，乘积的尾数为2n位。The second problem is that the basic school method handles the sign with a separate rule (+ with + yields +, + with - yields -, etc.). This method is mathematically correct, but it has two serious engi

10、neering problems. The first is that it involves 32 intermediate additions in a 32-bit computer, or 64 intermediate additions in a 64-bit computer. These additions take a lot of time.原码两位乘法原码两位乘法按照乘数每两位的情况，一次求出对应于该2位的部分积。增加少量逻辑电路，可使乘法的速度提高一倍。乘数的相邻两位Yi-1Yi有4种状态组合，分别对应一种操作：Yi-1Yi 操 作0 00 11 01 1相当于0X相当

11、于1X相当于2X相当于3X部分积Pi +0后右移2位部分积Pi +X后右移2位部分积Pi +2X后右移2位部分积Pi +3X后右移2位加2X很容易实现。把X左移一位，或者把X向左斜传送一位。加3X一般不能一次完成。分两次（3X=X+2X）又降低了速度。如果令 3X=4XX， 形式上看好象需要2次。实际上可以这样： 本次运算只做减减X，用一个欠帐触发器欠帐触发器C记下欠加4X，下一步操作时补上。 由于本次累加后，部分积要右移2位，相当于乘数相对左移2位。此时做+X相当于前一步+4X。所以，3X=4XX只需要做一次。欠帐触发器欠帐触发器C的初值为的初值为0。Yi-1Yi 操 作0 00 11 01

12、 1相当于0X相当于1X相当于2X相当于3X部分积Pi +0后右移2位部分积Pi +X后右移2位部分积Pi +2X后右移2位部分积Pi +3X后右移2位原码二位乘法的运算规则：当欠帐触发器当欠帐触发器C=0时，时，Yi-1 Yi C 0 0 0 0 1 0 1 0 0 1 1 0操 作部分积Pi +0后右移2位部分积Pi +X后右移2位部分积Pi +2X后右移2位部分积Pi X后右移2位0C0C0C1C当欠帐触发器当欠帐触发器C=1时，时，Yi-1 Yi C 0 0 1 0 1 1 1 0 1 1 1 1操 作部分积Pi +X后右移2位部分积Pi +2X后右移2位部分积Pi +-X补后右移2位

13、部分积Pi +0后右移2位0C0C1C1C减X用加-X补实现。右移按补码右移规则进行。右移按补码右移规则进行。 当乘数的数值部分是当乘数的数值部分是N位（位（N必须是偶数必须是偶数），则共需做），则共需做N/2次次加法和加法和N/2次右移。最后如果还有次右移。最后如果还有欠帐，再做一次欠帐，再做一次+X。欠帐触发器C的初值为0。 由于在运算中有由于在运算中有+2|X|，产生的进位可能侵占符号位，所以被，产生的进位可能侵占符号位，所以被乘数和部分积应该取乘数和部分积应该取3符号位。符号位。例2：X= -0.111111，Y= +0.111001，用原码二位乘法计算X*Y符号位单独处理符号位单独处

14、理，000YXP乘数乘数的数值部分的数值部分必须是偶数位必须是偶数位。相乘的是两数的绝对值。原码二位乘法的运算规则：解：X 原=1.111111乘积的符号位101000YXP| X |=0.111111| 2X |=001.111110例2：X= -0.111111，Y= +0.111001，用原码二位乘法计算X*YY 原=0.111001| Y |=0.111001-|X |补补=1.000001|X|= 0.111111, |Y|= 0.111001, | 2X |=001.111110, -|X |补=1.000001高位部分积 000. 0 0 0 0 0 0乘数 欠帐触发器C 1 1

15、 1 0 0 1 0 初始状态 000. 1 1 1 0 0 0 0 0 0 1 1 1 111. 1 1 1 0 0 1 0 0 0 1 1 1 1 右移2位 111. 1 0 0 1 0 0+ 111. 0 0 0 0 0 1000. 1 0 0 0 1 1 0 1 1 1 1 1 0 右移2位 010. 0 0 1 1 0 1+ 001. 1 1 1 1 1 0000. 0 0 1 1 1 1 1 1 1 1 1 0 0 右移2位 000. 1 1 1 1 1 1+ 000. 1 1 1 1 1 1+ 000. 1 1 1 1 1 1Yi-1Yi C010，加|X|,0CYi-1Yi C

16、100，加|2X| ,0CYi-1Yi C110，加-|X|补,1CC1，加|X|X*Y原原 =1. 111000000111X*Y= -0.111000000111|X*Y| = 0. 111000000111 在计算机系统内，由于电路故障或电磁干扰等原因，数据在存取或传送过程中可能产生错误。为了能发现或纠正这类错误，常采用具有能发现某些错误，或具有能确定错误的性质和准确的出错位置乃至能自动纠正错误的能力的编码方法，即数据校验码。Most codes are systematic: the transmitter sends a fixed number of original data b

17、its, followed by fixed number of check bits (usually referred to as redundancy in the literature) which are derived from the data bits by some deterministic algorithm. 其实现原理是在合法的数据编码之间加进一些不允许出现的非法编码，使合法编码的码距增大。当合法的数据编码出现错误时，就变成非法编码。这就可以用检测编码的合法性来发现错误。The receiver applies the same algorithm to the re

18、ceived data bits and compares its output to the received check bits; if the values do not match, an error has occurred at some point during the transmission.3.7 数据校验码数据校验码 由若干位代码组成的一个字叫“码字”，一种码制是若干种码字的组合。将两个码字逐位比较两个码字逐位比较，有几个二进制位不同有几个二进制位不同称为这两个码字间的距离两个码字间的距离。 只有一位不同只有一位不同的，称其码距为码距为1。例如，3位二进制代码有8种状态

19、，若一种码制用到全部8种码字，其码距为1。就是说，任何一个合法码字的一位或几位出错时，就变成另一个合法码字。一种码制中各码字间的最小距离称为该码制的一种码制中各码字间的最小距离称为该码制的“码距码距”。000111101001110010011100一种码制中各码字间的最小距离称为该码制的“码距”。 若增大编码的冗余度冗余度，设计该码制时用4个二进制位来表示8个合法码字。由于只利用了全部16种状态中的8种来表示合法码，就可以把其余8种状态作为非法码，则码距可能增大到2。当一个合法码的一位出错时，将变成一个非法码而被发现。所增加的一位称为所增加的一位称为校验位校验位。数据000001010011

20、100101110111编码00000011010101101001101011001111非法码00100001011101001011100011101101出错 合理的安排非法编码的数量和编码规则，增大合法码的码距就可以提高发现错误的能力，甚至能自动纠正错误；但表示一定数量的合法码所使用的二进制位数也增多，使数据存储和传送的数量增大，硬件开销也相应增大。常用的数据校验码有：奇偶校验码奇偶校验码、海明校验码海明校验码 和 循环冗余校验码循环冗余校验码等。 根据纠错理论，编码的最小距离与编码的检测、纠错能力的关系为：L1 = C+D其中：L是编码编码的最小距最小距离，D是可以检测错误代码可以

21、检测错误代码的位数位数，C是可以纠正错误代码可以纠正错误代码的位数位数，DC。当L=3时，可检测出检测出2个错误个错误，或者可检测并纠正可检测并纠正1位错误位错误。当L=4时，可检测检测出3个错误个错误，或者可检测检测出2位并纠正位并纠正1位错误位错误。奇偶校验码奇偶校验码 Parity Check Code 奇偶校验码的编码方法是给n位的合法编码增加一个奇偶校奇偶校验位验位，使其码距增加到码距增加到2。任何一位出错一位出错（包括校验校验位）都会使代码代码的奇偶性奇偶性改变改变，从而被发现。校验位可以放在最高数据位的左边，或最低数据位的右边。 若若n+1位的奇偶校验码中位的奇偶校验码中“1”的

22、个数为奇数的个数为奇数称为奇校验奇校验，“1”的个数为偶数的个数为偶数称为偶校验。偶校验。 当n位信息代码中有偶数个位信息代码中有偶数个1，则偶校验附加的校验位为偶校验附加的校验位为0，而奇校验的校验位为奇校验的校验位为1 。例如：数据代码奇校验码偶校验码1010101010100101010101101101101110110110A parity bit is an error detection mechanism that can only detect an odd number of errors.设校验位在最右边交叉奇偶校验交叉奇偶校验 奇偶校验码广泛应用于存储器读写检查，数据传

23、输过程中的检查等。对数据块的横向和纵向都有奇偶校验位。例如： A7 A6 A5 A4 A3 A2 A1 A0 横向校验位横向校验位 第第1字节字节 1 1 0 0 1 0 1 1 1第第2字节字节 0 1 1 1 1 1 0 0 1第第3字节字节 1 0 0 1 1 0 1 0 0第第4字节字节 1 0 0 1 0 1 0 1 0 纵向校验位纵向校验位 1 0 1 1 1 0 0 0交叉奇偶校验能够发现两个位同时出错。交叉奇偶校验能够发现两个位同时出错。 奇偶校验能发现奇偶校验能发现1位或者奇数个位同时出错，但不能发现位或者奇数个位同时出错，但不能发现偶数个位同时出错，也没有纠错能力。偶数个位

24、同时出错，也没有纠错能力。计算机组成原理设计性作业课题课题1 定点运算器设计定点运算器设计 设计一个简单的设计一个简单的16位定点运算器逻辑结构。位定点运算器逻辑结构。 画出逻辑图，说明所设计的定点运算器是怎样进行定点画出逻辑图，说明所设计的定点运算器是怎样进行定点补码加法运算、减法运算和逻辑运算的。补码加法运算、减法运算和逻辑运算的。 列出运算器做不同运算时的控制信号。列出运算器做不同运算时的控制信号。 在基本的定点运算器基础上，如果要求计算机还能做定点在基本的定点运算器基础上，如果要求计算机还能做定点乘法、除法运算，可以怎样设计？乘法、除法运算，可以怎样设计？实验课题实验课题1 ALU设计

25、设计实验内容：实验内容： 按照题目要求设计一个16位ALU的逻辑，决定外部的端口（名称、有效电平）和内部各元件的连接，画出系统框图和逻辑图，设计仿真数据，用VHDL编程和仿真。 一、主要元件设计一、主要元件设计 14位并行进位加法器 功能要求：能完成两个4位二进制数（补码和无符号数）的加法和逻辑加运算。内部有并行进位链。可以扩展成多位组。 2组间并行进位链逻辑 功能要求：4个4位小组的组间并行进位链逻辑。 将组间并行进位链逻辑与4个4位超前进位加法器连接可以构成16位超前进位加法器。可参考74182的逻辑函数。（4学时）实验课题实验课题1 ALU设计设计实验内容：实验内容： 按照题目要求设计一个16位ALU的逻辑，决定外部的端口（名称、有效电平）和内部各元件的连接，画出