数据链路层-差错控制(循环冗余码 CRC)
2.循环冗余码(CRC)
- 将任何一个由二进制位串组成的代码,与一个只含有 0 和 1 两个系数的多项式建立一一对应关系。
- 多项式的算数运算采用 代数域理论的规则,以 2 为模来完成,即加法没有进位,减法没有借位,模2加法和模2减法都等同于异或。
CRC 的基本思想:发送方和接受方先商定一个生成多项式 G(X),发送方编码和接受方校验都是利用预先商定的生成多项式来得到。假设 G(X) 的阶为 r,发送方要发送的信息位为 k位,CRC 的基本思想是在信息位的尾部追加一个 r位的冗余位,使得信息位与冗余位构成的码字所对应的多项式能够被 G(X)除尽。当接收方收到码字后,用其除以 G(X),如果有余数则表明传输过程中有错误。
CRC 的步骤
- 确定生成多项式 G(X)、信息位对应的多项式 K(X)、冗余位的位数 r(CRC中r等于 G(X) 的阶)
- 在信息位的后面加上 r 个 0,对应的多项式的 X^rK(X)
- 用 X^rK(X) 除以 G(X) 得到的余式就是冗余位对应的多项式 R(X)
- 这里的除法就是多项式的模2除法,模 2除法中用到的减法是模 2减法
- 得到信道上发送的码字多项式 T(X)=X^rK(X)+R(X)
- 校验。若传输过程无差错,则接受方收到的码字多项式能被 G(X) 整除;若不能被 G(X) 整除,则说明传输过程中产生了差错。
CRC的一些性质: