计算机组成原理第2章

1、1 第二章第二章 数据的表示和运算数据的表示和运算 2 2.1 2.1 数据的编码数据的编码 一、数制及其转换一、数制及其转换 1 1、进位记数制进位记数制 * *进位记数制进位记数制：又称进制或数制，是用一组固定的符号和统一又称进制或数制，是用一组固定的符号和统一 的规则来表示数值的方法的规则来表示数值的方法。参数参数有数码、基数和位权有数码、基数和位权 * *常用的常用的4 4种进制种进制： 二进制二进制八进制八进制十进制十进制十六进制十六进制 数码数码0,10,10,1,70,1,70,1,90,1,90,1,9,0,1,9,A,B,FA,B,F 基数基数2 28 810101616 位

2、权位权2 2i8 8i1010i1616i 书写形式书写形式B BO OD DH H * *R进制数表示：进制数表示：( (N N ) )R=(=(kn-1 -1 k1 1k0 0. .k-1 -1k-2-2 k- -m m) )R= 其中，其中，ki0,1,(0,1,(R-1)-1) 1n- mi i i Rk 3 2 2、R进制数进制数十进制数转换十进制数转换 例例11( (101.01101.01) )2 2 =( =(1 12 22 2+ +1 12 20 0+ +1 12 2-2 -2) )10 10=( =(5.25)5.25)10 10 ( (3A.C3A.C) )16 16 =

3、( =(3 316161 1+ +101016160 0+ +12121616-1 -1) )10 10=(58.75) =(58.75)10 10 3 3、十进制数十进制数R进制进制数转换数转换 (1)(1)十进制整数十进制整数R进进制整数转换制整数转换 例例22 余数余数 2 19 2 19 1 (1 (最低位最低位) ) 2 9 2 9 1 1 2 4 2 4 0 0 2 2 2 2 0 0 2 1 2 1 1 (1 (最高位最高位) ) 0 0 (19) (19)10 10=( =(1001110011) )2 2 余数余数 8 19 8 19 3 (3 (最低位最低位) ) 8 2

4、8 2 2 (2 (最高位最高位) ) 0 0 (19) (19)10 10=( =(2323) )8 8 * *转换规则：转换规则：按位权展开按位权展开 * *整数转换规则：整数转换规则：除基取余除基取余、上右下左上右下左 4 (2)(2)十进制小数十进制小数R进进制小数转换制小数转换 整数部分整数部分 0.68750.68752 = 2 = 1 1.375 .375 1 (1 (最高位最高位) ) 0.375 0.375 2 = 2 = 0 0.75 .75 0 0 0.75 0.75 2 = 2 = 1 1.5 .5 1 1 0.5 0.5 2 = 2 = 1 1.0 .0 1 (1 (

5、最低位最低位) ) (0.6875) (0.6875)10 10 = (0. = (0.10111011) )2 2 整数部分整数部分 0.68750.68758 = 8 = 5 5.5 .5 5 (5 (最高位最高位) ) 0.5 0.5 8 = 8 = 4 4.0 .0 4 4 ( (最低位最低位) ) (0.6875)(0.6875)10 10 = (0. = (0.5454) )8 8 例例33将将(0.6875)(0.6875)10 10分别转换成二、八进制数 分别转换成二、八进制数 (3)(3)十进制数十进制数R进制进制数转换数转换 * *转换规则：转换规则：整数部分、小数部分整数

6、部分、小数部分分别转换后再合并分别转换后再合并 练习练习11(19.6875)(19.6875)10 10=(X) =(X)2 2=(Y)=(Y)8 8，X=X=？Y=Y=？ * *小数转换规则：小数转换规则：乘基取整乘基取整、上左下右上左下右 5 4 4、二、八、十六进制数相互转换、二、八、十六进制数相互转换 * *数位长度关系：数位长度关系：1 1个八进制、十六进制数位个八进制、十六进制数位3 3 bitbit、4 4 bitbit * *转换规则转换规则：从从小数点向两边小数点向两边分别分别转换，转换， 数位不够数位不够时时补零、无效的零删除补零、无效的零删除 例例44(13.724)(

7、13.724)8 8=(=(00001 1 011.111011.111 010010 1 10000) )2 2=(1011.1110101)=(1011.1110101)2 2 (10011.01)(10011.01)2 2=(=(0 01010 011.01011.010 0) )2 2=(23.2)=(23.2)8 8 例例55(2B.E)(2B.E)16 16=( =(00001010 1011.1111011.1110 0) )2 2=(101011.111)=(101011.111)2 2 (11001.11) (11001.11)2 2=(=(0000001 1 1001.11

8、1001.110000) )2 2=(19.C)=(19.C)16 16 练习练习22(21.75)(21.75)10 10 (X)(X)2 2(Y)(Y)8 8(Z)(Z)16 16， ，X=X=？Y=Y=？Z=Z=？ (2D.E) (2D.E)16 16 (A)(A)2 2(B)(B)8 8(C)(C)10 10， ，A=A=？B=B=？C=C=？ 6 二、机器数及其编码二、机器数及其编码 * *数值数据：数值数据：组成组成 符号符号+数值数值+小数点小数点+ +数值数值 运算运算符号与数值符号与数值分开运算分开运算，减法减法先先比较大小比较大小 * *机器数：机器数：计算机内部计算机内部

9、编码表示编码表示的的数值数据数值数据 如如(+101)(+101)2 2(0 0101)101)2 2、(-101)(-101)2 2(1 1101)101)2 2 真值真值数学上带数学上带+/-+/-号的数值数据号的数值数据 * *机器数的编码方法：机器数的编码方法： 运算方法分析运算方法分析采用采用手工运算方法手工运算方法，硬件实现，硬件实现困难困难 采用采用新运算方法新运算方法，以利于以利于硬件实现硬件实现 编码方法编码方法原码、补码、反码、移码原码、补码、反码、移码等，等， 均用均用二进制二进制表示表示 硬件仅硬件仅0/10/1两个状态两个状态 符号符号/ /数值一起运算数值一起运算

10、减法不比较大小减法不比较大小 新的编码方法新的编码方法 表示可缺省表示可缺省 7 1 1、原、原码码( (Sign-magnitude) )表示法表示法 * *基本思想：基本思想：机器数机器数最高位最高位表示真值表示真值的的符号符号(0/1(0/1表示表示+/-)+/-)， 其余位其余位为真值的绝对值为真值的绝对值 * *整数原码定义：整数原码定义： 设设X= =xn-2 n-2 x0 0，则，则 X 原 原= =xn-1n-1xn-2n-2 x0 0， X 原 原 = = X 00X2 2n-1 n-1 2 2n-1 n-1 - - X = = 2 2n-1n-1 +| +|X| -2| -

11、2n-1 n-1 X00 例例11 + +11011101原 原= =0 01101 1101； - -11011101原 原= =1 11101 1101 例例2 2若若 X 原 原= =1 1101 101，则，则X= =- -101101 例例3 3若若 + +X 原 原= =0 0110 110，则，则 - -X 原 原= =1 1110 110 若若 + +Y 原 原= =0 0000 000，则，则 - -Y 原 原= =1 1000 000 +00原 原 -0-0原 原 练习练习11若若X=-01000=-01000，则，则 X 原 原= =？ ？ 若若 Y 原 原=101010

12、 =101010，则，则Y= =？ 符号位符号位 数值位数值位 8 * *小数原码定义：小数原码定义： 设设X= =0.0.x-1 -1 x-(n-1 -(n-1) )， ，则则 X 原 原= =x0 0. .x-1-1 x-(n-1) -(n-1) X 原 原 = = X 00X1 1 1-1-X=1+|=1+|X| -1| -1X00 例例44 +0+0.1001.1001原 原= =0 0.1001 .1001； -0-0.1001.1001原 原= =1 1.1001 .1001 例例5 5若若 X 原 原= =1 1.01 .01，则，则X= =-0-0.01.01 * *原码的特性

13、：原码的特性： X与与 X 原 原关系 关系 X 原 原与 与X表示值的范围相同，表示值的范围相同， +0+0原 原 -0-0原 原 运算方法运算方法符号与数值符号与数值分开运算分开运算( (与手工运算一致与手工运算一致) ) 适合于乘除法，适合于乘除法，加减法较复杂加减法较复杂 编码时编码时0 0可省略可省略 9 2 2、补码补码( (Twos complement) )表示表示法法 * *编码目标：编码目标：符号与数值符号与数值一起一起运算运算，减法，减法无需比较大小无需比较大小 * *有模运算：有模运算：运算只计量运算只计量小于小于“模模”的的部分，多余部分被丢弃部分，多余部分被丢弃 模

14、模计量系统的计数计量系统的计数范围范围 (1)(1)有模运算与补数有模运算与补数 示例示例时针从时针从1010点拨向点拨向7 7点：点：10-3=710-3=7；10+9=7+12=710+9=7+12=7 * *补数：补数：若若a、b、M满足满足a+ +b= =M，称，称a、b互为模互为模M的的补数补数 同余同余若若A、B、M满足满足A=B+kM ( (k为有符号整数为有符号整数) )， 则记则记 AB ( (mod M) )，称，称B和和A为模为模M的同余的同余 运算特征运算特征c- -a = = c-(-(M- -b) ) = = c+ +b (mod (mod M) )， 即即减去减去

15、一个数一个数等价于加上等价于加上这个数的补数这个数的补数 可将可将减法运算减法运算转化为转化为加法运算加法运算 10 * *减法无需比较大小减法无需比较大小的编码的编码思路思路： 负数负数用其正补数表示用其正补数表示，正数正数用其本身表示用其本身表示 示例示例 -48 (mod 12) -48 (mod 12)，+88 (mod 12)+88 (mod 12) 减法减法时，减数用其取负后编码表示、进行加法运算时，减数用其取负后编码表示、进行加法运算 示例示例9-45 9-45 (mod 12(mod 12) )，4-97 (mod 12)4-97 (mod 12) (2)(2)补码定义补码定义

16、 * *基本思想：基本思想：机器数机器数最高位最高位表示表示X的的符号符号(0/1(0/1表示表示+/-)+/-)， 其余其余位位为为| |X| |或或| |X| |的补的补数数 * *整数补码定义：整数补码定义： 设设X= =xn-2 n-2 x0 0，则，则模为模为2 2n n， X 补 补= =xn-1n-1xn-2n-2 x0 0，即，即 X 补 补 = = 2 2n n +X (mod 2 +X (mod 2n n) ) = = X 00X2 2n-1 n-1 2 2n n + +X=2=2n n -|-|X| -2| -2n-1 n-1 X0 0 说明说明为实现为实现“负数的负数的

17、xn-1 -1=1 =1”，模须为模须为2 2n n( (不是不是2 2n-1 n-1) ) 11 练习练习22若若X=-01000=-01000、Y=+01000=+01000， X 补 补= =？ ？ Y 补 补= =？ ？ 例例77n=5n=5、X00时时， X 补 补最大 最大= =0 011111111，Xmax max=2 =24 4-1=+15-1=+15 X0 0时时， X 补 补最小 最小=1 100000000，Xmin min=-2 =-24 4 =-16 =-16 原码原码 无无 1 1111 111 1 1001 001 1 1000000 0 0000 000 0

18、0001 001 0 0111111 补码补码 1 1000 000 1 1001 001 1 1111 111 0 0000 000 0 0001 001 0 0111111 真值真值 -2-2n-1 n-1 -(2 -(2n-1 n-1-1) -1) -1 -1 0 0 +1 +(2+1 +(2n-1 n-1-1) -1) +0000 +0000补 补=-0000 =-0000补 补=00000 =00000 数数0 0的补码惟一的补码惟一 补码表示数的个数比原码多补码表示数的个数比原码多1 1个个 例例66+0001+0001补 补=00001 =00001，-0001-0001补 补=

19、 =10 10 00000000+(-0001)=+(-0001)=1111111111 +1111 +1111补 补=01111 =01111，-1111-1111补 补= =10 10 00000000+(-1111)=+(-1111)=1000110001 2 25 5 最高位为最高位为1 1 12 * *小数补码定义：小数补码定义： 设设X= =0.0.x-1 -1 x-(n-1) -(n-1)，则 ，则 X 补 补= =x0 0. .x-1-1 x-(n-1) -(n-1) X 补 补 = = 2+ 2+X (mod 2) (mod 2) = = X 00X1 1 2+2+X=2-|

20、=2-|X| -1| -1X0 0 例例88+0.1011+0.1011补 补=0.1011 =0.1011 -0.1011 -0.1011补 补=2-0.1011= =2-0.1011=1010.0000-0.1011=1.0101.0000-0.1011=1.0101 10 说明说明模为模为2(2(不是不是1 1) )为为实现实现“负数负数的的x0 0=1=1” * *符号与数值一起运算符号与数值一起运算的原理分析：的原理分析：仅考虑不溢出情况仅考虑不溢出情况 0100(+4) 0100(+4) 1111(-1) 0101(+5) 1011(-5)1111(-1) 0101(+5) 101

21、1(-5) + + 0011(+3)0011(+3) + 1100(-4)+ 1100(-4) + + 1100(-41100(-4) ) + + 0100(+40100(+4) ) 0 0111(+7) 111(+7) 1 1011(-5) 011(-5) 001(+1) 001(+1) 111(-1)111(-1) 结果正确结果正确同号加同号加符号不变，符号不变，异号加异号加符号同绝对值较大者符号同绝对值较大者 13 设设X= =- -xn-2 n-2 x0 0， Y 补 补= =1 1yn-2n-2 y0 0，xi i及及yi i=0=0或或1 1 则则 X 补 补 = = 2 2n n

22、+ +X = = 2 2n-1 n-1+(2 +(2n-1 n-1-1)+1+ -1)+1+X = 1 0 = 1 0 0 + 10 + 1 1 1 + + 1 = 1 1 = 1 0 0 0 0 - - xn-2 n-2 x0 0 + + xn-2 n-2 x0 0 + 1 + 1 = = 1 1 xn-2 n-2 x0 + + 1 1 (3)(3)补码的特性补码的特性 * *X与与 X 补 补的关系 的关系：下述方法同样适用于纯小数下述方法同样适用于纯小数 设设X= =+ +xn-2 n-2 x0 0， Y 补 补= =0 0yn-2n-2 y0 0，xi i及及yi i=0=0或或1 1

23、 则则 X 补 补 = = X = = 0 0 xn-2 n-2 x0 Y = = Y 补 补 = = + + yn-2n-2 y0 0 Y =Y 补 补-2 -2n n = = 1 1yn-2 n-2y0 0-2 -2n-1 n-1+(2 +(2n-1 n-1-1)+1 -1)+1 = = 2 2n-1 n-1-2 -2n-1 n-1 -( -( 1111 - - yn-2 n-2 y0 0 + + 1 1 ) ) = = -(-( yn-2 n-2 y0 0 + + 1 1 ) ) 14 XX 补 补 若若X为为正数正数，改符号位为，改符号位为0 0，其余各位不变；，其余各位不变； 若若X

24、为为负数负数，改符号位为，改符号位为1 1，其余各位取反、末位加，其余各位取反、末位加1 1 例例99X=+0101=+0101， X 补 补= = X=-0101=-0101， X 补 补= =0 0 01010101； 1 1 1011011 1 X 补 补 X 若若 X 补 补最高位为 最高位为0 0，改其为正号，其余各位不变；改其为正号，其余各位不变； 若若 X 补 补最高位为 最高位为1 1，改其为负号，其余各位取反、末位加改其为负号，其余各位取反、末位加1 1 例例1010 X 补 补=0 =0 01010101，X=+=+ 01010101； X 补 补=1 =1 1011101

25、1，X= = - - 0100101 1 15 X 原 原 X 补 补 若若 X 原 原最高位为 最高位为0 0， X 补 补= =X 原 原； ； 若若 X 原 原最高位为 最高位为1 1， X 补 补= =X 原 原各数值位 各数值位取反、末位加取反、末位加1 1 例例1111 X 原 原=0 =0 0101,0101,X 补 补= = 0 0 0101 0101； X 原 原=1 =1 0101,0101,X 补 补= = 1 1 101 1011 1 X 补 补 X 原 原 若若 X 补 补最高位为 最高位为0 0， X 原 原= =X 补 补； ； 若若 X 补 补最高位为 最高位为

26、1 1， X 原 原= =X 补 补各数值位 各数值位取反、末位加取反、末位加1 1 例例1212 X 补 补=0 =0 0101,0101,X 原 原= = 0 0 0101 0101； X 补 补=1 =1 0101,0101,X 原 原= = 1 1 101 1011 1 符号位符号位( (最高位最高位) )不变不变 符号位符号位( (最高位最高位) )不变不变 16 * * X 补 补与 与-X 补 补的关系： 的关系： 设设 X 补 补= =xn-1n-1xn-2n-2 x0 0，则，则 当当X00时时，X = = X 补 补，其中 ，其中xn-1 n-1=0 =0， -X 补 补

27、= = 1 1xn-2n-2 x0 0 +1+1 = = xn-1 n-1xn-2n-2 x0 0 +1+1 X 补 补 -X 补 补 X 补补的各位取反 的各位取反( (含符号位含符号位) )、末位加、末位加1 1 - -X 补 补 X 补 补 -X 补 补的各位取反 的各位取反( (含符号位含符号位) )、末位加、末位加1 1 例例1313 X 补 补=1 =1 01100110，-X 补 补= = 0 0 1001+1 1001+1 = = 0 0 10101010 练习练习33若若X=-01001=-01001，-X 补 补= =？ ？ 若若 X 补 补=101010 =101010，

28、-X 补 补= =？ ？- -X= =？ 当当X0 0时时， X 补 补 = = 2 2n n -| -|X| |，其中，其中xn-1 n-1=1 =1， -X 补 补 =| =|X|=|= 2 2n n -X 补 补= =111 111-X 补 补+1 +1 = = xn-1 n-1xn-2n-2x0 0 +1 +1 17 0 0 0100101001 0 0 0100101001 练习练习44 若若X=+01001=+01001， X 原 原= = ， X 补 补= = 若若X=-01010=-01010， X 原 原= = ， X 补 补= = 1 1 0101001010 1 1 10

29、11010110 + + 0101001010 0 0 0101001010 若若 X 原 原=001010 =001010，X= = ， X 补 补= = 若若 X 原 原=101110 =101110，X= = ， X 补 补= = - - 0111001110 1 1 1001010010 + + 0111001110 1 1 1001010010 若若 X 补 补=001110 =001110，X= = ，-X 补 补= = 若若 X 补 补=101110 =101110，X= = ，-X 补 补= = - - 1001010010 0 0 1001010010 0 0 1010110

30、101 0 0 1010110101 若若-X 补 补=101011 =101011， X 补 补= = ， X 原 原= = 若若-X 补 补=001001 =001001， X 补 补= = ， X 原 原= = 1 1 1011110111 1 1 0100101001 714 18 3 3、反码反码( (Ones complement) )表示表示法法 * *编码目标编码目标：作为原码与补码相互转换时的一种作为原码与补码相互转换时的一种过渡编码过渡编码 * *整数反码定义整数反码定义：设设X= =xn-2 n-2 x0 0，取模，取模=2=2n n-1-1，则，则 X 反 反 = =

31、(2 (2n n-1)+-1)+X (mod 2 (mod 2n n-1)-1) = = X 00X2 2n-1 n-1 (2(2n n-1)+-1)+X -2 -2n-1 n-1 X00 * *小数反码定义小数反码定义：设设X= =0.0.x-1 -1 x-(n-1) -(n-1)，模 ，模=2-2=2-2-(n-1) -(n-1)，则 ，则 X 反 反 = = (2-2 (2-2-(n-1) -(n-1) ) + + X (mod 2-2 (mod 2-2-(n-1) -(n-1) ) = = X 00X1 1 (2-2(2-2-(n-1) -(n-1)+ )+X -1 -1X00 例例1

32、414+1101+1101反 反=01101 =01101，-1101-1101反 反=10010 =10010 10 例例1515+0.1101+0.1101反 反=0.1101 =0.1101，-0.1101-0.1101反 反=1.0010 =1.0010 * *反码与补码关系反码与补码关系：若若X为为正数正数， X 补 补= =X 反 反； ； 若若X为为负数负数， X 补 补= =X 反 反+1 +1 19 11 原码、补码、反码比较：原码、补码、反码比较： 机器数的机器数的最高位最高位均为符号位均为符号位(0/1(0/1表示正表示正/ /负负) ) 原码原码 无无 1 1111 1

33、11 1 1001 001 1 1000000 0 0000 000 0 0001 001 0 0111111 反码反码 无无 1 1000 000 1 1110 110 1 1111111 0 0000 000 0 0001 001 0 0111111 补码补码 1 1000 000 1 1001 001 1 1111 111 0 0000 000 0 0001 001 0 0111111 真值真值 -2-2n-1 n-1 -(2 -(2n-1 n-1-1) -1) -1 -1 0 0 +1 +(2+1 +(2n-1 n-1-1) -1) +0+0补 补=-0 =-0补 补，补码比原码、反码

34、 ，补码比原码、反码多表示多表示一个负数一个负数 若真值若真值X为为正数正数， X 原 原= =X 补 补= =X 反 反 若若真值真值X为为负数负数， X 补 补= =X 原 原数值位各位求反、末位 数值位各位求反、末位+1+1 X 反 反= =X X 原 原数值位各位求反 数值位各位求反 移码移码 0 0000 000 0 0001 001 0 0111 111 1 1000 000 1 1001 001 1 1111111 20 4 4、移码表示法、移码表示法 * *编码目标：编码目标：数数( (含符号及数值含符号及数值) )连续时，编码连续连续时，编码连续 * *整数移码定义：整数移码

35、定义： 设设X= =xn-2 n-2 x0 0，取模，取模=2=2n n、偏移量、偏移量=2=2n-1 n-1，则 ，则 X 移 移 = = 2 2n-1 n-1+ +X (mod 2 (mod 2n n) ) = = 2 2n-1 n-1 + + X -2 -2n-1 n-1 X2 2n-1 n-1 例例1616-111-111移 移=0001 =0001，-001-001移 移=0111 =0111， 000000移 移=1000 =1000， +001+001移 移=1001 =1001，+111+111移 移=1111 =1111，-1000-1000移 移=0000 =0000 补码

36、补码 1 1000 000 1 1001 001 1 1111 111 0 0000 000 0 0001 001 0 0111111 移码移码 0 0000 000 0 0001 001 0 0111 111 1 1000 000 1 1001 001 1 1111111 真值真值 -2-2n-1 n-1 -(2 -(2n-1 n-1-1) -1) -1 -1 0 +1 +(20 +1 +(2n-1 n-1-1) -1) * *移码的特性：移码的特性： 数在数轴上为数在数轴上为连续编码连续编码( (似无似无符号数符号数) )，便于比较，便于比较大小大小 X 移 移= =X 补 补符号位取反、

37、其余各位不变 符号位取反、其余各位不变 21 三、十进制数编码三、十进制数编码 * *BCDBCD码码( (Binary Coded Decimal) )：又称又称二二- -十进制编码十进制编码，是指，是指 用用4 4位二进制编码表示位二进制编码表示1 1位十进制数位的编码方式位十进制数位的编码方式 * *BCDBCD码种类：码种类：分分有权码有权码和和无权码无权码两种，最常用的是两种，最常用的是84218421码码 十进制数十进制数0 01 12 23 34 45 56 67 78 89 9 84218421码码00000000 00010001 00100010 00110011 0100

38、0100 01010101 01100110 01110111 10001000 10011001 余余3 3码码00110011 01000100 01010101 01100110 01110111 10001000 10011001 10101010 10111011 11001100 BCDBCD码缺省时指码缺省时指84218421码码( (特殊声明除外特殊声明除外) )！ * *十进制数的编码方法：十进制数的编码方法： 对各数位按序用对各数位按序用BCDBCD码编码，符号编码放在最后；码编码，符号编码放在最后； 用用特定编码特定编码表示符号表示符号( (如如11001100和和110

39、11101表示正和负表示正和负) ) 例例 + +427427表示为表示为0100 0010 0111 0100 0010 0111 11001100 - -123123表示为表示为0001 0010 0011 0001 0010 0011 11011101 22 四、字符及字符串编码四、字符及字符串编码 1 1、字符编码、字符编码 * *字符编码：字符编码：字符在字符在中中惟一惟一的的数字化数字化代码，代码， 表示字符在字符集中的表示字符在字符集中的序号序号或或特征号特征号 * *字符编码的类型：字符编码的类型：有输入码、内码、交换码、字模码有输入码、内码、交换码、字模码4 4种种 键盘键盘

40、 计算机计算机B B 转换转换 处理处理 传送传送 字模码字模码 内内 码码输入码输入码 交换码交换码 显示器显示器 传送传送 计算机计算机A A 交换码交换码 内内 码码 内内 码码 字符字符 数据数据 字符字符 字模库字模库 MEMMEM 交换码交换码 字符字符传送时传送时的编码的编码( (序号序号),), 仅与字符集大小有关仅与字符集大小有关 与输入法、字与输入法、字 符集大小有关符集大小有关 与字体、字号大小有关与字体、字号大小有关 字符字符存储时存储时的编码的编码( (数据数据表示表示),), 与字符集大小、存储器字长有关与字符集大小、存储器字长有关 23 * *有关字符编码的有关字

41、符编码的： 字符编码字符编码均指均指交换码交换码的编码！的编码！ 字符数据字符数据均指均指内码内码的编码！的编码！ * *常见字符编码常见字符编码( (交换码交换码) )种类：种类： 编码种类编码种类 码点码点 数量数量 编码编码 长度长度 说明说明 ASCIIASCII码码1281287 7美国标准信息交换码，英文，使用最广泛美国标准信息交换码，英文，使用最广泛 EBCDICEBCDIC码码2562568 8扩展二扩展二- -十进制交换码，英文，十进制交换码，英文，IBMIBM定义定义 UnicodeUnicode码码65536655361616统一字符码，支持各国语言，使用较广泛统一字符码

42、，支持各国语言，使用较广泛 ANSIANSI码码2562568 8美国国家标准协会交换码，英文，含美国国家标准协会交换码，英文，含ASCIIASCII码码 GB2312-80GB2312-80744574451414汉字国标码，中文汉字国标码，中文 码点数量码点数量需编码的信息数量；需编码的信息数量； ( (如交换码指字符数，字模码指字符点阵数如交换码指字符数，字模码指字符点阵数) ) 编码长度编码长度采用等长编码，长度采用等长编码，长度= log= log2 2 码点数量码点数量 ，UnicodeUnicode可变长可变长 24 2 2、字符串编码、字符串编码 * *字符串特性：字符串特性：

43、 由多个字符由多个字符构成构成 所含字符数不固定所含字符数不固定 * *字符串编码方法：字符串编码方法： 由各个字符编码由各个字符编码组成组成 通过通过特定编码特定编码标志字符串的结束，结束编码放在最后标志字符串的结束，结束编码放在最后 字符集必须包含该字符字符集必须包含该字符( (如如ASCIIASCII码中编码为码中编码为0 0的字符的字符) ) 例例字符串字符串“amam”的的ASCIIASCII编码编码为为1100001 1101101 1100001 1101101 00000000000000 作业一：作业一：P78P787927927 7 25 * *冗余校验思想：冗余校验思想：

44、 用用待发待发数据数据(M)(M)形成形成校验位校验位( (P)P)，M M与与P P一起一起传送传送 用用接收接收数据数据(M(M) )形成形成新新校验位校验位( (P P”) )，用，用P P及及P P”检错检错/ /纠错纠错 五、校验码五、校验码 存储器存储器 或或 传输传输 线路线路 M 函数函数f P 输出方输出方 比较器比较器 P” P 纠正器纠正器 M 函数函数f M 输入方输入方 状态状态 * *术语：术语：校验码校验码由由数据数据和和校验校验位位组成的组成的信息编码信息编码 检错检错( (检验检验)检查检查数据在传送过程中数据在传送过程中有有/ /无无错误错误 纠错纠错( (

45、校正校正)根据根据错误位置错误位置纠正数据纠正数据 * *常见校验码：常见校验码：奇偶校验码、海明校验奇偶校验码、海明校验码，循环码，循环冗余校验码冗余校验码 26 1 1、奇偶校验码、奇偶校验码 * *编码原理：编码原理：采用采用1 1位校验位位校验位，使校验码中使校验码中 “1 1”的位数的位数为奇数为奇数 或偶数个或偶数个 * *校验原理：校验原理：检测校验码中检测校验码中 “1 1”的的个数特性个数特性，是否有错是否有错 例例11 数据数据 1010010 1010010 0110100 0110100 1100011 1100011 奇校验码奇校验码 1010010 1010010

46、0110100 0110100 1100011 1100011 偶校验码偶校验码 1010010 1010010 0110100 0110100 1100011 1100011 有有奇校验奇校验/ /偶偶校验校验方法方法为为奇数奇数/ /偶数偶数个个 * *校验码编码：校验码编码： ( (设数据信息为设数据信息为m mn nm mn-1 n-1m m1 1) ) 校验码组成校验码组成共共n+1n+1位，位， 数据数据m mn nm mn-1 n-1mm1 1校验位校验位p p1 1 异或与模异或与模2 2加加 a b a b = = a+ba+b (mod 2)(mod 2) 校验位编码校验位

47、编码奇奇校验时：校验时：P=pP=p1 1=m=mn n+m+mn-1 n-1+m +m1 1+1 (mod 2)+1 (mod 2) 偶偶校验时：校验时：P=pP=p1 1=m=mn n+m+mn-1 n-1+m +m1 1 (mod 2) (mod 2) 27 * *校验方法：校验方法： 故障字故障字S S S=PS=P P P”，其中，其中P P是接收的、是接收的、P P”是形成是形成的的 检错检错 若若S=0S=0无错误，若无错误，若S=1S=1有有错误错误 纠错纠错 无此无此能力能力 ( (无法获得错误位置无法获得错误位置) ) 例例22 接收的接收的奇校验码奇校验码 故障字故障字S

48、 S 错误位数错误位数( (人工人工) ) 发送码发送码( (参考参考) ) 1 0 1 0 0 1 0 0001 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1?10 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0?10 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0?20 1 1 0 1 1 0 1 * *校验能力：校验能力：只能检测只能检测奇数个奇数个错误，无纠错能力错误，无纠错能力 例例33下列接收的校验码下列接收的校验码0100101001、1010010100、1001110011中，只中，只 有一个有有一个有奇数个错，发送奇数个错，发送时采用的

49、是奇时采用的是奇校验还是偶校验还是偶校验码？校验码？ * *应用：应用：应用于应用于I/OI/O传输传输的数据校验的数据校验 25 28 2 2、海明校验码、海明校验码 * *编码原理：编码原理：将数据分成将数据分成k k个有重叠的组个有重叠的组， 每个组使用一每个组使用一个奇偶校验位个奇偶校验位( (共共k k个校验位个校验位) ) * *校验原理：校验原理：多重奇偶校验多重奇偶校验，即，即某位某位错误错误导致导致多个校验位变化多个校验位变化， 从而实现检错与纠错从而实现检错与纠错( (定位定位) ) * *校验能力目标：校验能力目标：能能检测并纠正检测并纠正1 1位错误位错误 * *校验方

50、法：校验方法： ( (能力目标能力目标方法推导方法推导) ) 设数据设数据M=M=m mn nmm1 1，校验位，校验位P=P=p pk kpp1 1( (即有即有k k个奇偶检验组个奇偶检验组) ) 校验校验码的编码规则码的编码规则? ?k k的长度的长度? ? 故障字故障字S S S=S=s sk kss1 1，s si i=p=pi i p pi i”=p=pi i + + p pi i” (mod 2)(mod 2) 检错检错 若若S=0S=0无错误，无错误，S0S0有有错误错误 纠错纠错 S S值表示错误位置值表示错误位置( (共有共有n+kn+k种种) )，信息信息取反取反 26

51、校验码常称为校验码常称为单纠单纠 错码错码SECSEC 29 * *校验位位数校验位位数k k的确定：的确定： 校验能力目标要求校验能力目标要求 2 2k k-1n+k-1n+k，其中其中n+kn+k表示表示1 1位错误种类位错误种类 n n1 12 24 45 51111 12122626 27275757 5858120120 k(k(最小值最小值) )2 23 34 45 56 67 7 k k的取值的取值 * *校验码编码规则：校验码编码规则： ( (以以4 4个校验组为例个校验组为例) ) 故障字故障字S S值的约定值的约定S0S0时表示错误位置，时表示错误位置，S S值有值有n+k

52、+1n+k+1种种 无无 错错 误误: : 0000 0000 (校验码位置序号从校验码位置序号从1 1开始编号开始编号) ) 校验位错校验位错: : 0001(p0001(p1 1) )、0010(p0010(p2 2) )、0100(p0100(p3 3) )、1000(p1000(p4 4) ) 数据位错数据位错: : S S的其余码值的其余码值(2(2个个s si i=1)=1) 校验码的组成规则校验码的组成规则按按“S S值错误值错误位置位置”规则规则排列信息排列信息 位置序号位置序号 151514141313 1212 1111 10109 98 87 76 65 54 43 32

53、 21 1 信息排列信息排列m m11 11 m m10 10 m m9 9m m8 8m m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1 校验位次重要，校验位次重要，1 1个个s si i=1=1 30 位置及位置及 信息信息 校验组校验组 1515141413131212111110109 98 87 76 65 54 43 32 21 1 11111111 11101110 11011101 11001100 10111011 10101010 10011001 10001000 01110111 0110

54、0110 01010101 01000100 00110011 00100010 00010001 m m11 11 m m10 10 m m9 9m m8 8m m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1 第第4 4组组 第第3 3组组 第第2 2组组 第第1 1组组 检验位的编码规则检验位的编码规则 ( (缺省为偶校验方式缺省为偶校验方式) ) p p4 4m m11 11+m m1010+m m9 9+m m8 8+m m7 7+m m6 6+m m5 5 (mod 2) (mod 2) p p3 3m

55、 m11 11+m m1010+m m9 9+m m8 8 +m m4 4+m m3 3+m m2 2 (mod 2) (mod 2) p p2 2m m11 11+m m1010 +m m7 7+m m6 6 +m m4 4+m m3 3 +m m1 1 (mod 2) (mod 2) p p1 1m m11 11 +m m9 9 +m m7 7 +m m5 5+m m4 4 +m m2 2+m m1 1 (mod 2) (mod 2) * *应用：应用：常应用于常应用于I/OI/O传输、传输、RAIDRAID存储等方面的校验存储等方面的校验 28 信息位加入信息位加入校验组规则校验组规则

56、信息位的位置信息位的位置h hk khh1 1中，中，h hi i=1=1时就时就加入加入第第i i校验校验组组 该信息位错误时该信息位错误时s si i=1=1 31 解：解：2 23 3-1-17+37+3、2 24 4-1-17+4 7+4 校验位位数校验位位数=4=4位；位； 例例55求字符求字符b b的的ASCIIASCII码码(m(m7 7mm1 1=1100010)=1100010)的海明偶校验码。的海明偶校验码。 例例44若数据有若数据有1616位，则海明校验码的校验位最少为多少位位，则海明校验码的校验位最少为多少位? ? 解：解：2 2k k-116+k-116+k，k k最

57、小为最小为5 5位位(2(24 4-1-12020、2 25 5-1-121)21)。 根据故障字约定，校验码排列根据故障字约定，校验码排列m m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1 故偶校验码故偶校验码=m=m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1=1=1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 根据检验位编码规则，得根据检验位编码规则，得 （偶校验方式）（偶校验方式） p p4 4=

58、m=m7 7 m m6 6 m m5 5 =0 =0 p p3 3= = m m4 4 m m3 3 m m2 2 =1=1 p p2 2=m=m7 7 m m6 6 m m4 4 m m3 3 m m1 1=0=0 p p1 1=m=m7 7 m m5 5 m m4 4 m m2 2 m m1 1=0=0 29 32 例例66续例续例5 5，请分析下列接收的海明偶校验码是否有错？错，请分析下列接收的海明偶校验码是否有错？错 误时的位置？误时的位置？1100001101011000011010、1100000100011000001000、1100100100011001001000 解：解：

59、接收的接收的M M=1100010=1100010、P P=0110=0110，可求得，可求得P P”=0100=0100， S=P S=P+P+P”(mod 2)(mod 2)，即无进位的模，即无进位的模2 2加，得加，得S=0010S=0010， 有错误，位置有错误，位置2 2错误错误(p(p2 2位错位错) )，数据，数据M=1100010M=1100010 接收的接收的M M=1100000=1100000、P P=0100=0100，可求得，可求得P P”=0001=0001， S=P S=P+P+P”(mod 2)(mod 2)，得，得S=0101S=0101， 有错误，位置有错误

60、，位置5 5错误错误( (数据位数据位m m2 2错错) )，数据，数据M=11000M=11000 0 0 接收的接收的M M=1101000=1101000、P P=0100=0100，可求得，可求得P P”=0110=0110， S=P S=P+P+P”(mod 2)(mod 2)，得，得S=0010S=0010， 有错误，有错误，p p2 2错错？实际是？实际是m m4 4及及m m2 2位错位错(M(M=110=110 0 0 0)0)！ * *校验能力：校验能力：SECSEC能能检测并纠正检测并纠正1 1位错，最多只可位错，最多只可发现发现2 2位错！位错！ 30 33 3 3、循