第2章 数制与码制(2)

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2.11,葛莱码,(,格雷码,),为什么使用格雷码,编码盘问题,特点,:,对连续的码字之间只有一个数位变化,例,构造规则,规则,1,1),1,位葛莱码有,2,个码字：,0,和,1,。,2),（,n,+1,）,位葛莱码中的前,2,n,个码字等于,n,位葛莱码的码字，按顺序书写，加前缀,0,。,3),（,n,+1,）,位葛莱码中的后,2,n,个码字等于,n,位葛莱码的码字，但按逆序书写，加前缀,1,。,例：,n=1,n+1=2,位格雷码的构造,0,0,0,1,1,1,1,0,前缀加,1,后,2,个码字逆序,前缀加,0,2.12,字符编码,位串不一定只用来表示数值,最常见的非数值数据是,文本,，,即取自某字符集的字符串。,在计算机中，根据已建立的约定，用位串表示每个字符。,最常用的字符编码是,A S C I I,码，即美国信息交换标准码。,A S C I I,码用,7,位二进制串表示每个字符,A S C I I,码包括大写字母和小写字母、数字、标点符号及各种非打印控制字符。,2.13,动作、条件和状态的编码,数据类型：数值、位置、字符,非数据类型：动作、条件和状态,在数字系统设计中，经常遇到非数据的应用：将位串用于控制动作、标识条件、表示硬件的当前状态等等，最常用的编码类型是简单的二进制编码。,设有,n,个不同的动作、条件或状态，则需用,b,位二进制编码来表示，,b=log,2,n,位,括号,表示,上限函数,，表示取大于或等于括号内数值的最小整数,b,为满足,2,b,n,关系的最小整数,例,1,：一个简单的交通信号灯控制器，在南,-,北,（,N-S,）,和东,-,西（,E-W,）,街道的十字路口，信号有,6,种状态，这些状态可用,3,位二进制编码,例,2,：,有一个包含,n,个设备的系统，每个设备都完成一定的动作，在某一时刻，只有一个设备能进行操作。,A,图编码方案：,控制单元生成一个二进制的“设备选择”码字，每个设备将“设备,I D,”,与之比较来确定自己是否可以进行操作,B,图编码方案：使用,n,中选,1,码来控制,n,个设备，在有效码字的,n,位中，只有一位为,1,，其他位都为,0,。,n,中选,1,码中的每一位直接与相应设备的控制输入相连，这简化了设备的设计，因为这种方式不,需要设备,I D,，,只需要一个“使能”输入位,表,2-9,列出了的,1 0,中选,1,码的码字。,n,中取,m,码,（,m-out-of-n code,）是,n,中取,1,码的广义化，其有效码字中有,m,位是,1,其余为,0,。,n,中取,m,码字可用,m,输入与门进行检测，与门的输入全为,1,时输出才为,1,，,2.14,n,维体与距离,n,维体,：,n,位二进制串可以用几何学形象化，把它作为一个物体的顶点,图,2-8,为,n,1,、,2,、,3,、,4,时的,n,维体。,n,维体有,2,n,个顶点，每个顶点用一个,n,位二进制串标记。画几何图的边时，令每个顶点与另外,n,个顶点相邻，而这,n,个顶点的位串与给定的顶点只有一位不同,对于合理的,n,值，,n,维体容易将某些编码和逻辑最小化问题形象化,距离,（,d i s t a n c e,）,或,汉明距离,用,n,维体来给出几何解释,将,2,个位串逐位比较，不同位的数目叫做这,2,个位串间的“距离”,以,n,维体术语来阐述，,2,个位串间的距离就是相应的,2,个顶点间路径的最短长度,n,位葛莱码的问题等效于沿着,n,维体的边寻找一个路径，路径上每个顶点恰好被访问一次,2.15,检错码和纠错码,数字系统的,差错,（,e r r o r,）,指数据损坏，从正确值变成了其他值。,差错由物理,故障,（,f a i l u r e,）,引起，故障可能是暂时的，也可能是永久的,差错模式,故障对数据的影响用,差错模式,来预测,最简单的差错模式：,独立差错模式,单个差错 多个差错,可靠性编码,能减少错误发生，或发现错误，甚至纠正错误的编码称为可靠性编码,检错码,使用,n,位二进制串的编码不一定包含,2,n,个码字,特性：当码字被损坏或改变时，很可能产生不属于编码字的位串，即,非编码字,使用检错码的系统仅仅产生、传输和存储编码字,可用简单的规则检测位串中的差错，,如果位串是一个编码字，就假定它是正确的；如果位串是一个非编码字，则包含差错。,某种编码只不过是,n,维体顶点的一个子集，为了检测所有单个错误，一个码字对应的顶点与另一个码字对应的顶点不能直接相邻。,检错与距离的关系,如果所有可能的编码字对之间的最小距离为,2,，则能检测全部单个差错。,要检测多个位的错，就要用到最小距离大于,2,的编码。,奇偶校验码,由信息位和校验位,(,冗余部分,),两部分组成。校验位的取值可使整个校验码中的,1,的个数按事先的约定成为奇数或偶数。,奇偶校验码可发现奇数位错误，但不能发现偶数位错误。,1,位奇偶校验码,纠错码与多重检错码,用来纠正差错的编码叫做纠错码,通过使用,1,个以上的奇偶校验位、或,校验位,（,check bits,），,根据某些适当的规则，可以构造最小距离大于,2,的编码,一般而言，最小距离为,2,c+1,的编码最多可以用来纠正,c,位错；最小距离为,2,c,+,d,+1,的编码最多可以纠正,c,位错，同时最多可以检测,d,位错。,汉明码（海明码）,通过增加少数几个校验位,能检测出多位出错，并能自动恢复一或几位出错位的正确值,实现原理：,在数据中加入几个校验位，将数据代码的码距（距离）比较均匀地拉大，并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出错，为进一步自动纠错提供了依据,海明码的编码规则,对于任意,i,值，其方法能产生（,2,i,-,1,）,位的编码，其中包含,i,个校验位和,2,i,-,1,-,i,个信息位。信息位较少的距离为,3,的编码,位置为,2,的幂的所有位都是校验位，其余为信息位，每个校验位与信息位的一个子集组成一组,当用二进制表示的时候，每个校验位与若干信息位组成一组，这些信息位在校验位上的值都是,1,。对给定信息位值的组合，校验位用来产生偶校验，也就是让这组内,1,的总数为偶数。,海明码的每一位码,Hi,（,包括数据位和校验位本身）由多个校验位校验，其关系是被校验的每一位位号要等于它的各校验位的位号之和。这样安排的目的，是希望校验的结果能正确反映出出错的位号。,例：一个字节进行海明编码的实现过程,N=8,校验位的位数应为,5,，故海明码的总位数是,13,，表示为,H,13,H,12,H,11,H,3,H,2,H,1,五个校验位,P,5,-P,1,对应的海明位号分别是,H,13,、,H,8,、,H,4,、,H,2,和,H,1,。,其他四位,P,i,的位号等于,2,i-1,的关系。其余为数据位,D,i,，,则有如下排列关系：,P,5,D,8,D,7,D,6,D,5,P,4,D,4,D,3,D,2,P,3,D,1,P,2,P,1,每个海明码的位号，等于参与校验它的几个校验位的位号之和的关系如表,海明码,位号,数据位,校验位,参与校验的,校验位 位号,被校验位的,海明码位号,=,校验位,位号之和,H1 P1,1 1=1,H2,P2,22=2,H3 D11,、,23=1+2,H4 P344=4,H5 D21,、,45=1+4,H6 D32,、,46=2+4,H7 D41,、,2,、,47=1+2+4,H8 P488=8,H9 D51,、,89=1+8,H10 D62,、,810=2+8,H11 D71,、,2,、,811=1+2+8,H12 D84,、,812=4+8,H13 P51313=13,5,个校验位各自只与本身有关，数据位,D1,是由校验位,P1,和,P2,校验，查表，,D1,的海明码位号为,3,，而,P1,和,P2,的海明码位号分别是,1,和,2,，满足,3=1+2,的关系。又如,D7,（,H11,）,是由,P1,（,H1,）、,P2,（,H2,）和,P4,（,H8,）,三个校验位校验等,P1=D1,D2D4D5D7,P2=D1D3D4D6D7,P3=D2D3D4D8,P4=D5D6D7D8,两位出错与一位出错分不清的问题，补充一个总校验位,P5,（例：,D2,和,D4,同时出错，,P2,有反映，,P1,、,P3,没反映，,D2,或,D4,单个出错）,P5=D1,D2D3D4D5D6D7D8P4P3P2P1,每一位数据位,都至少出现在三个P,i,值的形成关系中,当任一位数据发生变化时，必将引起,3,个或,4,个,Pi,值跟着变化，该海明码的码距是,4,按如下关系对所得到的海明码实现偶校验,S1=P1,D1D2D4D5D7,S2=P2D1D3D4D6D7,S3=P3D2D3D4D8,S4=P4D5D6D7D8,S5=P5D1D2D3D4D5D6D7D8P4P3P2P1,S5,S1,能,反映,13,位海明码的出错情况。任何偶数个数出错，,S5,一定为,0,，因此可区分两位出错或一位出错,校正位,P5,D8,D7 D6 D5,P4,D4 D3 D2 P3 D1 P2 P1,H,13,H,12,H,11,H,10,H,9,H,8,H,7,H,6,H,5,H,4,H,3,H,2,H,1,1 1 1 1 1,1,1 1 1 1 1 1 1,0 1 1 1 1 1 0 0 0 0 0 0,0,0 1 0 0 0 0 1 1 1 1 0 0 0,0 0 1 1 0 0 1 1 0 0 1 1 0,0 0 1 0 1 0 1 0 1 0 1 0 1,海明码位号,S位,当,S5,S1,为,00000,时，表明无错,当,5,个,S,位有,3,或,4,位为,1,时，认为是某一数据出错，出错数据位的海明码位号由,S4S3S2S1,这四位的译码值（分别是,12,、,11,、,10,、,9,、,7,、,6,、,5,、,3,）指出。,例当,S5S4S3S2S1=10111,时，,S4S3S2S1,的译码值为,7,，即,H7,，,也就是,D4,出错（,S1,、,S2,、,S3,的表达式分析，均牵涉到,D4,值）,S5,S4,S3,S2,S1,D,4,D,3,D,2,P,3,D,1,P,2,P,1,1,1,1,1,1,010,1,1000,1,1,0,1,000,1,P,1,=D,1,D,2,D,4,P,2,=D,1,D,3,D,4,P,3,=D,2,D,3,D,4,P,0=,D,4,D,3,D,2,P,3,D,1,P,2,P,1,P,3,P,2,P,1,P,0,如果一个码字至少要改变,3,位才能获得另一个码字，就能够证明汉明码的最小距离是,3,。也就是说，要证明码字中,1,位或,2,位改变后生成的是非编码字。,在计算机存储系统中，特别是存储电路占了大部分系统故障的大型机中，距离为,3,和,4,的汉明码常用于检错和纠错。,汉明码特别适合于非常长的存储字的汉明码常用于检错和纠错。,循环冗余校验码,CRC,码一般是,k,位信息码之后拼接,r,位,校验位,应用,CRC,码的关键是如何从,k,位,信息位简便地得到,r,位,校验位（编码），以及如何从,k+r,位信息码判断是否出错,生成多项式,CRC,码的两个重要应用是磁盘驱动器和数据网络,编码方案,待编码的,k,位有效信息组表达为多项式,M,（,x,）,M,（,x,）,=,C,k,-1,x,k-1,+,C,k,-2,x,k-2,+,C,i,x,i,+C,1,x,1,+C,0,C,i,为,0,或,1,将信息位左移,r,位，,则可表示为多项式,M,（,x,）,x,r,。,这样就可以空出,r,位，,以便拼接,r,位,校验位,信息位组,左移,r,位,k位,K,位,r,位,n,CRC,码是用多项式,M,（,x,）,x,r,除以称为生成多项式,G(x),（,产生校验码的多项式）所得的余数作为校验位,二维码