通信人家园

 找回密码
 注册
搜索
热搜: 家园 活动
查看: 944|回复: 0

[原理资料] 通信中的校验纠错 [复制链接]

军衔等级:

  新兵

注册时间:
2016-12-22
发表于 2018-4-2 15:45:38 |显示全部楼层
CRC
CRC校验码位数  =  生成多项式 G(x) 位数 – 1  =  R
假设使用的生成多项式为G(x) = X3 + X + 1转换成对应的二进制除数为1011   R=4-1=3
原码为1010
第一步:将原码左移三位得到1010_000
第二步:项式(1011)对信息码(1010)做模2除法【实现:1010_0001011高位对齐做异或运算得到0001000左移一位之后,高位为0则除以0000,得到001000,左移一位之后,高位为0则除以0000,得到01000,。。。。。得到1000,高位为1则除以1011,得到0011】得到R位余位011
第三步:得到最终编码1010_011
汉明
汉明(74)码中,全部码长是7位:C7C6C5C4C3C2C1,其中4位原始信息位D3位奇偶效验位P通过如下方式组成:
  
C7
  
C6
C5
C4
C3
C2
C1
说明
D
D
D
P
D
P
P
信息位D与效验位P的排列形式
D
D
D
P
原始信息位C7C5C3与附加位C1组成偶效验
D
D
D
P
原始信息位C7C6C3与附加位C2组成偶效验
D
D
D
P
原始信息位C7C6C5与附加位C4组成偶效验
我们现在可以发现这样用3个附加位的好处了:如果由附加位C1组成的奇偶效验码C7C5C3C1发现错误,我们可以推断C7C5C3这三位中有一位出错;如果由附加位C2组成的奇偶效验码C7C6C3C2发现错误,我们可以推断C7C6C3中有一位出错;如果由附加位C4组成的奇偶效验码C7C6C5C4发现错误,我们则可以推断C7C6C5中有一位出错。
上叙规律用左图表示,根据124这三组奇偶效验码的指示,我们可以准确的知道原始信息位C7C6C5C3哪个出了错。比如12同时报错但4组无错,可以断定C3错了。
例如:原始信息码1101通过(74)码进行编码为:
  
C7
  
C6
C5
C4
C3
C2
C1
说明
1
1
0
P
1
P
P
信息位D与效验位P的排列形式
1
0
1
0
C1=0使得该组1的个数为2个
1
1
1
1
C2=1使得该组1的个数为4个
1
1
0
0
C4=1使得该组1的个数为2个
1
1
0
0
1
1
0
1100110为1101的(7,4)编码
编码后的1100110经过传输,假设因为线路噪音变为1110110
发送信息:1100110 ———> 接收到的信息:1110110
     位:7654321                               位:7654321
使用右图我们可以准确发现错误:
C1C7C5C3C1=111031,该组有错误
C2C7C6C3C2=111141,该组没错
C4C7C6C5C4=111031,该组有错误
根据集合方式,由14组的圆,我们肯定C5C7有错,由2组的圆,得到C7没错,于是出错的肯定是C5。为了纠正它,将收到的C5=0改为C5=1即可。
实际使用中,汉明采用了数学上更好的形式,可以非常方便的通过清晰的矩阵运算得到纠错结果。汉明在提出(74)码的过程中,还建立了基础的编码理论。经过高伯(Goppa)和谢伐斯曼(Tsfasman)的发展,现代编码已经是计算机系统中最重要的技术之一。汉明码还有一个更绕口的名字加线性分组码。
奇偶校验
奇校验:如果以二进制数据中1的个数是奇数为依据,则是奇校验
偶校验:如果以二进制数据中1的个数是偶数为依据,则是偶校验



您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|C114 ( 沪ICP备12002292号 )|联系我们 |网站地图  

GMT+8, 2018-7-19 21:48 , Processed in 0.093750 second(s), 14 queries , Gzip On.

Copyright © 1999-2018 C114 All Rights Reserved

Discuz Licensed

回顶部