FPGA 与数字 IC 设计 / 系统课时
用卡诺图消除冗余逻辑项
用卡诺图消除冗余逻辑项
当布尔表达式包含多个乘积项时,直接用与门、或门实现,可能产生不必要的逻辑门和较长的组合路径。本课使用一个四变量函数,从真值表填写卡诺图、合并相邻格子,再将化简结果映射为门电路,实际比较优化前后的门数与逻辑级数。
学习目标
- 能按照格雷码顺序填写三变量或四变量卡诺图,识别相邻的最小项。
- 能使用 1、2、4、8 格分组消去冗余变量,得到简化的与或表达式。
- 能根据统一的门电路计数规则比较优化前后的门数,并验证逻辑功能不变。
从真值表建立卡诺图
卡诺图(Karnaugh Map,K-map)是一种直观的布尔函数化简工具。每个格子对应一个输入组合,格子中的 1 表示该输入组合使函数输出为 1。它尤其适合处理 2~4 个输入变量的逻辑函数。
以四输入函数 为例,假设输出为 1 的最小项编号为:
最小项编号采用二进制位序 ,其中 是最高位, 是最低位。例如编号 5 对应 ,即 。
绘制四变量卡诺图时,把 放在行轴,把 放在列轴。两个轴都必须使用格雷码顺序:00、01、11、10,而不是普通二进制递增顺序。
| AB / CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | 1 |
| 01 | 1 | 1 | 1 | 1 |
| 11 | 1 | 1 | 0 | 0 |
| 10 | 1 | 1 | 0 | 0 |
填图时可以逐个核对:左上角是 ,第一行第三列是 ,第三行第一列是 。其余没有列出的最小项填 0。
格雷码排列保证水平或垂直相邻的两个格子只相差一个变量。第一列和最后一列也相邻,第一行和最后一行同样相邻;但对角线方向不算相邻。

用相邻分组消除变量
卡诺图的化简规则是把值为 1 的格子组成矩形分组,每组格子数必须是 2 的整数次幂,即 1、2、4、8、16。分组可以重叠,但不能包含值为 0 的格子,也不能为了凑数量组成 L 形。
对本例可以选择两个分组:
- 将前两行的全部 8 个格子组成一组。这些格子的 始终为 0, 都会变化,因此这一组化简成 。
- 将前两列的全部 8 个格子组成另一组。这些格子的 始终为 0, 都会变化,因此这一组化简成 。
两个分组在左上角四个格子发生重叠,这是合法的。每一个输出为 1 的格子至少被一个分组覆盖即可,不要求每格只能属于一个组。

于是函数化简为:
这个结果还可以由代数恒等式理解:两个相邻乘积项如果只在某个变量上互补,那么该变量可以被消去。
例如 。卡诺图实际上把这种相邻项合并过程变成了可视化分组。
分组时通常优先选择能够覆盖更多 1 的大组,再检查是否存在尚未覆盖的 1。大组能够保留更少变量,但分组数量也影响最终门数,所以不能只凭单组大小判断整个实现是否最优。
比较化简前后的门电路
为了让门数比较有统一标准,先约定使用具有任意所需输入数的与门、或门以及单输入非门;一个非门计 1 个门,一个多输入与门或或门也计 1 个门。暂不考虑标准单元库的最大扇入、驱动能力和布线延迟。
对于本例,按 和 的取值分类,可以得到一个尚未完全化简、但比十二个最小项展开式紧凑的表达式:
这三个乘积项覆盖的输入组合分别是 4、4、4 个,共计 12 个输出为 1 的组合。
按照上述计数规则,对比结果如下:
| 指标 | 化简前 | 化简后 |
|---|---|---|
| 表达式 | 3 个二变量乘积项 | 2 个单变量项 |
| 非门 | 2 | 2 |
| 与门 | 3 | 0 |
| 或门 | 1 | 1 |
| 总门数 | 6 | 3 |
| 最大逻辑级数 | 3 | 2 |
化简前,从输入 或 的反相信号路径出发,可能依次经过非门、与门、或门,共 3 级;化简后仅经过非门、或门,共 2 级。
因此在这个抽象门模型下,门数由 6 个降为 3 个,减少 50%。不过,实际综合工具可能使用 NOR 门、AOI 门等复合标准单元实现同一函数,面积和时序收益不一定与抽象门数成正比。
进一步应用德摩根定律:
如果允许使用二输入 NAND 门,整个函数甚至可以直接由一个 NAND 门实现。这说明卡诺图得到的是布尔层面的简化表达式,最终映射结果还取决于可用门类型。
验证化简结果是否等价
化简不能只凭图形直觉判断。对四变量函数,一共只有 种输入组合,可以逐一核对原函数与简化函数的输出。
使用下面的 Python 3 程序枚举全部组合,比较最小项定义和简化表达式:
from itertools import product
minterms = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13}
errors = []
for a, b, c, d in product((0, 1), repeat=4):
# ABCD 按从高位到低位构造最小项编号
index = (a << 3) | (b << 2) | (c << 1) | d
original = int(index in minterms)
# 卡诺图化简后的与或表达式
simplified = int((not a) or (not c))
if original != simplified:
errors.append(index)
print(f"检查组合数: 16")
print(f"不一致编号: {errors}")
print(f"等价验证: {len(errors) == 0}")预期输出:
检查组合数: 16
不一致编号: []
等价验证: True输出为空列表说明不存在逻辑不一致的输入组合。对于小规模组合电路,穷举真值表是非常直接的验证方式;如果后续使用 Verilog 编写 RTL,也可以对照原函数进行仿真或形式等价检查。
还可以进行两项手工边界检查:输入 时,无论 是什么,输出都应为 0;只要 或 ,输出都应为 1。这正是化简式保留的逻辑条件。
避免错误分组和错误优化
卡诺图最常见的错误不是计算复杂,而是误认相邻关系或遗漏覆盖。
- 错误:列按 00、01、10、11 排列。正确:使用 00、01、11、10,保证相邻格子仅改变一位。
- 错误:将斜对角的两个 1 合并。正确:只允许水平或垂直相邻,包含图形边界环绕的相邻关系。
- 错误:把六个 1 圈成一个大组。正确:每组格数只能是 1、2、4、8、16 等 2 的整数次幂,必要时采用两个可重叠的四格组。
- 错误:为了避免重复覆盖,将已经包含在某组中的 1 排除出其他组。正确:允许重叠,只需确保每个要求为 1 的格子被覆盖。
- 错误:把输入未定义直接当作无关项。正确:只有功能规格明确允许该输入组合输出任意值时,才能标记为 X,并在化简时选择性利用。
例如某个四变量控制器仅有 10 个合法状态,剩余 6 个状态不能自动视为 X。如果上电瞬态、故障或状态机异常可能进入这些状态,就必须明确非法状态的输出行为,否则优化后的电路可能在异常输入时产生危险控制信号。
卡诺图适用于变量较少、需要人工检查的组合逻辑。输入变量增加到 5~6 个时,图形分组明显变复杂;更大规模的逻辑通常交给综合工具处理。实际设计时保留原始真值表作为验收依据,用卡诺图理解冗余项,再根据目标标准单元库的面积和时序报告判断最终优化效果。