计算机导论图灵机模型及数据编码与运算课件

计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码内容提要内容提要2.1 2.1 概述概述2.2 2.2 图灵机图灵机2.3 2.3 数据在计算机中的表示数据在计算机中的表示内容提要2.1概述2.2图灵机2.3数据在计算机中计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2.1 2.1 概述概述图灵机模型理论是计算机学科最核心的理论之图灵机模型理论是计算机学科最核心的理论之一，它是在总结前人制造计算机思想的基础上提出一，它是在总结前人制造计算机思想的基础上提出的理论计算模型，它不仅指导了现代电子计算机的的理论计算模型，它不仅指导了现代电子计算机的设计，为计算机设计指明了方向，并且是算法分析设计，为计算机设计指明了方向，并且是算法分析和程序语言设计的基础理论。尽管如此，图灵机模和程序语言设计的基础理论。尽管如此，图灵机模型却并不复杂，也许正因为如此，才注定了其在计型却并不复杂，也许正因为如此，才注定了其在计算学科中所具有的强大生命力。掌握了图灵机理论，算学科中所具有的强大生命力。掌握了图灵机理论，等于获得了学习计算机系统知识的等于获得了学习计算机系统知识的“金钥匙金钥匙”。2.1概述图灵机模型理论是计算机学科最核计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2.2 2.2 图灵机图灵机 在第一台电子计算机ENIAC诞生的10年前即1936年，英国数学家图灵发表了题为“论可计算数及其在判定问题中的应用”OnComputerNumbersWithanApplicationtotheEntscheidungsProblem的学术论文，奠定了学术界公认的现代电子计算机的理论和模型基础。1、希尔伯特纲领、希尔伯特纲领20世纪初，逐步形成了关于数学基础研究的逻辑主义、逻辑主义、直觉主义直觉主义和形式主义形式主义三大流派。其中，形式主义流派的代表人物是数学家希尔伯特DHilbert。他在数学基础的研究中提出了一个设想，其大意是：将每一门数学的分支形式将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即化，构成形式系统或形式理论，并在以此为对象的元理论即2.2图灵机在第一台电子计算机ENIAC诞生的10计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码元数学中，证明每一个形式系统的相容性，从而导出全部元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性，数学的相容性，希尔伯特的这一设想，就是所谓的“西尔伯特纲领西尔伯特纲领”。“西尔伯特纲领”的目标，其实质就是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中，可以机械地判定任何给定命题的真伪。D DHilbert Hilbert 希尔伯特希尔伯特 元数学中，证明每一个形式系统的相容性，从而导出全部DHil计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码“西尔伯特纲领”的研究基础是逻辑和代数，主要源于19世纪英国数学家乔治英国数学家乔治布尔布尔GBoole所创立的逻辑代数体系即布尔代数。1854年，布尔在他的著作中成功地将“真”、“假”两种逻辑值和“与”、“或”、“非”3种逻辑运算归结为一种代数。这样，形式逻辑系统中的任何命题都可用数学符号表示出来，并能按照一定的规则推导出结论。尽管布尔没有将“布尔代数”与计算机联系起来，但他的工作却为现代计算机的诞生作了重要的理论准备。G GBooleBoole乔治乔治布尔布尔“西尔伯特纲领”的研究基础是逻辑和代数，主要源于19世纪G计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码希尔伯特的工作建立在布尔工作的基础上，并使其进一步具体化。希尔伯特对实现自己的纲领充满信心。然而，1931年，奥地利25岁的数理逻辑学家哥德尔KGdel提出的关于形式系统的“不完备性定理”中指出，这种形式系统是不存在的，从而宣告了著名的“西尔伯特纲领”的失败。希尔伯特纲领的失败同时也暴露了形式系统的局限性，它表明形式系统不能穷尽全部数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。希尔伯特的工作建立在布尔工作的基础上，并使其进一步具计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码“西尔伯特纲领”虽然失败了，但它仍然不失为人类抽象思维的一个伟大成果，它的历史意义是多方面的。首首先先，“西尔伯特纲领”是在保全古典数学的前提下去排除集合论悖论的，它给数学基础问题的研究带来了全新的转机。其次其次，希尔伯特纲领的提出使元数学得到了确立和发展。最后最后，对计算学科而言，最具意义的是，希尔伯特纲领的失败启发人们应避免花费大量的精力去证明那些不能判定的问题，而应把精力集中于解决具有能行性的问题。“西尔伯特纲领”虽然失败了，但它仍然不失为人类抽象计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2、图灵对计算本质的揭示、图灵对计算本质的揭示在哥德尔研究成果的影响下20世纪30年代后期，图灵AMTuring从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识。根据图灵的研究，直观地说，所谓计算就是计算者所谓计算就是计算者人人或机器或机器对一条两端可无限延长的纸带上的一串对一条两端可无限延长的纸带上的一串0和和1执行指执行指令，一步一步地改变纸带上的令，一步一步地改变纸带上的0或或1，经过有限步骤，最后得，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。到一个满足预先规定的符号串的变换过程。图灵用形式化方法成功表述可计算这一过程的本质。图灵的研究成果是哥德尔研究成果的进一步深化，该成果不仅再次表明了某些数学问题是不能用任何机械过程来解决的思想，而且还深刻揭示可计算所具有的“能行过程”的本质特征。2、图灵对计算本质的揭示计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵的描述是关于数值计算的，不过，我们知道英文字母表的字母以及汉字均可以用数来表示，因此，图灵机同样可以处理非数值计算。不仅如此，更为重要的是，由数值和非数值英文字母、汉字等组成的字符串，既可以解释成数据，又可以解释成程序，从而计算的每一过程都可以用字符串的形式进行编码，并存放在存储器中，以后使用时译码，并由处理器执行，机器码结果可以从高级符号形式即程序设计语言机械地推导出来。图灵的研究成果是：可计算性图灵可计算性可计算性图灵可计算性。在进行可计算性问题的讨论时，不可避免地要提到一个与计算具有同等地位和意义的基本概念，那就是算法。算法也称为能行图灵的描述是关于数值计算的，不过，我们知道英文计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码方法或能行过程，是对解题计算过程的精确描述，它由一组定义明确且能机械执行的规则语句、指令等组成。根据图灵的论点，可以得到这样的结论：任一过程是能行的任一过程是能行的能够具体表现在一个算法中能够具体表现在一个算法中，当且仅当它能够被一台图，当且仅当它能够被一台图灵机实现。灵机实现。图灵机等计算模型均是用来解决问题的，理论上的能行性隐含着计算模型的正确性，而实际实现中的能行性还包含时间与空间的有效性。方法或能行过程，是对解题计算过程的精确描述，它由计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码3 3、图灵机、图灵机为纪念图灵对计算机的贡献，为纪念图灵对计算机的贡献，美国计算机博物馆于美国计算机博物馆于1966年年设立了设立了“图灵奖图灵奖”计算机是使用相应的程序来完成任何设定好的任务。计算机是使用相应的程序来完成任何设定好的任务。图灵机是一种思想模型，图灵机是一种思想模型，它由三部分组成：它由三部分组成：一个控制器，一条可以无限延伸的一个控制器，一条可以无限延伸的带子和一个在带子上左右移动的读带子和一个在带子上左右移动的读写头。写头。3、图灵机为纪念图灵对计算机的贡献，计算机是使用相应的程序来计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码 根据图灵的观点可以得到这样的结论：凡是能用算凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。解决不了的问题，任何算法也解决不了。今天我们知道，图灵机与当时提出的用于解决计算问题的递归函数、演算和POST规范系统等计算模型在计算能力上是等价的。它们于20世纪30年代共同奠定了计算科学的理论基础。相比于其他几种计算模型，图灵机是从过程这一角度来刻画计图灵机是从过程这一角度来刻画计算的本质算的本质，其结构简单，操作运行规则也较少，从而为更多的人所理解。图灵机的特征图灵机的特征图灵机由一一条条两两端端可可无无限限延延长长的的带带子子、一一个个读读写写头头以及一组控制读写头工作的命令一组控制读写头工作的命令组成，如图所示。图灵机根据图灵的观点可以得到这样的结论：凡是能用算计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码的带子被划分为一系列均匀的方格。读写头可以沿带子方向左右移动，并可以在每个方格上进行读写。写在带子上的符号为一个有穷字母表：S0,S1,S2,SP。通常，可以认为这个有穷字母表仅有两个S0、S1字符，其中S0可以看作是“0”，S1可以看作是“1”，它们只是两个符号，要说有意义的话，也只有形式的意义。bb10100010bbb状态状态q q1 1读读写头写头控制器控制器的带子被划分为一系列均匀的方格。读写头可以沿带子方向左计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码由字符“0”和“1”组成的字母表可以表示任何一个数。机器的控制状态表为q1,q2,qm,。通常，将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。一个给定机器的“程序”认为是机器内的五元组qiSjSkR或L或Nql形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：个元素的含义如下：qi表示机器目前所处的状态；Sj表示机器从方格中读入的符号；Sk表示机器用来代替写入方格中的符号；R、L、N分别表示向右移一格、向左移一格、不移动；ql表示下一步机器的状态。由字符“0”和“1”组成的字母表可以表示任何一个数。计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机的工作原理图灵机的工作原理机器从给定带子上的某起始点出发，其动作完全由其初始状态及机内五元组来决定。就某种意义而言，一个机器其实就是它作用于纸带上的五元组集。一个机器计算的结果是从机器停止时带子上的信息得到的。4 4、冯、冯诺依曼型计算机诺依曼型计算机 1946年2月14日，世界上第一台数字电子计算机ENIAC在美国宾夕法尼亚大学研制成功。该机是使用电子线路来执行算术和逻辑运算以及信息存储的真正工作的计算机器，它的成功研制显示了电子线路的巨大优越性。但是，ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯诺依曼及其同事完成了关于电子计算装置逻辑结构设计的研究报告，具体 图灵机的工作原理计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码介绍了制造电子计算机和程序设计的新思想，给出了由控由控制器、运算器、存储器、输入和输出设备制器、运算器、存储器、输入和输出设备5类部件组成的，被称为冯诺依曼型计算机或存存储储程程序序式式计算机的组织结构，以及实现它们的方法，为现代计算机的研制奠定了基础，至尽为止，大多数计算机采用的仍然是冯诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯诺依曼被人们誉为“计算机器之父”。介绍了制造电子计算机和程序设计的新思想，给出了由控计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码内存储器内存储器运算器运算器外存储器外存储器输入设备输入设备输出设备输出设备控制器控制器数据信号数据信号控制信号控制信号注：注：冯冯冯冯 诺依曼型计算机的组织结构诺依曼型计算机的组织结构诺依曼型计算机的组织结构诺依曼型计算机的组织结构内存储器运算器外存储器输入设备输出设备控制器数据信号控制信号计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码John von Neumann冯冯 诺依曼诺依曼1949 EDSACEDSAC存储程序工作原理存储程序工作原理计算机的两个基本能力：一是能够存储程序，二是计算机的两个基本能力：一是能够存储程序，二是能够自动地执行程序。能够自动地执行程序。计算机是利用计算机是利用“存储器存储器”（内存）来存放所要执行（内存）来存放所要执行的程序的，而称之为的程序的，而称之为CPUCPU的部件可以依次从存储器中的部件可以依次从存储器中取出程序中的每一条指令，并加以分析和执行，直取出程序中的每一条指令，并加以分析和执行，直至完成全部指令任务为止。至完成全部指令任务为止。JohnvonNeumann1949EDSAC存储程序计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码香侬香侬香侬香侬是现代信息论的著名创始人。是现代信息论的著名创始人。1938年，香侬在发表的论文中，年，香侬在发表的论文中，首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算可首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算可以通过继电器电路来实现。以通过继电器电路来实现。阿塔纳索夫阿塔纳索夫阿塔纳索夫阿塔纳索夫提出了计算机的三条原则：提出了计算机的三条原则：1）以二进制的逻辑基础来实现数字运算，以保证）以二进制的逻辑基础来实现数字运算，以保证 精度；精度；2）利用电子技术来实现控制、逻辑运算和算术运）利用电子技术来实现控制、逻辑运算和算术运 算，以保证计算速度；算，以保证计算速度；3）采用把计算功能和二进制数更新存储功能相分）采用把计算功能和二进制数更新存储功能相分 离的结构。离的结构。Claude ShannonClaude Shannon奠定现代计算机发展的重要人物和思想奠定现代计算机发展的重要人物和思想ClaudeShannon奠定现代计算机发展的重要人物和思计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2.3 2.3 数据在计算机中的表示数据在计算机中的表示计算机中的数据和指令都是用二进制代码表示的，这是因为计算机的各组成部分是仅具有两个稳定状态的物理元件电子开关线路所组成。为此，要想深入学习计算机的各个部分，必须掌握二进制代码的有关知识。计算机中用二进制代码表示数据信息有两种方法：按“值”表示：在选定的进位制中正确地表示出数值，包括数字、符号、小数点位置及正负号等。如“9.5”可表示为二进制的“1001.1”。按“形”表示：按照一定的编码方法来表示数据。如用ASCII码 表 示“9.5”，其 形 式 为 0101101、0111001、0101110、0110101。2.3数据在计算机中的表示计算机中的数据和计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码1 1、进位制数及其相互转化、进位制数及其相互转化(一一)进位制数（进位计数制）进位制数（进位计数制）数制的定义：数制的定义：用一组固定的数字(数码符号)和一套统一的规则来表示数值的方法就叫做数制数制(numbersystem也称计数计数制制)。这一定义主要的内涵是：(1)数制的种类很多，除了十进制数，还有二十四进制(24小时为一天)，六十进制(60分为1小时，60秒为1分)，二进制(鞋、袜、筷子等两只为一双)，等等。(2)在一种数制中，只能使用一组固定的数字来表示数的大小。数字在一个数中所处的位置称为数位数位。具体使用多少个数字来表示一个数值的大小，就称为该数制的基数基数(base)。例如，十进制数(Decimal)1、进位制数及其相互转化计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码的基数是10，使用09十个数字，二进制数(Binary)的基数为2，使用0，1两个数字。在计算机文献中，十进制数是在数的末尾加字母D来标识。例如，1989D，表示十进制数1989。一般情况下，1989就是一个十进制数，不在后面加D。二进制数是在数的末尾加字母B来标识。例如，101B，表示二进制数的101，即十进制数的5。(3)在一种数制中，有一套统一的规则。N进制的规则是逢N进1，或者借1为N。权权或称位权位权，是指数位上的数字乘上一个固定的数值。十制数是逢十进一，所以对每一位数可以分别赋以位权100，101，102，。用这样的位权就能够表示十进制的数。的基数是10，使用09十个数字，二进制数(Binary)的计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码基数基数某一基数中的最大数是“基数减1”，而不是基数本身，如十进制数中的最大数为(101)9，二进制数中的最大数为(21)1；最小数均为0。数位数位、基数基数和位权位权是进位计数制中的三个要素。采用二进制记数法采用二进制记数法原因目前，在计算机内部，数据的计算和处理都采用二进制记数法，主要是由二进制数在技术操作上的可行性、可靠性、简易性以及其逻辑性所决定的。(1)可行性可行性若用十进制数，需要0，1，9等不同的10个基数，用电子技术实现这10种状态就很困难。而用二进制数，则只需0，1两个基数，要表示两个状态，这在电学技术上的基数计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码实现最为容易。例如，电灯的亮和灭，晶体管的导通和截止，等等。(2)可靠性可靠性因二进制数只要两个状态，数字转移和处理就不易出错，这样计算机工作的可靠性就高。(3)简易性简易性二进制数运算法则简单。例如，二进制的加法、积法法则都只有三个。运算法则少，使计算机运算器结构大大简化，控制也可随之简化。(4)逻辑性逻辑性由于二进制数只要0，1两个数码，可以代表逻辑代数中的“假”和“真”，这就是在计算机中使用二进制的逻辑性。实现最为容易。例如，电灯的亮和灭，晶体管的导通和截止，计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码具体分析二进制、十进制、八进制、十六进制的性质：十进制十进制DD具有十个数字符号0，1，2，3，9；逢十进一；基数为10，第i位的权为10i。举例：123.4510110221013100410-1510-2表示方法：123.4510123.45D二进制二进制BB具有两个数字符号0，1；逢二进一；基数为2，第i位的权为2i。具体分析二进制、十进制、八进制、十六进制的性质：计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码举例：101.101212202112012-102-212-3表示方法：101.1012101.101B八进制八进制QQ具有八个数字符号0，1，2，7；逢八进一；基数为8，第i位的权为8i。举例：137.43818238178048-138-2表示方法：137.438137.43Q举例：101.10121220211201计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码十六进制十六进制HH 具有十六个数字符号0，1，2，9，A，B，C，D，E，F；逢十六进一；基数为16，第i位的权为16i。举例：147B.CD16116341627161 B160C16-1D16-2表示方法：147B.CD16147B.CDH进位制数的相互转换进位制数的相互转换 1、十进制数与二进制数间的相互转换 D D B B十六进制HD计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2710？2例例1：510？22510222101227213126123021101即即510101227101101122710？2例1：510？2251计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码例例2：0.62510？20.62521.250120.50021.01即即0.625100.1012例例3：27.6251011011.1012口口 诀诀：整数部分整数部分，除2取余数，直到商为0。余数排列，由下到上；小数小数部分部分，乘2取整数，直到小数部分为0或达到所求的精确度。整数排列，由上到下。例2：0.62510？20.625计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码将二进制数的各位按权展开相加。例4：1012？101012122021120510例5：11011.1012？1011011.101212412302212112012-102-212-3270.50.12527.62510BDBD计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2、十进制与八进制间的相互转化 D Q 同与二进制间的转化类似，整数部分除以8，取余数；小数部分则乘以8，取整数。此外，我们知道，八进制的基数8正好是二进制基数的3次幂，即8123，故八进制的一位相当于二进制的三位。因此在转化时，也可以先将十进制数转化为二进制数，而后在进一步转化为八进制数。例略Q D将八进制数的各位按权展开相加。例略2、十进制与八进制间的相互转化计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码八进制与二进制的关系八进制与二进制的关系八进制八进制 对应二进制对应二进制八进制八进制对应二进制对应二进制00004100100151012010611030117111八进制与二进制的关系八进制对应二进制八进制对应二进制00计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码3、十进制数与十六进制数间的相互转化DH同与二进制间的转化类似，整数部分除以16，取余数；小数部分则乘以16，取整数。十六进制的基数16正好是二进制基数的4次幂，即16124，故十六进制的一位相当于二进制的四位。因此在转化时，也可以先将十进制数转化为二进制数，而后在进一步转化为十六进制数。例略HD将十六进制数的各位按权展开相加。例略3、十进制数与十六进制数间的相互转化计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码十六进制与二进制的关系十六进制与二进制的关系十六进制十六进制 对应二进制对应二进制 十六进制十六进制 对应二进制对应二进制 0000081000100019100120010A101030011B101140100C110050101D110160110E111070111F1111十六进制与二进制的关系十六进制对应二进制十六进制对应二计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2 2、数据的长度单位、数据的长度单位数据的长度单位有位、字节和字等。(1)(1)位位也称比特，记为bit(binarydigit的缩写)或小写b，这是最小的信息单位，是用0或1来表示的1个二进制数位。(2)(2)字节字节记为Byte或大写B，这是计算机的最小存储单元。PC机中由8个二进制位构成一个字节，从最小的00000000到最大的11111111，即一个字节可有256个值。一个字节也可以表示由8个二进制位构成的其它信息。一个字节可存放一个半角英文字符的编码(ASCII码)。两个字节可存放一个汉字编码，2、数据的长度单位计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码1个汉字至少需要两个字节或两个字符来表示。这里所说的字符是指ASCII码字符，即半角下的英文字母、数字或其它符号。位（位（BitBit）：度量数据的最小单位）：度量数据的最小单位字节（字节（ByteByte）：最常用的基本单位）：最常用的基本单位K K(KiloBytes(KiloBytes，千，千)字节字节1K=1024 byte=21K=1024 byte=21010M M（MegaBytesMegaBytes，兆）字节兆）字节1M=1024 K=21M=1024 K=22020G G（GigaBytesGigaBytes，吉）字节吉）字节1G=1024 M1G=1024 M=2=23030T T（TeraBytesTeraBytes，太）字节太）字节1T=1024 G=21T=1024 G=24040P P（PetaBytesPetaBytes，拍）字节拍）字节1T=1024 G=21T=1024 G=250501个汉字至少需要两个字节或两个字符来表示。这里所说的位（Bi计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码(3)(3)字字记为word或小写w，是计算机信息交换、加工、存储的基本单元。用二进制代码表示，一个字由一个字节或若干字节构成。它可以代表数据代码、字符代码、操作码和地址码或它们的组合。计算机的“字”用来表示数据或信息长度。3、数值的表示、数值的表示机器数 在计算机中，因为只有“0”和“1”两种形式，为了表示数的正、负号，也必须以“0”和“1”表示。通常把一个数的最最高位高位定义为符号位符号位，用0表示正，1表示负，称为数符数符；其余位仍表示数值。通常，把在机器内存放的正负号数码化正负号数码化的数成为机器数机器数，把机器外部由正负表示正负表示的数称为真值数真值数。(3)字计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码例如，若一个数占8位，真值数0101100B的机器数为10101100，存放在机器中如图示。机器数表示的范围受到字长和数据类型的限制。字长和数据机器数表示的范围受到字长和数据类型的限制。字长和数据类型确定了，机器数表示的范围也定了。类型确定了，机器数表示的范围也定了。整数和实数在机器中，难以表示小数点，故在机器中通过对小数点的位置加以规定来表示。因此，就有整数和实数区分。10101100数符数符例如，若一个数占8位，真值数0101100B的机器数1计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码1、整数 整数是没有小数部分的数，也可以认为小数点在数的最右边。整数分为带符号和不带符号两类。对带符号的整数，符号位被放在最高位。整数表示的数是精确的，但数的范围是有限的。根据存放数的字长，它们可以用8、16、32位等表示，各自表示数的范围见下表。不同位数和数的表示范围不同位数和数的表示范围二进制位数二进制位数二进制位数二进制位数 无符号整数的表示范围无符号整数的表示范围无符号整数的表示范围无符号整数的表示范围 有符号整数的表示范围有符号整数的表示范围有符号整数的表示范围有符号整数的表示范围 8 80 02552552 28 81 1 1281281271272 27 71 1 16160 065535655352 216161 1 32768327683276732767 2 215151 1 32320 02 232321 1 2 231312 231311 11、整数不同位数和数的表示范围二进制位数无符号整数的表示计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2、实数计算机处理的数值大部分是实数，即带有小数部分的数，尤其是在科学计算中。通常，为了能表示特大或特小的数，实数采用“浮点数”或称“科学表示法”表示，“浮点数”由两部分组成，即尾数和阶码。任意二进制规格化浮点数的表示形式为：Nd2pp,式中：d是尾数，前面的“”表示数符；p是阶码，前面的“”表示阶符。它在计算机内的存储形式如图示：阶阶 符符 E Ef f阶阶 码码 E E数数 符符 S Sf f尾尾 数数 S S浮点数存储格式浮点数存储格式 2、实数阶符Ef阶码E数符Sf尾数S计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码 阶码阶码通常用整数形式来表示，它指出的是小数点在数据中的位置，决定了浮点数的表示范围；尾数尾数通常用小数形式表示，给出了有效数字的位数，决定了浮点数的表示精度。所谓规格化的浮点数规格化的浮点数就是指尾数需满足条件：S1。二进制的原码、反码及补码表示 按值表示数需解决的一个问题是如何表示数的正负按值表示数需解决的一个问题是如何表示数的正负号。号。在计算机中，数的正负号是用“0”、“1”表示的。机器数在计算机时，若将符号同时和数值参加运算，则会产生错误的结果；否则要考虑计算机结果的符号问题，将增加计算机实现的难度。例如，54的结果应为1，但在阶码通常用整数形式来表示，它指出的是小数点在计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码计算机中若按照上面讲的符号和数值同时参加运算，结果为9，显然是错误的。若要考虑符号位的处理，则运算变得复杂。为了解决此类问题，在机器数中，数有三种表示法：原码primary code、反码ones complement和补码tows complement。设计算机的字长为n位，它可表示的真值xxn-2xn-3x0,其中xi0或1二进制数，则有：1、真值x xn-2xn-3x0时，原码、反码和补码完全相同，即x原x反x补0 0 xn-2xn-3x0计算机中若按照上面讲的符号和数值同时参加运算，结果计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码 2、真值x xn-2xn-3x0 时，原码、反码和补码与x的关系如下：x原1 1 xn-2 xn-3x0 x反1 x补1 (+1)从而可知，在n位的机器数中，最高位为符号位，若该位为0真值为正，该位为1则真值为负；其余的n1位为数值位，其取值为0或1。当真值为正时，原码、反码和补码的数值位完全相同；当真值为负时，原码的数值位保持真值的原样，反码的数值位为原码的各位取反，补码则是反码的最低位加1。根据以上关系，很容易实现真值与机器数之间及三种机器数之间的相互。2、真值xxn-2xn-3x0时，原码、反码计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码转换。例例1 1：已知计算机字长为：已知计算机字长为8 8位，试写出二进制数位，试写出二进制数101010101010和和101010101010在机器中表示的原码、反码及补码。在机器中表示的原码、反码及补码。首先写出它们的真值。设该机器采用定点整数表示，则真值形式如下：x0101010 y0101010真值x为正，故有 x原 x反 x x补00101010 真值y为负，有 x原10101010 x反11010101 x补11010110转换。计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码例例2 2：已知：已知101101101101，求真值，求真值x x。分析：最高位为符号位，先由x补求出x反 x反1011011101100 x补110011 从而有 y10011运算基础 计算机中的运算有两类，一是算术运算，另一类是逻辑运算。算术运算包括加、减、乘、除等四则运算。逻辑运算逻辑运算 常用的逻辑运算有逻辑乘逻辑乘“与”运算、逻辑加逻辑加“或”运算、逻逻辑辑非非“非”运算等运算，它们都是按位位进行运算的，也称逻辑操作。例2：已知101101，求真值x。计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码“与与”运算运算，“与与”AND”AND运算的规则如下：运算的规则如下：000 010 100 111式中，“”是“与”的运算符号，也可以用“”代替。“与与”运算的一般式为运算的一般式为 CAB 或 CABAB“或或”运算运算，“或或”OR”OR运算的规则如下：运算的规则如下：000 011 101 111式中，“”是“或”的运算符号，也可以用“”代替。“或或”运算的一般式为运算的一般式为 CAB 或 CAB“与”运算，计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码“非非”运算运算“非”NOT运算的规则如下：1 0式中，“”是“非”的运算符号。“非”运算的一般式为C“异或异或”运算运算“异或”EOR：Exclusive OR运算的规则如下：式中，“”是“异或”的运算符号。000=01=110=111=0“异或”运算的一般式为CAB“非”运算000=01=110=111=0“异或”运算的一计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码2 2、算术运算、算术运算二进制的四则运算二进制的四则运算按位进行运算按位进行运算 例例2 2：1110-00111110-0011？1110-00111011110110011101000001101111010111010000001101例例4 4：1000001 1011000001 101？例例1 1：1001100110001000？1001+100010001例例3 3：1101100111011001？100000110111011011101011011010002、算术运算例2：1110-0011？1110-计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码 补码加减运算补码加减运算 补码加法 设x,y为正或负整数的真值，则由补码的定 xx补补 y y补补 x+y x+y补补应用这一公式很容易实现补码的加法运算。例例1 1：设：设x x0110110,y0110110,y11110011111001。求求x xy y？解：在计算机中，真值x,y表示下列补码形式 x补0,0110110 y补1,0000111 根据式，有x+y补x补y补1，0111101 求得 xy1000011 结果正确补码加减运算计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码例例2 2：设：设x x1010011,y1010011,y01001010100101。求。求x xy y？解：x补0,1010011 y补0,0100101根据式，有x+y补x补y补0，1111000 求得 xy1111000 结果正确 例例3 3：设x x1000011,y1000011,y01000010100001。求求x xy y？x补 1,0111101+y补 1,1011111x补y补11,0011100丢失丢失即x补y补x+y补1,0011100 求得求得 x xy y1100100 1100100 结果正确结果正确 该该例例中中，因因机机器器字字长长假假定定为为8 8位位，故故xx补补yy补补 的的结结果果 中中 最最 高高 位位“1”“1”无无 法法 保保 存存，自自动动丢丢失失，计计算算机机中中 的的 实实 结结 果果 为为1,1,00111000011100。例2：设x1010011,y0100101。求xy计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码例4：设x1000101,y1100111。求xy？解：x补0,1000101 y补0,1100111 x补 y补1，0101100 即 x+y补x补y补1,0101100 求得 xy1010100 显然，该结果是错误的，因为两个正数想加，其和不可能为负数。分析如下：真值真值x x和和y y所表示的十进制数分别为所表示的十进制数分别为69691010和和 1031031010，其和为，其和为1721721010。该十进制数所对应的。该十进制数所对应的二进制数为二进制数为1010110010101100，需用，需用9 9位字长的机器数表示，位字长的机器数表示，现机器只有现机器只有8 8位字长，无法表示，称这种现象为位字长，无法表示，称这种现象为“溢出溢出overflow”overflow”。例4：设x1000101,y1100111。求x计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码 在在计计算算机机中中，一一旦旦发发生生溢溢出出，其其运运算算结结果果肯肯定定是是错错误误的，机器将进行溢出处理。的，机器将进行溢出处理。补码减法 设x，y为正或负整数的真值，则可利用下列补码关系求得xy之值。x-y x-y补补x+(-y)x+(-y)补补xx补补-y-y补补例如，设例如，设x x1010101,y1010101,y11000011100001。求求x xy y？x补0,1010101 y-1100001-y补1，0011111故得 x-yx-y补补 x+(-y)x+(-y)补补1，1110100 xy0001100在计算机中，一旦发生溢出，其运算结果肯定是错误的，机计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码字符的表示 字符包括西文字符和中文字符。字符编码的方法和简单，首先确定需要编码的字符总数，然后将每一个字符按顺序编号，编号值的大小无意义，仅作为识别与使用这些字符的依据。1、西文字符 对西文字符编码最常用的是ASCII字符编码，即American Standard Code for Information Interchange美国信息交换标准代码。ASCII是用7为二进制编码，它可以表示2即128个字符。每个字符用7位二进制码表示，其排列次序为d6d5dd3d2d1d0，d6为高位，d0为低位。字符的表示计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码B6B5B4B3B2B1B00000010100111001011101110000NULDLE空格空格0P、p0001SOHDC1！1AQaq0010STXDC2”2BRbr0011ETXDC3#3CScs0100EOTDC4$4DTdt0101ENQNAK%5EUeu0110ACKSYN&6FVfv0111BELETB7GWgw1000BSCAN（8HXhx1001HTEM）9IYiy1010LFSUB*:JZjz1011VTESC+;Kk1100FFFS,Nn1111SIUS/?O_oDELB6B5B4000001计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码 在ASCII码表中，十进制码值032和127NULSP和DEL共34个字符称为非图形字符又称为控制字符其余94个字符称为图形字符又称为普通字符。在这些字符中，从“0”“9”、从“A”“Z”、从“a”“z”都是顺序排列的，且小写比大写字母码值大小写比大写字母码值大3232，即位值，即位值d d5 5为为0 0或或1 1，这有利于大、小写字母之间的编码转换。计算机的内部存储与操作常以字节为单位，即8个二进制位为单位。因此，一个字符在计算机内实际是用8位表示。正常情况下，最高位d7为“0”。在需要奇偶校验时，这一位可用于存放奇偶校验的值，此时称这一位为校验位校验位。在ASCII码表中，十进制码值032和127N计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码 西文字符除了常用的ASCII编码外，还有另一种EBCDIC码。这种字符编码主要用在大型机器中。EBCDIC代码，即Extended Binary Coded Decimal Interchange Code扩展的二十进制交换码。EBCDIC码采用8位二进制码表示，有256个编码状态，但只选用其中一部分。1、汉字编码 英文是拼音文字，采用不超过128种字符的字符集就满足英文处理的需要，编码容易，而且在一个计算机系统中，输入、内部处理和存储都可以使用同一编码一般为ASCII码。汉字是象形文字，种类繁多，编码比较困难，而且在一个汉字处理系统中，输入、内部处理、输出对汉字编码的要求不尽相同。因此进行一系列的汉西文字符除了常用的ASCII编码外，还有另一种计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码字编码转换，用户用输入码输入码输入汉字，系统由输入码找到相应的内码，内码内码是计算机内部对汉字的表示，要在显示器上显示或在打印机上打印出用户所输入的汉字，需要汉字的字形码字形码，系统由内码找到相应的字形码。全称是GB231280信息交换用汉字编码字符集基本集，1980年发布，是中文信息处理的国家标准，也称汉字交字交换码，简称称GBGB码。一个国标码占两个字节一个国标码占两个字节,每个字每个字节节最最高高位位仍仍为为“0”“0”；英文字符的机内码是7位ASCII码，最高位也是“0”。因为西文字符和汉字都是字符，为了在计算机内部能够区分是汉字编码还是ASCII码，将国标码的将国标码的每每个个字字节节的的最最高高位位由由“0”“0”变变为为“1”“1”，变变换换后后的的国国标标码码称称为为汉汉字机内码。字机内码。由此可知汉字机内码的每个字节都大于128，字编码转换，用户用输入码输入汉字，系统由输入码找计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码而每个西文字符的ASCII码值均小于128。汉字字输入入码是一种用计算机标准键盘上按键的不同排列组合来对汉字的输入设计的编码，目的是进行汉字的输入，那么对于输入码，要求编码要尽可能的短，从而输入时击键的次数就比较少；另外重码要尽量少，这样输入时就可以基本上实现盲打；再者，输入编码还要容易学容易上手，以便推广。为了汉字的输出显示和打印，需要描述汉字的字形，即对汉字的字形进行编码，称为汉字的字形字的字形码，也称为汉字字模。汉字字形字字形码通常有两种表示方式：点通常有两种表示方式：点阵方式和矢量方式。方式和矢量方式。用点阵表示字形时，汉字字形码指的就是这个汉字字形点阵的代码。点阵规模越大，字形就越美观，同时其编码也就越长，所需的存储空间也就越大。矢量表示方式存储的是 而每个西文字符的ASCII码值均小于128。汉字输入码是一计算机导论计算机导论计算机导论计算机导论第第第第2 2 2 2章章章章 图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码图灵机模型及数据编码描述汉字字形的轮廓特征，当要输出汉字时，通过计算机的计算，由汉字字形描述生成所需要大小和形状的汉字点阵。二者的区别在于：前者编码、存储方式简单、无需转换直接输出，但字形放大后产生效果差，而且同一种字体不同的点阵需要不同的字库。矢量方式特点正好与前者相反。描述汉字字形的轮廓特征，当要输出汉字时，通过计算机