-
13 CRC
循环冗余校验原理及
FPGA
实现
13.1
基本
CRC
循环冗余校验原理介绍
循环冗余码校验英文名称为
Cyclical
Redundancy Check
，简称
CRC
。
它是利用除法及余数的原理来作错误侦测（
Error Det
ecting
）的。实
际应用时，发送装置计算出
CRC
值并随数据一同发送给接收装置，接收装
置对
收到的数据重新计算
CRC
并与收到的
CRC
相比较，若两个
CRC
值不同，
则说明数据通讯出现错误。
根据应用环境与习惯的不同，
CRC
又可分为以下几种标准：
①
CRC-12
码；
②
CRC-16
码；
③
CRC-
CCITT
码；
④
CRC-132
< br>码。
CRC-12
码通常用来传送
6-bit
< br>字符串。
CRC-16
及
CRC-CCITT<
/p>
码则用是来传送
8-bit
字符，其中<
/p>
CRC-16
为美国
采用，而
CRC-CCITT
为欧洲国家所采用。
CRC-132
< br>码大都被采用在一种称为
Point-to-
Point
的同步传输中。
特点
CRC
是种常用的检测错误的循环码，它能够榆测出如下错误：
（
1
）突发长度小于
r
的突发错误。
。
-
r-1
）
（
2
）
大部分突发长度等于
r<
/p>
十
l
的错误，
其
中不可检测的这类错误只占
2
（
（
3
）大部分突发
K
度大于
r+1
的错堤，其中不可检测
的这类错误只占
2
-r
。
（
4
）所有奇数个错误。
C
RC
检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能
力来看，
它所不能发现的错误的几率仅为
0.0047
%
以下。
从性能上和开销上考虑，
均远
远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，
CRC
无处不在：
著名的通讯协议
X.25
的
FCS(
帧检错序列
)
采用的是
CRC-CCITT
，
WinRAR
、
NERO
< br>、
ARJ
、
LHA
等压缩工具软件采用的是
CRC132
，磁盘驱动器
的读写采用了
CRC16
，
通用的图像存储格式
GIF
、
TIFF
等也都用
CRC
作为检错
手段。
生成原理
CRC
循环码即在
m
位信息码后再拼接
r
位的校验码，整个编码长度为
n
位，因此这种编码又叫
(n
，
k)
码。对于一个给定的
(n
，
k)
码，可以证明存
在一个最高次
幂为
n-k=r
的多项式
g(x)
。根据
g(x)
可以生成后位信息的校
验码，而
g(
x)
叫做这个
CRc
码的生成多项式。
校验码的具体生成过程为：
假设发送信息用数据多项式
m(x)
表示，将
< br>m(x)
左移
n
一
k
位，则可表
示成，
n(z
)
×
2
n-k
。这样
m(x)
的右边就会空出
n
一
k
位，即校验码的位置。
通过
m(x)
×
2
n-k
,
除以生成多项式
g(x)
得到的商
Q(x
和余数<
/p>
r(x)
，
其中余数
r(x)
就是校验码。即：
在发送端发送数据时余数加到信息码之后一同发出，将
一组信息码和
余数组成的数据块称为一个码元，设为
T(x)<
/p>
，则有
在接收端任一组多项式
T(x)
都应被
生成多项式
g(x)
整除，如果传输中
未发生错误，则接收码元与发送码元相同，故接收的码元必定能被
g(x)
整
除；若码元在传输中发生错误，则接收的码元可能除不尽而有余数，因此<
/p>
我们就以余数是否为零来判断接收码元中有无错误。可能有错误的码元正
< br>好也被
g(x)
整除，这是
CR
C
校验无力消除的，但通过选择多项式
g(x)
和增
加冗余位数，使余数
r(x)
多项式的位数增多，来降低发生这种错误的概率。
3.
生成多项式的选择
生成多项式
g(x)
是构成
CRC
校验码的关键。
它的选取并不是任何一个多
项式都可以作为生成多项式的，从检错与纠错的要求出发
，生成多项式应
能满足下列要求：
(
1)
任何一位发生错误都应使余数不为
0
；
(2)
不同位发生错误应当使余
数不同；
(13)
应满足余数循环规律。
CRC
有多种国际标准，各种标准如下：
CRC
校验可以
100
％地检测出所有奇数个随机错误和长度小于等于愚
(
是为
g(z)
的阶数
< br>)
的突发错误。所以
CRc
的生
成多项式的阶数越高，误判的概率
就越小。
13.2 CRC
循环冗余码
FPGA
设计思想
1.
编码电路的设计思想
编码电路的功能是己知信息数据位和生成多项式，要得到
对应的
CRC
码字。
CRC
码是系统码，对一个合法的
CRC
码字前面部分是
原始信息位，后面部分为校
验位部分。因此，若能求解出校验位，把它与原始数据组合即
可得到
CRC
码。现
已知
m(x)
，
G(x)
，要求
R(x)
，用
X*m(x)
除以
G(x)
，它的余式即为
X'R(x)
。用
二进制数表示，
即将原始信息位后添
r
个
0
后的数据除以生成多项式对应的二进
制数，所得余数即是校验位。
2.
解码电路的设计思想
一个合法的
CRC
码的多项式，它应该能被
G(x)
整除。据此，现对
一个位长为
n
的数据段
(
可能不是一合法
CRC
码
)
，
其多项式除以
G(x)
，
若其余数为零，
说明
该码
字是合法的，
取出其前面部分即为发端发送的有效数据，
即完成
解码；
若余
数不为
0
< br>，则该码字出错，接收方可以告知发方重发，或进行纠错后再解码。实
际上，对任
意的
CRC
码都能纠正一个错误。
3.
软件及硬件实现方法
一般有以下几种软件实现方法
：
逐位运算法
：则是用简单的软件编程来实现
CRC
编码，完成这种编码的原
理同使用线性反馈移位寄存器的
硬件方法雷同。假定监督位已储存在称之
为
CRC
的寄存器中，则逐位运算法则的实现步骤可归纳如下：
①给
CRC
寄存器赋值为
0
②如果
CRC
寄存器中最左边的
1
位是”
l
”
，则移人下一个消息位，
并且用
码的生成多项式对
CRC
寄存器
进行模
2
相加；否则，只移人下一个消息位
③重复第
2
步，直到一帧消息码的所有位都被移人为止。
标准查
找表运算法
：对所有增加了
a
位组合的
CRC
编码进行预处理，然后
在查找表
中找出对应的值作为
CRC
编码的监督位。假设监督位已储存在
称
之为
CRC
的寄存器中，则标准查找
表运算法则的软件实现步骤归纳如下：
< br>①给
CRC
寄存器赋值为
0
，即设置
(r
n
-
-k
一
1
，
.
...
，
ro)
位为
< br>0
。
②用右移了
(n
—
k
—
a)
位的
CRC
寄存器的内容对
a
个输入位进行模
2
相加，
即用
((r
n
-k-1,....,ro)
进行模
2
相加。
③在查找表中找出相应的值，并且用左移了
a
位
的
CRC
寄存器的内容对其
进行模
2
相加，即用
(
(r
n
-k-1,....,ro)
进
行模
2
相加，然后代替原
CRC
寄
存器的内容。
④重复第二和第三步，直到所有的信息位都移人为止。
一般有以下几种硬件实现方法：
(1
)
采用
LSFR
（线性反馈移位寄存器
组）来完成，这种方法简单，但
每次只能处理一位二进制数据，也很难以满足速度较高的场合。
(2)CRC
校验码的并行算法有查表法及基于查表法而导出的
一些方法，但这
些方法均需要存储长度较大的
CRC
余数表，并且随着并行位数的增加，余
数表的长度按指数增加，其现实性亦
随之大大降低
.
(13)
根据线性时
不变系统的特性推出了用于计算
CRC
校验码
< br>,
计算的转换矩
阵，但变换矩阵的推导方法过于烦琐。<
/p>
(4)
按字节运算方法，它直接推导出
CRC
校验码与输入数据和生成多项式的
逻辑关系，然后直接运算得出
CRC
校验码，这种方法直接、
简洁。
13.3 CRC
循环冗余码
FPGA
实现
CRC
—
16
校验码，
采用的生成多项式为
g(x)=x16+x
15+x2+l
，
依据上述的
推导公式
的结论设计出逻辑电路
(
见下图
)
，在图中有
16
级移位寄存器和
13
个异或门，实现
CRC
码的计算。初始化时每一位寄存器都清零，然后每输
入一位数据，
16
位移位寄存器按照异或逻辑由低到高进行移动
1
位，直到一
组校验数据结束，此时，
16
位移位寄存器的内容就是该组数据的
CRC-16
< br>的
校验位。
这里采用
按字节运算
方法，它直接推导出
CRC
校验码与输入数据和生成多项
式的逻辑关系，然后直接运算得出
CRC
校验
码。
添加
test bench
进行功能测试。
从仿真结果可知，
当输入为
1001
时，
通过<
/p>
CRC
校验得到的校验
位如上图所示。
由于串行
CRC
< br>运算，当前的
CRC
余数值只与当前信息码的最前一位的
输
入值和前一状态的
CRC
余数值有关
，所以，当输入到最后一位信息位时，
此时的校验位即为最终的校验位。这里输入的信息
为周期信号，所以当第
16
位到达后，从图中可以看到校验位为
1100
，这与通过计算
所得的结果一
致，验证是正确的。
通过综合后的
RTL
图以及内部详细的电路结构如
上图。
在板上调试时，需要添加一个信号产生模块
source,
以下是对
Source
添加
test
bench
后的功能仿真波形：
即输入信号设为
1101
。
-
-
-
-
-
-
-
-
-
上一篇：张敏版 科技英语阅读教程 英译汉 中文翻译
下一篇：超声波雷达的试验研究