卡诺图（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保证任意相邻方格仅有一个变量发生变化这正是合并最小项的依据ABABˉAABABˉA三、卡诺图的结构按变量数1. 二变量卡诺图2 个变量 A, BAB010m₀m₁1m₂m₃2. 三变量卡诺图A, B, CABC000111100m₀m₁m₃m₂1m₄m₅m₇m₆3. 四变量卡诺图A, B, C, DABCD0001111000m₀m₁m₃m₂01m₄m₅m₇m₆11m₁₂m₁₃m₁₅m₁₄10m₈m₉m₁₁m₁₀4. 五变量及以上通常采用两个或多个四变量卡诺图叠放如对应方格代表第 5 个变量为 0 或 1。变量超过 6 个时卡诺图不再实用需改用 Q-M 法Quine-McCluskey或计算机辅助工具。四、化简规则1. 合并规则圈内方格数必须为2ᵏ1, 2, 4, 8, 16…圈必须为矩形横向或纵向且全部为 1或全部为 0圈越大消去的变量越多卡诺图上下、左右边界相连环形结构四角也相邻2. 合并原则圈大小消去变量数1 格02 格14 格28 格316 格43. 化简步骤根据真值表/逻辑表达式填入卡诺图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)填卡诺图ABC000111100100111101画圈大圈 1第 1 列与第 4 列00 和 10共 4 格 → C 0 → 得C̄小圈 2m₄ 与 m₅A1, B0→ 得A B̄最简结果 FCˉABˉFCˉ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)填卡诺图ABCD0001111000d11d010d10110010100010画圈圈 14 格CD 11 一整列 →CD圈 24 格第一行 利用无关项 →ĀB̄如果选用 d最简结果一种选择 FCDAˉBˉFCDAˉBˉ示例 3一位全加器的设计全加器输入A、B、Cin输出Sum、CoutCout 的卡诺图ABCin010000010111111001画圈合并 CoutABB⋅CinA⋅CinCout​ABB⋅Cin​A⋅Cin​Sum的卡诺图无相邻 1最终 SumA⊕B⊕CinSumA⊕B⊕Cin​示例 4BCD 七段译码器片段设计 BCD 码到七段数码管 a 段的输出逻辑输入4 位 BCD 码 ABCD仅 0~9 有效10~15 为无关项 d利用 6 个无关项可大幅化简 a~g 各段表达式通过卡诺图可将原本复杂的 10 项最小项化简为 4~5 项的最简式大幅节省门电路资源。七、卡诺图 vs 其他方法方法适用变量数特点真值表代数法任意灵活但繁琐卡诺图≤ 6直观、快速、易出错少Q-M 算法任意系统化、可计算机实现ESPRESSO任意工业 EDA 实际使用八、总结卡诺图本质真值表的几何化、最小项相邻性的可视化表示核心优势直观、快速、人工可操作适合 ≤ 6 变量核心限制变量增多时图形复杂难以扩展重要意义是数字电路设计入门必备工具也是更高级逻辑优化算法的理论基础现代地位虽然实际工程化简已被 EDA 工具替代但卡诺图仍是理解逻辑优化思想最直观的途径