CRC的译码与纠错

2011-07-03 16:48:54来源: 互联网
CRC的译码纠错

  将收到的循环校验码用约定的生成多项式G(x)去除,如果码字无误则余数应为0,如有某一位出错,则余数不为0,且不同数位出错余数会不同。我们通过上例求出其出错模式,如表2-4所示。更换不同的待测码字可以证明:余数与出错位的对应关系是不变的,只与码制和生成多项式有关。因此表2.4给出的关系可作为系统线性(7,4)分组码的出错判别依据。对于其他码制或选用其他生成多项式,出错模式将发生变化。

表2.4 (7,4)循环码的出错模式 ( 生成多项式G(x)=1011 )

A1 A2 A3 A4 A5 A6 A7
余数
出错位
正确
错误
1   1  0  0  0  0  0
1   1  0  0  1  1  0
1   1  0  1  0  1  0
1   1  1  0  0  1  0
1   0  0  0  0  1  0
0   1  0  0  0  1  0
0 1 0
1 0 0
0 1 1
1 1 0
1 1 1
1 0 1
6
5
4
3
2
1

  如果循环码有一位出错,用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去,我们将发现一个有趣的结果:各次余数将按表2.4中的内容顺序循环。例如第七位出错,余数将为001,补0后再除,第二次余数为010,以后依次为100,011,…,反复循环。这是一个有价值的特点。如果我们在求出余数不为0之后,一边对余数补0继续做模2除,同时让被检测的校验码字循环左移。表2.4说明,当出现余数(101)时,出错位也移到A1位置。可通过异或门将它纠正后在下一次移位时送回A7。继续移满一个循环(对7,4码共移七次),就得到一个纠正后的码字。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当数据位数增多时,循环码校验能有效地降低硬件代价,这是它得以广泛应用的主要原因。

  关于生成多项式,并不是任何一个r次的多项式都可以作为生成多项式。从检错及纠错的要求出发,生成多项式应能满足下列要求:
  (1) 任何一位发生错误应当使余数不为0;
  (2) 不同位发生错误应当使余数不同;
  (3) 对余数继续作模2除,应使余数循环。

  将这些要求反映为数学关系是比较复杂的,对一个(n,k)码来说,可将(xn -1)分解为若干质因子式(注意是模2运算),根据编码所要求的码距,选取合适的r值,选其中的一个因式或若干因式的乘积作为生成多项式,为r次多项式,且最高、最低位系数均为1。

  例: x7-1=( x+1)(x3+x+1)(x3+x2+1) (模2运算)
  选择 G(x)= x+1 = 11,可构成(7,6)码,只能判一位错。
  选择 G(x)= x3+x+1=1011,或 x3+x2+1=1101,可构成(7,4)码,能判两位错或纠一位错。
  选择 G(x)=(x+1)(x3+x+1)=11101,可构成(7,3)码,能判两位错并同时纠正一位错。

  对使用者来说,可从有关资料上查到对应于不同码制的生成多项式,表2.5仅给出了一部分。

表2.5 生成多项式

N
K
码距d
G(x)多项式
G(x)二进制码
3+x+1)或 (x3+x2+1)G(x)=G1(x)(x+1)=(x3+x+1)(x+1)或 (x3+x2+1)(x+1)
1101
4+x+1)(x4+x+1)(x4+x3+x2+x+1)
10111
7
5
5+x2+1)(x5+x2+1)(x5+x4+x3+x2+1)
111010001
  26
  21
5
4+x+1)(x4+x+1)(x6+x4+x+1)
11101101001
51
5
16+x15+x2+1)
1010000110101

关键字:译码  纠错

编辑:神话 引用地址:http://www.eeworld.com.cn/mndz/2011/0703/article_10439.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
译码
纠错

小广播

独家专题更多

富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
带你走进LED王国——Microchip LED应用专题
带你走进LED王国——Microchip LED应用专题
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved