第四章 组合逻辑电路
课程：1A003 计算机组织与系统结构（第一部分 数字逻辑） 来源：北京大学软件研究所课程讲义 PPT 格式：PowerPoint 97-2003 二进制格式，LibreOffice 转 PDF 后 pdftotext 全文提取
一、逻辑电路的两种类型
组合逻辑电路 (Combinational Logic Circuit)
一个逻辑电路，如果它在任何时刻的输出仅仅是该时刻输入状态的函数，而与先前的输入状态无关，这样的逻辑电路称为组合逻辑电路。
时序逻辑电路 (Sequential Logic Circuit)
输出不仅取决于当前输入，还与之前的输入状态（电路的历史）有关。（详见第六、七章）
最小项 (Minterm)
设 A₁, A₂, …, Aₙ 是 n 个逻辑变量，P 是 n 个变量的乘积，如果在 P 中每个变量以原变量 Aᵢ 或反变量 Ā 的形式作为一个因子出现且仅出现一次，则称 P 为 n 个变量的一个最小项。
- 对于 n 个变量，共有 2ⁿ 个最小项
- 用 mᵢ 表示最小项，i 的确定规则：变量以原变量形式出现记做 1，以反变量形式出现记做 0，二进制数对应的十进制数就是 i 的值
- 例：ĀBC → 011 → m₃；ABC → 111 → m₇
最小项表达式（第一范式）
由最小项之和构成的逻辑表达式，称为逻辑函数的最小项表达式。
例：F(A,B,C) = ĀBC + AB̄C + ABC = m₃ + m₅ + m₇ = ∑m(3,5,7)
定理：n 个变量的任何一个逻辑函数，都可以展开成一组最小项的和或最大项的积，并且这种展开是唯一的。
化成最小项表达式的方法
- 真值表法（P171）
- 公式法（P172）
二、逻辑函数的图解化简法（卡诺图法）
卡诺图 (Karnaugh Map) —— 逻辑函数的最小项图示
- n 个变量的卡诺图包含 2ⁿ 个小格，分别对应 2ⁿ 个最小项。每个小格被赋值为 1 或 0。
- 每个变量及其反变量各占整个卡诺图区域的一半。
- 编号原则：任何一个小格的编号（二进制表示）与其相邻小格的编号相比仅有一位不同（格雷码排列）。
- 一个小格的相邻格的个数 = 变量个数
- 维度概念：
- 代表一个最小项的小格 = 0 维块
- 相邻两个 0 维块构成 1 维块（消去一个变量）
- 相邻两个 1 维块构成 2 维块（再消去一个变量）
- 以此类推
卡诺图结构示例
三变量卡诺图：m₂ 与 m₀、m₃、m₆ 相邻 四变量卡诺图：m₀ 与 m₁、m₂、m₄、m₈ 相邻（注意上下边、左右边也是相邻的）
利用卡诺图化简逻辑函数
基本方法：圈出所有为 1 的最小项，形成尽可能大的 2ᵏ 个方块的矩形圈，每个圈对应一个乘积项，所有圈的乘积项之和即为最简与或表达式。
化简举例：
- 例 1：F(A,B,C,D) = ∑m(0,1,3,8,9,11,13,14)
- 结果：F = ĀB̄C̄ + ĀCD + B̄D + ABC
- 例 2：F = ĀCD̄ + ĀB̄C̄D + BCD + ABCD̄ + ABC
- 结果：F = ĀC̄ + AB + ĀBD
- 例 3：五变量 F(A,B,C,D,E) = ∑m(2,8,9,10,15,18,24,25,26,31)
- 详见 P178
三、利用无关最小项化简逻辑函数
概念
在某些逻辑问题中，输入变量的某些取值组合不可能出现（或不允许出现），对应的最小项称为无关最小项（Don’t Care），记为 d。
- d 既可当作 1，也可当作 0，根据化简的需要而定
- 合理利用无关项可以大大简化逻辑电路
典型例题：四舍五入电路
输入 A,B,C,D 按 8421 编码，X = 8A + 4B + 2C + D 要求：X ≥ 5 时 F=1，否则 F=0
8421 码中 1010～1111 这六种取值不可能出现，是无关项。
F(A,B,C,D) = ∑m(5,6,7,8,9) + ∑d(10,11,12,13,14,15)
利用无关项化简结果：F = A + BC + BD
四、组合逻辑电路的分析
对给定的组合逻辑电路进行逻辑描述，找出对应的输入输出逻辑关系表达式，必要时化简或评价设计合理性。
基本步骤
- 根据给定电路，逐级写出输入输出关系式
- 依次代入，最后得到整个电路的输入输出关系式
- 如能化简则化简，明确电路功能和改进方案
例 1、例 2 详见 P180、P181
五、组合逻辑电路的设计
组合逻辑电路的设计也称综合，是分析的逆过程：由给定的逻辑功能求得实现该功能的逻辑电路。
基本步骤
- 根据逻辑功能列真值表
- 由真值表写出逻辑函数的最小项表达式
- 化简，并根据可用门电路类型化成所需形式
- 画出逻辑电路图
设计实例一：全加器 (Full Adder)
全加器：实现两个一位二进制数相加并考虑低位进位的逻辑电路。
- 三个输入端：加数 A、被加数 B、低位进位 J
- 两个输出端：和数 H、进位 J’
(1) 真值表
| A | B | J | H | J’ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
(2) 最小项表达式
H = ĀB̄J + ĀBJ̄ + AB̄J̄ + ABJ = ∑m(1,2,4,7) J’ = ĀBJ + AB̄J + ABJ̄ + ABJ = ∑m(3,5,6,7)
(3) 化简
- H 已最简（异或结构）
- J’ = BJ + AJ + AB
(4) 用与非门实现，画出逻辑图
可以用半加器（不考虑低位进位）组合构成全加器。
设计实例二：代码转换电路
设计要求：设计一个余 3 码到 8421 码的代码转换电路。
设计流程：
- 列真值表
- 写出各输出函数的最小项表达式
- 用卡诺图法化简
- 画出逻辑图
作业
P213：第 4、10、11(1)(3) 题
关联笔记
- 第一章 数制和编码 —— 数字逻辑基础，二进制/编码/码制
- 第二章 逻辑代数的基本原理及应用 —— 逻辑代数公式与化简方法
- 第三章 逻辑门电路 —— 基本门电路与实现
- 第六章 时序电路的基本单元－触发器 —— 时序逻辑电路基础
- 第五章 组合逻辑电路的应用 —— 组合电路实际应用
- 第七章 时序逻辑电路第八章 逻辑部件 —— 时序电路与逻辑部件