原创 CRC码的FPGA实现之一CRC的原理

2011-8-31 10:24 5669 0 1 分类: FPGA/CPLD

                       CRC码的FPGA实现之一CRC的原理

1.实验目的

学习用FPGA设计一个数据通信中常用的数据检错模块——循环冗余检验CRC模块,熟悉理解CRC的检错原理。

2.实验设备

硬件:SmartSOPC教学实验开发平台

软件:Quartus II9.1

3.实验内容

 

4.实验原理

循环冗余检验(CRC)算法原理

(一)基本原理

循环冗余检验(Cyclic Redundancy Check),是一种纠错能力很强,使用非常广泛的数据传输差错检错方法,是在串行通信中广泛采用的检验编码。CRC校验码的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC码)r位,并附在信息后边,构成一个新的二进制码序列数共(k+ r)位,最后发送出去。在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。接收端有两种处理方法:1、计算k位序列的CRC码,与接收到的CRC比较,一致则接收正确。2.计算整个k+r位的CRC码,若为0,则ILY: 宋体">  模2运算是一种二进制算法,CRC校验技术中的核心部分。与四则运算相同,模2运算也包括模2加、模2减、模2乘、模2除四种二进制运算。而且,模2运算也使用与四则运算相同的运算符,即“+”表示模2加,“-”表示模2减,“×”或“·”表示模2乘,“÷”或“/”表示模2除。与四则运算不同的是模2运算不考虑进位和借位,即模2加法是不带进位的二进制加法运算,模2减法是不带借位的二进制减法运算。这样,两个二进制位相运算时,这两个位的值就能确定运算结果,不受前一次运算的影响,也不对下一次造成影响。

  ①模2加法运算定义为:
000        0+1=1        1+0=1        1+1=0
例如0101+0011=0110,列竖式计算:
   0 1 0 1
0 0 1 1
────
   0 1 1 0


  ②模2减法运算定义为:
0-0=0        0-1=1        1-0=1        1-1=0
例如0110-0011=0101,列竖式计算:
   0 1 1 0
  0 0 1 1
────
   0 1 0 1

  ③模2乘法运算定义为:
0×0=0        0×1=0        1×0=0        1×1=1
多位二进制模2乘法类似于普通意义上的多位二进制乘法,不同之处在于后者累加中间结果(或称部分积)时采用带进位的加法,而模2乘法对中间结果的处理方式采用的是模2加法。例如1011×101=100111,列竖式计算:
       1 0 1 1
    
×  1 0 1
    
──
            1 0 1 1
     0 0 0 0
1 0 1 1
────
   1 0 0 1 1 1
  ④模2除法运算定义为:
0÷1=0        1÷1=1
多位二进制模2除法也类似于普通意义上的多位二进制除法,但是在如何确定商的问题上两者采用不同的规则。后者按带借位的二进制减法,根据余数减除数够减与否确定商1还是商0,若够减则商1,否则商0。多位模2除法采用模2减法,不带借位的二进制减法,因此考虑余数够减除数与否是没有意义的。实际上,在CRC运算中,总能保证除数的首位为1,则模2除法运算的商是由余数首位与除数首位的模2除法运算结果确定。因为除数首位总是1,按照模2除法运算法则,那么余数首位是1就商1,是0就商0。例如1100100÷1011=1110……110,列竖式计算:
               1 1 1 0
       ────
1 0 1 1〕1 1 0 0 1 0 0
     
1 0 1 1
      ────
           1 1 1 1
        - 1 0 1 1
       ────
             1 0 0 0
          - 1 0 1 1
         ──
               0 1 1 0
            - 0 0 0 0
           ──
                 1 1 0
3、信息代码多项式:在纠错编码代数中,把以二进制数字表示的一个数据系列堪称一个多项式。例如,二进制序列1010111,用多项式可以表示成:
         M(x)=x6+x4+x2+x+1
M(x)称为信息代码多项式。
4、生成多项式(generator polynomial):当进行CRC检验时,发送方与接收方需要事先约定一个除数,即生成多项式,一般记作G(x)。生成多项式的最高位与最低位必须是1。
   几种标准的CRC码生成多项式
 CRC码  生成多项式G(x)
 CRC-4 x4+x+1
 CRC-5 x5+x4+x2+1
 CRC-8 x8+x5+x4+1
 CRC-9 x9+x6+x5+x4+x3+1
 CRC-12 x12+x11+x3+x2+x+1
 CRC-16 x16+x15+x2+1
 CRC-CCITT x16+x12+x5+1
 CRC-32 x32+x26+x23+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
每一个生成多项式都可以与一个代码相对应,如CRC8对应代码:100110001。其中CRC-12、CRC-16、CRC-CCITT 、CRC-32为国际标准的CRC生成多项式。

在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC. CCITT,ARJ、LHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。

(三)CRC检验码的计算

CRC校验码软件生成方法:

    借助于多项式除法,其余数为校验字段。

例如:信息字段代码为: 1011001;对应m(x)=x6+x4+x3+1 

      假设生成多项式为:g(x)=x4+x3+1;则对应g(x)的代码为: 11001

      x4m(x)=x10+x8+x7+x4 对应的代码记为:10110010000;

采用多项式除法:  得余数为: 1010     (即校验字段为:1010)

发送方:发出的传输字段为: 1 0 1 1 0 0 1 1 0 10

                   信息字段      校验字段

接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)如果能够除尽,则正确。

 

看一下下面的生成码、解码的过程:发送的数据为“12”这是字符对应的16进制为3132H

20110831094432001.png


接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)如果能够除尽,则正确)。

20110831094525001.png


广告

文章评论 1条评论)

登录后参与讨论

liangjin_009_162190671 2014-7-30 09:47

very good!!!
相关推荐阅读
513910488_509737122 2011-09-09 19:07
【原创】Nios II Processor参数设置
                              【原创】Nios II Processor参数设置 软件:Quartus II10.0、SOPC Builder10.0 1.添加Nios ...
513910488_509737122 2011-08-31 14:03
CRC码的FPGA实现之三仿真验证
                                                  CRC码的FPGA实现之三仿真验证与时序分析 (3)建立波形仿真文件并进行仿真验证,分析其运行最高时...
513910488_509737122 2011-08-31 13:17
CRC码的FPGA实现之二编译技巧
                                                       CRC码的FPGA实现之二编译技巧 5.实验步骤 (1)启动Quartus II建立一个空...
513910488_509737122 2011-08-31 11:52
EPCS的三种编程方法之三IDE Flash Programmer
EPCS的三种编程方法之三IDE Flash Programmer   1.实验目的 学习使用Nios II IDE中的Flash Programmer对EPCS进行编程。 2.实验设备 硬件:Sma...
513910488_509737122 2011-08-31 11:47
EPCS的三种编程方法之一AS配置模式
EPCS的三种编程方法之一AS配置模式 1.实验目的 学习使用AS接口以及POF文件对EPCS进行编程。 2.实验设备 硬件:SmartSOPC教学实验开发平台 软件:Quartus II 10.0 ...
513910488_509737122 2011-08-31 11:46
EPCS的三种编程方法之二JTAG配置模式
EPCS的三种编程方法之二JTAG配置模式 1.实验目的 1.学习使用Quartus II的文件转换工具。 2.学习使用JTAG接口对EPCS进行编程。 2.实验设备 硬件:SmartSOPC教学实验...
广告
我要评论
1
0
广告
关闭 热点推荐上一条 /2 下一条