单位文秘网 2021-10-05 08:27:40 点击: 次
摘 要:循环冗余校验码是一种重要的循环码,编码和解码方法简单,容易实现,检错能力强,误判概率几乎为零,是一种效率极高的差错控制方法,可以满足通信系统可靠传送信息的要求,在测控及数据通信中得到了非常广泛的应用。详细介绍了循环冗余校验的编解码原理,分析了用DSP实现CRC的合理性,最后给出了根据校验原理实现的设计思想及流程图,具有一定的实用价值。
关键词:数据传输系统;循环冗余校验;数字信号处理器;算法分析
中图分类号:TN911.72文献标识码:B
文章编号:1004-373X(2008)07-083-03
DSP Implementation of CRC Algorithm in Data Communication System
HUA Tao1,WU Jin2
(1.System House,Siemens Signal Company Ltd.,Xi′an,710016,China;2.Xi′an University of Posts and Telecommunications,Xi′an,710061,China)
Abstract:Cyclic redundancy check code is a very important cyclic code,the coding and decoding methods are simple,easy to realize.It is strong to detect error,the probability of misjudging is nearly zero.It is a method with extremely high efficiency in controlling errors,which can fulfill the requirement of reliable information transmission in communication systems.It has got very extensive application in observing and controlling and data communication.This paper introduces the encoding and decoding principle of CRC in detail,analyzes the feasibility of CRC by DSP,and gives out the design proposal and flow chart according to the principle,which is very useful in applications.
Keywords:data communication system;cyclic redundancy check;digital signal processor;algorithm analysis
通信的目的是将信息及时可靠地传给对方,因此要求一个通信系统传送信息必须可靠快速。由于传输距离、现场状况、干扰等诸多因素的影响,设备之间的通信数据常会发生一些无法预测的错误。为了降低错误所带来的影响,一般在通信时采用数据校验的办法[1],而循环冗余码校验是常用的重要校验方法之一。CRC校验的检错能力强,在通信领域广泛地用于实现差错控制。数字信号处理器(DSP)是实施高速实时信号处理的专用处理器,目前DSP已成为通信、计算机、消费类电子产品等领域的基础器件,被誉为信息社会革命的旗手。CRC的高效检错能力、DSP的实时处理能力,可以满足通信系统传送信息的两大基本要求:可靠、快速。应用DSP系统来实现CRC,完成数据传输过程中的检错处理,便于集成,使用方便。使用DSP汇编语言,编解码效率高,速度快,实时性好,占用系统资源少。因此CRC校验被广泛使用在各种数据校验应用中。
1 循环冗余校验码
循环冗余校验码(Cyclic Redundancy Check Code,CRC)由线性分组码的分支而来,是一种检错能力很强的循环码。循环冗余校验对传送数据作错误侦测(Error Detecting)是利用除法及余数的原理。编码和解码方法简单,容易实现,检错能力强,误判概率几乎为零,而且这种方法取得校验码的方式具有很强的信息覆盖能力,是一种效率极高的错误校验法。这种高效的差错控制方法,在测控及数据通信中得到了广泛的应用[2]。
1.1 CRC的编码原理
CRC校验采用多项式编码方法,被处理的数据块可以看作是一个n阶的二进制多项式,即an-1 xn-1 + an-2 xx-2 +…+ a1 x + a0 。如一个8位二进制数10110101可以表示为:1x7+0x6+1x5+1x4+0x3+1x2+0x+1=x7+x5+x4+x2+1。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进、借位,和逻辑异或运算一致。
CRC码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),g(x)的首位和最后一位的系数必须均为1,两者相除之后将最后的余数作为CRC校验码。其实现步骤如下:
(1) 设待发送的数据块是m位的二进制多项式t(x),生成多项式为g(x),阶数为r。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为xrt(x)。
(2) 用生成多项式g(x)去除xrt(x),求得余数为二进制多项式y(x),阶数为r-1。这个二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。
(3) 用xrt(x)以模2的方式减去y(x),得到二进制多项式xrt′(x)。xrt′(x)就是包含了CRC校验码的待发送字符串。
1.2 CRC的解码原理
CRC校验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而构成一个总长为n=p+r位的二进制序列,例如,p位二进制数据序列D=[dp-1 dp-2 …d1 d0],r位二进制检验码R=[rr-1 rr-2…r1 r0],所得到的这个n位二进制序列就是M=[dp-1dp-2 …d1d0 rr-1 rr-2…r1 r0];附加在p位二进制数据序列之后的这个r位二进制检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误,这种特定关系就会被破坏。因此,通过检查这一关系,就可以实现对数据正确性的检验。
校验码R是通过对数据序列D进行二进制除法取余式运算得到的,他被一个称为生成多项式的(r+1)位二进制序列G=[gr gr-1…g1 g0]来除,用多项式可以表示为:
[SX(]xrD(x)[]G(x)[SX)]=Q(x)+[SX(]R(x)[]G(x)[SX)]
其中,xrD(x)表示将数据序列D左移r位(即在D的末尾再增加r个0位),Q(x)代表这一除法所得的商,R(x)就是所需的余式。这一运算关系还可以用下式表达:
R(x)=Re[xrD(x)G(x)]
其中,Re[ ]表示对括号内的式子进行取余式运算。
由CRC码的编码过程可知,接收方接收的n位二进制序列M(x)可以看作是D(x)和CRC校验码的组合,去掉M(x)序列的后r位就是发送的原始数据。所以CRC的解码过程则是对接收的前p位二进制数据进行如编码一样的CRC校验,发送方和接收方用同一个生成多项式G(x),将校验得到的r位CRC校验码与接收的M(x)序列的后r位CRC校验码相比较,以两个校验码是否相同为据,判断数据帧是否出错。两者相同,则表示数据帧传输正确;反之,则表示数据传输中出现错误。
CRC编码实际上是将待发送的p位二进制多项式D(x)转换成了可以被G(x)除尽的p+r位二进制多项式M(x)。所以CRC的解码过程也可以通过对M序列直接进行除法取余式运算,即:
M(x)G(x)=Q(x)+R(x)G(x)
所得到的余式R(x)若为零则表示数据传输正确,否则认为在传输过程中发生错误。许多CRC的硬件解码电路就是按这种方式进行检错的。
1.3 CRC的算法分析
以上介绍了CRC校验码的编码和解码原理,很明显,CRC校验过程就是进行除法取余式运算,实际上是一个循环移位的模2逻辑异或运算。这也就是CRC算法要解决的问题。
算法的依据和多项式的除法性质有关[3]。如果一个m位的多项式t(x)除以一个r阶的生成多项式g(x),t(x)=am-1xm-1+am-2xm-2+…+a2x2+a1x1+a0,将每一位akxk(0≤k<m)提出来,在后面补足r个0后,单独去除生成多项式g(x),得到余式位yk(x),则将ym-1(x)⊕ym-2(x)⊕…⊕y0(x)后得到的就是t(x)由生成多项式g(x)得到的余式。
上述算法是依据CRC校验码的产生原理来实现的,即计算法。这种方法代码简单,容易实现,所占用的内存也比较少,而且修改灵活,可移植性好,对任意长度的生成多项式都适用。但是这种以bit为单位对数据进行校验的算法对于发送的数据不长的情况比较适合。如果发送的数据块很长时,逐个bit进行校验,就会占用很多的处理器处理时间,大大降低校验的效率,尤其在高速通讯的场合,这是不允许的,这时可采用一次处理4位、8位、16位等方法,即是常用的按半字节、按字节查表法[4]。
查表法的优缺点与计算法刚好相反,运算速度快,不过这种方法要事先计算出一个参数表,需要占用相当大的内存空间,这就是查表法的缺点。本文不详述这种方法。计算法和查表法各有优缺点,实际应用时,根据应用场合对速度和内存的不同要求,选择最合适的校验方法。
2 CRC的DSP实现
2.1 用DSP实现CRC的设计思想
不同CRC码的生成多项式各不相同,CRC码的比特数也不同,且在有的通信协议中要求将余数寄存器先初始化为全0,另外的则须初始化为全1。因此,在程序设计时必须充分利用CRC码的共性及所用DSP指令具有代码简洁、容易实现、运算速度快等特点。
CRC的编解码用到模2的多项式除法,而多项式除法可以采用带反馈的移位寄存器来实现,因此,用DSP来实现CRC编解码的关键是通过DSP来模拟一个移位寄存器(也就是模拟手写多项式除法)。考虑到TMS320C54x系列DSP的累加器A和B均为40位,因此,可以用一个40位累加器A作为移位寄存器,若CRC码不够40位(设为k位),则仅用到A的最高k位,无用位就用0填充[5]。
在CRC的编码和解码中均涉及到码的移位和异或操作,这可以通过C54x系列的SFTA(算术移位)和XOR(异或)两条指令来实现。C54x系列还提供了特殊指令bitt和xc。bitt指令利用寄存器T,取出一个16位数据中的第(15-T)位,并送入TC(TC是特殊寄存器中的一位)。xc指令是条件执行语句,此指令先判断所列条件是否满足,再决定是否执行其后的2条单周期指令或1条双周期指令。其实现步骤如下:
(1) 先将CRC移位寄存器(即余数寄存器)A的每一位有效位均初始化为全0或全1(与协议有关),而无用位清0;
(2) 将CRC移位寄存器中的值左移一位,判断移出的第一位与输入序列的最高位异或之后是否为1;
(3) 若是1,则将A与生成多项式进行异或再跳到步骤(2)处理下一位;否则,直接跳到步骤(2)继续处理下一位。
在手写多项式除法的过程中可以发现,生成多项式即除式一共为k+1位,而余数寄存器A里仅有k位有效位,这可以视为余数寄存器的k+1位永远为0,因此,在实际的异或运算时,生成多项式的最高位即k+1位不必参与运算。
重复(2)、(3)两步,直到输入信息位全部处理完为止,则A的最高k位为进行多项式除法后所得的余数,若余数寄存器先初始化为全0,则此时A的最高k位就是CRC校验码,若余数寄存器先初始化为全1,则须将A取反后最高k位才是CRC码。
解码时,则是接收方对接收的原始数据进行同样的CRC校验,将得到的CRC码与发送方发送过来的CRC码比较来判断数据传输是否出错。
2.2 CRC流程图
为了实现上节讲述的设计思想,可以在程序中用指针AR2指向输入信息,用AR3指向输入信息字的某一位,用AR4表示够一个字的个数,AR5表示不够一个字的比特数,即:若参加计算的信息比特数为164,则AR4=10,AR5=4。该方法运用比较灵活,用他能够实现任意信息长度的40位以内任意CRC码的编解码。
但在实际的通信应用中,一般以字为单位传输数据。为了依次取出一个字中的bit15,bit14,…,bit0等16位信息位,在程序中可用一个全局变量bitpos,共占16个字,并将这16个地址的内容依次赋值为0,1,2,…,15,而在程序
中这些值不能被改变。为了实现循环长度为16的循环寻址,bitpos的地址必须为32字的整数倍。CRC编解码的流程图如图1所示。
图1 CRC编解码流程图
3 结 语
本文详细介绍了循环冗余校验码的编解码原理,通过反复测试,证明了上述CRC码的编码和解码的设计思想是正确的,能正确实现CRC-4,CRC-8,CRC-12,CRC-16,CCITT,CRC-32等的CRC码的编码和解码。用DSP汇编语言编写程序,具有代码简洁,编解码效率高,运算速度快,实时性好,占用系统资源少等优点[6]。该设计思想也适用于任意40位以内的CRC编码和解码,在其他DSP上也可以很方便地实现,具有一定的实用价值。
参 考 文 献
[1]樊昌信.通信原理[M].北京:国防工业出版社,2001.
[2]申敏,邓矣兵,郑建宏,等.DSP原理及其在移动通信中的应用[M].北京:人民邮电出版社,2001.
[3]周霖.DSP系统设计与实现[M].北京:国防工业出版社,2004.
[4]邹彦.DSP原理及应用[M].北京:电子工业出版社,2005.
[5]朱铭锆,赵勇,甘泉,等.DSP应用系统设计[M].北京:电子工业出版社,2002.
[6]郑红.TMS320C54xDSP应用系统设计[M].北京:北京航空航天大学出版社,2002.
[7]姚七栋,张春玉.CRC校验及其软件实现[J].现代电子技术,2006,29(13):67-68,71.
作者简介 华 涛 男,1976年出生,江西临川人,工学硕士,工程师。主要从事自动检测与控制技术方向的研究。吴 进 女,1975年出生,江苏常州人,工学硕士,讲师。主要从事数字信号处理方向的研究。
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-154-94083-1.html
上一篇:猕猴桃产业演化发展探析
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用