1、第二章计算机中数据信息的表示第二章计算机中数据信息的表示第二章计算机中数据信息的表示 本章学习的主要内容：本章学习的主要内容：1 1、计算机中常用进位计数制及其转换、计算机中常用进位计数制及其转换 2 2、符号数的编码方法、符号数的编码方法 3 3、数的定、浮点表示、数的定、浮点表示 4 4、非数值数据的表示、非数值数据的表示 5 5、十进制数串的表示、十进制数串的表示 6 6、数据校验码、数据校验码 2.1计算机中常用的进位计数制及其相互转计算机中常用的进位计数制及其相互转换换 一、进位计数制的基本概念一、进位计数制的基本概念-两个基本因素：基两个基本因素：基值和位权值值和位权值 二、计算机
2、中常用的进位计数制二、计算机中常用的进位计数制 1、计算机以二进制为基础，广泛采用二进制计、计算机以二进制为基础，广泛采用二进制计数。数。二进制计数的优点：二进制计数的优点：1）状态简单，易于实现。）状态简单，易于实现。2）算法简单。）算法简单。3）信息的存储和传输可靠。）信息的存储和传输可靠。4）节省设备。）节省设备。5）有数学工具）有数学工具-布尔代数布尔代数 二进制的缺点：二进制的缺点：1）人们不熟悉、不易懂。）人们不熟悉、不易懂。2）书写太长，使用不便。）书写太长，使用不便。2、十进制计数、十进制计数 计算机中十进制数的主要用途有两个计算机中十进制数的主要用途有两个 仅用于输入、输出仅
3、用于输入、输出-需二需二 十进制转换十进制转换 用于直接进行十进制运算用于直接进行十进制运算-需需BCD码码 常用的常用的BCD码有下面几种：码有下面几种：8421码码 余余3码码 2421码码十进制值十进制值8421码码余余3码码2421码码0000000110000100010100000120010010100103001101100011401000111010050101100010116011010011100701111010110181000101111109100111001111 3、八进制、十六进制计数八进制、十六进制计数八进制数八进制数 二进制数二进制数 十六进制十六进
4、制 二进制数二进制数 十六进制十六进制 二进制数二进制数0000000008100010011000191001201020010A1010301130011B1011410040100C1100510150101D1101611060110E1110711170111F1111 三、不同进位计数制数间的等值转换三、不同进位计数制数间的等值转换 1、任意的、任意的R进制数转换为十进制数进制数转换为十进制数-按权相加法按权相加法 2、十进制整数转换为任意的、十进制整数转换为任意的R进制整数进制整数-除除R取余取余法法 3、十进制小数转换为任意的、十进制小数转换为任意的R进制小数进制小数-乘乘R取
5、整取整法法 4、二进制数与八进制、十六进制数间的等值转换、二进制数与八进制、十六进制数间的等值转换 2.2 符号数的编码方法符号数的编码方法 一、机器数与真值一、机器数与真值 机器数是指数在计算机内部的二进制表示形式。机器数是指数在计算机内部的二进制表示形式。是把一个数的数值部分和符号均用二进制代码表示是把一个数的数值部分和符号均用二进制代码表示以后机器所能表示的数。以后机器所能表示的数。真值是指用一般书写形式表示的数。真值是指用一般书写形式表示的数。机器数的特点：机器数的特点：数的符号二进制代码化。数的符号二进制代码化。“0”0”代表，代表，“1”1”代表，且放在数据的最代表，且放在数据的最
6、高位。高位。小数点隐含在数据的某一固定位置上，不小数点隐含在数据的某一固定位置上，不占用存储空间。占用存储空间。机器数与机器的硬件规模有关，即与机器字机器数与机器的硬件规模有关，即与机器字长有关。长有关。二、原码表示二、原码表示：原码表示保持数据原有的数值部分的形式不变，原码表示保持数据原有的数值部分的形式不变，只将符号用二进制代码表示。原码表示是最简单的只将符号用二进制代码表示。原码表示是最简单的机器数表示方法。机器数表示方法。1 1、原码定义：、原码定义：2 2、在原码表示中，、在原码表示中，“0”0”有有“+0”+0”和和“-0”-0”之分。之分。+0+0原原=00 0=00 0 -0-
7、0原原=10 0=10 0 三、补码表示三、补码表示 1、补码的定义、补码的定义 2、补码的求法、补码的求法 3、特殊数的补码、特殊数的补码 4、补码的几个关系、补码的几个关系 1）补码与真值的关系）补码与真值的关系 2）补码与原码的关系）补码与原码的关系 3）机器正数与机器负数的关系）机器正数与机器负数的关系 4）补码的移位规则）补码的移位规则 5、补码的几何性质、补码的几何性质 从上面图中可以看出：从上面图中可以看出：1）正数的补码就是其本身；负数补码表示的）正数的补码就是其本身；负数补码表示的实质是将负数映像到正值区域。因此，加上实质是将负数映像到正值区域。因此，加上一个负数或减去一个正
8、数可以用加上另一个一个负数或减去一个正数可以用加上另一个数即补数来代替。数即补数来代替。2）从表示符号的角度，符号位的值代表了数）从表示符号的角度，符号位的值代表了数的正确的符号；从映像值来看，符号位的值的正确的符号；从映像值来看，符号位的值是映像值的一个数位，因此在补码运算中，是映像值的一个数位，因此在补码运算中，符号位与数值位一样参加运算。符号位与数值位一样参加运算。01234567-1-2-3-4-5-6-7-80000001001001000101011001110011000010011010110011011110111110111移码的几何性质真值真值移码移码 例1、设某机字长为
9、8位且采用整数表示。现已知机器数，试将其在不同的数据表示形式中所对应的十进制真值填入表内。表示形式机器数无符号数表示原码表示补码表示反码表示移码表示00110100110010111000000011111111 例例2、单项选择题、单项选择题 已知已知X1原原=11001010，X2补补=11001010 X3反反=11001010 则则X1、X2、X3的关系是：的关系是：1）X1 X2 X3 2）X2 X3 X1 3）X3 X1X2 4）X3 X2 X1 例例3、设一个六位二进制小数、设一个六位二进制小数X=0.a1a2a3a4a5a6 请回答下面问题。请回答下面问题。1）若）若X1/8，
10、则，则a1a2a3a4a5a6要满足什么条件？要满足什么条件？2）若）若X1/2，则，则a1a2a3a4a5a6要满足什么条件？要满足什么条件？3）若）若1/4 X 1/16，则，则a1a2a3a4a5a6要满足什么要满足什么条件？条件？010000或或001XXX或或0001且且a5a6至少有一个至少有一个1 2.3 2.3 数的定点表示与浮点表示数的定点表示与浮点表示 任何一个数均可表示为：任何一个数均可表示为：(N)(N)R RS SR Re e R:R:基值。计算机中常用的基值。计算机中常用的R R可取可取2 2、8 8、1616等。等。S S：尾数。代表数：尾数。代表数N N的有效数
11、字。计算机中一的有效数字。计算机中一般表示为纯小数。般表示为纯小数。e e：阶码。代表数：阶码。代表数N N的小数点的实际位置。一的小数点的实际位置。一般表示为纯整数。般表示为纯整数。一、定点表示一、定点表示 1 1、定点表示：约定计算机中参加运算的所有数、定点表示：约定计算机中参加运算的所有数据的小数点位置均是相同的而且是固定不变的。据的小数点位置均是相同的而且是固定不变的。定点表示是一种阶码定点表示是一种阶码e e的取值固定不变的机器的取值固定不变的机器数表示。数表示。2 2、定点数表示格式及数据表示范围：、定点数表示格式及数据表示范围：定点数有两种表示方法。定点小数和定点整数。定点数有两
12、种表示方法。定点小数和定点整数。尾尾 数数数符数符 尾尾 数数数符数符.（1位）位）（n位）位）（1位）位）（n位）位）纯小数纯小数纯整数纯整数1）原码表示的定点数表示范围原码表示的定点数表示范围机器数机器数真真 值值数数符符尾数尾数(n(n位位)定点小数定点小数定点整数定点整数最小正数最小正数0 0 00 00 01 012 2n n1 1最大正数最大正数0 0 11 11 11 111 12 2n n2 2n n1 1最大负数最大负数1 1 00 00 01 012 2n n1 1最小负数最小负数1 1 11 11 11 11(1(12 2n n)(2(2n n1)1)机器数机器数真真 值
13、值数数符符尾数尾数(n(n位位)定点小数定点小数定点整数定点整数最小正数最小正数0 0 00 00 01 012 2n n1 1最大正数最大正数0 0 11 11 11 111 12 2n n2 2n n1 1最大负数最大负数1 1 11 11 11 112 2n n1 1最小负数最小负数1 1 00 00 00 001 12 2n n2）补码表示的定点数的表示范围）补码表示的定点数的表示范围 3、比例因子的选择与溢出与溢出的概念比例因子的选择与溢出与溢出的概念 在定点运算中，参加运算的数据必须是定点小在定点运算中，参加运算的数据必须是定点小数或定点整数。因此在运算之前，必须选择一个数或定点整
14、数。因此在运算之前，必须选择一个恰当的恰当的比例因子比例因子，将所有参加运算的数均化成纯，将所有参加运算的数均化成纯小数或纯整数，然后再进行运算。运算结果再根小数或纯整数，然后再进行运算。运算结果再根据所选的比例因子转换成正确的值。据所选的比例因子转换成正确的值。比例因子必须选择恰当。选择太大，将会影响比例因子必须选择恰当。选择太大，将会影响运算精度；选择太小，会使运算结果超出机器所运算精度；选择太小，会使运算结果超出机器所能表示的数据范围，即出现溢出。能表示的数据范围，即出现溢出。溢出溢出：运算结果超出机器所能表示的数据范围。当：运算结果超出机器所能表示的数据范围。当出现溢出时，机器必须及时
15、识别并进行处理，一出现溢出时，机器必须及时识别并进行处理，一般采用中断的方法进行处理。般采用中断的方法进行处理。二、浮点数据表示二、浮点数据表示 1 1、浮点表示定义、浮点表示定义：浮点数据表示是指参加运算的各数的浮点数据表示是指参加运算的各数的小数点位置不是固定不变的，而是可以浮动小数点位置不是固定不变的，而是可以浮动的。即的。即 (N)(N)R RS SR Re e 中的中的 e e 值是可变的。值是可变的。由于由于 e e 的取值可变，因此在机器中必须将的取值可变，因此在机器中必须将 e e 表示出来。表示出来。2、浮点数据表示格式和数据表示范围浮点数据表示格式和数据表示范围 两种格式：
16、两种格式：1位 m位 1位 n位 1位 1位 m位 n位 3、浮点数的规格化表示浮点数的规格化表示 1）规格化表示的目的：充分利用尾数的位数，）规格化表示的目的：充分利用尾数的位数，表示更多的有效数字，以提高精度。表示更多的有效数字，以提高精度。2）规格化数的定义：）规格化数的定义：4、在浮点表示中，阶码和尾数位数的选择：、在浮点表示中，阶码和尾数位数的选择：在浮点数据表示中，一个浮点数由阶码和尾数在浮点数据表示中，一个浮点数由阶码和尾数两个部分组成。其中阶码的位数决定数据表示的两个部分组成。其中阶码的位数决定数据表示的范围；尾数的位数决定数据表示的精度。为了保范围；尾数的位数决定数据表示的精
17、度。为了保证更大的数据表示范围和更高的数据表示精度，证更大的数据表示范围和更高的数据表示精度，在计算机中通常都存在单精度浮点数、双精度浮在计算机中通常都存在单精度浮点数、双精度浮点数等多种浮点数格式。点数等多种浮点数格式。5、IEEE 754浮点数标准：浮点数标准：IEEE 754IEEE 754标准在表示浮点数时，每个浮点数均由三标准在表示浮点数时，每个浮点数均由三部分组成：符号位部分组成：符号位S S，指数部分，指数部分E E和尾数部分和尾数部分M M。浮点数可采用以下四种基本格式：浮点数可采用以下四种基本格式：(1)(1)单精度格式单精度格式(32(32位位)：E E8 8位，位，M M
18、2323位。位。(2)(2)扩展单精度格式：扩展单精度格式：E11E11位，位，M M3131位。位。(3)(3)双精度格式双精度格式(64(64位位)：E E1111位，位，M M5252位。位。(4)(4)扩展双精度格式：扩展双精度格式：E15E15位，位，M63M63位。位。S E M 数符数符 阶阶 码码 尾尾 数数 重点以重点以3232位单精度浮点数为例，介绍浮点位单精度浮点数为例，介绍浮点754754标准：标准：尾数尾数2323位，采用原码表示且采用隐藏位表示法；位，采用原码表示且采用隐藏位表示法；阶码阶码8 8位，采用特殊的移码，为移位，采用特殊的移码，为移127127码，即码，
19、即 EE移移 =127+E=127+E并规定如下：并规定如下：若若E E0 0，且，且M M0 0，则，则 N N为为0 0（真（真0)0)。若若E E0 0，且，且M0M0，则，则 N N(-1)(-1)S S2 2-126-126(0.M),(0.M),为非为非规格化数。为避免下溢而损失精度，允许采用比最规格化数。为避免下溢而损失精度，允许采用比最小规格化数小的非规格化数表示小规格化数小的非规格化数表示.若若1E2541E254，则，则 N N(-1)(-1)S S2 2E-127E-127(1.M)(1.M)。为规。为规格化数。格化数。若若E E255255，且，且M0M0，则，则 N
20、NNaNNaN (“非数值非数值”)。若若E E255255，且，且M M0 0，则，则 N N(1)1)S S(无穷大无穷大)。例例1：已知某机浮点数格式如下：已知某机浮点数格式如下：数符数符阶符阶符 阶阶 码码 尾尾 数数 0 1 2。5 6。111、该机所能表示的规格化最小正数、最大正数、最小负数、该机所能表示的规格化最小正数、最大正数、最小负数、和规格化最大负数的机器数的形式和它们所对应的十进制和规格化最大负数的机器数的形式和它们所对应的十进制值分别是什么？值分别是什么？2、已知用十六进制书写的机器数、已知用十六进制书写的机器数 1ECH、EC0H和和 FFFH，它们所表示的十进制值是
21、多少。它们所表示的十进制值是多少。3、试将十进制数、试将十进制数 12.25和和 35/2048表示为机器数并用十六表示为机器数并用十六进制书写。进制书写。例2：已知IEEE754单精度浮点数C4480000H和3F600000H，试求其所表示的十进制值。例3：将下列十进制数表示为IEEE754单精度浮点数并用十六进制书写。（1）78.125 （2）-567 （3）-9/512 三、定点表示与浮点表示的比较三、定点表示与浮点表示的比较 1.1.在字长相同的条件下，浮点表示的数据范在字长相同的条件下，浮点表示的数据范围大，精度高。围大，精度高。2.2.浮点运算算法复杂，所需设备量大，运算浮点运算
22、算法复杂，所需设备量大，运算速度慢。速度慢。2.4 2.4 非数值型数据的表示非数值型数据的表示 一、逻辑数一、逻辑数 二进制串二进制串 在计算机中一个逻辑数是用一个二进制串来在计算机中一个逻辑数是用一个二进制串来表示的。逻辑数具有下面几个特点：表示的。逻辑数具有下面几个特点：(1)(1)逻辑数没有符号的问题。逻辑数中各位逻辑数没有符号的问题。逻辑数中各位之间是相互独立的，既没有位权问题，也没之间是相互独立的，既没有位权问题，也没有进位问题。有进位问题。(2)(2)逻辑数中的逻辑数中的“0”0”与与“1”1”不代表值的大不代表值的大小，仅代表一个命题的真与假、是与非等逻小，仅代表一个命题的真与
23、假、是与非等逻辑关系。辑关系。(3)(3)逻辑数只能参加逻辑运算，并且是按位逻辑数只能参加逻辑运算，并且是按位进行的。进行的。二、字符与字符串二、字符与字符串 字符与字符串数据是计算机中用得最多的符号数据，字符与字符串数据是计算机中用得最多的符号数据，它是人和计算机联系的桥梁。为使计算机硬件能够它是人和计算机联系的桥梁。为使计算机硬件能够识别和处理字符，必须对字符按一定规则用二进制识别和处理字符，必须对字符按一定规则用二进制编码。编码。目前广泛使用的是目前广泛使用的是 ASCIIASCII码码(美国国家信息交换标美国国家信息交换标准字符码准字符码)和和EBCDICEBCDIC码码(扩展的二扩展
24、的二 十进制交换十进制交换码码)。ASCIIASCII码是用七位二进制表示一个字符，它包括码是用七位二进制表示一个字符，它包括1010个数字个数字(0(09)9)，5252个英文大、小写字母个英文大、小写字母(A(AZ Z，a a2)2)，3434个专用字符个专用字符(如，、如，、#等等)和和3232个控制字个控制字符符(如如NULNUL、LFLF、CRCR、DELDEL等等)共共128128个字符。个字符。ASCIIASCII字符编码符号的排列次序为字符编码符号的排列次序为b b6 6b b5 5b b4 4b b3 3b b2 2b bl lb b0 0，其中其中b b6 6b b5 5b
25、 b4 4为高位部分，为高位部分，b b3 3b b2 2b bl lb b0 0为低位部分。为低位部分。在计算机中，通常用一个字节表示一个字符。在计算机中，通常用一个字节表示一个字符。由于由于ASCIIASCII编码为七位二进制，字节的最高位编码为七位二进制，字节的最高位的作用：的作用：用作奇偶校验位，用来检测错误。用作奇偶校验位，用来检测错误。用于表示字符，形成扩展的用于表示字符，形成扩展的ASCIIASCII码。如码。如EBCDICEBCDIC码。码。EBCDIC(EstendedBinaryEBCDIC(EstendedBinary Coded Decimal Coded Decima
26、l Interchange Code)Interchange Code)是是IBMIBM公司常用的一种字公司常用的一种字符编码。它采用八位二进制数表示一个字符。符编码。它采用八位二进制数表示一个字符。在我国用于区分汉字和字符。如规定字节在我国用于区分汉字和字符。如规定字节的最高位为的最高位为“0”0”表示表示ASCIIASCII码，为码，为“1”1”表表示汉字编码。示汉字编码。字符串字符串 字符串是连续的一串字符，通常占用主存中多个字符串是连续的一串字符，通常占用主存中多个连续的字节进行存放连续的字节进行存放.一般一个字长可容纳多个字符，因此一般一个字长可容纳多个字符，因此 在计算机中，字符串
27、有两种存放方式：在计算机中，字符串有两种存放方式：低位字节存放方式低位字节存放方式 高位字节存放方式高位字节存放方式字节字节字节字节字节字节AA+1A+L-1 三、三、汉字信息的表示汉字信息的表示 为使计算机能够处理各种汉字信息，必须对为使计算机能够处理各种汉字信息，必须对汉字进行编码。汉字进行编码。汉字在计算机中的表示比较特殊。因为在计汉字在计算机中的表示比较特殊。因为在计算机中使用汉字，需要涉及到汉字的输入，算机中使用汉字，需要涉及到汉字的输入，存储与处理、汉字的输出等几方面的问题，存储与处理、汉字的输出等几方面的问题，因此汉字的编码也有多种类型。因此汉字的编码也有多种类型。汉字输入码汉字
28、输入码汉字内码汉字内码汉字字形码汉字字形码汉字交换码汉字交换码键盘输入键盘输入 存储、处理存储、处理交换汉字信息交换汉字信息显示、打印显示、打印 汉字交换码：汉字交换码：汉字交换码：用于不同汉字系统间交换汉字汉字交换码：用于不同汉字系统间交换汉字信息，具有统一的标准。信息，具有统一的标准。19811981年国家标准总局公布了年国家标准总局公布了信息交换用信息交换用汉字编码字符集汉字编码字符集，即即GB2312GB23128080，简称，简称国标码。该标准共收集汉字国标码。该标准共收集汉字67636763个，其中个，其中一级汉字一级汉字37553755个，二级汉字个，二级汉字30083008个，
29、再加个，再加上各种图形符号上各种图形符号682682个，共计个，共计74457445个。个。国标码规定每个汉字、图形符号都用两个国标码规定每个汉字、图形符号都用两个字节表示，每个字节只使用最低七字节表示，每个字节只使用最低七位。位。汉字内码：用于汉字信息的存储、交换、检汉字内码：用于汉字信息的存储、交换、检索等操作的机内代码，一般采用两个字节表索等操作的机内代码，一般采用两个字节表示。示。英文字符的机内代码是七位的英文字符的机内代码是七位的ASCIIASCII码，当用码，当用一个字节表示时，最高位为一个字节表示时，最高位为“0”0”。为了与英文字符能相互区别，目前我国的计为了与英文字符能相互区
30、别，目前我国的计算机系统中汉字内码都是以国标码为基础，算机系统中汉字内码都是以国标码为基础，在国标码基础上把每个字节的最高位置在国标码基础上把每个字节的最高位置“1”1”，作为汉字标识符。即机内码国标码作为汉字标识符。即机内码国标码8080H8080H 有些系统中，字节的最高位作为奇偶校验位，有些系统中，字节的最高位作为奇偶校验位，在这种情况下就用三个字节表示汉字内码。在这种情况下就用三个字节表示汉字内码。字形码：用点阵表示的汉字字形代码，它是字形码：用点阵表示的汉字字形代码，它是汉字的输出形式。又称字模。汉字的输出形式。又称字模。根据汉字输出的要求不同，点阵的多少也不根据汉字输出的要求不同，
31、点阵的多少也不同。同。简易型汉字为简易型汉字为16161616点阵，多用于显示。点阵，多用于显示。提高型汉字为提高型汉字为24242424点阵、点阵、32323232点阵，点阵，48484848点阵、点阵、64646464点阵、点阵、128128128128点阵，点阵，甚至更高，多用于打印。甚至更高，多用于打印。例：1616的汉字字形点阵，每个汉字要占用32个字节。2 25 5 十进制数串的表示十进制数串的表示 十进制数串在机器内部的表示有两种形式：十进制数串在机器内部的表示有两种形式：1 1、字符串形式、字符串形式 将十进制数串以字符串形式表示，即一个字节表示一个将十进制数串以字符串形式表示
32、，即一个字节表示一个十进制数字或符号。每个数字或符号的二进制编码就是它十进制数字或符号。每个数字或符号的二进制编码就是它的的ASCIIASCII码。码。根据数串中符号所处位置，又分为前分隔数字根据数串中符号所处位置，又分为前分隔数字串和后嵌入数字串两种表示形式。串和后嵌入数字串两种表示形式。在在前分隔数字串表示形式前分隔数字串表示形式中，符号位占用单独中，符号位占用单独一个字节，放在数字位之前。一个字节，放在数字位之前。在在后嵌入数字串表示形式后嵌入数字串表示形式中，符号位不单独占中，符号位不单独占用一个字节，而是嵌入到最低一位数字里面。其用一个字节，而是嵌入到最低一位数字里面。其规则是：若数
33、串的符号为正，则最低一位数字规则是：若数串的符号为正，则最低一位数字0 09 9的的ASCIIASCII编码不变编码不变(30H(30H39H)39H)；若数串的符号为；若数串的符号为负，则在最低数字位的负，则在最低数字位的ASCIIASCII码上加上码上加上40H40H，此时，此时数字编码为（数字编码为（70H70H79H79H）。）。十进制数的字符串表示主要应用于非数值处理，十进制数的字符串表示主要应用于非数值处理，如显示、打印。但对十进制数的算术运算很不方便，如显示、打印。但对十进制数的算术运算很不方便，因为每一字节只有低因为每一字节只有低4 4位表示数值，而高位表示数值，而高4 4位在
34、算术位在算术运算时不具有数值的意义。运算时不具有数值的意义。2 2、压缩的十进制数串：、压缩的十进制数串：用一个字节存放两个十进制数位，其值用用一个字节存放两个十进制数位，其值用BCDBCD码码表示，符号占半个字节，并存放在最低数值位之后。表示，符号占半个字节，并存放在最低数值位之后。通常用通常用11001100表示正号，表示正号，11011101表示负号。表示负号。在这种表示中，规定数字个数加符号位之和必在这种表示中，规定数字个数加符号位之和必须是偶数，否则在最高位之前补一个须是偶数，否则在最高位之前补一个0 0。压缩的十进制数串既节省了存储空间，又便于压缩的十进制数串既节省了存储空间，又便
35、于直接进行十进制算术运算，是广泛采用的十进制数直接进行十进制算术运算，是广泛采用的十进制数串表示方式。串表示方式。2.6 2.6 数据校验码数据校验码 数据校验码数据校验码：具有检测某些错误或带有自动纠：具有检测某些错误或带有自动纠正错误能力的数据编码。正错误能力的数据编码。数据校验码的基本原理是在合法的编码中加数据校验码的基本原理是在合法的编码中加入一些冗余码，使合法编码出现某些错误时，就入一些冗余码，使合法编码出现某些错误时，就成为非法编码。通过检测编码的合法性达到检错成为非法编码。通过检测编码的合法性达到检错的目的。的目的。常用的数据校验码有奇偶校验码、海明校验码、常用的数据校验码有奇偶
36、校验码、海明校验码、循环校验码。循环校验码。一、奇偶校验码一、奇偶校验码 奇偶校验码是一种最简单、最常用的校验码，奇偶校验码是一种最简单、最常用的校验码，广泛用于主存的读写校验或广泛用于主存的读写校验或ASCIIASCII码字符传送过程码字符传送过程中的检查。中的检查。1 1、基本原理：、基本原理：在在n n位有效信息位上增加一个校验位位有效信息位上增加一个校验位P P，构成，构成n n十十1 1位的奇偶校验码。校验位位的奇偶校验码。校验位P P的取值（的取值（0 0或或1 1）使）使n nl l位的奇偶校验码中位的奇偶校验码中“1”1”的个数为奇数（称为奇校的个数为奇数（称为奇校验验OddO
37、dd）或为偶数（称为偶校验）或为偶数（称为偶校验EvenEven）。）。校验位的位置在有效信息位的最高位之前或者校验位的位置在有效信息位的最高位之前或者在最低位之后。在最低位之后。校验时校验时，若，若n+1n+1位的奇偶校验码中，位的奇偶校验码中，“1”1”的个的个数不是奇数（奇校验）或不是偶数（偶校验）即表数不是奇数（奇校验）或不是偶数（偶校验）即表示有错。示有错。2、编码方程与校验方程：、编码方程与校验方程：设有效信息位为设有效信息位为Dn-1Dn-2Dn-3D1D0 其编码方程为：其编码方程为：Peven=D Dn-1DDn-2DDn-3DD1DD0 Podd=D Dn-1DDn-2DD
38、n-3DD1DD0+1 校验方程为：校验方程为：Eeven=D Dn-1DDn-2DDn-3DD1DD0 Peven Eodd=D Dn-1DDn-2DDn-3DD1DD0 Podd+1 3 3、奇偶校验的硬件实现：、奇偶校验的硬件实现：1 1）编码电路）编码电路：=1=1=1=1=1=11pevenpodd D6 D5 D4 D3 D2 D1 D0o 2）校验电路：）校验电路：=1=1=1=1=1=1=1 1偶校错奇校错 D6 D5 D4 D3 D2 D1 D0 Po4 4、奇偶校验的校错能力：、奇偶校验的校错能力：奇偶校验码只能发现奇数位个错误，而无法发奇偶校验码只能发现奇数位个错误，而无
39、法发现偶数位个错误，而且即使发现奇数位个错误也无现偶数位个错误，而且即使发现奇数位个错误也无法确定出错的位置；因而无法自动纠正错误。法确定出错的位置；因而无法自动纠正错误。但由于现代计算机可靠性比较高，出错概率很但由于现代计算机可靠性比较高，出错概率很低，而出错中只有一位出错的概率最高，因此用奇低，而出错中只有一位出错的概率最高，因此用奇偶校验检测一位出错，能够满足一般可靠性要求。偶校验检测一位出错，能够满足一般可靠性要求。在在CPUCPU与主存的信息传送过程中，奇偶校验被广与主存的信息传送过程中，奇偶校验被广泛应用。泛应用。二、海明校验码：二、海明校验码：海明校验码的实质是海明校验码的实质是
40、在奇偶校验的基础上，增加在奇偶校验的基础上，增加校验位的位数，构成多组奇偶校验，使每个有效信校验位的位数，构成多组奇偶校验，使每个有效信息位都被两个或多个校验位校验，这样不仅可以发息位都被两个或多个校验位校验，这样不仅可以发现错误而且还可确定出错位置并自动纠正错误。现错误而且还可确定出错位置并自动纠正错误。1、海明校验码校验位数的选择、海明校验码校验位数的选择 设有效信息位的位数为设有效信息位的位数为n n，校验位数为，校验位数为k k，则能够检，则能够检测一位出错并能自动纠正一位错误的海明校验码应测一位出错并能自动纠正一位错误的海明校验码应满足下面关系：满足下面关系：2 2k kn+k+1
41、n+k+1 由此式可计算出具有检由此式可计算出具有检1 1纠纠1 1错能力的海明校验码中错能力的海明校验码中n n与与k k的关系，如下表所示。的关系，如下表所示。有效信息位与校验位的关系有效信息位与校验位的关系 2、海明校验码的编码方法、海明校验码的编码方法 1）n n位有效信息选择位有效信息选择k k个校验位，构成个校验位，构成n+kn+k位的海明位的海明校验码。若校验码位号从左向右（或从右向左）按校验码。若校验码位号从左向右（或从右向左）按从从1 1到到n+kn+k排列，则校验位的位号分别为排列，则校验位的位号分别为2 2i i，i i0 0，1 1，2 2k k1 1，有效信息位按原排
42、列次序安排在其它位，有效信息位按原排列次序安排在其它位号中。号中。2）k k个校验位构成个校验位构成k k组奇偶校验，每个有效信息位组奇偶校验，每个有效信息位都被都被2 2个或个或2 2个以上的校验位校验。并且被校验的位个以上的校验位校验。并且被校验的位号等于校验它的校验位的位号之和。号等于校验它的校验位的位号之和。3 3）统计参与各组奇偶校验的位号，按奇偶校验原）统计参与各组奇偶校验的位号，按奇偶校验原理，由已知的有效信息求出各个校验位，进而形成理，由已知的有效信息求出各个校验位，进而形成海明校验码。海明校验码。3、海明校验码的校验方法、海明校验码的校验方法 校验时，校验时，K K个校验位进
43、行个校验位进行K K组奇偶校验，校验结组奇偶校验，校验结果形成果形成K K位的位的“指误字指误字”E Ek kE Ek-1k-1E E2 2E E1 1。若某组校验结果正确，指误字相应位为若某组校验结果正确，指误字相应位为0 0；若校；若校验结果错误，指误字相应位为验结果错误，指误字相应位为1 1。若校验结果。若校验结果 E Ek kE Ek-1k-1E E2 2E E1 1全全0 0，则表示无错；，则表示无错；E Ek kE Ek-1k-1E E2 2E E1 1全全0 0，则表示有错，则表示有错，并且指误字代码所对应的十进制值就是出错位的位并且指误字代码所对应的十进制值就是出错位的位号。将
44、该位取反，错误码即得到自动纠正。号。将该位取反，错误码即得到自动纠正。指误字指示出错的前提是代码中只存在一个错。指误字指示出错的前提是代码中只存在一个错。若有多个错，可能查不出来。若有多个错，可能查不出来。4 4、检、检2 2纠纠1 1错海明校验码错海明校验码 为了满足检为了满足检2 2纠纠1 1错的要求，在检错的要求，在检1 1纠纠1 1错海明校验错海明校验码的基础上再加一个校验位码的基础上再加一个校验位P P0 0 ，使其对整个，使其对整个n+kn+k位位的海明码进行奇偶校验。的海明码进行奇偶校验。编码时，首先按检编码时，首先按检1 1纠纠1 1错海明校验码的规则编制错海明校验码的规则编制
45、n+kn+k位的海明码，然后根据位的海明码，然后根据n+kn+k位中位中“1”1”的个数形成的个数形成P P0 0值，从而形成值，从而形成n+k+1n+k+1位的位的检检2 2纠纠1 1错海明校验码。错海明校验码。校验时首先由校验时首先由P0P0对整个对整个n+k+1n+k+1位海明校验码进行校验，位海明校验码进行校验，校验结果为校验结果为E0E0。然后再按检一纠一错海明校验码对。然后再按检一纠一错海明校验码对各组进行校验，得到指误字各组进行校验，得到指误字EkEkEkEk1 1E2E1E2E1。若校验结果若校验结果 E0E00 0，EkEkEkEkl lE1E100000 0 表示无错。表示
46、无错。E0E01 1，EkEkEkEkl lE100E1000 0 表示有一位出错，表示有一位出错，根据根据EkEkEkEkl lE1E1的值确定出错位号并自动纠正。的值确定出错位号并自动纠正。E0E00 0，EkEkEkEkl lE100E1000 0 表示有两位出错，表示有两位出错，此时无法确定出错位置，也无法纠错。此时无法确定出错位置，也无法纠错。E0E01 1，EkEkEkEkl lE1E100000 0 表示表示P0P0出错。出错。5、校错能力的讨论、校错能力的讨论 *码距的概念：码距的概念：在一组合法的编码中，任何两个编码中代码不同在一组合法的编码中，任何两个编码中代码不同的位数，
47、称为这两个编码的距离，其中最小的距离的位数，称为这两个编码的距离，其中最小的距离称为这组编码的码距，记作称为这组编码的码距，记作d。码距决定了一组编码。码距决定了一组编码的检错纠错的能力，校验位越多，码距越大，检错的检错纠错的能力，校验位越多，码距越大，检错纠错的能力越强。纠错的能力越强。若若 de+1,则可检测则可检测e个错误；个错误；若若 d2t+1,则可纠正则可纠正t个错误；个错误；若若 de+t+1且且et,则可检测则可检测e个错误，纠正个错误，纠正t个个错误。错误。三、循环冗余校验码（三、循环冗余校验码（CRC码）码）循环冗余校验码循环冗余校验码(Cyclic Redundancy
48、Check)(Cyclic Redundancy Check)简称简称为为CRCCRC码。是一种具有很强检错纠错能力的校验码，码。是一种具有很强检错纠错能力的校验码，广泛用于磁盘、磁带等辅助存储器的校验，在计算广泛用于磁盘、磁带等辅助存储器的校验，在计算机网络和通信中亦被广泛采用。机网络和通信中亦被广泛采用。1、基本原理、基本原理 若有效信息表示为多项式若有效信息表示为多项式M(xM(x)，选择一个约定的，选择一个约定的多项式多项式G(xG(x)，则有，则有 如果对于一个如果对于一个M(xM(x)，事先按某一，事先按某一G(xG(x)求得求得Q(xQ(x)和和R(xR(x)。传送时，把。传送时
49、，把M(xM(x)R(xR(x)作为编好的校验码传作为编好的校验码传送，当收到该校验码后仍用原约定的多项式送，当收到该校验码后仍用原约定的多项式G(xG(x)去去除，若能整除，即余数为除，若能整除，即余数为0 0，则表示该校验码正确；，则表示该校验码正确；若余数不为若余数不为0 0，表明有错，并可根据余数值确定出，表明有错，并可根据余数值确定出错位号，进行自动纠正。把错位号，进行自动纠正。把 G(xG(x)称为生成多项式。称为生成多项式。xGxQxRxM xGxRxQxGxM 2、编码方法、编码方法 1）已知）已知n位待编码信息（有效信息）为位待编码信息（有效信息）为M(xM(x)，选，选择某
50、一约定的择某一约定的k+1k+1位生成多项式位生成多项式G(xG(x)，构成，构成n+kn+k位的位的CRCCRC码。码。2 2）将）将M(xM(x)左移左移k k位，然后按模位，然后按模2 2除法规则除以除法规则除以G(xG(x)，得到得到k k位的余数位的余数R(xR(x).).3 3）将）将k k位的余数位的余数R(xR(x)倂接到倂接到M(xM(x)后面即得到后面即得到CRCCRC码。码。3 3、CRCCRC校验方法校验方法 将接收到的将接收到的n+kn+k位的位的CRCCRC码，除以原来约定的生成码，除以原来约定的生成多项式多项式G(xG(x),),若除得余数为若除得余数为0 0，表
