计算机组成原理第3章修改版.ppt

《计算机组成原理第3章修改版.ppt》由会员分享，可在线阅读，更多相关《计算机组成原理第3章修改版.ppt（57页珍藏版）》请在三一文库上搜索。

1、1,1、数字信息和二进制编码知识,数值、文字、符号、语音和图形 等统称信息， 在计算机内部，信息都必须用数字化的形式被存储、加工 和 传送，不同信息要通过编码来表示。 数字化信息编码的二个要素： 少量简单的基本符号 一定的组合规则 计算机中普遍选用两个基本点符号： 优点是： 基本符号个数最少，物理上容易实现 二进制码表示数值数据运算规则简单 与二值逻辑的 真、假 两个值对应简单,2,二进制数据算术运算规则,(2) 减法运算规则 0-0=0 0-1=1 并产生借位 1-0=1 1-1=0,(1) 加法运算规则 0+0=0 0+1=1 1+0=1 1+1=0 并产生进位,例如： 0101,+) 0

2、001,0110,例如： 1011,) 0101,0110,0110,3,二进制数据算术运算规则,乘法运算规则 例如： 1101 00=0 ) 0101 01=0 1101 10=0 0000 11=1 1101 1000001,除法运算规则 0101 例如： 1101 1000001 1000001 / 1101 = 0101 1101 01101 1101 0,4,数制与进位记数法,基 r 数制的概念 只用 r 个基本符号 ( 例如 0,1,2,r-1 ) 通过排列起来的符号串表示数值，r 称为该数制的基。 数值 N 的表示 N = Dm-1Dm-2 D1 D0D-1D-2 D-k 有 权

3、 的基 r 数制 每个Di（-kim-1）的单位值都赋以固定的值Wi，则称 Wi 为该位的 权 。 N 代表的实际值可表示为：,5,数制与进位记数法,若逢 r 进位，有 Wi = ri ，则 N 代表一个数值 r 是这个数制的基 i 表示这些符号排列的位号 Di 是位序号为 i 的位上的一个符号 ri 是位序号为 i 的位上的一个 1 代表的值 Di ri 是第 i 位的符号所代表的实际值 表示 对 m+k 位的值求累加和 称此数制为 r 进位数制，简称 r 进制。最常用的有二进制、八进制、十六进制 和 十进制 这4种。,ri,6,数制与进位记数法,计算机中常用的 4 种进位数制 二进制：r

4、= 2， 基本符号：0 1 八进制：r = 8， 基本符号：0 1 2 3 4 5 6 7 十进制：r = 10，基本符号：0 1 2 3 4 5 6 7 8 9 十六进制：r = 16，基本符号： 0 1 2 3 4 5 6 7 8 9 A B C D E F 其中 AF 表示十进制数 1015 4 种进位数制之间的关系: 二进制用于计算机内部,八和十六进制是二进制的缩写, 十进制用于人员。,7,二进制数八、十六和十进制,把二进制数转换为十进制数， 累加二进制数中全部数值为 1 的那些位的位权 (1101.1100)2=(123+122+021+120)10 + (12-1+12-2+02-

5、3+02-4)10 = (13.75)10 把二进制数转换成八或十六进制数时，从小数点向左和向右把每 3 或者 4 个二进制位分成一组，直接写出每一组所代表的数值，小数点后不足位数补0。 (1101.1001)2 = (D.9)16 = (15.44)8 ，而不是(15.41)8,8,数制与进位记数法,二进位数和十进制数之间的转换方法 二进制：r = 2， 基本符号：0 1 十进制：r = 10，基本符号：0 1 2 3 4 5 6 7 8 9 求二进制数所对应的十进制数值，可通过进位记数公式来计算，即把取值为 1 的数位的位权累加。 把十进制数转换为二进制，对整数部分通过除 2取余数来完成，

6、对小数部分通过乘 2 取整数来完成。 2 13-1 低位 0.762 2 6-0 1 0.522 高位 2 3-1 1 0.042 2 1-1 高位 0 0.082 0 0 0.16 低位 (13)10 = (1101)2 (0.76)10 = (0.1100)2,9,3、数值数据的编码和运算算法,二进制数值数据的类型 二进制表示的定点小数、整数和浮点数 数值数据编码目标 能方便统一地表示正数、零和负数，并且尽可能有利于简化对它们实现算术运算用到的规则； 数据符号的正与负，可用一位二进制的 0 和 1两个状态加以表示，数据数值用多位二进制表示。 常用的编码方案 原码表示、补码表示、反码表示,1

7、0,机器数与真值,一个数据的实际值被称为数的真值，机器数是指对数据符号位完成数字化处理后的机内表示。,11, X = X = X =,定点小数表示: Ns N1 N2 Nn,原,X,1 - X,-1 X 0,反,X,(2 - 2 )+ X,-n,0 X 1,-1 X 0,补,X,2 + X,Mod ( 2 - 2 ),0 X 1,-1 X 0,Mod 2,0 X 1,-n,(纯小数) 原码，反码，补码的定义,12,实例： X1 = 0.1011 -0.1011 0.0000 X 补 = 0 1011 1 0100 0 0000 说明：补码最高一位是符号位，符号 0 正 1 负 补码表示为：2符

8、号位 + 数的真值 补码零只有一个编码，故能表示 -1 补码能很好地用于加减（乘除）运算,定点小数表示: Ns N1 N2 Nn,X,2 + X,-1 X 0,0 X 1,(纯小数) 补码的定义与说明,定义： X 补 =,MOD 2,13,整数的编码表示,整数的 原码 反码 补码 表示 与小数的三种表示基本相同 差别仅表现在小数点的位置 可以认为整数的小数点在最低数值位的右侧 因此整数的模与整数位数有关 讲课中不大用整数讲 原 反 补 码定义 例如：整数六位编码 ( 1 位符号位，5 位数值位) X = +01110 X原= 0 01110 X补= 0 01110 X = - 01110 X原

9、= 1 01110 X补= 1 10010,14,x 为真值,n 为整数的位数,整数的编码表示,15,原 反 补码表示小结,正数的 原码、反码、补码表示均相同， 符号位为 0，数值位同数的真值。 零的原码和反码均有 2个编码，补码只 1个码 负数的 原码、反码、补码表示均不同， 符号位为 1，数值位：原码为数的绝对值 反码为每一位均取反码 补码为反码再在最低位+1 由 X补 求 -X补：每一位取反后再在最低位+1,16,补码表示中的符号位扩展,由 X补 求 X / 2补 的方法 原符号位不变，且符号位与数值位均右移一位 例如， X补 =10010 则 X/2补 =110010 不同位数的整数补

10、码相加减时， 位数少的补码数的符号位向左扩展， 一直扩展到与另一数的符号位对齐。 0101010111000011 0101010111000011 + 10011100 + 00011100 0101010101011111 0101010111011111,00000000,11111111,17,补码的一些补充说明,由X补（X0 X1X2Xn）求真值 X X补 = 2X0 + X X = X补 - 2X0 = X0 X1X2Xn - 2X0 = -X0 + (-X0+ X0 X-1X-2X-n) = -X0 + 0.X1X2Xn 由 X补 求 X/2补的关系 X补 = X0 X1X2Xn

11、 X/2补 = X0 X0X1X2Xn,18,数据的算术运算: 算法和原理性电路,补码加、减法运算 原码一位乘法运算 原码一位除法运算 补码一位乘法运算 补码一位除法运算 原码二位乘法运算 补码二位乘法运算 阵列乘、除法器实现的更快的乘除运算,19,补码加减法的实现,补码可以方便地完成加减法运算，符号位和数值位同等地参加运算，只要结果不溢出，就能得到补码的正确的符号和正确的数值结果，而且可以使用加法器线路完成减法运算，使运算器实现更加简单，运算控制也很方便，同时为用于乘除法运算奠定了基础。 X + Y补= X补+ Y补 X - Y补= X补 + -Y补 -Y补 = 对 Y补 逐位取反再在最低位

12、加 1,看一下实现补码加减运算的原理性电路,20,实现补码加减运算的逻辑电路, , / ,加,减,21,00000111,实现补码加运算的执行过程,X X+Y 完成加法运算，需把被加数和加数送ALU的输入端，运算结果要接收到累加器，需要给出命令： ,加数,10110001,01010110,00000111,命令建立,数据传送,加运算,存结果,命令建立,数据传送,命令建立,00000111,22,实现补码减运算的逻辑电路,X XY 完成减法运算，需把被减数和减数送ALU的输入端，运算结果要接收到累加器，需要给出命令： /，F1 ,命令建立,数据传送,加运算,存结果,命令建立,数据传送,命令建立

13、,1,00001110,01100101,01010110,0110101,23,补码加减法溢出判断,方法之一： 单符号位，正 + 正 得负 或 负 + 负 得正 方法之二： 数字位有向符号位的进位，但符号位不产生向更高位的进位，数字位没有向符号位的进位，但符号位产生向更高位的进位 方法之三： 双符号位的结果为 01 或 10，最高符号位 代表其 真正的符号,判断溢出的逻辑电路如何实现呢？,24,补码加减法运算实例,X = 0.1011 y = -0.0101 X补 = 00 1011, Y补 = 11 1011 模 4 补码 -Y补 = 00 0101 00 1011 00 1011 +11

14、 1011 + 00 0101 100 0110 01 0000 X+Y (不溢出) X-Y (溢出),正数加负数不会溢出 符号位和数值位都产生进位 双符号位结果相同不是溢出,正数加正数结果为负是溢出 数值位有进位符号位无进位是溢出 双符号位结果不相同是溢出,判断溢出的 3套方案是一个事实的 3种不同的表述,此时C=1，Z=0，S=0,25,补码加减法运算实例,X = 0.0011 y = -0. 0011 X补 = 0 0011, Y补 = 1 1101 -Y补 = 0 0011 0 0011 0 0011 + 1 1101 + 0 0011 1 0 0000 0 0110 X+Y (不溢出

15、) X-Y (不溢出),加减法运算过程中产生的特征位的值,此时C=1，Z=1，S=0,此时C=0，Z=0，S=0,2000:CMP R0,R1 JRNC 2000,2010:DEC R0 JRNZ 2010,26,原码一位乘运算方案,X*Y原 = ( X + Y) (X* Y ) 例如： X = 0.1101 Y = 0.1011 0. 1 1 0 1 * 0. 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 + 1 1 0 1 0 . 1 0 0 0 1 1 1 1 手工运算过程 最终乘积原码表示： 0 1 0 0 0 1 1 1 1,解决方案： 1. 每次求出部分积,不是一

16、次总累加 2. 变每次左移被乘数为右移部分积，移出的部分保存起来 ( 保存到哪 ? ) 3. 乘数放到一个移位寄存器中，判乘数每一位的值用最低的一位线路,符号异或， 绝对值相乘,该方案用于计算机会有问题： 1. 加法器只有两个数据输入端 2. 加法器与乘运算数据位数相同 3. 如何判断乘数每一位是 0 或者 1,27,实现原码一位乘法的逻辑线路图,加 法 器,部 分 积,被 乘 数,乘 数,F,最 低 位,加运算,移位线路 每位1套,第 i 位,第 i 位,第 i +1位,第 i -1位,F/2X FX F*2X,移位电路,最 高 位,三选一电路,被乘数作为加数，用乘数最低位的值控制累加，结果

17、右移一位存部分积寄存器，并且乘数同时右移一位。,部分积的最低位移入到乘数的最高位,计数器 Cd,28,原码一位乘运算过程举例,X = 0.1101 Y = 0.1011,29,原码一位乘运算过程举例,X = 0.1101 Y = 0.1011,30,原码一位乘运算过程举例,X = 0.1101 Y = 0.1011,31,原码一位乘运算过程举例,X = 0.1101 Y = 0.1011,32,原码一位乘运算过程举例,X = 0.1101 Y = 0.1011,33,原码一位乘运算过程举例,X = 0.1101 Y = 0.1011,34,原码一位乘运算过程举例,X = 0.1101 Y =

18、0.1011,35,除法运算,在计算机内实现除法运算时，存在与乘法运算类似的几个问题： 加法器与寄存器的配合，被除数位数较长，商一位一位地计算出来，如何放置商等。 这可以用左移余数得到解决，且被除数的低位部分可以与最终的商合用同一个寄存器，余数与上商同时左移一位。,36,F 加法器,A 被除数(余数),B 除数 1 0,与或门,与或门,2FA,FA,BF,/BF,1F,C 乘商寄存器,上商,与或门,2CC,计数器 Cd,实现原码一位除法运算的原理图,C/2C,37,原码一位除运算, X / Y 原 =( X + Y )（ X Y ) 原码一位除是指用原码表示的数相除，求出原码表示的商。除操作的

19、过程中，每次求出一位商。 从理解原理考虑，用恢复余数除法讲解计算机内的实现方法更直观方便，即确定上商应为还是为时，必须用被除数或中间余数减去除数，通过检查本次求得的余数为正还是为负才能知道，而不象人员计算时用眼睛可以直接看出来。若求出一个为负的余数来，通常应首先恢复其值为正，再求下一位商才有道理。但计算机内从来不用这种办法，而是直接用求得的负余数直接求下一位商。,38,加减交替除法原理证明,1. 若第 i - 1次求商，减运算的余数为 + Ri-1 ，商1， 余数左移 1位得 2Ri-1 。 2. 则下一步第 i 次求商 Ri = 2Ri-1 - Y 恢复余数为正且左移 1位得 2(Ri +

20、Y ) 3. 则再下一步第 i+ 1次求商 Ri+1 = 2( Ri + Y ) - Y = 2Ri + Y 公式表明, 若上次减运算结果为负, 可直接左移, 本次用 +Y 求商即可; 减运算结果为正，用 +Y 求商,39,0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 10 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 01 0 0 0 1 1 1,0 0 0 0 0

21、开始情形 -Y 0 0 0 0 0 0, 商1 0 0 0 1 0 左移1位 -Y 0 0 0 1 1 0, 商1 0 0 1 1 0 左移1位 -Y 0 0 1 1 0 0, 商1,被除数(余数),商,+),+),+),+),+),X=0.1011,Y=0.1101,X / Y = 0.1101,Y补 = 00 1101,-Y补=11 0011,原码除法执行的是绝对值相除, -Y用+-Y补 完成, +Y 用加Y的绝对值 (补码) 完成,除法运算,40,ALU的线路实现方案,ALU用于执行 2 路数据的算术与逻辑运算 例如： +、 等 已经讲过实现这几种运算的算法 例如：补码加减、逻辑运算、原

22、码一位乘除等 还给出了实现这些运算的原理性线路框图,B存放: 加数 被乘数 除数 逻辑数2,A存放: 被加数 高位积 被除数 逻辑数1,乘除运算用加减和移位多次迭代完成,41,4、检错纠错码,要提高计算机的可靠性，除了采取选用更高可靠性的器件，更好的生产工艺等措施之外，还可以针对薄弱环节，从数据编码上想一些办法，即采用少量冗余的线路，在原有数据位之外再增加一到几个校验位，使新得到的由数据位和校验位构成的码字带上某种特性，在经过薄弱环节之后，则通过检查该码字是否仍保持有这一特性，来判断码字中的某一、二位的值是否发生了变化，即是否出现了错误，甚至于定位错误后，自动改正这一错误，这就是我们这里说的检

23、错纠错编码技术。,42,检错纠错码,码距（最小码距）的概念：是指任意两个合法码之间至少有几个二进制位不相同。例如： 仅有一位不同，称最小码距为 1，例如用 4 位二进制表示16 种状态，则 16 种编码都用到了，此时码距为 1，就是说，任何一个编码状态的四位码中的一位或几位出错，都会变成另一个合法码，此时无检错能力。 若用 4 个二进制位表示 8 种合法状态，就可以只用其中的 8 个编码来表示之，而把另 8 种编码作为非法编码，此时可以使合法码的码距为 2。如果一个码字中的任何一位出错后都会成为非法码，则它就有了发现一位出错的能力。 合理增大码距，能提高发现错误的能力，但表示一定数量的合法码所

24、使用的二进制位数要变多，增加了电子线路的复杂性和数据存储、数据传送的数量。,43,非线性码,线性码,卷积码,分组码,非循环码,循环码,随机 错误,突发 错误,纠错码,校验位与信息位 的形成关系,信息位与校验位 的约束条件,码字本身的 结构特点,信息位与校验位排列位置关系,系统码,非系统码,纠错码分类,44,几种常用的检错纠错码,我们只介绍三种常用的检错纠错码： 奇偶校验码：用于并行数据传送中 海明校验码：用于并行数据传送中 循环冗余校验码：用于串行数据传送中,运行过程的 3 步曲：,45,用于并行码检错 原理：在 k 位数据码之外增加 1 位校验位， 使 K+1 位码字中取值为 1 的位数总保

25、持 为 偶数（偶校验）或 奇数（奇校验）。 例如：,奇偶校验码,0 0 0 1 1 0 0 0 1 0 0 0 0 1,0 1 0 1 0 0 1 0 1 1 0 1 0 1,46,奇偶校验码的实现电路,奇较验 偶校验 出错指示,47,海明校验码,用于多位并行数据检错纠错处理 实现：为 k 个数据位设立 r 个校验位，使 k+r 位 的码字同时具有这样两个特性： 能发现并改正 k+r 位中任何一位出错； 能发现 k+r 位中任何二位同时出错， 但已无法改正。 k 与 r 之间应该满足什么样的关系 ？,48,海明码的编码方法,合理地用 k 位数据位形成 r 个校验位的值，即保证用 k 个数据位中

26、不同的数据位组合来形成每个校验位的值，使任何一个数据位出错时，将影响 r 个校验位中不同的校验位组合起变化。这样一来，就可以通过检查是哪种校验位组合起了变化，来推断是哪个数据位错造成的，对该位求反则实现纠错。 有时两位出错与某种情况的一位出错对校验位组合的影响相同，必须加以区分与解决。 位数 r 和 k 的关系： 2r k+r+1, 即用 2r 个编码 分别表示 k个数据位、r个校验位中哪一位错，都不错 2r-1 k+r ，用 r-1 位校验码为出错位编码，再单独设一位用于区分 1 位还是 2 位同时出错，更实用,49,P1 = D2 D1 P2 = D3 D1 P3 = D3 D2,海明码的

27、实现方案 例如: k =3, r =4,D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1,P4 = P3 P2 P1 D3 D2 D1,S1 = P1 D2 D1 S2 = P2 D3 D1 S3 = P3 D3 D2 S4 = P4 P3 P2 P1 D3 D2 D1, 表示异或,编码方案,译码方案,50,（一）准备工作： (1) 按次序排列数据位、校验位， (2) 分别在不同横行中的P1、P2、P3、P4各列写 1, (3) 在 P1 P2 P3 各列低 3 横行中的其他位置填写 0,

28、(4) 在最顶横行其他各列填写 1；,海明码的实现方案 例如： k =3, r =4 如何通过一张表分配不同的数据位组合来形成每个校验位的值,D3 D2 D1 P4 P3 P2 P1,编码方案,D3 D2 D1 P4 P3 P2 P1 1 0 1 0 0 0 0 1 0 0 0 0 1,1 1 1 1,D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1,51,（二）为各校验位分配数据位组合： (1) 看表的低 3 横行右侧 4 列各列的编码值分别为： 1 (001)、2 ( 010) 、4 (100) 、0 (000) (2)

29、为低 3 横行左侧 3 列各列填写合理的编码值，其 规则是，使用没出现在右侧 4 列的最小正整数值 即 3 (011)、5 (101)、6 (110)。,海明码的实现方案 例如： k =3, r =4 如何通过一张表分配不同的数据位组合来形成每个校验位的值,编码方案,D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1,0 4 2 1,6 5 3,52,（三）写出各校验位的编码逻辑表达式： (1) 用 P1、P2、P3 取值为 1 的横行中那些取值为 1 的 数据位进行异或运算求得每个校验位的值; 结果是: P1 = D2 D1；

30、 P2 = D3 D1； P3 = D3 D2 (2) 用其他各校验位及各数据位进行异或运算求校验位 P4 的值，用于区分无错、奇数位错、偶数位错 3 种情况 总校验位 P4 = P3 P2 P1 D3 D2 D1,海明码的实现方案 例如： k =3, r =4 如何通过一张表分配不同的数据位组合来形成每个校验位的值,编码方案,D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1,53,P1 = D2 D1 P2 = D3 D1 P3 = D3 D2,海明码的实现方案 例如： k =3, r =4 设计结果为：,D3 D2 D1

31、P4 P3 P2 P1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1,P4 = P3 P2 P1 D3 D2 D1,S1 = P1 D2 D1 S2 = P2 D3 D1 S3 = P3 D3 D2 S4 = P4 P3 P2 P1 D3 D2 D1,：异或,编码方案,译码方案,译码方案是： 对接收到数据位再次编码，用得到的结果和传送过来的校验位的值相比较，结果分别用 S4S1 表示，二者相同表明无错，不同是有 1 位错了。 排查是哪一位错了，看 S4S1 这4 位的编码值。,54,海明码的应用实例,若无错，则 S4 S3 S2

32、 S1=0000 4 位 S 全为 0,如已有数据为 110，则有： P1=1，P2=1 P3=0，P4=0 请看如下 3 种情况： 无错， 单独 1 位错， 2 位同时错,若P2 D1错，则 S4 S3 S2 S1=0001 其中 S4 必为 0, S3S2S1 不为 000,若仅 D1 错，则 S4 S3 S2 S1=1011 4位 S中 3位为 1 其中 S4 必为 1,55,循环冗余校验码（CRC）介绍,用于多位串行数据传送中的检错、纠错处理，在 k 位数据位串行移位输出的过程中， 用带有异或门控制的移位寄存器形成 r 个校验位的值，跟随在数据位之后传送走。 在接收端再对 k+r 位的

33、码字进行合法与出错检查，若可能则自动改错。,56,检错纠错码小结,k 位码有 2K 个编码状态，全用于表示合法码，则任何一位出错, 均会变成另一个合法码，不具有检错能力。 (2) 从一个合法码变成另一个合法码，至少要改变几位码的值，称为最小码距 (码距)，码距和编码方案将决定其检错就错能力。 奇偶校验码的码距为 2， 常用的海明码和循环冗余码的码距为 4。,57,检错纠错能力,k+1 位码，只用其 2k 个状态，可以使码距为 2 , 如果一个合法码中的一位错了，就成为非法码， 通过检查码字的合法性，就得到检错能力，这就是奇偶校验码，只能发现1位错，不具备纠错能力。 (4) 对 k 位数据位，当给出 r 位校验位时， 要发现并改正一位错，须满足如下关系： 2r k + r +1 要发现并改正一位错，也能发现两位错，则应： 2r-1 k + r,