循环冗余校验码

循环冗余校验码的原理及应用循环冗余校验码（Cyclic Redundancy Check，简称CRC）是一种在数据传输中用于错误检测的校验码。

CRC的原理是通过在发送数据时附加一个校验值，接收端在接收数据时计算校验值，然后与发送端传递的校验值进行比较，如果两者一致，则说明数据传输没有错误，否则则存在数据错误。

CRC的应用非常广泛，包括网络传输、存储介质、通信等领域。

下面将详细介绍CRC的原理和应用。

1.原理：（1）生成多项式：CRC使用一个生成多项式进行计算。

该多项式可以是任意的，但在应用中通常使用一些标准的多项式。

生成多项式的位数确定了校验码的位数，通常为32位或64位。

（2）数据附加：在发送数据前，发送端会通过生成多项式对数据进行计算，生成一个校验码。

然后将校验码附加在原始数据的末尾。

（3）接收端计算：接收端在接收到数据后，通过与发送端使用同样的生成多项式对接收到的数据进行计算，生成一个接收端的校验码。

（4）校验比较：接收端的生成校验码与发送端传递的校验码进行比较，若一致，则说明数据传输没有错误；若不一致，则说明数据传输存在错误。

2.应用：（1）数据传输：CRC主要应用在网络传输领域，如以太网、Wi-Fi和蓝牙等。

在数据包发送前，发送端会对数据包进行CRC计算，然后将计算得到的校验码附加在数据包中。

接收端在接收到数据包后，再进行CRC计算，然后将计算得到的校验码与接收到的校验码进行比较，以判断是否存在传输错误。

（2）存储介质：CRC也应用在存储介质中，如硬盘驱动器、光盘等。

在数据存储时，CRC会被计算并存储在磁盘或光盘的头部或尾部。

在数据读取时，通过计算CRC来确保数据的完整性。

（3）通信：通信设备通常会使用CRC来检测数据的传输错误。

例如，调制解调器在发送数据前会计算CRC并将其附加在数据中，接收端在接收到数据后计算CRC，并与接收到的CRC进行比较。

（4）校验和验证：CRC也可以用于验证数据的完整性。

奇偶校验码、海明校验码和循环冗余校验码（CRC）奇偶校验码是 奇校验码 和 偶校验码 的统称.它们都是通过在要校验的编码上加⼀位校验位组成.如果是 奇校验 加上校验位后,编码中1的个数为 奇数个如果是 偶校验 加上校验位后,编码中1的个数为 偶数个⽔平奇偶校验是将若⼲字符组成⼀个信息块，对该信息块的字符中对应的位分别进⾏奇偶校验，下表给出了⽔平奇偶校验⽰例。

例:原编码 奇校验 偶校验0000 0000 1 0000 00010 0010 0 0010 11100 1100 1 1100 01010 1010 1 1010 0如果发⽣ 奇数 个位传输出错,那么编码中1的个数就会发⽣变化.从⽽校验出错误. 要求从新传输数据.⽬前应⽤的 奇偶校验码 有3种.⽔平奇偶校验码对每⼀个数据的编码添加校验位,使信息位与校验位处于同⼀⾏.垂直奇偶校验码把数据分成若⼲组,⼀组数据排成⼀⾏,再加⼀⾏校验码.针对每⼀⾏列采⽤ 奇校验 或 偶校验例: 有32位数据10100101 00110110 11001100 10101011垂直奇校验 垂直偶校验数据 10100101 1010010100110110 0011011011001100 1100110010101011 10101011校验为00001011 11110100⽔平垂直奇偶校验码就是同时⽤⽔平校验和垂直校验例:奇校验 奇⽔平 偶校验 偶⽔平数据 10100101 1 10100101 000110110 1 00110110 011001100 1 11001100 010101011 0 10101011 1校验 00001011 0 11110100 1然后是 海明校验码海明码也是利⽤奇偶性来校验数据的.它是⼀种多重奇偶校验检错系统,它通过在数据位之间插⼊k个校验位,来扩⼤码距,从⽽实现检错和纠错.设原来数据有n位,要加⼊k位校验码.怎么确定k的⼤⼩呢?k个校验位可以有pow(2,k) (代表2的k次⽅) 个编码,其中有⼀个代表是否出错.剩下pow(2,k)-1个编码则⽤来表⽰到底是哪⼀位出错.因为n个数据位和k个校验位都可能出错所以k满⾜ pow(2,k)-1 >= n+k设 k个校验码为 P1,P2…Pk, n个数据位为D0,D1…Dn产⽣的海明码为 H1,H2…H(n+k)如有8个数据位,根据pow(2,k)-1 >= n+k可以知道k最⼩是4那么得到的海明码是H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1然后怎么知道Pi校验哪个位呢.⾃⼰可以列个校验关系表海明码 下标 校验位组H1(P1) 1 P1H2(P2) 2 P2H3(D0) 1+2 P1,P2H4(P3) 4 P3H5(D1) 1+4 P1,P2H6(D2) 2+4 P2,P3H7(D3) 1+2+4 P1,P2,P3H8(P4) 8 P4H9(D4) 1+8 P1,P4H10(D5) 2+8 P2,P4H11(D6) 1+2+8 P1,P2,P4H12(D7) 4+8 P3,P4从表中可以看出P1校验 P1,D0,D1,D3,D4,D6P2校验 P2,D0,D2,D3,D5,D6P3校验 P3,D1,D2,D3,D7P4校验 P4,D4,D5,D6,D7其实上表很有规律很容易记要知道海明码Hi由哪些校验组校验可以把i化成 ⼆进制数 数中哪些位k是1,就有哪些Pk校验如H7 7=0111 所以由P1,P2,P3H11 11=1011 所以由P1,P2,P4H3 3=0011 所以由P1,P2那看看Pi的值怎么确定如果使⽤偶校验,则P1=D0 xor D1 xor D3 xor D4 xor D6P2=D0 xor D2 xor D3 xor D5 xor D6P3=D1 xor D2 xor D3 xor D7P4=D4 xor D5 xor D6 xor D7其中xor是异或运算奇校验的话把偶校验的值取反即可.那怎么校验错误呢.其实也很简单. 先做下⾯运算.G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6G3 = P3 xor D1 xor D2 xor D3 xor D7G4 = P4 xor D4 xor D5 xor D6 xor D7如果⽤偶校验那么 G4G3G2G1 全为0是表⽰⽆错误(奇校验全为1)当不全为0表⽰有错 G4G3G2G1 的⼗进制值代表出错的位.如 G4G3G2G1 =1010 表⽰H10(D5)出错了.把它求反就可以纠正错误了.下⾯举⼀个⽐较完全的例⼦:设数据为01101001,试⽤4个校验位求其偶校验⽅式的海明码.传输后数据为011101001101,是否有错?P1=D0 xor D1 xor D3 xor D4 xor D6=1 xor 0 xor 1 xor 0 xor 1=1P2=D0 xor D2 xor D3 xor D5 xor D6=1 xor 0 xor 1 xor 1 xor 1=0P3=D1 xor D2 xor D3 xor D7=0 xor 0 xor 1 xor 0=1P4=D4 xor D5 xor D6 xor D7=0 xor 1 xor 1 xor 0=0所以得到的海明码为0 1 1 0 0 1 0 0 1 1 0 1传输后为011101001101G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6=1G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6=0G3 = P3 xor D1 xor D2 xor D3 xor D7=0G4 = P4 xor D4 xor D5 xor D6 xor D7=1所以1001代表9即H9出错了,对它求反011001001101 和我们算的⼀样.由此可见 海明码 不但有检错还有纠错能⼒下⾯说下最后⼀种 CRC即 循环冗余校验码CRC码利⽤⽣成多项式为k个数据位产⽣r个校验位进⾏编码,其编码长度为n=k+r所以⼜称 (n,k)码. CRC码⼴泛应⽤于数据通信领域和磁介质存储系统中.CRC理论⾮常复杂,⼀般书就给个例题,讲讲⽅法.现在简单介绍下它的原理:在k位信息码后接r位校验码,对于⼀个给定的(n,k)码可以证明(数学⾼⼿⾃⼰琢磨证明过程)存在⼀个最⾼次幂为 n-k=r 的多项式g(x)根据g(x)可以⽣成k位信息的校验码,g(x)被称为 ⽣成多项式⽤C(x)=C(k-1)C(k-2)…C0表⽰k个信息位把C(x)左移r位,就是相当于 C(x)*pow(2,r)给校验位空出r个位来了.给定⼀个 ⽣成多项式g(x),可以求出⼀个校验位表达式r(x)C(x)*pow(2,r) / g(x) = q(x) + r(x)/g(x)⽤C(x)*pow(2,r)去除⽣成多项式g(x)商为q(x)余数是r(x)所以有C(x)*pow(2,r) = q(x)*g(x) + r(x)C(x)*pow(2,r) + r(x)就是所求的n位CRC码,由上式可以看出它是⽣成多项式g(x)的倍式.所以如果⽤得到的n位CRC码去除g(x)如果余数是0,就证明数据正确.否则可以根据余数知道 出错位 .在CRC运算过程中,四则运算采⽤ mod 2运算(后⾯介绍),即不考虑进位和借位.所以上式等价于C(x)*pow(2,r) + r(x) = q(x)*g(x)继续前先说下基本概念吧.1.多项式和⼆进制编码x的最⾼次幂位对应⼆进制数的最⾼位.以下各位对应多项式的各幂次.有此幂次项为1,⽆为0. x的最⾼幂次为r时, 对应的⼆进制数有r+1位例如g(x)=pow(x,4) + pow(x,3) + x + 1对应⼆进制编码是 110112.⽣成多项式是发送⽅和接受⽅的⼀个约定,也是⼀个⼆进制数,在整个传输过程中,这个数不会变.在发送⽅,利⽤ ⽣成多项式 对信息多项式做 模2运算 ⽣成校验码.在接受⽅利⽤ ⽣成多项式 对收到的 编码多项式 做 模2运算 校验和纠错.⽣成多项式应满⾜:a.⽣成多项式的最⾼位和最低位必须为1b.当信息任何⼀位发⽣错误时,被⽣成多项式模2运算后应该使余数不为0c.不同位发⽣错误时,应该使余数不同.d.对余数继续做模2除,应使余数循环.⽣成多项式很复杂不过不⽤我们⽣成下⾯给出⼀些常⽤的⽣成多项式表N K 码距d G(x)多项式 G(x)7 4 3 x3+x+1 10117 4 3 x3+x2+1 11017 3 4 x4+x3+x2+1 111017 3 4 x4+x2+x+1 1011115 11 3 x4+x+1 1001115 7 5 x8+x7+x6+x4+1 11101000131 26 3 x5+x2+1 10010131 21 5 x10+x9+x8+x6+x5+x3+1 1110110100163 57 3 x6+x+1 100001163 51 5 x12+x10+x5+x4+x2+1 10100001101011041 1024 x16+x15+x2+1 110000000000001013.模2运算a.加减法法则0 +/- 0 = 00 +/- 1 = 11 +/- 0 = 11 +/- 1 = 0注意:没有进位和借位b.乘法法则利⽤模2加求部分积之和,没有进位c.除法法则利⽤模2减求部分余数没有借位每商1位则部分余数减1位余数最⾼位是1就商1,不是就商0当部分余数的位数⼩于余数时,该余数就是最后余数.例 11101011)1100000101111101011101010110010(每商1位则部分余数减1位,所以前两个0写出)0000010(当部分余数的位数⼩于余数时,该余数就是最后余数)最后商是1110余数是010好了说了那么多没⽤的理论.下⾯讲下CRC的实际应⽤例: 给定的⽣成多项式g(x)=1011, ⽤(7,4)CRC码对C(x)=1010进⾏编码.由题⽬可以知道下列的信息:C(x)=1010,n=7,k=4,r=3,g(x)=1011C(x)*pow(2,3)=1010000C(x)*pow(2,3) / g(x) = 1001 + 011/1011所以r(x)=011所以要求的编码为1010011例2: 上题中,数据传输后变为1000011,试⽤纠错机制纠错.1000011 / g(x) = 1011 + 110/1011不能整除,所以出错了. 因为余数是110查1011出错位表可以知道是第5位出错.对其求反即可.循环冗余校验码CRC（Cyclic Redundancy Code）采⽤⼀种多项式的编码⽅法。

循环冗余校验码和海明码循环冗余校验码（CRC）是一种在数据传输中常用的纠错码，它利用多项式除法来进行计算，用来验证数据在传输过程中是否出现错误。

CRC码的计算过程比较简单，适用于高速传输和实时应用。

CRC码通常由一个生成多项式来生成，接收端也使用同样的生成多项式来进行校验，当数据在传输中出现错误时，接收端可以通过生成多项式计算来检测错误。

海明码（Hamming code）是一种可以进行错误检测和纠正的线性分组码，它可以通过添加冗余位来实现在传输过程中发生错误的位的纠正。

海明码在计算中利用了奇偶校验的原理，通过添加适当的奇偶位，可以实现对数据的错误检测和纠正。

海明码的计算过程相对复杂一些，但可以实现对数据的高效纠错。

CRC码和海明码在实际应用中有着各自的优缺点。

CRC码适用于高速传输和实时应用，它的计算速度快，但只能检测错误，并不能进行纠正。

而海明码可以进行错误检测和纠正，但计算复杂度较高，适用于传输速度较慢的场景。

在实际应用中，通常会根据具体的需求和场景来选择适合的错误检测和纠正技术。

在数据传输和存储领域，CRC码和海明码都有着广泛的应用。

在网络通信中，CRC码常用于以太网、Wi-Fi等高速传输中，用来验证数据的完整性。

而在存储系统中，海明码常用于磁盘和闪存等存储介质中，用来保证数据的可靠性和一致性。

这些应用场景都充分展现了CRC码和海明码在错误检测和纠正中的重要作用。

总的来说，CRC码和海明码都是常用的错误检测和纠正技术，它们在数据传输和存储中发挥着重要的作用。

虽然它们在计算复杂度、纠错能力等方面有所不同，但在实际应用中，可以根据具体的需求和场景来选择适合的技术。

通过合理的使用和结合，可以有效地保证数据的可靠传输和存储。

crc校验原理及代码CRC（循环冗余校验）是一种错误检测技术，通过对数据进行计算和比较，来确定数据是否被改变或破坏。

它主要用于数据通信中，确保数据的完整性。

CRC校验的原理是通过生成多项式来计算发送数据的校验码，并将校验码附加到数据末尾，接收方通过再次计算校验码来验证数据的完整性。

CRC采用二进制多项式除法的方式实现。

以下是一种常见的CRC校验算法，称为CRC-32算法，它使用32位的校验码：```pythondef crc32(data):crc = 0xFFFFFFFFfor byte in data:crc ^= bytefor _ in range(8):if crc & 1:else:crc >>= 1crc ^= 0xFFFFFFFFreturn crc```利用以上的代码，可以计算给定数据的CRC-32校验码。

下面是代码的解释：1. `crc32`函数的输入参数是字符串类型的数据。

2. `crc`变量初始值为0xFFFFFFFF，是32位全1的二进制数。

3.循环遍历输入数据中的每个字节，并进行计算。

4. `crc ^= byte`将校验码与当前字节进行异或操作。

5.在每个字节的8位中，循环判断最低位是否为17.若最低位为0，则直接右移一个位置。

8.在全部字节处理完成后，将校验码与0xFFFFFFFF进行异或操作，得到最终的校验码。

CRC校验在数据通信中非常常见，特别是在网络传输和存储媒介上。

它可以帮助检测传输过程中发生的位错误，提高数据的可靠性和完整性。

需要注意的是，CRC校验是一种错误检测机制，而不是错误纠正机制。

它只能告诉我们数据是否出现错误，而无法纠正错误。

若数据被改变或破坏，则接收方可以要求重新发送数据。

循环冗余校验码的原理及应用循环冗余校验码（Cyclic Redundancy Check, CRC）是一种常见的错误检测技术，用于验证数据传输的准确性。

它通过在发送数据之前附加一个冗余的校验码，并在接收端对接收到的数据进行校验，以便快速检测并纠正传输中的错误。

1.将每个待发送的数据与一个固定的生成多项式进行除法运算。

2.将除法运算的余数作为校验码添加到发送的数据后面。

3.接收端在接收到数据后，同样使用相同的生成多项式进行除法运算。

4.若接收端得到的余数为0，则说明数据传输没有错误；否则，说明数据传输中出现了错误。

1.网络通信：在计算机网络中，常使用CRC校验码来验证数据包的完整性，防止在传输过程中数据被篡改或错误。

2.存储设备：在硬盘驱动器、固态硬盘等存储设备中，使用CRC校验码来检测存储数据的正确性，防止数据损坏。

3.移动通信：在移动通信中，如GSM、CDMA、LTE等系统中，使用CRC校验来保证无线信号的可靠传输。

4.协议栈：在各种网络协议中，如以太网、WiFi、TCP/IP等，CRC校验码被用于保证数据传输的正确性。

5.数据传输设备：在串行通信中，如串口通信、RS-232等，常使用CRC校验码来验证数据传输。

1.高检测准确率：使用CRC校验码可以有效检测常见的错误类型，如单个位错、双比特错等。

2.高效性能：CRC算法的计算速度快，在实际应用中对系统的性能要求较低。

3.算法简单：CRC算法的实现比较简单和高效，适用于各种硬件和软件平台。

4.容错能力强：CRC校验码可以检测出较长的比特序列错误，如在存储设备中检测大容量文件的正确性。

5.灵活性：通过选择不同的生成多项式，CRC校验码可以适用于不同的数据长度和校验要求。

然而，循环冗余校验码也有一些不足之处，如：1.无法纠正错误：CRC校验码只能检测错误，而无法对错误数据进行纠正。

2.相同残余：不同的错误数据可能会产生相同的CRC校验码，从而导致无法检测到错误。

4．4．6 循环冗余校验码循环冗余校验码（Cyclic Redundancy Check ,CRC）是一种检错、纠错能力很强的数据校验码，主要用于计算机网络、同步通信及磁表面存储器等应用场合。

循环冗余校验码是通过除法运算来建立有效信息位和校验位之间的约定关系。

假定，待编码的有效信息以多项式M（X）表示，将它左移若干位后，用另一个约定的多项式G（X）去除，所产生的余数就是校验位。

有效信息位与校验位相拼接就构成了CRC码。

当接收方收到发来的CRC码后，他仍用约定的多项式G（X）去除，若余数为0，表明该代码接收无误；若余数不为0，表明某一位出错，再进一步由余数值确定出错的位置，并予以纠正。

1．循环冗余校验码的编码方法如图3-7所示，循环冗余校验码由两部分组成，左边为信息位，右边为校验位。

若信息位为N位，校验位为K位，则该校验码被称为（N ＋K，N）码。

循环冗余校验码的编码步骤如下：（1）将待编码的N位有效信息位表示为一个n－1阶的多项式M（X）。

（2）将M（X）左移K位，得到M （X）·X k（K由预选的K＋1位的生成多项式G（X）决定）。

（3）用一个预选好的K＋1位的生成多项式G（X）对M（X）·X k 作模2除法。

（4）把左移K位后的的有效信息位与余数作模2加法，即形成长度为N＋K的CRC码。

M（X）·X k＋R(X) ＝Q(X)·G(X) 这里，需介绍一下模2的运算规则。

模2运算不考虑加法的进位和减法的借位，即0±0＝0，0±1＝1，1±0＝1，1±1＝0。

作模2除法时，上商的原则是当部分余数首位是1时（即使被除数比除数小），商取1，反之商取0，然后按模2加减求得余数。

当被除数逐步除完时，最终的余数比除数少一位，此余数就是校验位。

例3．26：选择生成多项式为G(X)＝X3＋X＋1，请把4位有效信息1100编码成CRC码。

循环冗余码(crc)及计算方法循环冗余校验码，简称CRC（Cyclic Redundancy Check），是一种数据传输异常检测方法，已经被广泛应用于数据链路层和物理层等数据通信领域。

在传输过程中，所传输的信息数据可能被多次修改，或者有噪声或干扰。

这就导致了所接收到的数据并不是最初发出的特定数据，使得传输失败或受到破坏。

作为一种效果比较好的校验技术，CRC校验码技术就派上用场了，它通过数据发送者事先计算出一串特定长度（字节）的校验码放入发送的数据帧中，接收者收到数据帧时会对数据帧进行检测，以查看接收的数据帧校验码与数据是否原来发出数据时相同，如果不同，就表示数据帧损坏，接收者通知发送者重发。

CRC校验码单元通过将发出方所发送的原始数据（数据帧data）与一个固定长度的多项式（CRC多项式）按位依次做按位异或的运算，来生成新的检验码，称之为CRC校验码（check）。

如果接收res方收到了与发送snd方发出的数据帧内容相同的数据帧，那么接收res方也可以使用CRC多项式对收到的数据帧做相同的计算，如果生成的CRC校验码与原始数据帧中存储的CRC校验码相同，说明数据接收是无误的。

如果不一致，说明中间可能发生了数据传输错误，数据接收存在错误，这可能是由于传输和接收途经的环境中有噪声或是由于数据本身的丢失/"随机"改变或添加其他数据导致的。

CRC校验码的计算方法通常有两种，查表法和无查表法。

查表法即在发送前定义好一张查表，根据查表给出CRC-Code。

无查表法是一种比较复杂的算法，该法首先根据CRC多项式，将多项式拆解成一个个单项式数及其系数，然后，根据定义式进行模2加，一直进行运算，得出最后的CRC校验值，该校验值就作为原来数据在发送前附加上去。

CRC校验码是目前数据链路层较为安全的一种编码技术，它可以在较大的概率内检测出传输中的比特错误。

而且，CRC校验的编码效率高，而且相当安全，是一种能够在低价值硬件中实现的有效的编码和校验技术。