《第2章信息编码及在计算机中的表示.ppt》由会员分享，可在线阅读，更多相关《第2章信息编码及在计算机中的表示.ppt（93页珍藏版）》请在三一办公上搜索。
1、第2章信息编码及在计算机中的表示,内容,2.1 信息的数字化编码2.2 进位计数制及其相互转换 2.3 非数值数据的表示 2.4 数值数据的表示和运算 2.5 数据校验码,2.1 信息的数字化编码,编码：是用来将信息从一种形式转变为另一种形式的符号系统，通常选用少量最简单的基本符号和一定的组合规则，以表示出大量复杂多样的信息。信息的数字化编码：是指用“0”或“1”这种量最少、最简单的二进制数码，并选用一定的组合规则，来表示数据、文字、声音、图形和图像等各种复杂的信息。计算机中采用的是二进制数码,为什么？（重点）,2.2 进位计数制及其相互转换,2.2.1 进位计数制2.2.2 常用进位计数制间
2、的相互转换,2.2.1 常用的进位计数制,十进制数二进制数八进制数十六进制数,数制中的三个基本名词术语：数码：用不同的数字符号来表示一种数制的 数值，这些数字符号称为“数码”。基：数制所使用的数码个数称为“基”。权：某数制各位所具有的值称为“权”。,2.2.1 进位计数制,数码：0、1、8、9基：10（逢十进一，借一当十）权：以10为底的幂 任何一个十进制数DnDn-1D1D0D-1，可以表示成按权展开的多项式：Dn10nDn-110n-1D1101D0100D-110-1D-m10-m例如：1234.5的按权展开多项为：1234.51103210231014100510-1,1.十进制数(D
3、ecimal System),二进制数,二进制(Binary System)数码：0和1 基：2 权：以2为底的幂任何一个二进制数BnBn-1B1B0B-1B-m，可以表示成按权展开的多项式：Bn2nBn-12n-1B121B020B-12-1B（-m+1）2-(m-1)+B-m2-m例如：1101.01的按权展开多项为：1101.0112312202112002-112-2,八进制数,八进制数(Octave System)数码：0、1、6、7 基：8权：以8为底的幂八进制数的一般式可以表示为：n8nn-18n-1181080-18-1（-m+1）8-(m-1)-m8-m,十六进制数,十六进制
4、(Hexadecimal System)数码：0、1、8、9、A（1010）、B（1011）、C（1100）、D（1101）、E（1110）、F（1111）基：16权：以8为底的幂十六进制数的一般式可以表示为：n16nn-116n-111610160-116-1（-m+1）16-(m-1)-m16-m,例:二进制数1011.0101及其对应的八进制数、十进制数和十六进制数可以表示为：1101.0111(2)15.34(8)13.4375(10)E.7(16)或:(1101.0111)2(15.34)8(13.4375)10(E.7)16或:1101.011115.3413.4375E.7,二进
5、制数、八进制数、十六进制数转换为十进制数各种进位计数制可统一表示为下式：式中:R 某种进位计数制的基数；i 位序号；Ki 第i位上的一个数码为0R-1中的任一个；Ri 则表示第i位上的权；m,n 最低位和最高位的位序号。用上式可将任何一个二进制数、八进制数、十六进制数直接转换为十进制数,这叫做按权展开法。,2.2.2 常用进位计数制间的相互转换,例：二进制数转换为十进制数(1011.0101)212302212112002-112-202-312-4802101/401/16(11.3125)10 八进制数转换为十进制数(75.21)878158028-118-2 5652/81/64(45.
6、20238)10 十六进制数转换为十进制数(175.FB)161162716151601516-11116-2256112515/1611/162(373.98046875)10,十进制整数转换为二进制数（连除基数、倒取余）方法：除以2取余法。即逐次除以2，直至商为0，得出的余数即为二进制数各位的数码。【例2.1】把一个十进制数156转换为二进制数。结果：(156)10(10011100)2,十进制数转换为二进制数,方法：乘2取整法。即逐次乘以2，从每次乘积的整数部分得到二进制数各位的数码。【例2.2】把十进制小数 0.34375转换为二进制小数。结果：(0.34375)10(0.01011)
7、2 连乘基数、正向取整。,十进制纯小数转换为二进制数,二进制数与八进制数的转换,1.二进制数转换成八进制数方法：将二进制数从小数点开始分别向左(对二进制整数)或向右(对二进制小数)每三位组成一组，每一组有3位二进制数，转换成八进制数码中的1个数字，连接起来即可。不足3位的补0。,【例2.3】把二进制数(101100011.011100101)2转换为八进制数。,101 100 011.011 100 101,即有：(101100011.011100101)2(543.345)8,5 4 3.3 4 5,二进制数与八进制数的转换,【例2.4】把八进制数(7351.65)8 转换为二进制数。,即有
8、：(7351.65)8(111011101001.110101)2,7 3 5 1.6 5,111 011 101 001.110 101,2.八进制数转换成二进制数方法：将每1位八进制数写成相应二进制3位数，顺序写好即成。,二进制数与十六进制数的转换,二进制数转换成十六进制数方法：把十六进制数每位的数字与二进制数的4位数相对应。【例2.5】把二进制数(110100110101)2转换为十六进制数。1101 0011 0101 D 3 5即有:(110100110101)2(D35)16,二进制数与十六进制数的转换,十六进制数转换成二进制数方法：将每1位十六进制数写成相应的二进制4位数，顺序写
9、好即成。例如：E 8 B 1110 1000 1011即有:(E8B)16(111010001011)2 对于十进制数转换为八进制数或十六进制数的问题，我们可以先把十进制数转换成二进制数，然后再转换为八进制数或十六进制数。,4种数制之间的转换可参照下表进行,2.3 非数值数据的表示,2.3.1 字符数据的编码2.3.2 汉字编码,2.3.1 字符数据的编码,非数值数据又叫符号数据或字符数据，包括字母和符号。目前世界上用ASCII码(American Standard Code for Information Interchange)来表示。ASCII码有7位ASCII码和8位ASCII码两种，
10、7位ASCII码称为标准ASCII码，8位ASCII码称为扩充ASCII码。,ASCII码字符编码表,2.3.2 汉字编码,汉字编码：机内码和机外码机内码：是在计算机内部使用的用二进制代码表示的汉字编码，用于在计算机内部存储、交换、处理加工汉字信息机外码：是不在计算机内使用的汉字编码，主要是指汉字输入码。此外还有供输出的汉字字型点阵码。,国标码（了解）,国标码：指我国1981年公布的“中华人民共和国国家标准信息交换汉字编码”，是一种国家标准编码，代号为“GB2312-80”。它以94个可显示的ASCII码字符为基集，由两个字节构成。国标码与ASCII码属同一制式，可以认为国标码是扩展的ASCI
11、I码。,国家标准(GB2312-80)汉字字符集示意图,国标码用两个字节的16进制数表示，例如“文”的国标码是“4E44H”，“中华人民共和国”的国标码分别是“5650H、3B2AH、484BH、4371H、3932H、3A4DH、397AH”。,汉字机内码（实质：汉字的地址）,汉字机内码：在计算机系统内部用来表示汉字的编码。ASCII码是一种西文机内码在设计汉字机内码时，应遵循如下原则：汉字机内码的编码不能有二义性，否则和其他编码分不清，例如要能和ASCII码严格区分。代码的长度尽可能短，所能表示的汉字要尽可能多。应与国标码有相应的对应关系，以便于对汉字库的处理和对汉字的查找。,汉字机内码与
12、国标码的关系,汉字机内码高位字节国标码高位字节80H汉字机内码低位字节国标码低位字节80H例如：“文”的国标码是“4E44H”，要求它的机内码，只要把“文”字国标码两个字节的16进制数4EH和44H分别加80H，即成该汉字的机内码。4EH+80H=CEH44H+80H=C4H,汉字输入码（机外码）,汉字输入码：指直接从键盘输入的各种汉字输入方法的编码，属于外码。按照编码原理，汉字输入码主要分为三类：数字码（区位码和电报码）、拼音码和字形码。还有以汉字的音和形相结合的音形码和形音码。,数字码 数字码：将待编码的汉字集以一定的规则排序以后，依次逐个赋予相应的数字串作为汉字输入代码。典型的数字码：区
13、位码和电报码 优点：无重码 缺点：代码难以记忆。,例如，“文”字的区位码为4636，区码和位码分别用十六进制表 示即为“2E24H”，转换成国标码就是“4E44H”，它的机内码为“CEC4H”。,区位码与国标码、机内码的对应关系为：用十进制数输入的区码和位码先分别转换为十六进制数(各一个字节)，再分别加上20H，就成了国标码；再在两个字节分别加上80H，就成为机内码。,拼音码：汉语拼音方案为基础的输入方法最大优点：简单易学，只要会汉语拼音，就能输入汉字，并且输入时不影响思考，适合于业务人员和专业技术人员使用。全拼输入法双拼输入法增加联想功能以词为单位的智能拼音输入法,字形码：以汉字的形状确定的
14、编码最大特点：能广泛地为国内外不同地区使用汉字方言较重的人们服务缺点：编码规则较复杂。典型：五笔字型输入法 其它输入方法：音形码和形音码,汉字字型码汉字点阵字模库（重点）,汉字信息存储在计算机内有两种编码：一种是汉字机内码，另一种是字型点阵码。点阵字型方式：是把汉字像图形一样置于网状方格上，每格是存储器中的1个位(bit)，1616点阵是在纵向16点、横向16点的网状方格上描绘一个汉字，有笔划的格对应1，无笔划的格对应0。,图中表示了“华”字的1616点阵字型。这种用点阵形式存储的汉字字型信息的集合称为汉字的点阵字模库，简称汉字库。,汉字点阵字模的分类,汉字的、是计算机用于汉字输入、内部处理、
15、输出三种不同用途的编码。,汉字字符集（了解）,目前，在我国使用的计算机汉字操作平台中有三种汉字字符集。国标码字符集GB2312-80：我国政府于1981年公布的信息交换用汉字编码字符集 基本集，在该字符集中收录了6763个常用汉字和各种符号682个，合计7445个。GBK汉字集：即汉字内码扩充规范,”大字符集”。在此汉字集中一共收录了20900个汉字，它包容了GB2312-80的6763个常用汉字，台湾BIG5码的13000多个汉字。此扩充规范发布后，美国的Microsoft公司率先将GBK规范装入Windows95中。在Windows95简体中文版中，又增加了101个补充字，一共有21001
16、个字。,汉字字符集（了解）,国标码GB18030字符集：即GB18030-2000 信息技术 信息交换用汉字编码字符集 基本集的扩充新标准。该字符集共收录了27000多个汉字，总编码空间超过150万个码位，是真正的大汉字集。它在体系结构上延续了GB2311-1990信息处理 七位和八位编码字符集 代码扩充技术编码体系，采用单/双/四字节混合编码，该标准还收录了藏文、蒙文、维吾尔等主要的少数民族文字，以及世界上几乎所有的语言文字，为中文信息在Internet上的传输与交换提供了保障。,2.4 数值数据的表示和运算（重点）,2.4.1 机器数2.4.2 定点数的原码、反码、补码和移码2.4.3 定
17、点数和浮点数2.4.4 十进制数的编码,2.4.1 机器数,1.机器数和真值的概念符号的数值化：把正负符号用一位二进制数码来表示。符号位:符号数值化后占的若干个数值位。机器数:数的符号用二进制数“0”或“1”来表示的，且符号位总是在该数的最高数值位之前的那种数。规定“0”表示正号，“1”表示负号。原码、补码、反码、移码等把符号位和数值位一起编码表示的数就是机器数。真值:用“+”、“-”表示符号的那种数。例：N1=+0.1011，N2=-0.1011，这是真值，表示成机器数就为N1原=0.1011，N2原=1.1011。,用二进制数码表示 优点：使用元器件简单，便于硬件实现 运算简单 节省存储设
18、备 便于用逻辑代数进行逻辑设计机器数所表示的数值范围是有限的，无法表示时，便产生溢出机器数所表示的数值范围是由机器的字长决定，字长越长，所能表示的数的范围越大。,机器数的特点,例：一台字长为n位的机器，它所能表示的机器数X除0以外，最小是1，最大是2n-1，即其所表示的范围是：1X2n-1比1小的值，认为是机器零；数值大于2n-1，机器不能表示，我们称为“溢出”。,机器数的特点,对于不带符号位的定点纯小数(即小数点位于机器数的最左边的数)，字长为n位的机器所能表示的机器数X的范围是：2-n X1-2-n，如图所示：凡是小于2-n的数都认为是机器零；如果数值大于1-2-n的数，机器不能表示，被认
19、为机器数无穷大，产生溢出。从上面的分析情况可以看除，计算机产生溢出的一个重要原因是由计算机的字长造成的。,机器数的特点,符号的数值化表示 用0表示正(“+”)号，用1表示负(“-”)号。以字长为8位为例，+1101101和-1101101这两个数的表示如图所示:,根据小数点位置的不同，机器数有定点数和浮点数。定点数表示方式:小数点的位置是固定不变的数称为定点数。若约定小数点固定于机器数最低位的右边，则机器数表示整数；若约定小数点固定于机器数数值位的左边符号位的右边，则机器数表示纯小数。浮点数表示方式:浮点数是一种指数形式的表示方式，其一般表示式为：X=2rx。其中,r称为X的阶码，它指明了小数
20、点的位置，表示数的大小；x称为X的尾数，表明了X的有效值。,定点数和浮点数的不同表示,二进制数的运算规则,算术运算规则加法规则:000 011 101 1110减法规则：000 1011 101 110乘法规则：000 010 100 111除法规则：010 111,逻辑运算规则,逻辑或：又称逻辑加，用符号“”或“+”来表示。其运算规则为：000 011 101 111逻辑与：又称逻辑乘，用符号“”或“”来表示。其运算规则为：000010100111 逻辑非：即对每位的逻辑值取反，用二进制数字上划线表示规则为：逻辑异或：即实现按位加的功能，异或运算用符号()表示其运算规则是：000 01110
21、1 110进行异或运算的两位不相同时，异或结果为1，两位相同时，异或结果为0。,上一页,下一页,2.4.2 定点数的原码、反码、补码和移码,定点数的原码原码表示方法：符号位为0表示正数，为1表示负数，数值部分用二进制数的绝对值表示的方法。通常用X原表示X的原码。例如,要表示+59和-59的原码，假设机器数的位数是8位(机器的字长8位)，最高位是符号位，其余7位是数值位，那么+59和-59的原码表示为59原0011101159原10111011写成一般式则为：正数的原码 X原X(2n-1X0)负数的原码 X原2n-1-X(-2n-1X0)应注意，0的原码有两个值，有“正零”和“负零”之分。0原0
22、00000000原10000000,定点数的补码,补码的定义是：把某数X加上模数K，称为以K为模的X的补码。X补=K+X因此正数的补码是最高位为符号“0”，数值部分为该数本身；负数的补码是最高位为符号“1”，数值为用模2减去该数的绝对值。,求一个二进制数补码的方法是，正数的补码与其原码相同；负数的补码是先把其原码除符号外的各位先求反，然后在最低位加1。【例2.16】若X+0.1011，Y-0.1011，求X补、Y补。解：X补0.1011 Y补10-0.10111+1-0.10111.0101(mod 2)0的补码只有一种形式，就是n位0。字长为n位的定点整数补码的定义式为：,3.反码,正数的反
23、码就是这个数本身，而负数的反码是符号位为1，数值部分等于其绝对值各位求反。例如：59反00111011，59反11000100。零的反码也有两个，0反00000，-0反10000字长为n的定点整数反码的定义式为：可得到如下公式：XYX(Y的补码)X(Y的反码1),在8位机中，补码表示的范围为+127-128，下表列出了8位二进制数的各种表示方法。,目前大多数计算机均采用补码存储、补码运算，其运算结果仍为补码形式。【例2.17】在字长为8位的计算机中，求下列数的原码、反码及补码+18、-18、+31、-31、+127、-127解：+18原+18反+18补00010010-18原10010010-
24、18反11101101-18补11101110+31原+31反+31补00011111-31原10011111-31反11100000-31补11100001+127原+127反+127补01111111-127原11111111-127反10000000-127补10000001,4.移码,移码也叫增码或偏码，常用于表示浮点数中的阶码。对于字长为n的计算机，若最高位为符号位，数值为n-1位当偏移量取为2n-1时，其真值x所对应的移码的表示公式为：X移2n-1+X(-2n-1X2n-1)移码和补码之间的关系:当0X2n-1 时，X移2n-1+X2n-1+X补 当-2n-1X0 时，X移2n-1
25、+X(2n+X)-2n-1X补-2n-1 可见，X移可由X补求得，方法是把X补的符号位取反，就得到X移。,4.移码,【例2.18】X+1011，Y-1011，求X移和Y移。解：X补01011，所以 X移11011Y补10101，所以 X移00101,最高一位为符号位，其取值与原码、补码都相反，“1”表示正号，“0”表示负号。移码常用于表示浮点数的阶码，通常只使用整数。对移码一般只执行加减运算，在对两个浮点数进行乘除运算时，是尾数实现乘除运算，阶码执行加减运算。对阶码执行加减运算时，需要对得到的结果加以修正，修正量为2n-1，即要对符号位的结果取反后，才得到移码形式的结果。在移码的表示中，0有惟
26、一的编码，即0移10000，而且，机器零的形式为 000000。即当浮点数的阶码-2n-1时，不管尾数值的大小如何，都属于浮点数下溢，被认为其值为0，这时，移码表示的阶码值正好是每一位都为0的形式，与补码的0完全一致。这有利于简化机器中的判零线路。,移码的性质,2.4.3 定点数和浮点数,定点数表示法：通常把小数点固定在数值部分的最高位之前，或把小数点固定在数值部分的最后面。前者将数表示成纯小数，后者把数表示成整数。如图所示。对纯小数进行运算时，要用适当的比例因子进行折算，以免产生溢出，或过多损失精度。,浮点数表示法,浮点数是指在数的表示中，其小数点的位置是浮动的。任一个二进制数N可以表示成：
27、N2EM 式中，M为数N的尾数或数码，E为指数，是数N的阶码，是一个二进制整数 浮点数分为阶码和尾数两个部分。,浮点数的格式表示,格式1：Ms为尾数的符号位，安排在最高一位；E为阶码，紧跟符号位之后，占m位；M为尾数，在低位部分，占n位。,【例2.19】对一个真值为+23.25的十进制数，用浮点数格式1表示法表示其原码。(23.25)10(10111.01)2，用浮点数表示其原码为：2+1010.1011101，则在机器中表示为：这里阶码和尾数都用原码表示，实际上往往是尾数用补码表示，阶码用移码表示。,格式1举例,格式2：其中：Ns为阶码的符号位，安排在最高一位；E为阶码，紧跟阶符位之后，占m
28、位；Ms为尾数的符号位，在尾数之前的一位，M为尾数，在低位部分，占n位。,浮点数的格式表示,【例2.20】例2.19中的十进制数+23.25，用浮点数格式2表示法表示其原码、反码和补码。+23.25化成浮点数为：2+1010.1011101，则其原码、反码和补码分别表示为：,格式2举例,在浮点数的表示中，要注意三个问题：阶码的位数和尾数的位数的关系。例如，用32位表示的一个浮点数，符号位占1位，阶码用8位，尾数用23位，数的表示范围约为1.71038，精度约为十进制的7位有效数字。浮点数通常采用规格化的表示方法。所谓浮点数的规格化就是其尾数的第一位要为1，若不为1，就要用“左规”的方法使其为1
29、。左规就是尾数向左移动(同时调整阶码)，直至尾数的第一位为1或阶码为全0或最小值。如：2100.1101，-2100.1101就是规格化的浮点数；而2110.0110，-2110.0110是非规格化的浮点数。,浮点数表示法,【例2.21】把非规格化的浮点数N2110.0110规格化 解：把浮点数N的尾数向左移一位(或尾数的小数点右移一位)，变成0.1100，同时，阶码递减1，得到N2100.1100，就是规格化的浮点数。当一个浮点数的尾数为0，不论其阶码为何值；或者阶码的值遇到比它能表示的最小值还小时，不管其尾数为何值，计算机都把该浮点数看成是0，称为机器零。,2.4.4 十进制数的编码,BC
30、D码(Binary-Coded Decimal)是用4位二进制编码来表示一个十进制数，代码的每位都是固定有权的，因此称为有权码。把4位代码中为1的各位的权加起来，即得到这个对应的十进制数。,BCD码,8421码8421码是二进制编码各位的权分别是8、4、2、1，因此叫8421码。下表是十进制数码与8421码的对照表。,要注意，每1位十进制数码对应4位8421码，如十进制数175的8421码是000101110101，写成表达式即为：(175)10=(000101110101)8421,2421码2421码是二进制编码各位的权分别是2、4、2、1，因此叫2421码。下表6是十进制数码与2421码
31、的对照表。,注意，每1位十进制数码对应4位2421码，如十进制数175的2421码是000111011011，写成表达式即为(175)10=(000111011011)2421,BCD码,其他有权码BCD码中的其他有权码还有5211码、8-4-2-1码、4311码。它们也都是4位编码对应一位十进制数。下表列出了这三种有权码与十进制数的对照表。,BCD码,总结以上5种BCD码，可以归纳出BCD码的特点如下：用4位二进制数编码；是有权码，每位的权根据码制的不同而不同；除8421码外，其余都是对9的自补码。所谓对某数的自补码，就是只要该码自身取反，便可得到该码所对应的十进制数对某数的补码。对9的自补
32、码就是该码取反后，便可得到该码所对应的十进制数对9的补码。例如，5的2421码是1011，按位取反后得到0100，其对应的十进制数是4，4是5对9的补码。5的5211码是1000，按位取反后得到0111，其对应的十进制数也是4，是5对9的补码。,BCD码,余3码,把每个8421码都加上0011（即3）就得到余3码。余3码和十进制数、8421码的对应关系如表2-8所示。余3码的特点是：用4位二进制数编码；是无权码；也是对9的自补码；两个余3码相加，其和要进行修正，修正的方法是：有进位的位，结果加3(0011)；无进位的位，结果减3(0011)；两个余3码相减，其和也要进行修正，修正的方法是：对结
33、果中向高位借位的减3(0011)修正。,【例2.22】有两个十进制数38和45，试用余3码求其和。解：写出38和45的余3码(38)10=(01101011)余3码(45)10=(01111000)余3码 两个余3码相加 0110 1011+0111 1000 1110 0011 对余3码的和进行修正 1110 0011-0011+0011 1011 0110 从余3码求十进制数：(10110110)余3码=(83)10,余3码,格雷码,格雷码(Gray)是任何两个相邻的代码只有一个二进制位的状态不同，其余3个二进制位的状态必须相同的一种编码。可由8421码的相邻两位异或而得到的，例如，6的8
34、421码为0110，其格雷码就是0101。,上图是十进制数09和格雷码的对照表,格雷码的特点可以归纳为以下三点：是4位编码；是无权码；码距为1。码距:是指两个合法代码之间的不相同的位数。格雷码的每两个相邻的代码，如5(0111)和6(0101)之间尽有一位不相同，所以码距为1。像8421码的5(0101)和6(0110)之间有两位不相同，7(0111)和8(1000)之间四位都不相同，所以8421码的码距是不定的。,格雷码,2.5 数据校验码,在计算机系统中对数据的存取、传送数据有时会出现错误。为了提高数据传送的正确性，一方面要通过电路的可靠性来保证，另一方面在数据代码传送过程中，需要对代码进
35、行校验，代码校验的方法最好能查错和纠错。数据校验码就是一种常用的带有发现某些错误或带有自动改错能力的数据编码方法。常用的代码校验方法有奇偶校验、汉明校验和循环冗余校验三种方法。,2.5 数据校验码,2.5.1 码制的距离2.5.2 奇偶校验码2.5.3 汉明码2.5.4 循环冗余校验码,2.5.1 码制的距离,两个码字的距离：两个码字逐位比较，其不同字符的个数称为这两个码字的距离。例如0101110和0110110这两个码之间，有2个字符不同，则这两个码字之间的距离为2。一个码制的距离定义为：在这个编码之中各码字之间的最小距离。码制的距离与代码校验关系:这就是说，计算机在传送代码过程中发生一位
36、错，在代码距离为1的情况下是检查不出来的。如果代码的距离为2，当某一位在传送过程中出错时，这个出错代码就不是合法代码，从而判断出这是个错误代码，但不知道哪一位有错。,2.5.2 奇偶校验码,奇偶校验码的构成规则是在每个传送码的左边或右边加上1位奇偶校验位“0”或“1”，若是奇校验位，就把每个编码中1的个数凑成奇数；若是偶校验位，就把每个编码中1的个数凑成偶数。,距离为1的二进制码加上奇偶校验位就成为距离为2的码，这种编码能发现1个错误或奇数个错误，但不能定位。因此对奇偶校验码的评价是，能发现一位或奇数个位出错，而无定位纠错能力。,2.5.3 汉明码,以奇偶校验为基础的，但校验位不是1位，而是几
37、位。汉明码的实现原理是，在数据中加入几个检验位，将数据代码的码距比较均匀地拉大，并把数据的每一个二进制位分配在几个奇偶校验组中。汉明校验码的构成规则是由信息位和一组校验位构成汉明码这些校验位穿插在信息位中间。校验位的位数K和信息位的位数N应满足下述关系：2K-1N+K此式称为汉明不等式。,下表是按照汉明不等式计算出的N值和K值的对应关系表。,汉明码的构成和纠错原理,例：8421码是4位编码，其N值为4，则其K值为3。设信息位为I4、I3、I2、I1，按8421码编码，校验位是P3、P2、P1。一种8421汉明码如下表所列。,校验位的取值按如下公式求得：P3I4I3I2 P3 应满足I4、I3、
38、I2、P3为偶检验P2I4I3I1 P2 应满足I4、I3、I1、P2为偶检验P1I4I2I1 P1 应满足I4、I2、I1、P1为偶检验三个校验和按以下公式求得：S2I4I3I2P3S1I4I3I1P2S0I4I2I1P1若S2S1S00，则说明传送无错，即接收的代码是正确的；若S2S1S00，则说明传送有错，S2S1S0的十进制数值就是出错的位号，故将S2S1S0称为指误字。,7 6 5 4 3 2 1 I4 I3 I2 P3 I1 P2 P1发送4的汉明码 0 1 0 1 0 1 0接收的汉明码 0 1 1 1 0 1 0接收的汉明码第5位发生了错误，0变成了1。检验的情况是：S2I4I
39、3I2P3=0111=1S1I4I3I1P2=0101=0S0I4I2I1P1=0100=1可以得到，S2S1S0101，说明是第5位(信息位I2)在传送中发生了错误，只要将这一位取反就行。,【例2.21】一个8421码4的汉明码在传送时第5位发生错误的查纠错例子,汉明码能查出2位以上出错位，但不能定位。下面举一个2位出错的例子 7 6 5 4 3 2 1 I4 I3 I2 P3 I1 P2 P1发送4的汉明码 0 1 0 1 0 1 0接收的汉明码 0 0 1 1 0 1 0检验的情况是：S2I4I3I2P3=0011=0S1I4I3I1P2=0001=1S0I4I2I1P1=0100=1这
40、样，S2S1S0011，这里不是第3位出错，结果显然不对。若汉明码和奇偶校验码配合使用，则可区别是2位错还是1位错。,【例2.22】一个8421码4的汉明码在传送时第5、6两位同时发生错误。,2.5.4 循环冗余校验码,循环冗余校验码(CRC)是目前通信系统中广泛采用的一种校验码，主要用在同步通信上。编码格式循环冗余校验码的编码格式如图所示。循环冗余校验码由两部分组成，左边是信息位，右边是校验位；若总的循环冗余校验码的长度为n位，信息位是k位，则校验位就占n-k位。故该校验码也称(n,k)码。附加校验位是由信息码产生的，校验位越长，校验能力越强。,检验码的生成,检验码可按如下步骤生成：信息码的
41、权展开式乘以Xn-k。给出生成多项式 g(x)。如X.25协议中，数据链路层传送信息时需要附加16位检验位，其生成多项式为：g(x)=X16+X12+X5+1。生成多项式中最高次幂数是检验位的位数，最低次幂必须为0。4位检验位的生成多项式为：g(x)=X4+X3+X2+1。第步得到的多项式除以生成多项式，余数就是检验位的权展开式。注意：两多项式相除时，因为除法运算是模2运算，每一位相减是按位减，不发生借位。,解：把信息码110写成基数为X的权展开式X2+X(110=22+21+0)给定的生成多项式为g(x)=X4+X3+X2+1。信息码的权展开式乘以Xn-k(X2+X)X7-3=X6+X5 第
42、步所得的多项式除以生成多项式，得到检验位的多项式得到检验码的多项式为X3+1，因此可求得检验码为23+1=(1001)2。最后得到7位CRC检验码为 1101001。,【例2.28】有一个(7,3)码(整个编码7位，其中信息位3位)，其生成多项式为X4+X3+X2+1，令信息码为110，请求出其CRC检验码。,CRC码的检验方法,CRC码传送到接收方后，接收方就用CRC码除以生成多项式来检验。如果余数为0，说明传送正确；如果余数不为0，则传送出错。例如上面例子，110的CRC码为1101001，用1101001除以生成多项式11101，余数为0，传送正确。以上算法可以通过软件来实现，也可以通过硬件来实现。在使用硬件实现时，信息位的权展开式乘以Xn-k是通过移位寄存器的移位来实现的，而除以生成多项式是靠除法电路实现的。目前，CRC码大都采用硬件实现。,循环冗余校验码的特性,任何一个CRC码循环右移一位，产生新的码仍然是CRC码。正因为CRC码有这样的特性，且检验位又放在信息位的右边，形成信息码的多余部分，故称循环冗余检验码。任何两个CRC码进行按位异或，所得结果仍然是CRC码。,下表是信息码001111在生成多项式为X4+X3+X2+1的情况下的CRC码表，上述两个特点从下表中可以看出。,第 2 章 结 束The End,谢谢！,
