[工学]第6章 信息的表示.ppt

中国铁道出版社,第六章 信息的表示,重点内容： 定点数的表示方法； 浮点数的表示方法； 文字信息的表示； 其他信息的表示。,6.1 概述,直到在16世纪的某个时期，欧洲才采用了十进制数字（基数为10）的计数体系（或称为数制）。而此前阿拉伯和印度已经使用十进制数近一千年了。 今天，我们理所当然地认为，数字243代表的是2个100加上4个10，再加上3。虽然，0表示什么都没有。但事实上，大家都知道1和10这两个数所代表的意义有着实质性的差别。,6.1.1 位置编码系统,任意数字的值都可以通过表示成某个基数（或称为底，Radix）的乘幂形式。 通常也称为权重编码系统（Weighted Numbering System），因为数的每一个位置都是基数的幂次方。 例如： (243.51)10 2102+4101+3100+510-1+110-2 (23)10 232+131+230 (212)3 (22)10 124+023+122+121+020 (10110)2,位置编码系统中所使用的有效数字的数目等于系统的基数的大小。例如，在十进制体系中有10个数字09，而在三进制体系（基数是3）中的数字为0、1、2。不同的基采用下标的形式来表示，例如(33)10。 在计算机科学中，两个最重要的数制是二进制（基数为2）和十六进制（基数为16）。另外一个比较重要的数制是八进制（基数为8）。,6.1.1 位置编码系统,在选择计算机数值的表示方式时，应当全面考虑以下几个因素： 要表示数的类型 可能遇到的数值范围 数值精确度 数据存储和处理所需要的硬件代价,6.1.2 数值在计算机中的表示,由于数据是存储在存储器中，而存储器只能存储二进制位串，因此，数据的计算机表示需要解决下面的问题：正负号的表示和小数点的表示。 计算机中常用的数据表示格式有两种： 定点格式 浮点格式,6.1.2 数值在计算机中的表示,数值在计算机中的表示具有如下特点： 二进制表示 数据的编码化 正负号的数字化 小数点位置的约定 数据有模,6.1.2 数值在计算机中的表示,6.2 定点数的表示,所谓定点数，即约定机器中所有数据的小数点位置是固定不变的。由于约定在固定的位置，小数点就不再使用记号“”来表示。 从原理上讲，小数点位置固定在哪一位都可以，但是通常将数据表示成纯小数或纯整数。,6.2 定点数的表示,常用概念： 真值：书写表示的数值，如3、5等，这些数据由人识别。 机器数或机器码：数值在计算机中的编码表示，为二进制数串形式，供机器使用。 数值编码的内容就是在计算机中如何把真值映射为机器码。,约定将字的最高位（最左位）作为符号位对待，若最左位是0，则数是正的；若最左位是1，则为负数。 又称为符号幅值表示法。以一个n位数为例，最左位为符号位，其余n-1位为整数的幅值（绝对值）。 例如： 1800010010 1810010010,6.2.1 原码表示法,一般情况下，对于定点整数，原码表示的定义是：,6.2.1 原码表示法,一般情况下，对于定点小数，原码表示的定义是：,6.2.1 原码表示法,以位定点整数原码为例，说明了原码和真值在数轴上的映射关系：,6.2.1 原码表示法,原码的性质 原码的最高位表示符号，0为正，1为负。 0在原码表示中不唯一，有0、0之分。 n位原码总共有2n种编码，共可表示2n1个数，因为0用了两个编码。 负数的原码大于正数的原码。 原码的实质是表示数值的绝对值，因此由真值转换为原码的方法是：将写成0，写成1，数值位不变。,6.2.1 原码表示法,原码的优点 表示很直观 便于实现乘、除法运算 原码的缺点 加减运算时既要考虑数的符号，又要考虑幅值，才能进行所要求的运算，处理较为复杂。 0有两种表示，这样很不方便，因为它比单一表示法增加了测试零（计算机经常完成的一种操作）的困难。,6.2.1 原码表示法,有模运算是指在一定数值范围内进行的运算。 例如，最常见的有模运算环境是钟表，因为钟表表盘上最大刻度是12，任何运算结果都不会超过12，超过12之后又成了1。 我们常用的实数运算则属于无模运算。由于在计算机中采用有限的二进制位来表示数据，因此计算机中的所有运算都是有模运算。,6.2.2 补码表示法,有模运算中，用模减一个数的结果称为该数的补数。 对于有模运算来讲，减一个数等于加上该数对模的补数，补码就是按补数概念对数据进行编码的。 在补码表示法中，正数用本身来代表，而负数用其补数来代表。,6.2.2 补码表示法,对于定点整数，补码表示的定义是：,6.2.2 补码表示法,对于定点小数，补码表示的定义是：,6.2.2 补码表示法,以位定点整数补码为例，说明了补码和真值在数轴上的映射关系：,6.2.2 补码表示法,求负数补码的方法： 符号位置1，其余各位0变1，1变0，然后在最末位上加1； 从低位向高位找到第一个1，这个1和右边各位的0保持不变，左边的各高位按位取反。,6.2.2 补码表示法,补码的特性： 最高位表示符号，0为正，1为负。 0的表示唯一，即编码为全0的情况。 补码表示法比原码表示法多表示一个数据，即最小的负数。图6-2中的-4（100）就是一个实例。 负数补码值大于正数补码值。 补码算术右移时，要将符号位复制。 补码算术左移时，末位补0即可。 定点整数补码位数扩展时，要将符号位向左复制；定点小数补码进行位数扩展时，只需要在原机器码后补0即可。,6.2.2 补码表示法,6.2.2 补码表示法,【例6-2】将十进制数x（127、1、0、1、127）表示成二进制数及原码、补码值（使用8位二进制数）。 解：,6.3 浮点数的表示,使用定点表示法能表示以0为中心的一定范围的正、负的整数。通过重新假定小数点的位置，这种格式也能用来表示带有分数的数。但这种方法受到很大制约，它不能表示很大的整数，也不能表示很小的分数，即表示数的范围有限，这就引出了浮点数的表示方法。,6.3.1 原理,对于十进制数，人们使用科学计数法表示，通过动态地移动十进制小数点到一个约定位置，并使用10的指数来保持对此小数点的跟踪，从而允许只使用少数几个数字来表示很大范围的数。 例如： 976 000 000 000 000 9.761014 0.000 000 000 000 0976 9.7610-14。,6.3.1 原理,能以如下形式表示一个数： SB E 这样的数存储在一个二进制字的3个字段中： 符号：正或负。 有效数S（Significant）。 指数E（Exponent）。 基值B是隐含的并且不需存储，因为对所有数它都是相同的。,一个典型的32位浮点格式 最左位保存数的符号（0正，1负）。 指数值存于位1位8。所用的表示法称为偏移表示法。一个称为偏移的固定值，从字段中减去，才得到真正的指数。 字的最后一部分是有效数，称为尾数。 此例的基值被认为是2。,6.3.1 原理,浮点数的规格化（Normalized）表示 若不对浮点数的表示做出明确规定，同一个浮点数的表示就不是唯一的。 为了提高数据的表示精度，当尾数的值不为0时，其绝对值应0.5，即后数域的最高有效位应为l，否则要以修改阶码同时左右移小数点的办法，使其变成这一要求的表示形式。 对于补码而言，即尾数最高两位必须相异。 0.1xx.x 和 1.0xx.x 规格化 0.0xx.x 和 1.1xx.x 非规格化,6.3.1 原理,【例6-3】假设由S、E、M三个域组成的一个32位二进制字所表示的非规格化浮点数x，其真值表示为： x(1)S(1.M)2E-128 问：它所表示的规格化的最大正数、最小正数、最大负数、最小负数是什么？ 解： 最大正数：x 1(12-23)2127,6.3.1 原理,最小正数：x 1.02-128 最小负数：x 1(12-23)2127 最大负数：x 1.02-128,6.3.1 原理,6.3.2 二进制浮点表示的IEEE标准,IEEE标准定义的32位单精度浮点数格式 IEEE标准定义的64位双精度浮点数格式,6.3.2 二进制浮点表示的IEEE标准,以32位单精度浮点数为例，其偏移值为127，尾数有一位隐藏位，一个规格化的32位浮点数x的值可表示为：,6.3.2 二进制浮点表示的IEEE标准,IEEE标准中数的分类 对于指数值范围在1254（单精度）和12046（双精度），表示了一个规格化的非零浮点数。指数是偏移的，故真正指数范围是126127（单精度）和10221023（双精度）。一个规格化的数要求二进制小数点左边有一个1，这位是隐藏的，给出24位或53位有效位的有效数（标准中称为分数）。 0指数与0分数一起表示正零或负零，取决于它的符号位。正如我们曾提到的，有严格的0值表示式是有益的。,6.3.2 二进制浮点表示的IEEE标准,IEEE标准中数的分类（续） 全1指数与0分数一起表示正无穷大或负无穷大，取决于它的符号位。能有无穷大表示形式也是有用的。把上溢看成一个错误条件而停止程序执行，还是把它看成是一个值带入程序并继续处理，这样的裁决权留给用户。 0指数与非0分数一起表示一个反规格化（Denormalized）数。这种情况下，二进制小数点左边的隐藏位是0并且真指数是126或1022。数的正负取决于它的符号位。 全1指数与非0分数一起给出NaN值，它意味着不是一个数（Not a Number）。非数（NaN）用来通知各种例外情况。,6.3.2 二进制浮点表示的IEEE标准,6.4 文字信息的表示,现代计算机不仅处理数值领域的问题，而且处理大量非数值领域的问题，非数值信息没有数值大小的概念。这样一来，必然要引入文字、字母以及某些专用符号，以便表示文字语言、逻辑语言等信息。 例如人机交换信息时使用英文字母、标点符号、十进制数以及诸如$、%、+等符号。然而数字计算机只能处理二进制数据，因此，上述信息应用到计算机中时，都必须编写成二进制格式的代码，也就是字符信息用数据表示，称为符号数据。,6.4.1 字符与字符串的表示,目前国际上普遍采用的一种字符系统是7单位的ASCII码（美国国家信息交换标准字符码），它包括10个十进制数码，26个英文字母和一定数量的专用符号，如$、%、+、等，总共128个元素，因此二进制编码需要7位，加上一个偶校验位，共8位，刚好为一个字节。,6.4.1 字符与字符串的表示,字符串是指连续的一串字符，通常方式下，它们占用主存中连续的多个字节，每个字节存一个字符。 当主存字由2个或4个字节组成时，在同一个主存字中，既可按从低位字节向高位字节的顺序存放字符串内容，也可按从高位字节向低位字节的次序存放字符串内容。这两种存放方式都是常用方式，不同的计算机可以选用其中任何一种。,6.4.1 字符与字符串的表示,6.4.2 汉字的表示,1汉字的输入编码 为了能直接使用西文标准键盘把汉字输入到计算机，就必须为汉字设计相应的输入编码方法。 当前采用的方法主要有以下3类： 数字编码：国标区位码，例如“中”字位于第54区48位，区位码为5448。优点是无重码，且输入码与内部编码的转换比较方便，缺点是代码难以记忆。 拼音码：拼音码是以汉语拼音为基础的输入方法。凡掌握汉语拼音的人，不需训练和记忆，即可使用。汉字同音字太多，输入重码率很高，影响了输入速度。 字形编码：五笔字型编码。 为了加快输入速度，发展了词组输入、联想输入等多种快速输入方法。 利用语音或图像识别技术“自动”将拼音或文本输入到计算机内，并将其自动转换为机内代码表示。,6.4.2 汉字的表示,2汉字内码 汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码，一般采用两个字节表示。英文字符的机内代码是7位的ASCII码，当用一个字节表示时，最高位为0。为了与英文字符能相互区别，汉字机内代码中两个字节的最高位均规定为1。例如汉字操作系统CCDOS中使用的汉字内码是一种最高位为1的两字节内码。 有些系统中字节的最高位用于奇偶校验位，这种情况下用3个字节表示汉字内码。,3汉字字模码 字模码是用点阵表示的汉字字形代码，它是汉字的输出形式。 根据汉字输出的要求不同，点阵的多少也不同。简易型汉字为1616点阵，提高型汉字为2424点阵、3232点阵，甚至更高。因此字模点阵的信息量是很大的，所占存储空间也很大。以1616点阵为例，每个汉字要占用32B，国标两级汉字要占用256KB因此字模点阵只能用来构成汉字库，而不能用于机内存储。字库中存储了每个汉字的点阵代码。当显示输出或打印输出时才检索字库，输出字模点阵，得到字形。,6.4.2 汉字的表示,6.5 其他信息的表示,计算机处理的信息还包括语音、图像和图形等信息，这些信息在计算机中也必须用二进制的形式表示和处理，它们的表示在本质上同样是对信息进行二进制的编码表示问题。,6.5.1 语音的计算机表示, 对声音进行采样。 一般由麦克风、录音机等录音设备把语音信号变成频率、幅度连续变化的电流信号。它仍是一种模拟信号，不能被计算机接受，需要通过采样器每隔固定时间间隔对声音的模拟信号截取一个幅值，这个过程称为采样。采样结果得到与声音信号幅值相对应的一组离散数据值，它们包含了声音的频率、幅值等特征。 量化。 用专门的模/数转换电路将每一个离散值换成一个n位二进制表示的数字量，这是计算机能接受的数据形式，进一步编码后，就可以以声音文件送入计算机，存储在硬盘上。当计算机播放语音信息时，把声音文件中的数字信号还原成模拟信号，通过音响设备输出。,6.5.2 位图图像的计算机表示,抽样。 将图像在二维空间上的画面分布到矩形点阵的网状结构中，阵列中的每一个点称为像素点，分别对应图像在阵列位置上的一个点，对每个点进行抽样，得到每个点的灰度值（亦称量度值）。显然，阵列中有图像信息的点与无图像信息处的点灰度值不同，即或是有图像信息的各点，因为色彩、明亮层次不同其灰度值也不同。如果每个像素点的灰度值只取0、1两个值，图像点阵只有黑白两种情况，称二值图像，如果允许像素点的灰度值越多，图像能表现的层次、色彩就越丰富，图像在计算机上的再现性能就越好。 量化。 把灰度值转换成n位二进制表示的数值称为量化。,6.5.3 图形的计算机表示,对于矩形、三角形、直线、螺旋线等形状，计算机常使用另一种处理方法：图像采集设备输入图像后对图像依据某种标准进行分析、分解，提取出具有定意义的独立的信息单位图元，例如一段直线、一条曲线、一个矩形、一个圆、一个电路符号等，并设计一系列指令，用指令描述一个个的图元及各图元之间的联系，于是一幅原始图像以一组有序的指令形式存入计算机。 当计算机要显示一幅存储的图像时，只需读取指令、逐条解释、执行指令，就将指令描述的图元重新组合成图像输出。因为图像不是直接用画面的每一个像素点来描述，而是用图元序列描述，图像的这种表示方式称为图形，或称矢量图形。,6.6 校验码,差错控制 信号在物理信道上的传输过程中，由于线路本身电气特性产生的随机噪声（又称热噪声），会引起信号幅度、频率和相位的衰减或畸变，电信号在线路上反射造成的回音效应，相邻线路间的串扰以及各种外界因素（如闪电、开关跳闸、强电磁场变化等）会造成信号失真，从而出现数据传输错误。 计算机系统必须能发现（检测）这种差错，并且能采取措施纠正它，这种用于对差错进行检测与校正的技术叫差错控制。,6.6 校验码,差错控制编码 数据信息在向信道上发送之前，先按照某种关系附加上一定的冗余位，构成传输码然后在信道上发送。接收端收到传输码元后，检查信息位和冗余位之间的关系，就可以发现传输过程中是否有差错发生。 检错码（Error-Detecting Code） 纠错码（Error-Correcting Code）,6.6.1 奇偶校验码,是通过增加冗余位来使码字中1的个数保持为奇数或偶数的编码方法，是一种检错码。 垂直奇偶校验 水平奇偶校验 水平垂直奇偶校验,6.6.2 循环冗余码,循环冗余码（Cyclic Redundancy Code，CRC），CRC也称多项式码。因为任何一个由二进制数位串组成的代码，都可以唯一的与一个只含有0和1两个系数的多项式建立一一对应关系。 例如 代码1010111对应的多项式为X 6+X 4+X 2+X+1 多项式X 5+X 3+X 2+X+1对应的代码为101111,CRC码在发送端编码和接收端校验时，都可以利用事先约定的生成多项式G(X)来得到。k位要发送的信息位可对应于一个(k-1)次多项式K(X)，r位冗余位对应于一个(r-1)次多项式R(X)。由k位信息位后再加上r位冗余位组成的nk+r位码字则对应于一个(n-1)次多项式T(X)X rK(X)+R(X)。 例如： 信息位 1010001对应为：K(X)X 6+X 4+1 冗余位 1101对应为：R(X )X 3+X 2+1 码字10100011101对应为： T(X )X 4K(X )+ R(X )X 10+X 8+ X 4+ X 3+X 2+1,6.6.2 循环冗余码,由信息位产生冗余位的编码过程，就是已知K(X)求R(X)的过程，在CRC码中，可以通过找到一个特定的r次多项式G(X)(最高项Xr的系数为1)来实现。用G(X)去除XrK(X)得到的余式就是R(X)。 这里需要特别强调的是，这些多项式中的“”都是模2加（即异或运算）。此外这里的除法过程中用到的减法也是模2减法，它和模2加一样也是异或运算，即不考虑借位的减法。,6.6.2 循环冗余码,由于R(X)是G(X)除X rK(X )的余式，那么必然有： X r K(X )G(X )Q(X )+R(X ) 其中Q(X)为商式。 根据模2运算规则R(X )+R(X )0的特点，将上式改为： X r K(X )+R(X )/G(X )Q(X )， 即T(X)/G(X)Q(X)。 由此可见，信道上发送的码字多项式T(X ) X r K(X )+R(X )，若传输过程无差错，则接收方收到的码字多项式应能被G(X)整除。,6.6.2 循环冗余码,如果传输中有差错，比如要的传输码字是10100011101，由于噪声干扰，在接收端变成了10100011011，这相当于在码字上面串加了差错模式00000000110。差错模式中1的位置对应于变化了的信息位的位置。差错模式对应的多项式记为E(X)，如上例E(X)X 2+X。有差错时接收端收到的不再是T(X)，而是T(X)与E(X)的模2加，即： T(X)+E(X)/G(X)T(X)/G(X)+E(X)/G(X) 由此可见，若E(X)/G(X)不等于0，则这种差错就能检测出来；否则E(X)/G(X)0，由于码字多项式仍能被G(X)整除，就发生漏检。,6.6.2 循环冗余码,【性质1】若G(X)含有x+1的因子，则能检测出所有奇数错。 【性质2】若G(X)中不含有x的因子，或者换句话讲，G(X)中含有常数项1，那么能检测出所有突发长度r的突发错。 【性质3】若G(X)中不含有x的因子，而且对任何0en-1的e，除不尽Xe+1，则能检测出所有的双错。 【性质4】若G(X)中不含有x的因子，则对突发长度为r+1的突发错误的漏检率为2-(r-1)。 【性质5】若G(X)中不含有x的因子，则对突发长度b大于r+1的突发错误的漏检率为2-r。,6.6.2 循环冗余码,6.6.3 海明码,由R.Hamming在1950年首次提出的，它是一种