信息编码与信息表达

1、2第三章第三章 信息编码与数据表示信息编码与数据表示 数值数据的表示数值数据的表示3.13.1 浮点机器数的表示方法浮点机器数的表示方法 数据格式数据格式3.23.2 定点机器数的表示方法定点机器数的表示方法3.33.33.43.4 非数值数据的表示非数值数据的表示3.53.5 校验码校验码3.63.6 现代计算机系统的数据表示现代计算机系统的数据表示3.73.7 本章小结本章小结33.1 3.1 数值数据的表示数值数据的表示 进位计数制进位计数制一一 不同数制之间的相互转换不同数制之间的相互转换二二 十进制数的编码十进制数的编码三三4一、进位计数制一、进位计数制v 数制的两大要素： 基数R：

2、指在这种进位制中允许使用的基本数码个数。基数为R的数制称为R进制数。 R进制数的主要特点就是逢R进1 。 权Wi：权也称位权，指某一位i上的数码的权重值，即权与数码所处的位置i有关。 Wi Ri。v 假设任意数值N用R进制数来表示，形式为： N=（Dm1Dm-2D0 D-1D-2 D-k ）R 其中，Di为该进制的基本符号，Di0，R-1，i = -k， -k+1， ，m-1，m；小数点在D0和D-1之间。5一、进位计数制一、进位计数制v 则数值N的实际值为： 1)(mkiiiRDNv 例如：例如：R R1010，即十进制数。它的每一位上的数码，即十进制数。它的每一位上的数码D Di i只能取

3、只能取0 0，1 1，2 2，9 9；各个数码的；各个数码的权为权为1010i i，i i指指示数码所处的位置，个位示数码所处的位置，个位i i0 0，十位，十位i i1 1，百位，百位i i2 2，依此类推。，依此类推。v 思考：二进制、八进制、十六进制？思考：二进制、八进制、十六进制？6一、进位计数制一、进位计数制v 例1：（2345.459）102103 3102 41015100 410-1 510-2 910-3v 例2：（11011.011）2124 123 022121 12-0 02-1 12-2 12-3=（27.375）10v 例3：（123.67）8182 281 380

4、68-1 78-2=（83.859375）107二、不同数制之间的相互转换二、不同数制之间的相互转换 常用的几种数制的对应关系常用的几种数制的对应关系1 1 二、八、十六进制转换为十进制二、八、十六进制转换为十进制2 2 十进制转换为二、八、十六进制十进制转换为二、八、十六进制3 38（1 1）常用的几种数制的对应关系）常用的几种数制的对应关系十进制十进制 二进制二进制八进制八进制十六十六进制进制十进制十进制 二进制二进制八进制八进制十六十六进制进制0 0000000000 00 08 81000100010108 81 1000100011 11 19 91001100111119 92 2

5、001000102 22 21010101010101212A A3 3001100113 33 31111101110111313B B4 4010001004 44 41212110011001414C C5 5010101015 55 51313110111011515D D6 6011001106 66 61414111011101616E E7 7011101117 77 71515111111111717F F16161000010000202010109（2 2）二、八、十六进制转换为十进制）二、八、十六进制转换为十进制v 转换方法：转换方法：加权求和。加权求和。( (按式按式4

6、 41)1) 例：（例：（5AC.E65AC.E6）1616= 5= 516162 2 101016161 1 121216160 0 141416161 1 6 616162 2 （1452.89843751452.8984375）1010v 十进制（十进制（DecimalDecimal）、二进制（）、二进制（BinaryBinary）、八进）、八进制（制（OctalOctal）、十六进制（）、十六进制（HexdecimalHexdecimal）数分别）数分别用用D D、B B、Q Q、H H来标志。来标志。v 例如：（例如：（10111011）2 2（10111011）B B1011B10

7、11b1011B1011b （123.45123.45）2 2（ 123.45 123.45 ）D D 123.45D 123.45D 123.45123.45 （2B.D2B.D）1616= =（2B.D2B.D）H H= =（43.812543.8125）1010=(53.64)=(53.64)Q Q10（3 3）十进制转换为二、八、十六进制）十进制转换为二、八、十六进制v转换方法转换方法：可以分为以下两种方法：可以分为以下两种方法 直接转换：十进制直接转换：十进制二、八、十六进制二、八、十六进制 间接转换：十进制间接转换：十进制二进制二进制 八、十六进制八、十六进制v（a a）十进制转化

8、为）十进制转化为R R进制进制v（b b）二进制转化为八、十六进制）二进制转化为八、十六进制11（a a）十进制转化为）十进制转化为R R进制进制v转换方法转换方法 整数部分：整数部分：除以除以R R取余，先得低位取余，先得低位，直到商为，直到商为0 0。 小数部分：小数部分：乘乘R R取整，先得高位取整，先得高位，直到积为，直到积为0 0或或者达到精度要求为止。者达到精度要求为止。v例：（例：（123.75123.75）1010= =（ ？ ）2 2 （123.75123.75）1010= =（ ？ ）8 81111011.11173.612小数部分的精度要求小数部分的精度要求v 当小数部分

9、当小数部分不能整除为二进制不能整除为二进制时，则乘以时，则乘以2 2取整取整的过程中，积不会为的过程中，积不会为0 0；或者；或者当小数部分转化为当小数部分转化为二进制位数很长二进制位数很长，这时由精度来决定二进制位，这时由精度来决定二进制位数。数。v 例如：（例如：（0.350.35）1010（ ？ ）2 2无法整除无法整除 （0.68750.6875）1010（ ？ ）2 2位数太长位数太长v 若要求精度大于若要求精度大于1010，则表示，则表示“”左右两边左右两边的十进制值的差的绝对值的十进制值的差的绝对值1010。 则我们只需取则我们只需取4 4位二进制小数即可满足要求，位二进制小数即

10、可满足要求，因为因为10102d2 2时，校验码才具有时，校验码才具有检错能力检错能力，当码距，当码距dd 3 3时，校验码才具有时，校验码才具有纠错纠错能力能力。 码距：码距：一种码制的码距是指该码制中所有代码之一种码制的码距是指该码制中所有代码之间的最小间的最小距离距离。 两个代码之间的距离两个代码之间的距离：在一种编码中，在任何两：在一种编码中，在任何两个代码之间逐位比较，对应位值不同的个数。个代码之间逐位比较，对应位值不同的个数。 校验码的检错纠错能力与码距的关系如下：校验码的检错纠错能力与码距的关系如下： 若码距若码距d d为奇数，如果只用来检查错误，则可为奇数，如果只用来检查错误，

11、则可以发现以发现d d1 1位错误；如果用来纠正错误，则能位错误；如果用来纠正错误，则能够纠正够纠正 位错误。位错误。 若码距若码距d d为偶数，则可以发现为偶数，则可以发现 位错误，并能位错误，并能够纠正（够纠正（ ）位错误。）位错误。21d21d2d673.6 3.6 校验码校验码v 7 7、常见校验码：、常见校验码： 奇偶校验码：奇偶校验码：码距码距d=2d=2，检错码，检错码，能检验奇数能检验奇数位错误位错误；通常用于磁带或者串行通信中。；通常用于磁带或者串行通信中。 海明校验码：海明校验码：码距码距d=3d=3，纠错码，纠错码，能纠正能纠正1 1位位或多位错误或多位错误；通常用于磁盘

12、冗余阵列中。；通常用于磁盘冗余阵列中。 CRCCRC校验码：校验码：码距码距d=3d=3，纠错码，纠错码，能纠正能纠正1 1位错位错误误；通常用于磁盘或数据块的校验。；通常用于磁盘或数据块的校验。68v在有效信息位的前面或者后面添加一位奇（偶）校验在有效信息位的前面或者后面添加一位奇（偶）校验位就组成了奇（偶）校验码。位就组成了奇（偶）校验码。奇（偶）校验码的编码和译码在硬件上通常采用异奇（偶）校验码的编码和译码在硬件上通常采用异或非门（异或门）实现。或非门（异或门）实现。 1 1、编码、编码奇校验位的取值应该使整个奇校验码中奇校验位的取值应该使整个奇校验码中“1”1”的的个数为奇数，偶校验位

13、的取值应该使整个偶校个数为奇数，偶校验位的取值应该使整个偶校验码中验码中“1”1”的个数为偶数。的个数为偶数。假设在发送端，要发送七位假设在发送端，要发送七位ASCIIASCII码（码（B6 B5 B4 B6 B5 B4 B3 B2 B1 B0B3 B2 B1 B0），在），在ASCIIASCII码前面添加一位奇校码前面添加一位奇校验位验位P P奇奇或偶校验位或偶校验位P P偶偶变为一个字节的奇偶校验变为一个字节的奇偶校验码，则它们的生成表达式为码，则它们的生成表达式为01234560123456BBBBBBBPBBBBBBBP偶奇二、奇偶校验码二、奇偶校验码69 2 2、译码、译码 在接收端

14、，必须检验接收到的校验码信息的奇偶在接收端，必须检验接收到的校验码信息的奇偶性，对于奇校验码，校验码中性，对于奇校验码，校验码中“1”1”的个数应该为的个数应该为奇数，否则出错；对于偶校验码，校验码中奇数，否则出错；对于偶校验码，校验码中“1”1”的个数应该为偶数，否则出错。设的个数应该为偶数，否则出错。设E E奇奇为奇校验码为奇校验码出错信号，出错信号，E E偶偶为偶校验码出错信号，为为偶校验码出错信号，为1 1出错，出错，为为0 0正确，则它们的表达式为正确，则它们的表达式为0B6B5B4B2B1B0B3P奇奇P偶偶字符字符“A”A”的的ASCIIASCII码为码为41H41H，奇校验码为

15、，奇校验码为C1HC1H，偶校验码为偶校验码为41H41H。偶偶奇奇PBBBBBBBEPBBBBBBBE01234560123456二、奇偶校验码二、奇偶校验码70P奇奇/ /P偶偶B6B5B4B2B1B0B3E奇奇E偶偶二、奇偶校验码二、奇偶校验码71三、海明码三、海明码v 1 1、编码、编码v海明码的编码步骤如下：海明码的编码步骤如下：v（1 1）计算校验位的位数）计算校验位的位数假设信息位为假设信息位为k k位，增加位，增加r r位校验位，构成位校验位，构成n=k+rn=k+r位海明码字。若要求海明码能纠正一位位海明码字。若要求海明码能纠正一位错误，用错误，用r r位校验位产生的位校验位

16、产生的r r位指误字来区分位指误字来区分无错状态及码字中无错状态及码字中n n个不同位置的一位错误状个不同位置的一位错误状态，则要求态，则要求r r满足：满足：2 2 r r k + r + 1 k + r + 1计算出计算出k k位有效信息时，必须添加的能纠错一位有效信息时，必须添加的能纠错一位的海明校验码的校验位的位数位的海明校验码的校验位的位数r r72v（2 2）确定有效信息和校验位的位置）确定有效信息和校验位的位置假设假设k k位有效信息从高到低为位有效信息从高到低为 ，添加的，添加的r r位校验位为位校验位为 ，则它们构成，则它们构成n=k+rn=k+r位的海明位的海明码排列设为码

17、排列设为 ，H H的下标被称为海明位号，的下标被称为海明位号，则第则第i i位的校验位位的校验位P Pi i必须位于位号为必须位于位号为2 2i-1i-1的位置，的位置，即即 ，其中，其中，i=1i=1，2 2，r r；有效信息；有效信息则在其余的海明码位置上顺序排列。则在其余的海明码位置上顺序排列。三、海明码三、海明码73三、海明码三、海明码v（3 3）分组）分组由于海明码是分组进行奇偶校验的，每一组由于海明码是分组进行奇偶校验的，每一组通过一个监督表达式来监督有效信息的变化，通过一个监督表达式来监督有效信息的变化，因此，分组必须使得监督表达式得出的指误因此，分组必须使得监督表达式得出的指误

18、字能够反映出错位的位号。分组的原则是：字能够反映出错位的位号。分组的原则是：校验位只参加一组奇偶校验，有效信息则参校验位只参加一组奇偶校验，有效信息则参加至少两组的奇偶校验，若加至少两组的奇偶校验，若 D Di i = = H Hj j ，则，则D Di i参加那些位号之和等于参加那些位号之和等于j j的校验位的分组校验。的校验位的分组校验。74三、海明码三、海明码v（4 4）进行奇偶校验，合成海明码）进行奇偶校验，合成海明码首先，按照分组和奇偶校验的规律将每个校首先，按照分组和奇偶校验的规律将每个校验位的生成表达式写出，然后，再带入有效验位的生成表达式写出，然后，再带入有效信息的值，依次得出

19、校验位的取值，最后将信息的值，依次得出校验位的取值，最后将校验位按各自的位置插入，与有效信息一起校验位按各自的位置插入，与有效信息一起合成海明码。合成海明码。75三、海明码三、海明码v 2 2、译码、译码 在接收端收到每个海明码后，也必须按上述在接收端收到每个海明码后，也必须按上述分组检验每组的奇偶性有无发生变化，方法分组检验每组的奇偶性有无发生变化，方法是按照监督关系式算出指误字是按照监督关系式算出指误字SrSr Sr-1 Sr-1 S2 S2 S1 S1 ，若为全零，则说明各组奇偶性全部无变，若为全零，则说明各组奇偶性全部无变化，信息正确，将相应的有效信息位析取出化，信息正确，将相应的有效

20、信息位析取出来使用；否则，指误字的十进制值，就是出来使用；否则，指误字的十进制值，就是出错位的海明位号。错位的海明位号。76四、循环冗余码四、循环冗余码CRCCRCv循环冗余码循环冗余码CRCCRC（Cyclic Redundancy Cyclic Redundancy CodeCode），又称为多项式码。），又称为多项式码。 v1 1、编码、编码vk k位要发送的有效信息位可对应于一个位要发送的有效信息位可对应于一个k-1k-1次多项式次多项式M M（x x），），r r位冗余校验位对应于一位冗余校验位对应于一个个r-1r-1次多项式次多项式R R（x x）。由）。由k k位信息位后面位信息

21、位后面加上加上r r位冗余位组成的位冗余位组成的n=k+rn=k+r位位CRCCRC码字则对码字则对应于一个应于一个n-1n-1次多项式次多项式C C（x x），即：），即： C C（x x）= x= xr r M M（x x）+ R+ R（x x） 该该CRCCRC码称为（码称为（n n，k k）循环码。）循环码。 77四、循环冗余码四、循环冗余码CRCCRCv 由信息位产生冗余位的编码过程，就是已知由信息位产生冗余位的编码过程，就是已知M M（x x）求求R R（x x）的过程。在）的过程。在CRCCRC码中可以通过找到一个特定码中可以通过找到一个特定的多项式的多项式G G（x x）来实现

22、。用）来实现。用G G（x x）去除）去除x xr r M M（x x）得到的余式就是得到的余式就是R R（x x），假设商的多项式为），假设商的多项式为Q Q（x x），），编码过程编码过程 即即x xr r M M（x x）G G（x x） Q Q（x x）+ R+ R（x x）v 生成多项式生成多项式G G（x x）应满足以下条件：）应满足以下条件： (1)(1)必须是必须是r r次多项式，最高项次多项式，最高项x xr r 和和x x0 0的系数为的系数为1 1，即它对应的二进制编码是即它对应的二进制编码是r+1r+1位的。位的。 (2)CRC(2)CRC校验码的任何一位发生错误，余数

23、不为零；校验码的任何一位发生错误，余数不为零；且不同位发生错误，余数不同。且不同位发生错误，余数不同。 (3)(3)对余数继续模对余数继续模2 2除，应使余数循环。除，应使余数循环。)()()()()(xGxRxQxGxMxr78四、循环冗余码四、循环冗余码CRCCRCv目前已经有多种生成多项式被列入国际标准中，目前已经有多种生成多项式被列入国际标准中，如：如：CRC-4CRC-4、CRC-12CRC-12、CRC-16CRC-16、CCITT-16CCITT-16、CRC-CRC-3232等。等。v目前常用的目前常用的CRC-16CRC-16多项式为多项式为x x1616+x+x1212+x

24、+x5 5+1+1（记为（记为10211021），），CCITT-16CCITT-16多项式为多项式为x x1616+x+x1515+x+x2 2+1+1（记为（记为80058005）。）。图图3.9 CRC3.9 CRC（n,kn,k）校验码串行生成电路原理）校验码串行生成电路原理图图图中图中GiGi代表生成多项式代表生成多项式G G（x x）各项的系数）各项的系数 79四、循环冗余码四、循环冗余码CRCCRCv 2 2、译码、译码 v 接收端的校验过程就是用接收端的校验过程就是用G G（x x）来除接来除接收到的码字多项式的过程。收到的码字多项式的过程。若余式为零则认为传输无差错；若余式为

25、零则认为传输无差错；若余式不为零则传输有差错。出错的位置与若余式不为零则传输有差错。出错的位置与余数值是一一对应的关系，通过查找出错模余数值是一一对应的关系，通过查找出错模式表，即可以确定是那一位出错。式表，即可以确定是那一位出错。 803.7 3.7 现代计算机系统的数据表示现代计算机系统的数据表示v几种类型的数据在几种类型的数据在PentiumPentium系列系列CPUCPU中的表中的表示形式示形式 ：v1 1、字符串、字符串 由字符的由字符的ASCIIASCII码或者文字的码或者文字的UnicodeUnicode编码组成，编码组成，按顺序存放在内存或寄存器中。每个按顺序存放在内存或寄存

26、器中。每个ASCIIASCII码码字符占字符占1 1个字节，每个个字节，每个UnicodeUnicode编码占用编码占用2 2个字个字节节 813.7 3.7 现代计算机系统的数据表示现代计算机系统的数据表示vBCDBCD 在基于在基于PentiumPentium系列系列CPUCPU的的IAIA构架中，构架中，BCDBCD数据数据分为压缩的（分为压缩的（packedpacked）BCDBCD码和非压缩码和非压缩（unpackedunpacked）的）的BCDBCD码两种，前者以每字节码两种，前者以每字节2 2位位BCDBCD数字的形式存储，后者以每字节数字的形式存储，后者以每字节1 1位位BC

27、DBCD数字的方法存储数字的方法存储 823.7 3.7 现代计算机系统的数据表示现代计算机系统的数据表示v3 3、指针、指针 指针实际上是内存单元的地址，因此是无符指针实际上是内存单元的地址，因此是无符号数据。号数据。IAIA构架中定义了两种类型的指针，构架中定义了两种类型的指针， （1 1）一种是）一种是3232位的近指针，用于定义段内位的近指针，用于定义段内偏移量和段内访问；偏移量和段内访问； （2 2）一种是）一种是4848位的全指针，又称远指针，位的全指针，又称远指针，用于段间访问。用于段间访问。v4 4、浮点数、浮点数 PentiumPentium系列系列CPUCPU支持支持IEEE 754IEEE 754标准的标准的3 3种浮点种浮点