循环冗余校验码（CRC码）

循环冗余校验码的思想：
数据发送、接受方约定一个“除数”
K个信息位+R个校验位作为“被除数”，添加校验位后需保证除法的余数为0。收到数据后，进行除法检查余数是否为0，若余数非0说明出错，则进行重传或纠错。

例.设生成多项式为G(x)=$x^3$+$x^2$+1，信息码为101001，求对应CRC码。

1.确定K、R以及生成多项式对应的二进制码

K=信息码的长度=6，R=生成多项式最高次幂=3——>校验码位数N=K+R=9
生成多项式G(x)=1*$x^3$+1*$x^2$+0*$x^1$+1*$x^0$，对应二进制码1101

2.移位

信息码左移R位，低位补0。（101001000）

3.相除

对移位后的信息码，用生成多项式进行模2除法，产生余数

模2除法：

对应的CRC码：101001 001

4.检错和纠错

发送：101001001 记为$C_9$$C_8$$C_7$$C_6$$C_5$$C_4$$C_3$$C_2$$C_1$
接收：101001001 ———> 用110进行模2除——> 余数为000，代表没有出错。

K个信息位，R个校验位，若生成多项式选择得当，且$2^R$>=K+R+1，则CRC码课纠正1位错。（实际应用中一般只用来“检错”）

理论上可以正面循环冗余校验码的检错能力有以下特点：
1.可检测出所有奇数个错误；
2.可检测出所有双比特的错误；
3.可检测出所有小于等于校验位长度的连续错误

以下一个小例子：

/**
     * 计算CRC16校验码
     *
     * @param bytes
     * @return
     * [1,3,4,1,205,1,18,235,173]
     */
    public static String CRC16(byte[] bytes) {
        int CRC = 0x0000ffff;
        int POLYNOMIAL = 0x0000a001;
        int i, j;
        for (i = 0; i < bytes.length; i++) {
            CRC ^= ((int) bytes[i] & 0x000000ff);
            for (j = 0; j < 8; j++) {
                if ((CRC & 0x00000001) != 0) {
                    CRC >>= 1;
                    CRC ^= POLYNOMIAL;
                } else {
                    CRC >>= 1;
                }
            }
        }
        return Integer.toHexString(CRC);
    }


     public static void main(String[] args) {
        byte[] s ={1,3,4,1,(byte) 205,1,18,(byte)235,(byte)173};

         System.out.printf("1111%s\r\n",CRC16(s));
        if (CRC16(s)!="00"){
            System.out.printf("2222%s\n",CRC16(s));
        }
    }

前言

循环冗余校验码简称CRC码,是目前使用非常广泛的数据校验方式.它不仅能校验传递过来的数据正确性,还能筛查出哪一位出现了错误.它的局限性是只能校验一位数据发生跳变,在现实世界当中数据发生跳变很大很大的概率只有一位发生变化,因此CRC码也拥有很大的发挥舞台.

发送方数据处理

前期准备

假设发送方A向接收方B发送一串二进制数据101001.A需要计算出K位校验码,放在原始数据的后面一起发送给B.

它们双方事先约定了一个私密的二项式G(x) = x^3 + x^2 +1,这个多项式用来计算校验码的位数和值.二项式的设计必须符合一定的规则,G(x)的最高项和最低项的系数必须为1.通过这个二项式我们首先可以获取K的大小,最高项x^3的幂指数3就等于K.另外通过二项式G(x)生成数据串G(x) = 1*x^3 + 1*x^2 + 0*x^1 +1*x^0 = 1101(将二项式前面的系数组合在一起就形成了数据串).数据串可以帮助我们计算出校验码的值.

在有些情景下,我们无法获知多项式G(x).但直接得到了多项式生成后的数据串1101,此时怎么知道校验码有几位呢?用数据串的长度减去1就是K的大小.

校验码的计算

从上面描述可知二进制数据101001现在需要加上3位校验码,而用于校验的数据串也已经算出为1101.那通过这两个条件如何计算出校验码呢?在这里采用的是模2除法.模2除法它既不向上位借位,也不比较除数和被除数的相同位数值的大小,只要以相同位数进行异或运算即可.详细运算过程如下:

• 101001后面需要加上3位校验码,先添加3个0替代变成101001000,随后对1101做模二除法
• 然后要看被除数的最高位是1还是0,是1商就上1,是0商就上0.此时被除数最高位是1,所以商为1.1再乘以1101和1010做异或运算
• 第一轮计算余数为0111,舍弃最高位0,将后面的0填上就变成了1110.此时被除数变成了1110,最高位仍然为1,所以商仍然上1,将1101和1101做异或运算.结果0011,舍弃最高位0,将后面的1填上,被除数就变成了0111.依次类推算到最后一位的余数为001.
• 只要本着被除数的最高位为几商就写几的原则进行异或运算后的余数的最高位一定是0,是0就可以舍弃,继续进行下面的运算.最后得出的最终余数001就是我们想要的3位检验码.
• 通过这种模二除法有什么好处呢?比如说数101001后面加三个0后对1101做模二除法,最终会得到三位余数.然后将三位余数替换被除数的三个0再对1101做模二除法时,余数一定为0.换言之101001001再对1101做模二除法时余数一定为0.利用这个特性就可以做数据校验.

接受方数据校验

接受方B此时已经接受到了A传递过来的数据 101001001,并且他也知道事先约定的多项式g(x),他先通过g(x)计算出数据串为1101.他现在要开始做校验操作了.让101001001对1101做模二除法.

计算出来的余数为0,说明传送过来的数据正确.

假如传送过来的数据101001001第二位发生了跳变,变成了101001011,那运算结果又会如何?

最后计算出来的余数为010,并不为0,说明数据发生了跳变.而010代表数字2,指明是第二位数据出现了错误.细心的同学肯定会发现3位校验码最多只能表示8种情况,而101001001有9个数字,在最多只有一位数字发生跳变的前提下,它的错误情况有九种,这样的话3位校验码就无法表示所有的出错情况了.比如说101001001最高位发生了跳变.

最高位发生跳变时,被除数的最高位为0,商上0继续运算,算到最后的余数为010.此时我们可以发现最高位(第9位)发现跳变时最后算出的余数是010,而第二位发生跳变时也是010,如果接收方算出了010,它也无法确定到底是第二位出错还是第九位出错,这样就只能检错而不能纠错.为了避免此类状况的发生,多项式g(x)和信息数据的长度设计显得尤为重要.

cyclic redundancy check
CRC 循环冗余校验码
奇偶校验其实就是CRC校验的一种特例
循环冗余校验码由信息码n位和校验码k位构成。k位校验位拼接在n位数据位后面，n+k为循环冗余校验码的字长
具有检错、纠错能力的校验码
模二除法(模二除法的结果不等于普通除法)
当部分余数首位是1时商取1，反之商取0。然后每一位的减法运算是按位减，不产生借位
例如：

如果要传输的数据为：1101011011

除数设为：10011

在计算前先将原始数据后面填上4个0：11010110110000，之所以要补0，后面再做解释。

从这个例子可以看出，采用了模2的加减法后，不需要考虑借位的问题，所以除法变简单了。最后得到的余数就是CRC 校验字。为了进行CRC运算，也就是这种特殊的除法运算，必须要指定个被除数，在CRC算法中，这个被除数有一个专有名称叫做“生成多项式”。
生成多项式的最高阶数，就是要补0的个数。
生成多项式的选取是个很有难度的问题，如果选的不好，那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了，对于我们这些使用者来说，只要把现成的成果拿来用就行了。
计算方法:
1.计算冗余位的位数，即生成多项式的最高阶数

2.在信息位后补冗余位个数的0

3.将第二步的结果与生成多项式相除，这里采用的除法叫做模2除法，就是只要部分余数的高位为1，便可商1 之后上下做的减法是异或。

4.经过第三步不断地计算后得到余数
将信息为后面补的0换成余数