基于C语言的CRC编码与解码的实现

实验目的

1. 设置一个d位的数据D, r+1位的多项式G，编写程序生成CRC码，并把此CRC码 作为数据帧进行传送。

2. 编写两个子程序，分别实现CRC编码和CRC解码，在主函数中对子程序进行调用。 解码子程序应能根据解码情况判断出接收到的数据帧是否出错，并给出提示。

3. 要求分别以正确和错误的数据来检验此检错程序。

实验原理

CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列)，从而构成一个总长为n＝p＋r位的二进制序列；附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏。因此，通过检查这一关系，就可以实现对数据正确性的检验。

CRC校验码的计算

设信息字段为K位，校验字段为R位，则码字长度为N(N=K+R)。设双方事先约定了一个R次多项式g(x)，则CRC码：V(x)= A(x) g(x) = x Rm(x) + r(x)
其中: m(x)
为K次信息多项式，r(x)为R-1次校验多项式。
这里r(x)对应的代码即为冗余码，加在原信息字段后即形成CRC码。
r(x)的计算方法为：在K位信息字段的后面添加R个0，再除以g(x)对应的代码序列，得到的余数即为r(x)对应的代码(应为R－1位；若不足，而在高位补0)。

计算实例

下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G（X）
= X4 + X3 + 1，要求出二进制序列10110011的CRC校验码。具体的计算过程：

①首先把生成多项式转换成二进制数，由G（X）= X4 + X3 + 1可以知道：它一共是5位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1的位，也就是这个二进制的第4位、第3位、第0位的二进制均为1，其它位均为0）很快就可得到它的二进制比特串为11001。

② 因为生成多项式的位数为5，根据前面的介绍，得知CRC校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数，即CRC校验码为0100，如图所示。

③把上步计算得到的CRC校验码0100替换原始帧101100110000后面的四个“0”，得到新帧101100110100。再把这个新帧发送到接收端。

④当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。

CRC编码算法实现

① 选择生成多项式G，其最高次方为r，即r+1位的二进制位串

②计算D·2r, 即在数据D后面补r个0，构成d+r位的位串

③按模2除法求（D·2r/G）的余数R,即:

④从D·2r中模2减去R，得到新的数据T，即加了CRC的帧

代码实现

CRC.h文件：

#define
_CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

int D[40], M[40],
G[40];    //M[]为生成器数据 G[]为原始数据 D[]为经处理除数/待解码数据

int m, n;               //m为生成器长度 n为原始数据长度

 

void CRC(void);             //CRC编码

void CRL(void);             //CRC译码

void XOR (void);        //模2除法

operation.c文件：

#include "CRC.h"
//CRC编码
void CRC(void) {
         int i;
         for(i = 0; i <= n - 1; i++) D[i] = G[i];     //D[]为即将要处理的原始数据
         for(i = n; i <= m + n - 2; i++) D[i] = 0;   //对要进行操作的被除数D[]进行求补 
         printf("\n\t\t原始数据补数处理后为：");
         for(i = 0; i <= m + n - 2; i++)               //输出原始数据G[]求补后的数D[]
         printf("%d",D[i]);
         XOR();//进行模2除法，求余数                                                                                             
         for(i = 0; i <= n - 1; i++) D[i] = G[i];   //将余数加到原数据后面，完成CRC编码
         printf("\n\n\t编码后结果为：");
         for(i = 0; i <= m + n - 2; i++) printf("%d", D[i]);
}


//CRC译码
void CRL(int m, int n) {    
         int i;
         system("cls");
         printf("\n\n\t请输入%d位需要解码的数据：",n + m - 1);
         for(i = 0; i <= n + m - 2; i++) scanf("%d", &D[i]); //接收待验证编码序列D[]
         XOR();//对D[]进行模2除法进行验证                                                                                                                  
         for(i = 0; i <= m + n - 2; i++) if (D[i] != 0)i = m + n; //若余数均为0，则判断数据完全正确
         if(i == m + n - 1)
            printf("\n\n\t数据完全正确\n");
         else
           printf("\n\n\t数据出错\n");
}
//模2除法
void XOR(void) {

         int i, j, k = 0;
         for(i = 0; i <= n-1; i++){
             if (D[i] == 1){//当第一位为1时进行异或操作                                                     
                 k= 0;//k对生成器数据作比较的位置进行记录
                 for (j = i; j < i + m; j++){
                     if(M[k] == D[j]) D[j] = 0;        //两数相同为0
                     else
                     D[j] = 1;                         //两数相异为1
                     k++;
                     }                     
                    printf("\n\t\t异或结果:");   //对每次异或的结果进行输出显示 
                    for(k = 0; k <= m + n - 2; k++) printf("%d", D[k]);
                   }
         }
}

Main.c文件：

#include "CRC.h"
int main(){
   int i,a;
   printf("\n\n\t请输入生成器的长度：");
   scanf("%d", &m);
   printf("\n\t请输入原始数据的长度：");
   scanf("%d", &n);
   printf("\n\n\t请输入生成器 =
");
   for (i = 0; i <= m - 1; i++)
       scanf("%d", &M[i]);
   printf("\n\t请输入原始数据 =
");
   for ( i= 0; i <= n - 1; i++)
       scanf("%d", &G[i]);
   CRC();                      //CRC编码
   printf("\n\n\t是否继续(1代表继续，2代表退出)？ ");
   scanf("%d", &a);getchar();
   if (a == 1)CRL(m, n);           //若继续则进行译码
   else {
       system("cls");
       printf("\n\n\t按任意键退出\n");
       getchar();               //接收任意键
       exit(0);
   }
   return 0;
}

演示结果

CRC编码
CRC译码正确

CRC译码错误

总结

（1）CRC是一种常用的检错码，并不能用于自动纠错。
（2）只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的
错误的概率就很小。
（3）仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受（只是非常近似的认为是无差错的），并不能保证可靠传输。
（4）余数的位数一定要是比除数位数只能少一位，哪怕前面位是0，甚至是全为0（附带好整除时）也都不能省略。

Verilog 实现32位并行CRC编解码 可在一个时钟周期出结果

CRC简介

CRC(Cyclic Redundancy Check，循环冗余校验）是数据帧传输中常用的一种差错控制编码方式，针对要发送的数据帧，使用一些特定的多项式可以计算出CRC校验结果，CRC校验结果和原始数据一起传输到接收端。

接收端在接收数据的同时按照相同的多项式对接收数据进行校验运算，并将 校验结果和接收的结果进行对比，如果二二者相同则认为没有发生传输错误；如果不同，则认为是发生了传输错误。从理论上说，如果接收端计算出的CRC值与接收到的CRC值匹配，数据中仍有出错的可能，但由于这种可能性极低，在实际应用中可以视为0,即没有错误出现。当接收端CRC不匹配时，接收端可以采取不同的措施，例如，丢弃数据包并通知对端，要求对端重新发送，或者只进行丢弃处理，通过高层协议实现数据的重传。

CRC多项式

本文介绍的并行CRC多项式为：x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1.为32CRC常用多项式。crc32=32’h104c11db7.

仿真

很多提供的CRC编解码都是Verilog串行资料，因此博主花了点时间验证了Verilog并行实现。废话少说上图：

串行CRC

对于串行32位CRC，需要32个时钟周期出结果。本文一帧数据96bit，所以串行32crc需要分3批运算96次。
第一批

运算的第一批32位数据32’h00100000,crc结果32’h1d8ac870

运算的第二批32位数据32’h55555555,crc结果32’ha48ebce5

运算的第三批32位数据32’haaaaaaaa,crc结果32’hfc3c3755

则，96’h0010000055555555aaaaaaaa的串行CRC结果为32’hfc3c3755.一共用了96个时钟周期运算。

并行CRC

第一个时钟32位数据32’h00100000,并行crc结果32’h1d8ac870
第二个时钟32位数据32’h55555555,并行crc结果32’ha48ebce5
第三个时钟32位数据32’haaaaaaaa,并行crc结果32’hfc3c3755
96’h0010000055555555aaaaaaaa的并行CRC结果为32’hfc3c3755.
可以看出并行CRC和串行CRC结果保持一致，但是在同样的一帧96bit数据串行crc用了96个clk.并行crc用了3个clk（不看其他开销）。

具体Verilog的并行CRC代码如下链接下载

链接: https://download.csdn.net/download/baozouxiaoluoli/22331004.

一、CRC码的原理
CRC码是一种可以检查出多位错误的校验码。
利用CRC码检错的过程如下：
在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。

在上面这个图中，总位长必须符合这个式子（考试考过）

生成多项式是一个二进制序列，它比校验信息多一位（即r+1位），发送方用它对被校验的信息进行模二的除法运算，以此来生成校验码序列。接收方也这么操作。

补充一下模二运算是什么
模2除法·，从字面上可理解为二进制下的除法。
模2除法与算术除法类似，但每一位除的结果不影响其它位，即不向上一位借位，所以实际上就是异或。
举个栗子：
1111000除以1101：

二、CRC码的编码
先求这个式子的r的最大值

然后找到G（X） [这个好像是直接查就行了]
然后在有效信息后面补r个0
举个栗子

这个时候把之前的3个0替换成010就好了
这时候，1100010就是crc编码

三、那么如何校验呢
看这个图，比较清晰：

举个栗子

可以看到 余数为0，那就没错

但是如果是这样：

四、检错与纠错

看一下如何纠错

这个图讲的比较抽象 可以详细讲一讲 但是太晚了我以后再写吧。。。。。