之前做一个四路传感器告警板,四个输入分别是温度超限、压力超限、门磁打开和手动强制。哪几种组合该亮红灯,同事直接照着需求表列了十条,每条写成四个输入相与、十条再相或。仿真一次就过,逻辑没毛病。可综合报告出来,这片小 FPGA 的逻辑资源用掉了将近一半,而他后来改写的版本只用了几个查找表。同一个功能,两张真值表,面积差了十几倍。
差别不在代码风格,而在有没有化简。照真值表一条一条写出来的叫规范式:每个为 1 的行都单独占一个乘积项,四个变量就是四个文字,十行就是十个乘积项、四十个文字。化简要做的,是把「输出相同、输入只差一位」的行合并起来,用一个更短的乘积项代替它们。合并得越彻底,门越少、级数越浅、跑得越快。
这篇讲三件事:真值表里的最小项和无关项到底怎么用;SOP 和 POS 两种写法各自的代价;卡诺图怎么画、怎么圈、什么时候该停手改用工具。文中的化简结果和真值表穷举是本机用 Python 跑出来的,综合资源数字是经验量级,具体器件未在本机实测。
先看现象:十行真值表,为什么综合出一堆门
规范式的好处是「照着写不会错」。真值表哪一行为 1,就写一个最小项,所有最小项或起来,逻辑一定和真值表一致。坏处是它完全没有利用行与行之间的关系。比如有两行只有第一个输入不同、输出都为 1,这两行其实可以合并成一项,第一个输入被消掉。规范式不会自动做这件事,它老老实实写十个项。
在 FPGA 里,乘积项最终要映射成查找表。四输入查找表能装下任意一个四变量函数,但规范式的十个乘积项再加一个或,通常要拆成多个查找表级联,逻辑级数也变深。级数一深,关键路径变长,主频就上不去。在 ASIC 里更直接:每个乘积项都要一组与门,或门还要一棵树,面积和功耗都跟着涨。
所以化简不是「让公式好看」,而是在改电路的成本。下面用一个具体函数走一遍,从真值表到卡诺图再到最小表达式,每一步都能手工核对。
真值表:最小项、最大项和无关项
真值表把每种输入组合对应的输出列出来。n 个输入有 2 的 n 次方行,每一行叫一个最小项,英文 minterm。最小项的特点是:它是一个「只有这一种输入组合才为 1」的乘积项,每个变量要么原样、要么取反,一个都不能少。四变量最小项 m5 写成 A'BC'D,只有 A=0、B=1、C=0、D=1 时它才为 1。
把输出为 1 的那些最小项或起来,得到「最小项之和」,英文 Sum of Products,简称 SOP。这是最直白的写法,也是很多教科书默认的规范式。反过来,把输出为 0 的行写成或项再相与,得到「最大项之积」,Product of Sums,简称 POS。最大项在那一行输入下为 0,其余为 1。更严格的布尔代数推导,包括德摩根律和范式之间的转换,在命题逻辑那一篇里。
还有一种行叫无关项,英文 don't-care,记作 X 或 d。它表示「这组输入在现实里不会出现,或者出现了也不关心输出」。比如温度超限和门磁打开在机械上互斥,那这组组合就永远不会来。无关项在化简时是自由的:需要它当 1 就當 1,需要它当 0 就当 0,怎么让表达式更短就怎么用。但它在最终电路里仍然是一个真实的输入组合,不能假设它一定安全。
SOP 和 POS:两种写法,两种代价
SOP 是「先与后或」,对应电路是与门阵列加一个或门;POS 是「先或后与」,对应或门阵列加一个与门。两者在逻辑上等价,但项数和级数可能差很多。一个函数如果大部分行为 1,只有少数行为 0,用 POS 把 0 圈起来往往更省;反过来,1 少的函数用 SOP 更省。
SOP 更符合「事件触发」的直觉:哪几种条件成立就输出,读起来像需求清单。POS 像排除法,读起来反直觉。工程代码里 SOP 更常见,但综合工具两种都会试,最后选面积和时序更好的。
规范式不是终点。它每一项都含全部变量,文字最多;化简要减少项数和每项的文字数,这两个目标有时冲突,项最少不一定文字最少,文字最少不一定级数最浅。工程上先看综合后的时序和面积,再选折中。
布尔代数与卡诺图:一个靠推,一个靠看
布尔代数化简靠公式推导。常用的是这几条:A 与 1 等于 A,A 与 0 等于 0,A 或 1 等于 1,A 或 0 等于 A;A 与 A' 等于 0,A 或 A' 等于 1;还有吸收律 A 或 AB 等于 A,以及德摩根律。代数法适合变量少、结构明显的式子,也适合在代码里手工变形,但它很依赖眼力,项一多就容易漏。
卡诺图是布尔代数的图形版。真值表排成方格,相邻格只差一个变量,可合并的两行在图上正好挨着。不用背公式,把 1 圈成尽量大的矩形,每个矩形读一个乘积项,全部或起来就是结果。它把找可合并项从代数推导变成空间识别,对人工化简很友好。
两者的关系可以这样理解:卡诺图的每一个圈,背后都是一次代数合并;圈得越大,消掉的变量越多。卡诺图不是另一种数学,它只是把代数过程画了出来。也正因为如此,卡诺图只适合变量少、人眼能看全的场合。
卡诺图怎么画:格雷码、圈组和边界
卡诺图的坐标不是普通二进制顺序,而是格雷码顺序:00、01、11、10。这样排的目的是让相邻两格只差一位,注意 01 和 11 只差最高位,11 和 10 只差最低位。如果按 00、01、10、11 排,中间两格差两位,就不能合并,图就失去意义了。
圈组有三条硬规则。第一,每组格数必须是 2 的幂,1、2、4、8、16,不能圈 3 格或 6 格。第二,每组必须是矩形,可以跨行跨列,但不能拐弯。第三,图的四条边是相连的,最上行和最下行相邻,最左列和最右列相邻,四个角也互相相邻。很多人漏解,就是忘了边和角能连。
下面这张四变量卡诺图,行是 AB,列是 CD,都按格雷码排。格子里填的是输出值,X 是无关项。这个函数来自一个四路告警逻辑:1 表示该亮灯,0 表示不亮,X 表示机械上不会出现的组合。
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | X | 1 |
| 01 | 0 | 1 | 1 | 1 |
| 11 | 0 | 0 | X | 1 |
| 10 | 1 | 1 | X | 1 |
先把 1 和可以当 1 的 X 一起圈。图上有三个圈:AB 为 00 和 10 的两整行,八格,跨上下边界;CD 为 11 和 10 的两整列,八格,跨左右边界;AB 为 00、01 与 CD 为 01、11 交出的四格。三个圈覆盖所有 1,允许重叠,也把 X 用上了。
| 圈 | 覆盖的格子 | 消掉的变量 | 读出的项 |
|---|---|---|---|
| 上下两整行 | AB=00 与 AB=10 的全部列,八格 | 消掉 A 和 C、D 的变化 | B' |
| 左右两整列 | CD=11 与 CD=10 的全部行,八格 | 消掉 A、B、D 的变化 | C |
| 四格方块 | AB=00、01 与 CD=01、11 的交集 | 消掉 B 和 C | A'D |
读出项的方法:圈里保持不变的变量保留,变化的变量消掉;变量为 1 写原样,为 0 写取反。第一圈里 B 一直是 0,A、C、D 都在变,所以只剩 B'。第二圈里 C 一直是 1,其余在变,所以是 C。第三圈里 A 一直是 0、D 一直是 1,B 和 C 在变,所以是 A'D。
从图到表达式:十项四十个文字,压到三项四个文字
把三个项或起来,得到最小表达式:F 等于 B' 或 C 或 A'D。规范式有十个最小项,也就是十个乘积项、四十个文字;化简后三个乘积项、四个文字。这个差距不是理论上的,落到电路上就是与门阵列从十组变成三组,或门输入从十个变成三个。
用 Python 跑一遍 Quine-McCluskey 化简,输出的质蕴含项正好是这三项:C、B'、A'D。脚本还穷举了十六种输入,把化简式的计算结果和原始最小项表逐项比对,除无关项以外没有不一致。规范式那边统计出来是十项、四十个文字,和手算一致。
prime implicants:
--1- : C (1 literals)
-0-- : B' (1 literals)
0--1 : A'D (2 literals)
chosen cover:
B'
A'D
C
total literals: 4
mismatches vs spec (don't-cares ignored): []
canonical SOP minterms: 10
canonical literals: 40
canonical product terms: 10
换个写法验证也可以。下面这段 Python 直接按化简式算十六种输入,输出是一个长度十六的列表,位置就是最小项编号。你可以拿它和上面的卡诺图逐格对照,X 的位置在这里被当成 1 处理,所以第三、十一、十五位也是 1。这是化简时「借用了无关项」的结果,不代表真实电路必须让这三组输入亮灯。
def f(a, b, c, d):
return int((not b) or c or ((not a) and d))
print([f((m >> 3) & 1, (m >> 2) & 1, (m >> 1) & 1, m & 1) for m in range(16)])
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1]
无关项怎么用,才不会用出问题
无关项的价值在「扩大圈」。孤立的 1 只能圈一格,读一个四文字项;旁边有 X 就能圈成两格,消掉一个变量。X 越多,可圈的空间越大,表达式可能短很多,所以带无关项的设计化简收益更明显。
但无关项不能滥用。X 只在化简阶段自由,真实电路仍会给它确定输出,触发危险动作时必须显式处理。而且「不会出现」只是设计假设,传感器故障、接线错误、上电瞬态都可能打破它。安全相关的逻辑,宁可把 X 导向报警或停机,也别让工具为省两个门随意取值。
卡诺图的边界:五变量以上为什么不好画
二变量四格、三变量八格、四变量十六格,都还能一眼看全。五变量三十二格,通常画成两张四变量图,第三维用一层区分,相邻关系要跨图看。六变量六十四格,四张图叠起来,人眼记不住谁和谁相邻,手画的错误率比代数法还高。
五变量以上交给算法。Quine-McCluskey 精确但计算量随变量数指数增长,变量一多跑不动;Espresso 是启发式,不保证全局最优但速度快,综合工具常用这一类。FPGA 映射还会结合查找表结构优化,不只求最简 SOP。
所以「什么时候值得画卡诺图」有个实用判断:不超过四变量,或者五六个变量但结构规整、只想快速看几个大圈,可以手画;变量更多或需要严格最优,直接写代码、跑工具、看报告。卡诺图是理解和检查的工具,不是大规模设计的生产工具。
等价表达式不等于等价电路:险象
两个表达式在真值表上一样,电路却可能不一样。最典型的是静态 1 险象:输出本应保持 1,输入变化的一瞬间掉到 0,过一小段延迟又回来。原因是两条路径延迟不同,一条先断、另一条后通,中间出现空档。
比如 F 等于 A'B 或 AC。B、C 都为 1 时,无论 A 是 0 还是 1,输出都该是 1。可 A 从 1 变到 0,AC 先失效,A'B 要过一个非门和与门才生效,中间就出现短暂的 0。在卡诺图上,这表现为两个圈相邻,但相邻边界没有被同一个圈覆盖。
解决办法是加冗余项。加 BC 后,B、C 都为 1 时它恒为 1,把空档补上。BC 逻辑上多余,电路上必要。所以「最简表达式」不一定最适合直接实现:组合输出直接接异步输入时要考虑险象;后面接触发器,毛刺在时钟边沿前稳定下来,就未必是问题。
现象对照:这些症状先查哪儿
下面这些现象在写组合逻辑、跑综合、上板调试时很常见。表里给的是第一反应,不是完整流程,但能帮你少绕几圈。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 照真值表写,综合资源比预期多几倍 | 用了规范式,没有合并可化简的最小项,也没利用无关项 | 看综合报告的查找表数量和逻辑级数,对比化简后的表达式 |
| 仿真对,上板偶尔出现窄毛刺 | 组合逻辑存在静态险象,两条路径延迟不同 | 示波器看输出跳变,检查卡诺图上相邻圈是否共边 |
| 卡诺图圈完,表达式和真值表对不上 | 漏了边界相邻,或把含 0 的格圈进去了 | 按格雷码重排坐标,逐格核对圈内是否只有 1 和 X |
| 五变量卡诺图越画越乱 | 两张图之间的相邻关系没标清,人眼跟踪不了 | 改用 Quine-McCluskey 或 Espresso,别硬画 |
| 同一功能两种写法,时序一个过一个不过 | 逻辑级数和扇出不同,关键路径延迟不同 | 看综合后的级数、扇出和时序报告,不只看门数 |
| 无关项在仿真里是 X,上板却是 0 或 1 | 仿真把 X 当未知,综合把 X 当可优化项,语义不一致 | 显式写出 default 分支,别让工具替你决定 |
| 化简后门少了,反而更容易误触发 | 最简式去掉了冗余项,险象暴露到输出 | 检查输出是否直接进异步端口,必要时加冗余项或打一拍 |
边界与代价
第一,化简目标不单一。门数最少、文字最少、级数最浅、功耗最低经常互相拉扯。卡诺图的最简 SOP 只优化「与项数加文字数」,不一定最快,真实设计要看工具在目标工艺上的映射结果。
第二,卡诺图假设输入同时到达。实际有布线延迟、扇出差异、信号完整性问题,两个输入不会真同时变。化简只处理逻辑关系,处理不了物理时序,这也是险象的根源,高速设计因此更依赖寄存器和时序约束。
第三,无关项是设计假设,不是物理事实。用 X 省下的门,可能在故障组合里变成错误输出。安全、医疗、汽车这类场景宁可多花几个门,也要把不会出现的组合导向确定状态,可靠性优先。
第四,工具不是万能的。综合工具求的是最优映射,不是人类可读,可能把你清楚的表达式改得面目全非,也可能为时序复制逻辑。看报告关注资源、级数、时序、功耗,不必和源码逐行对应。
第五,手工化简仍然值得学。写代码前就能估出大概要多少门、关键路径在哪,工具结果异常时也能判断是源码还是约束问题。下一篇的选择器、译码器、编码器,本质是把真值表固化成标准模块,理解化简后看它们会轻松很多。
今天就能验证的五个练习
- 把本文的四变量函数抄到纸上,自己画一次卡诺图,圈出三个组,再和文中的表逐格核对。重点检查上下边界和左右边界有没有漏。
- 用 Python 写一个四变量真值表枚举,把 F 等于 B' 或 C 或 A'D 的结果打印成十六个数,和文中的列表比对。
- 把无关项改成 0,再化简一次,看看表达式会变成几项、几个文字。体会无关项对面积的影响。
- 构造一个静态 1 险象的例子,用两级门延迟模型仿真,观察输出在输入切换时是否出现窄脉冲;再加上冗余项,看脉冲是否消失。
- 找一个自己写过的多条件判断,把它改写成真值表,数一数原始写法有多少个乘积项,再试着合并。比较合并前后的条件数量和可读性。
收束:先想清楚,再让工具动手
真值表是把需求变成逻辑的第一种语言,最小项和无关项是它的词汇表;SOP 和 POS 是两种句式,各有各的代价。布尔代数适合推导,卡诺图适合肉眼找相邻,四变量以内手画很值,五变量以上交给算法。化简能省门、省级数、省功耗,但它优化的是逻辑,不是物理时序;等价表达式可能藏着险象。
下一篇从「一张表」走到「一个标准模块」:多路选择器、译码器、编码器,这三种组合逻辑器件几乎出现在所有数字系统里。它们的功能都能用真值表描述,但真正有意思的是怎么用少量门拼出来、怎么级联、以及拼接时会在哪里冒出险象。