FPGA 与数字 IC 设计 / 系统课时

用卡诺图消除冗余逻辑项

用卡诺图消除冗余逻辑项

当布尔表达式包含多个乘积项时,直接用与门、或门实现,可能产生不必要的逻辑门和较长的组合路径。本课使用一个四变量函数,从真值表填写卡诺图、合并相邻格子,再将化简结果映射为门电路,实际比较优化前后的门数与逻辑级数。

学习目标

  • 能按照格雷码顺序填写三变量或四变量卡诺图,识别相邻的最小项。
  • 能使用 1、2、4、8 格分组消去冗余变量,得到简化的与或表达式。
  • 能根据统一的门电路计数规则比较优化前后的门数,并验证逻辑功能不变。

从真值表建立卡诺图

卡诺图(Karnaugh Map,K-map)是一种直观的布尔函数化简工具。每个格子对应一个输入组合,格子中的 1 表示该输入组合使函数输出为 1。它尤其适合处理 2~4 个输入变量的逻辑函数。

以四输入函数 F(A,B,C,D)F(A,B,C,D) 为例,假设输出为 1 的最小项编号为:

F=Σm(0,1,2,3,4,5,6,7,8,9,12,13)F=\Sigma m(0,1,2,3,4,5,6,7,8,9,12,13)

最小项编号采用二进制位序 ABCDABCD,其中 AA 是最高位,DD 是最低位。例如编号 5 对应 01010101,即 A=0,B=1,C=0,D=1A=0,B=1,C=0,D=1。

绘制四变量卡诺图时,把 ABAB 放在行轴,把 CDCD 放在列轴。两个轴都必须使用格雷码顺序: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

填图时可以逐个核对:左上角是 m0m_0,第一行第三列是 m3m_3,第三行第一列是 m12m_{12}。其余没有列出的最小项填 0。

格雷码排列保证水平或垂直相邻的两个格子只相差一个变量。第一列和最后一列也相邻,第一行和最后一行同样相邻;但对角线方向不算相邻。

四变量卡诺图的格雷码排列及边界相邻关系

用相邻分组消除变量

卡诺图的化简规则是把值为 1 的格子组成矩形分组,每组格子数必须是 2 的整数次幂,即 1、2、4、8、16。分组可以重叠,但不能包含值为 0 的格子,也不能为了凑数量组成 L 形。

对本例可以选择两个分组:

  1. 将前两行的全部 8 个格子组成一组。这些格子的 AA 始终为 0,B,C,DB,C,D 都会变化,因此这一组化简成 A‾\overline A。
  2. 将前两列的全部 8 个格子组成另一组。这些格子的 CC 始终为 0,A,B,DA,B,D 都会变化,因此这一组化简成 C‾\overline C。

两个分组在左上角四个格子发生重叠,这是合法的。每一个输出为 1 的格子至少被一个分组覆盖即可,不要求每格只能属于一个组。

四变量卡诺图的两个八格分组

于是函数化简为:

F=A‾+C‾F=\overline A+\overline C

这个结果还可以由代数恒等式理解:两个相邻乘积项如果只在某个变量上互补,那么该变量可以被消去。

XY+XY‾=X(Y+Y‾)=XXY+X\overline Y=X(Y+\overline Y)=X

例如 A‾B+A‾B‾=A‾\overline A B+\overline A\overline B=\overline A。卡诺图实际上把这种相邻项合并过程变成了可视化分组。

分组时通常优先选择能够覆盖更多 1 的大组,再检查是否存在尚未覆盖的 1。大组能够保留更少变量,但分组数量也影响最终门数,所以不能只凭单组大小判断整个实现是否最优。

比较化简前后的门电路

为了让门数比较有统一标准,先约定使用具有任意所需输入数的与门、或门以及单输入非门;一个非门计 1 个门,一个多输入与门或或门也计 1 个门。暂不考虑标准单元库的最大扇入、驱动能力和布线延迟。

对于本例,按 AA 和 CC 的取值分类,可以得到一个尚未完全化简、但比十二个最小项展开式紧凑的表达式:

F=A‾C‾+A‾C+AC‾F=\overline A\overline C+\overline AC+A\overline C

这三个乘积项覆盖的输入组合分别是 4、4、4 个,共计 12 个输出为 1 的组合。

按照上述计数规则,对比结果如下:

指标 化简前 化简后
表达式 3 个二变量乘积项 2 个单变量项
非门 2 2
与门 3 0
或门 1 1
总门数 6 3
最大逻辑级数 3 2

化简前,从输入 AA 或 CC 的反相信号路径出发,可能依次经过非门、与门、或门,共 3 级;化简后仅经过非门、或门,共 2 级。

因此在这个抽象门模型下,门数由 6 个降为 3 个,减少 50%。不过,实际综合工具可能使用 NOR 门、AOI 门等复合标准单元实现同一函数,面积和时序收益不一定与抽象门数成正比。

进一步应用德摩根定律:

A‾+C‾=AC‾\overline A+\overline C=\overline{AC}

如果允许使用二输入 NAND 门,整个函数甚至可以直接由一个 NAND 门实现。这说明卡诺图得到的是布尔层面的简化表达式,最终映射结果还取决于可用门类型。

验证化简结果是否等价

化简不能只凭图形直觉判断。对四变量函数,一共只有 24=162^4=16 种输入组合,可以逐一核对原函数与简化函数的输出。

使用下面的 Python 3 程序枚举全部组合,比较最小项定义和简化表达式:

python
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}")

预期输出:

text
检查组合数: 16
不一致编号: []
等价验证: True

输出为空列表说明不存在逻辑不一致的输入组合。对于小规模组合电路,穷举真值表是非常直接的验证方式;如果后续使用 Verilog 编写 RTL,也可以对照原函数进行仿真或形式等价检查。

还可以进行两项手工边界检查:输入 A=1,C=1A=1,C=1 时,无论 B,DB,D 是什么,输出都应为 0;只要 A=0A=0 或 C=0C=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 个时,图形分组明显变复杂;更大规模的逻辑通常交给综合工具处理。实际设计时保留原始真值表作为验收依据,用卡诺图理解冗余项,再根据目标标准单元库的面积和时序报告判断最终优化效果。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用卡诺图消除冗余逻辑项

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通