精华内容
下载资源
问答
  • 2021-05-23 09:27:34

    众所周知,不可能有永远都不会出错的人,同样也不可能有永远不出错的计算机,永远不出错的数据。

    人有知错能改的觉悟,计算机也有,不过计算机没有人类聪明,只能通过一个特定的方法进行自我改正,这就是校验码存在的必要了。

    一般用得比较多的校验码有奇偶校验码,CRC循环冗余校验码,海明校验码等。

    这里只介绍用的最多的CRC循环冗余校验码。

    何为校验码

    校验码是通过一种计算方法,发出端在原始数据的尾部添加若干数据;然后接收端通过计算得出数据有无错误,并且能把错误的数据还原成正确的数据。

    例如,原始数据为1010,我们通过在其尾部添加若干数据,比如101,则数据变成了1010101,将这个新的数据发送出去;假如在发送过程中出现错误,数据变成了1110101,则接收端能根据1110101还原成原始正确的数据1010。

    CRC循环冗余校验码的特点

    CRC码是基于模2运算建立编码规律的校验码(模2运算可以简单的理解为异或运算)。

    编码方法:

    1.将原始数据用一个多项式M(x) = A*X^(n-1)+B*X^(n-2)+…+N*X^(1)+P*X^(0)

    比如说原始数据是1010,则表示为M(x) = 1*X^(3)+0*X^(2)+1*X^(1)+0*X^(0)

    2.将原始数据左移k位,得到M(X)*X^k,形成了n+k位信息。

    上面的1010,左移3位,得到1010 000

    3.用多项式M(X)*X^k 除以(或者说异或)一个特定的生成多项式G(X),所得余数则为需要拼接到原始数据尾部的CRC校验码。

    例:

    已知原始数据为1100,生成多项式G(X)=1011,则求算CRC码的过程如下:

    已知  :M(X) = 1100 = X^3+X^2      (n=4)

    由        G(X) = 1011 = X^3+X^1+1

    得        k+1 = n = 4

    得       k=3,需要左移3位

    故得     M(X)*X^3 = 1100 000

    (M(X)*X^3) / G(X)计算过程:

    1100 000                M(X)*X^3

    1011                      G(X)

    --------------

    111 0                     余数,高位0省去;然后余数左移1位,继续异或G(X)

    101 1                  G(X)

    ---------------

    10 10                  左移1位,继续异或G(X)

    10 11

    ----------------

    10                  由于k=3,而算到这里我们已经对余数移位2次,还需1次

    则最后算出来的结果是010,则原始数据变成了1100 010,最后三位是CRC码。

    很容易发现,如果我们需要算k位码,则G(X)的位数应该是K+1.

    由于最后的数据变成了7位,而有效数据还是4位,故上述的1100 010码又叫做(7,4)码,对应的还有(7,3)码,(7,6)码等。

    CRC码的译码规则和纠错方法

    还是刚刚的例子,我们用最后得出的数据除以G(X),发现其余数为0,这个就是正确的数据。

    我们尝试改动其中一位,比如说第2位,得到:1000 010,我们用这个数除以G(X),发现余数为111,余数不为0,则说明数据有错了!

    下面给出每个位出错对应的余数:

    序号

    N1  N2  N3  N4  N5  N6  N7

    余数

    出错位

    正确

    1    1    0    0    0    1    0

    000

    错误

    1    1    0    0    0    1    1

    001

    7

    错误

    1    1    0    0    0    0    0

    010

    6

    错误

    1    1    0    0    1    1    0

    100

    5

    错误

    1    1    0    1    0    1    0

    011

    4

    错误

    1    1    1    0    0    1    0

    110

    3

    错误

    1    0    0    0    0    1    0

    111

    2

    错误

    0    1    0    0    0    1    0

    101

    1

    假如我们现在收到一个错误的信息是1000 010,通过计算可以得出余数是111,但是如何得知是第几位出错了?

    我们试着对余数111补0后继续除下去,发现下一次的余数变成了101,继续下去,又变成了001,以后依次出现为010,100,011。。。反复循环,这就是“循环码”名字的由来。

    这样,假如N2出现错误,则出现了不为0的余数后,一方面对余数补0继续模2除,另一方面将被检测的校验码字循环左移,当余数为101(即数据的首位为0)时,通过异或门可以将其纠正后在下一次移位时送回N2。这样当移满一个循环后,就得到一个纠正后的数据了。

    最后给出几个标准

    在上面的计算中可以发现,G(X)的作用非常重要,生成CRC码和译码都需要它。值得指出的是,并不是随便一个(K+1)位数据都可以作为生成多项式,它要满足的条件:

    1.任何一位出错,都不能使余数为0,这是非常显然的;

    2.不同位发生错误后,余数不能相同;

    3.对余数继续模2除,应使余数循环。

    为了方便起见,也为了标准化工作,现在一般用的生成多项式有以下几个:

    CRC-16 = X16 + X15 + X2 + X0           美国二进制同步系统中采用

    CRC-CCITT = X16 + X12 + X5 + X0        由欧洲CCITT 推荐

    CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0

    下面贴出生成CRC码的代码

    #include #include

    using namespacestd;#define CRC_16 0x18005

    //CRC-16 = X16 + X15 + X2 + X0

    #define CRC_CCITT 0x11021

    //CRC-CCITT = X16 + X12 + X5 + X0

    #define CRC_32 0x104C11DB7

    //CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0

    #define CHECK_CODE 0x8000

    //check_code = x15,判断被除数位数>=16//check_code是为了每次做异或运算时保证位数是足够的

    unsignedlong table[256];void build_16(unsigned longpoly)

    {

    unsignedlongx;

    unsignedlongt;/*这里是将原始数据直接写入到t中

    for (unsigned long i=0; i<256; i++)

    {

    x = i << 8;

    t = 0;

    for (unsigned long j = 0; j < 8; j++)

    {

    if ( (x ^ t) & CHECK_CODE)

    t = (t << 1) ^ poly;

    else

    t <<= 1;

    x <<= 1;

    }

    table[i] = ( unsigned long ) t;

    }*/

    //下面的是把余数和原始数据分开的写法//原始数据只有8位

    for (int i=0; i<256; i++)

    {

    x= i<<8;//只移8位是为了位数对齐,因为下面的运算都是低位对齐的

    for (int j=0; j<8; j++)

    {if (x&CHECK_CODE)

    {

    x<<= 1;

    x= x^poly;

    }else x <<= 1;

    }

    table[i]= (i<<16)+x;

    }

    }void build_32(unsigned longpoly)

    {

    unsignedlongx;for (unsigned long i=0; i<256; i++)

    {

    x= i<<24;for (unsigned long j=0; j<8; j++)

    {if (x & 0x80000000) //判断位数是否足够,32位

    {

    x<<= 1;

    x= x^poly;

    }else x <<= 1;

    }

    table[i]= (i<<32)+x;

    }

    }intmain()

    {

    build_16(CRC_16);

    build_16(CRC_CCITT);

    build_32(CRC_32);for (int i=0; i<256; i++)

    {if (i % 10 == 0)

    cout<

    printf("%lx", table[i]);

    }return 0;

    }

    更多相关内容
  • 循环冗余校验码(CRC)计算源代码合集,里面包含了各种编程语言(包括C,C++,单片机等)CRC代码的实现
  • 基于FPGA的循环冗余校验码设计.pdf
  • 循环冗余校验码(CRC码)

    千次阅读 2022-03-16 14:45:19
    循环冗余校验码(CRC码) 循环冗余校验码的思想: 数据发送、接受方约定一个“除数” K个信息位+R个校验位作为“被除数”,添加校验位后需保证除法的余数为0。收到数据后,进行除法检查余数是否为0,若余数非0说明...

    循环冗余校验码(CRC码)

    循环冗余校验码的思想:
    数据发送、接受方约定一个“除数”
    K个信息位+R个校验位作为“被除数”,添加校验位后需保证除法的余数为0。收到数据后,进行除法检查余数是否为0,若余数非0说明出错,则进行重传或纠错。
    在这里插入图片描述
    例.设生成多项式为G(x)= x 3 x^3 x3+ x 2 x^2 x2+1,信息码为101001,求对应CRC码。

    1.确定K、R以及生成多项式对应的二进制码

    K=信息码的长度=6,R=生成多项式最高次幂=3——>校验码位数N=K+R=9
    生成多项式G(x)=1* x 3 x^3 x3+1* x 2 x^2 x2+0* x 1 x^1 x1+1* x 0 x^0 x0,对应二进制码1101

    2.移位

    信息码左移R位,低位补0。(101001000

    3.相除

    对移位后的信息码,用生成多项式进行模2除法,产生余数

    模2除法

    在这里插入图片描述
    对应的CRC码:101001 001

    4.检错和纠错

    发送:101001001 记为 C 9 C_9 C9 C 8 C_8 C8 C 7 C_7 C7 C 6 C_6 C6 C 5 C_5 C5 C 4 C_4 C4 C 3 C_3 C3 C 2 C_2 C2 C 1 C_1 C1
    接收:101001001 ———> 用110进行模2除——> 余数为000,代表没有出错。

    K个信息位,R个校验位,若生成多项式选择得当,且 2 R 2^R 2R>=K+R+1,则CRC码课纠正1位错。(实际应用中一般只用来“检错”)

    理论上可以正面循环冗余校验码的检错能力有以下特点:
    1.可检测出所有奇数个错误;
    2.可检测出所有双比特的错误;
    3.可检测出所有小于等于校验位长度的连续错误

    以下一个小例子:

    /**
         * 计算CRC16校验码
         *
         * @param bytes
         * @return
         * [1,3,4,1,205,1,18,235,173]
         */
        public static String CRC16(byte[] bytes) {
            int CRC = 0x0000ffff;
            int POLYNOMIAL = 0x0000a001;
            int i, j;
            for (i = 0; i < bytes.length; i++) {
                CRC ^= ((int) bytes[i] & 0x000000ff);
                for (j = 0; j < 8; j++) {
                    if ((CRC & 0x00000001) != 0) {
                        CRC >>= 1;
                        CRC ^= POLYNOMIAL;
                    } else {
                        CRC >>= 1;
                    }
                }
            }
            return Integer.toHexString(CRC);
        }
    
    
         public static void main(String[] args) {
            byte[] s ={1,3,4,1,(byte) 205,1,18,(byte)235,(byte)173};
    
             System.out.printf("1111%s\r\n",CRC16(s));
            if (CRC16(s)!="00"){
                System.out.printf("2222%s\n",CRC16(s));
            }
        }
    
    展开全文
  • 循环冗余校验码

    千次阅读 多人点赞 2020-08-02 10:32:16
    循环冗余校验码简称CRC码,是目前使用非常广泛的数据校验方式.它不仅能校验传递过来的数据正确性,还能筛查出哪一位出现了错误.它的局限性是只能校验一位数据发生跳变,在现实世界当中数据发生跳变很大很大的概率是只有...

    前言

    循环冗余校验码简称CRC码,是目前使用非常广泛的数据校验方式.它不仅能校验传递过来的数据正确性,还能筛查出哪一位出现了错误.它的局限性是只能校验一位数据发生跳变,在现实世界当中数据发生跳变很大很大的概率只有一位发生变化,因此CRC码也拥有很大的发挥舞台.

     

    发送方数据处理

    前期准备

    假设发送方A向接收方B发送一串二进制数据101001.A需要计算出K位校验码,放在原始数据的后面一起发送给B.

    它们双方事先约定了一个私密的二项式G(x) = x^3 + x^2 +1,这个多项式用来计算校验码的位数和值.二项式的设计必须符合一定的规则,G(x)的最高项和最低项的系数必须为1.通过这个二项式我们首先可以获取K的大小,最高项x^3的幂指数3就等于K.另外通过二项式G(x)生成数据串G(x) = 1*x^3 + 1*x^2 + 0*x^1 +1*x^0 = 1101(将二项式前面的系数组合在一起就形成了数据串).数据串可以帮助我们计算出校验码的值.

    在有些情景下,我们无法获知多项式G(x).但直接得到了多项式生成后的数据串1101,此时怎么知道校验码有几位呢?用数据串的长度减去1就是K的大小.

    校验码的计算

    从上面描述可知二进制数据101001现在需要加上3位校验码,而用于校验的数据串也已经算出为1101.那通过这两个条件如何计算出校验码呢?在这里采用的是模2除法.模2除法它既不向上位借位,也不比较除数和被除数的相同位数值的大小,只要以相同位数进行异或运算即可.详细运算过程如下:

                                                      

    • 101001后面需要加上3位校验码,先添加3个0替代变成101001000,随后对1101做模二除法
    • 然后要看被除数的最高位是1还是0,是1商就上1,是0商就上0.此时被除数最高位是1,所以商为1.1再乘以1101和1010做异或运算
    • 第一轮计算余数为0111,舍弃最高位0,将后面的0填上就变成了1110.此时被除数变成了1110,最高位仍然为1,所以商仍然上1,将1101和1101做异或运算.结果0011,舍弃最高位0,将后面的1填上,被除数就变成了0111.依次类推算到最后一位的余数为001.
    • 只要本着被除数的最高位为几商就写几的原则进行异或运算后的余数的最高位一定是0,是0就可以舍弃,继续进行下面的运算.最后得出的最终余数001就是我们想要的3位检验码.
    • 通过这种模二除法有什么好处呢?比如说数101001后面加三个0后对1101做模二除法,最终会得到三位余数.然后将三位余数替换被除数的三个0再对1101做模二除法时,余数一定为0.换言之101001001再对1101做模二除法时余数一定为0.利用这个特性就可以做数据校验.

     

    接受方数据校验

    接受方B此时已经接受到了A传递过来的数据 101001001,并且他也知道事先约定的多项式g(x),他先通过g(x)计算出数据串为1101.他现在要开始做校验操作了.让101001001对1101做模二除法.

                                                    

    计算出来的余数为0,说明传送过来的数据正确.

    假如传送过来的数据101001001第二位发生了跳变,变成了101001011,那运算结果又会如何?

                                                    

    最后计算出来的余数为010,并不为0,说明数据发生了跳变.而010代表数字2,指明是第二位数据出现了错误.细心的同学肯定会发现3位校验码最多只能表示8种情况,而101001001有9个数字,在最多只有一位数字发生跳变的前提下,它的错误情况有九种,这样的话3位校验码就无法表示所有的出错情况了.比如说101001001最高位发生了跳变.

                                                 

    最高位发生跳变时,被除数的最高位为0,商上0继续运算,算到最后的余数为010.此时我们可以发现最高位(第9位)发现跳变时最后算出的余数是010,而第二位发生跳变时也是010,如果接收方算出了010,它也无法确定到底是第二位出错还是第九位出错,这样就只能检错而不能纠错.为了避免此类状况的发生,多项式g(x)和信息数据的长度设计显得尤为重要.

    展开全文
  • 本文主要阐述了循环冗余校验码的编码原理、算法,实现编码所用的程序及硬件电路。此外还对信道编码的一些信息作了一定的介绍,并给出了用单片机实现循环冗余校验码编码的全过程。
  • CRC循环冗余校验码

    2022-04-03 16:51:33
    CRC 循环冗余校验码 奇偶校验其实就是CRC校验的一种特例 循环冗余校验码由信息码n位和校验码k位构成。k位校验位拼接在n位数据位后面,n+k为循环冗余校验码的字长 具有检错、纠错能力的校验码 模二除法(模二除法的...

    cyclic redundancy check
    CRC 循环冗余校验码
    奇偶校验其实就是CRC校验的一种特例
    循环冗余校验码由信息码n位和校验码k位构成。k位校验位拼接在n位数据位后面,n+k为循环冗余校验码的字长
    具有检错、纠错能力的校验码
    模二除法(模二除法的结果不等于普通除法)
    当部分余数首位是1时商取1,反之商取0。然后每一位的减法运算是按位减,不产生借位
    例如:
    在这里插入图片描述
    如果要传输的数据为:1101011011

    除数设为:10011

    在计算前先将原始数据后面填上4个0:11010110110000,之所以要补0,后面再做解释。
    在这里插入图片描述

    从这个例子可以看出,采用了模2的加减法后,不需要考虑借位的问题,所以除法变简单了。最后得到的余数就是CRC 校验字。为了进行CRC运算,也就是这种特殊的除法运算,必须要指定个被除数,在CRC算法中,这个被除数有一个专有名称叫做“生成多项式”。
    生成多项式的最高阶数,就是要补0的个数。
    生成多项式的选取是个很有难度的问题,如果选的不好,那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了,对于我们这些使用者来说,只要把现成的成果拿来用就行了。
    计算方法:
    1.计算冗余位的位数,即生成多项式的最高阶数

    2.在信息位后补冗余位个数的0

    3.将第二步的结果与生成多项式相除,这里采用的除法叫做模2除法,就是只要部分余数的高位为1,便可商1 之后上下做的减法是异或。

    4.经过第三步不断地计算后得到余数
    将信息为后面补的0换成余数

    展开全文
  • CRC循环冗余校验码生成器 ,计算机网络课程作业,有bug,参考,共享。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
  • 循环冗余校验码的基本思想和构造方法
  • 校验码:奇偶校验码、海明码、循环冗余校验码
  • 这里不再赘述循环冗余校验码的编码方式,直接进入编程。为了便于使用,博主在其中添加了根据tkinter模块编写的GUI界面辅助。全部代码在文末 目录 一、根据生成多项式得到生成编码 二、延长初始序列 三、同位序列异或...
  • 在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码(CRC)。CRC也是给信息码加上几位校验码,以增加整个编码系统的码距和查错纠错能力。 本文介绍了循环冗余校验码的基本原理,内含例题。
  • CRC(Cyclic Redundancy Check)循环冗余校验码是数据通信领域中最常用的一种差错校验码,在早期的通信中运用广泛,因为早期的通信技术不够可靠(不可靠性的来源是通信技术决定的,比如电磁波通信时受雷电等因素的...
  • 描述一、CRC简介循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及...
  • CRC校验实用程序库在数据存储和数据通讯领域,为了保证数据的正确,就不得不采用检错的手段,下面这篇文章主要给大家介绍了关于Java中循环冗余校验(CRC32)实现的相关资料,需要的朋友可以参考借鉴,下面来一起看看...
  • 在数据链路层传送的帧当中,广泛的采用了循环冗余校验码(CRC)的检错技术。 需要注意的是,CRC的除法运算当中,执行的是模2运算 在数据后面加上加上的冗余码,是帧检验序列FCS(Frame Check Sequence) 且有...
  • 循环冗余校验码CRC

    2022-05-18 21:30:46
    循环冗余校验码(CRC),简称循环码,是一种常用的、具有检错、纠错能力的校验码,在早期的通信中运用广泛。循环冗余校验码常用于外存储器和计算机同步通信的数据校验。奇偶校验码和海明校验码都是采用奇偶检测为...
  • 校验码——CRC循环冗余校验码,码距,例题

    万次阅读 多人点赞 2020-06-19 17:12:21
    相关文章: 校验码——码距 校验码——海明码及码距 校验码——CRC循环冗余校验码 一、循环冗余校验码 ... 在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码... 循环冗余校验码(CRC)的基本原理是:在...
  • 奇偶校验码&海明码&循环冗余校验码

    千次阅读 2021-02-08 11:57:48
    文章目录一、奇偶校验码二、海明码三、循环冗余校验码 一、奇偶校验码 特点:能检错,但是不能纠错。 码距: 一个编码系统中任意两个合法编码(码字)之间不同的二进数位(bit)数叫这两个码字的码距,而整个编码...
  • 计算方式如下图所示,若除数为n位,待校验的数据为k位,则现在待校验的数据后面添加n-1个0,然后再和除数进行模2除法,所谓模2除法,其实就是将竖式运算中的减法改为异或运算。 C代码实现 #include <...
  • 循环冗余校验在一些传输协议中,发送端并不指出消息长度,而是采用结束标志,考虑以下几种差错:1)在消息之前,增加1个或多个0字节;2)消息以1个或多个连续的0字节开始,丢掉1个或多个0;3)在消息(包括校验码)之后,...
  • CRC循环冗余校验码原理解析(附实例)

    千次阅读 2019-11-26 15:32:06
    CRC循环冗余校验码是数据通信中的一种查错校验码。 2.CRC原理 CRC 算法的基本思想是将传输的数据[M(X)] 当做一个位数很长的数。将这个数除以另一个数[G(X)] ,得到的余数[R(X)] 作为校验数据附加到原数据后面,组成...
  • CAN总线中循环冗余校验码的原理及其电路实现 [日期:2004-12-8] 来源:电子技术应用 作者:李书瑞 李 明 石龙海 [字体:大 中 小]   摘要:在CAN网络中传输摄文时,噪声干扰或传输中断等因素往往使接收端...
  • 循环冗余校验码(CRC)详解

    千次阅读 2021-04-09 11:46:20
    循环冗余校验码(CRC)广泛应用于数据通信领域和磁介质存储系统中。它利用生成多项式为k个数据未产生r个校验位来进行编码,其编码长度为k+r。由此可知,循环冗余校验码是由两部分组成的,左边为信息码(数据),右边...
  • 奇偶校验码是 奇校验码 和 偶校验码 的统称. 它们都是通过在要校验的编码上加一位校验位组成. 如果是 奇校验 加上校验位后,编码中1的个数为 奇数个 如果是 偶校验 加上校验位后,编码中1的个数为 偶数个 水平奇偶校验...
  • 计算机网络中CRC循环冗余校验方法的代码。其中有很多注释,读起来不麻烦,能够很好的阅读理解,对大家对于CRC的实现有更好的帮助.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,091
精华内容 8,036
关键字:

循环冗余校验码

友情链接: 160160.rar