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

1、计算机组成原理计算机组成原理Principles of Computer Composition2第二部分第二部分 数据的表示和运算数据的表示和运算 n 2.1 数制与编码数制与编码n 2.2 定点数表示和运算定点数表示和运算n 2.3 浮点数表示和运算浮点数表示和运算n 2.4 算术逻辑单元算术逻辑单元ALU3 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”所表示的值为该位的权所表示的值为该位的权 常见的进位制常见的进位制： 2，8，10，16进制

4、进制62.1.1 进位计数制及其相互转换进位计数制及其相互转换n十进制十进制(Decimal)b基数基数:10; 符号符号:0,1,2,3,4,5,6,7,8,9b计算规律计算规律:“逢十进一逢十进一 ”或或“借一当十借一当十”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为整数位数；为整数位数；m为小数位数。为小数位数。Di表

5、示表示第第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-m =Kn-1 rn-1 + Kn-2 rn-2 + +K1

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

7、换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 =(101000111) =(101000111) 2 2102.1.1 进位计数制及

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

9、=1.25 12 2 0.25=0.5 0 0.25=0.5 02 2 0.5=1 10.5=1 1(0.8125) (0.8125) 10 10 =(0.1101) =(0.1101) 2 2112.1.1 进位计数制及其相互转换进位计数制及其相互转换n3、其它进制之间的直接转换法、其它进制之间的直接转换法122.1.1 进位计数制及其相互转换进位计数制及其相互转换n二进制转换成八进制二进制转换成八进制例：例：(10110111 .01101) 2(10110111.01101) (10110111.01101) 2 2 =(267.32)=(267.32)8 8八进制八进制: 2 6 7

10、: 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 , 01132.1.1 进位计数制及其相互转换进位计数制及其相互转换n八进制转换二进制八进制转换二进制n例如例如: (123.46 ) 8n二进制转换成十六进制二进制转换成十六进制例：例：(110110111 .01101) 2(10110111.01101) 2 =(1B7.68)16十六进制十六进制: 1 B 7 .

11、6 8二进制二进制: 0001 ,1011 , 0111 . 0110 ,1000二进制二进制: 1 ,1011 , 0111 . 0110 ,1142.1.1 进位计数制及其相互转换进位计数制及其相互转换n十六进制转换成二进制十六进制转换成二进制n例如例如: (7AC.DE ) 16n=(0111,1010,1100.1101,1110 ) 2 n=(11110101100 .1101111 )2152.1.2 真值和机器数真值和机器数 机器数：机器数：符号数码化的数称为机器数符号数码化的数称为机器数 如如 ： X=01011 Y=11011 机器数的特点：机器数的特点： 1. 数的符号数值

12、化，通常放在二进制数的最高位数的符号数值化，通常放在二进制数的最高位 2. 二进制数的位数受机器设备的限制二进制数的位数受机器设备的限制 真值真值:带符号位的机器数称为真值。带符号位的机器数称为真值。 如如 二进制真值：二进制真值： X=+1011 y=-1011 符号位数值化后，为了能提高对机器数进行算术运符号位数值化后，为了能提高对机器数进行算术运算、提高运算速度，设置了多种符号位与数值一起编算、提高运算速度，设置了多种符号位与数值一起编码的方案。最常用的有：码的方案。最常用的有：原码、反码和补码原码、反码和补码162.1.2 真值和机器数真值和机器数带符号的数带符号的数 符号数字化的数符

13、号数字化的数+ 0.10110 1011小数点的位置小数点的位置+ 11000 1100小数点的位置小数点的位置 11001 1100小数点的位置小数点的位置 0.10111 1011小数点的位置小数点的位置真值真值 机器数机器数172.1.3 BCD码码n1 1、定义：、定义：n用四位二进制代码的不同组合来表示一个十进制数码的编码方用四位二进制代码的不同组合来表示一个十进制数码的编码方法，称为二法，称为二十进制编码，也称十进制编码，也称BCDBCD码码(Binary Coded (Binary Coded Decimal)Decimal)，或二进码十进数。是一种二进制的数字编码形式，或二进码

14、十进数。是一种二进制的数字编码形式，用二进制编码的十进制代码。用二进制编码的十进制代码。nBCDBCD码利用四个位元来储存一个十进制的数码，使二进制和十码利用四个位元来储存一个十进制的数码，使二进制和十进制之间的转换得以快捷的进行。相对于一般的浮点式记数法进制之间的转换得以快捷的进行。相对于一般的浮点式记数法，采用，采用BCDBCD码，既可保存数值的精确度，又可免却使电脑作浮码，既可保存数值的精确度，又可免却使电脑作浮点运算时所耗费的时间。此外，对于其他需要高精确度的计算点运算时所耗费的时间。此外，对于其他需要高精确度的计算，BCDBCD编码亦很常用。编码亦很常用。182.1.3 BCD码码n

15、2 2、原理、原理 （1 1）二）二十进制编码都采用压缩的十进制串的方法，十进制编码都采用压缩的十进制串的方法，即四个二进制位的值来表示一个十进制数码。即四个二进制位的值来表示一个十进制数码。 （2 2）各种编码的区别在于选用哪十个状态。选择的原）各种编码的区别在于选用哪十个状态。选择的原则是：要考虑输入和输出时转换方便；内部运算时，加、则是：要考虑输入和输出时转换方便；内部运算时，加、减运算规则要尽量简单；在特定场合，可能有其它一些要减运算规则要尽量简单；在特定场合，可能有其它一些要求。求。 （3 3）从每个二进制位是否有确定的位权区分，可把二）从每个二进制位是否有确定的位权区分，可把二十进

16、制编码分为有权码和无权码。十进制编码分为有权码和无权码。192.1.3 BCD码码n3 3、常用、常用BCDBCD编码方式编码方式n最常用的最常用的BCDBCD编码，就是使用编码，就是使用“0”0”至至“9”9”这十个数值的这十个数值的二进码来表示。这种编码方式，我们称之为二进码来表示。这种编码方式，我们称之为“84218421码码”。n对应不同需求，各人亦开发了不同的编码方法，以适应不对应不同需求，各人亦开发了不同的编码方法，以适应不同的需求。这些编码，大致可以分成有权码和无权码两种同的需求。这些编码，大致可以分成有权码和无权码两种。n有权有权BCDBCD码码，如：，如：8421(8421(

17、最常用最常用) )、24212421、5421 5421 n无权无权BCDBCD码码，如：余，如：余3 3码、格雷码码、格雷码202.1.3 BCD码码n4、二、二十进制（十进制（BCD）有权码）有权码1、对于有权码，将每位的数码与相应的位权相乘，再求和、对于有权码，将每位的数码与相应的位权相乘，再求和，就可以得到它所代表的十进制数值。，就可以得到它所代表的十进制数值。2、8421码实现加、减运算时的修正规则：码实现加、减运算时的修正规则：（1）4位一组二进制数，两个位一组二进制数，两个8421码表示的数相加之和等于码表示的数相加之和等于或小于或小于1001，即十进制的，即十进制的9时，不需要

18、修正，在各组内，时，不需要修正，在各组内，二进制代码相加，仍遵循二进制代码相加，仍遵循“逢二进一逢二进一”的规则。的规则。（2）4位一组二进制数，两个位一组二进制数，两个8421码相加结果大于码相加结果大于1001（即（即十进制十进制9）时，则应该对该组的）时，则应该对该组的4位进行位进行“加加6修正修正”，使，使它向高一组产生进位。它向高一组产生进位。（3）4位一组二进制数，两个位一组二进制数，两个8421码相加结果大于或等于码相加结果大于或等于10000（即十进制（即十进制16），而向高一组进位时，则应该对该），而向高一组进位时，则应该对该4位进行位进行“加加6修正修正”21222.1.3

19、 BCD码码3、其它编码方法还有：、其它编码方法还有：2421码、码、5211码、码、4311码和码和84-2-1码码( 四位二进制位的位权分别为四位二进制位的位权分别为8、4、-2、-1)等。其最方便等。其最方便使用的共同特点为：使用的共同特点为：(1) 对于对于2421码、码、5211码、码、4311码，任何两个十进制数位，码，任何两个十进制数位，采用这三种编码的任何一种编码，它们相加之和等于或大采用这三种编码的任何一种编码，它们相加之和等于或大于于10时，其结果的最高位向左产生进位，小于时，其结果的最高位向左产生进位，小于10时则不产时则不产生进位。这一特点有利于实现生进位。这一特点有利

20、于实现“逢十进位逢十进位”的计数和加法的计数和加法规则。规则。n(2) 对于对于2421码、码、5211码、码、4311码和码和84-2-1码，任何两个十码，任何两个十进制数位，采用这四种编码的任何一种编码，它们相加其进制数位，采用这四种编码的任何一种编码，它们相加其和等于和等于9时，即它们的二进制编码位互为反码，则其结果时，即它们的二进制编码位互为反码，则其结果的四个二进制位一定是的四个二进制位一定是1111，能较好地体现十进制的按，能较好地体现十进制的按9 取补与二进制的按取补与二进制的按1取补的对应关系，这对减法很有用。取补的对应关系，这对减法很有用。23242.1.3 BCD码码n二二

21、十进制（十进制（BCD）无权码）无权码 无权码中，用的较多的是余无权码中，用的较多的是余3码码(Excess-3 code)和格雷码和格雷码(Gray code)，格雷码又称循环码。，格雷码又称循环码。1. 余余3码码 （1） 余余3码是在码是在8421码的基础上，把每个代码都加上码的基础上，把每个代码都加上0011而形成的。而形成的。 （2） 普通普通8421码的加法器仍能为余码的加法器仍能为余3码加法器直接利用，具体规则如码加法器直接利用，具体规则如下：下： （A）若两个十进制数的余）若两个十进制数的余3码相加，如果结果不产生进位，则从所码相加，如果结果不产生进位，则从所得和值去减得和值去

22、减0011，便得十进制位和的余，便得十进制位和的余3码。码。 （B）若两个十进制数的余）若两个十进制数的余3码相加，如果结果有进位，则其进位正码相加，如果结果有进位，则其进位正确，确， 但需将所得和值加上但需将所得和值加上0011，才求得十进制数和的余，才求得十进制数和的余3码。码。252.1.3 BCD码码n2.格雷码格雷码n格雷码格雷码(Gray code)是一种无权码，采用绝对编码方式，是一种无权码，采用绝对编码方式，n格雷码属于可靠性编码，是一种错误最小化的编码方式格雷码属于可靠性编码，是一种错误最小化的编码方式n其中的所有相邻整数在它们的数字表示中只有一个数字不其中的所有相邻整数在它

23、们的数字表示中只有一个数字不同。它在任意两个相邻的数之间转换时，只有一个数位发同。它在任意两个相邻的数之间转换时，只有一个数位发生变化。由于最大数与最小数之间也仅一个数不同，故通生变化。由于最大数与最小数之间也仅一个数不同，故通常又叫循环码或反射码常又叫循环码或反射码 。262.1.3 BCD码码n5、二进制码与格雷码转换、二进制码与格雷码转换n二进制码二进制码-格雷码格雷码（编码）：（编码）：n从最右边一位起，依次将每一位与左边一位异或从最右边一位起，依次将每一位与左边一位异或(XOR)，作为，作为对应格雷码该位的值，最左边一位不变对应格雷码该位的值，最左边一位不变(相当于左边是相当于左边是

24、0)； n格雷码格雷码-二进制码（解码）：二进制码（解码）：n从左边第二位起，将每位与左边一位解码后的值异或，作为该从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）位解码后的值（最左边一位依然不变）. 272.1.3 BCD码码n6、常用、常用BCD码码282.1.3 BCD码码n7、“ 8421”BCD码加法运算码加法运算 BCD码运算应将每码运算应将每4位二进制数分为一组，组与组之间直位二进制数分为一组，组与组之间直接运算，逢十进一。但计算机中无法区分接运算，逢十进一。但计算机中无法区分BCD码，一概码，一概作为二进制数处理，因此，计算机做此运算后须

25、进行调整作为二进制数处理，因此，计算机做此运算后须进行调整。 调整方法：调整方法：和和9 (1001)2， 不调整不调整和和9 (1001)2 ， 加加6 (0110)2修正修正292.1.3 BCD码码302.1.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

26、0 1 1 1312.1.3 BCD码码 1&Xi3Yi3 Xi2Yi2 Xi1Yi1 Xi0Yi0 Si3 Si2 Si1 Si0Ci+1Ci Si3 Si2 Si1 Si0C i+1二进制二进制加法加法十进制校十进制校正正322.1.4 字符与字符串字符与字符串n1、字符表示法字符表示法n符号数据：字符信息用数据表示，如符号数据：字符信息用数据表示，如ASCII等；等；n目前国际上普遍采用的字符系统是七单位的目前国际上普遍采用的字符系统是七单位的ASCII码码(美美国国家信息交换标准字符码国国家信息交换标准字符码),它包括它包括10个十进制数码，个十进制数码，26个英文字母和一定数量的专用

27、符号，如个英文字母和一定数量的专用符号，如$，%，等，等，共，共128个元素，因此二进制编码需个元素，因此二进制编码需7位，加一位偶校验位位，加一位偶校验位，共，共8位一个字节。位一个字节。332.1.4 字符与字符串字符与字符串nASCII字符编码表字符编码表0000010100111001011101110000NUL DLESP0Pp0001SOH DC1!1AQaq0010STXDC2“2BRbr0011ETXDC3#3CScs0100EOTDC4$4DTdt0101ENQNAK%5EUeu0110ACKSYN&6FVfv0111DELETB7GWgw1000BSCAN8HXhx100

28、1HTEM(9IYiy1010LFSUB):JZjz1011VTESC*;Kk1100FFFS+Nn1111SIUS/?O_oDEL342.1.4 字符与字符串字符与字符串n2.2.字符串字符串 指连续的一串字符指连续的一串字符, ,通常方式下通常方式下, ,它们占用主存中连续它们占用主存中连续的多个字节的多个字节, ,每个字节存一个字符。当主存字由每个字节存一个字符。当主存字由2 2个或个或4 4个个字节组成时字节组成时, ,在同一个主存字中在同一个主存字中, ,既可按从低位字节向高位既可按从低位字节向高位字节的顺序存放字符串的内容字节的顺序存放字符串的内容, ,也可按从高位字节向低位也可按

29、从高位字节向低位字节的次序顺序存放字符串的内容。字节的次序顺序存放字符串的内容。352.1.4 字符与字符串字符与字符串例：将字符串：例：将字符串：IF AB THEN C 从高位字节到低位字节依次存在主存中。从高位字节到低位字节依次存在主存中。 设主存单元长度由设主存单元长度由4个字节组成。每个字节中存放相个字节组成。每个字节中存放相应字符的应字符的ASCII值，文字表达式中的空格值，文字表达式中的空格“ ”在主存中在主存中也占一个字节的位置。因而每个字节分别存放十进制的也占一个字节的位置。因而每个字节分别存放十进制的73、70、32、65、66、32、84、72、69、78、32、67。

30、主存 I F 空 A B 空 T H E N 空 C362.1.4 字符与字符串字符与字符串n3、汉字的表示方法、汉字的表示方法n汉字的输入编码汉字的输入编码当前采用的方法主要有以下三类当前采用的方法主要有以下三类: 数字编码数字编码 常用的是国标区位码常用的是国标区位码,用数字串代表一个汉字输入用数字串代表一个汉字输入。区位码是将国家标准局公布的。区位码是将国家标准局公布的6763个两级汉字分为个两级汉字分为94个个区区,每个区分每个区分94位位,实际上把汉字表示成二维数组实际上把汉字表示成二维数组,每个汉字每个汉字在数组中的下标就是区位码。区码和位码各两位十进制数在数组中的下标就是区位码。

31、区码和位码各两位十进制数字字,因此输入一个汉字需按键四次。因此输入一个汉字需按键四次。数字编码输入的优点是无重码数字编码输入的优点是无重码,且输入码与内部编码的转且输入码与内部编码的转换比较方便换比较方便,缺点是代码难以记忆。缺点是代码难以记忆。拼音码拼音码 拼音码是以汉字拼音为基础的输入方法。使用简单拼音码是以汉字拼音为基础的输入方法。使用简单方便，但汉字同音字太多方便，但汉字同音字太多,输入重码率很高输入重码率很高,同音字选择影同音字选择影响了输入速度。响了输入速度。字形编码字形编码 字形编码是用汉字的形状来进行的编码。把汉字字形编码是用汉字的形状来进行的编码。把汉字的笔划部件用字母或数字

32、进行编码的笔划部件用字母或数字进行编码,按笔划的顺序依次输按笔划的顺序依次输入入,就能表示一个汉字就能表示一个汉字37382.1.4 字符与字符串字符与字符串 汉字内码：汉字内码：是用于汉字信息的存储、交换、检索等操作的机内是用于汉字信息的存储、交换、检索等操作的机内代码代码,一般采用两个字节表示。英文字符的机内代码是七位的一般采用两个字节表示。英文字符的机内代码是七位的ASCII码码,当用一个字节表示时当用一个字节表示时,最高位为最高位为“0”。为了与英文字符。为了与英文字符能相互区别能相互区别,汉字机内代码中两个字节的最高位均规定为汉字机内代码中两个字节的最高位均规定为“1”。 字模码字模

33、码是用点阵表示的汉字字形代码是用点阵表示的汉字字形代码,它是汉字的输出形它是汉字的输出形式。式。n汉字的输入编码、汉字内码、字模码是计算机中用于输入汉字的输入编码、汉字内码、字模码是计算机中用于输入、内部处理、输出三种不同用途的编码。、内部处理、输出三种不同用途的编码。n汉字字模码汉字字模码392.1.4 字符与字符串字符与字符串402.1.5 校验码校验码n 二进制数据经过传送、存取等环节，会发生误码（二进制数据经过传送、存取等环节，会发生误码（1变变成成0或或0变成变成1），这就有如何发现及纠正误码的问题。所），这就有如何发现及纠正误码的问题。所有解决此类问题的方法就是在原始数据（数码位）

34、基础上有解决此类问题的方法就是在原始数据（数码位）基础上增加几位校验（冗余）位。增加几位校验（冗余）位。n1、码距、码距n 一个编码系统中任意两个合法编码（码字）之间不同一个编码系统中任意两个合法编码（码字）之间不同的二进数位（的二进数位（bit）数叫这两个码字的码距，而整个编码）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距系统中任意两个码字的的最小距离就是该编码系统的码距。412.1.5 校验码校验码n如表所示的一个编码系统，用三个如表所示的一个编码系统，用三个bitbit来表示八个不同信来表示八个不同信息中。息中。信息序号信息序号二进码字二进码字a2a

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

36、四个二进数字来编如果用四个二进数字来编8 8个码字，那么在码字间的最小个码字，那么在码字间的最小距离可以增加到距离可以增加到2 2信息序号信息序号二进码字二进码字a3a2a1a000000110012101030011411005010160110711118个码字相互间最少有两个码字相互间最少有两bit的差异。因此，的差异。因此，如果任何信息的一个数位被颠倒，就成为如果任何信息的一个数位被颠倒，就成为一个不用的码字，接收机能检查出来。例一个不用的码字，接收机能检查出来。例如信息是如信息是1001，误收为，误收为1011，接收机知道，接收机知道发生了一个差错，因为发生了一个差错，因为1011不

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

38、纠正一时，或能纠正一个错，或能检二个错，但不能同时个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进错和检错能力的进一步提高需要进一步增加码字间的最小距离。一步增加码字间的最小距离。 n右表概括了最小距离为右表概括了最小距离为1至至7的码的的码的纠错和检错能力。纠错和检错能力。码距码距码码 能能 力力检错检错 纠错纠错12345670 01 02 或或 12 加加 12 加加 23 加加 23 加加 3 码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选

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

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

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

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

43、n个信息的一个分组排列成矩形式样，并以横向奇偶（个信息的一个分组排列成矩形式样，并以横向奇偶（HP）及纵）及纵向奇偶（向奇偶（VP）的形式编出奇偶校验位。）的形式编出奇偶校验位。 m位数字位数字横向奇偶位横向奇偶位n个个码码字字a1a2am-1amHP1b1b2bm-1bmHP2c1c2cm-1cmHP3n1n2nm-1nmHPnVP1VP2VPm-1VPmHPn+1纵向奇偶位纵向奇偶位482.1.5 校验码校验码n分组奇偶校验码不仅能检测许多形式的错误。并且在给分组奇偶校验码不仅能检测许多形式的错误。并且在给定的行或列中产生孤立的错误时，还可对该错误进行纠定的行或列中产生孤立的错误时，还可对

44、该错误进行纠正。正。n例题：由例题：由 6 个字符的个字符的 7 位位 ASCII 编码排列，再加上水平编码排列，再加上水平垂直奇偶校验位构成下列矩阵（最后一列为水平奇偶校垂直奇偶校验位构成下列矩阵（最后一列为水平奇偶校验位，最后一行为垂直奇偶校验位）验位，最后一行为垂直奇偶校验位）: 492.1.5 校验码校验码X121X1111100VP11X10111X90=0X801X7001D1111X6X510Y20110101X4+1X3001001Y101100X2X103HP7 位 ASCII 码字符n则则 X1 X2 X3 X4 处的比特分别为处的比特分别为 ；n X5 X6 X7 X8

45、处的比特分别为处的比特分别为 ；n X9 X10 X11 X12 处的比特分别为处的比特分别为 ；nY1 和和 Y2 处的字符分别为处的字符分别为 和和 。111010001011I7502.1.5 校验码校验码-海明码海明码n3 3、海明校验码、海明校验码n 海明码是一种多重海明码是一种多重( (复式复式) )奇偶检错系统。它将信息用奇偶检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。海明码的传输码字逻辑形式编码，以便能够检错和纠错。海明码的传输码字是由信息和校验位组成的。每一个这种奇偶位被编在传输是由信息和校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。码字的特定位置上。n

46、实现得合适时，这个系统对于错误的数位无论是原有信息实现得合适时，这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能把它分离出来。位中的，还是附加校验位中的都能把它分离出来。512.1.5 校验码校验码-海明码海明码n推导并使用长度为推导并使用长度为m位的码字的海明码，所需步骤如下：位的码字的海明码，所需步骤如下：n1、确定最小的校验位数、确定最小的校验位数k，将它们记成，将它们记成D1、D2、Dk，每个校验位符合不同的奇偶测试规定。，每个校验位符合不同的奇偶测试规定。 n2、原有信息和、原有信息和k个校验位一起编成长为个校验位一起编成长为m+k位的新码字。位的新码字。选择选择k

47、个校验位（个校验位（0或或1）以满足必要的奇偶条件。）以满足必要的奇偶条件。 n3、对所接收的信息作所需的、对所接收的信息作所需的k个奇偶检查。个奇偶检查。 n4、如果所有的奇偶检查结果均为正确的，则认为信息无、如果所有的奇偶检查结果均为正确的，则认为信息无错误。错误。 n如果发现有一个或多个错了，则错误的位由这些检查的结如果发现有一个或多个错了，则错误的位由这些检查的结果来唯一地确定。果来唯一地确定。 522.1.5 校验码校验码-海明码海明码n校验位的位数校验位的位数n推求海明码时的一项基本考虑是确定所需最少的校验位数推求海明码时的一项基本考虑是确定所需最少的校验位数k。考虑长度为考虑长度

48、为m位的信息，若附加了位的信息，若附加了k个校验位，则所发送的总个校验位，则所发送的总长度为长度为m+k。n在接收器中要进行在接收器中要进行k个奇偶检查，每个检查结果或是真或是伪个奇偶检查，每个检查结果或是真或是伪。这个奇偶检查的结果可以表示成一个。这个奇偶检查的结果可以表示成一个k位的二进字，它可以位的二进字，它可以确定最多确定最多2k种不同状态。种不同状态。 这些状态中必有一个其所有奇偶测试这些状态中必有一个其所有奇偶测试都是真的，它便是判定信息正确的条件。于是剩下的（都是真的，它便是判定信息正确的条件。于是剩下的（2k-1）种状态，可以用来判定误码的位置。于是导出下一关系：种状态，可以用

49、来判定误码的位置。于是导出下一关系： n 2k-1m+k532.1.5 校验码校验码-海明码海明码n如如m=5，则要求，则要求2k-k5+1=6，根据计算可以得知，根据计算可以得知k的最小的最小值为值为4，也就是要校验，也就是要校验5位信息码，则要插入位信息码，则要插入4位校验码。位校验码。如果信息码是如果信息码是8位，则要求位，则要求2k-k8+1=9，根据计算可以得，根据计算可以得知知k的最小值也为的最小值也为4。根据经验总结，得出信息码和校验码。根据经验总结，得出信息码和校验码位数之间的关系如下所示。位数之间的关系如下所示。n 信息码位数与校验码位数之间的关系信息码位数与校验码位数之间的

50、关系信息码位数信息码位数1245111226275758120121247校验码位数校验码位数2345678542.1.5 校验码校验码-海明码海明码n码字格式码字格式n从理论上讲，校验位可放在任何位置，但海明码将校验位从理论上讲，校验位可放在任何位置，但海明码将校验位被安排在被安排在2n 的位置上。的位置上。 n下图列出了下图列出了m=4，k=3时，信息位和校验位的分布情况。时，信息位和校验位的分布情况。码字位置码字位置B1B2B3B4B5B6B7校验位校验位xxx信息位信息位xxx复合码字复合码字P1P2D1P3D2D3D4x552.1.5 校验码校验码-海明码海明码n校验位的确定（编码原

51、理）校验位的确定（编码原理）nk个校验位是通过对个校验位是通过对m+k位复合码字进行奇偶校验而确定位复合码字进行奇偶校验而确定的。的。n每个校验位的值代表了代码字中部分数据位的奇偶性（最终要每个校验位的值代表了代码字中部分数据位的奇偶性（最终要根据是采用奇校验，还是偶校验来确定），其所在位置决定了根据是采用奇校验，还是偶校验来确定），其所在位置决定了要校验的比特位序列。总的原则是：第要校验的比特位序列。总的原则是：第i位校验码从当前位开始位校验码从当前位开始，每次连续校验，每次连续校验i（这里是数值（这里是数值i，不是第，不是第i位，下同）位后再跳位，下同）位后再跳过过i位，然后再连续校验位，

52、然后再连续校验i位，再跳过位，再跳过i位，以此类推。位，以此类推。n最后根据所采用的是奇校验，还是偶校验即可得出第最后根据所采用的是奇校验，还是偶校验即可得出第i位校验码位校验码的值的值。 562.1.5 校验码校验码-海明码海明码n校验码的具体计算方法如下：校验码的具体计算方法如下：n p1（第（第1个校验位，也是整个码字的第个校验位，也是整个码字的第1位）的校验规位）的校验规则是：从当前位数起，校验则是：从当前位数起，校验1位，然后跳过位，然后跳过1位，再校验位，再校验1位，再跳过位，再跳过1位，位，。这样就可得出。这样就可得出p1校验码位可以校校验码位可以校验的码字位包括：第验的码字位包

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

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

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

56、后跳过8位，再连续位，再连续校验校验8位，再跳过位，再跳过8位，位，。这样就可得出。这样就可得出p4校验码位校验码位可以校验的码字位包括：第可以校验的码字位包括：第8位（也就是位（也就是p4本身）、第本身）、第9位、第位、第10位、第位、第11位、第位、第12位、第位、第13位、第位、第14位、第位、第15位位，第，第24位、第位、第25位、第位、第26位、第位、第27位、第位、第28位、第位、第29位、位、第第30位、第位、第31位，位，。同样根据所采用的是奇校验，还。同样根据所采用的是奇校验，还是偶校验，最终可以确定该校验位的值。是偶校验，最终可以确定该校验位的值。59602.1.5 校验

57、码校验码-海明码海明码n例如：例如：4位信息码为位信息码为1001，根据，根据2k-1m+k确定K为3，校验校验位位置为：位位置为：？ ？1 ？001。n先求第先求第1个个“？”（也就是（也就是p1，第，第1位）的值，因为整个码字长位）的值，因为整个码字长度为度为7（包括信息码长和校验码长），所以可以得出本示例中（包括信息码长和校验码长），所以可以得出本示例中p1校验码校验的位数是校验码校验的位数是1、3、5、7共共4位。这位。这4位中除了第位中除了第1位位（也就是（也就是p1位）不能确定外，其余位）不能确定外，其余3位的值都是已知的，分别位的值都是已知的，分别为：为：1、0、1。现假设采用的

58、是偶校验（也就是要求整个被校。现假设采用的是偶校验（也就是要求整个被校验的位中的验的位中的“1”的个数为偶数），从已知的的个数为偶数），从已知的3位码值可知，已位码值可知，已有有2个个“1”，所以此时，所以此时p1位校验码的值必须为位校验码的值必须为“0”，得出，得出p1=0。 n依次得出另两个分别是依次得出另两个分别是0和和1。n 所以海明码编码为：所以海明码编码为：0011001612.1.5 校验码校验码-海明码海明码n海明码的差错检测海明码的差错检测 ：海明码校验的方式就是各校验码对：海明码校验的方式就是各校验码对它所校验的位组进行它所校验的位组进行“异或运算异或运算”。nP1 负责校

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

60、应的校验码进行校验，如第1位位（只由（只由p1校验）、第校验）、第2位（只由位（只由p2校验）、第校验）、第4位（只由位（只由p3校验）。校验）。也就是这些位如果发生了差错，影响的只是对应的校验码的校验结也就是这些位如果发生了差错，影响的只是对应的校验码的校验结果，不会影响其它校验码的校验结果。果，不会影响其它校验码的校验结果。 2）所有信息码位均被至少两个校验码进行了校验，也就是至少校）所有信息码位均被至少两个校验码进行了校验，也就是至少校验了两次。验了两次。 632.1.5 校验码校验码-海明码海明码n对对m=4，k=3，偶校验的例子，只要进行，偶校验的例子，只要进行3次次偶性偶性测试。这