登入帳戶　 |　訂單查詢　 |　購物車/收銀台(0)　|　在線留言板　 |　付款方式　 |　聯絡我們　 |　運費計算　 |　幫助中心　|　 加入書簽
	全部範圍 - 圖書 - 　- 中文簡體書(大陸書) - 　- 英文書（原版） - - 音碟 - 　- 音樂 - 　- 影視 - - 雜誌 - 全文 精確	會員登入   新用戶註冊

HOME新書上架暢銷書架好書推介特價區會員書架精選月讀2023年度TOP分類閱讀雜誌

香港／國際用戶

最新/最熱/最齊全的簡體書網

品種：超過100萬種書，正品正价，放心網購，悭钱省心

送貨：速遞 / 物流，時效：出貨後2-4日

新書推薦： 《 德国天才4：断裂与承续 》 售價：NT$ 500.0 《 妈妈的情绪，决定孩子的未来 》 售價：NT$ 194.0 《 推拿纲目 》 售價：NT$ 1836.0 《 精致考古--山东大学实验室考古项目论文集（一） 》 售價：NT$ 1112.0 《 从天下到世界——国际法与晚清中国的主权意识 》 售價：NT$ 347.0 《 血色帝国：近代英国社会与美洲移民 》 售價：NT$ 265.0 《 海外中国研究·王羲之：六朝贵族的世界（艺术系列） 》 售價：NT$ 811.0 《 唐宋绘画史 全彩插图版 》 售價：NT$ 449.0

建議一齊購買： + NT$ 285 《 C程序设计语言（第2版?新版） 》 + NT$ 441 《 数学之美（第二版） 》 + NT$ 561 《 计算机科学概论（第11版）（英文版） 》 編輯推薦： 计算机科学的全景式展现 首屈一指的导论性教材 经典传承，新知荟萃 內容簡介： 《计算机科学概论第11版》是计算机科学概论课程的经典教材，全书对计算机科学做了百科全书式的精彩阐述，充分展现了计算机科学的历史背景、发展历程和新的技术趋势。《计算机科学概论第11版》首先介绍的是信息编码及计算机体系结构的基本原理第1章和第2章，进而讲述操作系统第3章和组网及因特网第4章，接着探讨了算法、程序设计语言及软件工程第5章至第7章，然后讨论数据抽象和数据库第8章和第9章方面的问题，第10章通过图形学讲述计算机技术的一些主要应用，第11章涉及人工智能，第12章通过对计算理论的介绍来结束全书。《计算机科学概论第11版》在内容编排上由具体到抽象逐步推进，很适合教学安排，每一个主题自然而然地引导出下一个主题。此外，书中还包含大量的图、表和示例，有助于读者对知识的了解与把握。 《计算机科学概论第11版》适合用作高等院校计算机以及相关专业本科生的教材。 關於作者： J. Glenn Brookshear 世界知名的计算机科学教育家。他在1975年获得新墨西哥州立大学博士后，创办了Marquette大学的计算机科学学位项目，并在该校任教至今。他的主要研究方向是计算理论。除了本书之外，他还著有Theory of Computationr: Formal Languages, Automata, and Complexity。 目錄： 目　录 第0章　绪论　1 0.1　算法的作用　1 0.2　计算机器的由来　3 0.3　算法的科学　7 0.4　抽象　8 0.5　学习大纲　8 0.6　社会影响　9 社会问题　11 课外阅读　12 第1章　数据存储　13 1.1　位和位存储　13 1.1.1　布尔运算　13 1.1.2　门和触发器　14 1.1.3　十六进制记数法　17 1.2　主存储器　18 1.2.1　存储器结构　18 1.2.2　存储器容量的度量　19 1.3　海量存储器　20 1.3.1　磁学系统　20 1.3.2　光学系统　22 1.3.3　闪存驱动器　23 1.3.4　文件存储及检索　24 1.4　用位模式表示信息　25 1.4.1　文本的表示　25 1.4.2　数值的表示　26 1.4.3　图像的表示　27 1.4.4　声音的表示　28 *1.5　二进制系统　29 1.5.1　二进制记数法　29 1.5.2　二进制加法　31 1.5.3　二进制中的小数　32 *1.6　整数存储　33 1.6.1　二进制补码记数法　33 1.6.2　余码记数法　36 *1.7　小数的存储　37 1.7.1　浮点记数法　37 1.7.2　截断误差　39 *1.8　数据压缩　41 1.8.1　通用的数据压缩技术　41 1.8.2　图像压缩　43 1.8.3　音频和视频压缩　44 *1.9　通信差错　45 1.9.1　奇偶校验位　45 1.9.2　纠错编码　46 复习题　47 社会问题　50 课外阅读　51 第2章　数据操控　52 2.1　计算机体系结构　52 2.1.1　CPU基础知识　52 2.1.2　存储程序概念　53 2.2　机器语言　54 2.2.1　指令系统　54 2.2.2 一种演示用的机器语言　56 2.3　程序执行　58 2.3.1　程序执行的一个例子　60 2.3.2　程序与数据　62 *2.4　算术逻辑指令　63 2.4.1　逻辑运算　63 2.4.2　循环移位及移位运算　65 2.4.3　算术运算　66 *2.5　与其他设备通信　67 2.5.1　控制器的作用　67 2.5.2　直接内存存取　68 2.5.3　握手　69 2.5.4　流行的通信媒介　69 2.5.5　通信速率　70 *2.6　其他体系结构　70 2.6.1　流水线70 2.6.2　多处理器计算机　71 复习题　72 社会问题　77 课外阅读　77 第3章　操作系统　79 3.1　操作系统的历史　79 3.2　操作系统的体系结构　82 3.2.1　软件概述　82 3.2.2　操作系统组件　84 3.2.3　系统启动　86 3.3　协调机器的活动　88 3.3.1　进程的概念　88 3.3.2　进程管理　88 *3.4　处理进程间的竞争　90 3.4.1　信号量　90 3.4.2　死锁　91 3.5　安全性　93 3.5.1　来自机器外部的攻击　93 3.5.2　来自机器内部的攻击　94 复习题　95 社会问题　98 课外阅读　98 第4章　组网及因特网　99 4.1　网络基础　99 4.1.1　网络分类　99 4.1.2　协议　100 4.1.3　网络互连　102 4.1.4　进程间通信的方法　104 4.1.5　分布式系统　105 4.2　因特网　106 4.2.1　因特网体系结构　106 4.2.2　因特网编址　108 4.2.3　因特网应用　109 4.3　万维网　113 4.3.1　万维网实现　113 4.3.2　HTML　114 4.3.3　XML　117 4.3.4　客户端和服务器端的活动　118 *4.4　因特网协议　119 4.4.1　因特网软件的分层方法　119 4.4.2　TCPIP协议簇　122 4.5　安全性　123 4.5.1　入侵的形式　124 4.5.2　防护和对策　125 4.5.3　加密　126 4.5.4　网络安全的法律途径　128 复习题　130 社会问题　131 课外阅读　132 第5章　算法　134 5.1　算法的概念　134 5.1.1　概览　134 5.1.2　算法的正式定义　135 5.1.3　算法的抽象本质　136 5.2　算法的表示　136 5.2.1　原语　137 5.2.2　伪代码　139 5.3　算法的发现　142 5.3.1　问题求解的艺术　142 5.3.2　入门　144 5.4　迭代结构　146 5.4.1　顺序搜索法　147 5.4.2　循环控制　148 5.4.3　插入排序算法　151 5.5　递归结构　154 5.5.1　二分搜索算法　154 5.5.2　递归控制　159 5.6　有效性和正确性　160 5.6.1　算法有效性　160 5.6.2　软件验证　163 复习题　167 社会问题　171 课外阅读　171 第6章　程序设计语言　172 6.1　历史回顾　172 6.1.1　早期程序设计语言　172 6.1.2　独立并超越机器　174 6.1.3　程序设计范型　175 6.2　传统的程序设计概念　179 6.2.1　变量和数据类型　180 6.2.2　数据结构　181 6.2.3　常量和字面量　182 6.2.4　赋值语句　183 6.2.5　控制语句　184 6.2.6　注释　187 6.3　过程单元　188 6.3.1　过程　188 6.3.2　参数　189 6.3.3　函数　192 6.4　语言实现　193 6.4.1　翻译过程　193 6.4.2　软件开发包　198 6.5　面向对象程序设计　199 6.5.1　类和对象　199 6.5.2　构造器　202 6.5.3　附加特性　202 *6.6　程序设计中的并发活动　204 *6.7　说明性程序设计　206 6.7.1　逻辑推演　206 6.7.2　Prolog　208 复习题　210 社会问题　213 课外阅读　214 第7章　软件工程　215 7.1　软件工程学科　215 7.2　软件生命周期　217 7.2.1　周期是个整体　217 7.2.2　传统的开发阶段　218 7.3　软件工程方法　220 7.4　模块化　221 7.4.1　模块式实现　222 7.4.2　耦合　224 7.4.3　内聚　225 7.4.4　信息隐藏　225 7.4.5　构件　226 7.5　行业工具　227 7.5.1　较老的工具　227 7.5.2　统一建模语言　228 7.5.3　设计模式　232 7.6　质量保证　233 7.6.1　质量保证的范围　233 7.6.2　软件测试　234 7.7　文档编制　235 7.8　人机界面　236 7.9　软件所有权和责任　238 复习题　240 社会问题　242 课外阅读　243 第8章　数据抽象　244 8.1　数据结构基础　244 8.1.1　数组　244 8.1.2　列表、栈和队列　245 8.1.3　树　245 8.2　相关概念　247 8.2.1　抽象　247 8.2.2　静态结构与动态结构　247 8.2.3　指针　248 8.3　数据结构的实现　248 8.3.1　数组的存储　248 8.3.2　列表的存储　251 8.3.3　栈和队列的存储　254 8.3.4　二叉树的存储　255 8.3.5　数据结构的操作　257 8.4　一个简短案例　259 8.5　定制的数据类型　263 8.5.1　用户自定义数据类型　263 8.5.2　抽象数据类型　264 *8.6　类和对象　266 *8.7　机器语言中的指针　267 复习题　269 社会问题　273 课外阅读　274 第9章　数据库系统　275 9.1　数据库基础　275 9.1.1　数据库系统的重要性　275 9.1.2　模式的作用　276 9.1.3　数据库管理系统　277 9.1.4　数据库模型　278 9.2　关系模型　279 9.2.1　关系设计中的问题　279 9.2.2　关系运算　282 9.2.3　SQL　285 *9.3　面向对象数据库　287 *9.4　维护数据库的完整性　289 9.4.1　提交回滚协议　289 9.4.2　锁定　290 *9.5　传统的文件结构　291 9.5.1　顺序文件　291 9.5.2　索引文件　294 9.5.3　散列文件　294 9.6　数据挖掘　297 9.7　数据库技术的社会影响　299 复习题　300 社会问题　303 课外阅读　304 第10章　计算机图形学　305 10.1　计算机图形学的范围　305 10.2　3D图形概述　307 10.3　建模　308 10.3.1　单个物体的建模　308 10.3.2　 整个场景的建模　313 10.4　渲染　314 10.4.1　光——表面交互　314 10.4.2　裁剪、扫描转换和隐藏面的消除　316 10.4.3　着色　319 10.4.4　渲染——流水线硬件　320 *10.5　处理全局照明　321 10.5.1　光线跟踪321 10.5.2　辐射度　323 10.6　动画　323 10.6.1　动画基础　323 10.6.2　运动学和动力学　325 10.6.3　动画制作过程　326 复习题　326 社会问题　328 课外阅读　329 第11章　人工智能　330 11.1　智能与机器　330 11.1.1　智能体　330 11.1.2　研究方法　332 11.1.3　图灵测试　332 11.2　感知　333 11.2.1　理解图像　333 11.2.2　语言处理　335 11.3　推理　338 11.3.1　产生式系统　338 11.3.2　搜索树　340 11.3.3　启发式搜索　342 11.4　其他研究领域　346 11.4.1　知识的表达和处理　346 11.4.2　学习　347 11.4.3　遗传算法　349 11.5　人工神经网络　349 11.5.1　基本特性　350 11.5.2　训练人工神经网络　351 11.5.3　联想记忆　353 11.6　机器人学　356 11.7　后果的思考　358 复习题　359 社会问题　363 课外阅读　364 第12章　计算理论　365 12.1　函数及其计算　365 12.2　图灵机　367 12.2.1　图灵机的原理　367 12.2.2　丘奇-图灵论题　369 12.3　通用程序设计语言　370 12.3.1　Bare Bones语言　370 12.3.2　用Bare Bones语言编程　372 12.3.3　Bare Bones的通用性　373 12.4　一个不可计算的函数　375 12.4.1　停机问题　375 12.4.2　停机问题的不可解性　376 12.5　问题的复杂性　379 12.5.1　问题复杂性的度量　379 12.5.2　多项式问题与非多项式问题　382 12.5.3　NP问题　383 *12.6　公钥密码学　386 12.6.1　模表示法　386 12.6.2　RSA公钥加密系统　387 复习题　389 社会问题　392 课外阅读　392 附录A　ASCII 码　394 附录B　处理二进制补码表示的电路　395 附录C　一种简单的机器语言　397 附录D　高级编程语言　399 附录E　迭代结构与递归结构的等价性　401 索引　403 问题与练习答案图灵社区网站下载 內容試閱： 数 据 存 储 在 本章中，我们学习有关计算机中数据表示和数据存储的内容。我们要研究的数据类型包括文本、数值、图像、音频和视频。除了传统计算外，本章的很多内容还涉及数字摄影、音频视频录制和复制，以及远程通信等领域。 本章内容 1.1　位和位存储 1.2　主存储器 1.3　海量存储器 1.4　用位模式表示信息 *1.5　二进制系统 *1.6　整数存储 *1.7　小数的存储 *1.8　数据压缩 *1.9　通信差错 复习题 社会问题 课外阅读 我们首先要学习的是在计算机科学中信息如何编码和存储。第一步，我们要讨论计算机数据存储设备的基础知识，然后研究如何进行信息编码并将其存储到系统内部。我们还将探讨现如今数据存储系统的各个分支，以及如何用数据压缩、错误处理等技术来克服其不足。 1.1 位和位存储 在今天的计算机中，信息是以0和1的模式编码的。这些数字称为位（bit，binary digits的缩写）。尽管你可能倾向于把它们与数值联系在一起，但它们的确只是些符号，其意义取决于正在处理的应用：有时用来表示数值；有时又代表字母表里的字符和标点符号；有时表示图像；有时还表示声音。 1.1.1 布尔运算 为了理解单独的位在计算机中是如何进行存储和操作的，这里我们假设位0代表FALSE（假），位1代表TRUE（真），这样表示就可以把对位的运算看做是对真假值的操作。数学家乔治?布尔（George Boole，1815—1864）是逻辑数学领域的先驱，为了纪念他，人们把处理真假值的运算命名为布尔运算（Boolean operation）。3个基本的布尔运算是AND（与）、OR（或）以及XOR（异或），见图1-1。这些运算类似于算术运算的乘法和加法，因为它们结合一对值（运算输入），然后得出第三个值（运算输出）。不过，与算术运算不同的是布尔运算结合的是真假值，而不是数值。 布尔运算AND是用于反映由两个较小、较简单语句通过连接词AND组成的语句的真假值。一般形式如下： P AND Q 其中，P代表一个语句，Q代表另外一个语句。例如： Kermit是一只青蛙 AND Piggy小姐是一位演员 AND运算的输入是复合语句分句的真假值，输出则是复合语句本身的真假值。因为P AND Q语句的值只有在其两个分句都是真时才为真，所以可以得出结论：1 AND 1的输出是1，而其他所有情况的输出值都将是0，如图1-1所示。 同理，OR运算是基于如下形式的复合语句： P OR Q 同样，P代表一个语句，Q代表另外一个语句。当其中至少有一个分句为真时，语句才为真，见图1 1。 图1-1 布尔运算AND、OR和XOR 英语中没有一个连词可以单独表示XOR。当两个分句一个为1（真），另一个为0（假）时，此XOR运算值是真。例如，P XOR Q语句的意思是“或者是P，或者是Q，但不会是两个共存”。（简言之，当两分句不同时，XOR运算为真。） NOT（非）运算是另一个布尔运算。它区别于AND、OR和XOR，因为它只有一个输入。它的输出就是输入值的相反值。如果NOT运算的输入值是真，那么它的输出值为假，反之亦然。因此，如果NOT运算的输入是下面的语句的真假值： Fozzie is a bear. 那么，其输出就是如下语句的真假值： Fozzie is not a bear. 1.1.2 门和触发器 门（gate）指的是一种设备，给出一种布尔运算输入值时，可以得出该布尔运算的输出值。门可以通过很多种技术制造出来，如齿轮、继电器和光学设备。今天的计算机中，门经常是通过微电子电路实现的，其中数字0和1由电压电平表示。不过，我们不需要关注这些细节问题。对于我们来说，知道用符号形式来表示门就足够了，如图1-2所示。注意，与、或、异或及非门是分别用不同形状的图表示的，输入值在一边，输出值在另一边。 图1-2 与、或、异或以及非门的图例及输入和输出值 这样的门为构造计算机提供了基础构件。构造计算机时，图1-3所示的电路是一个重要的环节，该电路是一个称为触发器的电路特例。触发器（flip-flop）是一个可以产生0或1输出值的电路，它的值会一直保持不变，除非其他电路过来的临时脉冲使其改变成另一个值。换句话说，输出值在外界的刺激下在两个值之间相互转换。如图1-3所示，只要电路两个输入值一直都是0，那么输出值（无论是0还是1）就不会改变。不过，如果在它的上输入端临时放置一个1，那么将强制其输出值为1；反之，在它下输入端临时放置一个1，那么将强制其输出值为0。 图1-3 一个简单的触发器电路 我们来仔细研究一下这个问题。在我们不知道图1 3中电路的当前输出值的情况下，假设上面的输入值变为1，而下面的输入值仍为0（见图1-4a），那么不管这个门另外一个输入值是什么，或门的输出值都将为1。这时，与门的两个输入值都为1，因为这个门的另外一个输入值已经为1（由经过触发器下输入端的非门获得）。与门的输出值于是变成1，也就意味着现在或门的第二次输入值将为1（见图1-4b）。这样就可以确保即使触发器上面的输入值变回0（见图1-4c），或门的输出值也会保持为1。总之，触发器的输出值已经为1，那么输入值变回0时，其输出值仍然保持不变。 图1-4 将一个触发器的输出值设置为1 同理，在下输入端上临时放置数值1会强制触发器的输出值为0，而且输入值变回0时，输出值仍然保持不变。 我们介绍触发器电路（见图1-3和图1-4）有3个原因。首先，它向我们展示了设备是如何通过门制造出来的，这是一个数字电路的设计过程，在计算机工程领域是一个很重要的课题。事实上，在计算机工程中，触发器只是诸多基础工具电路的一种。 第二，触发器的概念为抽象和使用抽象工具提供了一个例子。事实上，可以用多种方法设计触发器。图1-5给出了其中的一种方法，如果你用这个电路做实验就会发现，尽管它有着不同的内部结构，但它与图1-3中的外部特性是一样的。计算机工程师不必知晓触发器中实际使用的是哪种电路，只需理解触发器的外部特性并将其作为一个抽象工具来使用即可。一个触发器和其他定义良好的电路形成了一组构建块，而工程师就用这些构建块构造更复杂的电路。这样，计算机电路的设计就会呈现一种层次结构，其中每一层都将较低层次的构件作为抽象工具使用。 介绍触发器的第三个目的在于，触发器是在现代计算机中存储二进制位的一种方法。更精确地说，触发器可以被设置为具有0或1的输出值。其他电路可以通过发送脉冲到触发器的输入端调整这个值，还有其他一些电路可以将触发器的输出作为它们的输入来响应存储的值。这样，许多触发器被构造成非常小的电子电路，可以用在计算机内作为记录信息的一种方法，这些信息被编码成0和1的模式。实际上，众所周知的VLSI（Very Large-Scale Integration，超大规模集成）技术支持将成千上万个电子元件构造在一个晶片［称为芯片（chip）］上，它用来创建在控制电路中含有成千上万个触发器的微型设备。然后，这些芯片被用作构建计算机系统的抽象工具。事实上，在某些情况下VLSI被用来在单块芯片上创建整个计算机系统。 图1-5 构建触发器的另一种方法 1.1.3 十六进制记数法 当考虑计算机内部活动时，我们必须和位串打交道，有一些位串会非常长。一个长的位串常被称为流（stream）。但是，人脑不容易理解流。仅仅抄录位模式的101101010011就很乏味且容易出错误。因此，为了简化这种位模式的表示方法，我们常使用一种称为十六进制记数法（hexadecimal notation）的简写符号，它是利用计算机位模式的长度为4的倍数这样一个事实制定的。具体来说就是，十六进制记数法用一个符号表示位模式的4位。例如，一个12位串只需要3个符号就可以表示。 图1-6呈现了十六进制编码系统。左边一列展示的是所有长度为4的位模式，右边一列展示的是十六进制中代表左边位模式的符号。通过这个系统，10110101形式表示为B5。这是通过把位模式拆分为长度为4的子串，然后用十六进制的符号代替每一个子串得到的——1011由B来表示，0101由5来表示。同理，十六位模式1010010011001000可以缩减成更易为人接受的形式A4C8。 第2章将广泛使用十六进制记数法，由此你就能体会到它的效率。 问题与练习 1. 什么样的位模式输入可以使得下面的电路输出值为1？ 2. 对于图1-3中的触发器，我们在文中强调，下输入端放置1（保持上输入端为0），这样就迫使触发器的输出为0。描述一下这种情况触发器内部的活动序列。 3. 假定图1-5中触发器的输入都为0，描述一下当上输入端被临时设为1时所发生的活动序列。 4. a. 如果一个与门的输出值传递给了一个非门，那么这个组合电路计算的布尔运算称为与非。当且仅当输入值都为1时，输出值为0。与非门的符号和与门的符号类似，只是输出有一个圆圈。下面的电路包含与非门，那么这个电路完成什么布尔运算？ b. 如果一个或门的输出值传递给一个非门，那么这个组合电路计算的布尔运算称为或非，当且仅当输入值都为0时，输出值为1。或非门的符号和或门的符号类似，只是输出有一个圆圈。下面的电路包含一个与门和两个或非门。那么这个电路计算称为什么布尔运算？ 5. 用十六进制记数法来表示下面的位模式。 a. 0110101011110010 b. 111010000101010100010111 c. 01001000 6. 下面的十六进制模式表示什么位模式？ a. 5FD97 b. 610A c. ABCD d. 0100 1.2 主存储器 为了存储数据，计算机包含大量的电路（如触发器），每一个电路能够存储单独的一个位。这种位存储器被称为计算机的主存储器（main memory）。 1.2.1 存储器结构 计算机主存储器是以称为存储单元（cell）的可管理单位组织起来的，一个典型的存储单元容量是8位。［一个8位的串称为一个字节（byte），因此一个典型的存储单元容量是一个字节。］在像微波炉这样的家用电器中所使用的小型计算机的主存储器，仅仅包含几百个存储单元，但是大型计算机的主存储器可能有上亿个存储单元。 虽然计算机中没有左或右的概念，但是我们通常假设存储单元的位是排成一行的。该行的左端称为高位端（high-order end），右端称为低位端（low-order end）。高位端的最左一位称作高位或最高有效位（most significant bit）。取这个名称是因为，如果把存储单元里的内容解释为数值，那么这一位就是该数的最高有效数字。类似地，低位端的最右一位称为低位或最低有效位（least significant bit）。于是，我们可以如图1-7所示的那样描述字节型存储单元的内容。 图1-7 字节型存储单元的结构 为了区分计算机主存储器中的各存储单元，每一个存储单元都被赋予了一个唯一的“名字”，称为地址（address）。这类似于通过地址找到城市里的一座座房屋。不过，对于存储单元，所用地址都是用数字表示的。更精确地说，我们把所有的存储单元都看做是排成一行的，并按照这个顺序从0开始编号。这样的编址系统不仅为我们提供了唯一标识每个存储单元的方法，而且也给存储单元赋予了顺序的概念（见图1-8），这样就有了诸如“下一个单元”、“前一个单元”的说法。 图1-8 按地址排列的存储单元 将主存储器的存储单元和存储单元的位都进行排序，就产生一个重要结果，即计算机主存储器的所有二进制位本质上被排成了一长行，因而这个长行上的片段就可以存储比单个存储单元要长的位模式。特别是，我们只需要两个连续的存储单元就可以存储16位的串。 为了做成一台计算机的主存储器，实际存放二进制位的电路还组合了其他的电路，这些电路使得其他电路可以在存储单元中存入和取出数据。以这种方式，其他电路可以通过电信号请求从存储器中得到指定地址的内容（称为读操作），或者请求把某个位模式存放到指定地址的存储单元里（称为写操作）。 因为计算机的主存储器由独立的、可编址的存储单元组成，所以可以根据需要独立访问这些存储单元。为了反映用任何顺序访问存储单元的能力，计算机的主存储器常被称为RAM（Random Access Memory，随机存取存储器）。主存储器的这种随机存取特性与1.3节中将要讨论的海量存储系统形成鲜明对比，在海量存储系统中长二进制串被作为合并块来操控。 尽管我们介绍说触发器可以作为二进制位的一种存储方法，但是在现代的大多数计算机中，RAM都是用其他可以提供更小型化和更快响应时间的技术制造的，其中许多技术将位存储为可快速消散的电荷。因此，这些设备需要附加的电路，称为刷新电路，可以在1s内反复补充电荷很多次。因为它的这种不稳定性，所以通过这种技术构造的计算机存储器常被称为动态存储器（dynamic memory），于是就产生了术语DRAM（读作“DEE-ram”），用来表示动态RAM。有时候关于动态存储器也会用SDRAM（读作“ES-DEE-ram”），用来表示同步动态RAM，采取这种附加的技术可以缩短从存储单元取出信息所需要的时间。 1.2.2 存储器容量的度量 在第2章会学到，如果主存储器中存储单元的总数是2的幂，那么设计起来是很方便的，因此早期计算机存储器的大小通常以1024（210）个存储单元为度量单位。因为1024接近于数值1000，所以计算机行业的许多人采用前缀千（kilo）来表示这个单位。也就是说，术语千字节（kilobyte，简写形式为KB）用于表示1024字节。因此有4096个存储单元的计算机被称为有4 KB存储器（4096=4×1024）。随着存储器容量的增大，又新增了一些类似的度量单位，包括MB（兆字节）、GB（吉字节）、TB（太字节）。遗憾的是，这种前缀用法属于术语的误用，因为这些前缀已经是其他领域用于指称1000的幂。例如，在度量距离时千米（kilometer）指的是1000米（m），在度量无线电频率时，兆赫（megahertz）指的是1 000 000赫兹（Hz）。在此提醒大家：一般说来，千（kilo-）、兆（mega-）等术语在涉及计算机存储器时表示2的幂，但在其他环境中表示1000的幂。 问题与练习 1. 如果地址为5的存储单元存有值8，那么在将值5写入6号存储单元和将5号存储单元的内容移到6号存储单元之间有什么差别？ 2. 假定你想交换存储在2号和3号存储单元中的值。那么下面的步骤错在哪里？ 步骤1：把2号存储单元中的内容移到3号存储单元。 步骤2：把3号存储单元中的内容移到2号存储单元。 请设计能够正确交换这两个存储单元内容的步骤。如有必要可以使用额外的存储单元。 3. 4 KB计算机存储器里有多少个二进制位？ 1.3 海量存储器 由于计算机主存储器的不稳定性和容量的限制，大多数计算机都有称为海量存储（mass storage）系统的附加存储设备，包括磁盘、CD盘、DVD盘、磁带、闪存驱动器（所有这些我们稍后会讨论）。相对于主存储器，海量存储系统的优点是更稳定、容量大、价格低，并且在许多情况下可以针对存档的需要从计算机上方便地取下这类存储设备。 术语联机（on-line）和脱机（off-line）通常分别用来描述那些既能接入计算机又能从计算机上移除的设备。联机意味着设备或信息已经与计算机连接，不需要人的干预就可以使用。脱机意味着必须先有人的干预，设备和信息才可被计算机使用——或许需要先打开这个设备，或许需要将包含该信息的介质插到某机械装置里。 海量存储系统的主要不足之处是，它们一般都需要机械运动。因为主存储器的所有工作都是由电子器件实现的，所以比起计算机主存储器来，海量存储系统的数据存取需要花费更长的时间。 1.3.1 磁学系统 很多年以来，磁技术已经占据了海量存储领域。最常见的例子便是我们今天使用的磁盘（magnetic disk），它里面是薄的、可以旋转的盘片，表面有磁介质的涂层用以存储数据（图1-9）。读写磁头安装在盘片的上面和（或）下面，当盘片旋转时，每个磁头在盘片上面或下面相对于称为磁道（track）的圆圈转动。移动磁头时，可以对各个同心的磁道进行存取。在很多情况下，一个磁盘存储系统包含若干个安装在同一根轴上的盘片，层叠在一起，盘片之间留有足够的距离，使得磁头可以在盘片之间滑动。这种情况下，所有的磁头是一起移动的。因此，每当磁头移到新的位置时，就可以访问新的一组磁道，称为柱面（cylinder）。 因为一个磁道可以包含的数据通常比我们每一次要处理的数据多，所以每个磁道又被划分成若干个小弧区，称为扇区（sector）。记录在每个扇区上的信息是连续的二进制位串。磁盘上所有的扇区包含相同数目的二进制位（典型的容量是512个字节到若干KB），而且在最简单的磁盘存储系统里，每一个磁道被分为相同数目的扇区。因此，盘片边缘磁道扇区上存储的位密度要小于靠近盘片中心磁道上存储的位，这是因为外磁道要长于内磁道。事实上，在大容量磁盘存储器系统里，边缘磁道可包含的扇区要远多于靠近中心的磁道，这种存储能力常通过一种称作ZBR（zoned-bit recording，区位记录）的技术得以应用。运用ZBR，一些相邻的磁道被统一命名为区，一个典型的盘片大约包含10个区。一个区的所有磁道有相同数目的扇区，但是靠外的区中每一个磁道包含的扇区比靠内的区包含的多。因此，盘片边缘的存储空间利用率要高了。不考虑细节，我们只需知道，一个磁盘存储系统包含许多独立的扇区，每一个扇区又可以作为独立的位串进行存取。 图1-9 磁盘存储系统 磁道和扇区的位置不是磁盘物理结构的固定部分，而是通过称为磁盘格式化（formatting）的过程磁化形成的。这个过程通常是由磁盘的厂家完成的，出厂的此类盘称为格式化盘。大多数计算机系统都能够执行此项任务。所以，如果一个磁盘的格式化信息被破坏了，那么可以重新格式化这个磁盘，不过这种操作将会扔掉原先记录在磁盘上的所有信息。 一个磁盘存储系统的容量取决于所用盘片数目以及所划分磁道与扇区的密度。较小容量的系统可能只有一个盘片。大容量磁盘系统的容量可达数GB，甚至TB，可能在同一根轴上安装有3～6个盘片。此外，数据有可能存储在每个盘片上下两面。 有几个标准可以用来评估一个磁盘系统的性能：（1）寻道时间（seek time），读写磁头从一个磁道移到另一个磁道所需要的时间；（2）旋转延迟（rotation delay）或等待时间（latency time），盘片旋转一周所需要时间的一半，也就是读写磁头到达所要求磁道后，等待盘片旋转使读写磁头位于所要存取的数据（扇区）上所需要的平均时间；（3）存取时间（access time），即寻道时间和等待时间之和；（4）传输速率（transfer rate），在磁盘上读出或写入数据的速率。需要注意的是，在区位记录存储情况下，盘片旋转一次边缘道通过读写磁头传递的数据要多于内区道，因此数据传输速率依所使用盘片部分的不同而有所变化。 限制磁盘存取时间和传输速率的一个因素是磁盘系统旋转的速度。为了支持高速旋转，这些系统里的读写磁头不接触盘片，而只是“悬浮”在盘片表面。磁头与盘片之间的空间很小，以至于一粒小小的灰尘都可能卡在其中，并因此损坏磁盘和磁头，这一现象便是磁头划伤（head crash）。因此，磁盘系统出厂时都密封在箱子里。凭借这样的构造，磁盘系统能够以每秒几千次的速度旋转，达到每秒数以MB的传输速率。 因为磁盘系统的操作需要物理运动，所以难以与电子电路的速度相比。电子电路延迟时间是以纳秒（十亿分之一秒）甚至更小计算的，而磁盘系统的寻道时间、等待时间和存取时间是以毫秒（千分之一秒）度量的。因此，与电子电路等待结果的时间相比，从磁盘系统检索信息所需要的时间非常长。 磁盘存储系统不是唯一应用磁技术的海量存储设备。一种更古老的形式是磁带（magnetic tape）（见图1-10），在这些系统里，信息存储在一条细薄的塑料带的磁涂层上，而塑料带则绕在磁带卷轴上作为存储器。为了存取数据，磁带应装到称为磁带驱动器的设备里，并可以在计算机控制下读带、写带和倒带。磁带驱动器有大有小，小至盒式机，大至比较老式的大型盘式机。盒式机又称为流式磁带机，磁带的外表与立体声收音机类似。虽然这些磁带机的存储容量依赖于所使用的格式，但是大多数都能达到几GB。 图1-10 磁带存储装置 磁带的一个主要缺点是，在磁带卷轴之间要移动的带子很长时，在一条磁带不同位置之间移动非常耗费时间。于是相对于磁盘系统而言，磁带系统的存取时间比较长，因为磁盘的读写磁头只需要做短的移动就可以在不同的扇区存取数据。因此，磁带机对于联机的数据存储不是很常用。但是，磁带技术常应用在脱机档案数据存储中，原因是它具有容量大、可靠性高和性价比好等优势，但其他技术（如DVD、闪存等）的进步，正迅速地吞噬磁带系统最后的阵地。 1.3.2 光学系统 另一类海量存储器所应用的是光学技术，CD（Compact Disk，光盘）就是其中的一种。光盘的直径为12 cm（大约5英寸），由涂着光洁保护层的反射材料制成。通过在反射层上创建偏差的方法在光盘上面记录信息。激光束通过监视CD快速旋转时反射层的不规则反射偏差来读取信息。 CD技术最初用于音频录制，使用称为CD-DA（Compact Disk-Digital Audio，数字音频光盘）的记录格式，而今天CD作为计算机的数据存储设备，实质上使用的仍是同样的格式。特别值得一提的是，CD上的信息存储在一条磁道上，它呈螺旋形缠绕在CD上，很像老式唱片里的凹槽，不过与老式唱片不同的是，CD上的磁道是由内至外的（见图1-11）。这条磁道被划分为称为扇区的单元，每个扇区都有自己的标识，数据存储容量为2 KB，相当于在音频录制时 s的音乐。 图1-11 CD存储格式 需要注意的是，盘片外部边缘的螺旋磁道距离比内部磁道距离要长。为了使CD的存储能力达到最大，信息就按照统一的线性密度存储在整个螺旋形磁道上。这就意味着，螺旋形磁道上靠外边缘的环道存放的信息比内部的环道多。所以，如果盘片旋转一整圈，激光束在扫描螺旋形磁道外面的部分时读到的扇区个数要比里面的部分多。因此，为了获得统一的数据传输速率，根据激光束在盘片上的位置，CD-DA播放器能够调整盘片的旋转速度。但是用于计算机数据存储的大多数CD系统，盘片旋转的速度是比较迅速和恒定的，因此其CD驱动器必须适应数据传输速率的变化。 由于采用这种设计思想，CD存储系统在处理长且连续的数据串（如音乐复制等）时表现最好。但是，当一个应用需要随机存取数据项时，磁盘存储器所用的方法（单个、同心磁道被划分成独立存取扇区的形式）就优于CD所用的螺旋形方法。 传统CD的存储容量是600～700 MB。但是，DVD（Digital Versatile Disk）可具有多达几个GB的存储容量，它由多个半透明的层面构成，精确聚焦的激光可以识别其不同的层面。这种盘片能够存储冗长的多媒体信息，包括完整的一部电影。最后，蓝光技术（Blu-ray technology）使用蓝色（而非红色）激光，能够极为精确地聚焦激光束。因此，BD（Blu-ray Disk，蓝光光碟）的容量是DVD的5倍多。为了满足高清视频的需要，我们需要使用这种容量很大的存储设备。 1.3.3 闪存驱动器 基于磁学和光学技术的海量存储系统的一个普遍特征是，通过物理运动来存储和读取信息，例如，旋转磁盘、移动读写磁头和扫描激光束等。这就意味着，数据存储和读取的速度比电子电路的速度要慢。闪存（flash memory）技术有潜力克服这个缺点。在一个闪存系统里，用电子信号将二进制位直接送到存储介质中，电子信号使得该介质中二氧化硅的微小晶格截获电子，从而转换微电子电路的性质。因为这些微小晶格能够保持截获的电子很多年，所以闪存技术适合存储脱机数据。 尽管存储在闪存系统里的数据能够像在RAM应用中一样，以小字节单元存取，但是现代技术规定存储的数据应批量擦除。不过反复的擦除会逐渐损坏二氧化硅的晶格，这就意味着现今的闪存技术不适合主存储器应用，主存储器的内容在一秒钟可能被改变许多次。然而，在某些应用里改变可以被控制在一个合理的水平，例如数码相机、移动电话、手持式PDA，所以闪存已经成为海量存储技术的一个选择。的确，因为闪存对物理震动不敏感（与磁学系统和光学系统不同），它在便携式应用中的潜力巨大。 闪存设备称为闪存驱动器（flash drive），容量可达到几GB，可用于一般的海量存储应用。闪存设备被封装在小的塑料格子里（长约3英寸），其一端有一个可以取下的帽，当驱动器处于脱机状态时，可以保护这个设备的电子连接器。这些便携设备容量大，很容易连接到计算机以及从计算机断开，对于脱机状态的数据存储是很理想的选择。不过，由于它们的微小存储晶格的缺点，当涉及真正长期应用时，它们不如光学盘片可靠。 闪存技术的另一应用是SD存储卡（Secure Digital memory card），简称SD卡。SD卡的容量高达2 GB，它们被制成塑料封装的晶圆，有邮票大小（事实上还有更小的小型和微型SD卡），SDHC存储卡（Secure Digital High Capacity memory card，高容量SD存储卡）的存储容量可以高达32 GB，而作为新一代SD卡的SDXC存储卡（Secure Digital Extended Capacity memory card），其容量可超过1 TB。凭借不占空间的体积，这些卡可以方便地插入小型电子设备的插槽。因此，它们是数码相机、智能手机、音乐播放器、汽车导航系统，以及其他许多电子应用的理想选择。 1.3.4 文件存储及检索 海量存储系统中的信息一般被分组为较大的单元，即文件（file）。典型的文件可能由文本文档、照片、程序、音乐录音或者一组有关公司员工的数据组成。我们已经了解到，海量存储设备规定这些文件要以较小的多字节单元进行存储和检索。例如，存储在磁盘上的文件必须按照扇区操作，每个扇区都有固定的规格。符合存储设备特性的数据块称为物理记录（physical record）。因此，海量存储系统中的大文件通常包含多个物理记录。 与这种物理记录划分相对，文件通常还有其自然划分，这由它所表示的信息决定。例如，一个包含公司员工信息的文件由许多单元组成，其中每个单元包含一个员工的信息；一个有关文本的文件包含段落或页。这些自然产生的数据块称为逻辑记录（logical record）。 逻辑记录通常由称为字段（field）的较小单元组成。例如，一个包含员工信息的逻辑记录大致由姓名、地址、员工标识号等字段组成。有时候，文件的每一个逻辑记录是由一个特定的字段唯一标识出来的（也许是一个员工的标识号、一个部门标号或者是目录项标号）。这样的标识字段称为键字段（key field），键字段中的值称为键（key）。 逻辑记录的规格很少能与海量存储系统的物理记录相匹配。因此，人们可能会发现若干逻辑记录存放在一个物理记录里，或者一个逻辑记录存放在两个或者更多的物理记录里（见图1 12）。因此，海量存储系统的信息检索需要一定的整理工作。这个问题的一个常用解决方法是，在主存储器里留出一个足够大的区域，用于存放若干物理记录并将此存储空间作为重组区域。也就是说，与物理记录兼容的数据块可以在主存储区与海量存储系统之间传输，主存储区的数据能够根据逻辑记录引用。 图1-12 磁盘上的逻辑记录与物理记录 这种存储区域称为缓冲区（buffer）。一般情况下，缓冲区是在一个设备向另一个设备传输数据的过程中临时存储数据的区域。例如，现代的打印机都有自己的存储电路，其大部分被用作缓冲区，用于保存该打印机已经收到但还没有打印的那部分文档。 问题与练习 1. 我们可以从加快磁盘或CD转速中获得什么？ 2. 当记录数据到多盘片存储系统时，我们是应该写满一张盘片后再写另一张盘片，还是应该写满一个柱面后再写另一个柱面？ 3. 为什么在一个预订系统里，那些需要经常更新的数据要存储在磁盘里，而不是CD或DVD里？ 4. 使用字处理程序修改文档时，有时添加一段文本不会很明显地增加海量存储器中文件的大小，而有时一个符号的增加就会使文件增加几百个字节。为什么？ 5. 相对于本节介绍的其他海量存储系统，闪存驱动器有什么优势？ 6. 什么是缓冲区？ 1.4 用位模式表示信息 在研究了位存储的技术后，现在来了解如何将信息编码为位模式。我们的学习集中在对文本、数字数据、图像以及声音等编码的流行方法上，其中每一个编码系统都可能会影响到典型的计算机用户。我们的目标是充分了解这些技术，以便知道应用这些技术的效果。 1.4.1 文本的表示 文本形式的信息通常由一种代码表示，其中文本中的每一个不同的符号（例如字母和标点符号等）均被赋予唯一的位模式。这样，文本就表示为一个长的位串，连续的位模式逐一表示原文本中的符号。 在20世纪的40年代～50年代，人们设计了许多这样的代码，并结合不同的设备使用，随之增加了不少通信问题。为了缓解这种情况，ANSI（American National Standards Institute，美国国家标准化学会）采用了ASCII（American Standard Code for Information Interchange，美国信息交换标准码）。这种代码使用长度为7的位模式来表示大小写英文字母、标点符号、数字0～9以及某些控制字符，如换行、回车与制表符等。今天，ASCII码被扩展为8位位模式，方法就是在每个7位位模式的最高端添加一个0。这个技术不仅使所产生的代码的位模式与字节型存储单元相匹配，而且还提供了附加的128个位模式（通过给附加的位赋予数值1），可以表示除英语字母和关联的标点符号之外的符号。 美国国家标准化学会 美国国家标准化学会（ANSI）成立于1918年，学会下属了一些工程师协会和政府机构，作为非赢利性组织来规范私人企业自发标准的开发。今天，ANSI有1300多个成员，其中包括商业组织、专业组织、行业协会以及政府代表。ANSI的总部设在纽约，它代表美国作为ISO的成员。它的网站是http:www.ansi.org。 其他国家类似的组织包括澳大利亚标准组织、加拿大标准委员会、中国国家质量技术监督局、德国标准学会、日本工业标准委员会、墨西哥标准指导委员会、俄罗斯联邦国家标准和度量委员会、瑞士标准化协会和英国标准学会。 ISO——国际标准化组织 国际标准化组织（常称为ISO）建立于1947年，是世界范围标准化实体联盟，这些实体分别来自各个国家。现如今，它的总部设在瑞士日内瓦，有100多个实体会员和许多观察会员。（观察会员也是一些国家的标准化实体，这些国家还没有全国统一的标准化实体。这些会员不能直接参与标准的开发，但可以了解ISO的活动。）ISO的网站是http:www.iso.org。 8位模式的一部分ASCII码可见附录A。利用这个附录，我们可以将位模式 01001000 01100101 01101100 01101100 01101111 00101110 解码为报文“Hello.”，见图1-13。 图1-13 报文“Hello.”的ASCII码 ISO（International Organization for Standardization，国际标准化组织，这个组织的缩写也暗指了希腊语中意味“平等”的单词“isos”）开发了大量ASCII扩展，每种扩展都是针对某一主要语种设计的。例如，其中一个标准提供了表达大部分西欧语言文本所需的符号。在其128个附加模式中有表示英磅和德语元音?、?、ü的符号。 ISO扩展的ASCII标准在支持全世界多语通信方面取得了巨大进展，但是仍有两个主要障碍。首先，扩展的ASCII中额外可用的位模式数不足以容纳许多亚洲语言和一些东欧语言的字母表。其次，因为一个特定文档只能在一个选定的标准中使用符号，所以无法支持包含不同语种的语言文本的文档。实践证明，这两者都会严重妨碍其国际化使用。为弥补这一不足，Unicode在一些主要软硬件厂商的合作下诞生了，并迅速赢得了计算机行业的支持。这种代码采用唯一的16位模式来表示每一个符号。因此，Unicode由65 536个不同的位模式组成——足以表示用中文、日文和希伯来文等语言书写的文本。 由一长串根据ASCII或Unicode编码的符号组成的文件常称为文本文件（text file）。重要的是要区别下面两类文件：一类是由称为文本编辑器（text editor，常简称为编辑器）的实用程序操作的简单文本文件；一类是由字处理程序（word processor），如微软的Word产生的较复杂的文件。两者都是由文本材料组成的，但是，文本文件只包含文本中各个字符的编码，而由字处理程序产生的文件还包含许多专用格式码，用于表示字体变化、对齐信息等。 1.4.2 数值的表示 当所记录的信息只有数值时，以字符编码的形式存储信息效率就会很低。为了了解其中的原因，让我们来看看数值25的存储问题。如果我们坚持用ASCII编码符号来存储，每个符号一个字节，那么总共需要16个二进制位。此外，用16个二进制位可以存储的最大数是99。不过，我们马上就可以看到，使用二进制记数法（binary notation），16个二进制位可以存储0～65535范围内的任何一个整数。因此，二进制记数法（或它的变体）被广泛应用于计算机存储器中数值数据的编码。 二进制记数法是一种数值表示方法，只使用数字0和1，区别于传统的使用数字0、1、2、3、4、5、6、7、8和9的十进制记数系统。我们将在1.5节中更详细地学习二进制记数法，现在只需要初步了解该系统。我们来考虑一种老式的汽车里程表，它的显示轮只包含数字0和1，而不是传统的十进制数字0～9。里程表以全0读数开始，当汽车行驶几英里时，最右方的滚动显示轮从0旋转至1；当这个1旋转回0时，就使得一个1出现在它的左边，因此产生模式10；接着右边的0旋转为1，产生11；这时，最右边的数从1旋转回0，使得它左边的1也旋转回0，这就使另一个1出现在第3位上，产生模式100。简言之，在我们驾驶汽车时将看到下列顺序的里程表读数： 0000 0001 0010 0011 0100 0101 0110 0111 1000 这个序列包括了整数0～8的二进制表示。尽管有些冗长乏味，但是我们可以扩展这种计数技术，用以发现16个1组成的位模式是可以表示数值65 535的，这就证实了我们的说法：0～65 535范围内的任何整数都可以利用16个二进制位进行编码。 由于它的高效性，数字信息通常以二进制记数法的某种形式存储，而不用符号编码。我们称其为“二进制记数法的某种形式”，这是因为上面描述的简单二进制系统只是计算机里应用的若干数值存储技术的基础。二进制系统的某些变体将在本章的后面讨论。现在我们只需要知道，称为二进制补码（two’s complement）记数法（见1.6节）的系统通常用于存储整数，因为它提供了一种便利地表示负数和正数的方法。为了表示和这样带有分数部分的数，我们还要使用一种称为浮点（floating-point）记数法的方法（见1.7节）。 1.4.3 图像的表示 通常将图像表示为一组点，每一个点称为一个像素（pixel，是picture element的缩写），每个像素的显示被编码，整个图像就表示成这些已编码像素的集合，这个集合被称为位图（bit map）。这种方法很常用，因为许多显示设备（如打印机和显示器）都是在像素的概念上进行操作的。因此，位图格式的图像更便于显示。 在位图中的像素编码方式随着应用的不同而不同。对于黑白图像，每个像素由一个位表示，位的值取决于相对应像素是黑还是白。大多数的传真机采用此方法。对于更加精致的黑白照片，每个像素由一组位（通常是8个）表示，这就使得许多灰色阴影也可以表示出来。 就彩色图像而言，每个像素通过更为复杂的系统来编码。有两种方法很常用，我们称其中一种为RGB编码，每个像素表示为3种颜色成分——红、绿、蓝，它们分别对应于光线的三原色。一个字节通常用来表示每一个颜色成分的强度。因此，要表示原始图像中的一个单独像素，就需要3个字节的存储空间。 一个较常用的可以替代简单RGB编码的方法采用一个“亮度”成分和两个颜色成分。这时候，“亮度”成分（称为像素亮度）基本上就是红、绿、蓝部分的总和。（事实上，它是像素中白光的数量，但是现在我们不需要考虑这些细节。）其他两种成分（称为蓝色度和红色度）分别取决于在像素中所计算的像素亮度与蓝或红光数量之间的差。这3个成分合起来就包括了显示像素所需的信息。 利用亮度和色度成分进行图像编码这种方式的普及源自彩色电视领域，因为这种方法提供了可以同样兼容老式黑白电视接收器的彩色图像编码方式。事实上，只需要对彩色图像的亮度成分编码就可以制造出图像的灰度形式。 位图技术的一个缺陷在于，图像不能轻易调节到任意大小。基本上，增大图像的唯一途径就是变大像素，而这会使图像呈现颗粒状。（这就是应用于数码相机的“数字变焦”技术，与此相对的“光学变焦”是通过调整相机镜头实现的。） 为了避免缩放问题，表示图像时还可以把图像表示成几何结构的集合（如直线和曲线），这些几何结构可以用解析几何技术来编码。这种描述允许最终显示图像的设备决定几何结构的显示方式，而不是让设备再现特殊像素模式。这种方法被用在当今的字处理系统中，用于产生可缩放的字体。例如，TrueType（由微软和苹果开发）是用几何结构描述文本符号的系统，而PostScript（由Adobe系统开发）提供了一种描述字符及更一般的图形数据的方法。这种表示图像的几何方法也在CAD（Computer-Aided Design，计算机辅助设计）系统中很常见，用于在计算机屏幕上显示和操控三维物体的绘制。 对使用许多绘图软件（如微软的绘图工具）的用户来说，用几何结构表示图像与用位图表示图像之间的区别是明显的，这些绘图软件支持用户绘制的图中包含预先设定的形状（如矩形、椭圆形、基本线条等）。用户仅从菜单中选择所需的几何形状，然后使用鼠标绘制这个形状。在绘制过程中，软件保存了所画形状的几何描述。当鼠标给出方向后，内部的几何表示就被修改，再转化成位图形式显示出来。这种方法方便图像的缩放和形状的改变。然而，一旦绘制过程完成，就会去除基本的几何描述，仅保存位图，这意味着再做其他修改需要经历冗长的一个像素接一个像素的修改过程。另外，一些绘图系统会将描述作为几何图形保存下来并允许在之后进行修改。有了这些系统，就可以轻松地调整图形的大小，并可按各种尺寸显示清晰图像。 1.4.4 声音的表示 为了便于计算机存储和操作，对音频信息进行编码的最常用方法是，按有规律的时间间隔对声波的振幅采样，并记录所得到的数值序列。例如，序列0、1.5、2.0、1.5、2.0、3.0、4.0、3.0、0可以表示这样一种声波，即它的振幅先增大，然后经短暂的减小，再回升至较高的幅度，接着又减回至0（见图1-14）。这种技术采用每秒8000次的采样频率，已经在远程语音电话通信中使用了许多年。通信一端的语音被编码为数字值，表示每秒8000次的声音振幅。接着将这些数值通过通信线路传输到接收端，用来重现声音。 图1-14 序列0、1.5、2.0、1.5、2.0、3.0、4.0、3.0、0所表示的声波 尽管每秒8000次的采样频率似乎是很快的速率，但它还是满足不了音乐录制的高保真。为了实现今天音乐CD重现声音的质量，我们需要采用每秒44 100次的采样频率。每次采样得到的数据以16位的形式表示出来（32位用于立体声录制）。因此，录制成立体声的每一秒音乐需要100多万个存储位。 乐器数字化接口（简称MIDI）是另外一种编码系统。它广泛应用于电子键盘的音乐合成器，用来制作视频游戏的声音以及网站的辅助音效。MIDI是在合成器上编码产生音乐的指令，而不是对音乐本身进行编码，因此它避免了采样技术那样的大存储容量要求。更精确地说，MIDI是对什么乐器演奏什么音符以及持续时间进行编码。例如，单簧管演奏D音符2秒钟，可以编码为3个字节，而不必按照每秒44 100次的采样频率用两百多万个二进制位来编码。 简言之，可以把MIDI看做是对演奏者乐谱编码的一种方法，而不是对演奏本身编码。因此，MIDI“录制”的音乐在不同合成器上演奏时声音可能是截然不同的。 问题与练习 1. 下面是ASCII编码的一条消息，每个符号8位。它的含义是什么？（见附录A。） 01000011 01101111 01101101 01110000 01110101 01110100 01100101 01110010 00100000 01010011 01100011 01101001 01100101 01101110 01100011 01100101 2. 在ASCII码中，大写字母码和相应小写字母码之间的关系是什么？（见附录A。） 3. 用ASCII对这些语句编码： a. “Stop!” Cheryl shouted. b. Does 2+3＝5? 4. 描述一种在日常生活中能够呈现两种状态的设备，例如旗杆上的旗帜，或者升起或者下降。给一种状态赋值1，另一种赋为0。然后让我们看一下，当以这样的位来存储时，字母b的ASCII码会怎样表示？ 5. 将下列二进制表示分别转化为相应的十进制形式。 a. 0101 b. 1001 c. 1011 d. 0110 e. 10000 f. 10010 6. 将下列的十进制表示分别转化为相应的二进制形式。 a. 6 b. 13 c. 11 d. 18 e. 27 f. 4 7. 如果每个数字采用每字节一个ASCII码的模式编码，那么3个字节可以表示的最大数字值是多少？如果采用二进制编码，那么又能够表示多大的数字值？ 8. 除十六进制以外，另一种表示位模式的方法是点分十进制记数法（dotted decimal notation），其中每个字节由相对应的十进制数来表示，而且这些字节表示用句点分开。例如，12.5表示0000110000000101模式（12表示00001100字节，5表示00000101字节），而136.16.7表示100010000001000000000111模式。用点分十进制记数法表示下列位模式： a. 0000111100001111 b. 001100110000000010000000 c. 0000101010100000 9. 相对于位图技术，用矢量技术表示图像有哪些优点？位图技术相对于矢量技术又有哪些优点？ 10. 假如采用文中所讨论的每秒44 100次的采样频率，给立体声录音的1小时音乐编码。请问这段音乐编码的大小与CD的存储容量相比结果如何？ *1.5 二进制系统 在1.4节中我们看到，二进制记数法是表示数字值的一种方法，仅仅利用数字0和1；不同于普遍采用的十进制记数系统，十进制系统是利用数字0～9。现在我们要比较深入地研究一下二进制记数法。 1.5.1 二进制记数法 回顾十进制系统，每一个位置的表示都与一个量值相关联。在375的表示中，5的位置与量1相关联，7与量10相关联，3与量100相关联（见图1-15a）。每一个量值是它右边量值的10倍。整个表达式代表的数值是，每一个数字值与其位置的量值相乘所得积之和。举例说明：模式375表示（3×100）+（7×10）+（5×1），用更加技术性的表示法即（3×102）+（7×101）+（5×100）。 图1-15 十进制和二进制系统 在二进制记数法中，每个数字的位置也与一个量值相关联，只是与每个位置相联系的那个量值是它右边量值的两倍。更精确地说，二进制表示中最右边的数字与量值1（20）相关联，其左边的下一个位置与量值2（21）相关联，下一个与量值4（22）相关联，再下一个与量值8（23）相关联，依次类推。例如，在二进制表示1011中，最左边1的位置与量值1相关联，接下来一个1的位置与量值2相关联，0的位置与量值4相关联，最左边1的位置与量值8相关联（见图1-15b）。 为了求得二进制表示所表示的数值，我们可以采取和十进制相同的步骤，即先求得每个数字值与其量值的积，再计算各个乘积之和。例如，100101表示的数值是37，如图1-16所示。需要注意的是，因为二进制计数法仅使用数字0和1，这种求积再求和的步骤就可以简化为求数字值为1的位置对应的量值的和。因此，二进制模式1011表示的是数值11，因为3个1的位置分别与量值1、2以及8相关联。 图1-16 二进制表示100101的解码 在1.4节中，已经学习了如何用二进制记数法计数，这就使得我们可以对小整数进行编码。为了求得大数值的二进制表示，你可能更倾向于图1-17所描述的算法。让我们利用这个算法来求数值13的二进制表示（见图1-18）。首先，将13除以2，得到商数6和余数1。因为这个商不是0，步骤2告诉我们还要在商数（6）的基础上除以2，得到新的商数3和余数0。最新的商数仍然不为0，所以再除以2，得出商数1和余数1。再一次，将最新的商数除以2，此时得到商数0和余数1。因为现在的商数是0，我们进入步骤3，从余数列中得到原数（13）的二进制表示1101。 步骤 1　将该值除以2，记下余数。 步骤 2　只要所得的商不是零，就继续将最新的商除以2，并记下余数。 步骤 3　商为0时，将余数按所记录的顺序从右到左依次排列，即得到原数的二进制表示。 图1-17 求正整数二进制表示的算法 图1-18 利用图1-17的算法求13的二进制表示 1.5.2 二进制加法 为了理解两个用二进制表示的整数的相加过程，首先让我们回顾一下用传统十进制表示的数值的相加过程。例如，考虑下面的问题： 我们先对最右列的8和7相加，得到和为15，我们把5记录在这一列的底部，进位1放到下一列中，得到： 现在我们把下一列的5和2相加，并加上进位到这一列的1，得到的和为8，我们把8记录在这一列的底部，得到： 总之，这个过程就是从右到左相加每一列中的数字，把和中的零头数字写在列的底部，把和的大数（如果有）进到下一列。 为了相加两个用二进制表示的正整数，我们遵照相同的过程，只是所有和的计算都使用图1-19中显示的加法规则，而不是你在小学所学的传统的以10为基的加法规则。例如，为了解决问题 首先相加最右边的0和1，得到1，写于该列下方。接着相加下一列的1和1，得到10。把其中的0写于该列下，并将1记在了下一列的上面。这时，加法如下： 相加下一列的1、0和0，得到1，将1写于该列下。下一列的1和1总和为10，将0写于该列下，并将1记于下一列。这时，加法如下： 下一列的1、1和1总和为11（数值3的二进制符号），将低位1写于该列下方，并将另外一个1写在了下一列的上面。把那个1与那列原本的1相加，得到10。再一次，在该列下方写下低位0，并将1写在了下一列上面。现在得到 下一列的唯一项就是1，是上一列进过来的，所以我们将其记录为答案。最终的结果是： 图1-19 二进制加法法则 1.5.3 二进制中的小数 为了扩展二进制记数法，使其包含小数数值，我们使用了小数点（radix point），其功能与十进制符号中的十进制小数点是相同的。也就是说，小数点左边的数字代表整数部分（整个部分）的数值，如同前面讨论的二进制系统那样解释，而小数点右边的数字代表数值的小数部分，解释类似其他二进制位，只是它们的位置被赋予了小数的量值。也就是说，小数点右边第一位的量值是12（2?1），下一位的量值是14（2?2），再下一位是18（2?3），依次类推。需要注意的是，这仅仅是前面所述规则的延续，即每位所被赋予的量值是它右边大小的两倍。利用这些赋予二进制位位置的量值，对包含小数点和不包括小数点的二进制表示进行解码的步骤基本是相同的。更精确地说，我们把表示中每一个位值与其对应位位置的量值相乘。举例说明，二进制记数法表示的101.101，将其解码可得，见图1-20。 图1-20 二进制表示101.101的解码 应用于十进制系统里的加法技术同样适用于二进制系统。也就是说，对两个有小数点的二进制表示的数相加，我们只需要对齐小数点，然后像从前一样应用相同的加法步骤。例如，10.011加100.11得111.001，如下所示： 问题与练习 1. 将下列每个二进制表示转换为相应的十进制形式。 a. 101010 b. 100001 c. 10111 d. 0110 e. 11111 2. 将下列每个十进制表示转换为相应的二进制形式。 a. 32 b. 64 c. 96 d. 15 e. 27 3. 将下列每个二进制表示转换为相应的十进制形式。 a. 11.01 b. 101.111 c. 10.1 d. 110.011 e. 0.101 4. 用二进制记数法表示下列数值。 a. b. c. d. e. 5. 按照二进制记数法做下列加法。 a. 11011 b. 1010.001 c. 11111 d. 111.11 + 1100 + 1.101 + 0001 + 00.01 *1.6 整数存储 数学家们长久以来就对数字记数系统很感兴趣，而且他们的许多想法已经被证明与数字电路的设计是相符的。本节，我们将研究其中两种记数系统，二进制补码记数法和余码记数法。它们都用于在计算设备中表示整数。这些系统都是基于二进制系统的，但是增加了些其他的特性，因而与计算机设计更加匹配。尽管有这么多的优点，它们还是有缺陷的。我们的目标是了解这些特性以及它们是如何影响计算机用法的。 模拟与数字 在21世纪之前，许多研究人员都在讨论数字和模拟技术的优缺点。在一个数字系统里，数值被编码成一系列数字并存储在若干存储单元中，每个单元表示一个数字。在一个模拟系统里，每个数值存储在单独的一个存储单元里，它在一个连续的范围内可以表示任何数值。 让我们利用水桶作为存储器来比较这两种方法。为了模拟一个数字系统，我们让一个空桶表示数字0，一个满桶表示数字1，然后我们就可以利用浮点记数法（见1.7节）用一排水桶存储一个数字值。相反，为了表示模拟系统，我们用水桶水位表示数字值。乍一看，模拟系统看起来更精确，因为它不会有数字系统中的截断误差（见1.7节）。不过，在模拟系统中水桶的任何移动都会使水位检测出错，而在数字系统中没有剧烈的晃动是不会区分不出水桶有水没水的。因此，数字系统不像模拟系统对错误那样敏感。由于数字系统的这种健壮性，许多原来基于模拟技术的应用（例如电话通信、视频录制和电视）都转而使用数字技术。 1.6.1 二进制补码记数法 今天计算机表示整数最普遍的系统就是二进制补码（two’s complement）记数法。这个系统采用固定数目的二进制位来表示系统中的每一个数值。在今天的设备中，应用二进制补码系统是很普遍的，其中每个数值用一个32位的模式表示。这种大系统方便表示很大范围的数字，但对于教学不是很便利。因此，学习二进制补码系统的特性时，我们将把精力集中在比较小的系统上。 图1-21列出了两种二进制补码系统——一种基于长度为3的位模式，另一种基于长度为4的位模式。这种系统是这样构成的，即先规定适当长度的一组二进制0，接着用二进制计数，直到只有一个0，其他都是1的模式形成。这些模式表示数值0, 1, 2, 3,…。表示负值的模式是这样获得的，即先规定一组适当长度的二进制1，接着按照二进制反向计数，直到只有一个1，其他都是0的模式形成。这些模式表示数值?1, ?2, ?3,…。（如果你认为利用二进制反向计数有困难，那么可以仅从表格底部，即只有一个1，其他都为0的模式开始，计数到全是1的模式。） 图1-21 二进制补码记数法系统 注意，在二进制补码系统中位模式最左边的二进制位指明所表示数值的符号。因此，最左边的位常称为符号位（sign bit）。在二进制补码系统中，符号位为1的模式表示负值，符号位为0的模式表示非负值。 在二进制补码系统中，绝对值相同的正负数值之间的模式很相近，从右向左读时，直到第一个二进制1，它们都是相同的。然后，以这个1为分界线，左面的位模式互为补码。（一个模式的补码（complement）是通过转换所有的二进制0为1，并转换所有的二进制1为0得到的模式。）例如，图1 21中的4位系统，表示2和?2的模式都是以10结束，但是表示2的模式开始为00，而表示?2的模式开始为11。观察到这一点，我们就可以得出在绝对值相同的、表示正负值的位模式之间转换的算法。我们只需要从右到左复制原始的模式直到第一个1，接着在将剩余位转换为最终位模式时，对这些剩余位取反（图1-22）。 理解了二进制补码系统的这些基本特性，也可以得出一个二进制补码表示法的解码算法。如果要解码的模式有一个符号位0，我们仅仅需要读出这个数值，就好像这个模式是一个二进制表示。例如，0110表示数值6，因为110是6的二进制表示。如果要解码的模式有一个符号位1，就知道表示的数值是负的，而我们所要做的就是找到其绝对值。为了实现这个目的，我们先要利用图1-22中“复制及取反”的步骤，然后对获得的模式进行解码，就仿佛它只是一个简单的二进制表示。例如，为了对模式1010解码，首先我们意识到，因为这个符号位是1，表示的数值就是负的。因此，我们利用“复制及取反”步骤获得了模式0110，认识到这是6的二进制表示，然后得出结论：原始的模式表示?6。 图1-22 利用二进制补码记数法用4个位对数值6编码 1. 二进制补码记数法中的加法 我们采用二进制加法中使用的算法来计算二进制补码记数法中的数值相加，只是包括答案的所有位模式长度都相同。这就意味着，在二进制补码系统的加法中，由于最后一个进位，答案左边产生的任何一个附加位都要删除。因此，“加法运算”0101和0010得出0111，0111和1011得出0010（0111+1011=10010，缩减为0010）。 根据这个理解，我们来分析一下图1 23中的3个加法问题。每一个情况，我们都把问题转化为二进制补码记数法（采用长度为4的位模式），演示先前描述过的加法过程，然后对结果进行解码，回到一般的十进制记数法。 图1-23 转换为二进制补码记数法的加法问题 注意，图1-23的第3个问题涉及正值和负值的加法，它展示了二进制补码记数法的一个主要优点：任何带符号数字组合的加法都可以利用相同的算法，于是也就可以用相同的电路。这与人们传统的计算法是截然相反的。尽管小学生先学加法，然后是减法，但是应用二进制补码记数法的计算机只需知道加法就可以了。 例如，减法问题7?5与加法问题7+（?5）是一样的。因此，如果人们命令计算机执行7（存储为0111）减5（存储为0101），那么它首先要转换5为?5（表示为1011），然后执行0111+1011的加法过程，得到代表数值2的0010，如下所示： 因此我们可以看到，当二进制补码记数法用于表示数字值时，一个加法电路与一个取负电路的组合就足以解决加法以及减法的问题了。（这些电路的图示及解释详见附录B。） 2. 溢出问题 我们在前面的例子中忽略了这样一个问题，就是在任意的一个二进制补码系统中，都有对所表示数值大小的限制。当使用4位模式二进制补码时，可以表示的最大正整数是7，最小负整数是?8。具体来说，数值9无法被表示出来，这就意味着我们不能指望得出5+4的正确答案。事实上，它的结果会为?7。这种现象称为溢出（overflow）。也就是说，溢出指的是这样一个问题，即计算得出的数值超出了可以表示的数值范围。使用二进制补码记数法时，两个正值或负值分别相加都可能会出现这种情况。无论哪种情况，检查答案的符号位就可以发现溢出的条件。如果两个正值相加的结果是负值的模式，或者两个负值相加的结果为正，那么就发生了溢出问题。 当然，使用二进制补码系统的大多数计算机的位模式都比例子中的长，因而在进行较大数值操作时不会产生溢出。今天，人们普遍使用二进制补码记数法的32位模式来存储数值，可以得到的最大正值是2 147 483 647。如果需要更大的数值，我们可以使用更长的位模式，或者改变度量单位。例如，若在解答一个问题时用英尺代替英寸，所得数值就变小了，而且也可以达到所要求的精确度。 关键问题是计算机会制造错误。因此，使用计算机的人一定要意识到可能涉及的危险。其中一个问题就是，计算机程序员和使用者会自满而导致忽视一个事实，即小数值可以累加成大数值。例如，人们过去普遍使用二进制补码记数法的16位模式表示数值，这就意味着出现大于或等于215 =32 768的数值时就会产生溢出。1989年9月19日，一家医院多年来运行良好的计算机出现了故障。仔细检查后发现，那天距1900年1月1日共32 768天，而计算机的程序正是基于那个起始日期开始计算日期的。因此，由于溢出原因，1989年9月19日的日期产生了负值——设计计算机程序时没有考虑到这种现象。 1.6.2 余码记数法 表示整数值的另外一种方法是余码记数法（excess notation）。与二进制补码记数法相同，余码记数法中的每一个数值都表示为相同长度的位模式。为了建立一个余码系统，我们首先选择所使用的模式的长度，然后根据二进制记数呈现的顺序写下那个长度的所有位模式。接着我们发现，二进制1作为其最高位的第一个模式大约就在数列的中间。我们用这个模式表示0，其前的模式就分别用于表示?1, ?2, ?3,…，其后的模式分别用于表示1, 2, 3,…。使用长度为4的模式产生的编码见图1-24。我们可以看到，模式1101表示数值5，0011表示数值?5。（注意，余码系统和二进制补码系统的区别就是符号位相反。） 图1-24表示的系统称为余8记数法。为了了解其由来，首先我们用传统二进制系统的编码翻译每一个模式，然后将其与余码记数法表示的数值进行比较。对于每一个模式，你会发现二进制解释值比余码记数法解释值都要大8。例如，模式1100用二进制记数法表示为数值12，在余码系统中则表示4；0000用二进制记数法表示为数值0，但是在余码系统中则表示为?8。与此类似，在基于长度为5的位模式的余码系统中，模式10000用于表示0而不是通常的数值16，该记数法称为余16记数法。同样，你可以证明3位余码系统应该称为余4记数法（图1-25）。 问题与练习 1. 将下面每一个二进制补码表示转换为相应的十进制形式。 a. 00011 b. 01111 c. 11100 d. 11010 e. 00000 f. 10000 2. 用8位位模式将下列每一个十进制表示转换为相应的二进制补码形式。 a. 6 b. -6 c. -17 d. 13 e. -1 f. 0 3. 假定下列位模式表示的是用二进制补码记数法存储的数值，求出每一个值的负值的二进制补码表示。 a. 00000001 b. 01010101 c. 11111100 d. 11111110 e. 00000000 f. 01111111 4. 假定一台机器用二进制补码记数法存储数值，如果机器分别采用下列长度的位模式，那么可以存储的最大数和最小数分别是什么？ a. 4 b. 6 c. 8 5. 在下列问题中，每个位模式表示一个用二进制补码存储的数值。请执行文中所述的加法过程，按照二进制补码记数法求出它们的答案。并将问题及答案转换为十进制记数法进行验证。 a. 0101 b. 0011 c. 0101 d. 1110 e. 1010 + 0010 + 0001 + 1010 + 0011 + 1110 6. 计算下列由二进制补码记数法表示的问题，但这次要观察溢出问题，并指出哪个答案因产生溢出而不正确？ a. 0100 b. 0101 c. 1010 d. 1010 e. 0111 + 0011 + 0110 + 1010 + 0111 + 0001 7. 将下列问题从十进制记数法转换为长度为4的位模式的二进制补码记数法，然后将每一个问题转换成一个相应的加法问题（如计算机的做法），然后执行加法。将求得的答案转换为十进制记数法以进行验证。 a. 6 b. 3 c. 4 d. 2 e. 1 ??1 ? 2 ? 6 ??4 ? 5 8. 在二进制补码记数法里，一个正数和一个负数相加时会产生溢出吗？请说明理由。 9. 将下面每一个余8码表示转换为相应的十进制形式（解题时不要看文中的表格）。 a. 1110 b. 0111 c. 1000 d. 0010 e. 0000 f. 1001 10. 将下列的每一个十进制表示转换为相应的余8码形式（解题时不要看文中的表格）。 a. 5 b. -5 c. 3 d. 0 e. 7 f. -8 11. 数值9可以用余8记数法表示吗？用余4记数法表示6呢？请说明理由。 *1.7 小数的存储 不同于整数存储，对于包括小数部分的数值，我们不仅要存储代表其二进制表示的0和1，还有其小数点的位置。一种流行的方法是基于科学记数法的，称为浮点（floating-point）记数法。 1.7.1 浮点记数法 让我们以只用一个字节存储的例子来解释浮点记数法。尽管计算机通常使用更长的模式，这种8位格式也可以表示实际的系统，既可以表示重要的概念，又避免了长字节的混乱。 首先我们要规定这个字节的高位端为符号位。再次说明，符号位中的二进制0代表存储的数值为非负，1代表数值为负。接着，我们将这个字节剩余的7个位分为2组，或称其为域：指数域（exponent field）和尾数域（mantissa field）。我们规定符号位右边的3个位为指数域，余下的4个位为尾数域。图1-26描述了如何拆分字节。 我们可以借助下面的例子解释这些域的含义。假如一个字节由位模式01101011组成。利用前面的形式分析这个模式，可以看出符号位是0，指数是110，尾数是1011。为了对这个字节解码，我们首先要求解它的尾数，并在它的左边放置一个小数点，于是得到 .1011 接着，我们求解指数域（110）的内容，并将其解释为一个用3位余码方法（见图1 25）存储的整数。因此，我们所举例子的指数域模式表示正数2。这就要求我们将上面所得结果的小数点向右移动2位。（负指数域就意味着向左移动小数点。）因此，我们可以得到 10.11 这就是的二进制表示。接着，我们看到例子中的符号位是0，因此表示的数值是非负。可以得出结论：字节01101011表示。如果模式是11101011（除了符号位都与之前相同），表示的数值就将为。 再看一个例子，字节00111100。求尾数后得到 .1100 然后将小数点向左移动一位。指数域（011）表示数值?1，因此得到 .01100 这表示38。因为原始模式中的符号位是0，所以存储的数值是非负。我们得出结论：模式00111100表示38。 用浮点记数法存储数值，我们要颠倒前面的过程。例如，为了对编码，我们首先要将其用二进制记数法表示，得到1.001。接着，我们要从左到右将其位模式复制到尾数域，要从二进制表示的最左边的1开始。此时，这个字节如下： 1 0 0 1 我们现在必须填充指数域。为了达到这个目的，假定尾数域的左边有一个小数点，然后规定位的数量以及小数点移动的方向，以此得到原始的二进制数字。我们在例子中可以看到，.1001中的小数点要向右移动一位才能得到1.001，指数因此为正，所以我们将101（在余4记数法中表示为正1，见图1-25）置于指数域。最后，因为存储的数值是非负的，我们用0填充符号位。完成的字节如下： 0 1 0 1 1 0 0 1 当填充尾数域时，你可能会漏掉一个微妙的细节，这个规则是从左至右复制以二进制表示的位模式，并要从最左边的1开始。为阐述清楚，让我们考虑一下存储数值的过程，它用二进制记数法表示为.011。这时，其尾数为 1 1 0 0 而不会是 0 1 1 0 这是因为我们是从二进制表示最左边的1开始填充尾数域。遵循这个规则的表示称为规范化形式（normalized form）。 使用规范化形式减少了同一数值多种表示的可能性。例如，00111100和01000110都可以解码成，但是只有第一个模式才是规范化形式。遵循规范化形式也意味着，所有非0数值的表示都会有一个以1开始的尾数。不过，数值0是一个特例，它的浮点表示就是全部为0的位模式。 1.7.2 截断误差 如果要利用1字节浮点记数法存储数值，那么让我们考虑因此会出现的恼人问题。我们首先用二进制写，得到10.101。但是，当把这个模式复制到尾数域时，我们就用尽了空间，最右边的1（表示最后的）因此丢失了（图1-27）。如果现在忽视这个问题，继续填充指数域和符号位，那么我们最后得到的位模式将为01101010，它表示的是，而不是。这个现象称为截断误差（truncation error）或舍入误差（round-off error）。这就意味着，由于尾数域空间不够大，存储的部分数值丢失了。 图1-27 数值 的编码过程 使用较长的尾数域可以减少这种误差的发生。事实上，今天生产的大多数计算机都至少采用32位存储浮点记数法表示的数值，而不是我们在本书中采用的8位。这同时使得指数域也更长。不过，即使有这样较长的格式，有时候还是需要更高的精确度。 截断误差的另外一个来源就是在十进制记数法中比较常见的一个现象，即无穷展开式问题，例如发生在我们用十进制形式表示13的时候。无论我们用多少位数字，有一些数值都不能被精确地表示出来。传统的十进制记数法与二进制记数法区别在于，二进制记数法中有无穷展开式的数值多于十进制。例如，数值110表示为二进制时为无穷展开式。想象一下，一个粗心的人用浮点记数法存储和处理美元与美分时会产生什么样的问题？尤其是，如果美元被用作度量单位，那么一角就不能被精确地存储。其中一个解决方式就是，以分为单位处理数据，这样所有的数值就都是整数，都可以用诸如二进制补码这样的方法精确存储。 单精度浮点数 1.7节介绍的浮点表示法过于简单，不能用于实际的计算机中。毕竟，在全部实际数字中，这一表示法的8位只能表示其中256个数。我们在讨论中使用了8位模式来保持示例的简单性，但依然涵盖了重要的基本概念。 今天的许多计算机都支持32位形式的单精度浮点表示法。这一格式使用1位表示符号位，用8位表示指数（使用超码表示法），用23位表示尾数。因此，单精度浮点最多有7位十进制有效数字，可以表示极大的数（数量级为1038）直至极小的数（数量级为10?37）。也就是说，给定一个十进制数，可以非常精确地存储7位十进制有效数字，但仍有可能存在少量误差）。前7位之后的数字一定会因截断误差丢失，但数字的近似值会被保留下来。另一种形式是64位的双精度浮点数，最多有15位有效数字。 截断误差和与之相关的问题是工作在数值分析领域的人们每天都很关注的问题。这个数学分支研究的是执行大规模、高精度有效计算所涉及的问题。 下面的例子可以激起任何一位数值分析家的兴趣。假设我们要应用前面定义的1字节浮点记数法来做这3个数值的加法： 如果我们按照上述顺序加数值，首先就是加上，得到，二进制表示为10.101。遗憾的是，因为这个数值不能被精确地存储（如同前面所看到的），我们第一步的结果最后被存储为（与其中一个加数相同）。下一步是把这个结果再加到最后的上。截断误差在这里再一次出现了，最后的结果是错误的。 现在让我们以相反的顺序来加这些数值：首先将加到，得到，其二进制表示为.01。因此，第一步的结果在一个字节里被存储为00111000，这是精确的。然后，我们将这个加到数列中的下一个数值，得到，我们可以将其在一个字节里精确地存储为01101011。这次的答案是正确的。 总而言之，在浮点记数法表示的数字值加法中，它们相加的顺序很重要。问题是，如果一个大数字加上一个小数字，那么小数字就可能被截断。因此，多个数值相加的一般规则是先相加小数字，这是为了将它们累计成一个大数字（通过加到更大的数值上）。这就是前面例子中反映的现象。 今天商用软件包的设计师们在这方面做得很好，他们使没有经过培训的使用者也能很好地避免这种问题的发生。在一个典型的电子制表软件系统中，除非相加的各个数值大小差别达到1016或更多，否则所得结果都是正确的。因此，如果你认为有必要对数值 10,000,000,000,000,000 加1，那么你会得到答案： 10,000,000,000,000,000 而不是： 10,000,000，000,000,001 这样的问题在一些应用中是很严重的（例如导航系统），小误差可能在加法运算中累加，最终产生严重的后果。但是，对于一般的PC使用者，大多数商用软件提供的精确度已经足够了。 问题与练习 1. 用文中所述的浮点格式对下列位模式进行解码。 a. 01001010 b. 01101101 c. 00111001 d. 11011100 e. 10101011 2. 将下列数值编码成文中所述的浮点格式。指出截断误差的出现情况。 a. b. c. d. e. 3. 根据文中所述的浮点格式，模式01001001和00111101中哪一个表示的值更大？描述一种确定哪个模式表示的值更大的简单过程。 4. 使用文中所述的浮点格式时，可以表示的最大值是什么？可以表示的最小正值是什么？ *1.8 数据压缩 为了存储和传输数据，在保留原有内容的条件下，缩小所涉及数据的大小是有益的（有时也是必须的）。完成这一过程的技术称为数据压缩（data compression）。本节，我们首先要学习普通的数据压缩方法，然后了解一些为特殊应用设计的方法。 1.8.1 通用的数据压缩技术 数据压缩方案有两类。一类是无损（lossless）的，另一类是有损（lossy）的。无损方案在压缩过程中是不丢失信息的，有损方案在压缩过程中会发生信息丢失。通常有损技术比无损技术提供更大的压缩，因此在可以忽略小错误的数据压缩中应用很广，如图像和音频压缩。 对于被压缩数据由一长串相同的数值组成的情况，普遍使用称为行程长度编码（run-length encoding）的压缩技术，这是一种无损方法。它的过程是，将一组相同的数据成分替换成一个编码，指出重复的成分以及其在序列中出现的次数。例如，指出一个位模式包括253个1，接着118个0，接着87个1，这要比实际列出458个位节省空间。 另外一个无损数据压缩技术是频率相关编码（frequency-dependent encoding），在这个系统里，用于表示数据项的位模式长度与这个项的使用频率是反相关的。这些编码是变长编码的例子，意思是项由不同长度的模式表示，而不是像Unicode等编码那样，所有符号都由16个位表示。戴维?赫夫曼的功劳是发现了一般用于开发频率相关编码的算法，人们一般称用这种方法开发的编码为赫夫曼编码（Huffman code）。因此，今天使用的大多数频率相关编码都是赫夫曼编码。 让我们看一个频率相关编码的例子，考虑一下编码英文文本的任务。在英文中，字母e、t、a和i的使用频率要大于字母z、q和x。因此，当为英文文本编码时，如果用短位模式表示前面的字母，用长位模式表示后面的字母，那么就会节省空间。结果得到这样一个编码，其对英文文本的表示要比用统一长度编码时短。 在某些情况下，压缩的数据流由各个数据单元组成，每一个数据单元与其前面一个差别很小。动画的连续帧就是一个例子。这时，使用相对编码（relative encoding），也称为差分编码（differential encoding）的技术是很有用的。这些技术记录下了连续数据单元之间的区别，而不是全部单元；也就是说，每个单元是根据其与前一个单元的关系被编码的。相对编码用无损形式和有损形式都可以完成，这取决于连续数据单元之间的差别是精确地编码还是近似地编码。 还有其他流行的基于字典编码（dictionary encoding）技术的压缩系统。这里的术语字典（dictionary）指的是一组构造块，压缩的信息通过它们建造起来，而信息本身被编码成字典的一系列参照符。我们一般认为字典编码系统是无损系统，不过在学习图像压缩时我们将看到，有时候字典条目仅仅是正确数据成分的近似值，这就使其成了有损压缩系统。 字处理系统可以使用字典编码压缩文本文件，因为为了拼写检查，一些字典已经包含在这些字处理系统中，它们是很出色的压缩字典。特别值得一提的是，一个完整的单词可以编码成字典的一个单独参考符，而不是像使用ASCII和Unicode系统那样编码成一列单独的符号。字处理系统中的一个普通字典要包括大概25 000个条目，这就意味着一个条目可以用0到24999的整数识别。这就是说，字典中一个特定条目用15位的模式就足可识别。相反，如果用到的单词包括6个字母，则它的各个符号编码在8位ASCII码中需要48位，在Unicode中需要96位。 字典编码的一个变体是自适应字典编码（adaptive dictionary encoding，也称为动态字典编码）。在自适应字典编码系统中，编码过程中字典是可以改变的。一个流行的例子是LZW编码（Lempel-Ziv-Welsh encoding，根据它的创造者Abraham Lempel、Jacob Ziv和Terry Welsh的姓氏命名）。用LZW对信息编码，人们首先用包含基础构造块的字典，信息就是用那些构造块建起来的。但是，随着人们在信息中发现更大单元，它们就被加到了字典上——意思是，这些单元未来的出现可以被编码为一个（而不是多个）字典参照符。例如，当对英文文本编码时，人们首先要用这样的字典，它要包含单独字符、数字和标点符号。但是，当信息中的单词被确认后，可以将它们加到字典中。因此，随着对信息的编码字典会逐步扩展，而随着字典的扩展，信息中更多的单词（或者是重复的单词模式）就可以编码为字典的一个参照符。 结果是，信息用一部相当大的、完全针对本信息的字典编码。但是对这条信息解码并不一定需要这个大字典，只需要原始的小字典。的确，解码过程可以与编码过程用同一个小字典。接着，随着解码进程的继续，会遇到编码过程中发现的相同单元，因此可以将它们加到字典中，作为未来编码过程的参照符。 举例说明，考虑用LZW对信息编码： xyx　xyx　xyx　xyx 首先用一个有3个条目的字典，第一个是x，第二个是y，第三个是空格。我们先将xyx编码为121，意思是这个信息的第一个模式包括第一个字典条目，接着是第二个，然后又是第一个。接着空格被编码为1213。但是因为有了一个空格，我们知道前面的字符串已经形成了一个单词，所以我们将模式xyx加到字典里作为第四个条目。依此类推，整个信息就被编码为121343434。 如果我们现在要对这条信息解码，用原始的3条目字典，我们将首先将起始的1213串解码为xyx，接下来是空格。这时我们意识到xyx串形成了一个单词，因此将其加到字典中作为第四个条目，同编码过程中所做的一样。我们接着对这个信息解码，发现信息中的4指的是这第四个新条目，将其解码为单词xyx，因此产生模式： xyx　xyx 按这种方法，我们最终把121343434串解码为： xyx　xyx　xyx　xyx 这就是原始信息。 1.8.2 图像压缩 在1.4节中，我们已经了解到如何用位图技术对图像编码。不过，得到的位图通常是非常大的。因此，人们已经为了图像表示专门开发出许多压缩方案。 一种称为GIF（是Graphic Interchange Format的缩写，一些人读作“Giff”，还有一些人读作“Jiff”）的系统是一个字典编码系统，由CompuServe公司研制开发。它处理压缩问题的方法是，将赋予一个像素颜色的数量减少到只有256个。这些颜色的每一个红—绿—蓝组合都用3个字节编码，这256个编码被存储在一个称为调色板的表格（一个字典）里。图像中的每个像素都可以用一个字节表示，它的数值指出在256个调色条目中哪一个表示像素的颜色。（回顾：一个字节能够包括256个不同位模式中的任意一个。）需要注意的是，GIF用于任意图像时都是有损压缩系统，因为调色板中的颜色不可能与原始图像的颜色一致。 通过LZW技术将这个简单的字典系统扩展为自适应字典系统，GIF可以进一步压缩。尤其是，因为在编码过程中遇到像素模式时会将其加到字典中，所以将来遇到这些模式时就可以更加高效地编码了。因此，最终的字典是由原始调色板和一组像素模式构成的。 GIF调色板中某一个颜色通常被赋予值“透明”，意思是背景色可以透过被赋予该颜色的任何一个区域表现出来。这种选择与GIF系统的相对简便性相结合，使得在简单动画应用中GIF是一个合乎逻辑的选择，这种动画应用中的多重图像必须在计算机屏幕上移动。另一方面，它只能够对256种颜色编码，这就使得它不适合需要高精确度的应用，如摄影领域。 另外一种流行的图像压缩系统是JPEG（读作“JAY-peg”）。它是由ISO中的联合图像专家组（Joint Photographic Experts Group，标准因此得名）研制开发的标准。JPEG已经被证实是压缩彩色照片的一种有效标准，并被广泛用于摄影业。事实表明，大多数数码相机都将JPEG作为它们默认的压缩技术。 JPEG标准实际上包含多种图像压缩方法，每种都有它自己的目标。在需要绝对精确的情况下，JPEG可提供无损模式。不过，相对于JPEG的其他模式，JPEG的无损模式不能形成高级别的压缩，而且JPEG的其他选择模式已经很成功，这就意味着人们很少使用其无损模式。相反，称为JPEG基线标准的选择模式（也称为JPEG的有损顺序模式）已经成为许多应用的选择标准。 使用JPEG基线标准的图像压缩有几个步骤，其中有一些是利用人眼的局限性设计的。尤其是，相对于颜色的变化，人眼对亮度的变化更为敏感。因此，我们首先看一幅用光照和色度编码的图像。第一步，在一个2×2的像素方块中求色度的平均值，这样色度信息的大小减小为，但保留了所有的原始亮度信息。结果在没有明显图像质量损失的情况下获得了很高的压缩率。 下一步是将图像拆分成8×8的像素块，然后将每一个块作为一个单元来压缩信息。这是通过一种称为离散余弦转换的数学技术实现的，我们现在不需要关心这个转换的细节。更重要的是，这种转换将原始的8×8块变成了另外一种块，其中的条目反映了原始块中像素之间如何相互联系，而并不是实际像素值。

書城介紹　 |　合作申請　|　索要書目　 |　新手入門　|　聯絡方式　 |　幫助中心　|　找書說明　 |　送貨方式　|　付款方式	台灣用户　|　香港/海外用户
megBook.com.tw
Copyright (C) 2013 - 2024 （香港）大書城有限公司　All Rights Reserved.