第4章 组合逻辑设计（分析与综合）

一、导读

1.1 本章学习目标

掌握组合逻辑电路的基本特征：输出仅取决于当前输入，不具有记忆功能

熟练运用真值表、布尔表达式和逻辑电路图三种描述方法之间的相互转换

掌握组合逻辑电路的分析方法：从电路结构推导出逻辑功能

掌握组合逻辑电路的综合方法：从功能需求设计出实现电路

熟练使用卡诺图（Karnaugh Map）进行逻辑函数的化简

理解最小项、最大项、标准与或式和标准或与式的概念

了解冒险现象（Hazard）的成因、分类和消除方法

理解无关项（Don't Care）在逻辑化简中的应用

1.2 为什么本章如此重要

组合逻辑设计是数字设计的核心技能之一。在数字系统中，组合逻辑电路承担着数据通路处理、控制信号生成、地址译码、算术运算等关键功能。从最简单的逻辑门到复杂的处理器中的数据通路，组合逻辑无处不在。掌握组合逻辑的分析和综合方法，是每一位数字设计工程师的基本功。

组合逻辑的分析与综合构成了一个完整的设计闭环。分析是从已有电路出发，理解其功能行为的过程——给定电路结构，推导输出与输入的关系。综合则是从功能需求出发，设计出实现该功能的电路的过程——给定输入输出关系，构建最优的电路结构。这两个方向的能力缺一不可：分析能力帮助你理解现有设计和排查故障，综合能力帮助你创造新的设计。

卡诺图化简方法是组合逻辑设计中最经典的工具之一。虽然对于变量超过六个的函数，计算机辅助的化简算法（如Quine-McCluskey算法和ESPRESSO算法）更为实用，但卡诺图提供的直观几何视角对于培养逻辑化简的直觉仍然不可替代。理解卡诺图的工作原理，有助于深入把握逻辑函数中"蕴含项"、"质蕴含项"和"最小覆盖"等核心概念。

冒险现象是组合逻辑设计中一个容易被忽视但后果严重的问题。由于信号在不同路径上的传播延迟不同，即使逻辑功能在稳态下是正确的，在瞬态过程中也可能出现短暂的错误输出。在高速数字系统中，这些毛刺（Glitch）可能被下游的时序元件捕获，导致系统功能错误。理解冒险的成因并掌握消除方法，是设计可靠组合逻辑电路的必要条件。

1.3 核心问题引导

组合逻辑电路和时序逻辑电路的根本区别是什么？如何判断一个电路是组合逻辑还是时序逻辑？

从真值表到最简逻辑表达式的过程中，卡诺图相比代数化简法有什么优势？

什么是质蕴含项（Prime Implicant）？为什么逻辑化简的目标是找到质蕴含项的最小覆盖？

无关项（Don't Care）为什么可以帮助进一步化简逻辑函数？在实际设计中，无关项从何而来？

冒险现象在什么条件下会发生？静态冒险和动态冒险有什么区别？

为什么两级逻辑实现（与-或、或-与）在速度上有优势？多级逻辑实现有什么权衡？

当逻辑函数的变量超过六个时，卡诺图方法面临什么困难？有什么替代方案？

二、核心概念详解

2.1 组合逻辑电路的分析方法

组合逻辑电路分析的目标是确定给定电路的逻辑功能，即建立输出与输入之间的函数关系。分析过程通常遵循以下步骤：首先，从电路图中识别所有输入和输出变量；然后，从输入到输出逐级推导每个门的输出表达式；最后，将所有中间表达式代入，得到输出关于输入的完整布尔表达式。

分析结果可以用多种方式表示。布尔表达式给出了输出与输入之间的代数关系，便于进行数学分析和化简。真值表则穷举了所有可能的输入组合及其对应的输出值，提供了最完整但也最冗长的功能描述。对于n个输入变量的电路，真值表有2^n行，因此当变量较多时，真值表会变得非常庞大。

在实际工程中，分析还常常涉及时序特性的考察。信号从输入变化到输出稳定需要经历一定的传播延迟，这个延迟是各级门延迟的累加。在关键路径上，传播延迟决定了组合逻辑电路的最大工作速度。

2.2 组合逻辑电路的综合方法

组合逻辑电路综合是从功能需求出发设计电路的逆向过程。综合的标准流程为：首先，从文字描述或行为规格中提取输入输出关系，建立真值表；然后，从真值表写出标准布尔表达式（最小项之和或最大项之积）；接着，使用卡诺图或代数方法化简逻辑表达式；最后，根据化简结果画出逻辑电路图。

从真值表写出布尔表达式有两种标准形式。最小项之和（Sum of Minterms，SOP）形式：对于每个使输出为1的输入组合，写出对应的最小项（所有变量的与项），然后将所有最小项求或。最大项之积（Product of Maxterms，POS）形式：对于每个使输出为0的输入组合，写出对应的最大项（所有变量的或项），然后将所有最大项求与。

选择SOP还是POS形式取决于哪种形式包含更少的项。如果真值表中1的个数少于0的个数，SOP形式更简洁；反之则POS形式更简洁。化简后的目标是用最少的逻辑门和最少的门输入数实现所需功能，以降低硬件成本和传播延迟。

2.3 卡诺图化简方法

卡诺图（Karnaugh Map，K-map）是一种图形化的逻辑函数表示和化简工具。它将真值表的信息重新排列在一个二维网格中，使得逻辑上相邻的最小项在几何位置上也相邻。卡诺图的核心原理是利用了布尔代数中的相邻项合并规则：两个只有一个变量不同的与项可以合并为一个更简单的与项，消去那个不同的变量。

卡诺图的画法规则：n变量的卡诺图有2^n个小方格，每个方格对应一个最小项。方格的排列遵循Gray码顺序，确保相邻方格（包括上下左右边界的循环相邻）之间只有一个变量不同。二变量卡诺图是2x2的网格，三变量是2x4，四变量是4x4。

化简过程就是在卡诺图上画圈：用矩形圈住2^k个相邻的1方格（k=0,1,2,...），每个圈对应一个化简后的与项。圈越大，对应的与项越简单（包含的变量越少）。化简的目标是用最少的圈覆盖所有的1方格，每个圈尽可能大。

质蕴含项（Prime Implicant）是指不能被更大的圈包含的圈。本质蕴含项（Essential Prime Implicant）是指覆盖了至少一个不被其他任何质蕴含项覆盖的1方格的质蕴含项。最小覆盖的构造策略是：首先选择所有本质蕴含项，然后用最少的额外质蕴含项覆盖剩余的1方格。

2.4 冒险现象与消除

冒险（Hazard）是组合逻辑电路中由于信号传播延迟差异而导致的瞬态错误现象。即使逻辑函数在稳态下是正确的，在输入变化的瞬间，由于不同路径上的门延迟不同，输出可能出现短暂的错误脉冲（毛刺）。

静态冒险（Static Hazard）分为静态-1冒险和静态-0冒险。静态-1冒险是指输出在稳态下应保持为1，但在输入变化的瞬间短暂变为0。静态-0冒险则相反，输出应保持为0但短暂变为1。静态冒险发生在两个相邻最小项之间只有一个变量变化时，且这两个最小项没有被同一个圈覆盖。

动态冒险（Dynamic Hazard）是指输出在从0变1（或从1变0）的过程中，出现多次跳变（如0-1-0-1）的现象。动态冒险通常发生在多级逻辑电路中，信号通过多条不同长度的路径到达输出端。

消除冒险的方法主要有三种：第一，增加冗余项（Consensus Term）——在卡诺图中，为相邻但不被同一圈覆盖的1方格对增加一个额外的圈，确保所有相邻的1方格对都被至少一个共同的圈覆盖。第二，使用选通脉冲（Strobe）——在输出不稳定期间禁止输出，等待所有信号稳定后再采样。第三，在寄存器电路中，使用同步采样避免毛刺被时序元件捕获。

2.5 无关项的应用

无关项（Don't Care）是指在实际应用中不会出现或输出值无关紧要的输入组合。在真值表和卡诺图中，无关项用"X"或"d"表示。无关项的强大之处在于它既可以当作1也可以当作0，取决于哪种选择能使化简结果更简单。

无关项的来源有多种情况。在某些编码系统中，部分编码组合不会被使用。例如，用四位二进制数表示十进制数字（BCD码）时，1010至1111这六个组合是无关项。在某些应用中，特定的输入组合由于物理约束不可能出现。还有时候，输出在某些输入条件下的值不影响系统功能。

在卡诺图化简中，无关项可以灵活地被纳入或排除出圈，以获得最大的化简效果。合理利用无关项可以显著减少逻辑门的数量和电路的复杂度。

三、深入分析与讨论

3.1 多级逻辑优化

两级逻辑实现（如与-或两级）虽然结构简单、无冒险问题（如果设计正确），但可能使用过多的门和过多的输入。对于变量较多的函数，两级实现中单个门可能需要几十个输入，这在物理上是不可实现的。

多级逻辑实现通过将两级结构分解为多个层次，可以显著减少总的门输入数。但多级实现引入了新的问题：传播延迟增加（因为信号需要经过更多级门）、冒险分析更加复杂（多级路径增加了冒险的可能性）、优化空间更大但搜索难度也更高。

现代逻辑优化工具（如ESPRESSO）使用启发式算法在多级结构中寻找近似最优的解。这些工具能够处理数千个变量和数百万个最小项的函数，远超人脑和卡诺图的能力范围。

3.2 从布尔代数到算法化简

卡诺图在变量数不超过六时非常有效，但当变量更多时，图形方法变得不切实际。Quine-McCluskey算法是一种系统化的表格方法，可以处理任意数量的变量。该算法通过迭代地合并相邻最小项来生成所有质蕴含项，然后使用Petrick方法或行支配法找到最小覆盖。

然而，Quine-McCluskey算法的时间复杂度是指数级的，对于大规模函数不实用。ESPRESSO算法采用启发式策略，不追求严格的最优解，而是在可接受的时间内找到接近最优的解。ESPRESSO及其改进版本是目前工业界最常用的逻辑最小化工具。

四、实践案例

4.1 七段显示译码器的设计

七段显示器是最常见的数字显示设备之一，由七个LED段（a至g）组成，可以显示0至9十个数字。七段显示译码器是一个典型的组合逻辑电路，将BCD输入（四位）转换为七个段控制信号。

设计过程：首先建立真值表，四个输入（A3A2A1A0）对应十个有效BCD码（0000至1001），六个无关项（1010至1111）。七个输出分别对应七个段。然后为每个输出画四变量卡诺图，利用无关项进行化简。最后得到每个段的最简逻辑表达式并实现电路。

通过合理利用六个无关项，许多段的逻辑表达式可以大幅简化。例如，段a的表达式可以化简为A3 + A1 + A2'A0' + A2A0，仅需要几个门即可实现。

4.2 四人投票电路的设计

设计一个四人投票电路，当至少三人投赞成票时输出为1。设四个输入为A、B、C、D，输出为F。

建立真值表：在16种输入组合中，使F=1的组合为：1110、1101、1011、0111、1111共5个。写出最小项之和表达式，画四变量卡诺图。化简后得到F = ABC + ABD + ACD + BCD，这是一个对称的三输入与或表达式，可以用四个三输入与门和一个四输入或门实现。

这个设计没有无关项可以利用，且化简结果已经是最简形式。电路的传播延迟为两级门的延迟之和。如果输入信号变化频繁，需要检查是否存在冒险现象。

五、常见误区与注意事项

误区一：化简后的电路一定比未化简的电路更好。 化简减少了门数量和门输入数，但可能增加逻辑级数。在某些情况下，未化简的两级实现虽然门数较多，但传播延迟更小（只有两级），更适合高速应用。设计时需要根据具体约束（面积、速度、功耗）做出权衡。

误区二：卡诺图中圈越大越好，所以应该尽量画最大的圈。 虽然每个圈应尽可能大（以减少与项中的变量数），但更重要的是用最少的圈覆盖所有1方格。有时使用多个中等大小的圈比使用一个很大的圈加上许多小圈更有效。

误区三：冒险只在理论分析中有意义，实际电路中可以忽略。 在低频应用中，冒险产生的毛刺持续时间极短（纳秒级），通常不会影响系统功能。但在高速电路中，毛刺可能被时钟边沿捕获，导致严重的功能错误。特别是在将组合逻辑输出连接到触发器输入的设计中，必须认真处理冒险问题。

误区四：所有组合逻辑电路都需要消除冒险。 实际上，只有当组合逻辑的输出直接连接到异步清零/置位端或被时序元件采样时，冒险才需要被消除。如果组合逻辑的输出仅驱动其他组合逻辑的输入（最终由同步系统采样），冒险通常不会造成问题。

六、本章小结

本章系统介绍了组合逻辑电路的分析和综合方法。分析是从电路到功能的过程，综合是从功能到电路的过程。真值表、布尔表达式和逻辑电路图是三种互补的描述方式。卡诺图提供了直观的逻辑化简手段，质蕴含项和本质蕴含项的概念指导我们找到最优覆盖。冒险现象揭示了实际电路中传播延迟对逻辑功能的影响，增加冗余项和使用选通脉冲是消除冒险的有效方法。无关项的合理利用可以进一步简化电路。这些分析和综合技能是数字设计的核心能力，为后续章节中更复杂的组合逻辑模块和时序逻辑设计奠定了坚实基础。

七、思考题与练习

分析一个由两个二输入与门、一个或门和一个非门组成的电路（输入A和B分别经过非门后与A一起送入与门，B直接与A送入另一个与门，两个与门输出送入或门）。写出输出表达式，画出真值表，并说明该电路实现了什么功能。

使用卡诺图化简以下逻辑函数：F(A,B,C,D) = Sigma m(0,1,2,5,6,7,8,9,10,14)。标出所有质蕴含项和本质蕴含项，写出最简与或表达式。

在上题中，如果增加无关项d(3,11,15)，重新进行化简。比较有无无关项时的化简结果，说明无关项如何帮助简化电路。

设计一个将余3码（Excess-3 Code）转换为BCD码的组合电路。写出真值表，使用卡诺图化简每个输出，并画出逻辑电路图。

解释静态-1冒险和静态-0冒险的区别。对于函数F(A,B,C) = AB + A'C，当输入从ABC=110变为010时，是否存在冒险？如果有，如何通过增加冗余项来消除？

证明：一个组合逻辑电路如果所有信号路径的延迟都相同，则不会产生冒险。为什么在实际电路中这个条件无法满足？

使用Quine-McCluskey算法化简函数F(A,B,C,D) = Sigma m(0,2,4,6,8,10,12,14)。比较该方法与卡诺图方法的优缺点。

设计一个四位比较器，当两个四位二进制数A和A相等时输出1。使用卡诺图分析该设计是否存在冒险，并提出解决方案。