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

循环冗余校验码

▪ (K+r)被除数+r(余数)
▪ 如果余数位数小于r,最左的缺省位数为0。 ▪ 如果余数为0,则r=0。
4.CRC码的校验
• CRC码校验:
– 到达接收方的数据单去除以用来产生 循环冗余校验余数的G(X)。
– 如果余数0,将通过检验。如果余数非 零,将通不过检验。
5.多项式
• 任何一个二进制数序列可以和一个只含有 0和1两个系数的代数多项式建立起一一对 应的关系。因此,用来求CRC码的那个除 数通常用多项式来表示。原因如下:
• CRC接收电路再配上适当的硬件电路不仅可 以检错,而且可以纠错,纠错能力很强特别 适合检测突发性错误,在数据通信中得到较 广泛的应用。
检错性能
• 能检测出全部单个错误 • 能检测出全部随机二位错误 • 能检测出全部奇数个错误 • 能检测出全部长度小于k位的突发错误 • 能以[1-(1/2)k-1]概率检测出长度为(k+1)
码多项式
多项式 二进制序列实例
• 以n=3位二进制数为例
二进制数 对应多项式
000
0
001
1
010
x
011
x+1
100
x2
101
x2+1
111
x2+ x+1
1011011 x6+x4+x3+x+1
x5+x4+x2+x 110110
码多项式
• 码多项式运算法则:
– 二进制码多项式的加减运算为⊕模2加运算, 即两个码多项式相加时,对应项系数进行模 2加减。
– 代数多项式很短 – 可以通过多项式来进行概念的数学证明。
多项式
• 任何一个n位的二进制数都可以用一个n-1 次的 多项式来表示,这种多项式叫码多项式(又叫信息 多项式) 。
• 码多项式与二进制序列之间的一一对应关系:
– (an-1 an-2……a1a0)N
– A (x)= an-1Xn-1+an-2Xn-2 +……+a1X+a0X0
3.CRC码的生成
• CRC码生成和校验基本分为三步: – 第一步:在数据单元(k位)的末尾加 上r个0。r是一个比预定除数的比特位 数(r+1)少1的数。 – 第二步:采用二进制除法将新的加长 的数据单元(k+r位)除以除数。由此 除法产生的余数就是循环冗余码校验 码。
CRC码的生成
▪ 第三步:求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
6.CRC码生成器和校验器
– 乘除运算与普通多项式类似;
• 模2加减:即各位做不带进位、借位的按 位加减。这种加减运算实际上就是逻辑 上的异或运算。即加法和减法等价。
码多项式
• 生成多项式G(x):
– 求CRC码时所用的“除数”所对应的多项 式叫生成多项式。
• 在串行通信中通常使用下列三种生成多 项式G(X)来产生CRC码。
循环冗余校验编码(CRC)
• Cyclic Redundancy checking (CRC)循环 冗余校验,又称多项式码。
• 在循环冗余校验中,不是通过将各比特位 相加来得到期望的校验,而是通过在数据 单元末尾加一串冗余比特,称作循环冗余 校验码或循环冗余校验余数,使得整个数 据单元可以被另一个预定的二进制数所整 除。
位的突发性错误
课堂练习题
• 设某一循环码,其生成多项式为G(X) =X5 + X2+1,试求出信息序列 1101010101011的循环校验码CRC(要求 写出计算步骤)。
• 设某一循环码,其生成多项式为G(X)= X5+X4+ X2+1,试求出信息序列 1010001100的CRC循环校验码(要求写出 计算步骤)。
• 循环冗余码生成器采用模2除法。下图显 示了这一过程。
• CRC校验器的功能完全像发生器一样, 当收到附加了CRC码的数据后,做同样 的模2 除法。如果余数是全0,则将CRC 码丢弃,接受数据。否则,丢弃收到的 数据。
CRC校验码的生成器和校验器
数据 r个比特0数据
数据
g(x) r+1 余数
CRC校验码 r
先发数据位 后发校验位
发送方
g(x) r+1
余数 r
0接收,非0拒绝
接收方
0
G(X)
• 111010100011010

CRC校验码

信息码

CRC冗余校验码
7.CRC码性能
• CRC码是很有效的差错校验方法。除了正好 数据块的比特值是按除数值变化的错误外, 循环冗余校验(CRC)将检测出其他所有错误。 而且,常用的CRC除数通常有17,或是33 个比特,使得不可检测的错误可能降低到几 乎近于零。
(3)接收器用相同的数(生成多项式)去除 传来的帧。如果无余数,则认为无差错;如 果余数不为0,刚认为传输出错。
ห้องสมุดไป่ตู้
2.CRC校验常用场合
• 奇偶校验对一个字符校验一次,适合异 步通讯;而CRC对一个数据块(frame) 校验一次,适合同步通讯。在串行同步 通信中,几乎都使用这种校验方法。如 磁盘信息的读/写等。
1.CRC校验基本思想
• CRC校验的基本思想是:
(1)根据欲发的k位信息生成一个r比特的序 列 , 称 为 帧 校 验 序 列 FCS ( Frame checking Series)。
(2)求出实际发送的数据帧(k+r位),这 个帧所对应二进制序列恰好能够被某个预先 确定的数(生成多项式)整除。
相关主题