计算机组成原理三章new.ppt

《计算机组成原理三章new.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3.8数据校验码(检错纠错码)引言是一类数据编码方式，编码的用意不同----检错纠错数据在计算机系统内加工、存取和传送的过程中可能产生错误减少错误的发生：*提高硬件电路本身的稳定性*数据编码上找出路。采用带有某种特征能力的编码方法，通过少量的附加电路，使之能发现某些错误,甚至能自动纠正错误。8/22/20211数据校验码基本特征---发现错误，甚至自动纠正错误.检错是前提。常用的数据校验码三种：奇偶校验码、海明校验码、循环冗余校验码(CRC)实现校验码的基本原理：在普通编码的基础上增加一些冗余码，能够在正常合法码发生错误时，即变成非法码

2、时，通过检测编码的合法性发现错误甚至纠正错误编码(原数据+校验位)传输(码字)解码校验纠错码距的概念（最小码距）：码距是指任意两个合法码之间二进制位存在排列变化的最小位数。仅有一位不同，称(最小码距)为1码距为一时，无检错能力。一个合法码变另合法码8/22/20212从另一个角度说，检错纠错还是要有硬件开销的检错纠错，也是有能力限制的。某些错误能检出，不是所有的错误都能检出。3.8.1奇偶校验码1，原理对已有码距为一编码增加一位，使码距为二。所增加的一位---校验位。总体编码空间增大一倍。任一个合法编码的任一位发生错变(1->0,0-

3、>1)都会变成一个非法码。2，方法考察二进制编码中，数值位和校验位总体(码字)各位取值为1位数的奇偶性。8/22/202133，实现(1)奇校验:数据位取值为1的位数和校验位凑为奇数。(2)偶校验:数据位取值为1的位数和校验位凑为偶数。（应用中确定其一种。）设码字9位，数据8位校验1位高位校验位数据奇校验的编码偶校验的编码000000001000000000000000000101010000101010010101010001111111001111111101111111111111111111111110111111118/22/2

4、02144奇偶校验码的逻辑实现+奇较验偶校验出错指示+++++++同左侧电路编码电路译码电路P(校验位)八位数据位D7D6D5D4D3D2D1D0p异或门8/22/202155,实际应用特点开销最小。不能纠错，内存读写ASCII码传输，并行数据传输，发现奇数个错变3.8.1海明校验码1，原理对已有码距为一的编码增加几个检验位。用这些校验位来定位各编码中任一位错变。同时发现任两位的错变但不能定位了，也就不能纠错了。DDDDDDDDPPPPP*校验位需求量分析k为数据位数(二进制)，r为校验位数r位可编码不同信息2r个，其中一个编码用于表示未

5、出错8/22/20216可用来定位错误的信息编码有2r–1–r个。要定出有k位的数据中某位错变显然，要满足这个不等式2r–1–r≥k含义是对每一位的错变都有至少一个专门交验位编码即：2r≥k+r+1若要校正一位错，发现两位错，r和k的关系：2r-1≥k+r（海明不等式）k与r具体对应关系表3.8p972,海明码的基本编码方法（k个数据位，r个校验位）*合理地用k个数据位的不同组合形成r个校验位。使任一位出错时都会影响r个校验位中不同的校验位组合变化，从而定位错误。*有时两位同时出错和某一位的出错对校验组合的影响相同必须区别出来。8/22/

6、202173，八数据位海明码的构成k=8,r=5数据位：D8D7D6D5D4D3D2D1校验位：P5P4P3P2P1码字：P5D8D7D6D5P4D4D3D2P3D1P2P14,校验位的生成与数据位的组合(编码方程)P1=D1⊕D2⊕D4⊕D5⊕D7P2=D1⊕D3⊕D4⊕D6⊕D7P3=D2⊕D3⊕D4⊕D8P4=D5⊕D6⊕D7⊕D8P5=D1⊕D2⊕D3⊕D4⊕D5⊕D6⊕D7⊕D8⊕P1⊕P2⊕P3⊕P4P5称位总校验位，每个数据位至少参与三个校验位的生成8/22/20218Ｄ８Ｄ７Ｄ６Ｄ５Ｄ４Ｄ３Ｄ２Ｄ１Ｐ５Ｐ４Ｐ３Ｐ２Ｐ１１１

7、１１１１１１１１１１１１１１１０００００１０００１０００１１１０００１０００１１０１１０１０００１００１０１１０１１００００１１２１１１０９７６５３０８４２１校验位Ｐi生成与数据位组合的关系8/22/20219D1—D8某一位错变都会引起P1—P4变化的不同组合５,海明校验逻辑形成(偶校验为例)S1=P1⊕D1⊕D2⊕D4⊕D5⊕D7S2=P2⊕D1⊕D3⊕D4⊕D6⊕D7S3=P3⊕D2⊕D3⊕D4⊕D8S4=P4⊕D5⊕D6⊕D7⊕D8S5=P5⊕D1⊕D2⊕D3⊕D4⊕D5⊕D6⊕D7⊕D8⊕P1⊕P2⊕P3⊕P4S1S5是校验结

8、果S1—S4的每组01组合唯一地标识13位海明码的某位出错，为００００时说明没有错，S5为0而S1-S4有不为零者时有偶数位错8/22/202110译码出错对照表S5S4S3S2S1出错位──