信息表示与逻辑基础.ppt

共70页,1,Chapter 2 信息表示和数字逻辑基础,浙江大学计算学院 基础教学中心 2019年7月14日,共70页,2,Overview,理解数据表示 数制 数制转换 计算机中的数 另一种形式：码和编码 逻辑代数基础 逻辑电路 * 逻辑设计基础 *,共70页,3,2.1 理解数据表示,信息（Information）数据按有意义的关联拓扑结构的结果，信息来源于数据 应用层：数据表达的结论 技术层：数据表达的形式 数据Data 基本形式有数字、文字、图像、图形和音频和视频等 多媒体（Multimedia） 数据的类型广义、狭义数据类型 基本的数据 数学运算的“数制” 表示不同对象属性的“码制”,共70页,4,2.2 数制,数制（Number System） ：全称为记数（计数）体制 顺序记数，例如： 567. 1 多项式记数，例如：5102+6101+7100 +110-1,一般表达式： n：整数位；m：小数位； A：数码 0，1， N-1； R 为基数；Ri 权系数,共70页,5,1. 十进制 （Decimal）,数码 1、2、 、9、0 逢十进一：进位 人类生活环境常用的数制 十进制：货币，长度，重量，体积等 12/24进制：时间,共70页,6,二进制的数码：0、1， 逢二进一 特点： 只有 0 和 1 两个数码 基数为2，权系数2的整数次幂 容易用物理状态表示计算机的数制基础 二进制加法和乘法运算规则： 000 011 101 1110 000 010 100 111,2二进制 （Binary）,共70页,7,3八进制与十六进制,八进制 （Octor） 数码： 0、1、2、3、4、5、6、7，逢八进一 23=8：3位二进制=1位八进制 十六进制 Hexadecimal（中国传统衡器16进制） 数码 0、1、 9和A、B、C、D、E、F； 其中 A F：对应十进制的 10 11 12 13 14 15 逢十六进一 24=16：4位二进制=1位十六进制,共70页,8,常用数制,各种常用数制 (1) 二进制：0、1 逢二进一 (2) 十进制：0、1，9 逢十进一 (3) 八进制：0、1，7 逢八进一 (4) 十六进制： 逢十六进一 0、19、 A、B F （a、b f）,Back Overview,共70页,9,常用数制及转换（cont）,共70页,10,2.3 数制转换（cont）,二进制十进制 求幂相加展开多项式 例2.3 把二进制数 1101.01转换为十进制数 1101.01 2 = 123+122+021+120+02-1+12-2 = 8 + 4 + 0 + 1 + 0 + 0.25 = 13.25 10,共70页,11,数制转换（cont）,十进制二进制： 整数部分：除2取余,例2.4 将十进制数173转换为二进制。 将173用2进行连续整除 初等数学中的短除法,共70页,12,共70页,13,数制转换（cont）,十进制二进制小数部分：乘2取整,共70页,14,数制转换（cont）,十进制二进制157. 87=？b,157.87= 10010101.1110000,0.87=0.5+0.25+0.125+0.00390625+=0.11100001,共70页,15,数制转换（cont）,八进制 二进制 1 位八进制对应 3 位二进制 7 3 6 . 2 5 111 011 110 . 010 101 1100 . 0101 001 100 . 010 100 1 4 . 2 4,共70页,16,数制转换（cont）,十六进制 二进制 1 位十六进制 对应 4 位二进制 A 3 F . 2 B 1010 0011 1111 . 0010 1011,共70页,17,数制转换（cont）,十六进制 八进制 十六进制 二进制 八进制 十进制八进制 十进制二进制八进制 十进制十六进制 十进制二进制十六进制,共70页,18,数制转换（cont）,八进制十进制（求幂相加法） (1011)8=83+ 81+ 80=512+8+1=521 十六进制十进制（求幂相加法） (1011)16=163+ 161+ 160=4096+16+1=4113,共70页,19,数制转换小结,主要在十进制和二进制之间 二进制(八进制、十六进制)十进制 :求幂相加法 十进制二进制(八进制、十六进制) 整数部分: 除2(8、16)取余 小数部分: 乘2(8、16)取整 八进制二进制: 1位八进制对应3位二进制 十六进制二进制: 1位十六进制对应4位二进制 十六进制 二进制 八进制,共70页,20,数制转换使用Windows工具,Windows程序 附件计算器 菜单查看科学型 进制转换,Back Overview,共70页,21,2.4 计算机中的数,计算机采取一种约定的方法解决数的正或负问题 在数的前面增加一位符号位 用“0”表示正数，“1”表示负数 例如：+ 1011 写作 01011 - 1011 写作 11011 用0或1表示正负号的数计算机的“机器数” 对应的实际数值叫做机器数的“真值”尾数 根据对数的不同运算采用不同的编码方法 主要有原码、补码和反码三种,共70页,22,1原码,一个正数的原码和它的真值相同，符号位为0 负数的原码为这个数真值的绝对值，符号位为1 原码进行乘法运算 注意：计算机中使用定长格式的数据,共70页,23,2反码,反码 正数的反码与原码相同 负数的反码为对该数的原码除符号位外各位取反 例如，16位有符号数661： 0000 0010 1001 0101 = +661 反码 1111 1101 0110 1010 = -661 特点：一个数的反码和这个数的原数相加，其结果为所有位都是1,共70页,24,3补码,正数的补码与原码相同 负数的补码为对该数的原码除负号位外各位取反，然后在最后一位加1 0 000001010010101 = +661 -661 取补，先取反 1 111110101101010 再+1 1 111110101101011 （符号位保持不变，如果最高位进位则丢失） 补码的补码将还原为原码,共70页,25,补码进行加法运算,Example For： 十进制的a=11和b=-10，设5位二进制（带符号） a补= a原= 01011 b原=11010，b反=10101，b补= 1 0110 使用补码计算a和b之和,共70页,26,计算机中的数（cont）,求反码和补码与二进制数的位数有关 0 000001010010101 = +661 -661 取反 1 111110101101010 计算机中一般采用16位或32位及64位,共70页,27,2.4.2 定点数和浮点数,考虑数在计算机中的表示有以下几个因素 要表示的数的类型(小数、整数、实数等) 可能的数值范围：确定存储、处理能力 数值精确度：与处理能力相关 数据存储和处理所需要的硬件代价等 一般计算机中的数有两种常用表示格式：定点、浮点,共70页,28,定点数,定点格式数值范围有限：定长，16或32位 小数点固定在某一个位置 为了处理方便定点纯小数和定点纯整数,共70页,29,1定点纯小数,数的范围：（m+1）位定点小数格式的数N： N 1 2-m 比例因子 绝对值大于1，使用定点小数格式将产生“溢出（Overflow）” 比例因子原数据按比例缩小，计算结果再按该比例扩大得到实际的结果,小数点固定在数值部分最高位的左边,共70页,30,2定点纯整数,小数点固定在数值部分最低位的右边,数的范围：（m+1）位定点整数格式的数N N 2m 1 绝对值大于该范围的数，使用比例因子调整,共70页,31,3浮点数,小数点浮动科学计数法(指数) 123. 4567 = 0.1234567 103 容许的数值范围很大，硬件复杂 浮点数分为阶码和尾数两部分 阶码：表示小数点在该数中的位置，带符号整数 尾数：表示数的有效数值，可用整数或纯小数,Back Overview,共70页,32,2.5 另一种形式：码和编码,编码：用数码对非数值内容进行编号 编码的目的之一是为了标记特定的对象 数字、字母、符号 设计编码时需要按照一定的规则 就叫做“码制” （Code System） n位二进制可对2n个不同对象进行编码 二十进制码、ASCII码、汉字编码,共70页,33,2.5.1 ASCII,计算机在程序、系统之间需要进行数据交换 基本要求：双方使用相同的数据格式，统一编码 使用最广的字符集编码为ASCII码（American Standard Code for Information Interchange） 美国国家标准局(ANSI)制定，并被确定为ISO 646 ASCII码适用于所有拉丁文字字母 ASCII码有两种形式：7位码和8位码 7位ASCII码：标准单字节字符编码基于文本数据 8位扩展 ASCII 码第 8 位用于确定附加的 128 个特殊符号字符、外来语字母和图形符号（参见本书附录）,共70页,34,共70页,35,共70页,36,汉字编码 cont,在汉字系统中，每个汉字对应两个英文字符宽度 在汉字的存储、输入和输出中，处理的并不是汉字本身，而是汉字的编码 不同的环境下有不同的汉字编码 汉字交换码(国标码) 汉字机内码 汉字输入码。,共70页,37,2.5.2 Unicode编码,最初是Apple公司制定的通用多文种字符集 后被 Unicode 协会开发为能表示几乎世界上所有书写语言的字符编码标准 Unicode 字符清单有多种代表形式，包括 UTF-8，UTF-16 和 UTF-32，分别指使用8位、16位或32位表示字符 英文版Windows使用8位ASCII码或Unicode-8，中文版的Windows使用支持汉字系统的Unicode-16,共70页,38,2.5.3 汉字编码 cont,1 0111100 1 1001110,由输入法程序将输入码转换为交换码,由应用程序（如word）将机内码转换为字型码,0 0111100 01001110,由操作系统将交换码转换为机内码,共70页,39,汉字的存储与字库,为了输出汉字，必须存储汉字的字型 (1) 矢量化它由一组指令来描述字符的外形（轮廓）轮廓字体（TrueType） (2) 点阵图形将汉字分解为若干个“点”组成的点阵字型方式,存储每个汉字的字型信息需要1616个二进制位，共2*16 = 32字节。,共70页,41,2.5.3 汉字编码 cont,汉字编码字符集基本集-GB 2312-80 汉字字型信息的集合两级字库(国标) 第一级为常用汉字，共3755个 第二级为次常用汉字，共3008个 GB18030-2000信息交换用汉字编码字符集基本集的扩充GBK 收录了27484个汉字 总编码空间超过150万个码位信息平台基础 “微软拼音”和“全拼”输入法支持“GBK”字符集,共70页,42,*2.6 逻辑代数基础,使用二进制表示数有“大”、“小”之分 编码是用数字组合表示字符适应计算机处理数字量以外的大量的其他信息的需要 用二进制表示逻辑状态，以数学方法描述逻辑问题 用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑符号逻辑,共70页,43,2.6.1 什么是逻辑,逻辑（Logic） 探索、阐述和确立有效推理原则的学科亚里士多德创建 数理逻辑最基本的、最重要的两个组成部分命题演算，谓词演算 命题：一个有具体意义且能够判断真假的陈述句 命题演算命题如何通过一些逻辑连接词构成复合命题以及逻辑推理的方法,共70页,44,2.6.1 什么是逻辑（cont）,命题 原子命题：不能分解为更为简单的命题 复合命题：原子命题用连接词和标点符号构成 命题演算中的基本逻辑连接词 “与”、“或”、“非” 命题演算得到的值为真值 “真”（true，T） “假”（false, F）,共70页,45,2.6.1 什么是逻辑（cont）,可用实例来说明这些概念 中华人民共和国的法定货币是人民币 简单的陈述句命题，可判断其真假该命题为“真” 如果明天下雨，校运动会将推迟进行 这是复合命题,共70页,46,2.6.2 基本逻辑关系,基本逻辑连接词为“与”、“或”、“非” 用来描述逻辑关系的方法 文氏图（Venn）、真值表、逻辑代数式等 逻辑关系可以被解释为因果关系 “因”是条件 条件之间的关系用逻辑连接词进行组合 根据不同的条件得到“结果”,共70页,47,1 “与”关系,“与”(AND)是一种“交”(Intersection)关系 命题A和命题B的“与”符号表示 ：AB 当A和B同时为真时AB为真，否则为假。 AB的真值表：变量和逻辑关系的取值列表,共70页,48,2. 逻辑“或”关系,逻辑 “或” （并, Union）（，OR） 命题A和命题B的“或” ：AB 当且仅当A和B同时为假时AB为假 真值表：,共70页,49,3. 逻辑“非”关系,逻辑 “非”（NOT） 若A为真则“A非”为假；若A为假则“A非”为真 真值表,共70页,50,4逻辑代数异或,逻辑“异或”（） 命题A和命题B的“异或” ：A B 当且仅当A和B不相同时为真两者不可兼得 真值表,共70页,51,2.6.3 逻辑代数,用数学方法描述、求解逻辑问题 命题逻辑注重于关系的研究，逻辑代数则侧重于关系的实现 数字电路也称为逻辑电路，两态器件表示二进制的两个状态 命题逻辑值“T”逻辑代数中的“1”，“F”作为“0”逻辑命题的对应关系反映到代数方法中逻辑代数 开关的闭合逻辑状态“1”，断开表示“0”； 电路输出电压高于某个值“1”，低于某个电压的值“0”,共70页,52,逻辑代数 cont,用数学符号表示逻辑关系 逻辑“与”也叫做逻辑“乘”符号“”表示或省略（类似于数学中的乘法表示） AB可表示为AB或直接记为 AB。 逻辑“或”也叫逻辑“加”，用“+”表示 A B可以表示为 A+B。 逻辑“非”也叫逻辑“反”，逻辑“非”求反运算 逻辑命题真值表中的T和F分别用 1 和 0 代替逻辑代数真值表,共70页,53,逻辑命题真值表,逻辑代数真值表,共70页,54,*2.7 逻辑电路,模拟信号（Analog）和离散（Disperse）信号 离散信号数字信号 大小和增减变化都是某一个最小数量的整数倍 处理离散信号的电路就叫做数字电路也叫做逻辑电路计算机的实现基础 逻辑电路实现的是逻辑关系 可以用逻辑电路描述逻辑代数,共70页,55,*2.7 逻辑电路 cont,逻辑电路只关心电路的状态 实现基本逻辑关系的电路门电路(Gate) 晶体管非门电路逻辑电路的电特性,共70页,56,逻辑电路 cont,逻辑电路构成的系统叫做“数字系统”（Digital System） 在数字系统中高电平为1，低电平为0“正逻辑”，反之为“负逻辑”。一般以正逻辑为主,这些逻辑电路模块早在60年代就被制作成小规模的集成电路,共70页,57,1. 基本门电路,用基本门电路可以组合成多种复合门电路,（a）与门 F=AB （b）或门 F = A+B （c）非门 F =,共70页,58,2. 与非门,共70页,59,3.或非门,共70页,60,4. 异或门,图 2.13 使用基本门组合而成的异或门,共70页,61,*2.8 逻辑设计基础,按照给出的具体问题通过真值表逻辑表达式化简最简或最优逻辑电路 计算机大多数部件包括CPU，都由门电路设计组合成的数字集成电路,共70页,62,2.8.1 设计加法器,加法器 逻辑器件实现加法运算的电路,设A、B分别为一位二进制 S为A、B之和，C为A加B产生的进位，真值表,共70页,63,图2.14 一位二进制加法器,共70页,64,2.8.2 半加器/全加器,半加器