近日，因为项目的需要，重新拾起编码理论，这个项目当中，发送端的信息序列添加了CRC码字，好在接收端进行CRC校验，检测接收到的信息序列是否在传输过程中出现了错误。CRC编码作为循环码字的一种，通常用在数据传输的检错中，其生成原理与循环码字的生成完全一致，其原理下面会进行说明。
1. 编码原理
        循环码的码字多项式都是多项式g(D)的倍式，该g(D)的阶数为r=n-k，对于一个信息序列M(D)，其码字多项式可以表示为
A(D) = D^(n-k)*M(D) + r(D),
        r(D)为监督码多项式，它等于D^(n-k)*M(D)除以g(D)得到的余式，说的通俗一点，循环码的构造就是凑出一个余式r(D)使得码字多项式A(D)能够被生成多项式g(D)整除，在传输过程中码字A(D)一旦发生了错误，则接收端的码字不能够被生成多项式整除，就可以知道在传输过程中发生了错误，在循环码字的纠错范围内时，可以根据错误的图案（接收到的码字除以生成多项式的余式），找到对应错误的信息比特位。余式r(D)可以表示为
r(D) = D^(n-k)*M(D) mod g(D),
        下面举个例子看看循环码字是怎么生成的。对于一个(7, 4)的系统循环码，7表示码字长度n=7，4表示编码的信息序列长度k=4，那么监督序列的长度r=n-k=3，系统码表示生成的n比特码字中，前面k个比特的码字与信息码字完全一致，只是在信息码字后添加了r个比特的校验位。言归正传，(7, 4)系统循环码的生成多项式为g(D) = D^3 + D^2 + 1，若信息码为1001，那么怎么求编码后的码字呢？我们知道，只要求出后面r个比特的监督码字就行了，前面的k个比特的码字照抄信息码字就行了。信息码字1001写成多项式的形式为
M(D) = D^3 + 1,
        监督多项式通过求余得到：
r(D) = D^3*(D^3 + 1) mod (D^3 + D^2 + 1) = D + 1,
        码字多项式：
A(D) = D^3*(D^3 + 1) + D + 1 = D^6 + D^3 + D + 1,
        码字多项式写成序列的形式为1001011。值得一提的是，在编码过程中，所采用是GF(2)域上的加减法运算，相当于说减法也可看成加法，所有的加法都是模2加运算，即
1 + 1 = 0, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0,
        对于k比较长的情况，写成这种多项式的形式不便于计算，这里提供另外一种表达形式，实际上都是求余式操作，不过在形式上做了简化而已。
                                                                                         1  1  1  1
                                                                                 _____________________
                                                               1101       |         1   0  0  1  0  0  0
                                                                                   +    1   1  0  1
                                                                                   ----------------------------
                                                                                              1  0  0  0
                                                                                        +    1  1  0  1
                                                                                     -----------------------------
                                                                                                   1  0  1  0
                                                                                              +   1  1  0  1
                                                                                             -----------------------------
                                                                                                       1  1  1  0
                                                                                                 +    1  1  0  1
                                                                                               -------------------------------
                                                                                                            0  1  1   
        该方法只是将多项式操作变成了数字操作，信息序列1001后添加3个0代表乘上D^3，生成多项式D^3 + D^2 + 1写成序列形式就是1101，每次商上面的一位操作，进行模2加，余式继续同样的操作，直到补零的信息序列截止到最后一位，剩下的余式011即为监督序列，两种方法原理相同，当然结果也是相同的。
2. 硬件电路


        上面的硬件电路图就是生成多项式g(D) = D^3 + D^2 + 1，对应的循环码字生成电路，至于为什么是这样，笔者表示上课时，老师也没讲，自己也并未深究，为了应付考试，强行记住了，然而到了做项目的时候，才发现自己对该电路完全没搞懂，于是乎，琢磨了一番，总算是搞明白了，下面且听我细细道来。
        首先，讲一下硬件电路对应的时序控制，由于该循环码字是系统码，生成的码字在前k=4个比特是将信息序列直接输出，也即与门1在1拍~4拍是开启的，信息序列进行编码，但输出相关的与门2是关闭的，与门2的输出在前4拍一直是0，在或门处，信息序列直接输出；到了5拍~7拍，需要输出监督序列了，这是信息序列已经全部处理完毕，监督序列完全寄存在了D1~D3这3个寄存器中，只要将这3比特的监督序列直接输出即可，这时与门1在5拍~7拍关闭，与门2在5拍~7拍开启，或门输出的是寄存器直接出来的监督序列。
        接下来，我们看看电路的左半部分是如何由信息序列生成监督序列的。我们看生成多项式g(D) = D^3 + D^2 + 1，对应到图上寄存器D3和D2后面的异或门，通过反馈操作实现除法求余操作。它的生成原理与第一小节编码原理给出的基本相同，但不同的地方是，由于信息比特是按照时钟逐比特输入的，没办法做到像编码原理给出的将这个信息序列对生成多项式求余，而是每进来一个信息比特，进行判断，然后操作。具体是啥意思呢，我讲个例子就清楚了。,
        信息序列还是1001，初始状态时，D1~D3三个寄存器的值都为0，输入的第一个信息比特是1，与D3的异或是1，这里为什么输入序列与D3做异或呢？其实这里隐含了一个选择操作，D1~D3代表当前的余式，D3表示余式的最高位，如果当前的输入与当前的余式最高位D3相同的话，则当前输入与余式的模2加为0，即当前输入更新使得余式最高位为0，则此时商上面上0，不用对生成多项式做模2加运算，余式只要右移一位完成余式的更新操作（一个比特与0异或等于自身，所以这种情况下，电路中异或不起作用）；另一种情况是，当前的余式最高位D3与当前输入序列异或为1，表示当前输入更新后余式包含最高位，需要对生成多项式求余，求余操作通过电路中的异或进行，完成D1~D3的更新。具体步骤如下：
        (1) 初始状态：                       输入ui             D1    D2    D3                   输出uo
                                                                                  0       0        0
        (2)                                              1                     1       0        1                         1
        (3)                                              0                     1       1        1                         0
        (4)                                              0                     1       1        0                         0
        (5)                                              1                     1       1        0                         1
        D1~D3剩下的011即为监督比特，剩下3拍，逐比特输出：
        (6)                                              0                     0       1        1                         0
        (7)                                              0                     0       0        1                         1
        (8)                                              0                     0       0        0                         1
3. FPGA实现
        根据第二部分的电路原理分析，我们可以将循环码的编码分成两个阶段，第一个阶段为编码阶段，码字输出选择信息序列的输入直接作为输出；第二阶段为监督码字输出阶段，在第一阶段的最后，监督码字实际上已经完全生成，存储在寄存器中，第二阶段的任务就是将监督码字逐个输出，由此可以通过状态机实现该操作。状态机可以设置三种状态：IDLE, ENCODING, OUT。IDLE状态表示状态机处于空闲状态，不进行任何操作；ENCODING状态时，状态机进行输入信息序列的循环编码，同时输出信息码字；OUT状态时，输出监督码字。下面将采用verilog语言实现循环码的编码过程：


module cyc_encoding(
  input                       clk,
  input                       rst_n,
  input                       e_start_i,                //编码启动信号，比第一个信息序列早一个时钟周期
  input                       symbol_i,                //输入信息序列
  output reg              e_start_o,               //输出启动信号
  output reg              symbol_o                //输出编码序列
);


// 常量定义
parameter INFO_BITS_LEN = 4;          //信息序列长度
parameter CODED_BITS_LEN = 7;     //编码码字长度


wire enable;
wire encoding_start;
wire encoding_end;


reg [2:0] symbol_cnt;


// 状态机定义
parameter IDLE = 3'b001;
parameter ENCODING = 3'b010;
parameter OUT = 3'b100;
reg [2:0] state;


/**********************************************************/

// 编码状态机
/**********************************************************/

always @(posedge clk)
  begin
    if(!rst_n)
        state <= IDLE;
    else begin
        case(state)
            IDLE:  state <= e_start_i ? ENCODING : IDLE;
            ENCODING:  state <= encoding_start ? OUT : ENCODING;
            OUT:  state <= encoding_end ? IDLE : OUT;
            default:  state <= IDLE;
        endcase
    end
  end


assign enable = (state != IDLE);


/**********************************************************/
// 符号计数器
/**********************************************************/

always @(posedge clk)
    begin
        if(!rst_n)
            symbol_cnt <= 3'd0;
        else
            symbol_cnt <= enable ? (symbol_cnt + 1'b1) : 3'd0;
    end


assign encoding_start = (symbol_cnt == INFO_BITS_LEN -1);
assign encoding_end = (symbol_cnt == CODED_BITS_LEN -1);


reg [2:0] encoding_reg;
/**********************************************************/

// 寄存器更新操作
/**********************************************************/

always @(posedge clk)
    begin
        if(!rst_n)
            encoding_reg <= 3'd0;
        else begin
            case(state)
                IDLE:  encoding_reg <= 3'd0;
                ENCODING:
                    begin
                        encoding_reg[0] <= encoding_reg[2] ^ symbol_i;
                        encoding_reg[1] <= encoding_reg[0];
                        encoding_reg[2] <= encoding_reg[1] ^ encoding_reg[2] ^ symbol_i;
                    end
                 OUT:  encoding_reg <= {encoding_reg[1:0], 1'b0};
                 default:  encoding_reg <= 3'd0;
            endcase
        end
    end


/**********************************************************/

// 输出编码后的符号
/**********************************************************/

always @(posedge clk)
    begin
        if(!rst_n)
            symbol_o <= 1'b0;
        else begin
            case(state)
                IDLE:  symbol_o <= 1'b0;
                ENCODING:  symbol_o <= symbol_i;  //信息序列
                OUT:  symbol_o <= encoding_reg[2];  //监督序列
                default:  symbol_o <= 1'b0;
            endcase
        end
    end


/**********************************************************/

// 启动信号输出
/**********************************************************/

always @(posedge clk)
    begin
        if(!rst_n)
           e_start_o <= 1'b0;
        else
           e_start_o <= e_start_i;
    end

在ＣＡＮ系统中为保证报文传输的正确性，需要对通信过程进行差错控制。目前常用的方法是反馈重发，即一旦收到接收端发出的出错信息，发送端便自动重发，此时的差错控制只需要检错功能。常用的检错码有两类：奇偶校验码和循环冗余校验码。奇偶校验码是一种最常见的检错码，其实现方法简单，但检错能力较差；循环冗余校验码的编码也很简单且误判率低，所以在通信系统中获得了广泛的应用。下面介绍ＣＡＮ网络中循环冗余校验码（即ＣＲＣ码）的原理和实现方法。 １ ＣＲＣ码检错的工作原理          ＣＲＣ码检错是将被处理报文的比特序列当作一个二进制多项式Ａ（ｘ）的系数，该系数除以发送方和接收方预先约定好的生成多项式ｇ（ｘ）后，将求得的余数ｐ（ｘ）作为ＣＲＣ校验码附加到原始的报文上，并一起发给接收方。接收方用同样的ｇ（ｘ）去除收到的报文Ｂ（ｘ），如果余数等于ｐ（ｘ），则传输无误（此时Ａ（ｘ）和Ｂ（ｘ）相同）；否则传输过程中出错，由发送端重发，重新开始ＣＲＣ校验，直到无误为止。         上述校验过程中有几点需注意：①在进行ＣＲＣ计算时，采用二进制（模２）运算法，即加法不进位，减法不借位，其本质就是两个操作数进行逻辑异或运算；②在进行ＣＲＣ 计算前先将发送报文所表示的多项式Ａ（ｘ）乘以ｘn，其中ｎ为生成多项式ｇ（ｘ）的最高幂值。对二进制乘法来讲，Ａ（ｘ）·ｘn就是将Ａ（ｘ）左移ｎ位，用来存放余数（ｘ），所以实际发送的报文就变为Ａ（ｘ）·ｘn＋ｐ（ｘ）；③生成多项式ｇ（ｘ）的首位和最后一位的系数必须为１。图１为ＣＲＣ校验的工作过程。 

          目前已经有多种生成多项式被列入国际标准中，如：ＣＲＣ－４、ＣＲＣ－１２、ＣＲＣ－１６、ＣＣＩＴＴ－１６、ＣＲＣ－３２等。ＣＡＮ总线中采用的生成多项式为ｇ（ｘ）＝ｘ15＋ｘ14＋ｘ10＋ｘ8＋ｘ7＋ｘ4＋ｘ3＋１。可以看出，ＣＡＮ总线中的ＣＲＣ校验采用的多项式能够校验七级，比一般ＣＲＣ校验（ＣＲＣ－４、ＣＲＣ－１２、ＣＲＣ－１６等）的级数（二～五级）要高许多，因而它的检错能力很强，误判率极低，成为提高数据传输质量的有效检错手段。
 
2 CRC序列计算方法
多项式ｇ（ｘ）除法的余数就是发送到总线上的CRC序列。为了实现这个功能，可以使用15位的移位寄存器----CRC_RG(14 : 0)。如果NXTBIT指示位流的下一位，那么从帧的起始到数据末尾都由没有填充的位顺序给定。CRC序列的计算如下：
CRC_RG=0;                                             //初始化移位寄存器 REPEAT         CRCNXT = NXTBIT  EXOR  CRC_RG(14);        //异或运算         CRC_RG(14 : 1)= CRC_RG(13 : 0);     //寄存器左移1位         CRC_RG(0)=0;                IF CRCNXT THEN              CRC_RG(14 : 0)==CRC_RG(14 : 0)  EXOR   (4599hex);         ENDIF UNTIL   (CRC序列开始或有一错误条件) 

	

欢迎FPGA工程师加入官方微信技术群
点击蓝字关注我们FPGA之家-中国最好最大的FPGA纯工程师社群
实验目的
学习用FPGA设计一个数据通信中常用的数据检错模块——循环冗余检验CRC模块，熟悉理解CRC的检错原理。
实验原理
循环冗余检验(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加法运算定义为：
0＋0＝0        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生成多项式。
国际通行标准可以查看 http://en.wikipedia.org/wiki/Cyclic_redundancy_check
在数据存储和数据通讯领域，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
接收方：使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)如果能够除尽，则正确)。
人有两条路要走，一条是必须走的，一条是想走的，你必须把必须走的路走漂亮，才可以走想走的路~~~
欢迎通信工程师和FPGA工程师关注公众号
全国第一大FPGA微信技术群
欢迎大家加入全国FPGA微信技术群，这个群体拥有数万工程师、一群热爱技术的工程师，这里的FPGA工程师相互帮助，相互分享，技术氛围浓厚！赶紧叫上小伙伴一起加入吧！！
用手指按住就可以加入FPGA全国技术群哦
FPGA之家元器件芯城
优势元器件服务，有需求请扫码联系群主：金娟 邮箱：293580331@qq.com 欢迎推荐给采购
ACTEL、AD部分优势订货(经营全系列)：
XILINX、ALTERA优势现货或订货(经营全系列)：
(以上器件为部分型号，更多型号请咨询群主金娟)
服务理念：FPGA之家元器件自营芯城，旨在方便工程师快速方便购买器件服务，经过数年竭诚服务，我们的客服遍布国内大型上市公司、军工科研单位、中小企业、最大的优势是强调服务至上的理念、并且做到快速交货、价格优惠！
直营品牌：Xilinx ALTERA ADI TI NXP ST E2V、镁光 等百余元器件品牌，尤其擅长欧美对华禁运器件，欢迎工程师朋友把我们推荐给采购或者亲自咨询我们！我们将一如既往提供业内最佳服务！
FPGA技术群官方鸣谢品牌：Xilinx、 intel(Altera)、microsemi(，Actel)、LattIC e，Vantis，Quicklogic，Lucent等

基于CAN总线的CRC校验码的原理与实现
王鹏
【摘 要】CAN总线又称为控制器局域网技术，属于工业现场总线，应用范围很广.CAN系统中通常
采用反馈重发机制对通信过程进行差错控制.当接收端反馈给发送端出错信息后，发送端便自动重发
，经此过程，只需要检错就可以了.循环冗余校验码实现简单，误判率比较低，还具有纠错功能，在
通信系统中应用较为广泛.
【期刊名称】赤峰学院学报(自然科学版)
【年(卷),期】2014(000)004
【总页数】2
【关键词】控制器局域网；差错校验；CRC循环校验
CAN(Controller Area Network)全称控制器局域网，是工业现场总线的一种，是应用最广泛的开放
式现场总线之一.与其它通信网的不同之处在于：第一，报文传送中不包含目的地址，而是以全网广
播为基础，各接收站根据报文中的标识符过滤报文，以决定接收还是丢弃，其优点在于可在线上网
下网、即插即用和多站接收；第二，强化了对数据安全性的要求，满足控制系统及其它较高数据安
全要求的系统需求.
CAN系统中通常采用反馈重发机制对通信过程进行差错控制，以保证报文能正确的传输.当接收端反
馈给发送端出错信息后，发送端便自动重发，在此过程中，只需要检错就可以了.一般的检错码有两
类：奇偶校验码和循环冗余校验码.奇偶校验码只具有检错能力，实现方法简单，不能纠错；循环冗
余校验码也很简单，而且误判率比较低，还具有纠错功能，在通信系统中应用较为广泛.
下面，通过实例，来说明CAN网络中循环冗余校验码的工作原理和实现方法.
1 CRC检错码的工作原理
一般情况，一个由二进制数位串组成的发送序列，可以用一个只含有0和1系数的多项表达式的系数
表示出来，例如：代码1001011对应的多项式为X6+X3+X+1，再如：代码为1010111，则对应的
多项式X6+X4+X2+X+1.
CRC检错码是采用多项式相除的运算方法实现的，如被处理报文的比特序列对应的多项式为P
(X)，收发双方约定的多项式为G(X),用P(X)除以G (X)后，求得余数多项式R(X)，并将多项式R(X)附
加到多项式P(X)的后边，生成M(X)，这样能保证M(X)除以G(X)的余数为0.此时，可以将M(X)作为
发送序列发给接收方.接收方用收到的报文N(X)去除同样的G(X)，如果余数等于0，则说明接收到的
序列与发送的序列一致，接收到的数据没有错误；否则，说明传输过程中出错，由发送端重发，重
新开始CRC校验，直到接收到的数据没有错误为止.