计算机算法和算法逻辑实现 课件.ppt
《计算机算法和算法逻辑实现 课件.ppt》由会员分享,可在线阅读,更多相关《计算机算法和算法逻辑实现 课件.ppt(160页珍藏版)》请在三一办公上搜索。
1、计 算 机 组 成 原 理,第六-八讲,计算机算法和算法逻辑实现,1、定点数加减法运算及电路实现补码的加减法运算,全加器,溢出,快速加法运算(进位链),74181ALU2、定点数乘除运算和电路实现原码、补码,布斯算法,原码恢复余数、不恢复余数3、快速乘除法运算技术和电路实现布斯高基乘法,阵列乘法器,阵列除法器4、浮点数四则运算以及实现加减乘除,本讲安排,本讲将解决的主要问题,掌握计算机算法。加减乘除运算方法和运算器的构成,原码和补码的加减乘除四则运算,浮点数的四则运算。,补码加、减法,溢出概念与检测方法,基本的二进制加法/减法器,十进制加法器,加法规则: 先判符号位,若相同,绝对值相加,结果符
2、号不变; 若不同,则作减法, |大| - |小|,结果符号与|大|相同。减法规则: 两个原码表示的数相减,首先将减数符号取反,然后将被减数与符号取反后的减数按原码加法进行运算。,补码加法,1.原码加/减法运算,补码加法的公式:, x 补 y 补 xy 补 (mod 2),在模2意义下,任意两数的补码之和等于该两数之和的补码。 这是补码加法的理论基础。,2.补码加法运算,特点:不需要事先判断符号,符号位与码值位一起参加运算。 符号位相加后若有进位,则舍去该进位数字。,假设采用定点小数表示,因此证明的先决条件是: x1, y1, xy1。,(1) x0, y0, 则 xy0。 相加两数都是正数,故
3、其和也一定是正数。正数的补码和原码是一样的,可得: x 补 y 补xy xy 补(mod 2),公式证明:,(2) x0, y0, 则 xy0 或 xy0 时, 2+ (x+y) 2, 进位2必丢失, 又因 (x+y)0, 故 x补 y补xy xy补 (mod 2) 当xy0时, 2 (xy) 2, 又因 (x+y)0, 故x补y补2(xy)xy补(mod 2),(3) x0, 则 xy0 或 xy0。 同(2),把 x 和 y 的位置对调即可。 (4) x0, y0, 则 xy0。 相加两数都是负数,则其和也一定是负数。x补2x, y补2yx补 y补2x2y2(2xy) 因为|xy|1, 1
4、(2xy)2, 2(2xy) 进位2 必丢失,又因x+y0 故 x补 y补2(xy) xy补(mod 2),至此证明了在模2意义下,任意两数的补码之和等于该两数之和的补码。 其结论也适用于定点整数。补码加法的特点: (1)符号位要作为数的一部分一起参加运算; (2)在模2的意义下相加,即大于2的进位要丢掉。,结论:,例: x0.1001, y0.0101, 求 xy。,解: x补0.1001, y补0.0101 x补0.1001 y补 0.0101 xy 补 0.1110,所以 xy0.1110,例: x0.1011, y0.0101, 求 xy。,所以 xy0.0110,解: x补0.101
5、1,y补1.1011 x补0.1011y补1.1011 xy补 10.0110,补码减法,减法运算要设法化为加法完成,补码减法运算的公式: xy 补 x 补 y 补 x 补y 补,公式证明: 只要证明y补 y补, 上式即得证。,xy补x补 y补(mod 2) 令 y= x0补x补 + x补故 x补 x补 (mod 2),证明:,例: x0.1101, y0.0110, 求 xy。,解:x补0.1101 y补0.0110,y补1.1010 x补 0.1101 y补 1.1010 xy补 10.0111,xy0.0111,解: x补=1.0011 y补=1.1010 -y补=0.0110 x补 1
6、.0 0 1 1 + -y补 0.0 1 1 0 x-y补 1.1 0 0 1,例: x= -0.1101,y= -0.0110,求x-y=?,x-y = -0.0111,溢出及与检测方法,在定点小数机器中,数的表示范围为|1。在运算过程中如出现大于1的现象,称为 “溢出”。,1. 概念,解: x补=0.1011 y补=0.1001 x补 0. 1 0 1 1 + y补 0. 1 0 0 1 x+y补1. 0 1 0 0 两个正数相加的结果成为负数,这显然是错误的。,例: x=+0.1011, y=+0.1001, 求x+y。,例: x= -0.1101, y= -0.1011, 求x+y。,
7、解: x补=1.0011 y补=1.0101 x补 1. 0 0 1 1 + y补 1. 0 1 0 1 x+y补 0. 1 0 0 0 两个负数相加的结果成为正数,这同样是错误的。,发生错误的原因,是因为运算结果产生了溢出。两个正数相加: 结果大于机器所能表示的最大正数,称为上溢;两个负数相加:结果小于机器所能表示的最小负数,称为下溢。,分析 :,2.溢出的检测方法,x补 0. 1 0 1 1 + y补 0. 1 0 0 1 x+y补1. 0 1 0 0,x补 1. 0 0 1 1 + y补 1. 0 1 0 1 x+y补 0. 1 0 0 0,(1) 单符号位法,判断电路,一个符号位只能表
8、示正、负两种情况,当产生溢出时,符号位的含义就会发生混乱。如果将符号位扩充为两位(Sf1、Sf2),其所能表示的信息量将随之扩大,既能判别是否溢出,又能指出结果的符号。,(2) 双符号位法,双符号位法也称为“变形补码”或“模4补码” 。,变形补码定义:, 任何小于1的正数: 两个符号位都是“0”,即 00.x1x2.xn; 任何大于-1的负数:两个符号位都是“1”,即 11.x1x2xn,两数变形补码之和等于两数和的变形补码,要求: 两个符号位都看做数码一样参加运算; 两数进行以4为模的加法,即最高符号位上产生的进位要丢掉,模4补码加法公式: x补+ y补=x+y补 (mod 4),采用变形补
9、码后数的表示:,Sf1Sf2 00 结果为正数,无溢出 01 结果正溢 10 结果负溢 11 结果为负数,无溢出,即:结果的两个符号位的代码不一致时,表示溢出; 两个符号位的代码一致时,表示没有溢出。 不管溢出与否,最高符号位永远表示结果的正确符号。,溢出逻辑表达式为: VSf1Sf2 中Sf1和Sf2分别为最高符号位和第二符号位,此逻辑表达式可用异或门实现。,双符号位的含义如下:,解: x补=00.1100 y补=00.1000 x补 0 0. 1 1 0 0 + y补 0 0. 1 0 0 0 0 1. 0 1 0 0 符号位出现“01”,表示已溢出,正溢。即结果大于+1,例 x= +0.
10、1100, y= +0.1000, 求x+y。,解: x补=11.0100 y补=11.1000 x补 1 1.0 1 0 0 + y补 1 1.1 0 0 0 1 0. 1 1 0 0符号位出现“10”,表示已溢出,负溢出。即结果小于-1,例 x= -0.1100, y= -0.1000, 求x+y。,从上面例中看到: 当最高有效位有进位而符号位无进位时,产生上溢; 当最高有效位无进位而符号位有进位时,产生下溢。 (简单地说是正数相加为负数或负数相加为正数则产生溢出) 故溢出逻辑表达式为: VCfCo 其中Cf为符号位产生的进位,Co为最高有效位产生的进位。此逻辑表达式也可用异或门实现。,(
11、3) 利用进位值的判别法,x补0 0. 1 1 0 0+y补0 0. 1 0 0 00 1. 1 0 0 0,x补1 1.0 1 0 0+y补1 1.1 0 0 01 0.1 1 0 0,VC1Co,VSf1Sf2,判断电路,基本的二进制加法/减法器,1.一位全加器,逻辑电路(一位全加器),常用的全加器逻辑电路,逻辑符号,2.n位的行波进位加减器,n个1位的全加器(FA)可级联成一个n位的行波进位加减器。,T被定义为相应于单级逻辑电路的单位门延迟。 T通常采用一个“与非”门或一个“或非”门的时间延迟来作为度量单位。,3.n位的行波进位加法器的问题,时间延迟,(1)对一位全加器(FA)来说,Si
12、的时间延迟为6T(每级 异或门延迟3T);Ci1的时间延迟为5T。,3T,3T,T,T,(2) n位行波进位加法器的延迟时间ta为:, 9T为最低位上的两极“异或”门再加上溢出“异或”门的总时间; 2T为每级进位链的延迟时间。,tan2T9T(2n9)T,考虑溢出检测时,有:,当不考虑溢出检测时,有:ta(n-1)2T9T,ta为在加法器的输入端输入加数和被加数后,在最坏的情况下加法器输出端得到稳定的求和输出所需要的最长时间。 ta越小越好。,缺点:(1)串行进位,它的运算时间长;(2)只能完成加法和减法两种操作而不能完成逻辑操作。 多功能算术/逻辑运算单元(ALU): 不仅具有多种算术运算和
13、逻辑运算的功能; 而且具有先行进位逻辑。 从而能实现高速运算。,由一位全加器(FA)构成的行波进位加法器:,1.基本思想,SiAiBiCi,一位全加器(FA)的逻辑表达式为:,将Ai和Bi先组合成由控制参数S0,S1,S2,S3控制的组合函数Xi和Yi;(2)然后再将Xi,Yi和下一位进位数通过全加器进行全加。这样,不同的控制参数可以得到不同的组合函数,因而能够实现多种算术运算和逻辑运算。,解决方案:,多功能算术/逻辑运算单元(ALU),将全加器的功能扩展以完成多种算术逻辑运算。,= AiBiBiCiCiAi,参数S0 ,S1 ,S2 ,S3 分别控制输入Ai 和Bi ,产生Y和X的函数。其中
14、:Yi是受S0 ,S1控制的Ai和Bi的组合函数;Xi是受S2 ,S3控制的Ai和Bi组合函数。,函数关系如表所示。, 核心部分是由两个半加器组成的全加器。 由M控制第二级半加器选择逻辑运算或 算术运算(所需的低位进位Cn )。,一位ALU基本逻辑电路,进一步化简:,FiYiXiCn+i Cni1YiXiCni,综上所述,ALU的一位逻辑表达式为:,FiYiXiCn+i Cni1YiXiCni,4位之间采用先行进位(并行进位)公式。 根据 Cni1YiXiCni ,每一位的进位公式可递推如下: 第0位向第1位的进位公式为: Cn1Y0X0Cn (其中Cn是向第0位(末位)的进位) 第1位向第2
15、位的进位公式为: Cn2Y1X1Cn1Y1Y0X1X0X1Cn 第2位向第3位的进位公式为: Cn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2Cn 第3位的进位输出(即整个4位运算进位输出)公式为: Cn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn,4位ALU的进位关系及逻辑电路,Cn1Y0X0CnCn2Y1X1Cn1Y1Y0X1X0X1CnCn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2CnCn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn Cn+4是最后进位输出。 逻辑表达式表
16、明, 这是一个先行进位逻辑。换句话说, 第0位的进位输入Cn可以直接传送到最高位上去,因而可以实现高速运算。 下图为用上述原始推导公式实现的4位算术/逻辑运算单元(ALU) 74181ALU,从进位关系上看,正逻辑表示的74181,第3位的进位输出(即整个4位运算进位输出)公式为: Cn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn设 GY3Y2X3Y1X2X3Y0X1X2X3 PX0X1X2X3 则 Cn4GPCn 其中G称为进位发生输出,P称为进位传送输出。 在电路中多加这两个进位输出的目的,是为了便于实现多片(组)ALU之间的先行进位。,P
17、和G的含义,负逻辑表示的74181,2.算术逻辑运算的实现,上图中控制端用来控制ALU进行算术运算还是进行逻辑运算:0时: 对进位信号没有任何影响。此时Fi 不仅与本位的被操作数Yi 和操作数Xi 有关, 而且与向本位的进位值Cn+i 有关, 因此0时, 进行算术操作。 1时: 封锁了各位的进位输出, 即Cn+i 0, 因此各位的运算结果Fi 仅与Yi 和Xi 有关, 故1时, 进行逻辑操作。,下图为工作于负逻辑和正逻辑操作方式的74181ALU方框图。两种操作是等效的。, 对正逻辑操作数来说: 算术运算称高电平操作; 逻辑运算称正逻辑操作 (即高电平为“1”,低电平为“0”)。 对于负逻辑操
18、作数来说: 正好相反。,(1) H高电平,L低电平;(2) *表示每一位均移到下一个更高位,即A*2A。(3) 算术运算操作是用补码表示法来表示的,其中: “加”是指算术加,运算时要考虑进位; 符号“”是指“逻辑加”。(4) 减法是用补码方法进行的,其中数的反码是内部产生的, 而结果输出“A减B减1”,因此做减法时需在最末位产生一个强迫进位(加1), 以便产生“A减B”的结果。(5) “AB”输出端可指示两个数是否相等;,3.并行加法器的进位逻辑,74181ALU为4位并行加法器, 组成16位的并行加法器怎么办? 4片(组)74181连接 怎样连? 组与组之间串行连接 组与组之间并行连接,组间
19、串行进位,C4G0P0 C0,C8G1P1 C4,C12G2P2 C8,C16G3P3 C12,进位关系,Cn1Y0X0CnCn2Y1X1Cn1Y1Y0X1X0X1CnCn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2CnCn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn,组内,组间,GY3Y2X3Y1X2X3Y0X1X2X3 PX0X1X2X3,进位传递时间,(2)组间并行进位两级先行进位的ALU,由串行进位关系,C8 = G1P1 C4 = G1 + P1 (G0P0 C0 ) = G1+G0P1+P0P1C0,得:,C4 = G0P0
20、 C0,C12= G2P2 C8 = G2 + P2 (G1+G0P1+P0P1Cn) = G2+G1P2+G0P1P2+P0P1P2C0,C16 = G3+P3C12 = G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3C0 = G*P*C0,其中: P*P0P1P2P3 G*G3G2P3G1P1P2G0P1P2P3,根据上述公式实现逻辑电路:,0,进位的传递时间,由上图可见, 当Xi和Yi形成以后,经过1.5ty,产生第一小组的C1,C2,C3 和所有的Gi、Pi;, 经过1.5ty,由第二级进位链产生C4,C8,C12,C16; 再经1.5ty后,产生第2,3,4小组内的
21、C5C6C7, C9C10C11,C13C14C15。整个进位传递时间为4.5ty。,4.先行进位部件(CLA)74182,74182是一个并行进位部件,其内部结构图如下:,其中G*称为成组进位发生输出,P*称为成组进位传送输出。,Cn+= G0+P0CnCn+= G1+P1Cn+= G1+G0P1+P0P1CnCn+= G2+P2Cn+= G2+G1P2+G0P1P2+P0P1P2CnCn4 = G3+P3Cn+= G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3Cn = G*P*Cn其中: P*P0P1P2P3 G*G3G2P3G1P1P2G0P1P2P3,先行进位部件74
22、182CLA所提供的进位逻辑关系如下:,74181ALU设置了P和G两个本组先行进位输出端。 如果将四片74181的P,G输出端送入到74182先行进位部件(CLA),又可实现第二级的先行进位,即组与组之间的先行进位。,例:16位字长ALU的构成, C3、C7、C11是由74182同时形成的; 其不同点是74182还提供大组间的进位函数G* 和大 组传递条件P*,以便在位数更长时组成下一级先行进 位链。,由图可知:,用若干个74181ALU位片, 与配套的74182先行进位部件CLA在一起, 可构成一个全字长的ALU。,例:全字长的ALU的构成,用两个16位全先行进位部件级联组成的32位ALU
23、逻辑方框图。,十进制加法器,十进制加法器可由BCD码(二十进制码)来设计,它可以在二进制加法器的基础上加上适当的“校正”逻辑来实现。,X+Y+C10不调整,X+Y+C10调整,故: 1. 和为1015时,加6校正; 2. 和数有进位时,加6校正。,和数(4位)有进位调整,1.一位BCD码行波式进位加法器一般结构:,101010111100110111101111,2.n位BCD码行波式进位加法器一般结构:,原码乘法,补码乘法,定点乘法运算,设n位被乘数和乘数用定点小数表示 被乘数 x原xf . xn1 x1x0 乘数 y原yf . yn1 y1y0 则乘积 z原(xfyf)(0. xn1 x1
24、x0)(0. yn1 y1y0) 式中,xf为被乘数符号, yf为乘数符号。,原码一位乘法,1. 乘法的手工算法,(2) 手工运算过程:,设0.1101,0.1011,(1)乘积符号的运算规则:同号相乘为正,异号相乘为负。,(1) 机器通常只有n位长, 两个n位数相乘, 乘积可能为2n位。(2) 只有两个操作数相加的加法器难以胜任将n位积 一次相加起来的运算。,机器与人们习惯的算法不同之处:,0.1 1 0 1 x 0.1 0 1 1 y 0.0 0 0 0 1 1 0 1 x共4次右移 0.0 0 0 1 1 0 1 x共3次右移 0.0 0 0 0 0 0 x共2次右移 + 0.0 1 1
25、 0 1 x共1次右移 0.1 0 0 0 1 1 1 1,2. 适合定点机的形式,为了适合两个操作数相加的加法器,将 xy 改写成下面形式:,xy = x(0.1011) = 0.1x + 0.00 x + 0.001 x + 0.0001 x = 0.1 x+0.1 0 + 0.1 (x+0.1 x) = 2-1 x+ 2-1 0 + 2-1(x+2-1x) ,根据此式,按式中括号可表达的层次,从内向外逐次进行移位累加。,一般而言,设被乘数x,乘数y都是小于1的n位定点正数: x=0.x1x2.xn 1 y=0.y1y2.yn 1,其乘积为:xy=x(0.y1y2.yn ) =x(y12-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机算法和算法逻辑实现 课件 计算机 算法 逻辑 实现
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-1800530.html