CRC循环冗余校验

时间:2021-08-22 11:58:25

在传输帧的过程中,由于电干扰或热噪音等等影响,帧的比特位会出错。特别是在光链路中,需要差错检测机制来及时纠正。最常用的一项技术CRC(Cyclic Redundancy Check)循环冗余校验 。


CRC 码是基于模2建立的校验码,它的运算不考虑进位和借位,即俩个相同的数模2恒为0。


CRC循环冗余校验


编码原理

CRC 编码的理论基础源于数学分支中的一个有限域。听起来深奥,但基本思想很容易理解。接下来从组成它的每一个多项式展开。


首先考虑一个由N次多项式表示的N+1位比特消息M(X),每一比特位的值为 对应其每项多项式的系数,且从为高位比特开始。如一个8比特10011010对应的多项式为 M(x)=x^7 +x^4 +x^3 +x^1。


为了计算CRC 发送方和接收方还得协定一个除数多项式 C(x), C(X) 对检测差错有很大影响,且准确的选择通常是协议设计的一部分,如以太网使用的就是CRC-32 位。


发送方想要发送一个 n+1 比特长的消息时,其实发送的是 n+1 +k 位的P(x),K 位 为校验冗余码,指的是额外发送的比特位,他们不向消息中加入新消息,而是用明确的算法从原始消息中导出信息。我们要做的就是使P(X)能除C(X)且余数为0,另一方面,如果有传输错误,就无法整除,会产生一个非0余数。


例子如下:有效信息为1100,生成多项式C(x)=1011,求其CRC编码?
CRC循环冗余校验