4--3---校验码.ppt

*;*;*;*;*; 海明校验码 这是由Richard Hamming于1950年提出的、目前还被广泛采用。它的实现原理，是在数据中加入几个校验位，并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验组的值发生变化，这不但可以发现出错，还能指出是哪一位出错，为自动纠错提供了依据。 ; 海明校验码 假设校验位的个数为r，则它能表示2r个信息，用其中的一个信息指出“没有错误”，其余的2r-1个信息指出错误发生在哪一位。然而错误也可能发生在校验位，因此只有k=2r-1-r个信息能用于纠正被传送数据的位数，即信息位有k位，也就是说要满足关系： 2r≥k+r+1 (3.18); 海明码求解具体步骤： 1）确定校验码的位数； 2）确定校验码的位置； 3）确定数据的位置 ； 4）求出校验位的值 。;若海明码的最高位号为m，最低位号为1，即HmHm-1…H2H1，则此海明码的编码规律通常是： 校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。 ;若海明码的最高位号为m，最低位号为1，即HmHm-1…H2H1，则此海明码的编码规律通常是： 校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。 ;若海明码的最高位号为m，最低位号为1，即HmHm-1…H2H1，则此海明码的编码规律通常是： 校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。 ;;表3.8 数据位k与校验位r的对应关系 ;若海明码的最高位号为m，最低位号为1，即HmHm-1…H2H1，则此海明码的编码规律通常是： 校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。 ;(2) 海明码的每一位码Hi(包括数据位和校验位本身)由多个校验位校验，其关系是被校验的每一位位号要等于校验它的各校验位的位号之和。这样安排的目的，是希望校验的结果能正确反映出出错??的位号。 按上述规律讨论一个字节的海明码。 ;每个字节由8个二进制位组成，此处的k为8，按式(3.19)求出校验位的位数r应为5，故海明码的总位数为13，可表示为H13H12H11…H3H2H1 5个校验位P5~P1对应的海明码位号应分别为H13，H8，H4，H2和H1。P5只能放在H13一位上，它已经是海明码的最高位了，其他4位满足Pi的位号等于2i-1的关系。其余为数据位Di，则有如下排列关系：P5D8D7D6D5P4D4D3D2P3D1P2P1 按前面讲的，每个海明码的位号，要等于参与校验它的几个校验位的位号之和的关系，可以给出如表3.9所示的结果。 ;表3.9 出错的海明码位号和校验位位号的关系 ;图3.11是H=12，数据位k=8，校验位r=4的海明校验线路，记作(12，8)分组码。 如前所述，假如要进一步判别是1位错还是2位错，则再增加一个校验位。并用图3.12来取代图3.11虚框中的内容，此时增加了一个奇偶形成线路S5。如为一位错，仍按图3.11来纠正数据位；如为两位错，则无法纠正错误。 ; 图3.11 (12，8)分组码海明校验线路 ; 图3.12 判1位/2位错的附加线路 ;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;纠错原理 由于M(x)·xk=Q(x)·G(x)+R(x)，根据模2加的规则： M(x)·xk+R(x)=M(x)·xk-R(x)=Q(x)·G(x) 所以合法的循环冗余校验码应当能被生成多项式整除。如果循环冗余校验码不能被生成多项式整除，就说明出现了信息查错。并且，有信息差错时，循环冗余校验码被生成多项式整除所得到的余数与出错位有对应关系，因而能确定出错位置。 请看书表1.5为例2.3.1所得到的循环冗余校验码的出错模式。 ; 进一步分析还会发现，循环冗余校验码当有一位出错时，用生成多项式作模2除将得到一个不为0的余数，将余数补0继续作模2除又得到一个不为0的余数，再补0再作模2除……，于是余数形成循环。对上例，形成001,010,100,011,110,111,101；001,010,100,…的余数循环。这也就是“循环码”的来历。 ;*; 生成多项式的选择主要靠经验。有三种多项式已经成为标准，具有极高的检错率。它们是： CRC-12=x12+x11+x3+x2+x+1