清华计算机组成原理课件03 运算方法和运算部件精选.pptVIP

* 计算机组成原理 * 解：已知D10D9D8D7D6D5D4D3D2D1D0=10110100110 由于被校验位的位号等于校验它的各校验位位号之和以 及各校验位的取值等于它参与校验的数据位取值的异或。所 以校验位的取值以及所求海明码为： P1=D0?D1 ? D3 ? D4 ? D6 ? D8 ? D10 =1 P2=D0 ? D2 ? D3 ? D5 ? D6 ? D9 ? D10=1 P3=D1 ? D2 ? D3 ? D7 ? D8 ? D9 ? D10=1 P4=D4 ? D5 ? D6 ? D7 ? D8 ? D9 ? D10=0 D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1 =101101000111011 传送正确时校验和的值为0，如果不等于0，则是几就是 第几位出错，是7则是第7位D3出错，此时将其取反即可纠正 错误。 例题：采用4位校验位、偶校验方式， 写出10110100110的海明码。 * 计算机组成原理 * 奇偶形成线路 奇偶形成线路 奇偶形成线路 奇偶形成线路 * 计算机组成原理 * 以上 图3.11是H=12，数据位k=8，校验位 r=4的海明校验线路，记作（l2.8）分组码。 图3.ll中的H12,H11,...,H1是被校验码，D8,D7,...，D1是纠正后的数据。在线路中，先用奇偶形成线路得到S4,S3,S2,S1，如果S4～S1为全“0”，说明代码无错，则D8D7...DI=H12H11H10H9H7H6H5H3。如果S4～S1不为全0，说明有错。若为1100或1011，则分别表示H12或Hll位错，对应这两种出错情况，相关的两条译码线之一为“l”，它与相应的数据使经异或线路，就把该位校正过来，得到正确编码输出。依此类推如S4S3S2S1为1010，1001，0111，0110，0101或0011，分别表示H10，H9,H7,H6,H5或H3位错，用相同的方法予以纠正、如错误发生在校验位上。则相关的译码线（1000，0l00，0010，0001）之一为l，在图3 11中未画出。 如前所述，假如要进一步判别是1位错还是2位错，则再增加一个校验位、并用图 3.12来取代图3.11虚框中的内容，此时增加了一个奇偶形成线路S5。如为一位错，仍按图3.11来纠正数据位；如为两位错，则无法纠正错误。 * 计算机组成原理 * C1 C2 …... C K r 1 r 2 …… r i 3.7.3 循环冗余校验方法(CRC码) 环冗余校验方式：通过某种数学公式建立信息位和校验位之间的约定关系——能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。 CRC编码格式是在k位信息后加r位检验码。 N N-1 2 1 信息位（k位） 校验位（r位） * 计算机组成原理 * 1、CRC码的编码方法 CRC整个编码长度为 n=k+r 位，故CRC码又叫（n，k）码。其编码方法如下： 假设被传送的k位二进制信息位用C(x)表示, 系统选定的生成多项式用G(X)表示，将C(x)左移 G(X)的最高次幂(即等于需要添加的校验位的位数r)，写作 C(x) ? 2 r 然后将其C(x) ? 2 r除以生成多项式G(x)，所得商用Q(x)表示，余数用R(x)表示。则： 两边同时乘以G(x)并左移 R(x) 得到： * 计算机组成原理 * 故有： 上式中，等式左边即为所求的n位CRC码， 其中余数表达式R(x)就是校验位(r位)。且等 式两边都是G(x)的倍数。 发送信息时将等式左边生成的n位CRC码 送给对方。当接收方接到n位编码后，同样除 以G(x)，如果传输正确则余数为0，否则则可 以根据余数的数值确定是哪位数据出错。 由于CRC编码采用的加、减法是按位加 减法，即不考虑进位与借位，运算规则为： 0?0=0，0?1=1，1?0=1，1?1=0 * 计算机组成原理 * 例：有一个（7,4）码（即CRC码为7位，信息码为4位），已确定生成多项式为：