第2章 数制与码制(2).ppt

《第2章 数制与码制(2).ppt》由会员分享，可在线阅读，更多相关《第2章 数制与码制(2).ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.11 葛莱码(格雷码)l为什么使用格雷码编码盘问题特点:对连续的码字之间只有一个数位变化例构造规则规则11)1位葛莱码有2个码字：0和1。2)（n+1）位葛莱码中的前2n个码字等于n位葛莱码的码字，按顺序书写，加前缀0。3)（n+1）位葛莱码中的后2n个码字等于n位葛莱码的码字，但按逆序书写，加前缀1。例：n=1 n+1=2位格雷码的构造0 00 11 11 0前缀加1后2个码字逆序前缀加02.12 字符编码l位串不一定只用来表示数值l最常见的非数值数据是文本，即取自某字符集的字符串。l在计算机中，根据已建立的约定，用位串表示每个字符。l最常用的字符编码是A S C I I码，即美国信息交

2、换标准码。A S C I I码用7位二进制串表示每个字符lA S C I I码包括大写字母和小写字母、数字、标点符号及各种非打印控制字符。2.13 动作、条件和状态的编码l数据类型：数值、位置、字符l非数据类型：动作、条件和状态在数字系统设计中，经常遇到非数据的应用：将位串用于控制动作、标识条件、表示硬件的当前状态等等，最常用的编码类型是简单的二进制编码。设有n个不同的动作、条件或状态，则需用b位二进制编码来表示，b=log2n 位括号 表示上限函数，表示取大于或等于括号内数值的最小整数 b为满足2bn关系的最小整数例1：一个简单的交通信号灯控制器，在南-北（N-S）和东-西（E-W）街道的十

3、字路口，信号有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

4、其余为0。n中取m码字可用m输入与门进行检测，与门的输入全为1时输出才为1，2.14 n维体与距离ln维体：n位二进制串可以用几何学形象化，把它作为一个物体的顶点图2-8为n1、2、3、4时的n维体。n维体有2n个顶点，每个顶点用一个n位二进制串标记。画几何图的边时，令每个顶点与另外n个顶点相邻，而这n个顶点的位串与给定的顶点只有一位不同l对于合理的n值，n维体容易将某些编码和逻辑最小化问题形象化l距离（d i s t a n c e）或汉明距离用n维体来给出几何解释将2个位串逐位比较，不同位的数目叫做这2个位串间的“距离”以n维体术语来阐述，2个位串间的距离就是相应的2个顶点间路径的最短长度

5、n位葛莱码的问题等效于沿着n维体的边寻找一个路径，路径上每个顶点恰好被访问一次2.15 检错码和纠错码l数字系统的差错（e r r o r）指数据损坏，从正确值变成了其他值。差错由物理故障（f a i l u r e）引起，故障可能是暂时的，也可能是永久的l差错模式故障对数据的影响用差错模式来预测l最简单的差错模式：独立差错模式l单个差错 多个差错l可靠性编码能减少错误发生，或发现错误，甚至纠正错误的编码称为可靠性编码l检错码使用n位二进制串的编码不一定包含2n个码字特性：当码字被损坏或改变时，很可能产生不属于编码字的位串，即非编码字l使用检错码的系统仅仅产生、传输和存储编码字可用简单的规则检

6、测位串中的差错，如果位串是一个编码字，就假定它是正确的；如果位串是一个非编码字，则包含差错。某种编码只不过是n维体顶点的一个子集，为了检测所有单个错误，一个码字对应的顶点与另一个码字对应的顶点不能直接相邻。l检错与距离的关系如果所有可能的编码字对之间的最小距离为2，则能检测全部单个差错。要检测多个位的错，就要用到最小距离大于2的编码。l奇偶校验码由信息位和校验位(冗余部分)两部分组成。校验位的取值可使整个校验码中的1的个数按事先的约定成为奇数或偶数。u 奇偶校验码可发现奇数位错误，但不能发现偶数位错误。1位奇偶校验码l纠错码与多重检错码用来纠正差错的编码叫做纠错码通过使用1个以上的奇偶校验位、

7、或校验位（check bits），根据某些适当的规则，可以构造最小距离大于2的编码一般而言，最小距离为2 c+1的编码最多可以用来纠正c位错；最小距离为2c+d+1的编码最多可以纠正c位错，同时最多可以检测d位错。l汉明码（海明码）通过增加少数几个校验位,能检测出多位出错，并能自动恢复一或几位出错位的正确值l实现原理：在数据中加入几个校验位，将数据代码的码距（距离）比较均匀地拉大，并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出错，为进一步自动纠错提供了依据 l海明码的编码规则对于任意i值，其方法能产生

8、（2i-1）位的编码，其中包含i个校验位和2i-1-i个信息位。信息位较少的距离为3的编码位置为2的幂的所有位都是校验位，其余为信息位，每个校验位与信息位的一个子集组成一组当用二进制表示的时候，每个校验位与若干信息位组成一组，这些信息位在校验位上的值都是1。对给定信息位值的组合，校验位用来产生偶校验，也就是让这组内1的总数为偶数。l海明码的每一位码Hi（包括数据位和校验位本身）由多个校验位校验，其关系是被校验的每一位位号要等于它的各校验位的位号之和。这样安排的目的，是希望校验的结果能正确反映出出错的位号。例：一个字节进行海明编码的实现过程N=8 校验位的位数应为5，故海明码的总位数是13，表示

9、为H13H12H11H3H2H1l五个校验位P5-P1对应的海明位号分别是H13、H8、H4、H2和H1。其他四位Pi的位号等于2i-1的关系。其余为数据位Di，则有如下排列关系：P5D8D7D6D5P4D4D3D2P3D1P2P1每个海明码的位号，等于参与校验它的几个校验位的位号之和的关系如表海明码位号数据位校验位参与校验的校验位 位号被校验位的海明码位号=校验位 位号之和H1 P1 1 1=1H2 P2 22=2H3 D11、23=1+2H4 P344=4H5 D21、45=1+4H6 D32、46=2+4H7 D41、2、47=1+2+4H8 P488=8H9 D51、89=1+8H10

10、 D62、810=2+8H11 D71、2、811=1+2+8H12 D84、812=4+8H13 P51313=135个校验位各自只与本身有关，数据位D1是由校验位P1和P2校验，查表，D1的海明码位号为3，而P1和P2的海明码位号分别是1和2，满足3=1+2的关系。又如D7（H11）是由P1（H1）、P2（H2）和P4（H8）三个校验位校验等P1=D1D2D4D5D7P2=D1D3D4D6D7P3=D2D3D4D8P4=D5D6D7D8两位出错与一位出错分不清的问题，补充一个总校验位P5（例：D2和D4同时出错，P2有反映，P1、P3没反映，D2或D4单个出错）P5=D1D2D3D4D5D

11、6D7D8P4P3P2P1每一位数据位,都至少出现在三个Pi值的形成关系中,当任一位数据发生变化时，必将引起3个或4个Pi值跟着变化，该海明码的码距是4按如下关系对所得到的海明码实现偶校验S1=P1D1D2D4D5D7S2=P2D1D3D4D6D7S3=P3D2D3D4D8S4=P4D5D6D7D8S5=P5D1D2D3D4D5D6D7D8P4P3P2P1S5S1能反映13位海明码的出错情况。任何偶数个数出错，S5一定为0，因此可区分两位出错或一位出错校正位P5 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1H13 H12 H11 H10 H9 H8 H7 H6 H5

12、H4 H3 H2 H11 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 1 0 0 00 0 1 1 0 0 1 1 0 0 1 1 00 0 1 0 1 0 1 0 1 0 1 0 1 海明码位号S位当S5S1为00000时，表明无错当5个S位有3或4位为1时，认为是某一数据出错，出错数据位的海明码位号由S4S3S2S1这四位的译码值（分别是12、11、10、9、7、6、5、3）指出。例当S5S4S3S2S1=10111时，S4S3S2S1的译码值为7，即H7，也就是D4出错（S1、S2、S3的表达式分析，

13、均牵涉到D4值）S5S4S3S2S1D4D3D2P3D1P2P1111110101100011010001P1=D1D2D4P2=D1D3D4P3=D2D3D4P0=D4D3 D2 P3 D1 P2 P1P3P2P1P0如果一个码字至少要改变3位才能获得另一个码字，就能够证明汉明码的最小距离是3。也就是说，要证明码字中1位或2位改变后生成的是非编码字。在计算机存储系统中，特别是存储电路占了大部分系统故障的大型机中，距离为3和4的汉明码常用于检错和纠错。汉明码特别适合于非常长的存储字的汉明码常用于检错和纠错。l循环冗余校验码lCRC码一般是k位信息码之后拼接r位校验位l应用CRC码的关键是如何从

14、k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错l生成多项式lCRC码的两个重要应用是磁盘驱动器和数据网络编码方案待编码的k位有效信息组表达为多项式M（x）M（x）=Ck-1xk-1+Ck-2xk-2+Cixi+C1x1+C0Ci为0或1将信息位左移r位，则可表示为多项式M（x）xr。这样就可以空出r位，以便拼接r位校验位信息位组左移r位k位 K位 r位nCRC码是用多项式M（x）xr除以称为生成多项式G(x)（产生校验码的多项式）所得的余数作为校验位l二维码(乘积码)把信息位排成二维矩阵，行、列奇偶位分别用来校验行和列。编码Crow用于行，其最小距离为dr o w

15、；编码Cc o l用于列，其最小距离为dc o l二维码的重要应用是在R A I D存储系统中，R A I D表示廉价磁盘冗余阵列l校验和码上述奇偶校验操作是基于数位的模2加法，即在一组数位中，如果1的个数为偶数，则模2和为0；1的个数为奇数则模2和为1。这种按模加法的技术可以扩展到除2外的其他基数，用于形成检验位。l模2 5 6加法来检查字节所生成的单个校验字节，称做校验和，它等于所有的信息字节按模2 5 6相加所得到的和2.16 用于串行数据传输与存储的编码l大多数计算机和其他数字系统以并行格式传输和存储数据l网络上串行传输数据l串行格式则允许在任一时刻只传输或存储数据的1位l速率（bit

16、 rate，单位b p s）即是每秒传输l的比特数，它在数值上等于每秒内时钟频率的周期数（赫兹，或H z）l位时间位速率的倒数，在数值上等于时钟周期（秒）l位元（bit cell）每位占用的时间每个位元期间出现在传输线上的实际信号格式取决于线路码（line code）不归零制（N o n-R e t u r n-t o-Z e r o，N R Z）最少需要3个信号用于恢复串行数据流：定义位元的时钟信号，定义字边界的同步信号和串行数据本身串行线路编码不归零逢1翻转归零制双极性归零制在N R Z编码中，发送到线路上的每个位值占据整个位元，对短距离传输而言，这是最简单和最可靠的编码方案需要提供定义位元的数据发送时钟信号数字锁相环（digital phase-locked loop,DPLL）从串行数据流中恢复时钟信号的模拟/数字电路