|
|
|
计算机系统运行时，在各个部件之间经常需要进行数据交换，为保证数据传送过程的正确无误，必须引入差错检查机制对数据进行校验，以检测是否有数据传送错误。其基本原理是：在编码中引入一定的冗余位，当被传送的编码中出现错误时就使之成为非法代码而被检测出。
|
|
|
|
|
|
奇偶校验码用于并行码的检错。其原理是：在k位数据码之外增加1位校验位，使k+1位码字中取值为1的位数总保持为偶数（偶校验）或奇数（奇校验）。
|
|
|
|
|
|
|
|
|
|
（2）垂直校验：设4个字节的数据为一组进行垂直奇校验。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
（3）垂直水平校验：设4个字节的数据为一组进行垂直水平奇校验。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
实现：为k个数据位设r个校验位，使k+r位的码字（即海明码）能发现k位中任何一位出错且可以纠正。
|
|
|
|
|
|
|
|
|
|
设r个校验位PrPr-1…P1,k个数据位Dk-1Dk-2…D0，产生的海明码为Hr+k,Hr+k-1…H1，则有如下规则。
|
|
|
|
规则1：Pi在海明码的2i-1位置，即Hj=Pi,j=2i-l；数据位则依序从低至高占据海明码中其他的位置。
|
|
|
|
规则2：海明码中的任意位都是由若干校验位来校验的。其对应关系是：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位则是由其自身来校验的。
|
|
|
|
|
|
下面以k=8对纠1位错的海明码的编码及校验原理给予说明。
|
|
|
|
|
|
当r=4时，有24≥8+4+1，可以满足2r≥k+r+1。
|
|
|
|
|
|
|
|
如：确定P4的位置，因j=2i-1=24-1=8，则有P4在H8的位置。同理得到以下位置的对应关系：
|
|
|
|
H12H11H10H9H8H7H6H5H4H3H2H1
|
|
|
|
|
|
|
|
|
|
形成Hi与P1相关的数据位有：S1=D0十D1十D3十D4十D6。
|
|
|
|
形成Hi与P2相关的数据位有：S2=D0十D2十D3十D5十D6。
|
|
|
|
形成Hi与P3相关的数据位有：S3=D1十D2十D3十D7。
|
|
|
|
形成Hi与P4相关的数据位有：D7十D6十D5十D4。
|
|
|
|
|
|
|
|
设G1=S1十P1；G2=S2十P2；G3=S3十P3；G4=S4十P4。若采用偶校验则G4~G1的值全为0时数据正确，反之有错。用对出错位取反的方法即可实现纠错。
|
|
|
|
例如，G4~G1=0111，其值为7，对应于H7（D3的位置）。将D3的值取反就实现了纠错。
|
|
|
|
|
|
利用生成多项式为k个数据位产生r个校验位来进行编码，其编码长度为k+r。CRC的代码格式为：
|
|
|
|
|
|
由此可知循环冗余校验码由两部分组成，左边为信息码，右边为校验码，若信息码占k位，则校验码就占n-k位，所以又称为（n,k）码。
|
|
|
