差错检验与纠正： 循环冗余校验与汉明码
差错检验与纠正： 循环冗余校验与汉明码
对于信号传输过程种出现错误是很正常的
我们提供了两种策略
- 添加只能使对方推测出有无错误的冗余信息，检错码
- 添加使对方推测出没有出错前的数据的冗余信息，纠错码
两种策略占据不同的生态位置，
高度可信的信道（光纤）使用检错码更合算，偶尔发生错误就重传
错误发生频繁的信道上(无线链路)使用纠错码更合算，以便接收方能够计算原来的数据
检错码
- 奇偶
- 校验和
- 循环冗余校验
纠错码
- 汉明码
- 二进制卷积码
- 里德所罗门码
- 低密度奇偶校验码
下面介绍两种 循环冗余和法海明码
一丶循环冗余
在传输过程中可能会产生比特差错：1 可能会变成 0 而 0 也可能变成 1，误码率与信噪比有很大的关系，我们就要在数据后面添加上的冗余码称为帧检验序列 FCS (Frame Check Sequence)。
在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术，使用CRC获得FCS,下面演示CRC的用法
余数为0就没有错，且除数p越大，检测效果越好，越小可能有些错检测不出来
二丶汉明码
数据块总长度n，其中数据位长度m，校验位长度为r，n=m+r
码率=n/m 码率差别很大 有噪声的信道码率或许为1/2，光纤接近1
编码距离
合法代码集 {10001001，10110001}
可以看出 需要3个一位错误 才能使得 10001001 变成 10110001，直接两个进行异或运算
不同位数的个数称为编码距离，这个与检错能力与检错能力有关
一个完整的合法码字列表，从这找出两个具有最小还没距离的码字，这个距离就是编码距离，比如编码距离为d，需要d个1位错才能将一个合法代码转变成另一个合法代码，另外说假如我们
- 为了检测d个错误，需要一个距离为d+1的编码方案，
- 为了纠正d个错误，需要一个距离为2d+1的编码方案，
汉明码
海明码是具有1位纠错能力的编码，重叠分组的奇偶校验方法，如下图的7位数据