第二章数据的机器级表示解读.ppt

海明码举例 假定一个8位数据M为：M8M7M6M5M4M3M2M1=根据上述公式求出相应的校验位为： 　　 P4 = M5⊕M6⊕M7⊕M8=0⊕1⊕1⊕0=0 P3 = M2⊕M3⊕M4⊕M8=1⊕0⊕1⊕0=0 　　 P2 = M1⊕M3⊕M4⊕M6⊕M7 =0⊕0⊕1⊕1⊕1=1 　　 P1 = M1⊕M2⊕M4⊕M5⊕M7 =0⊕1⊕1⊕0⊕1=1 　假定12位码字 (M8M7M6M5P4M4M3M2P3M1P2P1) 读出后为： (1) 数据位M’=M校验位P’’=P=0011 (2) 数据位M’=校验位P’’=P=0011 (3) 数据位M’=M校验位P’’= 1011 　要求分别考察每种情况的故障字。 (1) 数据位M’=M校验位P’’=P=0011，即无错。 因为M’=M，所以P’= P， 因此 S = P’’⊕P’=P⊕P=0000。 海明码举例 (2) 数据位M’=校验位P’’=P=0011，即M5错。 对M’生成新的校验位P’为： P4’ = M5’⊕M6’⊕M7’⊕M8’=1⊕1⊕1⊕0=1 P3 ’= M2’⊕M3’⊕M4’⊕M8’=1⊕0⊕1⊕0=0 P2’ = M1’⊕M3’⊕M4’⊕M6’⊕M7’ =0⊕0⊕1⊕1⊕1=1 P1 ’= M1’⊕M2’⊕M4’⊕M5’⊕M7’=0⊕1⊕1⊕1⊕1=0 故障字S为： S4= P4 ’⊕ P4’’=1⊕0=1 S3= P3 ’⊕ P3’’=0⊕0=0 S2= P2 ’⊕ P2’’=1⊕1=0 S1= P1 ’⊕ P1’’= 0⊕1=1 因此，错误位是第9位，排列的是数据位M5，所以检错正确, 纠错时，只要将码字的第9位（M5）取反即可。 海明码举例 (3) 数据位M’=M校验位P’’= 1011， 即：校验码第4位(P4)错。 因为M’=M，所以P’= P，因此故障位S为： S4= P4 ’⊕ P4’’=0⊕1=1 S3= P3 ’⊕ P3’’=0⊕0=0 S2= P2 ’⊕ P2’’=1⊕1=0 S1= P1 ’⊕ P1’’= 1⊕1=0 错误位是第1000位(即第8位)，这位上排列的是校验位P4，所以检错时发现数据正确，不需纠错。 单纠错和双检错码 单纠错码（SEC） 问题：上述(n=8/k=4)海明码的码距是几？ 码距d=3。因为，若有一位出错，则因该位至少要参与两组校验位的生成，因而至少引起两个校验位的不同。两个校验位加一个数据位等于3。 例如，若M1出错，则故障字为0011，即P2和P1两个校验位发生改变，12位码字中有三位（M1、P2和P1）不同。 根据码距与检错、纠错能力的关系，知：这种码制能发现两位错，或对单个位出错进行定位和纠错。这种码称为单纠错码（SEC）。 单纠错和双检错码 单纠错和双检错码（SEC-DED） 具有发现两位错和纠正一位错的能力，称为单纠错和双检错码（SEC-DED）。 若要成为SEC-DED ，则码距需扩大到d= 4。为此，还需增加一位校验位P5，将P5排列在码字的最前面，即：P5M8M7M6M5P4M4M3M2P3M1P2P1，并使得数据中的每一位都参与三个校验位的生成。从表中可看出除了M4和M7外，其余位都只参与了两个校验位的生成。因此P5按下式求值： 　　　 P5= M1⊕M2⊕M3⊕M5⊕M6⊕M8 当任意一个数据位发生错误时，必将引起三个校验位发生变化，所以码距为4。 SKIP 循环冗余码 循环冗余校验码（Cyclic Redundancy Check），简称CRC码 具很强的检错、纠错能力。 用于大批量数据存储和传送(如：外存和通信)中的数据校验。 为什么大批量数据不用奇偶校验？ 在每个字符后增加一位校验位会增加大量的额外开销；尤其在网络通信中，对传输的二进制比特流没有必要再分解成一个个字符，因而无法采用奇偶校验码。 通过某种数学运算来建立数据和校验位之间的约定关系。 奇偶校验码和海明校验码都是以奇偶检测为手段的。 网络或通信课程中会学到。 CRC码的检错方法 基本思想： 数据信息M(x)为一个n位的二进制数据，将M(x)左移k位后，用一个约定的“生成多项式”G(x)相除，G(x)是一个k+1位的二进制数，相除后得到的k位余数就是校验位。校验