检错码与纠错码，一码归一码

写在前面：
为什么需要差错处理
任何信道，即使是光纤，也会出错。
差错的类型
单个错误：分散在各块中
突发错误：集中在某个块中
注:突发错误比单个错误更加难于处理,通常利用处理单个处理的方法来应对突发错误。
差错的处理
纠错码：发现错误，从错误中恢复出正确的来。因其需要太多的冗余位，纠错开销太大，在有线网络中极少使用，主要用于无线网络中。
检错码：只能发现错误，不能从错误中恢复，但可采用重传
两种不同的处理方法适用于不同的环境
文章有部分引用

检错码

为什么要用检错码？
纠错需要较多的冗余位，信道利用率不高。
局域网中，主要使用的是检错码
奇偶校验码（海明距离为2，检1位错）
互联网校验(这里不做介绍)
循环冗余校验码

奇偶校验
一个校验位（Parity Bit）追加到数据后。
校验位的值取“0”还是“1”，取决于整个码字的总的“1”的个数。（奇数还是偶数）。等同于异或运算的结果1个个数。（异或:相同得0，不同得1）
奇偶校验无法纠错。在数据传输之前，我们会求一次校验位，传输后，会求一次校验位，那么，在奇偶校验中，我们通过比较这两个校验位是否相同，若结果为1，则说明有奇数个错误，结果为0，则说明正确或者偶数个错误。

循环冗余校验码（CRC码）
（1）基本思想
CRC码可以发现并纠正信息串行读/写、存储或传送中出现的一位或多位错（与多项式的选取有关）

（2）示例

发送端编码



接收端的检错

纠错码：汉明间距与汉明码

汉明距离
在一个码组集合中，任意两个码字之间对应位上码元取值不同的位的数目定义为这两个码字之间的汉明距离。即
d(x,y)=∑x[i]⊕y[i]，这里i=0,1,…n-1，x,y都是n位的编码，⊕表示异或
例如，(00)与(01)的距离是1，(110)和(101)的距离是2。
在一个码组集合中，任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。
最小汉明距离越大，码组越具有抗干扰能力。
下面我们用d表示码组的最小汉明距离。
1当码组用于检测错误时，设可检测e个位的错误，则
d >= e + 1
设有两个距离为d的码字A和B，如果A出现了e个错误，则A变成了以A为圆心，e位半径的球体表面的码字。为了能够准确地分辨出这些码字既不是A也不是B，那么A误码后变成的球面上的点与B至少应该有一位距离（如果B在球面上或在球面内部则无法分辨出到底B是不是A的错误码），即A与B之间的最小距离d >= e+1。
2若码组用于纠错，设可纠错t个位的错误，则
d >= 2t+1
设有码字A和B，如果A出现了t个错误，B也出现了t各错误，则A码变成以A为圆心，t为半径的球面上的码字；B码变成以B为圆心，t为半径的球面上的码字。为了在出现t个错之后仍能分辨一个码字到底是属于A的错码还是属于B的错码，A,B为球心的两个球面应该不相交，即球心A，B之间距离应该大于2t，所以d >= 2t+1。
3。如果码组用于纠正t个错，检测e个错，则
d >= e+t+1, 这里e>t
这种检错纠错方式结合的情况同上述两个情况类似。当码字出现t个或者小于t个错时，系统按照纠错方式工作。当码字出现超过t个错而小于等于e个错时，系统按照检错方式工作；当A出现e个错，B出现t个错时，既要纠正B的错，又要发现A的错，则以A为球心，e为半径的球和以B为球心，t为半径的球应该不相交，所以A,B之间的距离应该大于等于e+t+1，即d>=e+t+1。

汉明码
汉明码是一种线性分组码。线性分组码是指将信息序列划分为长度为k的序列段，在每一段后面附加r位的监督码，且监督码和信息码之间构成线性关系，即它们之间可由线性方程组来联系。这样构成的抗干扰码称为线性分组码。
设码长为n，信息位长度为k，监督位长度为r=n-k。如果需要纠正一位出错，因为长度为n的序列上每一位都可能出错，一共有n种情况，另外还有不出错的情况，所以我们必须用长度为r的监督码表示出n+1种情况。而长度为r的监督码一共可以表示2^r种情况。因此
2^r >= n + 1， 即r >= log(n+1)
我们以一个例子来说明汉明码。假设k=4，需要纠正一位错误，则
2^r >= n + 1 = k + r + 1 = 4 + r + 1
解得 r >= 3。我们取r=3，则码长为3+4=7。用a6,a5,…a0表示这7个码元。用S1,S2,S3表示三个监关系式中的校正子。我们作如下规定（这个规定是任意的）：
S1 S2 S3 错码的位置
0 0 1 a0
0 1 0 a1
1 0 0 a2
0 1 1 a3
1 0 1 a4
1 1 0 a5
1 1 1 a6
0 0 0 无错
按照表中的规定可知，仅当一个错码位置在a2,a4,a5或a6时校正子S1为1，否则S1为0。这就意味着a2,a4,a5,a6四个码元构成偶校验关系：
S1 = a6⊕a5⊕a4⊕a2 (1)式
同理，可以得到：
S2 = a6⊕a5⊕a3⊕a1 (2)式
S3 = a6⊕a4⊕a3⊕a0 (3)式
在发送信号时，信息位a6,a5,a4,a3的值取决于输入信号，是随机的。监督为a2,a1,a0应该根据信息位的取值按照监督关系决定，即监督位的取值应该使上述(1)(2)(3)式中的S1,S2,S3为0，这表示初始情况下没有错码。即
a6⊕a5⊕a4⊕a2 = 0
a6⊕a5⊕a3⊕a1 = 0
a6⊕a4⊕a3⊕a0 = 0
由上式进行移项运算，得到：
a2 = a6⊕a5⊕a4
a1 = a6⊕a5⊕a3
a0 = a6⊕a4⊕a3
已知信息位后，根据上式即可计算出a2,a1,a0三个监督位的值。
接收端受到每个码组后，先按照(1)~(3)式计算出S1,S2,S3，然后查表可知错码情况。
例如，若接收到的码字为0000011，按照(1)~(3)计算得到：
S1 = 0, S2 = 1, S3 = 1
查表可得在a3位有一个错码。
这种编码方法的最小汉明距离为d=3，所以这种编码可以纠正一个错码或者检测两个错码。

哈姆雷特，请保持前行！