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

《第2章 数制与码制(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、常用的字符编码是ASCII码，即美国信息交换标准码。ASCII码用7位二进制串表示每个字符ASCII码包括大写字母和小写字母、数字、标点符号及各种非打印控制字符。2.13动作、条件和状态的编码数据类型：数值、位置、字符非数据类型：动作、条件和状态在数字系统设计中，经常遇到非数据的应用：将位串用于控制动作、标识条件、表示硬件的当前状态等等，最常用的编码类型是简单的二进制编码。设有n个不同的动作、条件或状态，则需用b位二进制编码来表示，b=[log2n]位括号[]表示上限函数，表示取大于或等于括号内数值的最小整数∴b为满足2

3、b≥n关系的最小整数例1：一个简单的交通信号灯控制器，在南-北（N-S）和东-西（E-W）街道的十字路口，信号有6种状态，这些状态可用3位二进制编码例2：有一个包含n个设备的系统，每个设备都完成一定的动作，在某一时刻，只有一个设备能进行操作。A图编码方案：控制单元生成一个二进制的“设备选择”码字，每个设备将“设备ID”与之比较来确定自己是否可以进行操作B图编码方案：使用n中选1码来控制n个设备，在有效码字的n位中，只有一位为1，其他位都为0。n中选1码中的每一位直接与相应设备的控制输入相连，这简化了设备的设计，因为这种方

4、式不需要设备ID，只需要一个“使能”输入位表2-9列出了的10中选1码的码字。n中取m码（m-out-of-ncode）是n中取1码的广义化，其有效码字中有m位是1其余为0。n中取m码字可用m输入与门进行检测，与门的输入全为1时输出才为1，2.14n维体与距离n维体：n位二进制串可以用几何学形象化，把它作为一个物体的顶点图2-8为n＝1、2、3、4时的n维体。n维体有2n个顶点，每个顶点用一个n位二进制串标记。画几何图的边时，令每个顶点与另外n个顶点相邻，而这n个顶点的位串与给定的顶点只有一位不同对于合理的n值，n维体容

5、易将某些编码和逻辑最小化问题形象化距离（distance）或汉明距离用n维体来给出几何解释将2个位串逐位比较，不同位的数目叫做这2个位串间的“距离”以n维体术语来阐述，2个位串间的距离就是相应的2个顶点间路径的最短长度n位葛莱码的问题等效于沿着n维体的边寻找一个路径，路径上每个顶点恰好被访问一次2.15检错码和纠错码数字系统的差错（error）指数据损坏，从正确值变成了其他值。差错由物理故障（failure）引起，故障可能是暂时的，也可能是永久的差错模式故障对数据的影响用差错模式来预测最简单的差错模式：独立差错模式单个差

6、错多个差错可靠性编码能减少错误发生，或发现错误，甚至纠正错误的编码称为可靠性编码检错码∵使用n位二进制串的编码不一定包含2n个码字特性：当码字被损坏或改变时，很可能产生不属于编码字的位串，即非编码字使用检错码的系统仅仅产生、传输和存储编码字∴可用简单的规则检测位串中的差错，如果位串是一个编码字，就假定它是正确的；如果位串是一个非编码字，则包含差错。某种编码只不过是n维体顶点的一个子集，为了检测所有单个错误，一个码字对应的顶点与另一个码字对应的顶点不能直接相邻。检错与距离的关系如果所有可能的编码字对之间的最小距离为2，则能

7、检测全部单个差错。要检测多个位的错，就要用到最小距离大于2的编码。奇偶校验码由信息位和校验位(冗余部分)两部分组成。校验位的取值可使整个校验码中的1的个数按事先的约定成为奇数或偶数。奇偶校验码可发现奇数位错误，但不能发现偶数位错误。1位奇偶校验码纠错码与多重检错码◇用来纠正差错的编码叫做纠错码◇通过使用1个以上的奇偶校验位、或校验位（checkbits），根据某些适当的规则，可以构造最小距离大于2的编码◇一般而言，最小距离为2c+1的编码最多可以用来纠正c位错；最小距离为2c+d+1的编码最多可以纠正c位错，同时最多可以

8、检测d位错。汉明码（海明码）通过增加少数几个校验位,能检测出多位出错，并能自动恢复一或几位出错位的正确值实现原理：在数据中加入几个校验位，将数据代码的码距（距离）比较均匀地拉大，并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出