校验码最终版

检错纠错码数据在计算机系统内形成、存取和传送的过程中难免会产生错误。为减少和避免这类错误，一方面是精心设计各种电路，提高计算机硬件的可靠性，另一方面是在数据编码上找出路，即采用一点冗余的线路，在原有数据位之外再增加一到几位校验位，使新得到的码字带上某种特性，之后则通过检查该码字是否仍保持有这一特性，来发现是否出现了错误，甚至于定位错误后，自动改正这一错误，这就是我们这里说的检错纠错编码技术。1

数据校验码的实现原理：是在合法的数据编码之间，加入一些不允许出现的（非法的）编码，使合法数据编码出现某些错误时，就成为非法编码。

码距：是指任意两个合法码之间至少有几个二进制位不相同。仅有一位不同，称其码距为1，例如用四位二进制表示16种状态，16种编码都用到了，此时码距为1，就是说，任何一个状态的四位码中的一位或几位出错，就变成了另一合法码，此时无查错能力。若用其中的8个状态编码，此时码距为2。一般来说，合理地增大合法码的码距，就能提高发现错误的能力，但表示一定数量的合法码所使用的二进制位数变多，增加了数据存储的容量或数据传输的数量。2编码的纠错、检错能力与编码的最小距离有关L——编码的最小距离D——检测错误的位数C——纠正错误的位数L1=D+C(D≥C)L=3具有一位

纠错能力3几种常用的检错纠错码我们只介绍三种常用的检错纠错码：奇偶检错码，用于并行数据传送中海明检错与纠错码，用于并行数据传送中循环冗余码，用于串行数据传送中编码过程译码过程原始数据码字(数据+校验)结果数据形成校验位的值，加进特征检查接收的码字，发现/改正错误传送主存读、写4奇偶校验码用于并行码检错原理：在k位数据码之外增加1位校验位，使K+1位码字中取值为1的位数总保持为偶数（偶校验）或奇数（奇校验）。例如： 00011000100001

01010010110101

偶校验奇校验校验位原有数字位

两个新的码字5奇偶校验码的实现电路+奇较验偶校验偶校验出错指示+++++++同左侧电路编码电路译码电路P(校验位)八位数据位D7D6D5D4D3D2D1D0p6奇偶校验码常用于：存储器读写检查；ASCII字符、其他类型信息传送过程中的出错检查。缺点：只能发现有无差错，而不能确定发生差错的位置；只能发现奇数个二进位错，不能发现偶数个二进制错。7海明校验码用于多位并行数据检错纠错处理实现：为k个数据位设立r

个校验位，使k+r

位的码字同时具有这样两个特性：1.能发现并改正k+r

位中任何一位出错，2.能发现k+r

位中任何二位同时出错，但已无法改正。要特性1成立，必须有如下关系：2r>=k+r+1要特性1和2同时成立，k和r有如下关系：2r-1>=k+r8k值最小的r值1--344--10511--25626--56757--11989海明码的编码方法合理地用k位数据位形成r个校验位的值，即保证用k个数据位中不同的数据位组合来形成每一个校验位的值，使任何一个数据位出错时，将影响r个校验位中不同的校验位组合起变化。换言之，通过检查是哪种校验位组合起了变化，就能确定是哪个数据位错，对该位求反则实现纠错。有时两位错与某种情况的一位错对校验位组合的影响相同，必须能区分一位或双位错。10海明码的编码规律：

假设海明码的最高位号为m，最低位号为1，即：HmHm-1…H2H1。（1）校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按照从低到高逐位依次排列的关系分配各数据位。（2）海明码的每一位码Hi（包括数据位和校验位本身）由多个校验位校验，其关系是被校验的每一位位号要等于校验它的各校验位的位号之和。这样安排的目的，是希望校验的结果能反映出出错位的位号。（3）在增大合法码码距时，使所有码的码距尽量均匀的增大，以保证对所有码的检错能力平衡提高。11海明码位号数据位校验位参与校验的校验位位号被校验的海明码位号＝校验位位号之和H1P111＝1H2P222＝2H3D11、23＝1＋2H4P344＝4H5D21、45＝1＋4H6D32、46＝2＋4H7D41、2、47＝1＋2＋4H8P488＝8H9D51、89＝1＋8H10D62、810＝2＋8H11D71、2、811＝1＋2＋8H12D84、812＝4＋8H13P51313＝1312++P1D1D2D4D5D7P2

D1D3D4D6D7P3D2D3D4D8P4

D5D6D7D8P5D1D2D3D4D5D6D7D8P1P2P3P4＋＋＋＋+P1=D1D2D4D5D7P2=

D1D3D4D6D7P3=

D2D3D4D8P4=

D5D6D7D8P5=D1D2D3D4D5D6D7D8P1P2P3P4S1=S2=S3=S4=

S5=：异或编码方案译码方案+++++++++++++++++++++++++＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋用一个校验码和形成这个校验码的编码方程执行异或，又一次执行偶校验运算13通过检查五个S的结果，可以实现检错纠错的目的：偶数个数出错，S5一定为0，因此S5可区分两位错或一位出错；任何一位（含数据位、校验位）均不错，则S4~S1都应为0；S4~S1不全为0，说明有错，例如若为1100或1011，则分别表示H12或H11位错，由检验线路直接纠正。140000奇偶形成电路H12H11H10H9H8奇偶形成电路H12H7H6H5H4奇偶形成电路H11H10H6H3H2H7奇偶形成电路H11H9H5H3H1H74~16译码器S4S3S2S1H30011＋D1无错H121100＋D8H111011＋D7H101010＋D6H91001＋D5H70111＋D4H60110＋D3H50101＋D2有错S4S3S1S215海明码常用于：大中型计算机存储器的校验中科院98年试题：请写出数据10110100110的海明码，用4位校验位，采用偶校验。16P1=D2+D1P2=

D3+D1P3=

D3+D2海明码的实现方案，如何确定数据位和校验位的对应关系？例如：k=3,r=4D3D2D1

P4P3P2

P1

111

1

111110010010100

1

00110001

P4=

P3

+

P2

+

P1

+D3+D2+D1S1=P1+

D2+D1S2=P2

+

D3+D1S3=P3

+

D3+D2S4=P4

+

P3

+

P2

+

P1

+D3+D2+D1+：异或编码方案译码方案17海明码的实现方案，如何确定数据位和校验位的对应关系？例如：k=3,r=4D3D2D1

P4P3P2

P1

1.排列好码字的每一位：3个数据位D3D2D14个校验位P4P3P2P12.在P4~P1列不同行写13.在P4~P1列其他处写04.看P4~P1列3位码的值

04215.定D3~D1列3位码的值653-11110000000000421653写D3~D1列3位码的值在顶行各空闲位置写18.写P4~P1的编码表达式9.写S4~S1的编码表达式11001111011111118P1=D2+D1P2=

D3+D1P3=

D3+D2海明码的实现方案，如何确定数据位和校验位的对应关系？例如：k=3,r=4D3D2D1

P4P3P2

P1

111

1

111110010010100

1

00110001

P4=

P3

+

P2

+

P1

+D3+D2+D1S1=P1+

D2+D1S2=P2

+

D3+D1S3=P3

+

D3+D2S4=P4

+

P3

+

P2

+

P1

+D3+D2+D1+：异或8.写编码表达式9.写译码表达式19如何实现检错与纠错？D3D2D1

P4P3P2

P1

111

1

111110010010100

1

00110001S1=P1+

D2+D1S2=P2

+

D3+D1S3=P3

+

D3+D2S4=P4

+

P3

+

P2

+

P1

+D3+D2+D1译码表达式P4是总校验位，区别一位还是双位错纠错，对比出错模式表S4~S1都是0，无错误S4~S1非全0，有错误①与哪一列同值，哪位错对出错数据位求反以纠正②S4=0，但S3~S1非全0表明是双位错，无法纠正③否则属于更多位同时错20循环冗余码用于多位串行数据传送中的检错纠错处理，在

k位数据位串行移位输出的过程中，用带有异或门控制的移位寄存器形成

r个校验位的值，跟随在数据位之后传送走。在接收端再对k+r位的码字进行合法与出错检查，若可能则自动改错。21循环冗余码的实现原理循环冗余码是在k位数据位串行移位输出过程中求出r

个校验位的值。其数学原理用的是模2除，即对由k个数据位后跟r个取值为0的位构成的数，除以从数学表中查来的一个生成多项式（对应一个特定的r+1位的二进制数），求出的r

位的余数就是校验位的结果。为了描述不断移位操作过程中的数据，引进伪变量X和它的的不同的幂，以表示一个二进制数取值为1的那些位的值。此时原来说的k位数据，k+r位码字，r位的余数均可以用一元多项式表示。模2除时作除数用的二进制数也表现为多项式的形式，叫做生成多项式。22CRC码工作原理用多项式M（x）.xr除以生成多项式（产生检验码的多项式）所得余数作为校验位。为了得到r位余数（校验位），G（x）必须是r+1位。M（x）.xr＋R(x)=[Q(x).G(x)+R(x)]+R(x)=[Q(x).G(x)]+[R(x)+R(x)]=Q(x).G(x)因此，所得CRC码可被G(x)表示的数码除尽。23模2除与移位寄存器模2除类似于正常二进制除法，区别有两点：上商只看被除数的最高位，其值为1则上商1，其值为0则上商0。求余数用本位相减，上商为1时，求余数只用本位相减，位间无借位。模2除运算，可以用带有异或门控制的移位寄存器实现，不用加法电路，简单又速度快，且可与串行数据移位输出用同一电路。24循环冗余码的实现的数学原理1011110000001011101110000001110010111

1011101k=3数据为100r=4求出的校验值为1011100可写成X2为求四位校验位，可用X+X+X+1去模2除42X+X+X+1叫做生成多项式，由查表得到。42码字为100101125循环冗余码的实现电路线性分组（7，3）码，即3位数据加4位校验查表得到生成多项式：G（X）=X4+X2+X+1

T4T3T2T1T0CP

+++++101