第二章数据信息的表示2007

1、1数据信息的表示2编码编码：用少量简单的基本符号，按照一定的组合规则，表示出大量复杂多样的信息。(数字、英文、中文)两大要素：基本符号的种类、符号的组合规则。 3真值与机器数真值：按一般书写形式表示的数值，可以是各种进制。机器数：在机器中连同数符一起数码化的数。有原码、补码、反码、移码四种表示法。 4原码定义：对于纯小数：设x=x0.x1x2xn-1，其中x0为符号位，小数点在符号位后不占存储位，共n位字长，则：x原=x 0 x 1-2-(n-1)1-x=1+|x| -(1-2-(n-1) )x 05原码 正数符号位为0，负数符号位为1，其余为不变。不够字长数值位后补0。 例：x1=+0.10

2、11,x1原=0.1011000 x2=-0.1011,x2原=1.1011000 正0：0.0000000, 负0：1.0000000 由于真值零占掉了两个编码，因此n位原码只能表示(2n-1)个原码。例如n=8，则只能表示28-1=255个原码。 真值原码的转换方法：6原码表示范围：n=8位 最大小数原码 0.111 1111： 0.111 1111=1-0.000 0001=1-2-(8-1) 最小小数原码 1.111 1111 (-0.1111111) -0.111 1111=-(1-0.000 0001) =-(1- 2-(8-1)337原码定义：对于纯整数，设x=x0 x1x2xn

3、-1，其中x0为符号位，共n位字长。则：x原=x 0 x 2(n-1)-12(n-1)-x=2(n-1)+|x| -(2-(n-1) -1)x 08原码真值原码的转换方法：正数符号位为0，负数符号位为1，其余为不变。不够字长，符号位后，数值位前补0。例：x1=+1011,x1原=00001011 x2=-1011,x2原=10001011正0：00000000, 负0：100000009原码表示范围：最大整数=0 111 1111=27-1=127最小整数=1 111 1111=-(27-1)=-127原码的优点：直观、转换容易。缺点：实现加减法运算难。10补码模的概念：任何大于模的数，都可将

4、模的整数倍丢掉而不至于造成错误。 例：时钟调校：10点调到6点 方法一：正拨8，10+8=18mod 12=6 方法二：倒拨4，10-4=10+(-4)+12=10+8=18 (mod12)=6 既A-B=A+(-B)+K 模K将补码引入计算机可将减法转换为加法。11补码定义：对于纯小数，x=x0.x1x2xn-1，共n位字长，其中0是符号位(20)，符号位向更高位进位将丢失(模为21)，则x补=x 0 x 1-2-(n-1)2+x=2-|x| -1 x 0可见，对于纯小数正数补码、原码相同。12补码对于负数，X=x0.x1x2x3x n-1, |X|=0. x1x2x3x n-1,X补=2-

5、|X| =10-|X| =1.1111+0.001-0. x1x2x3x n-1 =1.111-0. x1x2x3x n-1+0.001 =1. +0.0001其中 为1-xi即按位取反。 求负数补码的方法为：除符号位外，数值位按位取反，末位加1。1x)1( nxxi13补码真值（原码）补码： 如果符号位为0，则该数为正数， 补码=原码 如果符号位为1，则该数为负数， 补码=除符号位外，原码按位取反，末位加1。 例：若x1=+0.1011, x2=-0.1011，字长为8位，则其补码分别为：x1补=0.1011000 x2补=1.0100111+0.0000001=1.0101000 +0补=

6、0.000 0000 -0补=1.000 0000补= 1.111 1111+0.000 0001=0.000 0000 14补码已知补码求真值（原码）的方法： 如果符号位为0，则该数为正数，补码所表示的数即为真值。 如果符号位为1，则该数为负数，原码值为补码按位取反末位加1。 15补码表示范围： 补码可表示的最小数值是(-1)补=1.000 0000 最大值与原码相同1-2(n-1) 字长n位3316补码定义：对于纯整数，设x= x0 x1x2x3x n-1，共n位字长，其中x0为符号位，模为2n，它的补码定义为： x补=X 0 x 2n-1-1 2n+x= 2n -|x| -2n-1 x0

7、17补码真值 补码：同纯小数。例：x1=1011，x2=-1011，字长为8位，补码分别为：x1补=00001011x2补= 28-0001011=100000000-0001011=1111010118补码对于真值0，其补码是唯一的，即+0补=-0补=000表示范围：n=8时 最小整数 (-128)补=1000 0000 最大整数127 即-2n-1至2n-1-119补码n位补码能表示2n个补码。 纯小数补码表示中，(-1)补=1.000 0000 纯整数中，(128)补=1000 0000 注意：在纯整数中(-1)补 =(1000 0001)补 =1111 111120反码定义：对于纯小数

8、， x0.x1x2x3x n-1，共n位字长，反码的定义为：x反=X 0 x 1- 2-(n-1) (2- 2-(n-1) )+x -(1- 2-(n-1) )x0 转换方法： 对于正数，原码反码相同， 对于负数，除符号位外，将原码的数值位按位取反。21反码例：x1=+0.1011,x2=-0.1011，字长为8位 则其反码分别为： x1反=0.1011000， x2反=1.0100111 +0反=0.00，-0反=1.11122反码定义：对于纯整数， x0 x1x2x3x n-1，共n位字长，反码的定义为：x反=X 0 x 2(n-1) -1( 2n-1 )+x -( 2(n-1)-1 )x

9、0 转换方法：同纯小数。+0反=000，-0反=111123反码取值范围：同原码可表示数据个数：同原码24移码若纯整数x为n位（包括符号位），则其移码定义为 x移=2(n-1)+x，- 2(n-1)x 2(n-1)-1 移码用在计算机浮点数的阶码（表示指数，都是整数）中，所以不研究纯小数。 移码的转换方法：将补码符号位取反 表示范围：与补码相同(-128)移=0000 0000 (127)移=1111 1111 x1x2 x1移x2移25移码例：x=+1000，设字长为8位，则： x补=00001000 x移=27+x补=10000000+00001000=10001000 x=-1000，则

10、： x补=11111000 x移=27+x补=1000000+11111000=01111000 0的移码是唯一的：+0移=-0移=10026转换方法小结原码移码反码补码符号位取反除符号位，按位取反+1，0除符号位，按位取反，0只有整数真值+ 0- 127作业2.1 2.2x/2补 y/2补 2.3 -2y补 2.5 (2)28数的定点、浮点表示不同种类的计算机，数的表示是有差别的，不能相互识别。不同计算机的指令也有很大差别。“数据结构”课程主要研究各类型数据内部逻辑结构和物理结构之间的关系（软）。“数据表示”研究能由计算机硬件直接识别的数据类型，如：“定点数”、“浮点数”（硬）。29数的定点

11、表示数据的定点表示 1.定点小数：将小数点固定在符号位d0之后，数值最高位d-1之前，由于小数一般用浮点数表示，所以定点小数不常用。计算机中小数的小数点是用隐含位置来表示的。根据小数点的位置是否固定，可分为定点表示和浮点表示。符号小数点位置（隐含）n-1位数值位30数的定点表示2.定点整数 将小数点固定在数的最低为之后。符号位小数点位置（隐含）n-1位数值位31数的定点表示带符号、不带符号的定点整数带符号的定点整数：一般用于算术运算的操作数，可用原码、补码、反码表示。不带符号的定点整数：一般用于表示字符、逻辑量、特征值等。 1. 为了兼顾效率和硬件复杂度，目前计算机大都采用多种定长定点整数。3

12、2数的定点表示例：Intel8086 1. 无符号二进制数： 8位取值范围：00H0FFH 16位取值范围：0000H0FFFFH2. 带符号二进制数： 8086系列芯片的有符号数是用补码表示的。 8位取值范围：80H7FH 即 128127 16位取值范围：8000H7FFFH即-327683276733数的定点表示注意：数据的表示范围随数机器码表示方法的不同而不一样。定点小数：若字长为n位，用原码表示时， 负数范围：1.111111.0001，即 - (1-2-(n-1) -2-(n-1) 正数范围：0.001 0.111，即： 2-(n-1) (1-2-(n-1) 所以，表示范围为：-(

13、1-2-(n-1) (1-2-(n-1) 。 若字长为n位，用补码表示时， 负数范围：1.00.01.111，即：-1-2-(n-1) 正数范围：0.0010.1111，即：2-(n-1) (1-2-(n-1) 所以，范围为-1(1-2-(n-1) 。34数的定点表示 定点整数：若字长为n，原码表示时范围为：-(2(n-1)-1) 2(n-1)-1。补码表示时范围为：-2(n-1) (2(n-1)-1)。 溢出处理： 绝对值小于最小数当做机器0处理，称为“下溢”。（定点小数） 大于最大正数或小于绝对值最大的负数称为“溢出”，此时计算机将中止运算做溢出处理。035数的定点表示定点数的缺点： 对于

14、定点计算机，既有整数部分又有小数部分的数必须变为约定的定点数形式才能处理。所以编程时需要设定一个比例因子，所得的数还要根据比例因子还原成实际的数值。 但实际计算时常常遇到非常大或非常小的数，比例因子难以确定。让小数点根据需要浮动可解决这一问题。这就是浮点数。36数的浮点表示数N=M*RE 其中R为阶的基数，通常R=2、8、16 E称为阶码(Exponent) M称为尾数(Mantissa) 它们都是带符号的定点数。在大多数计算机中，尾数都是纯小数，多用补/原码。阶码为定点整数，多用移码或补码表示。37数的浮点表示1.浮点数的表示格式： 格式1：阶符，即指数部分的符号位。1位阶码值（表示幂)。m

15、-1位。尾数部分符号位。1位。数符尾数值部分。n-1位 基数R约定为2（一旦机器的浮点部件设计好，R就不可再改变，所以一般都不在表示中出现）， 通常阶码采用补码表示的定点整数形式，尾数用补码定点小数形式。 38数的浮点表示格式2：数符阶符阶码值尾数值此种形式，通常阶码采用移码形式。阶码39数的浮点表示2. 浮点数的规格化形式： 浮点数都是近似表示的，精度由尾数决定，数的表示范围大小由R、E决定。为了提高精度需要使尾数的有效位数尽可能占满可用的位数。这种措施称为浮点数的规格化。规格化要求尾数： 1/R=|M|1 R=2时： =|M|1 即2-1=|M|20 (0.1)2=|M|(1)240数的浮

16、点表示 将一个浮点数转换为规格化的过程，称为浮点数规格化。 右规：尾数右移一位，阶码+1 左规：.左-1 注：隐藏位 对于规格化浮点数小数点后第一个值是固定的（正数：1，负数：原码1，补码0），所以该位往往缺省，称为隐藏位。41数的浮点表示例：用格式2，共32位，数符1位，阶码8位用移码，其余位为尾数。 0.1101 0001*210110 数符：+ 0 阶码：10110 0001 0110 0001 0110 1001 0110 尾数：1101 0001 1010 0010 00 所以：0 1001 0110 1010 0010 008补移隐藏位42数的浮点表示例:某机用32位表示一个数，阶

17、码部分占8位（含一位符号位）。设x1=-256.5,x2=127/256。请写出x1和x2的两种浮点数表示格式。解：1）x1=-256.5=-(100000000.1)2=-29*0.1000000001阶码的补码为+9补=00001001，移码为10001001，尾数=1.01111111110000000000000（规格化补码）第一种格式为：00001001，1.01111111110000000000000十六进制表示的格式为：09BFE000第二种格式为：1，10001001，01111111110000000000000十六进制格式为：C4BFE00 2）作业43数的浮点表示3.

18、浮点数的表示范围：浮点数的机器0：1）尾数M=0，并且2）阶码有n+1位时，E=-2n （n+1=8位时，E=-128 移码=0000 0000 -128是此时阶码可表示的最小值）44数的浮点表示 对于32位字长浮点数，一位符号位。8位阶码用移码，尾数23位用原码，尾数规格化，第一位隐藏。基数为2。求表示范围。1）阶码：8位移码，所以表示范围-1281272）尾数：原码，隐藏一位，所以是24位。 所以：最小正数0.100=0.5（不是0.001因为规格化） 最大正数0.1 1=(1-2-24)所以，正数范围0.5*2-128(1-2-24)*2127 同理：最小负数=1.111= -(1-2-

19、24) 最大负数=1.100=(-0.5)所以，负数范围-(1-2-24)*2127-0.5*2-12845数的浮点表示4.浮点数的溢出： 浮点数的溢出是对规格化的阶码进行判断。 阶码大于机器的最大阶码，称为上溢，此时机器不能再继续运算，一般进行中断处理。 阶码小于最小阶码，称为下溢，把浮点数各位强迫为0，机器仍可继续运行。正上溢负下溢负上溢正下溢-(1-2-24)*21270.5*2-128-0.5*2-128(1-2-24)*212746数的浮点表示5. 浮点数表示数据的分布密度定点数在数轴上，除了原码的+-0，其余均匀分布。浮点数在数轴上不均匀分布，因为：1）浮点数尾数固定：0.100至

20、0.112）阶码变化：|E|=0某一值 所以，阶码取m+1时比取m时区域覆盖大一倍，但其中的数据个数是一样的，所以，离原点越远越稀。47数的浮点表示6. IEEE754中浮点数标准1）IEEE标准委员会1985年3月批准的。内容包括：浮点数表示形式、类型、定义、舍入方式、例外处理等。2）IEEE754浮点数的格式：尾数用原码，指数用移码。格式如下： 对于单精度字长32，s为符号位，阶码e为8位，f为23位，尾数最高位隐藏。 48数的浮点表示(1)若e=（1111 1111）2=255且f0，则无论s取何值，浮点数v为NaN（非数）。(2)若e=255且f=0，则v=(-1)s*，为。(3)若0

21、e255, 则v=(-1)s*2e-127*(1.f)。(4)若e=0且f 0，则v=(-1)s*2e-126*(0.f)(5)若e=0且f =0，则v=(-1)s*0，即0。 对于双精度字长64，阶码e为11位，f为52位，尾数最高位隐藏。相应255、127、126各值改为2047、1023、1022。49数的浮点表示(1)若e=（1111 1111）2=255且f0，则无论s取何值，浮点数v为NaN（非数）。(2)若e=255且f=0，则v=(-1)s*，为。(3)若0e255, 则v=(-1)s*2e-127*(1.f)。(4)若e=0且f 0，则v=(-1)s*2e-126*(0.f)

22、(5)若e=0且f =0，则v=(-1)s*0，即0。 对于双精度字长64，阶码e为11位，f为52位，尾数最高位隐藏。相应255、127、126各值改为2047、1023、1022。前面讲的规格化形式是：移码偏移量为128，尾数规格化为0.1f.IEEE754规格化为：1.f的形式，移码偏移量12750数的浮点表示例2.6：0.15625=(0.00101)2 0.00101 0.101*2-2 规格化 1.01*2-3 IEEE规格化 阶码偏移量为127，所以： e=127-3=124=(0111 1100)2 所以，IEEE754单精度浮点数为： 0 0111 1100 010051数的

23、浮点表示例2.6：-5=-101 数符：1 IEEE规格化1.01*22 e=127+2=129=(1000 0001)2 IEEE754单精度浮点数： 1 1000 0001 010052数的浮点表示例2.7：IEEE754单精度浮点数用十进制表示。1 1000 0001 00100S=1 e=129 f=1/8=0.125代入公式（3）(-1)1*22*(1.125)=-4.553定点与浮点表示的比较 数值的表示范围 ：浮点表示法所能表示的数值范围将远远大于定点表示法 。精度 ：对于字长相同的定点数与浮点数来说，浮点数虽然扩大了数的表示范围，但这是以降低精度为代价的，也就是数轴上各点的排列

24、更稀疏了 。数的运算 ：浮点运算要比定点运算复杂 。溢出处理 ：定点运算时，当运算结果超出数的表示范围，就发生溢出；而在浮点运算时，运算结果超出尾数的表示范围却并不一定溢出，只有当阶码也超出所能表示的范围时，才发生溢出。 54定点与浮点表示的比较 浮点数在数的表示范围等方面优于定点数；但运算器线路比较复杂，运算速度比较慢，价格也较高。并不是所有的计算机都具有浮点运算功能，通常计算机可以分为：定点机、定点机加浮点运算部件（如Intel 80 x87协处理器）、浮点机。55作业2.7 2.8(100.25)d转IEEE754单精度IEEE754单精度0C1C90000H转十进制56非数值数据的表示

25、 非数值数据：字符、字符串、图形符号、汉字和逻辑数据等各种数据 。1. 字符的表示法 ：字符编码方式有很多种，国际上普遍采用了一些标准化代码：ASCII码(8位)、扩展BCD交换码 、Unicode码(16位)等。例：表2-5的ASCII码表。 57非数值数据的表示 基本ASCII码： 0 ，共8位，最高位为0。共27=128个不同组合。 查表时，通过列确定高3位，行确定低四位。 例：0000 0111 BEL扩展ASCII码： 最高位为1，虽然美国国家标准信息协会也给出了其定义。但各国都自己定义其含义。58非数值数据的表示 2.字符串的表示 ：占用主存中连续的多个字节，每个字节存一个字符。

26、从高位字节向低位字节 从低位字节向高位字节的顺序存放 主存中每个字节存的都是相应字符的ASC编码值 。 例：P35 （此例中4个字节一行，几个字节一行与主存的字长有关）3.汉字的表示法 ： 汉字编码：汉字输入码 汉字交换码 汉字机内码 汉字字型码 59非数值数据的表示 数字编码字音编码字型编码交换码汉字机内码字型码打印汉字显示汉字60非数值数据的表示 数字编码字音编码字型编码交换码汉字机内码字型码打印汉字显示汉字电报码区位码61非数值数据的表示 数字编码字音编码字型编码交换码汉字机内码字型码打印汉字显示汉字全拼双拼62非数值数据的表示 数字编码字音编码字型编码交换码汉字机内码字型码打印汉字显示

27、汉字五笔63非数值数据的表示 数字编码字音编码字型编码交换码汉字机内码字型码打印汉字显示汉字GB2312-80，用于不同汉字系统间进行交换，也称为国际码。国际码=区位码+2020H64非数值数据的表示 数字编码字音编码字型编码交换码汉字机内码字型码打印汉字显示汉字用于汉字信息存储、交换和处理操作。 汉字机内码为两字节长的代码，为了与ASCII码区别，最高位置1汉字机内码=汉字国标码+8080H。 65非数值数据的表示 数字编码字音编码字型编码交换码汉字机内码字型码打印汉字显示汉字点阵字库66逻辑数据的表示法 逻辑数据是用来表示二值逻辑中的“是”与“否”、或“真”与“假”两个状态的数据。计算机中

28、的基2码的两个状态“1”和“0”就能表示逻辑数据的两个状态。例如用“1”表示真，则“0”就能表示假。 67十进制数串的表示 二十进制编码 (Binary Coded Decimal) : 是用4位二进制数表示1位十进制数字，它具有二进制的形式，又具有十进制的特点。不是将十进制数转换为二进制。 68十进制数串的表示 4位二进制数，有16种不同的状态，从中选出10个状态来表示十进制数的09，有多种选择方法。常用的几种: 十进制有权码:有权码是指表示十进制数的4位二进制数中的每一位都有一个确定的权值。 8421码：4位二进制数中的每一位从左到右的权分别为8、4、2、1。则数字09的8421编码为00

29、00，0001，1001。 例：(259)d所对应的8421码为0010 0101 1001。 对应的二进制数为：1 0000 0011 69十进制数串的表示 十进制无权码: 无权码指表示一个十进制数的4位二进制码的每一位都没有确定的权值。 余3码(Excess 3Code)：8421码+0011 格雷码(Gray Code)，格雷码又称循环码，如表2-7所示。70十进制数串的存储 大多数通用性较强的计算机，都能直接处理十进制形式表示的数值。采用十进制表示数据可提高机器的运行效率、提高数据的表示范围和运算精度，（十进制数在计算机处理时是以十进制的位组成的数串形式存储与计算的，其位数即串长是可变

30、的，规定了最长可用位数，因此不受二进制整数和浮点数统一格式的约束）。71十进制数串的存储 非压缩的十进制数串 ：非压缩的十进制数串实际上就是前述的字符串，即一个字节存放一个十进制数或符号的ASC码(7位)。十进制数串占用主存连续的多个字节。 为了指明一个数串，需要给出该数串在主存中的起始地址和串长。 72十进制数串的存储 前分隔式数字串是让符号位占用单独一个字节，并把符号位放在数字位之前，用字符“+”表示正号，用字符“-”表示负号，每个数字位占用一个主存字节，存放的是0到9十个数字字符中相应一个字符的ASC编码值。 例:+123 在主存中为 2B、31、32、33 -45678在主存中为 2D

31、、34、35、36、37、3873十进制数串的存储 后嵌入数字串是不再为符号位单独分配一个字节，而是把它嵌入到最低一位数字里。其规则是把负号变成十六进制的40，并将其与最低数字位的值相加。 例：+123存为 31 32 33 -123存为 31 32 7374十进制数串的存储 2. 压缩的十进制数串： 一个字节可存放两位BCD码表示的十进制数， 用压缩的十进制数串表示一个数，要占用主存连续的多个字节。 每个数位占用半个字节，其值可用BCD码或数字字符的ASC码的低4位表示。 符号位也占半个字节并放在最低数字位之后，其值选用BCD码中的六种冗余状态中的有关值，如用12（C）表示正号，用13（D）

32、表示负号。 规定数位加符号位之和必须为偶数，当和不为偶数时，应在最高位数字之前补一个“0”。 例如+123表示为 123C ,-23表示为023D。 附加的75数据信息的校验 数据的校验码就是一种带有发现错误或者带有自动改正错误能力的数据编码方法。它的基本原理是在合法的数据编码之间加进一些冗余码，使合法的数据编码出现某些错误时就变成非法编码，通过检测编码的合法性来达到发现错误的目的。 76数据信息的校验 码距：任意两个合法编码之间至少有几个二进制位不相同，不相同的位数称为此编码的码距。码距为1的编码不能发现错误。 例：4位二进制数编码的十六个编码全为合法编码，那么任何一个编码出现错误都会变成另

33、外一个合法编码，因此就查不出错误。 希望传送的代码为0000 经传送后产生了错误，被传送为0001 而0001也是一合法代码。 所以，码距大于1的编码才能发现错误或校正错误。 77奇偶校验码 奇偶校验码是一种开销最小的校验码，它的实现原理是使原来合法编码的码距由1变为2。可发现奇数个数位出错，但不能指出出错位置。78奇偶校验码 1水平奇偶校验 ：实现的方法是为数据信息(设n位)再补充一个二进制位的校验位。 偶校验：约定数据信息位+校验位中1的个数为偶数（数据信息中“1”的个数为奇数时，校验位填“1”，否则校验位填“0”） 奇校验： 把数据信息连同它的校验位共(n+1)位作为合法代码写入主存。当

34、从主存读出这个代码时，通过检测电路检测这(n+1)位代码的合法性 。79奇偶校验码 数据 奇校验编码 偶校验编码 00000000 100000000 000000000 00110010 000110010 100110010 10111111 010111111 11011111180奇偶校验码 ASC编码 奇校验编码 偶校验编码 “0” 01100001011000000110000“A” 1000001 1100000101000001 “C” 10000110100001111000011在表2.8和表2.9所示的奇校验码或偶校验码中，最高一位为校验位，其余几位为信息位。实际应用中多

35、数采用奇校验，因为奇校验中不存在全“0”代码，在某些场合下更便于判别。 81奇偶校验码 奇偶校验码的编码和校验是由专门的电路实现的，常见的有并行奇偶统计电路，如图2-3所示：这是一个由若干个异或门组成的结构，以下给出了P偶、P奇、“偶校验出错”和“奇校验出错”等信号。校验位P偶=D7D6D5D4D3D2D1D0校验位P奇=偶校验出错=P偶D7D6D5D4D3D2D1D0奇校验出错=D0D1D2D3D4D5D6D7D0D1D2D3D4D5D6D7 P奇82奇偶校验码 图奇偶校验位的取值及校验电路23 D7D6D5D4D3D2D1D0D校ABP偶P奇偶校验出错 奇校验出错 83奇偶校验码 2垂直奇

36、偶校验 ：垂直校验是把被校验的数据分成定长的若干组，每一组中对于相同的位附加一个校验位，校验码同样可以用奇校验，也可以用偶校验。例：4个字节为1组，该组数的奇校验码和偶校验码： 垂直奇校验码被校验码-0100110100011111101101100001101100000000垂直偶校验码被校验码-101100100001111110110110000110110000000084奇偶校验码 3水平垂直奇偶校验：水平校验和垂直校验还可以联合起来使用，提高代码的校验能力。水平垂直校验的方法是把垂直校验的代码连同垂直校验码一起再附加1位水平校验位。还是上面的例子，水平垂直校验码为：0 00000

37、000 被 1 00000000 被0 00011011 校 1 00011011 校1 10110110 验 0 10110110 验1 00011111 位 0 00011111 位0 01001101垂直奇校验码 1 01001101垂直奇校验码 水平偶校验位 水平奇校验位85海明校验码 海明校验的实现原理：在数据中加入k个校验位，把数据分配到k个奇偶校验小组中去。如果要求能检测与自动校正一位，发现两位错，则N=k+r 2k 1校验码共为N位有效信息位为r位校验位为k位86海明校验码 r 12-45-1112-26 27-57 58-120k 234567 校验码分成k组作奇偶校验，产生

38、k位检错信息。这k位就构成一个指误字，可指出2k种状态，其中一状态表示无错，余下的组合状态就能指出2k 1位中某位出错。r、k关系见下表：87海明校验码 分组原则： 1每个校验位Pi分配在海明码的第2i-1的位置上。海明码其余各位为有效信息位，并从低向高依次排列。 2海明码的有效信息位由多个校验位进行校验。 被校验位的位码=所有校验这位的校验位位码之和。 3校验位仅参加一组校验。 88海明校验码 例：海明码位置号： H15 H14 H13 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 D10 D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0

39、 P2 P1 校验码分别位于：20，21，22，23位上。 21-1=124-1=823-1=422-1=289海明校验码 校验关系如表2-10。计算方法由2确定： 如D0位于H3，3=2+1，所以由位于H1和H2的P1、P2校验。 D9位于H14，14=8+4+2，所以由位于H8和H4、H2的P4、P3、P2校验 各校验位由本身校验。90海明校验码 由此表可得，偶校验时P1P4取值的逻辑表达式： P1=D0D1D3D4D6D8D10 P2=D0D2D3D5D6D9D10 P3=D1D2D3D7D8D9D10 P4=D4D5D6D7D8D9D10即它所能够校验的数据位的异或。至此，发送方已将海

40、明码求出。91表 海明码的分组210 PPDPDDDPDDDDDDD1203123445678910海明码HHHHHHHHHHHHHHH123456789101112131415海明码位号122.1(3= 2+ 1)44.1(5= 4+ 1)4.2(6= 4+ 2)4.2.1(7= 4+ 2+ 1)88.1(9= 8+ 1)8.2(10= 8+ 2)8.2.1(11= 8+ 2+ 1)8.4(12= 8+ 4)8.4.1(13= 8+ 4+ 1)8.4.2(14= 8+ 4+ 2)8.4.2.1(15= 8+ 4+ 2+ 1)参与校验的校码位位号PPPPPPPPPPPPPPPPPPPPPP12

41、21331323214414242143、PPPPPPPPPP4314324321、参与的校验码92海明校验码 当海明码数据传送到接收方后，再把P1、P2、P3和P4右边的逻辑表达式再分别异或上P1P4的值，得到： G1=D0D1D3D4D6D8D10P1 G2=D0D2D3D5D6D9D10P2 G3=D1D2D3D7D8D9D10P3 G4=D4D5D6D7D8D9D10P4 当采用偶校验时，G1G4的值为“0”，则传送正确。当不为上述值时，传送就有错误。通过查表2-10可知是哪一位出错。 93海明校验码 例：G1G2G3G4=0011 说明P3=1、P4=1 查表2-10得出错位H12即

42、D7 G1G2G3G4=0111 说明P2=1、P3=1、P4=1 查表2-10得出错位H14即D9 94海明校验码 指误字无错出错位号含义1234567891011121314第一组G1000第二组G2011第三组G3001第四组G400195海明校验码 例2.8请求出数据10110100110的海明码，用4位校验位采用偶校验方式。解：已知D10 D9 D8 D7 D6 D5 D4 D3 D2 D1 D0=10110100110 则： P1=0100011=1 P2=0101001=1 P3=1101101=1 P4=0101101=0将校验位放到数据码中去，形成海明码：海明码位置号：H15

43、 H14 H13 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1海明码： 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 D10 D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1将这个海明码传送到接收方后，假设D9产生错误，应该是G4、G3、G2为“1”，G1仍为“0”；如果校验位P2产生错误，只有G2=1，G4、G3、G1为“0”。96循环冗余校验码 CRC码一般指的是在k位信息码之后再拼接r位校验位。其编码格式如下图：97循环冗余校验码 1.模二运算：模2运算是指以按位模2相加为基础的四则运算，运算时不考虑进位和借位。(1) 模2加减：即按位加，可用异或逻辑实现。模2加与模2减的结果相同，即00=0，01=1，10=1,11=0。(2) 模2乘：按模2加求部分积之和。(3) 模2除：按模2减求部分余数。上商的原则是当部分余数的首位为“1”时，商取“1”；当部分余数的首位为“0”时，商取“0”。当部分余数的位数小于除数的位数时，该余数即为最后余数。 98循环冗余校验码 2. CRC码的原理和编码规则： 1)设被传送的k位二进制信息用表达式C(x)表示 C(x)=Ck-1Ck-2C1C0 Ci取值0或1 2)将C(x)左移(n-k)位(即左移r位)，即C(x)2r。这样C(x)的右边就会空出r位，这r位