海明码和CRC编码的图解和详细计算过程

1、奇偶校验码二进制数据经过传送、存取等环节，会发生误码（1变成0或0变成1），这就有如何发现及纠正误码的问题。

所有解决此类问题的方法就是在原始数据（数码位）基础上增加几位校验（冗余）位。

一、码距一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit ）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。

如图1所示的一个编码系统，用三个bit 来表示八个不同信息中。

在这个系统中，两个码字之间不同的bit 数从1到3不等，但最小值为1，故这个系统的码距为1。

如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。

例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收机仍将认为011是正确的信息。

然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图图 1图 2注意，图8-2的8个码字相互间最少有两bit 因此，如果任何信息的一个数位被颠倒，码字，接收机能检查出来。

例如信息是1001，误收为1011接收机知道发生了一个差错，因为1011不是一个码字（表中没有）。

然而，差错不能被纠正。

的，正确码字可以是1001，1111，0011或1010能确定原来到底是这4个码字中的那一个。

也可看到，在这个系统中，偶数个（2或4）差错也无法发现。

为了使一个系统能检查和纠正一个差错，必须至少是“3”。

最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。

错和检错能力的进一步提高需要进一步增加码字间的最小距离。

图8-3的表概括了最小距离为1至7的码的纠错和图3检错能力。

码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。

所以，选择码距要取决于特定系统的参数。

数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。

要有专门的研究来解决这些问题。

二、奇偶校验奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。

奇偶校验码、海明校验码和循环冗余校验码（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码和海明码都是常用的错误检测和纠正技术，它们在数据传输和存储中发挥着重要的作用。

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

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

海明码详解这两天也在研究海明码的问题，把我的理解说给你吧，按照我说的可以顺利得到海明码步骤：一、确定校验码的位数k二、确定校验码的位置三、数据的位置四、求出校验位的值首先，海明码的作用是：在编码中如果有错误，可以表达出第几位出了错，二进制的数据只有0和1，修改起来很容易，求反即可，这需要加入几个校验位。

重要的知识点：海明码的组成，不是简单的在后面加上校验位，海明码≠数据位+检验位那检验位该怎么加呢？它是根据总的位置来加的，加在【2的几次幂】的位置上，这个位置不是我们通常的从右向左数位置，刚好相反，是从左右如下图：P是校验位， D是数据位：原始的数据是：101101 校验位是插到了 1 2 4 8这几个位置上的。

位置M1M2M3M4M5M6M7M8M9M10甲P1 P2 D1P3 D2D3D4P4 D5D6乙10 110 1步骤一、确定校验码的位数k公式：m+k+1≤2^k (m是数据位的位数，K是要加的校验位的位数数据长是4位，校验码就是3位4+k+1≤2^kK最小只能是3数据长是5,6,7,8,9,校验码就是4位5+k+1≤2^kK最小就只能取4101101 数据位是6位，那校验位应该是4位，那总位数是：6+4=10位步骤二、确定校验码的位置位置M1M2M3M4M5M6M7M8M9M10甲P1 P2 D1P3 D2D3D4P4 D5D6乙10 110 1（图1）注意：【位置是从左----------右编码】（网上好多都反了，都是从右往左的，这应该是错的）校验位就插在2的幂次方的位置上。

4个检验位就是插到，2的0次方=1，2的1次方=2，2的2次方=4，2的3次方=8的位置上。

始上（图1）步骤三、数据的位置数据位置就按顺序写入进去就OK了，不要写到校验位就是的了。

步骤四、求出校验位的值也就是求图1中：p1 p2 p3 p4 的值。

那这几个数该如何求值呢？这里就要引进一个线性码的概念了，就是这4位校验码和图1中的那些位置上的数有关系呢？这里有一个进制转换的问题要先解决：因为是4位校验码，所以我们可以s4 s3 s2 s1 这个数来表示这个4位校验码，也就是p4 p3 p2 p1M1号位是十进制的1 转成四位二进制数就是：0001 即M1 和s1有关系同样的道理M2 变成四位二进制数： 0010 0010----s4 s3 s2 s1 s2的位置上是1 ，所以M2和S2有关系。

海明码编码计算、检错和纠错原理解析一、海明码检错/纠错基本思想海明码（Hamming Code）是一个可以有多个校验位，具有检测并纠正一位错误代码的纠错码，所以也仅用于信道特性比较好的环境中，如以太局域网。

它的检错、纠错基本思想如下：（1）将有效信息按某种规律分成若干组，每组安排一个校验位通过异或运算进行校验，得出具体的校验码（2）在接收端同样通过异或运算看各组校验结果是否正确，并观察出错的校校组，或者多个出错的校验组的共同校验位，得出具体的出错比特位（3）对错误位取反来将其纠正二、海明码计算海明码计算要按以下步骤来进行：计算校验码位数→确定校验码位置→确定校验码1. 计算校验码位数假设用N表示添加了校验码位后整个传输信息的二进制位数，用K代表其中有效信息位数，r表示添加的校验码位数，它们之间的关系应满足：N=K＋r≤2r－1（是为了确保r位校验码能校验全部的数据位，因为r位校验码所能表示的最大十进制数为2r-1，同时也确保各位码本身不被其他校验码校验）信息码位数12~45~1112~2627~5758~120121~247校验码位数2 3 4 5 6 7 82. 确定校验码位置海明码的校验码的位置必须是在2n次方位置（n从0 开始，分别代表从左边数起分别是第1、2、4、8、16……），信息码也就是在非2n次方位置3. 确定校验码校验位置选择原则：第i位校验码从当前校验码位开始，每次连续校验i位后再跳过i位，然后再连续校验i位，再跳过i位，以此类推。

确定每个校验码所校验的比特位：P1校验码位校验的码字位为：第1位（也就是P1本身）、第3位、第5位、第7位、第9位、第11位、第13位、第15位，……。

P2校验码位校验的码字位为：第2位（也就是P2本身）、第3位，第6位、第7位，第10位、第11位，第14位、第15位，……。

P3校验码位校验的码字位为：第4位（也就是P4本身）、第5位、第6位、第7位，第12位、第13位、第14位、第15位，第20位、第21位、第22位、第23位，……。

软考历程（2）——海明码校验这两天学了校验码，在计算机系统基础知识这块，校验还是挺重要的。

这⾥涉及到的校验码有三种：奇偶校验码（Parity Code）海明码(Hamming Code)循环冗余检验码（CyclicRedundancy Check，CRC）1.奇偶校验码这是⼀种最简单最有效的校验⽅法，通过在编码中添加⼀位校验位。

使1的个数为偶数（偶校验）或奇数（奇校验）。

从⽽使码距变为2。

奇校验能够检測代码中奇数位出错的编码，不能够发现偶数位出错的情况。

2.海明码这是利⽤奇偶性来检错和纠错的校验⽅法。

其构成⽅法为：在数据位之间插⼊k个校验位。

求海明码的过程能够分为下⾯⼏个步骤：（1）依据数据位n，确定校验位k, n和k满⾜关系：2k-1≥n+k；（2）设海明码为H1。

H2。

H3。

……H n+k,将校验位依次放在20,21,22，2i-1……的位置上。

（3）将数据位由低位到⾼位依次放在海明码剩余的位置上。

（4）找出每⼀个校验位所校验的数据位，⽅法为：第⼀个校验位隔⼀位校验⼀位。

第⼆个校验位隔两位校验两位，第三个校验位隔三位校验三位……每⼀个校验位都校验它⾃⾝；（5）分别对每⼀个校验位所校验的数据位做抑或运算，结果为校验位的值。

（6）将所得校验位的值填⼊当中，即得海明码。

3.循环冗余校验码它由两部分组成。

左边为信息码。

右边为校验码。

校验码是由信息码产⽣的，求CRC编码时，採⽤模2运算。

多⽤于数据通信领域和磁介质存储领域，在參加的上个中⾕项⽬中就⽤到了CRC校验，那会⼉对于这个东东还认为蛮深奥的呢！。

crc码的计算过程CRC码，即循环冗余校验码，是一种确保高速数据传输系统数据准确性的重要手段。

CRC码能够检测出那些难以检测的二进制错误，比如噪声造成的中间数据错误，以及数据传输过程中被误码改变的数据。

本文将介绍CRC码的计算过程。

CRC码的计算过程需要通过三步：首先，生成CRC码；其次，在数据传输过程中，将CRC码加入到数据中；最后，接收端进行CRC校验，用来确认数据传输过程中没有发生错误。

首先，生成CRC码。

CRC码是根据特定的多项式计算出来的，它由一系列位（bit）组成，长度根据不同的应用而定，一般是8位或者16位。

首先，把要发送的数据（Data）按照一定的格式分成多个字节，每个字节包含8 bit；接着，把CRC码的位数（n）也按照一定的格式分成多个字节，每个字节也包含8 bit；最后，根据特定的多项式，将其中的每一个字节进行相关操作，计算出最终的CRC校验值。

其次，在数据传输过程中，将CRC码加入到数据中。

当要发送的数据以及对应的CRC码计算完成以后，此时发送端才开始正式发送数据。

在发送之前，发送端会将数据和CRC码进行组合，并把CRC码添加到数据的末尾。

这样，在数据传输过程中，接收端就能够接收到CRC码，从而可以进行CRC校验。

最后，接收端进行CRC校验，以确保数据的准确性。

接收端收到的数据包含有CRC码，但是这个CRC码是否正确，只有进行CRC校验才能确定。

因此，接收端首先会把收到的数据和CRC码分别存放在不同的寄存器中，并且以相同的格式进行存放；接着，根据特定的多项式，对收到的数据以及CRC码进行比较，计算出一个新的CRC码，如果两个CRC码不相同，则表明在传输过程中发生了错误；如果两个CRC码相同，则表明传输的数据是没有错误的。

综上所述，CRC码的计算过程共分为三步：首先，根据特定的多项式生成CRC码；其次，在传输过程中将CRC码加入到数据中；最后，接收端进行CRC校验，以确保数据准确性。

1、奇偶校验码二进制数据经过传送、存取等环节，会发生误码（1变成0或0变成1），这就有如何发现及纠正误码的问题。

所有解决此类问题的方法就是在原始数据（数码位）基础上增加几位校验（冗余）位。

一、码距一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。

如图1所示的一个编码系统，用三个bit来表示八个不同信息中。

在这个系统中，两个码字之间不同的bit数从1到3不等，但最小值为1，故这个系统的码距为1。

如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。

例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收机仍将认为011是正确的信息。

然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图图 1图 2注意，图8-2的8个码字相互间最少有两bit因此，如果任何信息的一个数位被颠倒，码字，接收机能检查出来。

例如信息是1001，误收为1011接收机知道发生了一个差错，因为1011不是一个码字（表中没有）。

然而，差错不能被纠正。

的，正确码字可以是1001，1111，0011或1010能确定原来到底是这4个码字中的那一个。

也可看到，这个系统中，偶数个（2或4）差错也无法发现。

为了使一个系统能检查和纠正一个差错，必须至少是“3”。

最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。

错和检错能力的进一步提高需要进一步增加码字间的最小距离。

图8-3的表概括了最小距离为1至7的码的纠错和检错能力。

图3 码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。

所以，选择码距要取决于特定系统的参数。

数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。

要有专门的研究来解决这些问题。

二、奇偶校验奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。

一、CRC编码1、已知多项式和原报文，求CRC编码，如：使用多项式G(x)=x^5 + x^4 + x +1,对报文进行CRC编码，则编码后的报文是什么？方法与步骤：步骤1：对报文，在末尾添加所给多项式的最高次阶个0，如本题为x^5，则添加5个0，变为：。

步骤2：由多项式G(x)=x^5 + x^4 + x +1，得其阶数为1的二进制编码为：110011。

步骤3：步骤1中求得的对步骤2中求得的110011进行模二除法，所得到的余数即为校验码，把校验码添加在原报文尾部即为所求的编码报文，具体如下：2.已知道接收到的CRC编码，求原编码或判断是否出错，如：已知G(x)=x^5 + x^4 + x +1，接收的为，问是否出错步骤一：由多项式G(x)=x^5 + x^4 + x +1，得其阶数为1的二进制编码为：110011。

步骤二：用接收的报文对步骤一的110011进行模二除法，看余数是否为0，如为0则正确，如不为0，则出错，计算余数为1，则出错。

如下图：二、海明码1.求海明码，如：求1011海明码。

步骤一：求校验码位数r，公式为：2^r ≥r+k+1的最小r。

题目中为2^3≥3+4+1,所以取r=3，即校验码为3位。

步骤二：画图，并把原码的位编号写成2的指数求和的方式,其中位编号长度为原码和校验码个数之和，从1开始。

校验码插在2的阶码次方的位编号下，且阶小于r。

如下：原码的位编号写成2的指数求和：7=2^2+2^1+2^0;6=2^2+2^1;5=2^2+2^0;3=2^1+2^0;步骤三：求校验位，即每个校验位的值为步骤二中“原码的位编号写成2的指数求和”式子中相应2的阶出现的位编号下原码的值异或。

即：r0=I4异或I2异或I1=1；(2^0次出现在7，5，3位，其对应的值为I4，I2，I1) r1=I4异或I3异或I1=0；(2^1次出现在7，6，3位，其对应的值为I4，I3，I1) r2=I4异或I3异或I2=0；(2^0次出现在7，6，5位，其对应的值为I4，I3，I2) 把r0,r1,r2带入海明码，得所求的海明码为：10101012.已知海明码，求原码或判断是否出错并改正错位，如：信息位8位的海明码，接收时，判断是否出错，并求出发送端信息位。

计算机组成原理--海明码的编码和校验⽅法（易懂）海明码（也叫汉明码）具有⼀位纠错能⼒。

本⽂以1010110这个⼆进制数为例解释海明码的编码和校验⽅法。

编码 确定校验码的位数x 设数据有n位，校验码有x位。

则校验码⼀共有2x种取值⽅式。

其中需要⼀种取值⽅式表⽰数据正确，剩下2x-1种取值⽅式表⽰有⼀位数据出错。

因为编码后的⼆进制串有n+x位，因此x应该满⾜2x-1 ≥　n+x 使不等式成⽴的x的最⼩值就是校验码的位数。

在本例中，n=7，解得x=4。

确定校验码的位置 校验码在⼆进制串中的位置为2的整数幂。

剩下的位置为数据。

如图所⽰。

位置1234567891011内容x1x21x3010x4110 求出校验位的值 以求x2的值为例。

为了直观，将表格中的位置⽤⼆进制表⽰。

位置00010010001101000101011001111000100110101011内容x1x21x3010x4110 为了求出x2,要使所有位置的第⼆位是1的数据（即形如**1*的位置的数据）的异或值为0。

即x2^1^1^0^1^0 = 0。

因此x2 = 1。

同理可得x1 = 0, x3 = 1, x4 = 0。

位置00010010001101000101011001111000100110101011内容01110100110 因此1010110的海明码为01110100110。

校验 假设位置为1011的数据由0变成了1，校验过程为： 将所有位置形如***1, **1*, *1**, 1***的数据分别异或。

***1: 0^1^0^0^1^1 = 1 **1*: 1^1^1^0^1^1 = 1 *1**: 1^0^1^0 = 0 1***: 0^1^1^1 = 1 以上四组中，如果⼀组异或值为1，说明该组中有数据出错了。

***1 **1* 1***的异或都为1，说明出错数据的位置为1011。

海明码简单分析确定校验位个数海明码的码组长度需要符合：2^r – 1 （r代表校验位个数）为什么是这个公式呢？因为：只有这样才能保证校验位⾜够覆盖整个需要校验的码组。

1、奇偶校验码二进制数据经过传送、存取等环节，会发生误码（1变成0或0变成1），这就有如何发现及纠正误码的问题。

所有解决此类问题的方法就是在原始数据（数码位）基础上增加几位校验（冗余）位。

一、码距一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit ）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。

如图1所示的一个编码系统，用三个bit 来表示八个不同信息中。

在这个系统中，两个码字之间不同的bit 数从1到3不等，但最小值为1，故这个系统的码距为1。

如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。

例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收机仍将认为011是正确的信息。

然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图图 1图 2注意，图8-2的8个码字相互间最少有两bit 因此，如果任何信息的一个数位被颠倒，码字，接收机能检查出来。

例如信息是1001，误收为1011接收机知道发生了一个差错，因为1011不是一个码字（表中没有）。

然而，差错不能被纠正。

的，正确码字可以是1001，1111，0011或1010能确定原来到底是这4个码字中的那一个。

也可看到，这个系统中，偶数个（2或4）差错也无法发现。

为了使一个系统能检查和纠正一个差错，必须至少是“3”。

最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。

错和检错能力的进一步提高需要进一步增加码字间的最小距离。

图8-3的表概括了最小距离为1至7的码的纠错和图3检错能力。

码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。

所以，选择码距要取决于特定系统的参数。

数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。

要有专门的研究来解决这些问题。

二、奇偶校验奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。

海明码距离及检错纠错问题和CRC校验海明校验码两个长度相等的字符串的海明距离是在相同位置上不同的字符的个数，也就是将⼀个字符串替换成另⼀个字符串需要的替换的次数。

海明距离与检错和纠错的关系:1.海明距离为d+1的编码能检测出d位差错。

因为在距离为d+1的检验码中，只改变d位的值，不可能产⽣另⼀个合法码。

如奇偶校验码，海明距离为2，能查出单个错。

2.海明距离为2d+1的编码，能纠正d位差错。

因为此时，如果⼀个码字有d位发⽣差错，它仍然距离原来的码字距离最近，可以直接恢复为该码。

（奇偶校验码，海明距离为2，可以检出单个错）纠正单⽐特错的冗余位下界,m为数据位数，r为校验位数 (m+R+1)≤2^r1.每⼀个码字从左到右编号，最左边为第1位2.校验位和数据位凡编号为2的乘幂的位是校验位，如1、2、4、8、16、……。

其余是数据位，如3、5、6、7、9、……。

3.每⼀个校验位设置根据：包括⾃⼰在内的⼀些位的集合的奇偶值(奇数或偶数)。

海明码纠错过程(只纠错1位)⾸先将差错计数器置“0”。

当海明码数据到达接收端后，接收端逐个检查各个校验位的奇偶性。

如发现某⼀校验位和它所检测的集合的奇偶性不正确，就将该检验位的编号加到差错计数器中。

待所有校验位核对完毕：若差错计数器仍为“0”值，则说明该码字接收⽆误。

⾮“0”值，差错计数器的值为出错位的编号，将该位求反就可得到正确结果。

循环冗余检错码CRC可以检测到所有长度⼩于等于r的突发错误⼴泛⽤于各种⽹络，⼏乎所有的局域⽹使⽤CRC编码时发送⽅和接收⽅必须预先商定⼀个⽣成多项式G(x),假设有⼀个m为的帧M(x)，使⽤G(x)⽣成的帧的步骤如下：假设G(x)的阶为r，那么M(x)在末尾添加r个0，得到 m+r位的位模式。

利⽤模2出发，⽤G(x)去除 ,得到对应的余数（总是⼩于等于r位）。

利⽤减去(模2减法)第2步中得到的余数，得到的位模式就是即将被传输的带校验和的帧⼩结：Sender在数据帧的低端加上r个零，对应多项式为XrM(x)采⽤模2除法，⽤G(x)去除XrM(x)，得余数采⽤模2减法，⽤XrM(x)减去余数，得到带CRC校验和的帧Receiver⽤收到的幀去除以G（x）为零：⽆错误产⽣。

1、奇偶校验码二进制数据经过传送、存取等环节，会发生误码（1变成0或0变成1），这就有如何发现及纠正误码的问题。

所有解决此类问题的方法就是在原始数据（数码位）基础上增加几位校验（冗余）位。

一、码距一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit ）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。

如图1所示的一个编码系统，用三个bit 来表示八个不同信息中。

在这个系统中，两个码字之间不同的bit 数从1到3不等，但最小值为1，故这个系统的码距为1。

如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。

例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收机仍将认为011是正确的信息。

然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图图 1图 2注意，图8-2的8个码字相互间最少有两bit 因此，如果任何信息的一个数位被颠倒，码字，接收机能检查出来。

例如信息是1001，误收为1011接收机知道发生了一个差错，因为1011不是一个码字（表中没有）。

然而，差错不能被纠正。

的，正确码字可以是1001，1111，0011或1010能确定原来到底是这4个码字中的那一个。

也可看到，这个系统中，偶数个（2或4）差错也无法发现。

为了使一个系统能检查和纠正一个差错，必须至少是“3”。

最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。

错和检错能力的进一步提高需要进一步增加码字间的最小距离。

图8-3的表概括了最小距离为1至7的码的纠错和图3检错能力。

码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。

所以，选择码距要取决于特定系统的参数。

数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。

要有专门的研究来解决这些问题。

二、奇偶校验奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。

1.海明码概念：海明码是一种多重(复式)奇偶检错系统。

它将信息用逻辑形式编码，以便能够检错和纠错。

用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。

每一个这种奇偶位被编在传输码字的特定位置上。

实现得合适时，这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能把它分离出来。

它必须满足以下瓜葛式：2^r=n+1或2^r=k+r+1。

海明码的编码效率为：R=k/(k+r)(式中k为信息位位数，r为增长冗余位位数)1.>表名称的词诠释：码字：表示一个帧包孕的k个数据位，r个校验位，n=k+r，则此n比特单元称为n位码字。

码距：两个码字之间差别的比特位数量。

例如，000与010的码距为1；000与110的码距为2；000与111的码距为3。

2.海明码的步骤：1.>0确定最小的校验位数k，将它们记成D1、D2、…、Dk，每个校验位符合不同的奇偶测试规定。

2．>原有信息和k个校验位一起编成长为m+k位的新码字。

选择k校验位（0或1）以满足必要的奇偶条件。

3．>对所接收的信息作所需的k个奇偶检查。

4．>如果所有的奇偶检查结果均为正确的，则认为信息无错误。

如果发现有一个或多个错了，则错误的位由这些检查的结果来唯一地确定。

3海明码的编码规则1.>每一个校验位Ri被分配在海明码的第2的i次的位置上，2.>海明玛的每中央电视台位(Hi)是由多个/一个校验值进行校验的，被校验码的位置码是所有校验这位的校验位位置码之和。

4海明码的特点1.>如果两个码字之间的码距为d，则需要d个比特就可以把一个码字转换成另外一个码字2.>为了检查出d个纰缪(单比特错)，需要使用的码距为d+一个编码3.>为了纠正d个纰缪，需要使用码间隔为2d+1的编码5编码步调(1)按照信息位数，确定校验位数，2的k次方≥k+r+1，其中，k为信息位数，r 为校验位数。

一、CRC编码1、已知多项式和原报文，求CRC编码，如：使用多项式G(x)=x^5 + x^4 + x +1,对报文10100110进行CRC编码，则编码后的报文是什么？方法与步骤：步骤1：对报文10100110，在末尾添加所给多项式的最高次阶个0，如本题为x^5，则添加5个0，变为：1010011000000。

步骤2：由多项式G(x)=x^5 + x^4 + x +1，得其阶数为1的二进制编码为：110011。

步骤3：步骤1中求得的1010011000000对步骤2中求得的110011进行模二除法，所得到的余数即为校验码，把校验码添加在原报文尾部即为所求的编码报文1010011011000，具体如下：2.已知道接收到的CRC编码，求原编码或判断是否出错，如：已知G(x)=x^5 + x^4 + x +1，接收的为1010011011001，问是否出错？步骤一：由多项式G(x)=x^5 + x^4 + x +1，得其阶数为1的二进制编码为：110011。

步骤二：用接收的报文1010011011001对步骤一的110011进行模二除法，看余数是否为0，如为0则正确，如不为0，则出错，计算余数为1，则出错。

如下图：二、海明码1.求海明码，如：求1011海明码。

步骤一：求校验码位数r，公式为：2^r ≥r+k+1的最小r。

题目中为2^3≥3+4+1,所以取r=3，即校验码为3位。

步骤二：画图，并把原码的位编号写成2的指数求和的方式,其中位编号长度为原码和校验码个数之和，从1开始。

校验码插在2的阶码次方的位编号下，且阶小于r。

如下：原码的位编号写成2的指数求和：7=2^2+2^1+2^0;6=2^2+2^1;5=2^2+2^0;3=2^1+2^0;步骤三：求校验位，即每个校验位的值为步骤二中“原码的位编号写成2的指数求和”式子中相应2的阶出现的位编号下原码的值异或。

即：r0=I4异或I2异或I1=1； (2^0次出现在7，5，3位，其对应的值为I4，I2，I1)r1=I4异或I3异或I1=0； (2^1次出现在7，6，3位，其对应的值为I4，I3，I1)r2=I4异或I3异或I2=0； (2^0次出现在7，6，5位，其对应的值为I4，I3，I2)把r0,r1,r2带入海明码，得所求的海明码为：10101012.已知海明码，求原码或判断是否出错并改正错位，如：信息位8位的海明码，接收110010100000时，判断是否出错，并求出发送端信息位。

海明码的计算：码距：是不同码字的海明距离的最小值。

（1）可查出多少位错误：可以发现“≤码距-1”位的错误（2）可以纠正多少位错误：可以纠正“<码距/2”位的错误，因此如果要能纠正n位错误，则所需最小的码距是：2n+1。

计算：海明码是放置在2的幂次位上的即1,2,4,8,16,32,而对于信息位为m的原始数据，需加入k位的校验码，它满足m+k+1<.海明码的求法：一、有一种简单的方法，则是从第1位开始，遇到校验位留下空格。

如原始信息为101101100,并采用偶校验：1011011001 2 3 4 5 6 7 8 9 10 11 12 13二、然后概据以下公式填充校验位：1，2，4，8B1=B3⊕B5⊕B7⊕B9⊕B11⊕B13=1⊕0⊕1⊕0⊕1⊕0=1B2=B3⊕B6⊕B7⊕B10⊕B11=1⊕1⊕1⊕1⊕1=1B4=B5⊕B6⊕B7⊕B12⊕B13=0⊕1⊕1⊕0⊕0=0B8=B9⊕B10⊕B11⊕B12⊕B13=0⊕1⊕1⊕0⊕0=0三、最后将结果填入，得到结果：11100110011001 2 3 4 5 6 7 8 9 10 11 12 13海明码的纠错：如下给出一个加入了校验码的的信息，并说明有一位的错误，要找出错误位：11100110010001 2 3 4 5 6 7 8 9 10 11 12 13将B1，B2，B4，B8代入上式的公式中：B1=B1⊕B3⊕B5⊕B7⊕B9⊕B11⊕B13=1⊕1⊕0⊕1⊕0⊕0⊕0=1 B2=B2⊕B3⊕B6⊕B7⊕B10⊕B11=1⊕1⊕1⊕1⊕1⊕0=1B4=B4⊕B5⊕B6⊕B7⊕B12⊕B13=0⊕0⊕1⊕1⊕0⊕0=0B8=B8⊕B9⊕B10⊕B11⊕B12⊕B13=0⊕0⊕1⊕0⊕0⊕0=1然后从高位往下写，B8+B4+B2+B1=1011=11（十进制）即11位出错。

海明码的计算方法海明码是一种具有纠错功能的校验码。

本文简单地介绍海明码的计算方法。

海明码的目的是能够纠正一位误码。

假设信息码共有 n 位，海明码共有 h 位，那么总共的码长为 n + h 位。

为能检测出 n + h 位编码中其中一位的错误，海明码必须能够表示至少 n + h + 1 种状态，其中 n + h 种表示 n + h 位编码中有一位错误，另外还需要一种来表示整个编码正确无误。

则海明码的长度需要满足下列关系：2 h>= n + h + 1于是根据这个式子我们可以得出以下的关系表：h 2 3 4 5 6 7 8n 1 2~4 5~11 12~26 27~57 58~120 121~247以 4 位信息位为例，由上表可以看出需要的海明码长度为 3。

设信息位为 x4x3x2x1，添加的 3 位海明码为 a3a2a1，信息码和海明码组合之后得到的码为 H7H6H5H4H3H2H1。

错误无H1H2H3H4H5H6H7C101010101C1= H1+ H3+ H5+ H7= 0C200110011C2= H2+ H3+ H6+ H7= 0C300001111C3= H4+ H5+ H6+ H7= 0如上表，在H1～H7中添加的 3 位海明码使得 C1～C3的值为零。

其中C1～C3为校验和。

这样当 Hn 传输出错时，有 (C3C2C1)2= n。

令 H1 = a1, H2= a2, H4= a3,则得出H 7H6H5H4H3H2H1= x4x3x2a3x1a2a1将上面的关系代入C1～C3的计算公式，得到C 1 = H1+ H3+ H5+ H7= a1+ x1+ x2+ x4= 0C 2 = H2+ H3+ H6+ H7= a2+ x1+ x3+ x4= 0C 3 = H4+ H5+ H6+ H7= a3+ x2+ x3+ x4= 0即a 1 + x1+ x2+ x4= 0a 2 + x1+ x3+ x4= 0a 3 + x2+ x3+ x4= 0即a 3 = x4+ x3+ x2a 2 = x4+ x3+ x1a 1 = x4+ x2+ x1。