数字逻辑与数字集成电路-第1章.ppt

卡诺图化简 卡诺图化简的核心是找到并且合并相邻最小项 相邻三种情况 相接 相对 相重 5变量卡诺图才会出现相重的情况 合并过程中先找大圈合并 圈越大消去的变量越多 使每一最小项至少被合并包含过一次 每个合并的圈中 至少要有一个 1 没有被圈过 否则这个圈就是冗余的 4个变量卡诺图的最小项 m1 m0 m3 m2 m5 m4 m7 m6 m13 m12 m15 m14 m9 m8 m11 m10 m1的相邻最小项是m0 m3 m5 m9 其中m9是相对的 其余为相接 同样 m0与m8相对 与m2也相对 与或 表达式化简 例3 与或 表达式化简 如果在上图中的m10 1 可以出现8个1相连 消去3个变量 与或 表达式化简 此时 图上有13个最小项为1 只有3个最小项为0 写F的表达式更简单 注意 经常是写F比直接写F简单 5变量卡诺图的最小项 CBA 同样以m1为例 它的相邻最小项有5个 m0 m3 m9 m17 m5 其中m17为相对的 m5为相重的 其余为相接 例题 5变量卡诺图化简 化简结果 1 4逻辑函数的表格法化简 Q M法 计算机辅助逻辑设计的方法 卡诺图化简法直观方便 过程简单明了 但只适合于变量数4的函数 化简过程有规律 可编程 便于计算机实现 4变量卡诺图的最小项 m1 m0 m3 m2 m5 m4 m7 m6 m13 m12 m15 m14 m9 m8 m11 m10 相邻两个最小项中有一个变量互补 如何体现 从最小项的编号上看有什么规律 Q M方法的基本思想 相邻两个最小项中有一个变量互补 在最小项编号上的规律 以4变量卡诺图为例分析观察 m1同m0 m3 m5 m9相邻 每个mi都有4个相邻 它们的下标编号为 0001与0000 0011 0101 1001结论 相邻最小项编号中 1 的个数差等于1 m1同m2 m4 m8 3个最小项不相邻 它们的下标编号中 1 的个数差等于0 m1还有m6 m7 m10 m11 m12 m13 m14 m15等8个最小项不相邻 它们的下标0110 0111 1010 1011 这些最小项编号中 1 的个数差可能等于1 也可能不等于1 Q M方法的基本思想 续 根据最小项编号中 1 的个数差就能判断是否相邻 最小项编号中 1 的个数差 等于0 最小项肯定不相邻 等于1 最小项有可能相邻 算法步骤 1 最小项分组 将最小项编号中 1 的个数相同的最小项分在一组 并按组号大小排序 2 相邻组比较 合并最小项编号中 1 的个数差等于1的所有相邻最小项 得到函数的全部质蕴涵项 3 求必要质蕴涵项 从全部质蕴涵项中消去冗余项 得到必要质蕴涵项 即为化简结果 步骤1求函数的全部质蕴涵项 函数的 质蕴涵项 就是不能再合并的最小项 先把F中的各mi 按下标i中 1 的个数 由少到多 分组排队列表I 组号是mi中i所包含 1 的个数 在表I的相邻组间进行逐项搜索 寻找相邻项 把可以合并的记在表II中 并在表I中相应的最小项旁作记号 表II所列均是变量数为n 1的与项 n是F的变量数 它们同样按与项所含 1 的个数由少到多 分组排列 重复上述过程 直到不能合并为止 步骤1求函数的全部质蕴涵项 续 例 1 1 1 1 15 1 0 1 1 13 34 0 0 1 1 12 0 1 0 1 10 1 0 0 1 9 0 1 1 0 6 2 0 0 0 1 8 0 0 1 0 4 0 1 0 0 2 1 A B C D 最小项 组号 表I 问 1组需要和3 4组比吗 步骤1求函数的全部质蕴涵项 续 P1 P2 P3 P4 P5 P6 P7 在表I II III中 未打 的 标以P1 P7 称质蕴涵项 全部质蕴涵项覆盖了F的所有最小项 对表II继续上述过程 得表III 这一过程一直要进行到没有可合并的相邻组为止 步骤1求函数的全部质蕴涵项 续 用卡诺图画出F的全部质蕴涵项 P1 P4 P5是冗余的 下面的目的是要用表格法找出必要的质蕴涵项 P1 DBA P2 CBA 从卡诺图看哪些是冗余的 步骤1求函数的全部质蕴涵项 续 由图可见 P1 P7覆盖了F的全部最小项 对每个P项 它们是不能再和其它P项或最小项合并了 由图还可见 P1 P7中有不必要的质蕴涵项 例如 若P2 P3必要 则P1就不必要 为此 下一步骤就要从全部质蕴涵项中消去冗余项 选出必要的质蕴涵项 步骤2寻找必要的质蕴涵项 寻找必要质蕴涵项的过程 就是在表格中消去冗余质蕴涵项的过程 作全部质蕴涵项P1 P7与全部最小项mi对应的二维表格 例如 P1包含了最小项m2和m6 在对应位置画三角 m2被包含P1和P2所包含 表IV 质蕴涵项 最小项 只有P7包含4个最小项 其它只有2个最小项 步骤2寻找必要的质蕴涵项 续 判断哪些行是必要的 先行消去 再列消去 方法 先找只有一个 的列 它们所对应的行一定要保留 这个P项是必要质蕴涵项 对表IV 只有m9和m15对应的列只有一个 在卡诺图中表示这两个最小项只被画一次 这些列肯定是必要的 m9它所对应的P7有4个 分别对应m8 m9 m12 m13 因此P7为必要的 由于P7必要 P7所蕴涵的m8 m9 m12 m13可从表中暂时删去 以简化表IV 同理 由于m15是必要的 P6也为必要 P6所蕴涵的m13 m15可以从表中暂时删去 如下图 行消去 找到的是要保留的必要质蕴涵项 暂时从表格中消去的目的是为了简化表格 步骤2寻找必要的质蕴涵项 续 质蕴涵项 最小项 步骤2寻找必要的质蕴涵项 续 行消去 暂时消去了要保留的必要质蕴涵项 使表格简化 列消去 的目的是去掉不必要的质蕴涵项方法 先找只有一个 的行 如果在它所对应的列上也有 则表示这个P项被其它行所包含 这个P项就可以消去 在Pi行记有 的各列 若在Pj行对应列中也均记有 则Pi行就是不必要的质蕴涵项 步骤2寻找必要的质蕴涵项 续 表V 表VI 表V中 P4行只有一个 它所对应的m4列包含在P3行中 故P4为非必要的质蕴涵项 同理 P5也为非必要的质蕴涵项 表V简化为表VI 步骤2寻找必要的质蕴涵项 续 最后 再对简化后的表VI进行 行消去 P2 P3为必要质蕴涵项 因为m4和m10列只有一个 所以P2 P3必须保留 因P2 P3蕴涵了表VI中所列全部m项 m2 m4 m6 m10 故P1为非必要质蕴涵项 化简结果为 必要质蕴涵项的卡诺图表示 根据最小项编号中 1 的个数差判断是否相邻 第一步求全部质蕴涵项 分组后在相邻组间反复比较 两个最小项间只要有一个变量不同 就可以消去一个变量 最后得到覆盖F所有最小项的全部质蕴涵项 第二步求必要质蕴涵项 找出只有一个 的mi列 它所对应的P项一定是要保留的 找出只有一个 的Pi行 如果在它所对应的m列上也有 则表示这个P项是可以消去的 反复这一过程得到所有的必要质蕴涵项 多输出逻辑函数的表格法化简不要求 p38 45 计算机辅助逻辑化简的其他算法还在继续研究 逻辑函数的表格化简法 Q M法 小结 1 5特殊形式的逻辑函数化简 基本形式的逻辑函数 单输出逻辑函数 F f A B C 特殊形式的逻辑函数 1 多输出逻辑函数2 包含不管项的逻辑函数只要求掌握卡诺图化简法 1 多输出逻辑函数的化简 多输出逻辑函数 同一组输入变量 有两个以上的输出 F1 f A B C F2 f A B C 化简时 在 与或 表达式中要尽量寻找公共的 或 项 使公共项为多个函数共享 这时从单个输出看可能不是最简 但总体是最简 ABC是公共项 单独看F1 F2都是最简 但没有公共项 2 有 不管项 的逻辑函数化简 包含不管项 Don tCare 的逻辑函数 函数F的取值只和一部分最小项有关 另一部分最小项既可以取 0 也可以取 1 这些最小项称 不管项 或 任意项 不管项 的两种情况 1 这些输入组合不可能出现2 其输入组合虽能出现 但最小项的值是 1 还是 0 人们不关心 例 设计一位十进制数的数值范围判断器 当x 5 F 1 否则 F 0 ABCD表示一位十进制数 A是低位 D是高位 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 F D C B A 有 不管项 的逻辑函数化简 续 F的卡诺图 F D AC BC 把 项当作 1 1 6逻辑函数的实现 由最小项和函数式表达的逻辑函数要用逻辑电路来实现 实现时要考虑的问题包括可用集成电路的种类 逻辑函数的形式 集成电路的级数等 下列三种 与非 与非 结构最常用 与非 与非实现与 或 非实现或非 或非实现 门电路符号 传统符号IEEE标准符号习惯符号 门电路符号 例1 异或逻辑 A B不相同时 F为1 A B相同时 F为0 因此称异或逻辑或半加逻辑 表示为 F AB 逻辑符号 异或逻辑的实现 例题 逻辑问题的描述 逻辑设计的第一步 由文字叙述的设计要求 抽象为逻辑表达式的过程 然后才能化简 实现 例1 设计一个多数表决逻辑电路 判别ABC三人中是否为多数赞同 解 输入为0 表示反对 输入为1 表示赞同 当ABC中有两个和两个以上为 1 时 表示多数赞同 F 1 否则F 0 CBAF00000010010001111000101111011111 多数表决逻辑电路的真值表 F m3 m5 m6 m7 例2 1位二进制全加器的设计与实现 不考虑进位叫半加 考虑进位叫全加 真值表 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 Cn Fn Cn 1 Yn Xn 3个输入2个输出 输入输出 全加器逻辑的卡诺图化简 实现方案一 Fn用异或门实现 Cn用 与非 门实现 Cn用 与或非 门实现 实现方案二 直接由最小项用与或非门实现 需要3级门 实现方案三 写的表达式 经变换后只要2级门 实现方案三 续 组合逻辑 电路的输出只是和当前状态有关 和过去的状态无关 AB F ABF 理想情况 门电路没有延迟 F AB 组合逻辑 电路的输出只是和当前状态有关 和过去的状态无关 AB F ABF 实际情况 门电路存在延迟因此要尽量减少级数 组合逻辑 电路的输出只是和当前状态有关 和过去的状态无关 AB F ABF 实际情况 门电路存在延迟前沿延迟与后沿延迟不相等 本章重点 逻辑代数与逻辑函数的概念逻辑函数的化简 重点是4变量卡诺图作业 2 6 2 3 2 7 1 2 2 10 2 11 2 3 2 12 3 2 13 4 2 14 1 2 16 1