信息编码 与 信息表达

《信息编码 与 信息表达》由会员分享，可在线阅读，更多相关《信息编码 与 信息表达（85页珍藏版）》请在金锄头文库上搜索。

1、 第三章 信息编码与数据表示数值数据的表示3.1浮点机器数的表示方法数据格式3.2定点机器数的表示方法3.33.4非数值数据的表示3.5校验码3.6现代计算机系统的数据表示3.7本章小结 Date23.1 数值数据的表示进位计数制一不同数制之间的相互转换二十进制数的编码三Date3一、进位计数制v 数制的两大要素： 基数R：指在这种进位制中允许使用的 基本数码个数。基数为R的数制称为R进制 数。 R进制数的主要特点就是逢R进1 。权Wi：权也称位权，指某一位i上的数 码的权重值，即权与数码所处的位置i有关 。 Wi Ri。v 假设任意数值N用R进制数来表示，形式为： N=（Dm1Dm-2D0

2、D-1D-2 D-k ）R 其中，Di为该进制的基本符号，Di0 ，R-1，i = -k， -k+1， ，m-1，m ；小数点在D0和D-1之间。Date4一、进位计数制v 则数值N的实际值为： 例如：R10，即十进制数。它的每一位上 的数码Di只能取0，1，2，9；各个数码 的权为10i，i指示数码所处的位置，个位i0 ，十位i1，百位i2，依此类推。 思考：二进制、八进制、十六进制？Date5一、进位计数制v 例1：（2345.459）102103 3102 4101 5100 410-1 510-2 910-3v 例2：（11011.011）2124 123 022 121 12-0 0

3、2-1 12-2 12-3=（ 27.375）10v 例3：（123.67）8182 281 380 68-1 78-2=（83.859375）10Date6二、不同数制之间的相互转换常用的几种数制的对应关系1二、八、十六进制转换为十进制2十进制转换为二、八、十六进制3Date7（1）常用的几种数制的对应关系十进制 二进制八进制十六 进制十进制 二进制八进制十六 进制000000081000108100011191001119200102210101012A300113311101113B401004412110014C501015513110115D601106614111016E70111

4、7715111117F16100002010Date8（2）二、八、十六进制转换为十进制v 转换方法：加权求和。(按式41) 例：（5AC.E6）16= 5162 10161 12160 14161 6162 （ 1452.8984375）10 v 十进制（Decimal）、二进制（Binary）、八进 制（Octal）、十六进制（Hexdecimal）数分别 用D、B、Q、H来标志。 v 例如：（1011）2（1011）B1011B1011b （123.45）2（ 123.45 ）D 123.45D 123.45 （2B.D）16=（2B.D）H=（43.8125）10=(53.64)QDa

5、te9（3）十进制转换为二、八、十六进制v转换方法：可以分为以下两种方法 直接转换：十进制二、八、十六进制 间接转换：十进制二进制 八、十六进 制 v（a）十进制转化为R进制 v（b）二进制转化为八、十六进制Date10（a）十进制转化为R进制v转换方法 整数部分：除以R取余，先得低位，直到 商为0。 小数部分：乘R取整，先得高位，直到积 为0或者达到精度要求为止。 v例：（123.75）10=（ ？ ）2 （123.75）10=（ ？ ）81111011.11 173.6Date11小数部分的精度要求v 当小数部分不能整除为二进制时，则乘以2取 整的过程中，积不会为0；或者当小数部分转 化为

6、二进制位数很长，这时由精度来决定二进 制位数。v 例如：（0.35）10（ ？ ）2无法整除 （0.6875）10（ ？ ）2位数太长v 若要求精度大于10，则表示“”左右两边 的十进制值的差的绝对值2时，校验码才 具有检错能力，当码距d 3时，校验码才具有 纠错能力。 码距：一种码制的码距是指该码制中所有代 码之间的最小距离。 两个代码之间的距离：在一种编码中，在任 何两个代码之间逐位比较，对应位值不同的个数 。 校验码的检错纠错能力与码距的关系如下： 若码距d为奇数，如果只用来检查错 误，则可以发现d1位错误；如果用来纠正 错误，则能够纠正 位错误。 若码距d为偶数，则可以发现 位错 误，

7、并能够纠正（ ）位错误。Date663.6 校验码v 7、常见校验码： 奇偶校验码：码距d=2，检错码，能检验 奇数位错误；通常用于磁带或者串行通信中 。 海明校验码：码距d=3，纠错码，能纠正 1位或多位错误；通常用于磁盘冗余阵列中。 CRC校验码：码距d=3，纠错码，能纠正1 位错误；通常用于磁盘或数据块的校验。Date67v 在有效信息位的前面或者后面添加一位奇（偶）校验 位就组成了奇（偶）校验码。 奇（偶）校验码的编码和译码在硬件上 通常采用异或非门（异或门）实现。 1、编码 奇校验位的取值应该使整个奇校验码中 “1”的个数为奇数，偶校验位的取值应该使整 个偶校验码中“1”的个数为偶数

8、。 假设在发送端，要发送七位ASCII码（ B6 B5 B4 B3 B2 B1 B0），在ASCII码前面添加 一位奇校验位P奇或偶校验位P偶变为一个字节的 奇偶校验码，则它们的生成表达式为二、奇偶校验码Date682、译码 在接收端，必须检验接收到的校验码信 息的奇偶性，对于奇校验码，校验码中“1”的 个数应该为奇数，否则出错；对于偶校验码， 校验码中“1”的个数应该为偶数，否则出错。 设E奇为奇校验码出错信号，E偶为偶校验码出错 信号，为1出错，为0正确，则它们的表达式为奇偶校验的编码电路奇偶校验的编码电路 例如：例如：字符“A”的ASCII码为 41H，奇校验码为C1H， 偶校验码为41

9、H。二、奇偶校验码Date69二、奇偶校验码Date70三、海明码v1、编码 v 海明码的编码步骤如下： v （1）计算校验位的位数 假设信息位为k位，增加r位校验位，构成 n=k+r位海明码字。若要求海明码能纠正一位 错误，用r位校验位产生的r位指误字来区分 无错状态及码字中n个不同位置的一位错误状 态，则要求r满足： 2 r k + r + 1 计算出k位有效信息时，必须添加的能纠 错一位的海明校验码的校验位的位数rDate71v （2）确定有效信息和校验位的位置 假设k位有效信息从高到低为 ，添加 的r位校验位为 ，则它们构成n=k+r位的 海明码排列设为 ，H的下标被称为海明 位号，则

10、第i位的校验位Pi必须位于位号为2i-1的位 置，即 ，其中，i=1，2，r；有效 信息则在其余的海明码位置上顺序排列。三、海明码Date72三、海明码v （3）分组 由于海明码是分组进行奇偶校验的，每一 组通过一个监督表达式来监督有效信息的变 化，因此，分组必须使得监督表达式得出的 指误字能够反映出错位的位号。分组的原则 是：校验位只参加一组奇偶校验，有效信息 则参加至少两组的奇偶校验，若 Di = Hj ， 则Di参加那些位号之和等于j的校验位的分组 校验。Date73三、海明码v （4）进行奇偶校验，合成海明码 首先，按照分组和奇偶校验的规律将每个 校验位的生成表达式写出，然后，再带入有

11、 效信息的值，依次得出校验位的取值，最后 将校验位按各自的位置插入，与有效信息一 起合成海明码。Date74三、海明码v2、译码 在接收端收到每个海明码后，也必须按上 述分组检验每组的奇偶性有无发生变化，方 法是按照监督关系式算出指误字Sr Sr-1 S2 S1 ，若为全零，则说明各组奇偶性全 部无变化，信息正确，将相应的有效信息位 析取出来使用；否则，指误字的十进制值， 就是出错位的海明位号。Date75四、循环冗余码CRCv循环冗余码CRC（Cyclic Redundancy Code），又称为多项式码。 v1、编码 vk位要发送的有效信息位可对应于一个k-1 次多项式M（x），r位冗余校

12、验位对应于 一个r-1次多项式R（x）。由k位信息位后 面加上r位冗余位组成的n=k+r位CRC码字 则对应于一个n-1次多项式C（x），即：C（x）= xr M（x）+ R（x）该CRC码称为（n，k）循环码。 Date76四、循环冗余码CRCv 由信息位产生冗余位的编码过程，就是已知M（x） 求R（x）的过程。在CRC码中可以通过找到一个特 定的多项式G（x）来实现。用G（x）去除xr M（x ）得到的余式就是R（x），假设商的多项式为Q（x ），编码过程 即 xr M（x）G（x） Q（x）+ R（x ） v 生成多项式G（x）应满足以下条件： (1)必须是r次多项式，最高项xr 和x0

13、的系数 为1，即它对应的二进制编码是r+1位的。 (2)CRC校验码的任何一位发生错误，余数不 为零；且不同位发生错误，余数不同。 (3)对余数继续模2除，应使余数循环。Date77四、循环冗余码CRCv 目前已经有多种生成多项式被列入国际标准中 ，如：CRC-4、CRC-12、CRC-16、CCITT-16、 CRC-32等。 v 目前常用的CRC-16多项式为x16+x12+x5+1（记为 1021），CCITT-16多项式为x16+x15+x2+1（记为 8005）。图3.9 CRC（n,k）校验码串行生 成电路原理图 图中Gi代表生成多项式G（x）各 项的系数 Date78四、循环冗余

14、码CRCv2、译码 v接收端的校验过程就是用G（x）来除接 收到的码字多项式的过程。 若余式为零则认为传输无差错； 若余式不为零则传输有差错。出错的位 置与余数值是一一对应的关系，通过查找出 错模式表，即可以确定是那一位出错。 Date793.7 现代计算机系统的数据表示v几种类型的数据在Pentium系列CPU中的 表示形式 ： v1、字符串 由字符的ASCII码或者文字的Unicode编码 组成，按顺序存放在内存或寄存器中。每个 ASCII码字符占1个字节，每个Unicode编码占 用2个字节 Date803.7 现代计算机系统的数据表示vBCD 在基于Pentium系列CPU的IA构架中

15、，BCD 数据分为压缩的（packed）BCD码和非压缩 （unpacked）的BCD码两种，前者以每字节2 位BCD数字的形式存储，后者以每字节1位 BCD数字的方法存储 Date813.7 现代计算机系统的数据表示v3、指针 指针实际上是内存单元的地址，因此是 无符号数据。IA构架中定义了两种类型的指 针， （1）一种是32位的近指针，用于 定义段内偏移量和段内访问； （2）一种是48位的全指针，又称 远指针，用于段间访问。 v4、浮点数 Pentium系列CPU支持IEEE 754标准的3种 浮点数格式：单精度、双精度和扩展精度浮 点数。Date82本章小结v 数制有两个要素：基数R与位权W。计算机中的信息 均由二进制来表示，即R=2，W=2i。用于表示十进制 数值的二进制编码被称为BCD码，4位二进制编码表 示一个十进制数字。 v 机器数是数值数据在机器中的表示形式，根据小数 点的位置是否浮动，可以分为定点数和浮点数。 定点机器数根据小数点的隐含位置又分为定 点小数和定点整数两种。 浮点机器数由阶码E和尾数M两部分构成，阶 码是定点整数，尾数是定点小数；阶码E（即指 数）的底，一般隐含为2。浮点机器数的小数点 的位置随阶码数值而变化。IEEE754标准的浮点 数有单精度、双精度