第2章 计算机系统中的数据表示方法

第2章计算机系统中的数据表示方法程利新哈尔滨工程大学计算机科学与技术学院2.1概述计算机的组成在很大程度上取决于数字、字符和控制信息的表示方法。计算机系统基本信息单元：位（bit），表示了电子开关的状态或电位的高低。字节（byte）：8位组成的计算机存储器编址的基本单位。字（word）：由两个或者多个相邻的字节构成。字的大小表示特定计算机体系结构能够处理的数据大小。8位计算机、16位计算机、32位计算机、64位计算机、……。半字节（nibble）：字节的一半（高4位或者低4位）2.2位置编码系统十进制表示法位置编码系统（positionalnumberingsystem）基本思想：任意数字的值可以通过表示成某个基数（或称为底，radix）的乘幂形式，也称为权重编码系统（weightednumberingsystem）。在位置编码系统中，数中每一个位置都是基数的幂次方，故称位置编码系统。位置编码系统中所使用的有效数字的数目等于系统基数的大小。任何一种计数系统（数制）的最大合法数字均为基数减1.采用下标表示基数，缺省的表示十进制数2.2位置编码系统计算机科学中，最重要的数制是二进制（基数是2）和十六进制（基数为16）。另外一个比较重要的数制是八进制（基数为8）。2.3十进制数和二进制数之间的转换二进制计数系统实质上已经成为所有依赖于数字控制的电子设备的核心基础。二进制计数法简单，可以较为方便的转换为对应电子线路。2.3.1无符号整数的转换转换方法分为两种：重复减法除法余数法重复减法比较麻烦，要求对所使用基数的幂指数形式比较熟悉除法余数法简单并快速N为无符号二进制数表示范围：0到2N-1无符号十进制数。对二进制数进行算术运算时，给定位数二进制数所能表示的数值范围是非常重要的。溢出（overflow）现象：运算结果超出二进制位数所能表示范围。2.3.2分数转换在任意数制中，分数都可以采用其他数制中基数的负指数幂来近似表示。小数点分开整数部分和分数部分，十进制小数点，二进制小数点。对于分数转换，同样可以采用重复减法和余数法。其中余数法由除法余数法变为乘法余数法，同时由取余数，变为取结果的整数部分，结果的顺序从由下而上变为由上而下。对于循环分数，执行某些取舍近似算法，保证有限字长条件下的转换精度。重复减法和余数法可以用于任意基数数字间的转换，若通过十进制数中转，可比直接转换快捷和精确。2.3.3以2的指数幂为基数的数制之间的转换将二进制转换为十六进制或者八进制增加可读性16=24，8=23，因而可以对二进制数进行分组，从而快速进行十六进制或者八进制转换。倍乘转换法一种将二进制数转换为十进制数的最快方法基本思想：从最左边的位开始，每个后面位（高位）的2的乘幂总是前面位（低位）的2的乘幂的2倍。从最左边的位开始进行计算，将第一位乘以2加到第二位上去，得到结果再乘以2加到第三位上，以此类推，直到最右边的位。2.4带符号整数的表示方法将存储单元的最高位作为符号位，最高位为‘0’表示正整数，最高位为‘1’表示负整数。带符号整数表示法符号幅值法（原码）：利用符号位后的剩余位数表示数字的幅值（大小）反码补码2.4.1符号幅值表示法（原码）符号幅值表示法中，数字的最左边的位（也称为最高位，或者最高有效位）是一个符号，而余下的位用来表示数值的幅值（或称为绝对值）。N位二进制数，采用符号幅值表示法能够表示的整数范围是：-2(N-1)+1到2(N-1)-1。符号幅值表示法尽管方法简单，但是对其进行运算则较为复杂。对于符号幅值表示法表示的数据，运算过程中产生的对最高位的进位必须舍弃。符号位需要进行单独处理。原码加减法与十进制算术的纸笔运算方法类似。2.4.1符号幅值表示法（原码）原码的缺点：计算复杂存在正0和负0的区别2.4.2补码体系十进制减法可以通过加上减数与全9组成的数字的差，再加回一个进位的方法来实现。这种方法称为取减数的9的补码，或者称为求减数的十进制反码。这种表示法的好处是不需要单独处理符号位。2.4.2补码体系反码：如果已知基数为r，有d位数字表示，那么数字N的反码定义为（rd-1）-N构成一个二进制数的反码很简单，将二进制数按位取反即可。正数的反码就是其本身，负数才有反码。二进制减法可转化为反码加法：将减数表示成反码形式，与被减数相加，最高位的进位加到结果的最低位从而得到最终结果。由反码求原码的方法与由原码求反码的方法一致。N位二进制数，采用反码表示法能够表示的整数范围是：-2(N-1)+1到2(N-1)-1。反码的缺点：存在正‘0’：00000000和负‘0’：11111111。2.4.2补码体系补码：如果已知基数为r，有d位数字表示，若数字N不等于0，则N的反码定义为rd–N，如果N等于0，则N的补码定义为0.求补码方法：对于正数，其补码就是其本身，对于负数，其补码通过将其原码按位取反后加1得到。补码运算中，必须舍弃所有与最高位有关的进位。由补码求原码方法：将补码按位取反后加1得到。N位二进制数，采用补码表示法能够表示的整数范围是：-2(N-1)到2(N-1)-1。补码运算溢出判断法则：如果进入符号位和移出符号位的进位相同，那么没有溢出发生，否则，就有溢出发生，也就是出现一个错误。补码是目前最通用的带符号数字表示方法。2.5浮点表示法早期计算机的设计初衷是面向整数计算的，在处理浮点数计算的问题中，采用一些编程技巧来使得浮点运算得以实现。浮点运算的处理方法：科学计数法。即在一个整数机的系统中实现浮点仿真，将小数部分（尾数）和指数部分分别表示。科学计数法是现代数字计算机中浮点计算法的基础。2.5.1一个简单的模型数字计算机系统中，浮点数由三部分组成：符号位、指数部分（以2的幂指数形式表示）和小数部分，其中小数部分称为有效数。表示范围和精度表示范围越大，使用的指数位数越多精度越高，需要的有效数的位数越多2.5.1一个简单的模型为了解决负指数如何表示的问题，采用偏移指数的方法。偏移指数方法的思想：在允许的范围内将每一个整数指数转化成一个非负整数指数，这样就可以把每个整数都作为一个二进制数来存储。偏移指数方法：在指数允许的表示范围之内，在每个指数上加一个固定偏移值来对整数指数进行调整。一般取偏移值为可表示范围的中间值。规格化：将有效数的最左边的位设置为1。2.5.2浮点算法浮点数加减法：先将两个数表示成具有同一基数的相同指数形式，然后将小数部分相加减。浮点数乘除法：与十进制指数运算法则相同2.5.3浮点误差误差产生的原因：计算机的有限整数系统对无限的实数系统进行建模，只能是实数系统的的一个近似。所使用的位数越多，近似就越好。但误差总是存在的。不管把系统设计得有多么大，只要是利用有限的系统表示实数，或多或少都会引入不同程度的浮点误差，即使是最小的误差，有时也会导致严重的后果。2.5.4IEEE-754浮点标准前面引入的浮点模型可以推广至任意位数浮点数的表示。由于标准的不统一，各类系统难以兼容。1985年，IEEE发表单精度和双精度浮点表示标准IEEE-754。IEEE-754单精度浮点数字长32位，其中8位指数，以127为偏移值，23位有效数，1位符号位。IEEE-754双精度浮点数字长64位，其中11位指数，52位有效数，1位符号位，偏移值为1023。2.6字符编码数字计算机除了使用二进制体系表示和处理数字值，还要考虑将计算机内部数值转换成人所能理解的形式。这种转换方式既取决于计算机使用的编码系统，也和这些数值的存取方式有关。2.6.1二进制编码的十进制数二进制编码的十进制数（Binary-CodedDecimal,BCD)：将每个十进制数字编码成一个4位二进制数形式。在按照8位进行存储时，BCD码的高4位称为区位，而低4位称为数字。区位表示了符号，1111为无符号数，1100为正数，1101为负数。压缩的BCD码：将多个相连的数字放入相邻的半字节中，只留下一个半字节表示符号。这样可以简化计算，并且可以节省空间。2.6.2EBCDICEBCDIC（ExtendedBinaryCodedDecimalInterchangeCode）：为了提高计算机系统的信息处理能力以及同时存储数字和数据的统一方法。2.6.3ASCIIASCII（AmericanStandardCodeforInformationInterchange）美国信息交换标准码ASCII码来自5位的摩尔编码，并被扩充至7位编码，被称为第5种国际字母。ASCII码定义了32个控制字符，10个数字，52个英文字母，32个特殊字符以及空格符号。最高位预留用于奇偶校验位。ASCII码的应用十分广泛，20世纪80年代，计算机设备制造商利用奇偶校验位来为128和255之间的数值提供一个“扩展的”字符集。2.6.4统一字符编码无论是EBCDIC，还是ASCII码，均面向拉丁语系字母的编码。对于非拉丁语系字符的编码难以处理。统一字符编码（Unicode）被发明用于都全世界每一种语言的大多数字符进行统一编码。2.7用于数据记录和传递的编码方式ASCII码、EBCDIC码和Unicode用于存储器中的字符编码，但不适合磁介质存储和远距离传输。数据编码：用于磁介质存储和远距离传输的字符编码2.7.1不归零编码采用电平的高低或者磁通量的极性表示编码容易出错。2.7.2反转不归零编码采用信号的转变表示编码，电平的变化表示1，没有变化表示02.7.3相位调制编码也称为曼彻斯特编码（ManchesterCoding）：通过为编码的每一位提供一个信号跳变，二进制数1由上升跳变给出，0则对应一个下降跳变，从而解决同步问题。2.7.4频率调制编码在每个位单元中至少提供一个信号跃变，这些同步跃变发生在每个位单元的开始处。同时对于二进制数1还要在位单元的中间再多提供一个额外信号跃变2.7.5运行长度限制编码一种对有字符编码组成的字进行分块的编码方式。2.8错误检测与校正错误检测与校正的必要性既不可能不产生错误，也不可能百分百检测出错误的发生，或者校正错误。在计算机系统的设计中，错误检测和校正十分重要。2.8.1循环冗余码校验循环冗余码校验（CyclicRedundancyCheck，CRC）：一种求校验和的错误检测方法。CRC可在一大块或者是一长串数据中判断是否出现错误。CRC将生成的错误校验位加在原始信息数据位的后面，组成错误校验位的位组合，进行传输或者存储。利用位组合中的错误校验位检验数据位的正确性。2.8.1循环冗余码校验模2算术：无进位和借位的二进制算术0+0=00+1=11+0=11+1=0CRC计算和使用方法确定CRC多项式P将待编码数据字I左移P的位数减1位将I作为被除数，将P作为除数，进行模2除法，略去商只留下余数把余数加到I上，组成编码字M校验时，将P作为除数，将M做为被除数，若能整除，则没有出错，否则，传输或存储过程中一定发生了错误。2.8.1循环冗余码校验CRC多项式采用大指数幂的互质多项式时，检测效果最好标准多项式CRC-CCITT(ITU-T):X16+X12+X5+1CRC-12:X12+X11+X3+X2+X+1CRC-16(ANSI):X16+X15+X2+1CRC-32:X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X+1CRC硬件加速将各种可能输入的位组合模式产生的余数“烧录”到存储设备中2.8.2海明编码（HammingCode）较为适用于存储设备的错误检测和恢复机制数据通信数据检测出错误后，可进行数据重传存储数据再生较难海明编码基于奇偶校验的概念，检测和校正能力随着所加入奇偶校验位的数目成正比。常用于随机错误的检测和校正应用前提：数据位中每一位的出错概率相同，与其他位的出错没有关联2.8.2海明编码（HammingCode）海明编码术语校验位：海明编码中所使用的奇偶校验位，也称冗余位编码字：由所存储信息字（数据字）加上冗余位形成的二进制编码。每个数据字有且仅有一个编码字与其对应。海明距离（Hammingdistance）：两个编码字之间不同位的位置数目最小海明距离：对于任意一种计算海明校验位的算法，都可以构造出全部合法编码字的完整列表。各对编码字之间的最小海明距离称为该编码的最小海明距离，记为D(min)。最小海明距离决定了编码校验错误的能力。2.8.2海明编码（HammingCode）海明码错误检测原理：若两个编码字的海明距离为d，那么把一个编码字转换为另一个编码字需要翻转d个单一位，因此不同单一位位置数目小于d的编码字，为出错编码字。最小海明距离决定了编码校验错误的能力。任意编码字X若要被当做另一个合法编码字Y来接收的话，那么X中至少需要发生D(min)个错误。因此要检验k（或者少于k个）单位错误，编码就必须具有D(min)=k+1的海