循环冗余校验(CRC)原理

原理简介

CRC通过增加若干冗余位数据来于核实数据传输或者数据存储的正确性和完整性。

假如要传输的有效数据D有k位，冗余数据F共n-k位，那么整个传输帧T：

图 1校验码格式

数据发送方和接受方要实现预定一个(n-k+1)位的整数P，并且约定T和F满足：

TmodP==0……(1)

其中mod是求余运算，加上图1显示的关系有：

T=（2n−k）*D+F……(2)

基于上述要求，实际应用时，发送方和接收方按以下方式通信：

1. 发送方和接收方在通信前，约定好预设整数P。

2. 发送方在发送前通过(1)和(2)式确定并填充F，然后发送。

3. 接收方收到数据，进行 result = T mod P 运算，当且仅当result = 0时接收方认为没有差错。

发送方在发送数据前需要确定填充的(n-k)位F值。

我们知道采用无进位的二进制加法，等价于将被加数和加数进行异或(XOR)操作。

由于我们最终的目的是(1)式，根据(2)式，我们有

(2n-kD+F)/P=2n-kD/P+F/P……(3)
现在，我们令

2n-kD/P=Q+R/P……(4)
于是，我们有

(2n-kD+F)/P=Q+R/P+F/P……(5)
由于采用无进位的二进制加法(等价于XOR操作)，因此当我们令 F=R时，即

T=2n-kD+R，有 (2n-kD+F)/P=Q+R/P+F/P=Q……(6)

此时便有(1)式成立。因此利用模二加法我们知，我们需要添加的帧检验序列F为：

F=2n-kDmodP……(7)

举个例子

发送方要传输的数据D是10110100共8位，发送方和接收方约定P为101，共三位，冗余位n-k共2位 那么F=2n-kDmodP=（22*10110100）mod(101) =(1011010000)mod(101)=00 那么传输帧T就是1011010000