卡诺图：可视化的布尔化简

TL;DR: 卡诺图(K-map)把真值表排成一张格雷码编码的二维网格,相邻单元只差一个变量。把网格上相邻的 1 圈成 2 的幂次大小的矩形组,直接得到最小积之和(SOP)表达式——根本不需要做代数推演。卡诺图对最多 4 个变量的函数能可靠地最小化;对 5–6 变量,可使用 Quine–McCluskey 算法;再多就要靠 ESPRESSO 之类的算法化综合工具。

基于布尔定律的代数化简当然有效,但它依赖于在合适的时机看出合适的因式分解。一旦错过一次机会,就可能得到次优结果。当表达式涉及四个或更多变量时,可能的变形数量会爆炸式增长。

卡诺图(K-map)通过把代数化简变成可视化的图形识别来解决这个问题。它由贝尔实验室物理学家 Maurice Karnaugh 于 1953 年提出,把真值表排成一张二维网格,相邻单元恰好只差一个变量。在网格上把相邻的 1 圈成组,就直接得到最小积之和表达式——不需要任何代数操作。

AND 门元件示意图

可视化的真值表：什么是 K-map？

本质上,卡诺图就是真值表的另一种伪装。真值表把输入与输出按线性、垂直方式列出;K-map 把它们重新排成一张二维网格。这并不只是为了好看。K-map 的精妙之处在于它对单元格的特定排列方式。

在标准真值表中,行按二进制递增(00、01、10、11)。在 K-map 中,行和列遵循一种叫格雷码(Gray code)的序列。格雷码序列里,任意两个相邻的数——无论横向还是纵向移动——只相差一个比特。这种性质被称为逻辑相邻性(logical adjacency),正是化简的引擎。当你把含有 ‘1’ 的相邻单元圈成一组时,你其实是在可视化地识别那些”会变化(因而不影响结果)“的变量并把它们消掉,留下一个最小的布尔项。

在深入现代 ALU 设计中常见的复杂 4 变量图之前,我们先看看输入为 $A$ 、 $B$ 的基础 2 变量图。它由 $2^2 = 4$ 个单元组成,代表四个可能的最小项(minterm)。

	$B=0$ ( $\overline{B}$ )	$B=1$ ( $B$ )
$A=0$ ( $\overline{A}$ )	$m_0$ ( $\overline{A}\overline{B}$ )	$m_1$ ( $\overline{A}B$ )
$A=1$ ( $A$ )	$m_2$ ( $A\overline{B}$ )	$m_3$ ( $AB$ )

注意它们的相邻关系:从 $m_0$ 到 $m_1$ ,只有变量 $B$ 改变;从 $m_1$ 到 $m_3$ ,只有变量 $A$ 改变。这种网格上的物理邻近,代表了我们可以利用来减少门数量的逻辑关系。

体验基础逻辑

圈组的艺术：从 K-map 到最简逻辑

使用 K-map 的目标是用尽可能大的矩形组覆盖图中所有的 1。但有一个限制:每组的单元数必须是 2 的幂(1、2、4、8、16,以此类推)。你画的每一组,都对应一个化简后的乘积项。最终优化后的表达式,就是把这些组的结果”求和”(OR 起来)——也就是积之和形式。

圈组的规则严格而直接。机械地按规则操作就能保证得到最小结果。

覆盖每一个 ‘1’: 图中的每个 ‘1’ 都必须至少属于一个组。不允许有未圈起来的 1。
必须为 2 的幂: 每组必须恰好包含 $2^k$ 个单元——1、2、4、8 或 16。不能有 3、5、6 这样的组。一片由 6 个 1 组成的区域必须用 4 和 2 两个组来覆盖。
尽量做大组: 越大的组消去越多变量。2 个单元的组消去 1 个变量;4 个单元消去 2 个;8 个单元消去 3 个。永远先寻找尽可能大的组。
允许重叠: 一个 ‘1’ 可以同时属于多个组。要积极地用重叠来扩大组。
必须是矩形: 组必须是矩形(包含正方形)。L 形、T 形、对角形都不合法。
图是环绕的: 最左列与最右列相邻,最上行与最下行相邻。可以把图想象成一个环面(torus)——四个角彼此相邻。

深入：4 变量 K-map

让我们看一个真实场景。假设我们正在为某个 CONTROL_UNIT 设计一段逻辑,它要在 4 位输入满足特定条件时触发信号。我们的函数为 $F(A,B,C,D) = \Sigma m(0, 2, 5, 7, 8, 10, 13, 15)$ 。

$\Sigma m$ 表示法只是”当二进制输入等于这些十进制值时输出为 HIGH”的简写。先把 16 格网格填好。

	$CD=00$	$CD=01$	$CD=11$	$CD=10$
$AB=00$	1 ( $m_0$ )	0	0	1 ( $m_2$ )
$AB=01$	0	1 ( $m_5$ )	1 ( $m_7$ )	0
$AB=11$	0	1 ( $m_{13}$ )	1 ( $m_{15}$ )	0
$AB=10$	1 ( $m_8$ )	0	0	1 ( $m_{10}$ )

接下来寻找模式。

组 1：四个角

看 $m_0, m_2, m_8, m_{10}$ 处的 1。由于图在水平和垂直两个方向都环绕,这四个角实际上互为相邻!它们构成一个大小为 4 的组。

变量 A: 从 0 变到 1。(舍去)
变量 B: 始终为 0。(保留 $\overline{B}$ )
变量 C: 从 0 变到 1。(舍去)
变量 D: 始终为 0。(保留 $\overline{D}$ )
结果: $\overline{B}\overline{D}$

组 2：中间方块

中间在 $m_5, m_7, m_{13}, m_{15}$ 处构成一个完美的 2x2 方块。

变量 A: 从 0 变到 1。(舍去)
变量 B: 始终为 1。(保留 $B$ )
变量 C: 从 0 变到 1。(舍去)
变量 D: 始终为 1。(保留 $D$ )
结果: $BD$

所有的 1 都已被覆盖。最终化简表达式为:

F = \overline{B}\overline{D} + BD

这就是 XNOR 门的布尔定义——8 个 4 输入 AND 门构成的庞大网络坍缩为单一元件。

XNOR 门元件示意图

探索化简后的 XNOR 电路

常见陷阱：为什么必须用格雷码

一个常见错误是用标准二进制顺序——00、01、10、11——画 K-map。不要这么做。

如果用标准二进制,你就破坏了相邻性原理。看从 01 到 10 的跳变,两个比特都改变了 ( $0 \to 1$ 与 $1 \to 0$ )。如果这两个相邻单元都是 1,你无法把它们化简,因为有不止一个变量在变化。格雷码序列 (00、01、11、10) 保证你在图上每走一步都对应恰好一个变量的变化。这就是让数学在视觉上奏效的”魔法”。没有格雷码,K-map 不过是一张令人迷惑的表格;有了格雷码,它就成了一台计算器。

用 OSCILLOSCOPE_8CH 验证

数字工程中最令人满足的时刻之一,就是证明你那个”小”电路与”大”电路做的是完全相同的事。在 digisim.io 上,你可以实时做到这一点。

搭出蛮力版本: 用 8 个 AND 门和一个大型 OR 门来表达原始的最小项之和。
搭出优化版本: 在它下面放一个 XNOR 门(或两 AND 一 OR 的等价形式)。
同步输入: 把同一组 4 个 INPUT_SWITCH 同时接到两个电路上。
分析: 把蛮力电路的输出接到 OSCILLOSCOPE_8CH 的通道 1,把优化输出接到通道 2。

当你把开关切到全部 16 种组合时,OSCILLOSCOPE_8CH 上两个波形会完全一致。然而,如果你看传输延迟 ( $t_{pd}$ ),会发现优化版本的响应明显更快。在高速 CPU 项目中,这些纳秒就是 1MHz 时钟和 10MHz 时钟之间的差距。

真实世界应用：远不止考试

K-map 不只是为了应付考试,它是硬件描述工作中的常规工具。

1. ALU 控制逻辑

在典型的 8 位 CPU 中,ALU(算术逻辑单元)需要根据”操作码(opcode)“决定执行加法、减法,还是按位 AND。这个操作码可能是 4 位宽。工程师用 K-map 设计译码逻辑,把这 4 位操作码转换为针对 ADDER_8BIT 或 COMPARATOR_8BIT 等模块的具体控制线。最小化这套逻辑能减少”指令译码”时间——这是 CPU 性能的关键瓶颈。

2. 有限状态机(FSM)

无论是交通灯控制器还是复杂协议处理器,FSM 都依赖”次态逻辑”。这套逻辑根据当前状态(存在 REGISTER 中)和当前输入决定下一个状态。这些真值表很快就会变得庞大。K-map 让设计者能找到最高效的信号路由方式,常常能在最终实现里省下几十个门。

ALU 元件示意图

常见误区

要避免的常见错误:

悬空输入: AND 门的每个输入都必须接到某个东西。悬空输入在仿真器里可能行为可预测,但在真实硬件中会拾取噪声。
忽略环绕: 检查角和边。一些最优雅的化简来自圈起四个角或上下两行。
冗余组: 一旦所有 1 都被覆盖就停下。“看起来更顺眼”而再多加一组,只会向电路里塞入不必要的门,违背了 K-map 的初衷。

无关项的力量

在许多真实设计中,某些输入组合根本不可能出现。例如 BCD(二进制编码十进制)系统用 4 位表示 0–9 的数字,所以 1010 至 1111 这些组合永远不会出现。在 K-map 里,我们用 $X$ (无关项,don’t care)而不是 0 或 1 来标记这些不可能的输入。

关键在于:每个 $X$ 你都可以视为 0 或 1 中任意一个——以能让你形成更大组的那个为准。既然这些输入在实际中永不出现,无论电路对它们输出什么都无所谓。

例: 假设一个 4 变量函数在单元 0、2、8、10 处为 1,在单元 1 和 3 处为无关项。不利用无关项时,四个角的 1 会圈成 $\overline{B}\overline{D}$ 。但如果把单元 1 和 3 视为 1,你可以在第一行额外形成一个大小为 4 的组( $\overline{A}\overline{B}$ ),再加上原来的角组,可能得到更简单的总表达式。在真实设计中,无关项常常能把最终门数减少 20%–30%。

下一步

本文是 Boolean Algebra Fundamentals 系列的一部分。相关阅读:

布尔代数 —— K-map 圈组背后的代数恒等式。
积之和(SOP) —— K-map 直接产出的规范形式。
Beyond SOP: 和之积 —— 对偶最小化方法。
德摩根定律 —— 在不同形式之间转换所用的变换规则。

卡诺图把一项复杂的代数任务变成了一道视觉拼图。对最多 4 变量的函数,它能可靠地产出最小 SOP(或 POS)表达式。对 5–6 变量,K-map 仍可使用,但已显笨重;此时由 Quine–McCluskey 等算法方法接手。

把上面 worked example 中的蛮力版本和优化版本都搭出来,看着波形在示波器上完美对齐。开始一个新电路来验证。