当前位置:文档之家› 循环冗余校验码

循环冗余校验码


检错性能
能检测出全部单个错误 能检测出全部随机二位错误 能检测出全部奇数个错误 能检测出全部长度小于k位的突发错误 能以[1-(1/2)k-1]概率检测出长度为(k+1) 位的突发性错误

例如:g(x)=x^4+x^3+x^2+1,(7,3)码,信息码 110产生的CRC码就是: 对于g(x)=x^4+x^3+x^2+1的解释:(都是从右往 左数)x4就是第五位是1,因为没有x1所以第2位 就是0。 11101 | 110,0000(设a=11101 ,b=1100000) 用b除以a做模2运算得到余数:1001 余数是1001,所以CRC码是1001,传输码为: 110,1001

若信息码字为11100011,生成多项式 G(X) =X5+X4+X+1,则计算出的 CRC 校验码为? 1110001100000/110011=10110110*11001 1+11010,所以11010是校验码。

课堂练习题

设某一循环码,其生成多项式为G(X)=X5 + X2+1,试求出信息序列1101010101011的循 环校验码CRC(要求写出计算步骤)。
6.CRC码生成器和校验器 循环冗余码生成器采用模2除法。下图显 示了这一过程。 CRC校验器的功能完全像发生器一样,当 收到附加了CRC码的数据后,做同样的模 2 除法。如果余数是全0,则将CRC码丢 弃,接受数据。否则,丢弃收到的数据。
பைடு நூலகம்
CRC校验码的生成器和校验器
数据
r个比特0数据
数据
1011011 x6+x4+x3+x+1

x +x4+x2+x 110110
5
码多项式

码多项式运算法则:
二进制码多项式的加减运算为⊕模2加运算,
即两个码多项式相加时,对应项系数进行模 2加减。 乘除运算与普通多项式类似;

模2加减:即各位做不带进位、借位的按 位加减。这种加减运算实际上就是逻辑 上的异或运算。即加法和减法等价。
循环冗余校验码
概述

循环冗余检查(CRC)是一种数据传输检错功能, 对数据进行多项式g(X)计算,并将得到的结果 附在要传输的信息的后面,接收设备也执行类似 的算法,以保证数据传输的正确性和完整性。若 CRC校验不通过,系统重复向硬盘复制数据,陷 入死循环,导致复制过程无法完成。出现循环冗 余检查错误的可能原因非常多,硬件软件的故障 都有可能。接收方如何检查收到的信息有无错误? 首先接收方和发送方约定一个‚生成多项 式‛g(x)。相当于两方传递信息需要对的口令。

第三步:求CRC循环冗余校验码 (K+r)被除数+r(余数)


如果余数位数小于r,最左的缺省位数为0。 如果余数为0,则r=0。
生成多项式G(X)要满足的原则
生成多项式应满足以下原则 a、生成多项式的最高位和最低位必须为1。 b、当被传送信息(CRC码)任何一位发生错 误时,被生成多项式做模2除后应该使余数不 为0 。 c、不同位发生错误时,应该使余数不同。 d、对余数继续做模2除,应使余数循环。
码多项式

生成多项式G(x):
求CRC码时所用的‚除数‛所对应的多项式
叫生成多项式。

在串行通信中通常使用下列三种生成多 项式G(X)来产生CRC码。
CRC-16:G(x)=X16+X15+X2+1,美国二进制同
步系统中采用。 CRC-CCITT:G(x)=X16+X12+X5+1,CCITT推荐。 CRC-32:G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7+ X5+X4+X2+X+ 1

5.多项式

任何一个二进制数序列可以和一个只含有 0和1两个系数的代数多项式建立起一一对 应的关系。因此,用来求CRC码的那个除 数通常用多项式来表示。原因如下:
代数多项式很短 可以通过多项式来进行概念的数学证明。
多项式

任何一个n位的二进制数都可以用一个n-1 次的多项 式来表示,这种多项式叫码多项式(又叫信息多项 式) 。 码多项式与二进制序列之间的一一对应关系:
实际应用中,g(x)的取值是有限制的,它受限于 以下国际标准: CRC-CCITT=x^16+x^12+x^5+1 CRC-16=x^16+x^15+x^2+1 CRC-12=x^12+x^11+x^3+x^2+x+1 关于g(x)的国际标准还有一些,这里不一一介绍。 人工计算循环冗余校验码需要先弄清的知识:多 项式除法、异或运算。

3.CRC码的生成

CRC码生成和校验基本分为三步: 第一步:在数据单元 (k 位)的末尾加 上r个0。r是一个比预定除数g(x)的比 特位数(r+1)少1的数。 第二步:采用二进制除法将新的加长 的数据单元(k+r位)除以除数g(x) 。 由此除法产生的余数就是循环冗余码 校验码。
CRC码的生成

编码规则
非常简单,要说明的:模2除就是在除的过程 中用模2加,模2加实际上就是我们熟悉的异 或运算,就是加法不考虑进位,公式是: 0+0=1+1=0,1+0=0+1=1 即‘异’则真,‘非异’则假。 由此得到定理:a+b+b=a 也就是‘模2减’和 ‘模2加’直值表完全相同。 有了加减法就可以用来定义模2除法,于是就 可以用生成多项式g(x)生成CRC校验码。

编码规则
CRC码是由两部分组成,前部分是信息码,就是 需要校验的信息,后部分是校验码,如果CRC码 共长n个bit,信息码长k个bit,就称为(n,k)码。 它的编码规则是: 移位 将原信息码(kbit)左移r位(k+r=n),而后尾 巴上添r个0。 相除 运用一个生成多项式g(x)(必须转换成二进制 数)用模2除上面的式子,得到的余数就是校验码。 移位后的信息码mod多项式g(x)=校验码

设某一循环码,其生成多项式为G(X)= X5+X4+ X2+1,试求出信息序列1010001100的 CRC循环校验码(要求写出计算步骤)。
g(x)
r+1 余数 先发数据位 后发校验位
g(x)
r+1
CRC校验码
r
余数
0接收,非0拒绝
r
发送方
接收方
G(X)
0



111010100011010 CRC校验码 信息码 CRC冗余校验码
7.CRC码性能
CRC码是很有效的差错校验方法。除了正好 数据块的比特值是按除数值变化的错误外, 循环冗余校验(CRC)将检测出其他所有错误。 而且,常用的CRC除数通常有17,或是33个 比特,使得不可检测的错误可能降低到几乎 近于零。 CRC接收电路再配上适当的硬件电路不仅可 以检错,而且可以纠错,纠错能力很强特别 适合检测突发性错误,在数据通信中得到较 广泛的应用。
引言

CRC(Cyclic Redundancy Check)循环冗余校 验码,是常用的校验码,在早期的通信中运用 广泛,因为早期的通信技术不够可靠(不可靠 性的来源是通信技术决定的,比如电磁波通信 时受雷电等因素的影响),不可靠的通信就会 带来‘确认信息’的困惑。
简介


对通信的可靠性检查就需要‘校验’,校验是从数据 本身进行检查,它依靠某种数学上约定的形式进行检 查,校验的结果是可靠或不可靠,如果可靠就对数据 进行处理,如果不可靠,就丢弃重发或者进行修复。 (倒推法):发送方发送的是T(x),接收方接收到的是 R(x),若T(x)和R(X)相等,则传输的过程中没有出现错 误。如何判断T(x)和R(X)是否相等?若R(X)能够被g(x)整 除,则接收方认为T(x)和R(X)相等,即传输的过程中没 有出现错误。发送方要传输的信息info包含在T(x)里, info是T(x)的一部分,但不能说info就是T(x)。


(an-1 an-2……a1a0)N A (x)= an-1Xn-1+an-2Xn-2 +……+a1X+a0X0

码多项式
多项式

二进制序列实例
以n=3位二进制数为例 二进制数 对应多项式 000 0 001 1 x 010 x+1 011 x2 100 x2+1 101 111 x2+ x+1
相关主题