卡诺图（Karnaugh Map）详解
一、卡诺图的定义
卡诺图（Karnaugh Map，简称 K-Map）是由美国工程师 Maurice Karnaugh 于 1953 年提出的一种图形化逻辑函数化简工具。它本质上是真值表的二维矩阵表示形式，通过将相邻最小项合并，快速得到逻辑函数的最简表达式。
核心思想：利用"逻辑相邻性"（仅有一位变量不同的最小项可以合并），通过几何相邻直观地完成代数化简。
二、卡诺图的基本原理
1. 最小项与最大项
对 n 个变量的逻辑函数：
- 最小项（minterm）：所有变量以原变量或反变量形式相乘的乘积项，共 2ⁿ 个，记作 m₀, m₁, ..., m_{2ⁿ-1}
- 最大项（maxterm）：所有变量以原变量或反变量形式相加的和项，记作 M₀, M₁, ...
2. 格雷码排列（Gray Code）
卡诺图的行和列采用格雷码排序（如 00, 01, 11, 10），保证任意相邻方格仅有一个变量发生变化，这正是合并最小项的依据：
AB+ABˉ=AAB+ABˉ=A
三、卡诺图的结构（按变量数）
1. 二变量卡诺图（2 个变量 A, B）
| A＼B | 0 | 1 |
|---|---|---|
| 0 | m₀ | m₁ |
| 1 | m₂ | m₃ |
2. 三变量卡诺图（A, B, C）
| A＼BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | m₀ | m₁ | m₃ | m₂ |
| 1 | m₄ | m₅ | m₇ | m₆ |
3. 四变量卡诺图（A, B, C, D）
| AB＼CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | m₀ | m₁ | m₃ | m₂ |
| 01 | m₄ | m₅ | m₇ | m₆ |
| 11 | m₁₂ | m₁₃ | m₁₅ | m₁₄ |
| 10 | m₈ | m₉ | m₁₁ | m₁₀ |
4. 五变量及以上
通常采用两个或多个四变量卡诺图叠放（如对应方格代表第 5 个变量为 0 或 1）。变量超过 6 个时，卡诺图不再实用，需改用 Q-M 法（Quine-McCluskey）或计算机辅助工具。
四、化简规则
1. 合并规则
- 圈内方格数必须为2ᵏ（1, 2, 4, 8, 16…）
- 圈必须为矩形（横向或纵向），且全部为 1（或全部为 0）
- 圈越大，消去的变量越多
- 卡诺图上下、左右边界相连（环形结构），四角也相邻
2. 合并原则
| 圈大小 | 消去变量数 |
|---|---|
| 1 格 | 0 |
| 2 格 | 1 |
| 4 格 | 2 |
| 8 格 | 3 |
| 16 格 | 4 |
3. 化简步骤
- 根据真值表/逻辑表达式填入卡诺图（1、0、d 无关项）
- 圈出尽可能大的圈，圈数尽可能少
- 每个 1 至少被圈一次；可重复被圈但不能漏
- 利用无关项（d / X）帮助形成更大的圈
- 写出每个圈对应的乘积项，做"或"运算得最简积之和（SOP）
五、应用领域
1. 数字逻辑电路设计
- 组合逻辑电路：化简门级实现，减少门数和级数
- 时序电路：化简状态方程、输出方程、激励方程
2. 计算机硬件设计
- CPU 控制器、ALU 设计中的逻辑函数化简
- 存储器译码电路、指令译码器
3. 自动控制与工业系统
- PLC（可编程逻辑控制器）梯形图逻辑优化
- 传感器逻辑判断电路
4. 通信与编码
- 差错控制编码中的校验逻辑化简
- 译码器、多路选择器设计
5. EDA / Verilog/VHDL 前端设计
- 综合工具背后逻辑优化算法的理论基础
- 教学/手工验证综合结果
6. 教学与算法基础
- 数字电子技术、计算机组成原理课程核心内容
- Q-M 算法、ESPRESSO 算法的入门基础
六、典型示例
示例 1：三变量函数化简
给定函数： F(A,B,C)=∑m(0,2,4,5,6)F(A,B,C)=∑m(0,2,4,5,6)
填卡诺图：
| A＼BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 |
画圈：
- 大圈 1：第 1 列与第 4 列（00 和 10）共 4 格 → C = 0 → 得
C̄ - 小圈 2：m₄ 与 m₅（A=1, B=0）→ 得
A B̄
最简结果： F=Cˉ+ABˉF=Cˉ+ABˉ
示例 2：四变量函数化简（含无关项）
给定函数： F(A,B,C,D)=∑m(1,3,7,11,15)+∑d(0,2,5)F(A,B,C,D)=∑m(1,3,7,11,15)+∑d(0,2,5)
填卡诺图：
| AB＼CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | d | 1 | 1 | d |
| 01 | 0 | d | 1 | 0 |
| 11 | 0 | 0 | 1 | 0 |
| 10 | 0 | 0 | 1 | 0 |
画圈：
- 圈 1（4 格）：CD = 11 一整列 →
CD - 圈 2（4 格）：第一行 + 利用无关项 →
ĀB̄（如果选用 d）
最简结果（一种选择）： F=CD+AˉBˉF=CD+AˉBˉ
示例 3：一位全加器的设计
全加器输入：A、B、Cin；输出：Sum、Cout
Cout 的卡诺图：
| AB＼Cin | 0 | 1 |
|---|---|---|
| 00 | 0 | 0 |
| 01 | 0 | 1 |
| 11 | 1 | 1 |
| 10 | 0 | 1 |
画圈合并： Cout=AB+B⋅Cin+A⋅CinCout=AB+B⋅Cin+A⋅Cin
Sum的卡诺图无相邻 1，最终： Sum=A⊕B⊕CinSum=A⊕B⊕Cin
示例 4：BCD 七段译码器（片段）
设计 BCD 码到七段数码管 a 段的输出逻辑：
- 输入：4 位 BCD 码 ABCD（仅 0~9 有效，10~15 为无关项 d）
- 利用 6 个无关项可大幅化简 a~g 各段表达式
通过卡诺图可将原本复杂的 10 项最小项化简为 4~5 项的最简式，大幅节省门电路资源。
七、卡诺图 vs 其他方法
| 方法 | 适用变量数 | 特点 |
|---|---|---|
| 真值表+代数法 | 任意 | 灵活但繁琐 |
| 卡诺图 | ≤ 6 | 直观、快速、易出错少 |
| Q-M 算法 | 任意 | 系统化、可计算机实现 |
| ESPRESSO | 任意 | 工业 EDA 实际使用 |
八、总结
- 卡诺图本质：真值表的几何化、最小项相邻性的可视化表示
- 核心优势：直观、快速、人工可操作，适合 ≤ 6 变量
- 核心限制：变量增多时图形复杂，难以扩展
- 重要意义：是数字电路设计入门必备工具，也是更高级逻辑优化算法的理论基础
- 现代地位：虽然实际工程化简已被 EDA 工具替代，但卡诺图仍是理解逻辑优化思想最直观的途径