基于只读存储器硬件产生循环冗余校验码

第24卷第4期

2003年12月锦州师范学院学报(自然科学版)JournalofJinzhouNormalCollege(NaturalScienceEdition).24No.4VolDec.2003

基于只读存储器硬件产生循环冗余校验码

尹作友,张志强,王　东

(渤海大学信息科学与工程学院,辽宁锦州121000)

摘　要:介绍了只读存储器在电路设计中的特殊使用,主要介绍采用了只读存储器硬件产生循

环冗余校验码的机制和实现方法。

关键词:只读存储器;循环冗余检验码;查表

中图分类号:TP39　　　文献标识码:A　　　文章编号:10072533X(20067203

1　引言

,,在过程测控仪表中传统的模拟信号传输方、多信息的数据传输,克服了模拟信号传输的瓶颈现象。在数字通信中,、气候及仪表间转接、通信线路质量变差等多方面影响,使传输的数据出现差错现象。为确保数据传输的正确性,对传输的数据进行校验是通信中非常重要的一环。常用的校验方法有奇偶校验、行列奇偶校验、循环冗余校验等,其中检错能力最强的是循环冗余校验(简称CRC校验),适宜在高可靠性要求的通信中使用。实现CRC码的方法很多,可以由软件或硬件实现,用软件来实现CRC校验码,主要缺点是校验时间长,如一字节的数据信息,要循环移位8次,并进行相应的判断和复杂的运算,才能得到一个完整的CRC值,所以速度慢。用硬件实现时速度快,传统的方法用移位寄存器等硬件构成电路实现,亦可采用具有CRC校验功能的大规模集成电路,但成本高。本文采用只读存储器(ROM)实现CRC校验码的方法。2　循环冗余校验码(CRC)

设M(x)是要传送的信息,将其左移K位,得多项式XK・M(x),然后除以生成多项式G(x)(为k+1个

减法采位),则得到商Q(x)及余数R(x)(K个位)。即:XK・M(x)=Q(x)・G(x)+R(x)。在运算过程中加、

用模2运算,规则是无借位及进位,即对应位采用异或运算,则有:xK・M(x)+R(x)=Q(x)・G(x)+R(x)

K+R(x)=Q(x)・G(x)。显然,由于XK・X・M(x)+R(x)称为循环冗余校验码,R(x)冗余校验位。M(x)信

息最后K位都是“0”,R(x)可直接加到其后面形成信息流,而不必破坏M(x)的信息位。CRC校验的这种特殊性质,给信息传输带来很大方便,收方只要将收到的信息序列编码除以G(x)多项式,若余数为0,则可认为传输无差错。所得到的M+K位信息流中,前M位是传输的有用数据信息,后K位则是CRC的冗余校验位,不同的信息,形成的循环冗余校验码(CRC)是不同的。

3　CRC码的ROM实现原理

CRC生成多项式G(x)是通信时双方预先约定的,能够对信息在传输过程中任何一位出错进行校验,对4位二进制信息码,根据生成多项式形成的条件,其表达式为G(x)=X3+X2+1,按CRC校验原理,一个4位M(X)信息,有一个3位二进制数的CRC位相对应,而一个4位信息M(x)可以为00H、01H、…、0FH

收稿日期:2003-06-23

作者简介:尹作友(19652),男,副教授,从事计算机应用教学科研工作.

68锦州师范学院学报(自然科学版)第24卷中的任何一个,所以应有16个的CRC码,即生成了一个16个信息的CRC码参数表,相当于查表得到,如表所示。

　　只读存储器在正常工作时,只能读取存储器中数据,不能把数据写入存储器,为了实现上述4位信息的转换,可采用1634位的ROM,即有4根地址线,4根数据线(实用3根),4根地址线构成16个存储单元。转换前,预先用写入器把每个4位M(X)的CRC位先写到ROM中去,每个4位的M(X)信息编码作为存储单元的地址,对应的单元写入信息所对应的CRC位。在只读存储器正常工作时,把要转换的M(X)信息,直接送给ROM前面地址锁存器的输入端,同时也送到一个数据寄存器的输入端,微处理器发出一个信号给地址锁存器,地址锁存器的输出送到只读存储器的地址输入端,ROM的数据线输出的信息就是信息M(X)所对应的CRC位,即如果来自前端数据总线的信息M(X)为1110,通过地址锁存器送到只读存储器后,只读存储器的输出为010,送到数据锁存器U2,最后微处理器给数据锁存器U1和U2一个信号,使两个数据锁存器同时输出到后面数据总线输出到其它微处理器,硬件框图如图1所示。

对于8位二进制信息码,

常用的是国际电报电话咨询委

员会推荐的CRC-CCITT,其

表达式为G(x)=X16+X15+

2X+1,按CRC字节信息,有一个数(两个字节)的位相对

应,而一个字节信息M(x)可

以为00H、01H、…、0FFH中的

任何一个,所以应有256个双

字节的CRC位,即生成了一个

512字节的CRC参数表。采用图1

的ROM可用256316位的只读存储器,每个元存放16位二进制数,电路实现同上,只是增加了存储器的单元数和每个单元的位数,容量增加。

对于多字节CRC校验码,如果同上述的方法实现,所需的ROM存储单元的数多,要求ROM的存储量大,为了减少ROM的容量,多字节的CRC码可由单字节CRC值经过特定算法来实现。设M(x)为n字节信息,由CRC校验原理可知:

816=Q(X)+=Q(X)+G(X)G(X)G(X)

当M(x)增加一个字节时,Mn+1(x)=x8・Mn(x)+M0(x),则有:

[1**********]8()=+=XQnX+X+G(X)G(X)G(X)G(X)G(X)

8888168=XQn(X)+X+=XQn(X)+q(x)++G(X)G(X)G(X)G(X)

8(X)+=Q′G(X)

以上推理可知,当已知n字节信息的CRC值,求取n+1字节信息的CRC位时,首先由增加的字节异或原CRC的高8位[rnH(x)+rnl(x)],形成一新的字节,求取该字节的CRC位,再与原CRC低8位相异或,便可求得信息的CRC位。这说明,如果能求得单字信息的CRC位,可求取多字节信息的CRC位。而单字节CRC位的求取方法,一种是采用上面所述的直接查表法得到,即将信息以字节为单位划分,由节字值由CRC参数表中查出相应的CRC校验位。设原信息CRC校验值位表示为Rn(x)=X8CRCH+CRCL,CRCH、CRCL分别

　第4期尹作友,张志强,王东:基于只读存储器硬件产生循环冗余校验码69表示CRL检验位的高8位、低8位。另一种方法是双字段CRC查表法,字节M(X)可由多项式表示为M(x)=a7x7+a6x6+a5x5+a4x4+a3x3+a2x2+a1x1+a0,设MH(x)=a7x7+a6x6+a5x5+a4x4,ML(x)=a3x3+a2x2+a1x1+a0则M(x)=MH(x)+ML(x)。即一个字节M(x)可按其高4位和低4位形成的两个字段异或而成。采用分段查表法,可以大大减少ROM的容量,在电路实现上,只要对信息M(X)高4位和低4位分别由不同的ROM查表电路得到CRC值,CRC校验原理可知,字节M(x)的CRC校验位可由下式算出:

16161616==+=RH(X)+RL(X)同样对于多字节的G(X)G(X)G(X)G(X)

CRC位,也可以分成多个,分别通过各自的ROM查表电路,取得CRC位,然后组合在一起,求得总的CRC位。

4　结束语

在实现CRC码时,采用的ROM可以由PROM、EPROM、EEPROM、GAL、EPLD、FPGA等可编辑器件担任,特别是采用FPGA器件担任时,除了速度快以外,相应的其它电路如锁存器、寄存器也可以由FP2

函数发生GA器件担任,这样可大大减少成本,增加电路的可靠性。使用ROM、

器等功能。

参考文献:

[1]王爱英.计算机组成与结构[M].北京:,.

[2]张端.数字电路与逻辑设计[M].:,CylicBasedonRead-onlyMemoryHardware

YIN　Zuo2you,ZHANG　Zhi2giang,WANG　Dong

(BoHaiUinvorsity,Jinzhou121000,china)

Abstract:Thistextintroducesthespecialusageforread-onlymemoryintheelectriccircuitdesigningItismainlyaboutthemethodmechanismforread-onlymemorythehardwareproducingcirculatingre2dundancycheckcode.

Keywords:read-onlymemory;cyclicredundancycheckcode;checktable

第24卷第4期

2003年12月锦州师范学院学报(自然科学版)JournalofJinzhouNormalCollege(NaturalScienceEdition).24No.4VolDec.2003

基于只读存储器硬件产生循环冗余校验码

尹作友,张志强,王　东

(渤海大学信息科学与工程学院,辽宁锦州121000)

摘　要:介绍了只读存储器在电路设计中的特殊使用,主要介绍采用了只读存储器硬件产生循

环冗余校验码的机制和实现方法。

关键词:只读存储器;循环冗余检验码;查表

中图分类号:TP39　　　文献标识码:A　　　文章编号:10072533X(20067203

1　引言

,,在过程测控仪表中传统的模拟信号传输方、多信息的数据传输,克服了模拟信号传输的瓶颈现象。在数字通信中,、气候及仪表间转接、通信线路质量变差等多方面影响,使传输的数据出现差错现象。为确保数据传输的正确性,对传输的数据进行校验是通信中非常重要的一环。常用的校验方法有奇偶校验、行列奇偶校验、循环冗余校验等,其中检错能力最强的是循环冗余校验(简称CRC校验),适宜在高可靠性要求的通信中使用。实现CRC码的方法很多,可以由软件或硬件实现,用软件来实现CRC校验码,主要缺点是校验时间长,如一字节的数据信息,要循环移位8次,并进行相应的判断和复杂的运算,才能得到一个完整的CRC值,所以速度慢。用硬件实现时速度快,传统的方法用移位寄存器等硬件构成电路实现,亦可采用具有CRC校验功能的大规模集成电路,但成本高。本文采用只读存储器(ROM)实现CRC校验码的方法。2　循环冗余校验码(CRC)

设M(x)是要传送的信息,将其左移K位,得多项式XK・M(x),然后除以生成多项式G(x)(为k+1个

减法采位),则得到商Q(x)及余数R(x)(K个位)。即:XK・M(x)=Q(x)・G(x)+R(x)。在运算过程中加、

用模2运算,规则是无借位及进位,即对应位采用异或运算,则有:xK・M(x)+R(x)=Q(x)・G(x)+R(x)

K+R(x)=Q(x)・G(x)。显然,由于XK・X・M(x)+R(x)称为循环冗余校验码,R(x)冗余校验位。M(x)信

息最后K位都是“0”,R(x)可直接加到其后面形成信息流,而不必破坏M(x)的信息位。CRC校验的这种特殊性质,给信息传输带来很大方便,收方只要将收到的信息序列编码除以G(x)多项式,若余数为0,则可认为传输无差错。所得到的M+K位信息流中,前M位是传输的有用数据信息,后K位则是CRC的冗余校验位,不同的信息,形成的循环冗余校验码(CRC)是不同的。

3　CRC码的ROM实现原理

CRC生成多项式G(x)是通信时双方预先约定的,能够对信息在传输过程中任何一位出错进行校验,对4位二进制信息码,根据生成多项式形成的条件,其表达式为G(x)=X3+X2+1,按CRC校验原理,一个4位M(X)信息,有一个3位二进制数的CRC位相对应,而一个4位信息M(x)可以为00H、01H、…、0FH

收稿日期:2003-06-23

作者简介:尹作友(19652),男,副教授,从事计算机应用教学科研工作.

68锦州师范学院学报(自然科学版)第24卷中的任何一个,所以应有16个的CRC码,即生成了一个16个信息的CRC码参数表,相当于查表得到,如表所示。

　　只读存储器在正常工作时,只能读取存储器中数据,不能把数据写入存储器,为了实现上述4位信息的转换,可采用1634位的ROM,即有4根地址线,4根数据线(实用3根),4根地址线构成16个存储单元。转换前,预先用写入器把每个4位M(X)的CRC位先写到ROM中去,每个4位的M(X)信息编码作为存储单元的地址,对应的单元写入信息所对应的CRC位。在只读存储器正常工作时,把要转换的M(X)信息,直接送给ROM前面地址锁存器的输入端,同时也送到一个数据寄存器的输入端,微处理器发出一个信号给地址锁存器,地址锁存器的输出送到只读存储器的地址输入端,ROM的数据线输出的信息就是信息M(X)所对应的CRC位,即如果来自前端数据总线的信息M(X)为1110,通过地址锁存器送到只读存储器后,只读存储器的输出为010,送到数据锁存器U2,最后微处理器给数据锁存器U1和U2一个信号,使两个数据锁存器同时输出到后面数据总线输出到其它微处理器,硬件框图如图1所示。

对于8位二进制信息码,

常用的是国际电报电话咨询委

员会推荐的CRC-CCITT,其

表达式为G(x)=X16+X15+

2X+1,按CRC字节信息,有一个数(两个字节)的位相对

应,而一个字节信息M(x)可

以为00H、01H、…、0FFH中的

任何一个,所以应有256个双

字节的CRC位,即生成了一个

512字节的CRC参数表。采用图1

的ROM可用256316位的只读存储器,每个元存放16位二进制数,电路实现同上,只是增加了存储器的单元数和每个单元的位数,容量增加。

对于多字节CRC校验码,如果同上述的方法实现,所需的ROM存储单元的数多,要求ROM的存储量大,为了减少ROM的容量,多字节的CRC码可由单字节CRC值经过特定算法来实现。设M(x)为n字节信息,由CRC校验原理可知:

816=Q(X)+=Q(X)+G(X)G(X)G(X)

当M(x)增加一个字节时,Mn+1(x)=x8・Mn(x)+M0(x),则有:

[1**********]8()=+=XQnX+X+G(X)G(X)G(X)G(X)G(X)

8888168=XQn(X)+X+=XQn(X)+q(x)++G(X)G(X)G(X)G(X)

8(X)+=Q′G(X)

以上推理可知,当已知n字节信息的CRC值,求取n+1字节信息的CRC位时,首先由增加的字节异或原CRC的高8位[rnH(x)+rnl(x)],形成一新的字节,求取该字节的CRC位,再与原CRC低8位相异或,便可求得信息的CRC位。这说明,如果能求得单字信息的CRC位,可求取多字节信息的CRC位。而单字节CRC位的求取方法,一种是采用上面所述的直接查表法得到,即将信息以字节为单位划分,由节字值由CRC参数表中查出相应的CRC校验位。设原信息CRC校验值位表示为Rn(x)=X8CRCH+CRCL,CRCH、CRCL分别

　第4期尹作友,张志强,王东:基于只读存储器硬件产生循环冗余校验码69表示CRL检验位的高8位、低8位。另一种方法是双字段CRC查表法,字节M(X)可由多项式表示为M(x)=a7x7+a6x6+a5x5+a4x4+a3x3+a2x2+a1x1+a0,设MH(x)=a7x7+a6x6+a5x5+a4x4,ML(x)=a3x3+a2x2+a1x1+a0则M(x)=MH(x)+ML(x)。即一个字节M(x)可按其高4位和低4位形成的两个字段异或而成。采用分段查表法,可以大大减少ROM的容量,在电路实现上,只要对信息M(X)高4位和低4位分别由不同的ROM查表电路得到CRC值,CRC校验原理可知,字节M(x)的CRC校验位可由下式算出:

16161616==+=RH(X)+RL(X)同样对于多字节的G(X)G(X)G(X)G(X)

CRC位,也可以分成多个,分别通过各自的ROM查表电路,取得CRC位,然后组合在一起,求得总的CRC位。

4　结束语

在实现CRC码时,采用的ROM可以由PROM、EPROM、EEPROM、GAL、EPLD、FPGA等可编辑器件担任,特别是采用FPGA器件担任时,除了速度快以外,相应的其它电路如锁存器、寄存器也可以由FP2

函数发生GA器件担任,这样可大大减少成本,增加电路的可靠性。使用ROM、

器等功能。

参考文献:

[1]王爱英.计算机组成与结构[M].北京:,.

[2]张端.数字电路与逻辑设计[M].:,CylicBasedonRead-onlyMemoryHardware

YIN　Zuo2you,ZHANG　Zhi2giang,WANG　Dong

(BoHaiUinvorsity,Jinzhou121000,china)

Abstract:Thistextintroducesthespecialusageforread-onlymemoryintheelectriccircuitdesigningItismainlyaboutthemethodmechanismforread-onlymemorythehardwareproducingcirculatingre2dundancycheckcode.

Keywords:read-onlymemory;cyclicredundancycheckcode;checktable