计算机组成原理：2-5 数据的机器层次表示

1、复习思考题51. 一个的二进制编码用_表示。2.若某汉字的区位码=2016H，则其国标码= _。 3.若某汉字的国标码=3456H，则其机内码= _。 4.有效信息长度=N的偶校验码的编码效率R=_。5.码距=1时的数据校验码没有纠错能力，但有检错能力。 （ ）6.码距越大，则校验码的检、纠错能力越强。（ ）7.奇校验码可以检查出奇数位错误，偶校验码可以检查出偶数位错误。（ ）第2章 数据的机器层次表示2.1 数值数据的表示2.2 机器数的定点表示与浮点表示2.3 非数值数据的表示2.4 十进制数和数串的表示2.5 现代微型计算机系统中的数据表示举例2.6 数据校验码校验码的类别n三种常用的检

2、错纠错码：n奇偶检错码奇偶检错码 用于用于并行并行数据传送中数据传送中n海明检错与纠错码海明检错与纠错码 用于用于并行并行数据传送中数据传送中n循环冗余码循环冗余码 用于用于串行串行数据传送中数据传送中编码过程编码过程译码过程译码过程码字传码字传送送原始数据原始数据结果数据结果数据形成校验位的值，形成校验位的值，加进特征加进特征检查接收的码字，检查接收的码字，发现发现/ /改正错误改正错误例例2：数据数据 ： 0111 0101奇校验码奇校验码 0111 01010发送端发送端（编码）（编码）0110 01110接收端接收端正确！正确！奇偶校验码的编码与校验方法例例1：数据数据 ： 0111

3、0101偶校验码偶校验码 0111 01011发送端发送端（编码）（编码）0110 01011接收端出错出错D7D6D5D4D3D2D1D0D校奇形成偶校验出错奇校验出错偶形成AB=1=1=1=1=1=1=1=111奇偶校验位的形成及校验电路偶 形 成 = D0 D1 D2 D3 D4 D5 D6 D7偶校验出错= D校 D0D1D2 D3D4D5D6D7 0 1 1 1 0 1 0 1 发送端发送端 1 0 1 1 1 0 10 0 = 00 1 = 11 0 = 11 1 = 0D7D6D5D4D3D2D1D0D校奇形成偶校验出错奇校验出错偶形成AB=1=1=1=1=1=1=1=111奇偶

4、校验位的形成及校验电路偶 形 成 = D0 D1 D2 D3 D4 D5 D6 D7偶校验出错= D校 D0 D1 D2 D3 D4 D5 D6 D7 0 1 1 1 0 1 0 1 0接收端接收端 1 0 1 1 1 0 1 0 10 0 = 00 1 = 11 0 = 11 1 = 0奇偶校验码的扩展交叉校验交叉校验横向校验横向校验：每个字节有一个奇偶校验位：每个字节有一个奇偶校验位纵向校验纵向校验：全部字节的同一位有一个奇偶校验位：全部字节的同一位有一个奇偶校验位1 1 0 0 1 0 1 110 1 0 1 1 1 0 001 0 0 1 1 0 1 001 0 0 1 0 1 0 1

5、0 1 0 0 1 1 0 0 01第第1字节字节第第2字节字节第第3字节字节第第4字节字节纵向校验纵向校验(偶偶)a7 a6 a5 a4 a3 a2 a1 a0横向校验横向校验( (偶偶) )交叉校验交叉校验可检出同可检出同一字节的一字节的双错双错1001奇偶校验码的扩展交叉校验交叉校验横向校验横向校验：每个字节有一个奇偶校验位：每个字节有一个奇偶校验位纵向校验纵向校验：全部字节的同一位有一个奇偶校验位：全部字节的同一位有一个奇偶校验位1 1 0 0 1 0 1 110 1 0 1 1 1 0 001 0 0 1 1 0 1 001 0 0 1 0 1 0 10 1 0 0 1 1 0 0

6、01第第1字节字节第第2字节字节第第3字节字节第第4字节字节纵向校验纵向校验(偶偶)a7 a6 a5 a4 a3 a2 a1 a0横向校验横向校验( (偶偶) )001交叉校验交叉校验可定位单可定位单错，即可错，即可纠正单错纠正单错2.6 海明校验码n海明校验码n是一种多重奇偶校验，这是一种不仅能检错，是一种多重奇偶校验，这是一种不仅能检错，而且能自动纠错的校验码。而且能自动纠错的校验码。n校验原理n以奇偶校验为基础，在数据中掺杂一组校验位，以奇偶校验为基础，在数据中掺杂一组校验位，并规定每个校验位的校验范围。并规定每个校验位的校验范围。n当某一位出错后，就会引起有关的几个校验位当某一位出错后

7、，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。出错误的位置，为自动纠错提供了依据。校验码中校验位数的确定n 要使编码能纠正一位出错并能发现两位错，则校验码必须具有nN位数据位每一位的位置状态位数据位每一位的位置状态nK位校验位每一位的位置状态位校验位每一位的位置状态n无错无错情况的状态情况的状态n应满足关系应满足关系 2K-1N+K+1数数 据据 位位校验位校验位NKN1341011252656Kmin4567校验位在海明码中的分布n 校验位的分布规则： 把位号数是2的权值的那些位，分配做奇偶校验位

8、n 假设数据位N=8，校验位位数K=5, 故海明码的总位数为13。它们的排列关系可表示为： 海明码位号: H13H12H11H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 海明码： P5 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1n 海明码的特点n每个校验位由其本身校验；每个校验位由其本身校验；n每个数据位由若干校验位校验每个数据位由若干校验位校验. .海明码的各位与校验位的关系被校验的每一位的位号被校验的每一位的位号=校验它的各校验位的位号之和校验它的各校验位的位号之和海明码位号海明码位号数据位校验位数据位校验位参与校验的校参与校验的校验位位号验位位

9、号关系关系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+8海明码各校验位的生成海明码位号海明码位号数据位校验位数据位校验位参与校验的校验位位号参与校验的校验位位号关系关系H3D11,23=1+2H5D21,45=1+4H6D32,46=2+4H7D41,2,47=1+2+4H9D51,89=1+8H10D62,810=2+8H11D71,2,811=1+2+8H

10、12D84,812=4+8与与P1有关的数据位有关的数据位1，2，4，5，7与与P2有关的数据位有关的数据位1，3，4，6，7与与P3有关的数据位有关的数据位2，3，4，8与与P4有关的数据位有关的数据位5，6，7，8与与P5有关的数据位有关的数据位：1，2，3，5，6，8 每位信息位都均匀地出现每位信息位都均匀地出现在在3个个Pi值形成有关，当任值形成有关，当任一信息位发生变化时，必引一信息位发生变化时，必引起起3个个Pi值的变化，即合法值的变化，即合法海明码的码距为海明码的码距为4。海明码各校验位的生成n 若采用n则则P1P5分别为与它相关的数据位的偶校验位分别为与它相关的数据位的偶校验位

11、n 若采用奇校验码n则则P1P5分别为与它相关的数据位的奇校验位分别为与它相关的数据位的奇校验位校验位校验位可校验的有关数据位可校验的有关数据位P11，2，4，5，7P21，3，4，6，7P32，3，4，8P45，6，7，8P51，2，3，5，6，8 P1=D1 D2 D4 D5 D7 P2=D1 D3 D4 D6 D7 P3=D2 D3 D4 D8 P4=D5 D6 D7 D8 P5=D1 D2 D3 D5 D6 D8海明码的各位与校验位的关系海明码位号海明码位号13海明码位号海明码位号8421海明码的各位与校验位的关系海明码位号海明码位号13海明码位号海明码位号8421 P1=D1 D2

12、D4 D5 D7 P2=D1 D3 D4 D6 D7 P3=D2 D3 D4 D8 P4=D5 D6 D7 D8 P5=D1 D2 D3 D5 D6 D8例：有8位信息代码：1010 1100，求它的海明码，用偶校验。解：信息代码8位位N=8K=5海明码共N+K=8+5=13位位13 12 11 10 9 8 7 6 5 4 3 2 1 P1P2D1 P3D2 D3 D4 P4D5 D6 D70101100P1： 1，2，4，5，70 0 1 0 01P2： 1，3，4，6，70 1 1 1 01P3:2，3，4，80 1 11P4： 5，6，7，80 1 00 1 1 1 0海明码海明码P5

13、D8 111P5： 1，2，3，5，6，80 0 1 0 1111 P1=D1 D2 D4 D5 D7 P2=D1 D3 D4 D6 D7 P3=D2 D3 D4 D8 P4=D5 D6 D7 D8 P5=D1 D2 D3 D5 D6 D8海明码的检错和纠错按偶校验写出校验方程为： S1=P1 D1 D2 D4 D5 D7 S2=P2 D1 D3 D4 D6 D7 S3=P3 D2 D3 D4 D8 S4=P4 D5 D6 D7 D8 S5=P5 D1 D2 D3 D5 D6 D8校验位校验位可校验的有关数据位可校验的有关数据位P11，2，4，5，7P21，3，4，6，7P32，3，4，8P4

14、5，6，7，8P51，2，3，5，6，813 12 11 10 9 8 7 6 5 4 3 2 1 P1P2D1 P3D2 D3 D4 P4D5 D6 D70101100 1 1 1 0海明码海明码P5D8 11海明码的检错和纠错S5S1的值的值检错和纠错情况检错和纠错情况00000无错无错仅有一位不为仅有一位不为0某一校验位出错某一校验位出错或三位海明码同时出错或三位海明码同时出错有两位不为有两位不为0两位海明码同时出错，此时只能检错两位海明码同时出错，此时只能检错有三位不为有三位不为0一位信息位出错一位信息位出错或三位校验位同时出错，或三位校验位同时出错，出错位的位号由出错位的位号由S4S

15、1编码值指明，此编码值指明，此时可以纠错。时可以纠错。有有4位或位或5位不为位不为0出错情况严重，系统工作可能出现故障，出错情况严重，系统工作可能出现故障，应检查系统硬件的正确性应检查系统硬件的正确性海明码的检错和纠错举例n假设前例中的海明码传送后，若接收变成了1111001101011 P1P2D1 P3D2 D3 D4 P4D5 D6 D71101100P1， 1，2，4，5，70 0 1 0 11P2， 1，3，4，6，70 1 1 1 11P3， 2，3，4，80 1 10P4， 5，6，7，80 1 11 1 1 1 0海明码海明码P5D8 111P5， 1，2，3，5，6，80 0

16、 1 0 1011S1：S2：S3:S4：S5：11101S4S3S2S1=1011，看成一个看成一个“指误字指误字”因为因为1011B=11D，说明，说明H11出了错出了错.纠错：将纠错：将H11取反值即可。取反值即可。 1101001101011 循环冗余码(Cyclic Redundancy Check)n在计算机网络、在计算机网络、同步通信、磁同步通信、磁表面存储器中表面存储器中广泛使用循环冗余校验码广泛使用循环冗余校验码，简称简称CRC码。码。n它用于多位串行数据传送中的检错纠错处理n在 N 位数据位串行移位输出的过程中，用电路形成K 个校验位的值，跟随在数据位之后传送。n在接收端再

17、对 N+K 位的代码进行合法与出错检查，若可能则自动改错。 数据位数据位 校验位校验位NK( N+K, N ) 码码循环冗余码的运算基础模2运算n 以2为模，按位相加的运算，在运算中不考虑借位和进位 模2加减法：00=0，01=1，10=1，11=0 模2乘法：按模2加求部分积之和 模2除法 ：按模2 减求部分余数 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 01 0 0 0 01 0 111 0 10 1 000 0 01 0 011 0 10 1商商余数余数循环冗余码编码原理nCRC的编码原理任何一个二进制序列中的各个位均可看成一个任何一

18、个二进制序列中的各个位均可看成一个多项式的系数：多项式的系数：如：1101n M(x)待编码的有效信息的多项式表示。待编码的有效信息的多项式表示。n M(x)xK 将将M(x)左移左移 K 位得到多项式，使低位得到多项式，使低 K 位为零。位为零。n G(x)生成多项式，生成多项式， G(x)的长度为的长度为 K+1 位。位。1 x3+1 x2+0 x1+1 x0 x3 + x2 + 1循环冗余码编码原理这时将这时将R(x)与与M(x) xK 拼装，就得到拼装，就得到 N+K 位位CRC编码编码： M(x)xK R(x) = G(x) Q(x) + R(x) R(x)“两个相同数据的模两个相同

19、数据的模2和为零和为零”，即，即R(x) R(x) = 0，所以所以 M(x)xK R(x) = G(x) Q(x)可以看出，所求得的可以看出，所求得的CRC码是一个可被码是一个可被G(x)整除整除的的数码。数码。)()()()(xRxGxQxxMKn 假设M(x) XK 除以生成多项式G(x) ，用R(x)表示余数，用Q(x)表示商：循环冗余码编码举例 例 设有效信息位是M(x)=1100，生成多项式 G(x)=1011，试求M(x)的CRC码。 解：(1)因为G(x)有4位长， K+1=4 所以 K=3 (2)M(x)左移K=3位， M(x) x3 = 1100000 (3)用G(x)对M(x) xK 作“模2除” 1100000 1011 = 1110 010 R(x)=010 (4)M(x)x3 与R(x) 作“模2加”，即可求得它的CRC编码 M(x) x3 + R(x) = 1100000 + 010 = 1100