第二章(数据的表示与数据校验)77

1、第2章数据的表示与数据校验本章主要内容 数据表示形式的多样性 二进制数值数据的编码格式 信息传输过程中的检错与纠错码2.1 数据表示形式的多样性 数值、文字、符号、语音、图形、图像等数值、文字、符号、语音、图形、图像等统称数据，在计算机内部，都必须用统称数据，在计算机内部，都必须用数字数字化编码化编码的形式被的形式被存储存储、加工加工 、传送传送 。 数字化编码数字化编码二要素二要素 少量简单的基本符号少量简单的基本符号 一定的组合规则一定的组合规则 表示表示大量复杂多样大量复杂多样的信息的信息2.1.1 适合于人的数据表示形式 如时钟、十进制、语音数据、图形数据等。 输入计算机之前的数据、计

2、算机输出的数据都要力争符合人的习惯。2.1.2 适合计算机的表示形式-编码 采用二进制的理由 符号个数最少，物理上容易实现(数字电路)。用二个状态如导通/截止，高/低电压等来表示，比用十个状态方便。 用二进制码表示数值数据运算规则简单。加法和乘法各只有4条运算规则。 十进制与二进制转换简单。 与二值逻辑的真、假两个值对应简单。 高电压1，低电压-0。二进制无符号数据算术运算规则二进制无符号数据算术运算规则(1) 加法运算规则加法运算规则 0+0=0 例如：例如： 0101 0+1=1 +) 0001 1+0=1 0110 1+1=0 并产生进位并产生进位(2) 减法运算规则减法运算规则 0-0

3、=0 例如：例如： 1011 0-1=1 并产生借位并产生借位 -) 0101 1-0=1 0110 1-1=0二进制数据算术运算规则(3) 乘法运算规则 例如： 1101 0X0=0 X) 0101 0X1=0 1101 1X0=0 1101 1X1=1 1000001(4)除法运算规则 1101 例如： 1110101/1001 1001 1110101 1001 1011 1001 01001 1001 0 0000进位记数法与进制转换 进位记数法 任何一个数都可以写成以下算式： N=Di*ri (i=-k,-k+1,.,m-1)N 代表一个数值r 是这个数制的基(Radix)。r=2,

4、8,10,16,i表示这些符号排列的位号Di是位号为i的位上的一个符号ri是位号为i的位上的一个 1 代表的值Di*ri是第i位的所代表的实际值表示m+k位的值求累加和计算机中常用的数制常用数制基数r基本符号第i位的权值二进制20,12i八进制80,1,2,3,4,5,6,78i十六进制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F16i十进制100,1,2,3,4,5,6,7,8,910i十-八-十六进制数据的二进制编码十进制数八进制数十六进制数十进制数八进制数十六进制数0000000081000100100019100120100010A101030110011B101

5、141000100C110051010101D110161100110E111071110111F1111 例(101)2 =(5) 8 =(5)16(101101011)2=(101 101 011) 2 =(5 5 3) 8(101101011)2=(1 0110 1011) 2 =(1 6 B) 16十进制数 二十进制编码(BCD码)表示法是指用四位二进制数字来表示一位十进制数字。 多位十进制数字表示为这种编码的数串。 由于24=16个状态，而二进制只要10个状态，因此需要舍去其中6种状态。 根据舍去状态的不同(有多种方案)，BCD码分为有权码和无权码。有权码无权码十进十进制数制数842

6、1码码2421码码5211码码4311码码00000000000000000100010001000100012001000100011001130011001101010100401000100011110005010110111000011160110110010101011701111101110011008100011101110111091001111111111111十进十进制数制数余余3码码格雷码格雷码（1）格雷码格雷码（2）000110000000010100000101002010100110110301100010001040111011010105100011101011

7、6100110100011710101000000181011110010019110001001000 例如十进制数6578用8421码表示。65780110 0101 0111 1000hexbinary36353738ASCII(hex)符号数据的表示形式 键盘上可以输入的符号： 大小写英文字母：52个 数字09：10个 专用符号 控制符号 ASCII和EBCDLC码(略)每个字符在内存中占用一个字节。ASCII字符编码集字符编码集 b6 b5 b4 000 001 010 011 100 101 110 111 b3 b2 b1 b0 0000 NUL DLE SP 0 P , p 0

8、001 SOH DC1 ! 1 A Q a q 0010 STX DC2 “ 2 B R b r 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ETB 7 G W g w 1000 BS CAN ( 8 H X h x 1001 HT EM ) 9 I Y i y 1010 LF SUB * : J Z j z 1011 VT ESC + ; K k 1100 FF FS , N n 1111 SI US / ? O

9、 _ o 符号数据(字符、汉字)的显示 字符、汉字等只能以图形的方式显示给人看。一般以点阵的形式显示。如：16*16的汉字点阵8*8的点阵汉字的输入、存储 汉字存储必须遵守国家标准。 英文符号采用ASCII码，1Byte。 常用的汉字有6000多个，故需要2B来存储。为了区分汉字和英文符号，所以在机器中，描述汉字时每个字节的最高位为1。因此汉字编码有机内码和机外码之分。 机外码常用的有国标码 GB2312。 机内码与国标码的关系 机内码国标码8080H 例如国标码(十六进制)二进制机内码机内码(十六进制)3B7A0011 1011 0111 10101011 10111111 1010BBFA

10、 输入码 键盘输入。拼音、五笔字型等 语音输入。 手写输入。 扫描输入。图形数据表示形式 图形可分为 规则图形，如直线，圆、圆弧等。 不规则图形，如照片、地图等。 可以用点阵表示任何图形，但需要较多的空间。 对于规则图形，可以存储有关的特征和规则即可。 直线,可以存储起点、终点和线条的类型即可。2.1.3 数据格式的相互转换 通过键盘向计算机输入的数字肯定是用ASCII码形式表示的十进制数，必须通过软件将其转换成二进制数。反之，计算机的运行结果输出时，常常需要通过软件转换成十进制数。 由于二进制数冗长，读写不方便等缺点，常使用八进制或十六进制来进行书写等。 需要在不同进制数之间转换。十进制转二

11、进制整数部分除2取余 小数部分乘2取整2 1 1222521011010.625 * 210.25 * 200.5 * 21 0.0 除尽为止 求得位数满足要求为止低低高高高高低低(11)10=(1011)2 (0.625)10=(0.101)2(11.625)10=(1011.101)2二进制转十进制 从二进制数求其十进制的值，逐位码权累加求和。 (1011.101)2=1*23+0*22+1*21+1*20+ 1*2-1+0*2-2+1*2-3 =8+0+2+1+0.5+0.0+0.125 =11.625二到八或十六进制转换二到八 从小数点向左右三位一分组（10 011 100 . 01)

12、2 = ( 234 . 2 )8 010 二到十六 从小数点向左右四位一分组（1001 1100 . 01)2 = ( 9C . 4 )16 0100 说明：整数部分不足位数对转换无影响， 小数部分不足位数要补零凑足,否则出错。八或十六到二进制转换 (107.6)8=(001 000 111.110)2 (1E7.6)16=(0001 1110 0111.1100)2下列表格内容请记下来i2ii2i01664127128248256389512416101024532161024*642.2机器数的编码格式 机器数是指数据在计算机内部的二进制编码形式（有多种）。 真值是指原来书写形式表示的数(

13、实际值)。 选择机器数的原则 只照顾机器(运算方便、节省存储空间)，不照顾人(是否便于理解) 。 按小数点位置是否固定，机器数分为定点数和浮点数(实数) 。 为了有效、方便地表示正负数，定点数表示又分为原码、反码、补码、移码等编码方案。2.2.1 二进制定点数的原码表示 二进制数据编码方法应达到目标：如何能方便地表示正数、零和负数，尽可能地有利于简化对它们实现算术运算用到的规则。1、符号表示数的符号只有“+”和“-”，每一位二进制信息只有“0”和“1”。可以用“0”表示“+”，“1”表示“-” 。由于符号是放在最左边，所以存放数据的单元中的最高位用于表示该数据的符号。 例如：N1=+0.101

14、1 N2=-0.1101 则它们在机器中可以表示为：N1 0.1011N2 1.1101符号数值部分2、运算中符号处理 运算中存在的问题：是否与数值一起参与运算，结果给下一次运算带来什么影响等。 将符号位与数值位一起编码的方法分为原码、补码、反码、移码等。 原码表示法中机器数分为符号和数值两部分。符号用“0”表示该数为正，“1”表示该数为负。数值部分为真值的绝对值。符号数值部分的绝对值 例如 X=+0.1011,Y=-0.1101,求X原,Y原。 解 根据定义得： X原=0.1011Y原=1.11013、原码表示 用公式表示：对于小数X，其原码表示定义为：X 1X=0X原=1-X 0=X-1

15、性质1 真值0的原码表示。 +0原=0.0000 -0原=1.0000 从上可知，0的原码表示形式不是唯一的。 性质2 若X原=X0.X1X2X3Xn，X0表示原码机器数的符号位，它满足： 0 X=0 X0= 1 X=X=0 X原= 2n-X 0=X-2n 优点：简单，直观，易懂。 缺点：做加减法时，需要将符号位和数值部分分开处理。 原码表示进行加减运算的各种情况。要求操作第一操作数符 第二操作数符 实际操作加法+ +- - - -+ +- -+减法+-+ +- -+ +- -+ + +-2.2.2 二进制定点数的补码表示 从上表可以看出由于负数的原码表示，在两操作数符号相异时，应作加运算实际

16、上改为减运算；本应作减运算实际上改为加运算。 倘若能找到一种机器数的表示法，对它所表示的正负数，要求做加法就作加法，且结果为正确的机器数表示；对于做减法，减去一个负数等于加上与这个负数值对应的正数，减去一个正数，等于加上与这个正数值相等的负数。 好处：减法也能转变为加法。符号位与数值部分一起参与运算简化了运算规则 先看两个十进制数的运算： 79-38=41 79+62=141 如果使用两位十进制数的运算器（如算盘），多余的100因为超出了运算器的位数和范围而自动丢掉，结果为41。 在数学上可以用同余式表示： 79+(-38)=79+62=41 (mod 100) 进一步定义为： -38=62

17、(mod 100) 称-38的补码(对模100而言)是62。 结论：负数用补码表示时，可以把减法转化为加法。 在计算机中，机器能表示的数据位数是固定的，其运算都是有模的运算。位数模数整数n2n小数n2 若运算结果超出了能表示的数值范围，则只保留它的低n位，超过n位的高位部分就自动舍弃了(类似于向一个杯子倒水)。 补码定义： 对于n位小数，其补码定义为 X 1X=0 X补= (mod 2) 2+X 0=X-1 对于n位整数，其补码定义为 X 2nX=0 X补= (mod 2n+1) 2n+1+X 0=X-2n原码与补码之间的转换方法 1、根据定义进行计算原码真值补码 2、原码直接求补码规则对于正

18、数，原码与补码相等；对于负数，转换规则为：符号位不变，数值部分求反加1(在最低位)。 补码直接求原码的规则同上。例 X原=0.1011，Y原=1.1101，求X补=？ Y补=？解：X补=0.1011， Y补=1.0010+0.0001=1.0011 由X补求机器负数-X补规则：连同符号位一起求反加1(在最低位）例 X补=0.1011，Y补=1.1101，求-X补=？ -Y补=？解：-X补=1.0101， -Y补=0.0010+0.0001=0.0011补码加法运算 可以证明，在无溢出的情况下， X补+Y补=X+Y补(mod 2) 称-X补为X补的机器负数。 X-Y补=X+(-Y) 补 =X补+

19、-Y补 =X补-Y补(mod 2) 即将减法变成加法运算。下面再讨论一些性质 (1)0的补码表示是唯一的 +0补=0.000 -0补=10.00+(-0)=0.000 (mod 2) (2)由性质(1)知 X-X补=X补+-X补=0 所以 -X补= -X补即负号在括号内外是一样的。 X-Y补= =X补+-Y补 (mod 2) (3)设X补=X0.X1X2Xn，求X。若 1X=0 则 1X补=X=0 , X0=0； 0=X=-1 则 2=X补=2+X=1 ,X0=1； 所以 0 1X=0 X补=2X0+X 其中 X0= 1 0=X-1X=XX=X补补-2X-2X0 0=X=X0 0.X.X1 1

20、X X2 2X Xn n-2X-2X0 0 =0.X =0.X1 1X X2 2X Xn n-X-X0 0补码的算术移位操作 十进制的算术移位设 X=00.X1X2Xn，对 X 执行乘以10的运算 10*X=0X1.X2Xn0 相当于左移1位对 X 执行除以10的运算 X/10=00.0X1X2Xn 相当于右移1位 二进制真值的算术移位设 X=00.X1X2Xn，对 X 执行乘以2的运算 2*X=0X1.X2Xn0 相当于左移1位对 X 执行除以2的运算 X/2=00.0X1X2Xn 相当于右移1位 (4)由X补，求X/2补(即算术右移,要保持真值不变) 由性质(3)知 X=0.X1X2Xn-

21、X0 所以 X/2=0.X1X2Xn/2-X0/2 =0.0X1X2Xn+X0/2-X0 =0.X0X1X2Xn-X0 比较性质3中的X和性质4中的X/2可得 X/2补=X0.X0X1X2Xn 由X补求X/2补的规则： 符号位不变，连同符号位一起右移一位。 算术左移1位的操作规则 符号位参与向左移位 左移时最高位丢失，最低位补0 左移时可能发生“溢出”现象，判断“溢出”的规则与补码加减法判断“溢出”相同补码的演变 模2补码的修改 对于上述补码，其真值范围为 1X-1，实际上可扩充到 X=-1(为什么?) 因 -1补=2+(-1)=1.000 这样补码定义可修改为： X 1X0 X补= (mod

22、 2) 2+X 0X-1 模4补码变形补码 由于参与运算的数X满足 1X-1，所以两数相加减时其结果有可能超出模2补码表示的真值范围。因此提出了模4补码，其定义如下： X 2X0 X补= (mod 4) 4+X 0X-2 可以证明:若X补=X00X01.X1X2Xn则 X00正好是表示其真值的符号，即X00=0，表示正数，X00=1，表示负数。 模2补码的性质及码制之间转换均可用于模4补码。 模4补码的真值范围是模2补码的一倍。 假若仍表示1X-1的真值（下一个参加运算的数要求），小数点左边就一定相同，所以说模4补码是有两个符号位的补码称为变形补码。 注意：在计算机中存储和传送数据时用一位符号

23、位，而在运算时数据采用两位符号位表示。 利用双符号位判断定点数溢出结果范围双符号是否溢出 2X101正溢出1X000无溢出0X-111无溢出-1X-210负溢出2.2.3 二进制定点数的反码表示 在补码表示法中已经提到补码可以通过原码除符号位外“求反加1”得到。如果只求反不加1，就得到了反码表示法。 对于小数X，其反码定义为 X 1X0 X反= (mod 2-2-n) 2-2-n+X 0X-1 其中 n代表小数的位数。 性质 0的反码表示 +0反=0.000 -0反=2-2-n+(-0)=1.111 即在反码表示中，“0”的表示不唯一。 对于 n位整数X，其反码定义为 X 2nX0 X反= (

24、mod 2n-1) 2n+1-1+X 0X-2n8位二进制代码与真值、原码、补码、反码的对应关系二进制代码无符号数对应的真值原码对应的真值补码对应的真值反码对应的真值0000000000000000000111110111111127-127-127-127-11000000027-0-27-(27-1)1000000127+1-1-(27-1)-(27-2)1111111028-2-(27-2)-2-11111111128-1-(27-1)-1-0真值、原码、补码、反码的对应关系二进制代码(真值)原码补码反码+0000000000000000000000000000000+000000100

25、0000010000000100000001+1111111011111110111111101111111-0000000100000000000000011111111-0000001100000011111111111111110-11111101111111010000010100000001-11111111111111110000001100000000-10000000Not10000000Not真值、原码、补码、反码关系 1、三种机器数的最高位为符号位，符号位和数值部分之间约定用“.”或“，”分隔。 2、原码补码、反码转换规则对于正数，原码、补码、反码相等；对于负数，转换规则为

26、：符号位不变，数值部分求反，补码在最低位还加1。 3、补码、反码的符号位参与运算。 4、原码和反码对0的表示不唯一。 5、对于一个整数的表示，用多少位二进制与所用的模数有关。 25都可以证明。定点数(整数与小数)表示 按小数点的位置分： 定点小数 定点整数 按数有无符号分： 带符号的 不带符号的数 定点小数： 无符号小数: 有符号小数:dn-1.d2d1d0最高有效位小数点dn-1.d2d1d0最高有效位小数点 定点整数：dN-1.d2d1d0最高有效位小数点 进行算术操作时，应使用带符号的数；数据可用原码、补码或反码表示。 表示逻辑量或某些特征值时，应用不带符号的数。dN-1.d2d1d0最

27、高有效位小数点 注意：1、小数点在机器中是无法表示的，是人们在编程时的一种约定。2、对于计算机来说，符号位与其它位没有什么区别，这也只是人们的一种约定。 定点数的长度(位数)分为固定长数据表示。一般取机器字长，参与运算的操作数长度也是固定的，一般称作定长运算或定长操作。多种定长数据表示。对每种字长的存储和单独运算仍然是定长的。如X86系列机，定长数据有：8位，16位，32位，64位。下面再讲述几个问题 1、数据表示的范围-以8位为例十进制数范围二进制形式maxminmaxmin无符号整数28-101111111100000000有符号整数原码27-1-(27-1)011111111111111

28、1有符号整数补码27-1-270111111110000000无符号小数1-2-801111111100000000有符号小数原码1-2-7-(1-2-7)0111111111111111有符号小数补码1-2-7-10111111110000000 2、在按字节编址的机器中，16位、32位、64位字长的地址如何确定。 以16位字长为例高字节低字节字节地址a地址a+1偶数(硬件规定)2.2.4 2.2.4 十进制数的编码十进制数的编码 原因商业统计等领域，运算简单，数据量大。在输入/输出中十进制数二进制数转换所占的时间比例很大。为提高机器的效率，最好能直接对十进制数进行运算和处理。扩大数据的表示

29、范围和提高运算精度。 十进制数串有两种表示形式。 一、字符串形式 指一个字节存放一个十进制的数位或符号位的ASCII码。 在主存中，一个十进制数串占用连续多个字节，故需要给出该数串在主存中的起始位置和位数(串的长度)。 一个十进制数可表示为： 无符号十进制数、有符号十进制数 有符号十进制数是让符号位占用单独一个字节，并把符号位放在数字位之前。 缺点：高四位的值在进行算术运算时不具有数值意义。 主要用在非数值计算的应用领域中。 例如 +543表示如下左图。 例如 -96865可表示 (4个字节/主存单元)如上右图。33H34H35H2BH图35H36H38H36H39H30H30H2DH图符号

30、ACSII码+ +2BH- -2DH 二、压缩十进制数据串形式一个字节存放两个十进制数位每位值可用二十编码(BCD码)表示符号位占用半个字节 如8421码，用12(CH)表示正号，用13(DH)表示负号。 优点：节省存储空间，可直接完成十进制数的算术运算。 例如-78表示如下图。 问题：1、十进制数串如何变成BCD码?2、BCD码如何变成二进制数据?7 8D 0图字节字节 在这种表示中，规定数据位数加符号位数必须为偶数，当不为偶数时，应补一个0。7 80 D图字节字节2.3 检错/纠错码 提高计算机的可靠性办法：采取选用更高可靠性的器件更好的生产工艺等措施采用检错纠错编码技术 采用一点冗余的线

31、路，在原有数据位之外再增加一到几位校验位，使新得到的码字带上某种特性，之后则通过检查该码字是否仍保持有这一特性，来发现是否出现了错误(检错码)，甚至于定位错误后，自动改正这一错误(纠错码)。非线性码线性码卷积码分组码非循环码循环码循环码 随机 错误 突发 错误纠错码校验位与信息位 的形成关系信息位与校验位的约束条件码字本身的 结构特点信息位与校验位排列位置关系系统码非系统码纠错码分类几种常用的检错纠错码三种常用的检错纠错码：奇偶检错码， 用于并行数据传送中海明检错与纠错码， 用于并行数据传送中循环冗余码， 用于串行数据传送中编码过程译码过程传送原始数据码 字结果数据形成校验位的值，加进特征检查

32、接送的码字，发现 / 改正错误2.3.1 奇偶校验码用于并行码检错原理：在 k 位数据码之外增加 1 位校验位，使 K+1 位码字中取值为 1 的位数总保持为 偶数（偶校验）或 奇数（奇校验）。例如：0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 原有数字位 两个新的码字 偶校验偶校验奇校验奇校验校验位数据编码、传送及检错过程数据编码、传送及检错过程： 设原始数据为d6 d5 d4 d3 d2 d1 d0 ，增加1个偶校验位d7，构成8位偶校验编码。d7 = d6 d5 d4 d3 d2 d1 d0 式中 为异或运算。 发送方把8

33、位的偶校验码d7d6 d5 d4 d3 d2 d1 d0 发送出去。 接收方收到8位偶校验码d7d6 d5 d4 d3 d2 d1 d0 。 校验电路用来检查8位数据中取值1的个数是否为偶数。若是，则没有出错，否则，出现了错误。 check= d7 d6 d5 d4 d3 d2 d1 d0奇偶校验码的实现电路+ 奇校验 偶校验 出错指示(check)+同左侧电路编码电路译码电路D7 (校验位)八位数据位0 D6 D5 D4 D3 D2 D1 D0p 奇偶校验又分为 垂直校验 水平校验 水平垂直校验1、垂直(纵向)奇偶校验 以七单位码数字0-9为例说明垂直奇偶校验码(表2-1)表2-1七单位数字

34、的垂直奇偶校验码(偶校验）0123456789B70000000000B61111111111B51111111111B40000000011B30000111100B20011001100B10101010101校验0110100110 2、水平(横向)奇偶校验 对一组信息内各字符的同一位进行奇偶校验时，称为水平奇偶校验。 仍以七单位码为例并用表2-2来说明。 传送时是按列传送字符。表2-2水平奇偶校验（偶校验）0123456789校验B700000000000B611111111110B511111111110B400000000110B300001111000B200110011000B

35、1010101010113、水平垂直奇偶校验 同时进行水平和垂直奇偶校验的方式称为水平垂直奇偶校验。 仍以七单位码为例来说明，如表2-3。0123456789校验B700000000000B611111111110B511111111110B400000000110B300001111000B200110011000B101010101011校验01101001101表2-3水平垂直奇偶校验 水平校验码和垂直校验码只能发现奇数个错，不能发现偶数个错。 水平垂直校验码具有较强的检错能力，它不但能发现所有一位、二位和三位错误，而且能改正一位错误。2.4.2 海明校验码海明校验码 定义1 对2个二进

36、制代码中的每一位进行比较，取值不同的位数称为这2个二进制代码的海明距离。 定义2 最小码距=Min(Xi和Yi之间的海明距离)，其中Xi和Yi( i != j)是某编码系统中任意2个合法代码。 例1 用4位二进制代码表示一个十六进制，由于没有任何剩余状态未被使用，因而最小 码距为1。 例2 给例1的编码增加1个奇校验位，变成5位二进制代码表示一个十六进制数，此时，任何一个合法码在某一位上取值的变化，都会变成非法代码。于是码距=2。 海明校验码的原理 在数据中加入几个校验位，将数据代码的码距较均匀地拉大; 把数据的每一个二进制位分配在几个奇偶校验组中。 当某一位出错后，就会引起有关几个校验位的值

37、发生变化，这不但可以发现错误，还能指出是哪一位出错。 在此介绍纠正一位错误的编码。 r=? 校验位的状态应当有m+1种(含无错)，以便能指出m位中的任何一位有错或无错。所以增添的奇偶校验位数r应满足： 2rm+1=k+r+1 海明校验码构成K位信息r位校验码m位 不同位数的数据编成海明码所需的最小校验位数，如表2-4。表2-4 不同位数的数据所需海明码的最小校验位数kr 133410411255265665119 7 注：书上P430页表为再加上一位校验位，对整个海明码进行校验。 若海明码的最高位号为m，最低位号为1。 海明码的编码规则： (1)、校验位位数与数据位位数之和为m，每个校验位i在

38、海明码中被分在位号2i-1的位置，其余各位为数据位，从低位向高位依次排列。HmHm-1H2H1位号 (2)、海明码的每一位Hi(包括数据位和校验位本身)由多个校验位校验，其关系: 被校验的每一位位号2i-1 (i=1) (3)、在增大合法码的码距时，使所有码的码距尽量均匀地增大，以保证对所有码的检错能力平衡提高。 由编码规则(2)，得出如表2-5。 也可以下面公式获得 Pi= Hi|j&i=iH13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P1 例如对一个字节进行海明编码。 每个字节由8个二进制位组成(k=8)，根据表2-4可

39、知 r=4，再加上一位对整个信息的校验位，故海明码的位数为13，表示： 表2-5海明码位号与校验位的位号关系海明码位号数据位/校验位参与校验的校验位位号海明码位号=位号之和H1P111=1H2P222=2H3D11,23=1+2H4P344=4H5D21,45=1+4H6D32,46=2+4HD41,2,47=1+2+4H8P488=8H9D51,89=1+8H10D62,810=2+8H11D71,2,811=1+2+8H12D84,812=4+8H13 P51313=13 从表2-5求出Pi值的偶校验的结果： P1=D1 D2 D4 D5 D7 P2 =D1 D3 D4 D6 D7 P3

40、=D2 D3 D4 D8 P4 =D5 D6 D7 D8 P5=D1 D2 D3 D4 D5 D6 D7 D8 P1 P2 P3 P4 例如对字符C(8位)进行海明校验，其海明码如下: 从上述公式可知 P1=1 1 0 0 1=1 P2 =1 0 0 0 1 =0 P3 =1 0 0 0 =1 P4 =0 0 1 0 =1 P5=0 海明码为：0 0100 1 001 1 1 0 1H13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P1P50100P4001P31P2P1 设其中一位出错，如第八位接收到的编码为： 校验结果： S1=P1

41、 D1 D2 D4 D5 D7=0 S2 =P2 D1 D3 D4 D6 D7=0 S3 =P3 D2 D3 D4 D8=0 S4 =P4 D5 D6 D7 D8=1 S5=1H13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P10010000011101由于S4-S1不为00000，所以有错，错误位在S4-S1=01000处。2.3.3 循环冗余校验码循环冗余校验码(CRC码码) 循环冗余校验码主要用于传输纯二进制比特流信息的情况。 循环冗余校验码(n位)由信息位(k位)加上校验位(r位)构成。即k位信息位r位校验位 应用CRC码的关

42、键是如何从k位信息得到r位校验位，以及如何从k+r位信息码判断是否出错。k+r位1、模2四则运算 模2运算是指按位模2相加为基础的四则运算，运算时不考虑进位和借位。 (1) 模2加减法0+0=00+1=11+0=11+1=00-0=0 0-1=1 1-0=1 1-1=0 结论：减去一个数等于加上该数。 (2) 模2乘法按模2加求部分积。例1011 110 0000 1011 1011 111010 (3) 模2除法按模2减求余数。例 101 | 10110000 101 010 000 100 101 01余数2、CRC码编码方法 设待编码的信息为Ck-1Ck-2C1C0。 将待编码的k位有效信息位组表示为多项式m(x)； M(x)=Ck-1xk-1+Ck-2xk-2+C1x+C0 由于CRC码是由信息位(k位)加上校验位(r位)构成，故相当于将M