第二章数据的表示3.ppt

第二章 数据的表示 2.1数据、信息和媒体 2.2数字化信息编码 2.3数值数据的编码表示 2.4非数值数据的编码表示 2.5二进制信息的计量单位 2.6数据校验码 2.6数据校验码 数据校验的方法大多采用“冗余校验”的思想，即除原数据信息外，还增加若干位编码，这些新增的代码称为校验位。 为了判断一种码制的冗余程度，并估价查错和纠错能力，引入码距的概念。 由若干位代码组成的一个字称为码字，将2个码字逐位比较，具有不同代码的位的个数叫做这2个码字的距离。各码字间的最小距离称为码距。 2.6数据校验码 数据校验码中，一个码字是指数据位与校验位按照某种规律排列得到的代码。 码距和检错、纠错能力的关系为： 如果码距d为奇数，则发现d-1位错，或者能纠正(d-1)/2位错 如果码距d为偶数，则能发现d/2位错，并能纠正（d/2）-1位错。 常用的数据校验码有奇偶校验码、海明校验码、和循环冗余校验码 2.6.1奇偶校验码 奇偶校验码的基本思想是通过在原数据信息中增加一位（奇/偶校验位），使整个码字中1的个数为奇数个（奇校验）或偶数个（偶校验）。将原数据和校验位一起存储、传送，在终部件得到的相应码字再进行一次编码，求出新的校验位，根据新校验位确定是否发生了错误。 2.6.1奇偶校验实现过程 设数据为B=bn-1bn-2…b0，在终部件接收到的数据为B’= bn-1’bn-2’…b0’。在源部件处得到的校验位是P，在终部件处得到的校验位是P’。最终校验位是P* 第一步：在源部件求出校验位P P= bn-1 ⊕ bn-2 ⊕ … ⊕ b0 ⊕1 (奇校验） P= bn-1 ⊕ bn-2 ⊕ … ⊕ b0 (偶校验） 第二步：在终部件求出校验位P’ P’= bn-1 ’⊕ bn-2 ’ ⊕ … ⊕ b0 ’ ⊕1 (奇校验） P= bn-1 ’ ⊕ bn-2 ’ ⊕ … ⊕ b0 ’ (偶校验) 2.6.1奇偶校验实现过程 第三步：判断有无奇偶错 P*=P⊕P’ P*=1,有奇数位错 P*=0,无错或有偶数位错。 奇偶校验码中，若2个数据有奇数位不同，则他们相应的校验位就不同，若偶数位不同，则校验位相同，但至少2位数据位不同，因而2个码字之间至少有2位不同，码距d=2,因而只能发现奇数位错，不能发现偶数位错，而且不能确定出错的位置，因此不具有纠错能力。 [例2.47]奇偶校验码:产生校验位（演 示2-27.swf） 要从源部件发送数终部件。请写出采用奇校验法的过程 [例2.48]奇偶校验码：产生校验位（演示2-28.swf） 要从源部件发送数终部件。请写出采用偶校验法的过程 [例2.49]奇偶校验码：校验过程无错情况（演示2-29.swf） 在终部件处，根据接收到的码字判断数据是否出错。约定采用奇校验法 [例2.50]奇偶校验码：校验过程（演示2-30.swf） 在终部件处，根据接收到的码字判断数据是否出错。约定采用偶校验法 3种情况（无错、奇数位错、偶数位错） 2.6.2海明校验码 将数据按某种规律分成若干组，对每组进行奇偶检测，就能提供多位检错信息，从而对错误位置进行定位，并纠正。海明校验码实质上是一种多重奇偶校验码。 海明校验码最终的比较结果称为故障字，故障字和校验码位数相同。 2.6.2海明校验码校验位数确定 假定数据位数为n，校验位为k，则故障字位数为k，k位故障字能表示的状态最多为2k，每种状态用来表示一种出错的情况，对于最多一位错的情况，结果有无错、数据中一位错、校验位中一位错，共为n+k+1种情况。所以，要对所有结果进行正确表示， 2k≥1+n+k 2.6.2海明校验码分组方式确定 数据位和校验位的排列为n+k的码字，将每一位的出错位置与故障字的数值建立关系，就可以通过故障字的值确定码字中出错的位置，就可以取反纠正了。 一般分组原则： 如果故障字各位全为0，则表示没有错误 如果故障字中有且只有一个1，则表示校验位中有一位错，不需纠正 如果故障字中有多于1位的1，则表示有一个数据位错，出错位置由故障字数值确定，将出错位取反纠正 [例2.51]故障字和分组方式 8位数据位，M=M8M7M6M5M4M3M2M1 校验位为2k≥1+8+k,k=4。P=P4P3P2P1 故障字为0000~1111的16种组合 无错：0000 校验位错：0001，0010，0100，1000 数据位错：取剩余的８个组合 为了根据故障字代码得到出错位置，最好和位号一致 [例2.52]故障字和分组方式8位数据位，4位校验位（演示2-31.swf） 故障字和出错情况分配 2.6.2海明校验码的校验位生成 在上面的分组