第11章 逻辑代数基础

第11章逻辑代数基础 第一章逻辑代数基础 本章知识要点 数字系统的基本概念 常用计数制及其转换 带符号二进制数的代码表示 常用的几种编码 逻辑代数的基本定律 逻辑函数的化简 代数法 卡诺图法 11 1概述 11 1 1数字系统什么是数字系统 数字系统是一个能对数字信号进行加工 传递和存储的实体 它由实现各种功能的数字逻辑电路相互连接而成 例如 数字计算机 第一章基本知识一 数字信号若信号的变化在时间上和数值上都是离散的 或者说断续的 则称为离散信号 离散信号的变化可以用不同的数字反映 所以又称为数字信号 简称为数字量 例如 学生成绩记录 工厂产品统计 电路开关的状态等 数字系统中处理的是数字信号 当数字系统要与模拟信号发生联系时 必须经过模 数 A D 转换和数 模 D A 转换电路 对信号类型进行变换 例如 某控制系统框图如下图所示 二 数字逻辑电路用来处理数字信号的电子线路称为数字电路 由于数字电路的各种功能是通过逻辑运算和逻辑判断来实现的 所以数字电路又称为数字逻辑电路或者逻辑电路 数字逻辑电路具有如下特点 1电路的基本工作信号是二值信号 它表现为电路中电压的 高 或 低 开关的 接通 或 断开 晶体管的 导通 或 截止 等两种稳定的物理状态 2电路中的半导体器件一般都工作在开 关状态 对电路进行研究时 主要关心输出和输入之间的逻辑关系 3电路结构简单 功耗低 便于集成制造和系列化生产 产品价格低廉 使用方便 通用性好 4由数字逻辑电路构成的数字系统工作速度快 精度高 功能强 可靠性好 由于数字逻辑电路具有上述特点 所以 数字逻辑电路的应用十分广泛 随着半导体技术和工艺的发展 出现了数字集成电路 集成电路发展十分迅速 数字集成电路按照集成度的高低可分为小规模 SSI 中规模 MSI 大规模 LSI 和超大规模 VLSI 几种类型 三 数字计算机及其发展1 数字计算机数字计算机是一种能够自动 高速 精确地完成数值计算 数据加工和控制 管理等功能的数字系统 其结构框图如图所示 2 计算机的发展数字计算机从1946年问世以来 其发展速度是惊人的 根据组成计算机的主要元器件的不同 至今已经历了四代 具体见下表 计算机的发展趋势 速度 功能 可靠性 体积 价格 功耗 伴随着微电子技术的飞速发展 进一步加速了计算机的发展与普及 目前广泛使用的微型计算机就是建立在超大规模集成电路基础之上的 以个人计算机为例 PC机CPU芯片80 86的集成规模如下表所示 在80586CPU中 密集程度如何呢 大约用500个晶体管串接起来才能绕人的头发丝一周 全球最大计算机芯片生产商英特尔公司 已制造出一种比市面上现有最高速处理器快十倍的处理器 这种处理器芯片上的晶体管 厚度只有零点零三微米 相当于只有三个原子的大小 市面现有芯片所使用的最小晶体管 尺寸为零点一八微米 英特尔新芯片的晶体管则小很多 这些晶体管一个接着一个排列 要超过十万个才能达到一张普通纸张的厚度 11 1 2数字逻辑电路的类型和研究方法 一 数字逻辑电路的类型根据一个电路有无记忆功能 可将数字逻辑电路分为组合逻辑电路和时序逻辑电路两种类型 组合逻辑电路 如果一个逻辑电路在任何时刻的稳定输出仅取决于该时刻的输入 而与电路过去的输入无关 则称为组合逻辑 CombinationalLogic 电路 由于这类电路的输出与过去的输入信号无关 所以不需要有记忆功能 例如 一个 多数表决器 表决的结果仅取决于参予表决的成员当时的态度是 赞成 还是 反对 因此属于组合电路 时序逻辑电路 如果一个逻辑电路在任何时刻的稳定输出不仅取决于该时刻的输入 而且与过去的输入相关 则称为时序逻辑 SequentialLogic 电路 由于这类电路的输出与过去的输入相关 所以要有记忆功能 要用电路中记忆元件的状态来反映过去的输入信号 例如 一个统计串行输入脉冲信号个数的计数器 它的输出结果不仅与当时的输入脉冲相关 还与前面收到的脉冲个数相关 因此 计数器是一个时序逻辑电路 时序逻辑电路按照是否有统一的时钟信号进行同步 又可进一步分为同步时序逻辑电路和异步时序逻辑电路 二 数字逻辑电路的研究方法 对数字系统中逻辑电路的研究有两个主要任务 一是分析 二是设计 对一个现成的数字逻辑电路 研究它的工作性能和逻辑功能称为分析 根据提出的逻辑功能 在给定条件下构造出实现预定功能的逻辑电路称为逻辑设计 或者逻辑综合 逻辑电路分析与设计的方法随着集成电路的迅速发展在不断发生变化 最成熟的方法是传统的方法 1 逻辑电路分析和设计的传统方法传统方法 传统方法是建立在小规模集成电路基础之上的 它以技术经济指标作为评价一个设计方案优劣的主要性能指标 设计时追求的是如何使一个电路达到最简 如何达到最简呢 在组合逻辑电路设计时 通过逻辑函数化简 尽可能使电路中的逻辑门和连线数目达到最少 而在时序逻辑电路设计时 则通过状态化简和逻辑函数化简 尽可能使电路中的触发器 逻辑门和连线数目达到最少 注意 一个最简的方案并不等于一个最佳的方案 最佳方案应满足全面的性能指标和实际应用要求 所以 在用传统方法求出一个实现预定功能的最简结构之后 往往要根据实际情况进行相应调整 随着集成电路技术的飞跃发展 数字逻辑电路的分析和设计方法在不断发生变化 但用逻辑代数作为基本理论的传统方法始终逻辑电路分析和设计的基本方法 2 用中 大规模集成组件进行逻辑设计的方法由于中 大规模集成电路的不断发展 使芯片内部容纳的逻辑器件越来越多 因而 实现某种逻辑功能所需要的门和触发器数量已不再成为影响经济指标的突出问题 用中 大规模集成组件去构造满足各种功能的逻辑电路时 如何寻求经济合理的方案呢 要求设计人员必须注意 充分了解各种器件的逻辑结构和外部特性 做到合理选择器件 充分利用每一个已选器件的功能 用灵活多变的方法完成各类电路或功能模块的设计 尽可能减少芯片之间的相互连线 3 用可编程逻辑器件 PLD 进行逻辑设计的方法各类可编程逻辑器件 PLD 的出现 给逻辑设计带来了一种全新的方法 人们不再用常规硬线连接的方法去构造电路 而是借助丰富的计算机软件对器件进行编程烧录来实现各种逻辑功能 这给逻辑设计带来了极大的方便 4 用计算机进行辅助逻辑设计的方法面对日益复杂的集成电路芯片设计和数字系统设计 人们不得不越来越多地借助计算机进行辅助逻辑设计 目前 已有各种设计数字系统的软件在市场上出售 计算机辅助逻辑设计方法正在不断推广和应用 不少人认为计算机设计自动化已形成计算机科学中的一个独立的学科 11 2数制及其转换 编码 11 2 1进位计数制数制是人们对数量计数的一种统计规律 日常生活中广泛使用的是十进制 而数字系统中使用的是二进制 十进制中采用了0 1 9共十个基本数字符号 进位规律是 逢十进一 当用若干个数字符号并在一起表示一个数时 处在不同位置的数字符号 其值的含意不同 同一个字符6从左到右所代表的值依次为600 60 6 二 R进制广义地说 一种进位计数制包含着基数和位权两个基本的因素 基数 指计数制中所用到的数字符号的个数 在基数为R计数制中 包含0 1 R 1共R个数字符号 进位规律是 逢R进一 称为R进位计数制 简称R进制 位权 是指在一种进位计数制表示的数中 用来表明不同数位上数值大小的一个固定常数 不同数位有不同的位权 某一个数位的数值等于这一位的数字符号乘上与该位对应的位权 R进制数的位权是R的整数次幂 例如 十进制数的位权是10的整数次幂 其个位的位权是100 十位的位权是101 一个R进制数N可以有两种表示方法 1 并列表示法 又称位置计数法 其表达式为 N R Kn 1Kn 2 K1K0 K 1 K m R 2 多项式表示法 又称按权展开法 其表达式为 N R Kn 1 Rn 1 Kn 2 Rn 2 K1 R1 K0 R0 K 1 R 1 K m R m Ki Ri其中 R表示基数 n为整数部分的位数 m为小数部分的位数 Ki为R进制中的一个数字符号 其取值范围为0 Ki R 1 m i n 1 可归纳注意 R进制的特点如下 有0 1 R 1共R个数字符号 逢R进一 10 表示R 位权是R的整数次幂 第i位的位权Ri 一 二进制基数R 2的进位计数制称为二进制 二进制数中只有0和1两个基本数字符号 进位规律是 逢二进一 二进制数的位权是2的整数次幂 任意一个二进制数N可以表示成 N 2 Kn 1Kn 2 K1K0 K 1 K m 2 Kn 1 2n 1 Kn 2 2n 2 K1 21 K0 20 K 1 2 1 K m 2 m Ki 2i其中 n为整数位数 m为小数位数 Ki为0或者1 m i n 1 例如 一个二进制数1011 01可以表示成 1011 01 2 1 23 0 22 1 21 1 20 0 2 1 1 2 2二进制数的运算规则如下 加法规则0 0 00 1 11 0 11 1 0 进位为1 减法规则0 0 01 0 11 1 00 1 1 借位为1 乘法规则0 0 00 1 01 0 01 1 1除法规则0 1 01 1 1 例如 二进制数A 11001 B 101 则A B A B A B A B的运算为 二进制的优点 运算简单 物理实现容易 存储和传送方便 可靠 因为二进制中只有0和1两个数字符号 可以用电子器件的两种不同状态来表示一位二进制数 例如 可以用晶体管的截止和导通表示1和0 或者用电平的高和低表示1和0等 所以 在数字系统中普遍采用二进制 二进制的缺点 数的位数太长且字符单调 使得书写 记忆和阅读不方便 为了克服二进制的缺点 人们在进行指令书写 程序输入和输出等工作时 通常采用八进制数和十六进制数作为二进制数的缩写 四 八进制基数R 8的进位计数制称为八进制 八进制数中有0 1 7共8个基本数字符号 进位规律是 逢八进一 八进制数的位权是8的整数次幂 任意一个八进制数N可以表示成 N 8 Kn 1Kn 2 K1K0 K 1K 2 K m 8 Kn 1 8n 1 Kn 2 8n 2 K1 81 K0 80 K 1 8 1 K 2 8 2 K m 8 m其中 n 整数位数 m 小数位数 Ki 0 7中的任何一个字符 m i n 1 五 十六进制基数R 16的进位计数制称为十六进制 十六进制数中有0 1 9 A B C D E F共16个数字符号 其中 A F分别表示十进制数的10 15 进位规律为 逢十六进一 十六进制数的位权是16的整数次幂 任意一个十六进制数N可以表示成 N 16 Kn 1Kn 2 K1K0 K 1K 2 K m 16 Kn 1 16n 1 Kn 2 16n 2 K1 161 K0 160 K 1 16 1 K 2 16 2 K m 16 m其中 n 整数位数 m 小数位数 Ki 表示0 9 A F中的任何一个字符 m i n 1 下表列出了与十进制数0 15对应的二进制数 八进制数 十六进制数 11 2 2数制转换 数制转换是指将一个数从一种进位制转换成另一种进位制 从实际应用出发 要求掌握二进制数与十进制数 八进制数 以及十六进制数之间的相互转换 一 二进制数与十进制数之间的转换1 二进制数转换为十进制数 方法 多项式替代法二进制数转换成十进制数时 只需将二进制数表示成按权展开式 并按十进制运算法则进行计算 所得结果即为该数对应的十进制数 例如 10110 101 2 1 24 1 22 1 21 1 2 1 1 2 3 16 4 2 0 5 0 125 22 625 10 2 十进制数转换为二进制数 方法 基数乘除法十进制数转换成二进制数时 应对整数和小数分别进行处理 整数转换采用 除2取余 的方法小数转换采用 乘2取整 的方法 1 整数转换 除2取余 法 将十进制整数N除以2 取余数计为K0 再将所得商除以2 取余数记为K1 依此类推 直至商为0 取余数计为Kn 1为止 即可得到与十进制整数N对应的n位二进制整数Kn 1 K1K0 注意 当十进制小数不能用有限位二进制小数精确表示时 可根据精度要求 求出相应的二进制位数近似地表示 一般当要求二进制数取m位小数时 可求出m 1位 然后对最低位作0舍1入处理 例如 将十进制小数0 323转换成二进制小数 保留4位小数 即 0 323 10 0 0101 2 若一个十进制数既包含整数部分 又包含小数部分 则需将整数部分和小数部分分别转换 然后用小数点将两部分结果连到一起 二 二进制数与八进制数 十六进制数之间的转换 1 二进制数与八进制数之间的转换由于八进制中的基本数字符号0 7正好和3位二进制数的8种取值000 111对应 所以 二进制数与八进制数之间的转换可以按位进行 二进制数转换成八进制数 以小数点为界 分别往高 往低每3位为一组 最后不足3位时用0补充 然后写出每组对应的八进制字符 即为相应八进制数 八进制数转换成二进制数时 只需将每位八进制数用3位二进制数表示 小数点位置保持不变 2 二进制数与十六进制数之间的转换 二进制数与十六进制数之间的转换同样可以按位进行 只不过是4位二进制数对应1位十六进制数 即4位二进制数的取值 0000 1111 分别对应十六进制字符0 F 二进制数转换成十六进制数 以小数点为界 分别往高 往低每4位为一组 最后不足4位时用0补充 然后写出每组对应的十六进制字符即可 十六进制数转换成二进制数 只需将每位十六进制数用4位二进制数表示 在对数进行算术运算时 必然涉及到数的符号问题 人们通常在一个数的前面用 号表示正数 用 号表示负数 数字系统中如何处理呢 在数字系统中 符号和数值一样是用0和1来表示的 一般将数的最高位作为符号位 用0表示正 用1表示负 为了区分一般书写表示的带符号二进制数和数字系统中的带符号二进制数 通常将用 表示正 负的二进制数称为符号数的真值 而把将符号和数值一起编码表示的二进制数称为机器数或机器码 常用的机器码有原码 反码和补码三种 补充带符号二进制数的代码表示 补充 1原码 用原码表示带符号二进制数时 符号位用0表示正 1表示负 数值位保持不变 原码表示法又称为符号 数值表示法 一 小数原码的定义设二进制小数X 0 X 1X 2 X m 则其原码定义为 例如 若X1 0 1011 X2 0 1011 则X1和X2的原码为 X1 原 0 1011 X2 原 1 0 1011 1 1011 根据定义 小数 0 的原码可以表示成0 0 0或1 0 0 二 整数原码的定义 设二进制整数X Xn 1Xn 2 X0 则其原码定义为例如 若X1 1101 X2 1101 则X1和X2的原码为 X1 原 01101 X2 原 24 1101 10000 1101 11101同样 整数 0 的原码也有两种形式 即00 0和10 0 原码的优点 简单易懂 求取方便 缺点 加 减运算不方便 当进行两数加 减运算时 要根据运算及参加运算的两个数的符号来确定是加还是减 如果是做减法 还需根据两数的大小确定被减数和减数 以及运算结果的符号 显然 这将增加运算的复杂性 如何克服原码的缺点呢 首先请看下面的例子 当要将时针从10点调至5点时 可顺调7格 7 也可反调5格 5 即对12进制而言10 5 10 7 这里 5 7 12 通常称5和7对12进制而言互补 为了克服原码的缺点 引入了反码和补码 补充 2反码 带符号二进制数的反码表示 符号位 用0表示正 用1表示负 数值位 正数反码的数值位和真值的数值位相同 而负数反码的数值位是真值的数值位按位变反 一 小数反码的定义设二进制小数X 0 x 1x 2 x m 则其反码定义为 例如 若X1 0 1011 X2 0 1011 则X1和X2的反码为 X1 反 0 1011 X2 反 2 2 4 X2 10 0000 0 0001 0 1011 1 0100即 根据定义 小数 0 的反码有两种表示形式 即0 0 0和1 1 1 二 整数反码的定义设二进制整数X Xn 1Xn 2 X0 则其反码定义为例如 若X1 1001 X2 1001 则X1和X2的反码为 X1 反 01001 X2 反 25 1 X 100000 1 1001 11111 1001 10110即 同样 整数 0 的反码也有两种形式 即00 0和11 1 采用反码进行加 减运算时 无论进行两数相加还是两数相减 均可通过加法实现 加 减运算规则如下 X1 X2 反 X1 反 X2 反 X1 X2 反 X1 反 X2 反 运算时 符号位和数值位一样参加运算 当符号位有进位产生时 应将进位加到运算结果的最低位 才能得到最后结果 例如 若X1 0 1110 X2 0 0101 则求X1 X2可通过反码相加实现 运算如下 X1 X2 反 X1 反 X2 反 0 1110 1 1010即 X1 X2 反 0 1001 由于结果的符号位为0 表示是正数 故X1 X2 0 1001 补充 3补码带符号二进制数的补码表示 符号位 用0表示正 用1表示负 数值位 正数补码的数值位与真值相同 负数补码的数值位是真值的数值位按位变反 并在最低位加1 一 小数补码的定义设二进制小数X 0 X 1X 2 X m 则其补码定义为 例如 若X1 0 1011 X2 0 1011 则X1和X2的补码为 X1 补 0 1011 X2 补 2 X 10 0000 0 1011 1 0101注意 小数 0 的补码只有一种表示形式 即0 0 0 二 整数补码的定义设二进制整数X xn 1xn 2 x0 则其补码定义为例如 若X1 1010 X2 1010 则X1和X2的补码为 X1 补 01010 正数补码的数值位与真值相同 X2 补 25 X 100000 1010 10110 负数补码的数值位是真值的数值位按位变反 并在最低位加1 整数 0 的补码也只有一种表示形式 即00 0 采用补码进行加 减运算时 可以将加 减运算均通过加法实现 运算规则如下 X1 X2 补 X1 补 X2 补 X1 X2 补 X1 补 X2 补 运算时 符号位和数值位一样参加运算 若符号位有进位产生 则应将进位丢掉后才得到正确结果 例如 若X1 1001 X2 0011 则采用补码求X1 X2的运算如下 X1 X2 补 X1 补 X2 补 10111 1110110111 11101 丢掉110100即 X1 X2 补 10100 由于结果的符号位为1 表示是负数 故 X1 X2 1100 注意 补码 负数 还原成真值时 应对数值位减一变反 显然 采用补码进行加 减运算最方便 11 2 3编码 1 十进制数的二进制编码 BCD码 用4位二进制代码对十进制数字符号进行编码 简称为二 十进制代码 或称BCD BinaryCodedDecimal 码 BCD码既有二进制的形式 又有十进制的特点 常用的BCD码有8421码 2421码和余3码 十进制数字符号0 9与8421码 2421码和余3码的对应关系如下表所示 一 8421码8421码 是用4位二进制码表示一位十进制字符的一种有权码 4位二进制码从高位至低位的权依次为23 22 21 20 即为8 4 2 1 故称为8421码 按8421码编码的0 9与用4位二进制数表示的0 9完全一样 所以 8421码是一种人机联系时广泛使用的中间形式 注意 1 8421码中不允许出现1010 1111六种组合 因为没有十进制数字符号与其对应 2 十进制数字符号的8421码与相应ASCII码的低四位相同 这一特点有利于简化输入输出过程中BCD码与字符代码的转换 8421码与十进制数之间的转换8421码与十进制数之间的转换是按位进行的 即十进制数的每一位与4位二进制编码对应 例如 258 10 001001011000 8421码 0001001000001000 8421码 1208 10 8421码与二进制的区别例如 28 10 11100 2 00101000 8421 二 2421码 2421码是另一种有权码 其4位二进制码从高位至低位的权依次为2 4 2 1 若一个十进制字符X的2421码为a3a2a1a0 则该字符的值为 X 2a3 4a2 2a1 1a0例如 1101 2421码 7 10 2421码与十进制数之间的转换2421码与十进制数之间的转换同样是按位进行的 例如 258 10 001010111110 2421码 0010000111101011 2421码 2185 10 注意 1 2421码不具备单值性 例如 0101和1011都对应十进制数字5 为了与十进制字符一一对应 2421码不允许出现0101 1010的6种状态 2 2421码是一种对9的自补代码 即一个数的2421码只要自身按位变反 便可得到该数对9的补数的2421码 例如 具有这一特征的BCD码可给运算带来方便 因为直接对BCD码进行运算时 可利用其对9的补数将减法运算转化为加法运算 3 应与二进制数进行区别 三 余3码余3码是由8421码加上0011形成的一种无权码 由于它的每个字符编码比相应8421码多3 故称为余3码 例如 十进制字符5的余3码等于5的8421码0101加上0011 即为1000 注意 余3码有6种状态0000 0001 0010 1101 1110和1111是不允许出现的 余3码与十进制数之间的转换也是按位进行的 值得注意的是每位十进制数的编码都应余3 例如 256 10 010110001001 余3码 1000100110011011 余3码 5668 10 余3码也是一种对9的自补代码 将两个余3码表示的十进制数相加时 能正确产生进位信号 但对 和 必须修正 修正的方法是 如果有进位 则结果加3 如果无进位 则结果减3 2可靠性编码作用 为