循环冗余校验码(CRC)和海明校验码

二进制数据经过传送、存取等环节，会发生误码(1变成0或0变成1)，就有了如何发现及纠正误码的问题。

验错、纠错、码距

验错顾名思义，检验错误。纠错，在验错的基础上，还要纠正错误。
码距，一言蔽之：不同位的个数即是码距。两个码组对应位上数字的不同位的个数称为码组的距离，简称码距，又称海明（Hamming）距离。例如00110和00100码距为1，12345和13344码距为2，Caus和Daun码距为2。

海明校验码公式（假设为k个数据位设置r个校验位）
2^r ≥ k + r + 1

海明校验码

求1011的海明码
1.根据公式：k等于4。代入2^r ≥ 5 + r可知，r最小为3。所以海明码位数为4+3=7位
2.填表：信息位从高到低依次存放；海明校验码放在2的幂次位上

 位数       1      2      3      4      5      6      7
信息位                    1             1      0      1
校验位      r1     r2            r3
 下标       1      2     1+2     4     4+1    4+2    4+3    
海明码      r1     r2    r1+r2   r3    r3+r1  r3+r2  r3+r2+r1

得到r1、r2、r3位置：
r1:3、5、7
r2:3、6、7
r3:5、6、7

3.异或运算（同0异1）：
第3、5、6、7位分别为1、1、0、1，则
r1=3⊕5⊕7 ==> 1⊕1⊕1 ==> 0⊕1 ==> 1
r2=3⊕6⊕7 ==> 1⊕0⊕1 ==> 1⊕1 ==> 0
r3=5⊕6⊕7 ==> 1⊕0⊕1 ==> 1⊕1 ==> 0
4.代入表格，从低位到高位排序的海明码为：1010101

 位数       1      2      3      4      5      6      7
信息位                    1             1      0      1
校验位      1      0             0

循环冗余校验码(CRC)

假设使用的生成多项式是 G(x)=x³+x+1。4位的原始报文为1010，求编码后的报文？

1.根据G(x)=x³+x+1得到二进制1011：G(x)=x³+x+1等价于G(x)=x³+x¹+x⁰。其中x²没有，而指数3、1、0位有。则第3、1、0为1，第2位为0，即1011

2.1101共有4位，在原始报文后添（4 - 1）个0，得到1010 000

3.对第二步的1010 000进行模2除法（同0异1）：

                 1 0 0 1
        ___________________
        |               
1 0 1 1 |  1 0 1 0 0 0 0
        /  1 0 1 1      
         ——————————————————
             0 0 1 0
             0 0 0 0
         ——————————————————
               0 1 0 0
               0 0 0 0
         ——————————————————
                 1 0 0 0
                 1 0 1 1
         ——————————————————
                   0 1 1  (余数，校验位)

4.编码后的报文（CRC码）：原始报文1010加上余数011，即1010 011