计算机组成原理 No4 数据的表示和运算-1

1、计算机组成原理计算机组成原理 Principles of Computer Composition 2 第二部分第二部分 数据的表示和运算数据的表示和运算 n 2.1 数制与编码数制与编码 n 2.2 定点数表示和运算定点数表示和运算 n 2.3 浮点数表示和运算浮点数表示和运算 n 2.4 算术逻辑单元算术逻辑单元ALU 3 2.1 2.1 数制与编码数制与编码 2.1.1 进位计数制及其相互转换进位计数制及其相互转换 2.1.2 真值和机器数真值和机器数 2.1.3 BCD码码 2.1.4 字符与字符串字符与字符串 2.1.5 校验码校验码 42.1 数制与编码数制与编码 n计算机中使用的

2、数据可分成两大类：计算机中使用的数据可分成两大类： 符号数据符号数据: :非数字符号的表示（非数字符号的表示（ASCIIASCII、汉字、图形等）、汉字、图形等） 数值数据数值数据: :数字数据的表示方式（定点、浮点）数字数据的表示方式（定点、浮点） n计算机数字和字符的表示方法应有利于数据的存储、加工计算机数字和字符的表示方法应有利于数据的存储、加工 ( (处理处理) )、传送；、传送； n编码：用少量、简单的基本符号，选择合适的规则表示尽编码：用少量、简单的基本符号，选择合适的规则表示尽 量多的信息，同时利于信息处理（速度、方便）量多的信息，同时利于信息处理（速度、方便） 52.1.1 进

3、位计数制及其相互转换进位计数制及其相互转换 一、数制一、数制 进位计数制进位计数制 进位计数制：进位计数制：用少量的数字符号（也称数码），按先用少量的数字符号（也称数码），按先 后次序把它们排成数位，由低到高进行计数，计满进后次序把它们排成数位，由低到高进行计数，计满进 位，这样的方法称为进位计数制位，这样的方法称为进位计数制 基数：基数：进位制的基本特征数，即所用到的数字符号个进位制的基本特征数，即所用到的数字符号个 数数 例如例如10进制进制 ：09 十个数码表示，基数为十个数码表示，基数为10 权：权：进位制中各位进位制中各位“1”所表示的值为该位的权所表示的值为该位的权 常见的进位制常

4、见的进位制： 2，8，10，16进制进制 62.1.1 进位计数制及其相互转换进位计数制及其相互转换 n十进制十进制(Decimal) b基数基数:10; 符号符号:0,1,2,3,4,5,6,7,8,9 b计算规律计算规律:“逢十进一逢十进一 ”或或“借一当十借一当十” b并列表示并列表示:N10=dn-1dn-2 d1d0d-1d-2 d-m 十进制数的多项式表示十进制数的多项式表示: bN10=dn-1 10n-1 + dn-2 10n-2 + +d1 101 + d0 100 + d-1 10-1 + d-2 10-2 + +d-m 10-M m,n为正整数为正整数,其中其中n为整数位

5、数；为整数位数；m为小数位数。为小数位数。Di表示表示 第第i位的系数位的系数,10i称为该位的权称为该位的权. 123.45 =1102+ 2101+ 3 100 + 410-1+ 510-2 注：注：等式左边为并列表示法，等式右边为多项式表示法等式左边为并列表示法，等式右边为多项式表示法 72.1.1 进位计数制及其相互转换进位计数制及其相互转换 n二二 、进位计数制之间的转换、进位计数制之间的转换 1、R进制转换成十进制的方法进制转换成十进制的方法 b按权展开法按权展开法:先写成多项式先写成多项式,然后计算十进制结果然后计算十进制结果. bN= Kn-1Kn-2 K1K0K-1K-2 K

6、-m =Kn-1 rn-1 + Kn-2 rn-2 + +K1 r1 + K0 r0 + K-1 r-1 + K-2 r-2 + K-m r-m n= 82.1.1 进位计数制及其相互转换进位计数制及其相互转换 n2、十进制转换成二进制方法、十进制转换成二进制方法 10进制到进制到R进制：进制： 整数部分：除整数部分：除r取余，取余，r为进制基数为进制基数 小数部分：乘小数部分：乘r取整取整 十进制转换成二进制十进制转换成二进制,一般分为两个步骤：一般分为两个步骤： 整数部分的转换整数部分的转换 除除2取余法（基数除法）取余法（基数除法） 小数部分的转换小数部分的转换 乘乘2取整法（基数乘法）

7、取整法（基数乘法） 92.1.1 进位计数制及其相互转换进位计数制及其相互转换 n整数部分的转换整数部分的转换 除基取余法：除基取余法：把给定的除以基数把给定的除以基数,取余数作为最低位的系数取余数作为最低位的系数, 然后继续将商部分除以然后继续将商部分除以 基数基数,余数作为次低位系数余数作为次低位系数,重复操重复操 作直至商为作直至商为 0 例如：用基数除法将例如：用基数除法将(327)10转换成二进制数转换成二进制数 2 327 余数余数 2 163 1 2 81 1 2 40 1 2 20 0 2 10 0 2 5 0 2 2 1 2 1 0 2 0 1 (327)(327)10 10

8、 =(101000111) =(101000111) 2 2 102.1.1 进位计数制及其相互转换进位计数制及其相互转换 n小数部分的转换小数部分的转换 乘基取整法：乘基取整法：把给定的十进制小数乘以把给定的十进制小数乘以2,取其整数作为二取其整数作为二 进制小数的第一位进制小数的第一位,然后取小数部分继续乘以然后取小数部分继续乘以2,将所的整数将所的整数 部分作为第二位小数部分作为第二位小数,重复操作直至得到所需要的二进制重复操作直至得到所需要的二进制 小数小数 例如例如: :将将(0.8125) (0.8125) 10 10 转换成二进制小数 转换成二进制小数. . 整数部分整数部分 2

9、 2 0.8125=1.625 10.8125=1.625 1 2 2 0.625=1.25 10.625=1.25 1 2 2 0.25=0.5 0 0.25=0.5 0 2 2 0.5=1 10.5=1 1 (0.8125) (0.8125) 10 10 =(0.1101) =(0.1101) 2 2 112.1.1 进位计数制及其相互转换进位计数制及其相互转换 n3、其它进制之间的直接转换法、其它进制之间的直接转换法 122.1.1 进位计数制及其相互转换进位计数制及其相互转换 n二进制转换成八进制二进制转换成八进制 例：例：(10110111 .01101) 2 (10110111.0

10、1101) (10110111.01101) 2 2 =(267.32) =(267.32)8 8 八进制八进制: 2 6 7 : 2 6 7 . . 3 2 3 2 二进制二进制: : 0 010 ,110 , 111 10 ,110 , 111 . . 011 , 01 011 , 010 0 二进制二进制: 10 ,110 , 111 : 10 ,110 , 111 . . 011 , 01011 , 01 132.1.1 进位计数制及其相互转换进位计数制及其相互转换 n八进制转换二进制八进制转换二进制 n例如例如: (123.46 ) 8 n二进制转换成十六进制二进制转换成十六进制 例

11、：例：(110110111 .01101) 2 (10110111.01101) 2 =(1B7.68)16 十六进制十六进制: 1 B 7 . 6 8 二进制二进制: 0001 ,1011 , 0111 . 0110 ,1000 二进制二进制: 1 ,1011 , 0111 . 0110 ,1 142.1.1 进位计数制及其相互转换进位计数制及其相互转换 n十六进制转换成二进制十六进制转换成二进制 n例如例如: (7AC.DE ) 16 n=(0111,1010,1100.1101,1110 ) 2 n=(11110101100 .1101111 )2 152.1.2 真值和机器数真值和机器

12、数 机器数：机器数：符号数码化的数称为机器数符号数码化的数称为机器数 如如 ： X=01011 Y=11011 机器数的特点：机器数的特点： 1. 数的符号数值化，通常放在二进制数的最高位数的符号数值化，通常放在二进制数的最高位 2. 二进制数的位数受机器设备的限制二进制数的位数受机器设备的限制 真值真值:带符号位的机器数称为真值。带符号位的机器数称为真值。 如如 二进制真值：二进制真值： X=+1011 y=-1011 符号位数值化后，为了能提高对机器数进行算术运符号位数值化后，为了能提高对机器数进行算术运 算、提高运算速度，设置了多种符号位与数值一起编算、提高运算速度，设置了多种符号位与数

13、值一起编 码的方案。最常用的有：码的方案。最常用的有：原码、反码和补码原码、反码和补码 162.1.2 真值和机器数真值和机器数 带符号的数带符号的数 符号数字化的数符号数字化的数 + 0.1011 0 1011 小数点的位置小数点的位置 + 1100 0 1100 小数点的位置小数点的位置 1100 1 1100 小数点的位置小数点的位置 0.1011 1 1011 小数点的位置小数点的位置 真值真值 机器数机器数 17 2.1.3 BCD码码 n1 1、定义：、定义： n用四位二进制代码的不同组合来表示一个十进制数码的编码方用四位二进制代码的不同组合来表示一个十进制数码的编码方 法，称为二

14、法，称为二十进制编码，也称十进制编码，也称BCDBCD码码(Binary Coded (Binary Coded Decimal)Decimal)，或二进码十进数。是一种二进制的数字编码形式，或二进码十进数。是一种二进制的数字编码形式， 用二进制编码的十进制代码。用二进制编码的十进制代码。 nBCDBCD码利用四个位元来储存一个十进制的数码，使二进制和十码利用四个位元来储存一个十进制的数码，使二进制和十 进制之间的转换得以快捷的进行。相对于一般的浮点式记数法进制之间的转换得以快捷的进行。相对于一般的浮点式记数法 ，采用，采用BCDBCD码，既可保存数值的精确度，又可免却使电脑作浮码，既可保存数

15、值的精确度，又可免却使电脑作浮 点运算时所耗费的时间。此外，对于其他需要高精确度的计算点运算时所耗费的时间。此外，对于其他需要高精确度的计算 ，BCDBCD编码亦很常用。编码亦很常用。 18 2.1.3 BCD码码 n2 2、原理、原理 （1 1）二）二十进制编码都采用压缩的十进制串的方法，十进制编码都采用压缩的十进制串的方法， 即四个二进制位的值来表示一个十进制数码。即四个二进制位的值来表示一个十进制数码。 （2 2）各种编码的区别在于选用哪十个状态。选择的原）各种编码的区别在于选用哪十个状态。选择的原 则是：要考虑输入和输出时转换方便；内部运算时，加、则是：要考虑输入和输出时转换方便；内部

16、运算时，加、 减运算规则要尽量简单；在特定场合，可能有其它一些要减运算规则要尽量简单；在特定场合，可能有其它一些要 求。求。 （3 3）从每个二进制位是否有确定的位权区分，可把二）从每个二进制位是否有确定的位权区分，可把二 十进制编码分为有权码和无权码。十进制编码分为有权码和无权码。 19 2.1.3 BCD码码 n3 3、常用、常用BCDBCD编码方式编码方式 n最常用的最常用的BCDBCD编码，就是使用编码，就是使用“0”0”至至“9”9”这十个数值的这十个数值的 二进码来表示。这种编码方式，我们称之为二进码来表示。这种编码方式，我们称之为“84218421码码”。 n对应不同需求，各人亦

17、开发了不同的编码方法，以适应不对应不同需求，各人亦开发了不同的编码方法，以适应不 同的需求。这些编码，大致可以分成有权码和无权码两种同的需求。这些编码，大致可以分成有权码和无权码两种 。 n有权有权BCDBCD码码，如：，如：8421(8421(最常用最常用) )、24212421、5421 5421 n无权无权BCDBCD码码，如：余，如：余3 3码、格雷码码、格雷码 20 2.1.3 BCD码码 n4、二、二十进制（十进制（BCD）有权码）有权码 1、对于有权码，将每位的数码与相应的位权相乘，再求和、对于有权码，将每位的数码与相应的位权相乘，再求和 ，就可以得到它所代表的十进制数值。，就可

18、以得到它所代表的十进制数值。 2、8421码实现加、减运算时的修正规则：码实现加、减运算时的修正规则： （1）4位一组二进制数，两个位一组二进制数，两个8421码表示的数相加之和等于码表示的数相加之和等于 或小于或小于1001，即十进制的，即十进制的9时，不需要修正，在各组内，时，不需要修正，在各组内， 二进制代码相加，仍遵循二进制代码相加，仍遵循“逢二进一逢二进一”的规则。的规则。 （2）4位一组二进制数，两个位一组二进制数，两个8421码相加结果大于码相加结果大于1001（即（即 十进制十进制9）时，则应该对该组的）时，则应该对该组的4位进行位进行“加加6修正修正”，使，使 它向高一组产生

19、进位。它向高一组产生进位。 （3）4位一组二进制数，两个位一组二进制数，两个8421码相加结果大于或等于码相加结果大于或等于 10000（即十进制（即十进制16），而向高一组进位时，则应该对该），而向高一组进位时，则应该对该4 位进行位进行“加加6修正修正” 21 22 2.1.3 BCD码码 3、其它编码方法还有：、其它编码方法还有：2421码、码、5211码、码、4311码和码和84-2-1码码 ( 四位二进制位的位权分别为四位二进制位的位权分别为8、4、-2、-1)等。其最方便等。其最方便 使用的共同特点为：使用的共同特点为： (1) 对于对于2421码、码、5211码、码、4311码，

20、任何两个十进制数位，码，任何两个十进制数位， 采用这三种编码的任何一种编码，它们相加之和等于或大采用这三种编码的任何一种编码，它们相加之和等于或大 于于10时，其结果的最高位向左产生进位，小于时，其结果的最高位向左产生进位，小于10时则不产时则不产 生进位。这一特点有利于实现生进位。这一特点有利于实现“逢十进位逢十进位”的计数和加法的计数和加法 规则。规则。 n(2) 对于对于2421码、码、5211码、码、4311码和码和84-2-1码，任何两个码，任何两个 十进制数位，采用这四种编码的任何一种编码，它们相加十进制数位，采用这四种编码的任何一种编码，它们相加 其和等于其和等于9时，即它们的二

21、进制编码位互为反码，则其结时，即它们的二进制编码位互为反码，则其结 果的四个二进制位一定是果的四个二进制位一定是1111，能较好地体现十进制的按，能较好地体现十进制的按 9 取补与二进制的按取补与二进制的按1取补的对应关系，这对减法很有用取补的对应关系，这对减法很有用 。 23 24 2.1.3 BCD码码 n二二十进制（十进制（BCD）无权码）无权码 无权码中，用的较多的是余无权码中，用的较多的是余3码码(Excess-3 code)和格雷码和格雷码(Gray code)，格雷码又称循环码。，格雷码又称循环码。 1. 余余3码码 （1） 余余3码是在码是在8421码的基础上，把每个代码都加上

22、码的基础上，把每个代码都加上0011而形成的。而形成的。 （2） 普通普通8421码的加法器仍能为余码的加法器仍能为余3码加法器直接利用，具体规则如码加法器直接利用，具体规则如 下：下： （A）若两个十进制数的余）若两个十进制数的余3码相加，如果结果不产生进位，则从所码相加，如果结果不产生进位，则从所 得和值去减得和值去减0011，便得十进制位和的余，便得十进制位和的余3码。码。 （B）若两个十进制数的余）若两个十进制数的余3码相加，如果结果有进位，则其进位正码相加，如果结果有进位，则其进位正 确，确， 但需将所得和值加上但需将所得和值加上0011，才求得十进制数和的余，才求得十进制数和的余3

23、码。码。 25 2.1.3 BCD码码 n2.格雷码格雷码 n格雷码格雷码(Gray code)是一种无权码，采用绝对编码方式，是一种无权码，采用绝对编码方式， n格雷码属于可靠性编码，是一种错误最小化的编码方式格雷码属于可靠性编码，是一种错误最小化的编码方式 n其中的所有相邻整数在它们的数字表示中只有一个数字不其中的所有相邻整数在它们的数字表示中只有一个数字不 同。它在任意两个相邻的数之间转换时，只有一个数位发同。它在任意两个相邻的数之间转换时，只有一个数位发 生变化。由于最大数与最小数之间也仅一个数不同，故通生变化。由于最大数与最小数之间也仅一个数不同，故通 常又叫循环码或反射码常又叫循环

24、码或反射码 。 26 2.1.3 BCD码码 n5、二进制码与格雷码转换、二进制码与格雷码转换 n二进制码二进制码-格雷码格雷码（编码）：（编码）： n从最右边一位起，依次将每一位与左边一位异或从最右边一位起，依次将每一位与左边一位异或(XOR)，作为，作为 对应格雷码该位的值，最左边一位不变对应格雷码该位的值，最左边一位不变(相当于左边是相当于左边是0)； n格雷码格雷码-二进制码（解码）：二进制码（解码）： n从左边第二位起，将每位与左边一位解码后的值异或，作为该从左边第二位起，将每位与左边一位解码后的值异或，作为该 位解码后的值（最左边一位依然不变）位解码后的值（最左边一位依然不变）.

25、27 2.1.3 BCD码码 n6、常用、常用BCD码码 28 2.1.3 BCD码码 n7、“ 8421”BCD码加法运算码加法运算 BCD码运算应将每码运算应将每4位二进制数分为一组，组与组之间直位二进制数分为一组，组与组之间直 接运算，逢十进一。但计算机中无法区分接运算，逢十进一。但计算机中无法区分BCD码，一概码，一概 作为二进制数处理，因此，计算机做此运算后须进行调整作为二进制数处理，因此，计算机做此运算后须进行调整 。 调整方法：调整方法： 和和9 (1001)2， 不调整不调整 和和9 (1001)2 ， 加加6 (0110)2修正修正 29 2.1.3 BCD码码 30 2.1

26、.3 BCD码码 n校正算法校正算法 算法：算法： 1 每位数相加，遵循每位数相加，遵循“逢二进一逢二进一”的原则的原则 2 和是和是1015时，必须加时，必须加6矫正矫正 3 和有进位时，必须加和有进位时，必须加6校正校正 例如：例如：28+9=37 0 0 1 0 1 0 0 0 + 1 1 0 0 1 0 0 1 1 1 0 0 0 1 + 0 1 1 0 校正值校正值 0 0 1 1 0 1 1 1 31 2.1.3 BCD码码 1 Kk 1100 FFFS+Nn 1111 SIUS/?O_oDEL 34 2.1.4 字符与字符串字符与字符串 n2.2.字符串字符串 指连续的一串字符指

27、连续的一串字符, ,通常方式下通常方式下, ,它们占用主存中连续它们占用主存中连续 的多个字节的多个字节, ,每个字节存一个字符。当主存字由每个字节存一个字符。当主存字由2 2个或个或4 4个个 字节组成时字节组成时, ,在同一个主存字中在同一个主存字中, ,既可按从低位字节向高位既可按从低位字节向高位 字节的顺序存放字符串的内容字节的顺序存放字符串的内容, ,也可按从高位字节向低位也可按从高位字节向低位 字节的次序顺序存放字符串的内容。字节的次序顺序存放字符串的内容。 35 2.1.4 字符与字符串字符与字符串 例：将字符串：例：将字符串：IF AB THEN C 从高位字节到低位字节依次存

28、在主存中。从高位字节到低位字节依次存在主存中。 设主存单元长度由设主存单元长度由4个字节组成。每个字节中存放相个字节组成。每个字节中存放相 应字符的应字符的ASCII值，文字表达式中的空格值，文字表达式中的空格“ ”在主存中在主存中 也占一个字节的位置。因而每个字节分别存放十进制的也占一个字节的位置。因而每个字节分别存放十进制的73 、70、32、65、66、32、84、72、69、78、32、67。 主存 I F 空 A B 空 T H E N 空 C 36 2.1.4 字符与字符串字符与字符串 n3、汉字的表示方法、汉字的表示方法 n汉字的输入编码汉字的输入编码 当前采用的方法主要有以下三

29、类当前采用的方法主要有以下三类: 数字编码数字编码 常用的是国标区位码常用的是国标区位码,用数字串代表一个汉字输入用数字串代表一个汉字输入 。区位码是将国家标准局公布的。区位码是将国家标准局公布的6763个两级汉字分为个两级汉字分为94个个 区区,每个区分每个区分94位位,实际上把汉字表示成二维数组实际上把汉字表示成二维数组,每个汉字每个汉字 在数组中的下标就是区位码。区码和位码各两位十进制数在数组中的下标就是区位码。区码和位码各两位十进制数 字字,因此输入一个汉字需按键四次。因此输入一个汉字需按键四次。 数字编码输入的优点是无重码数字编码输入的优点是无重码,且输入码与内部编码的转且输入码与内

30、部编码的转 换比较方便换比较方便,缺点是代码难以记忆。缺点是代码难以记忆。 拼音码拼音码 拼音码是以汉字拼音为基础的输入方法。使用简单拼音码是以汉字拼音为基础的输入方法。使用简单 方便，但汉字同音字太多方便，但汉字同音字太多,输入重码率很高输入重码率很高,同音字选择影同音字选择影 响了输入速度。响了输入速度。 字形编码字形编码 字形编码是用汉字的形状来进行的编码。把汉字字形编码是用汉字的形状来进行的编码。把汉字 的笔划部件用字母或数字进行编码的笔划部件用字母或数字进行编码,按笔划的顺序依次输按笔划的顺序依次输 入入,就能表示一个汉字就能表示一个汉字 37 38 2.1.4 字符与字符串字符与字

31、符串 汉字内码：汉字内码：是用于汉字信息的存储、交换、检索等操作的机内是用于汉字信息的存储、交换、检索等操作的机内 代码代码,一般采用两个字节表示。英文字符的机内代码是七位的一般采用两个字节表示。英文字符的机内代码是七位的 ASCII码码,当用一个字节表示时当用一个字节表示时,最高位为最高位为“0”。为了与英文字符。为了与英文字符 能相互区别能相互区别,汉字机内代码中两个字节的最高位均规定为汉字机内代码中两个字节的最高位均规定为“1”。 字模码字模码是用点阵表示的汉字字形代码是用点阵表示的汉字字形代码,它是汉字的输出形它是汉字的输出形 式。式。 n汉字的输入编码、汉字内码、字模码是计算机中用于

32、输入汉字的输入编码、汉字内码、字模码是计算机中用于输入 、内部处理、输出三种不同用途的编码。、内部处理、输出三种不同用途的编码。 n汉字字模码汉字字模码 39 2.1.4 字符与字符串字符与字符串 402.1.5 校验码校验码 n 二进制数据经过传送、存取等环节，会发生误码（二进制数据经过传送、存取等环节，会发生误码（1变变 成成0或或0变成变成1），这就有如何发现及纠正误码的问题。所），这就有如何发现及纠正误码的问题。所 有解决此类问题的方法就是在原始数据（数码位）基础上有解决此类问题的方法就是在原始数据（数码位）基础上 增加几位校验（冗余）位。增加几位校验（冗余）位。 n1、码距、码距 n

33、 一个编码系统中任意两个合法编码（码字）之间不同一个编码系统中任意两个合法编码（码字）之间不同 的二进数位（的二进数位（bit）数叫这两个码字的码距，而整个编码）数叫这两个码字的码距，而整个编码 系统中任意两个码字的的最小距离就是该编码系统的码距系统中任意两个码字的的最小距离就是该编码系统的码距 。 412.1.5 校验码校验码 n如表所示的一个编码系统，用三个如表所示的一个编码系统，用三个bitbit来表示八个不同信来表示八个不同信 息中。息中。 信息序号信息序号 二进码字二进码字 a2a1a0 0000 1001 2010 3011 4100 5101 6110 7111 在这个系统中，两

34、个码字之间不在这个系统中，两个码字之间不 同的同的bit数从数从1到到3不等，但最小值为不等，但最小值为 1，故这个系统的码距为，故这个系统的码距为1。如果任。如果任 何码字中一位或多位被颠倒了，结何码字中一位或多位被颠倒了，结 果这个码字就不能与其它有效信息果这个码字就不能与其它有效信息 区分开。区分开。 如果传送信息如果传送信息001，而被误收为，而被误收为 011，因，因011仍是表中的合法码字，仍是表中的合法码字， 接收机仍将认为接收机仍将认为011是正确的信息是正确的信息 。 422.1.5 校验码校验码 n如果用四个二进数字来编如果用四个二进数字来编8 8个码字，那么在码字间的最小

35、个码字，那么在码字间的最小 距离可以增加到距离可以增加到2 2 信息序号信息序号 二进码字二进码字 a3a2a1a0 00000 11001 21010 30011 41100 50101 60110 71111 8个码字相互间最少有两个码字相互间最少有两bit的差异。因此，的差异。因此， 如果任何信息的一个数位被颠倒，就成为如果任何信息的一个数位被颠倒，就成为 一个不用的码字，接收机能检查出来。例一个不用的码字，接收机能检查出来。例 如信息是如信息是1001，误收为，误收为1011，接收机知道，接收机知道 发生了一个差错，因为发生了一个差错，因为1011不是一个码字不是一个码字 （表中没有）

36、。然而，差错不能被纠正。（表中没有）。然而，差错不能被纠正。 假定只有一个数位是错的，正确码字可以假定只有一个数位是错的，正确码字可以 是是1001，1111，0011或或1010。接收者不能。接收者不能 确定原来到底是这确定原来到底是这4个码字中的那一个。个码字中的那一个。 也可看到，也可看到， 在这个系统中，偶数个（在这个系统中，偶数个（2或或4） 差错也无法发现。差错也无法发现。 432.1.5 校验码校验码 n为了使一个系统能检查和纠正一个为了使一个系统能检查和纠正一个 差错，码间最小距离必须至少是差错，码间最小距离必须至少是 “3”。最小距离为。最小距离为3时，或能纠正一时，或能纠正

37、一 个错，或能检二个错，但不能同时个错，或能检二个错，但不能同时 纠一个错和检二个错。编码信息纠纠一个错和检二个错。编码信息纠 错和检错能力的进一步提高需要进错和检错能力的进一步提高需要进 一步增加码字间的最小距离。一步增加码字间的最小距离。 n右表概括了最小距离为右表概括了最小距离为1至至7的码的的码的 纠错和检错能力。纠错和检错能力。 码距码距 码码 能能 力力 检错检错 纠错纠错 1 2 3 4 5 6 7 0 0 1 0 2 或或 1 2 加加 1 2 加加 2 3 加加 2 3 加加 3 码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了码距越大，纠错能力越强，但数据冗余也越大

38、，即编码效率低了 。所以，选择码距要取决于特定系统的参数。所以，选择码距要取决于特定系统的参数。 442.1.5 校验码校验码 n2、奇偶校验、奇偶校验 n 奇偶校验码是一种通过增加冗余位使得码字中奇偶校验码是一种通过增加冗余位使得码字中“1”的个的个 数恒为奇数或偶数的编码方法数恒为奇数或偶数的编码方法,它是一种它是一种检错码检错码。例如，。例如， 单个的奇偶校验将使码的最小距离由一增加到二。单个的奇偶校验将使码的最小距离由一增加到二。 n 一个二进制码字，如果它的码元有奇数个一个二进制码字，如果它的码元有奇数个1，就称为具有，就称为具有 奇性。例如，奇性。例如， “10110101”有五个

39、有五个1。同样，偶性码字具。同样，偶性码字具 有偶数个有偶数个1。 n奇性检测等效于所有码元的奇性检测等效于所有码元的模二加模二加，并能够由所有码元的，并能够由所有码元的 异或运算异或运算来确定。来确定。 452.1.5 校验码校验码 n 对于一个对于一个n位字，奇性由下式给出：位字，奇性由下式给出： n 奇性奇性=a0 a1 a2 an n 奇偶校验可描述为：给每一个码字加一个校验位，用它奇偶校验可描述为：给每一个码字加一个校验位，用它 来构成奇性或偶性校验。来构成奇性或偶性校验。 n 奇偶校验编码通过增加一位校验位来使编码中奇偶校验编码通过增加一位校验位来使编码中1的个数为的个数为 奇数（

40、奇校验）或者为偶数（偶校验），从而使码距变为奇数（奇校验）或者为偶数（偶校验），从而使码距变为 2。因为其利用的是编码中。因为其利用的是编码中1的个数的奇偶性作为依据，所的个数的奇偶性作为依据，所 以不能发现偶数位错误。以不能发现偶数位错误。 462.1.5 校验码校验码 n数字数字0的七位的七位ASCII码（码（0110000） n如果传送后右边第一位出错，如果传送后右边第一位出错，0变成变成1。接收端还认为是一。接收端还认为是一 个合法的代码个合法的代码0110001（数字（数字1的的ASCII码）。若在最左边码）。若在最左边 加一位奇校验位，编码变为加一位奇校验位，编码变为1011000

41、0，如果传送后右边第，如果传送后右边第 一位出错，则变成一位出错，则变成10110001，1的个数变成偶数，就不是的个数变成偶数，就不是 合法的奇校验码了。合法的奇校验码了。 n但若有两位（假设是第但若有两位（假设是第1、2位）出错就变成位）出错就变成10110011，1 的个数为的个数为5，还是奇数。接收端还认为是一个合法的代码，还是奇数。接收端还认为是一个合法的代码 （数字（数字3的的ASCII码）。所以奇偶校验不能发现。码）。所以奇偶校验不能发现。 472.1.5 校验码校验码 n分组（纵横）奇偶校验码分组（纵横）奇偶校验码 n 实际工作中还经常采用纵横都加校验奇偶校验位的编码系统实际工

42、作中还经常采用纵横都加校验奇偶校验位的编码系统-分组分组 奇偶校验码奇偶校验码 n n个信息的一个分组排列成矩形式样，并以横向奇偶（个信息的一个分组排列成矩形式样，并以横向奇偶（HP）及纵）及纵 向奇偶（向奇偶（VP）的形式编出奇偶校验位。）的形式编出奇偶校验位。 m位数字位数字 横向奇偶位横向奇偶位 n 个个 码码 字字 a1a2am-1amHP1 b1b2bm-1bmHP2 c1c2cm-1cmHP3 n1n2nm-1nmHPn VP1VP2 VPm- 1 VPmHPn+1 纵向奇偶位纵向奇偶位 48 2.1.5 校验码校验码 n分组奇偶校验码不仅能检测许多形式的错误。并且在给分组奇偶校验

43、码不仅能检测许多形式的错误。并且在给 定的行或列中产生孤立的错误时，还可对该错误进行纠定的行或列中产生孤立的错误时，还可对该错误进行纠 正。正。 n例题：由例题：由 6 个字符的个字符的 7 位位 ASCII 编码排列，再加上水平编码排列，再加上水平 垂直奇偶校验位构成下列矩阵（最后一列为水平奇偶校垂直奇偶校验位构成下列矩阵（最后一列为水平奇偶校 验位，最后一行为垂直奇偶校验位）验位，最后一行为垂直奇偶校验位）: 49 2.1.5 校验码校验码 X12 1 X11 11100 VP 11 X10 111 X9 0= 0 X8 01 X7 001D 1111 X6X5 10Y2 0110101

44、X4 + 1 X3 001001 Y1 01100 X2X1 03 HP7 位 ASCII 码 字符 n则则 X1 X2 X3 X4 处的比特分别为处的比特分别为 ； n X5 X6 X7 X8 处的比特分别为处的比特分别为 ； n X9 X10 X11 X12 处的比特分别为处的比特分别为 ； nY1 和和 Y2 处的字符分别为处的字符分别为 和和 。 1110 1000 1011 I7 502.1.5 校验码校验码-海明码 海明码 n3 3、海明校验码、海明校验码 n 海明码是一种多重海明码是一种多重( (复式复式) )奇偶检错系统。它将信息用奇偶检错系统。它将信息用 逻辑形式编码，以便能

45、够检错和纠错。海明码的传输码字逻辑形式编码，以便能够检错和纠错。海明码的传输码字 是由信息和校验位组成的。每一个这种奇偶位被编在传输是由信息和校验位组成的。每一个这种奇偶位被编在传输 码字的特定位置上。码字的特定位置上。 n实现得合适时，这个系统对于错误的数位无论是原有信息实现得合适时，这个系统对于错误的数位无论是原有信息 位中的，还是附加校验位中的都能把它分离出来。位中的，还是附加校验位中的都能把它分离出来。 512.1.5 校验码校验码-海明码 海明码 n推导并使用长度为推导并使用长度为m位的码字的海明码，所需步骤如下：位的码字的海明码，所需步骤如下： n1、确定最小的校验位数、确定最小的

46、校验位数k，将它们记成，将它们记成D1、D2、Dk ，每个校验位符合不同的奇偶测试规定。，每个校验位符合不同的奇偶测试规定。 n2、原有信息和、原有信息和k个校验位一起编成长为个校验位一起编成长为m+k位的新码字。位的新码字。 选择选择k个校验位（个校验位（0或或1）以满足必要的奇偶条件。）以满足必要的奇偶条件。 n3、对所接收的信息作所需的、对所接收的信息作所需的k个奇偶检查。个奇偶检查。 n4、如果所有的奇偶检查结果均为正确的，则认为信息无、如果所有的奇偶检查结果均为正确的，则认为信息无 错误。错误。 n如果发现有一个或多个错了，则错误的位由这些检查的结如果发现有一个或多个错了，则错误的位

47、由这些检查的结 果来唯一地确定。果来唯一地确定。 522.1.5 校验码校验码-海明码 海明码 n校验位的位数校验位的位数 n推求海明码时的一项基本考虑是确定所需最少的校验位数推求海明码时的一项基本考虑是确定所需最少的校验位数k。 考虑长度为考虑长度为m位的信息，若附加了位的信息，若附加了k个校验位，则所发送的总个校验位，则所发送的总 长度为长度为m+k。 n在接收器中要进行在接收器中要进行k个奇偶检查，每个检查结果或是真或是伪个奇偶检查，每个检查结果或是真或是伪 。这个奇偶检查的结果可以表示成一个。这个奇偶检查的结果可以表示成一个k位的二进字，它可以位的二进字，它可以 确定最多确定最多2k种

48、不同状态。种不同状态。 这些状态中必有一个其所有奇偶测试这些状态中必有一个其所有奇偶测试 都是真的，它便是判定信息正确的条件。于是剩下的（都是真的，它便是判定信息正确的条件。于是剩下的（2k-1） 种状态，可以用来判定误码的位置。于是导出下一关系：种状态，可以用来判定误码的位置。于是导出下一关系： n 2k-1m+k 53 2.1.5 校验码校验码-海明码海明码 n如如m=5，则要求，则要求2k-k5+1=6，根据计算可以得知，根据计算可以得知k的最小的最小 值为值为4，也就是要校验，也就是要校验5位信息码，则要插入位信息码，则要插入4位校验码。位校验码。 如果信息码是如果信息码是8位，则要求

49、位，则要求2k-k8+1=9，根据计算可以得，根据计算可以得 知知k的最小值也为的最小值也为4。根据经验总结，得出信息码和校验码。根据经验总结，得出信息码和校验码 位数之间的关系如下所示。位数之间的关系如下所示。 n 信息码位数与校验码位数之间的关系信息码位数与校验码位数之间的关系 信息码位数信息码位数1245111226275758120121247 校验码位数校验码位数2345678 542.1.5 校验码校验码-海明码 海明码 n码字格式码字格式 n从理论上讲，校验位可放在任何位置，但从理论上讲，校验位可放在任何位置，但海明码将海明码将校验位校验位 被安排在被安排在2n 的位置上。的位置

50、上。 n下图列出了下图列出了m=4，k=3时，信息位和校验位的分布情况。时，信息位和校验位的分布情况。 码字位置码字位置B1B2B3B4B5B6B7 校验位校验位x xx 信息位信息位 x x x 复合码字复合码字P1P2D1P3D2D3D4 x 55 2.1.5 校验码校验码-海明码海明码 n校验位的确定（编码原理）校验位的确定（编码原理） nk个校验位是通过对个校验位是通过对m+k位复合码字进行奇偶校验而确定位复合码字进行奇偶校验而确定 的。的。 n每个校验位的值代表了代码字中部分数据位的奇偶性（最终要每个校验位的值代表了代码字中部分数据位的奇偶性（最终要 根据是采用奇校验，还是偶校验来确

51、定），其所在位置决定了根据是采用奇校验，还是偶校验来确定），其所在位置决定了 要校验的比特位序列。总的原则是：第要校验的比特位序列。总的原则是：第i位校验码从当前位开始位校验码从当前位开始 ，每次连续校验，每次连续校验i（这里是数值（这里是数值i，不是第，不是第i位，下同）位后再跳位，下同）位后再跳 过过i位，然后再连续校验位，然后再连续校验i位，再跳过位，再跳过i位，以此类推。位，以此类推。 n最后根据所采用的是奇校验，还是偶校验即可得出第最后根据所采用的是奇校验，还是偶校验即可得出第i位校验码位校验码 的值的值。 56 2.1.5 校验码校验码-海明码海明码 n校验码的具体计算方法如下：校

52、验码的具体计算方法如下： n p1（第（第1个校验位，也是整个码字的第个校验位，也是整个码字的第1位）的校验规位）的校验规 则是：从当前位数起，校验则是：从当前位数起，校验1位，然后跳过位，然后跳过1位，再校验位，再校验1 位，再跳过位，再跳过1位，位，。这样就可得出。这样就可得出p1校验码位可以校校验码位可以校 验的码字位包括：第验的码字位包括：第1位（也就是位（也就是p1本身）、第本身）、第3位、第位、第5 位、第位、第7位、第位、第9位、第位、第11位、第位、第13位、第位、第15位，位，。然。然 后根据所采用的是奇校验，还是偶校验，最终可以确定该后根据所采用的是奇校验，还是偶校验，最终

53、可以确定该 校验位的值。校验位的值。 n p2（第（第2个校验位，也是整个码字的第个校验位，也是整个码字的第2位）的校验规则位）的校验规则 是：从当前位数起，连续校验是：从当前位数起，连续校验2位，然后跳过位，然后跳过2位，再连续位，再连续 校验校验2位，再跳过位，再跳过2位，位，。这样就可得出。这样就可得出p2校验码位校验码位 可以校验的码字位包括：第可以校验的码字位包括：第2位（也就是位（也就是p2本身）、第本身）、第3 位，第位，第6位、第位、第7位，第位，第10位、第位、第11位，第位，第14位、第位、第15位，位， 。同样根据所采用的是奇校验，还是偶校验，最终可。同样根据所采用的是奇

54、校验，还是偶校验，最终可 以确定该校验位的值。以确定该校验位的值。 57 58 2.1.5 校验码校验码-海明码海明码 n p3（第（第3个校验位，也是整个码字的第个校验位，也是整个码字的第4位）的校验规则位）的校验规则 是：从当前位数起，连续校验是：从当前位数起，连续校验4位，然后跳过位，然后跳过4位，再连续位，再连续 校验校验4位，再跳过位，再跳过4位，位，。这样就可得出。这样就可得出p4校验码位校验码位 可以校验的码字位包括：第可以校验的码字位包括：第4位（也就是位（也就是p4本身）、第本身）、第5 位、第位、第6位、第位、第7位，第位，第12位、第位、第13位、第位、第14位、第位、第

55、15位，位， 第第20位、第位、第21位、第位、第22位、第位、第23位，位，。同样根据所采。同样根据所采 用的是奇校验，还是偶校验，最终可以确定该校验位的值用的是奇校验，还是偶校验，最终可以确定该校验位的值 。 n n p4（第（第4个校验位，也是整个码字的第个校验位，也是整个码字的第8位）的校验规则位）的校验规则 是：从当前位数起，连续校验是：从当前位数起，连续校验8位，然后跳过位，然后跳过8位，再连续位，再连续 校验校验8位，再跳过位，再跳过8位，位，。这样就可得出。这样就可得出p4校验码位校验码位 可以校验的码字位包括：第可以校验的码字位包括：第8位（也就是位（也就是p4本身）、第本身

56、）、第9 位、第位、第10位、第位、第11位、第位、第12位、第位、第13位、第位、第14位、第位、第15位位 ，第，第24位、第位、第25位、第位、第26位、第位、第27位、第位、第28位、第位、第29位、位、 第第30位、第位、第31位，位，。同样根据所采用的是奇校验，还。同样根据所采用的是奇校验，还 是偶校验，最终可以确定该校验位的值。是偶校验，最终可以确定该校验位的值。 59 60 2.1.5 校验码校验码-海明码海明码 n例如：例如：4位信息码为位信息码为1001，根据，根据2k-1m+k确定K为3，校验校验 位位置为：位位置为：？ ？1 ？001。 n先求第先求第1个个“？”（也就

57、是（也就是p1，第，第1位）的值，因为整个码字长位）的值，因为整个码字长 度为度为7（包括信息码长和校验码长），所以可以得出本示例中（包括信息码长和校验码长），所以可以得出本示例中 p1校验码校验的位数是校验码校验的位数是1、3、5、7共共4位。这位。这4位中除了第位中除了第1位位 （也就是（也就是p1位）不能确定外，其余位）不能确定外，其余3位的值都是已知的，分别位的值都是已知的，分别 为：为：1、0、1。现假设采用的是偶校验（也就是要求整个被校。现假设采用的是偶校验（也就是要求整个被校 验的位中的验的位中的“1”的个数为偶数），从已知的的个数为偶数），从已知的3位码值可知，已位码值可知，已

58、 有有2个个“1”，所以此时，所以此时p1位校验码的值必须为位校验码的值必须为“0”，得出，得出p1=0 。 n依次得出另两个分别是依次得出另两个分别是0和和1。 n 所以海明码编码为：所以海明码编码为：0011001 612.1.5 校验码校验码-海明码 海明码 n海明码的差错检测海明码的差错检测 ：海明码校验的方式就是各校验码对：海明码校验的方式就是各校验码对 它所校验的位组进行它所校验的位组进行“异或运算异或运算”。 nP1 负责校验海明码的第负责校验海明码的第1、3、5、7、（P1、D1、D2、D4、 ）位，（包括）位，（包括P1自己）自己） nP2 负责校验海明码的第负责校验海明码的

59、第2、3、6、7、（P2、D1、D3、D4、 ）位，（包括）位，（包括P2自己）自己） nP3 负责校验海明码的第负责校验海明码的第4、5、6、7、（P3、D2、D3、D4、 ）位，（包括）位，（包括P3自己）自己） n 62 2.1.5 校验码校验码-海明码海明码 n各校验码校验的码位对照表各校验码校验的码位对照表 从表中可以得出以下两个规律：从表中可以得出以下两个规律： 1）所有校验码所在的位是只由对应的校验码进行校验，如第）所有校验码所在的位是只由对应的校验码进行校验，如第1位位 （只由（只由p1校验）、第校验）、第2位（只由位（只由p2校验）、第校验）、第4位（只由位（只由p3校验）。

60、校验）。 也就是这些位如果发生了差错，影响的只是对应的校验码的校验结也就是这些位如果发生了差错，影响的只是对应的校验码的校验结 果，不会影响其它校验码的校验结果。果，不会影响其它校验码的校验结果。 2）所有信息码位均被至少两个校验码进行了校验，也就是至少校）所有信息码位均被至少两个校验码进行了校验，也就是至少校 验了两次。验了两次。 632.1.5 校验码校验码-海明码 海明码 n对对m=4，k=3，偶校验的例子，只要进行，偶校验的例子，只要进行3次次偶性偶性测试。这些测测试。这些测 试（以试（以A、B、C表示）在图中所示各位的位置上进行。表示）在图中所示各位的位置上进行。 奇偶条件奇偶条件