校验码最终版.ppt

《校验码最终版.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、为1，例如用四位二进制表示16种状态，16种编码都用到了，此时码距为1，就是说，任何一个状态的四位码中的一位或几位出错，就变成了另一合法码，此时无查错能力。若用其中的8个状态编码，此时码距为2。一般来说，合理地增大合法码的码距，就能提高发现错误的能力，但表示一定数量的合法码所使用的二进制位数变多，增加了数据存储的容量或数据传输的数量。编码的纠错、检错能力与编码的最小距离有关L——编码的最小距离D——检测错误的位数C——纠正错误的位数L1=D+C(D≥C)L=3具有一位纠错能力几种常用的检错纠错码我们只介绍三种常用的检错纠错码：奇偶检错码，用于并行数据传送中海明检错与纠错码，用于并行数据传送中

3、循环冗余码，用于串行数据传送中编码过程译码过程原始数据码字(数据+校验)结果数据形成校验位的值，加进特征检查接收的码字，发现/改正错误传送主存读、写奇偶校验码用于并行码检错原理：在k位数据码之外增加1位校验位，使K+1位码字中取值为1的位数总保持为偶数（偶校验）或奇数（奇校验）。例如：0001100010000101010010110101偶校验奇校验校验位原有数字位两个新的码字奇偶校验码的实现电路+奇较验偶校验偶校验出错指示+++++++同左侧电路编码电路译码电路P(校验位)八位数据位D7D6D5D4D3D2D1D0p奇偶校验码常用于：存储器读写检查；ASCII字符、其他类型信息传送过程中

4、的出错检查。缺点：只能发现有无差错，而不能确定发生差错的位置；只能发现奇数个二进位错，不能发现偶数个二进制错。海明校验码用于多位并行数据检错纠错处理实现：为k个数据位设立r个校验位，使k+r位的码字同时具有这样两个特性：1.能发现并改正k+r位中任何一位出错，2.能发现k+r位中任何二位同时出错，但已无法改正。要特性1成立，必须有如下关系：2r>=k+r+1要特性1和2同时成立，k和r有如下关系：2r-1>=k+rk值最小的r值1--344--10511--25626--56757--1198海明码的编码方法合理地用k位数据位形成r个校验位的值，即保证用k个数据位中不同的数据位组合来形成每一

5、个校验位的值，使任何一个数据位出错时，将影响r个校验位中不同的校验位组合起变化。换言之，通过检查是哪种校验位组合起了变化，就能确定是哪个数据位错，对该位求反则实现纠错。有时两位错与某种情况的一位错对校验位组合的影响相同，必须能区分一位或双位错。海明码的编码规律：假设海明码的最高位号为m，最低位号为1，即：HmHm-1…H2H1。（1）校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按照从低到高逐位依次排列的关系分配各数据位。（2）海明码的每一位码Hi（包括数据位和校验位本身）由多个校验位校验，其关系是被校验的每一位位号要等于校验它的各校验位的位号

6、之和。这样安排的目的，是希望校验的结果能反映出出错位的位号。（3）在增大合法码码距时，使所有码的码距尽量均匀的增大，以保证对所有码的检错能力平衡提高。海明码位号数据位校验位参与校验的校验位位号被校验的海明码位号＝校验位位号之和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＝13++P1D1D2D4D5D7P2D1D3D4D6D7P3D2D3

7、D4D8P4D5D6D7D8P5D1D2D3D4D5D6D7D8P1P2P3P4＋＋＋＋+P1=D1D2D4D5D7P2=D1D3D4D6D7P3=D2D3D4D8P4=D5D6D7D8P5=D1D2D3D4D5D6D7D8P1P2P3P4S1=S2=S3=S4=S5=：异或编码方案译码方案+++++++++++++++++++++++++＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋用一个校验码和形成