考研帮 > 数学 > 每日一练

2.1 制与编码

  校验得到的结果值S5~S1(指误字),它能反映12位海明码的出错情况:
  当S4~S1为0000时,表明无错。
  当S4~S1中仅有一位不为0,表明是1校验位出错或12位海明码(包括信息位和校验位)同时出错。由于后一种出错的可能性很小,故认为是前一种错,出错位是该Si对应的Pi位。
  当S4~S1中有两位不为0,表明是2位海明码同时出错,此时只能发现错误,而无法确定出错的位置。
  当S4~S1中有3位不为0,表明是1位信息位出错或4位校验位同时出错,由于后一种错误的可能性很小,故认为是前一种错。出错位的位号由S4~S1 这4位代码值指明,此时不仅能检查出一位错,而且能准确的定位,因此可以纠正这个错误(将该位变反)。
  当S4~S1中有4位不为0时,表明出错情况严重,系统工作可能出现故障,应检查系统硬件的正确性。
  第2、第4种出错的情况列于表2-4中。若表中仅有一个Si不为0,表示Pi出错,因为是校验位出错,故此时并不需要校正它们。当4个Si位有3个为1时,表示是某一信息位Di出错。出错信息位的海明码位号由S4~S1这4位的译码值指出(分别为12,11,10,9,7,6,5,3)。例如,当S4~S1=0111时,S4~S1的译码值为7,即对应H7(也就是D4)位出错。

表2-4 海明码出错情况表

海 明 码 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
位    号 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
S4
S3
S2
S1
1
1
0
0
1
0
1
1
1
0
1
0
1
0
0
1
1
0
0
0
0
1
1
1
0
1
1
0
0
1
0
1
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1

   3.循环冗余校验码
  循环冗余校验码(Cyclic Redundancy Check,CRC)是一种具有很强的检错、纠错能力的校验码。循环冗余校验码常用于外存储器的数据校验,在计算机通信中也被广泛采用。CRC码可以发现并纠正信息存储或传送过程中连续出现的多位错误,其实现方法主要是:在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位(编码),以及如何从k+r位信息码判断是否出错。
  循环冗余校验码是通过除法运算来建立有效信息位和校验位之间的约定关系的。假设待编码的有效信息以多项式M(X)表示,将它左移若干位后,用另一个约定的多项式G(X)去除,所产生的余数R(X)就是检验位。有效信息和检验位相拼接就构成了CRC码。当整个CRC码被接收后,仍用约定的多项式G(X)去除,若余数为0表明该代码是正确的;若余数不为0表明某一位出错,再进一步由余数值确定出错的位置,以便进行纠正。
  (1)CRC码的编码方法。CRC码是由两部分组成的,如图2-2所示。左边为信息位,右边为校验位。若信息位为N位,校验位为K位,则该校验码被称为(N+K,N)码。

  循环冗余校验码编码规律如下:
  ① 把待编码的N位有效信息表示为多项式M(X);
  ② 把M(X)左移K位,得到M(X)×XK,这样空出了K位,以便拼装K位余数(即校验位);
  ③ 选取一个K+1位的产生多项式G(X),对M(X)×XK做模2除;

  ④ 把左移K位以后的有效信息与余数R(X)做模2加减,拼接为CRC码,此时的CRC码共有N+K位。
  例如,选择的产生多项式为1011,把4位有效信息1100编成CRC码的过程如下。

  M(X)×X 3+R(X)=1100000+010=1100010
  这种CRC码称为(7,4)码。
  (2)CRC码的校验与纠错。把接收到的CRC码用约定的生成多项式G(X)去除,如果正确,则余数为0;如果某一位出错,则余数不为0。不同的位数出错其余数不同,余数和出错位序号之间有唯一的对应关系。如表2-5所示列出了(7,4)码的出错模式。
  如果某一位出错,则余数不为0,对此余数补0后,当做被除数再继续除下去,余数将按表2-5的顺序循环。例如:第七位(A7)出错,余数为001,把其补0后再除以G(X),第二次余数为010,以后依次分别为100,011,110,111,101,然后又回到001,反复循环,这就是“循环码”一词的来源。根据CRC码的特征,一边对余数补0继续做模2除法,同时让被检测的校验码循环左移。当余数为101时,原来出错的A7位已移到A1的位置,通过异或将其求反纠正,在下一次循环左移时送回A7。所以,移满一个循环(7次),就得到一个纠正的码字。

表2-5 (7,4)码的出错模式(G(X)=1011)

  A1 A2 A3 A4 A5 A6 A7 余数 出错位
正确码 1 1 0 0 0 1 0 000
错误码 1
1
1
1
1
1
0
1
1
1
1
1
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
0
0
0
0
0
001
010
100
011
110
111
101
7
6
5
4
3
2
1

 

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭