加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

DataMatrix译码1——纠错

(2012-04-05 18:45:28)
分类: DataMatrix
    设“ABCDE12”通过RS编码后为C(x)={66 67 68 69 70 142 129 56 75 145 55 46 20 95 253 237 62 111},经过信道时发生了失真,接收到的数据为R(x)={66 99 68 69 70 142 129 56 75 145 55 46 20 95 253 237 62 111}。译码的首先需要通过纠错将T(x)还原出来。
    设有RS(n,k),其中包含数据码字k个,冗余码字n-k个,可纠正错误t=(n-k)/2个;在本例中,n=18,k=8,冗余10个,可纠错5位。纠错过程如下:
   
1、生成伴随式{S1, S2, ……, S2t}
   设接收码字http://s10/middle/4572df4ehbcece9aa8ed9&690
   先计算出伴随式http://s15/middle/4572df4ehbcecf3e2b36e&690, i = 1,2,……2t;显然,若接收码字R(x)无任何错误,则Si = 0;反过来,若Si全部=0(i = 1,2,……2t),说明接收码字无错误,即R(x) = C(x)。  
   设E(x)为错误图样http://s8/middle/4572df4eh794aebaf7617&690
   若信道产生了t个错误,则E(x)也可以表示为:
  http://s6/middle/4572df4ehbced785ea8a5&690,表示各个错误位置,Yi为该位置上的错误值。
   由于 R(x) = C(x)+E(x),
  http://s13/middle/4572df4ehbced6a21606c&690,所以
  http://s11/middle/4572df4ehbced7f4b70fa&690http://s3/middle/4572df4ehbced84f23ec2&690,得到方程组①:
        http://s16/middle/4572df4ehbced9ac5cf2f&690

2、求错误位置多项式σ(x)
    目前已知Si,要通过方程组①求得X1~ Xt,需要借助下面的“错误位置多项式”:
  http://s14/middle/4572df4ehbcee9535cd6d&690,其中Xi来自E(x),现在借助方程组①,建立{σ1,σ2 ……,σt}与{S1,S2 ……,St}之间的关系。
  σ(x)=0的根为http://s7/middle/4572df4ehbceecf2b3b06&690,故而可以构建以下方程组:
  http://s6/middle/4572df4ehbceee5be0505&690
  现在开始变换:
  第1步:上述1 ~ t个等式,第i个等式左右分别乘以http://s4/middle/4572df4ehbceef63652b3&690,得:
  http://s2/middle/4572df4ehbcef05fef631&690
  σi系数相加,结合方程组①,可以得到:
 
http://s1/middle/4572df4ehbcef14eaea80&690
 第2步:上述1 ~ t个等式,第i个等式左右分别乘以http://s3/middle/4572df4ehbcef194da6d2&690,同理得:
  http://s5/middle/4572df4ehbcef1f4f1074&690
 第t步:上述1 ~ t个等式,第i个等式左右分别乘以http://s10/middle/4572df4ehbcef24469239&690,同理得:
  http://s16/middle/4572df4ehbcef2ae45e4f&690
  如此得到方程组,得到Si与σi之间的关系(Xi与Yi已经消失了)
  http://s4/middle/4572df4ehbcef2eb3af63&690
  通过解方程组,求出{σ1,σ2 ……,σt}

3、求出错误位置Xi
  由于
http://s5/middle/4572df4ehbcef5adc7924&690,则i即为错误位置。

4、求错误值Yi
  求出Xi后,设得到r个实际有错误的位置(r<=t),分别为http://s13/middle/4572df4ehbced6a21606c&690建立以下方程组:
  http://s5/middle/4572df4ehbd030f56ede4&690
  解方程即可求出http://s5/middle/4572df4ehbd02dba16a44&690逐一把R(x)替换掉即可将C(x)还原出来。


0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有