循环冗余校验码(CRC).pdf

CRC32算法学习笔记以及如何用java实现

一：说明

二：基本概念及相关介绍

2．1什么是CRC

在远距离数据通信中，为确保高效而无差错地传送数据，必须对数据

进行校验即差错控制。循环冗余校验CRC(CyclicRedundancy

Check/Code)是对一个传送数据块进行校验，是一种高效的差错控

制方法。

CRC校验采用多项式编码方法。多项式乘除法运算过程与普通代数

多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，

错位，如同逻辑异或运算。

2．2CRC的运算规则

CRC加法运算规则：

0+0=0

0+1=1

1+0=1

1+1=0(注意：没有进位)

CRC减法运算规则：

0-0=0

0-1=1

1-0=1

1-1=0

CRC乘法运算规则：

0*0=0

0*1=0

1*0=0

1*1=1

一、循环冗余校验码（CRC）

CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n

阶的二进制多项式，由。如一个8位二进制数可以表示

为：。多项式乘除法运算过程与普通代数多项式的乘除法相同。多

项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算一

致。

采用CRC校验时，发送方和接收方用同一个生成多项式g（x）,并

且g（x）的首位和最后一位的系数必须为1。CRC的处理方法是：

发送方以g（x）去除t（x），得到余数作为CRC校验码。校验时，

以计算的校正结果是否为0为据，判断数据帧是否出错。

CRC校验可以100％地检测出所有奇数个随机错误和长度小于等于

k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数

越高，那么误判的概率就越小。CCITT建议：2048kbit/s的PCM基

群设备采用CRC-4方案，使用的CRC校验码生成多项式g（x）=。

采用16位CRC校验，可以保证在bit码元中只含有一位未被检测

出的错误。在IBM的同步数据链路控制规程SDLC的帧校验序列

FCS中，使用CRC-16，其生成多项式g（x）=；而在CCITT推荐

的高级数据链路控制规程HDLC的帧校验序列FCS中，使用

CCITT-16，其生成多项式g（x）=。CRC-32的生成多项式g（x）

=。CRC-32出错的概率比CRC-16低倍。由于CRC-32的可靠

性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等

领域运用十分广泛。在一些UART通信控制芯片（如MC6582、

Intel8273和Z80-SIO）内，都采用了CRC校验码进行差错控制；以

太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。

二、CRC校验码的算法分析

CRC校验码的编码方法是用待发送的二进制数据t（x）除以生成多

项式g（x），将最后的余数作为CRC校验码。其实现步骤如下：

（1）设待发送的数据块是m位的二进制多项式t（x），生成多项

式为r阶的g（x）。在数据块的末尾添加r个0，数据块的长度增加

到m+r位，对应的二进制多项式为。

（2）用生成多项式g（x）去除，求得余数为阶数为r-1的二进

制多项式y（x）。此二进制多项式y（x）就是t（x）经过生成多项式

g（x）编码的CRC校验