循环冗余码校验（精选3篇）
循环冗余码校验 篇1
引言
随着网络技术的发展, 通信在质量、速度、成本等领域都面临着新挑战。许多学者进行深入研究并提出了各种改善措施。其中, 循环冗余校验码 (Cyclical Redundancy Check, 简称为CRC) 作为一种特色编码对通信性能改进有举足轻重的作用。它具有严谨的代数结构, 其性能易于分析;循环结构特性, 编解码电路简单易于实现。特别是CRC系统码, 在编码电路上更能简化电路结构。CRC码在串行通信中有着得天独厚的优势, 电路成本较低;但是它的速度完全依赖于时钟频率的提高, 对于速度要求较高的场合, 特别是实时的通信, 时钟频率成为颈瓶[1]。为了提高速度, 并行算法相继出现:查表法[2]能一次处理一个字节或半个字节来生成CRC校验码, 但它需要预先计算512个字节或32个字节的查找表, 实际上码表会随着信息位数的增加以指数增加, 极大地降低其现实可行性。在深入分析系统CRC码的特点后得出一种并行编码实现方法。
1 CRC系统码的一般原理
CRC系统码是利用次数为n-k的生成多项式g (x) 为k位数据生成r个校验位, 在数据传送时将r个校验位附加在数据位的后面构成n位的数据, 接收方通过接收到的数据位和检验位进行验证, 判断数据位在传送过程中是否发生变化[3]。原理相当于
式中
分别为码字多项式、信息多项式及校验多项式及分别为码字、信息位及校验位。由 (1) 式容易得到
在二进制中, 逆元就是本身, 于是
因此, 结合二进制的除法性质, 用g (x) 除m (x) ⋅xn-k便可得到校验多项式r (x) 。
2 并行算法的校验码的逻辑关系推导
由CRC系统码的生成矩阵得到的码字结构上与 (1) 式相同:明显的分组码结构, 即前k位是信息位, 后r位是校验位。这有利于在解码部分快速提取信息位。系统码的生成矩阵G形式为:
该G矩阵的特殊性还在于每一行矢量都是该CRC系统码的码字, 基于此, 在同时要满足 (3) 与 (4) 的条件下, 唯有信息组基底 (1 0 0 0 0 0 0 0) , (01000000) , …, (00000001) 生成的互相独立的k个码字按照一定的顺序排列才能构造成有如 (4) 式结构的矩阵。所以将对应的信息多项式:mk-1 (x) =xk-1, mk-2 (x) =xk-2, …, 0m (x) =1, 分别乘以xn-k, 然后用g (x) 除就得到各自的余式, 再按照G的结构排列便得生成矩阵。
采用CRC-CCITT (16位) (国际电报电话咨询委员会推荐) 标准可捕捉一位或两位错;具有奇数个错的全部错误;所有低于16位的突发性错误, 长度为17的突发性错的99.998%, 长度18以上的突发性错误的99.997%[4]。CRC-CCITT的G矩阵通过式 (3) 得出:
假设待发送的信息组, 其生成的码字为, 由于生成矩阵G、信息组m&与任一码字c&都有这样的关系:c&=m&·G。于是便能得到基于该生成矩阵的各校验位与信息位的逻辑关系, 如表1所示。
对应不同的生成多项式, 生成矩阵也不尽相同;但只要计算出CRC系统码的生成矩阵便能得到与表1相似的逻辑关系表。
3 编码器的FPGA实现
CRC解码与编码的原理是相通的, 编码是对输入数据进行CRC编码, 解码是验证判断接收到的CRC编码是否正确, 计算采用的方式是相同的;只是解码部分要判断信息是否正确并且根据判断结果提取正确信息, 纠正或抛弃有误的信息[5]。所以并行处理应用在这两个模块中, 能大大提高通信的速度。并行处理方式是每次输入一组数据, 且在一个时钟内计算得出CRC结果。这种方式是要确定数据的位数, 在本文中, 采用VHDL (Very high speed integrated Circuit Hardware Description Language) 设计一个 (24, 8) 编码器, 利用FPGA (Field Programmable Gate Array, 即现场可编程门阵列) 技术进行仿真。表2是此设计的端口说明。
VHDL语言的主要代码:
对所设计的编码器进行时序仿真, 便得到如图1所示的波形图。
从图1可以看出, 16位的CRC码在数据输入当个周期内就能得到, 延迟时间与时钟周期之比远小于1%, 与传统硬件电路LFSR相比, 尽管串行电路的速度很高, 但每次只能处理一位数据, 本文的算法在时间上是绝对的占优势。而且本文的方法仅仅占用11个logic elements资源, 消耗的资源与串行方法相当。仿真是在QuartusⅡ6.1平台上, 所选用的器件为Strati系列。
4 结束语
从分析CRC码的特点出发, 提出了并行计算的方法对CRC—CCITT校验码进行了设计, 这种方法在8位数据并行输人大大提高了运行速度, 并且在数据输入的当前周期内就可以得到CRC校验码的结果。从综合的结果也可以看出, 这种方式具有逻辑简单, 速度更快, 占用资源更少的优点, 可以很方便地在FPGA中实现。
参考文献
[1]Braun, F., Waldvogel, M..Fast Incremental CRC Updates for IP over ATM Networks.High Performance Switching and Routing, 2001IEEE Workshop on.29-31May2001.p48–52.
[2]张莉丽, 张振权, 刘仁.CRC查表生成算法汇编的实现及其优化.计算机应用, 石油化工自动化, 2005, 第4期.
[3]王新梅, 肖国镇.纠错码一原理与方法[M].西安:西安电子科技大学出版社, 2001.
[4]程立辉, 黄贻彬, 付金华, 徐洁.CRC算法在计算机网络通信中的漏检分析.河南科学, 2007.6, 第25卷第3期.
[5]张树刚, 张遂南, 黄士坦.CRC校验码并行计算的FPGA实现.计算机技术与发展, 2007.2, 第17卷第2期.
循环冗余码校验 篇2
在数据通信和计算机通信过程中,由于信道上各种噪声和干扰等复杂因素的影响,使接收端收到的信息与发送端发送的信息不一致,即接收端收到的信息产生了误码。用误码率(PC)来度量信道传输信息的准确度,即
PC=错误接收码元数/接收码元数。
为了尽可能地降低通信的误码率,提高数字通信的可靠性,往往要采用差错控制编码(又叫信道编码)。用差错控制编码可以发现可能产生的误码(检错码),或发现并纠正错码(纠错码)。
差错控制的目的是提高通信的可靠性。差错控制最常用的方法有三种:自动请求重发方式(ARQ)、向前纠错方式(F E C)和混合纠错方式(H E C)。其中FEC和HEC是基于纠错编码,而A R Q是基于检错编码。
FEC依赖于在发送码字中有控制地加入冗余信息。信号在噪声信道中进行传输时会产生误码现象,从而需要进行误码检测和纠正。不管接收码字的译码是否成功,接收机都不进行任何进一步处理。因此,使用于FEC的信道编码技术只要求发射机和接收机之间是单向的链接。
A R Q的基本思想完全不同于F E C。ARQ采用冗余的目的仅仅是为了进行误码检测。当在传输的码字中检测到错误时,接收机就要求重传错误的码字,这就需要使用一条返回路径(反馈信道)。因此,ARQ只能用于半双工或全双工的链路。实现检错功能的差错控制方法有很多,常用的有:奇偶校验、校验和检测、重复码检验、横比码校验、行列冗余码校验等。
HE C是F E C和AR Q的结合。
为了不破坏数据的完整性,差错控制借助于前向纠错FEC的方法来实现。图1给出了采用这种方法的数字通信系统模型。离散信源产生二进制的信息,发射几种的信道编码器收到比特信息后,按照指定的规则加上冗余发送到接收端。接收机中的译码器对收到的数据进行误码检测和纠错。
循环冗余校验CRC是由分组线性码的分支而来,其主要应用是二元码组。由于检错能力强,误判概率很低等优点,被广泛应用于工业测控和数据通信领域。下面重点介绍CRC校验的原理、算法分析,及其C++源程序设计。
2 CRC算法原理
C R C码是一种线性、分组的系统码。在K位信息码之后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。CRC校验采用多项式编码方法,被处理的n比特的数据块可以看作是一个n-1阶的二进制多项式。例如一个8比特的二进制数10111001可以表示为:x7+x5+x4+x3+1。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进、借位,和逻辑异或运算一致。
模2除步骤如下:
1)用除数对被除数最高几位做模2减,没有借位。
2)除数右移一位,若余数最高位为1,商为1,并对余数做模2减。若余数最高位为0,商为0,除数继续右移一位。
3)一直做到余数的位数小于除数时,该余数就是最终余数。
对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(X)。根据G(X)可以生成K为信息的校验码,而G(X)叫做这个CRC码的生成多项式。
假设待发送的K位信息多项式用C(X)表示,将C(X)左移R位,则可表示为C(X)*2R,这样C(X)的右边就会空出R位,这就是校验码的位置。通过C(X)*2R除以生成多项式G(X)得到的余数就是校验码。Q(X)为商,R(X)为余数。即
在发送端发送信息时,将校验码R(X)加到信息码C(X)之后一同发出。并将这时发出的信息称为T(X)码,其码元形式如下。T(X)正好能被G(X)整除。
接收方收到信息码为T’(X)。如果传输中未发生错误,则接收码T’(X)与发送码T(X)相同,故能被G(X)整除;如果传输中发生错误,则接收码T’(X)与发送码T(X)不相同,且不能被G(X)整除。因此,我们就以T’(X)除以G(X)的余数是否为0来判断接收码元中是否有错误。也有可能收到的错误码元除以G(X)余数为0,这种问题是CRC所不能解决的,只能通过选择G(X)和增加冗余位来降低这种错误的概率。
3 CRC算法分析
C RC码是用待发送的二进制数据C(X)左移R位,然后除以生成多项式G(X),得到的余数就是CRC码。CRC码的具体生成步骤如下:
1)将x的最高幂次为R的生成多项式G(X)转换成对应的R+1位二进制数。
2)将待发送的二进制数据C(X)左移R位,相当于对应的信息多项式C(X)*2R。
3)用生成多项式(二进制数)对信息码做模2除,得到R位的余数R(X)。
4)将余数拼接到信息码左移后空出的位置,得到完整的C R C码。
例如,假设使用的生成多项式是G(X)=x3+x+1,4位的原始报文为1 0 1 0,求编码后的报文。
解的过程如下:
1)将生成多项式G(X)=x3+x+1转换成对应的二进制数1011.
2)生成多项式有4位,要把原始报文C(X)左移3位变为1010000.
3)用生成多项式对应的二进制数对左移3位后的原始报文进行模2除。
4)得到余数0 1 1,即校验码。
5)编码后的报文(C R C码)为1010011
通过CRC编码规则可以看出,CRC编码实际上是将待发送的K位二进制数据C(X)转换成了可以被生成多项式G(X)除尽的K+R位的二进制多项式C(X)*2R,所以,解码时,可以用接收到的数据除以G(X),如果余数为0,则表示传输过程没错误,如果余数不为0,则表示传输过程肯定存在错误。解码时,将接收到的二进制数据去掉尾部的R位数据,得到的就是原始的二进制数据信息。
4 CRC算法性能分析
生成多项式的选取会影响检错纠错的性能。生成多项式应该满足下列要求:任何一位发生错误都应使余数不为0;不同位发生错误应当使余数不同;应满足余数循环规律。
生成多项式的幂次越高,其检错能力越强。若生成多项式G(X)的最高幂次为R,则该C R C校验码的检错性能如下:
1)可检测出所有奇数个错误。
2)可检测出所有单个突发错误。
3)可检测出所有两个错误。
4)可检测出所有长度小于等于R个比特的突发错误。
5)对于长度等于R+1个比特的突发错误,其漏检率仅为1/2 r-1。
6)对于长度大于等于R+1个比特的突发错误,其漏检率仅为1/2r。
CRC码具有良好的检错能力,因而在工业测控和数据通信领域得到了广泛的应用。下面是已经成为国际标准的CRC码生成多项式:
CRC—16为美国采用,而CRC—CCITT为欧洲国家所采用,CRC—32大都被采用在一种
称为Point-to-Point的同步传输中。在实际应用,可根据需要来选用相应的生成多项式。
5 结束语
CRC校验由于实现简单,纠错能力强,被广泛应用于各种数据校验场合及工业测控领域。本文阐述了CRC的校验原理及算法性能分析,并给出了用C++实现的CRC-14源程序,已在PC机上验证通过。并且中科院国家授时中心“BPL长波授时系统现代化改造项目”中,用到了CRC编码技术。用软件实现的CRC不仅可以降低成本,还可广泛应用于微机及各种数据通信领域,为系统长期稳定运行提供了可靠保障。
摘要：在数据通信与网络中,为了尽可能地降低通信的误码率,提高数字通信的可靠性,可以采用一种循环冗余校验码CRC(Cyclic Redundancy Check),简称循环码或CRC码。由于它是一种编码简单,且高效、可靠的差错控制方法,检错能力强,误码概率低,因而被广泛应用于工业测控及数据通信领域。本文阐述用循环冗余校验CRC进行差错控制的原理,CRC算法分析及CRC算法的C++程序设计方法。
关键词：循环冗余校验,CRC算法,差错控制
参考文献
[1]李永忠,苏惠娟.CRC在数据通信中的应用及软件实现.西北民族学院学报.1998.19(1)
[2]李寿强.循环冗余校验CRC的算法分析及其实现方法.成都电子机械高等专科学校学报.2003年第4期
[3]瞿中告,袁威,徐问之.CRC算法在计算机网络通信中的应用.微机发展.2002年第2期
循环冗余码校验 篇3
关键词：循环冗余校验,CRC编解码,实验系统
一、引言
随着人们对数据业务的需求越来越多,数据通信在近来得到了长足的发展。但是由于通信信道传输特性的不理想和加性噪声的影响,设备之间的数据通信常会发生一些无法预测的错误,为确保高效而无差错的传输数据,降低错误而带来的影响,必须对数据进行差错检测及控制。在诸多检错手段中,循环冗余检测方法(CRC)是非常有效的一种方法。CRC是对传送数据进行校验的特点是:检错能力极强,开销小,易于编程。从其检错能力来看,它所不能发现错误的几率达0.0047﹪以下,从其性能及开销上均远远优于奇偶校验以及算术和检错等方式。因而,在数据存储和数据通信领域,CRC无处不在。
FPGA是在PAL、GAL、PLD等可编程器件的基础上进一步发展的产物,采用了逻辑单元阵列这样一个新概念,内部包括可配置逻辑模块CLB、输出输入模块IOB和内部连线三个部分。用户可对FPGA内部的逻辑模块和I/O模块重新配置,以实现用户的逻辑。它还具有静态可重复编程和动态在系统重构的特性,使得硬件的功能可以像软件一样通过编程来修改。FPGA如同一张白纸或是一堆积木,工程师可以通过传统的原理图输入法,或是硬件描述语言自的设计一个数字系统。通过软件仿真,我们可以事先验证设计的正确性。因此,FPGA的使用非常灵活。利用FPGA实现CRC校验是一个高效的切实可行的方法。
在教学过程中,我们尝试利用现有的EDA实验箱设备,设计实现小型的CRC校验系统,拓展设备的功能,提高设备使用效率。
二、系统总体设计
循环冗余校验CRC是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。它的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。
校验码的具体生成过程为:假设发送信息用信息多项式C(X)表示,将C(x)左移R位,则可表示成C(x)*2R,这样C(x)的右边就会空出R位,这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。
生成多项式是接受方和发送方的一个约定,也就是一个二进制数,在整个传输过程中,这个数始终保持不变。在发送方,利用生成多项式对信息多项式做模2除(异或运算)生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除(异或运算)检测,当被传送信息(CRC码)任何一位发生错误时,被生成多项式做模2除(异或运算)后应该使余数不为0。
基于这样的原理,利用FPGA实现的小型的循环冗余校验实验系统可以由五个部分组成:数据输入电路、CRC编码处理电路、CRC解码处理电路、时钟电路、显示电路。作为CRC校验的输入部分,本设计采用通用的数字机械式键盘。本系统显示信息电路采用共阴极8位7段数码管显示码值,使用3-8译码器译码。CRC校验结果提示电路用LED灯显示,方便、简洁。时钟电路使用可调数字信号源产生时钟。编解码处理电路使用FPGA适配器。发送端首先将数据写入设计好的FIFO存储器,然后依次地调出数据进行编码,然后将生成的CRC码发送出去,并给以接收端一个接收信号;接收端收到信号后,开始对接收到的数据进行解码,并将解码信息反馈给发送方。当解码正确时,发送方继续发送下一个数据,当解码错误时,发送方把刚发的数据重新调出,进行编码,发送出去。系统原理图见图1。
三、系统具体设计
1、CRC编解码的设计
本系统最主要的部分是CRC编解码的设计。
首先来讨论编码的设计。本文设计完成12位信息位加5位CRC校验位的通信系统的发送和接收,CRC模块的端口的数据定义如下:
设计的总体思路:首先装载信息位12位数据,取出其中的高6位与生成多项式系数作异或运算,得到的结果取其低5位与原来信息码的低6位并置并在其后补上一个"0",补足12位,再与生成多项式做同样的异或运算,连续作7次这样的运算,最后得到的异或结果就是CRC校验位。这样通过巧妙的移位运算实现多项式的相除运算。
部分程序代码的实现如下:
解码部分的设计与编码部分类似,不过更加简单,只需要将接收的CRC码直接与发端相同的生成多项式相除,除尽表示没有出现传输差错,直接去掉校验位,就可以得到信息码了。关键的部分代码如下:
2、其他部分的设计
(1)数据输入电路部分:将其设计成为一个FIFO的数据缓存器,这样做的目的,可以接收源源不断传来的数据,另一方面考虑到可能传输出现差错,可以从缓存将数据调出来重新传输一遍,直到正确传输为止,才删去数据。
(2)显示电路部分:输入数据与输出数据都可以采用数码管来进行显示,通过数码管显示可以清楚地观察到传输过程中数据传输的准确性。传输过程出现的差错可以由接收端反馈,在发送端可以用LED灯进行提示。
(3)按键消抖电路部分:由于设计采用开关是机械开关结构,因此在开关切换的瞬间会在接触点出现信号来回弹跳的现象.基于VHDL的按键消抖法主要有三种:电平检测消抖法、定时检测消抖法以及脉宽检测消抖法。本系统采用定时检测消抖法可以进行按键的消抖。
至于时钟电路,对于数码显示电路而言,需要额外提供一个较高频率的扫描电路,其他的时钟可以用普通的时钟提供。
实验系统的实物图如下:
四、结束语