模2除法和CRC

计算机网络/网络编程

CRC 校验过程如下：

  1. 收发双方商定一个多项式 G(x)

    一个 k 位二进制串可以视为从 Xk - 1 到 X0 的 k - 1 阶多项式的系数序列，如 1101 对应的多项式是 3 阶多项式 G(x) = X3 + X2 + 1。

  2. 发送方使用 G(x)和模 2 除法计算帧检验序列 FCS(即余数)，将 FCS 拼接在原始帧后面发送

    设要发送的原始帧长度为 m 位，G(x) 阶数为 r，首先将原始帧后面补 r 个 0，得到一个 m + r 位的被除数，将 G(x) 作为除数，进行模 2 除法，得到一个 r 位的余数，即 FCS，将 FCS 拼在原始帧后面，得到一个 m + r 位的序列，且它一定是可以被 G(x) 整除的，发送该帧。

  3. 接收方使用 G(x) 去除收到的带有 FCS 的帧，若整除说明无差错

设原始帧为 101001，G(x) 为 1101，计算模 2 除法的过程如下：

  1. 先补 0 得到被除数
  2. 若被除数首位为 1，则商1，否则商零
  3. 模 2 加减法计算余数，即异或运算
  4. 所得余数首位必为 0，去掉首位，被除数后面一位落下来，若现在余数首位为 1，则商1，否则商 0
  5. 重复 3， 4 两步直到余数位数少于除数 G(x) 的位数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
                1 1 0 1 0 1    //商
        | -----------------
1 1 0 1 | 1 0 1 0 0 1 0 0 0	//被除数首位为1，商1
        | 1 1 0 1	          	//异或
          -----------------
            1 1 1 0			//余数去除首位,作为新的被除数
            1 1 0 1			//被除数首位为1,商1
          -----------------
              0 1 1 1			//余数去除首位,作为新的被除数
              0 0 0 0			//首位为0,商0 
          -----------------
                1 1 1 0     
                1 1 0 1     
          -----------------
                  0 1 1 0     
                  0 0 0 0
          -----------------
                    1 1 0 0
                    1 1 0 1
          -----------------        
                      0 0 1	//余数位数少于除数,停止，得到 FCS