第2章
组合逻辑设计
2.1 引言
电路是一个可以处理离散变量的网络。一个电路可以被看成一个黑盒子。如图2-1所示，其中包括：
- 一个或者多个离散变量输入端（input terminal）；
- 一个或者多个离散变量输出端（output terminal）；
- 描述输入和输出的关系的功能规范（function specification）；
- 描述输入改变时输出响应的延迟的时序规范（timing specification）。
窥视黑盒子的内部，电路由一些节点和元件组成。元件（element）本身又是一个带有输入、输出、功能规范和时序规范的电路。节点（node）是一段导线，它通过电压传递离散变量。节点可分为输入节点、输出节点或内部节点。输入节点接收外部世界的值，输出节点输出值到外部世界。既不是输入节点也不是输出节点的线称为内部节点。如图2-2所示一个带有3个元件和6个节点的电路，E1、E2和E3是三个元件，A、B、C是输入节点，Y和Z是输出节点，n1是E1和E3之间的内部节点。
数字电路可以分为组合（combinational）电路和时序（sequential）电路。组合电路的输出仅仅取决于输入的值，换句话说，它组合当前输入值来确定输出的值。举个例子，一个逻辑门是一个组合电路。时序电路的输出取决于当前输入值和之前的输入值，换句话说，它取决于输入的序列。组合电路是没有记忆的，但是时序电路是有记忆的。这一章重点放在组合电路上，第3章考察时序电路。
组合电路的功能规范表示当前各种输入值情况下所得到的输出值。组合电路的时序规范包括从输入到输出延迟的最大值和最小值。在这一章中，我们首先将集中介绍功能规范，后面部分再回过来学习时序规范。
如图2-3所示，一个组合电路有2个输入和1个输出。在图的左 边是输入节点A和B，在图的右边是输出节点Y。盒子里面的符号表示它只能使用组合逻辑实现。在这个例子中，逻辑功能F被指定为或逻辑：Y=F(A, B)=A+B。简单地说，输出Y是2个输入A和B的函数，即Y=A OR B。
图2-4给出了图2-3中组合逻辑电路的两种可能实现（implementation）。在这本书中，我们将多次看到，一个函数通常存在许多种实现。可以根据配置和设计约束选择给定的模块来实现组合电路。这些约束通常包括面积、速度、功率和设计时间。
图2-5是一个有多个输出的组合电路。这个特殊的组合电路称为全加器（full adder），我们在5.2.1节中会再次遇到。图中的两个式子根据输入A、B和Cin来确定输出S和Cout的函数。
为了简化画图，我们经常用一根信号线表示由多个信号构成的总线（bus），总线上有一根斜线，并在旁边标注一个数字，数字表示总线上的信号数量。例如，图2-6a中的组合逻辑块有3个输入和2个输出。如果总线的位数不重要或者在上下文中很明显，斜线旁可以不标识数字。图2-6b中，两个组合逻辑块有任意数量的输出，一个逻辑块的输出作为下一个逻辑块的输入。
组合电路的构成规则告诉我们如何通过较小的组合电路元件构造一个大的组合电路。如果一个电路由互相连接的电路元件构成，在满足以下条件时，它就是组合电路。
- 每一个电路元件本身都是组合电路；
- 每一个电路节点或者是一个电路的输入，或者是连接外部电路的一个输出端；
- 电路不能包含回路：经过电路的每条路径最多只能经过每个电路节点一次。
例2.1 组合电路。根据组合电路的构成规则，图2-7所示电路中哪些是组合电路？
解：图2-7a是组合电路。它由2个组合电路元件构成（反向器I1和I2）。它有3个节点：n1、n2和n3。n1是整个电路和I1的输入；n2是内部节点，是I1的输出和I2的输入；n3是电路和I2的输出。图2-7b不是组合电路，因为它存在回路：异或门的输出反馈到一个输入端。因此，从n4开始通过异或门到n5再返回到n4是一个回路。图2-7c是组合电路。图2-7d不是组合电路，因为节点n6同时连接I3和I4的输出端。图2-7e是组合电路，表示了两个组合电路连接而构成一个大的组合电路。图2-7f不遵循组合电路的构成规则，因为它有一个回路通过2个元件。它是否为组合电路需要视元件的功能而定。
像微处理器这样的大规模电路非常复杂，我们可以用第1章介绍的原理来管理复杂性。可以应用抽象和模块化原则将电路视为一个明确定义了接口和功能的黑匣子。可以应用层次化原则由较小的电路构建复杂电路。组合电路的构成规则应用了约束原理。
一个组合电路的功能规范通常描述为真值表或者布尔表达式。在后续章节中，我们将介绍如何通过真值表得到布尔表达式，如何使用布尔代数和卡诺图来化简表达式，并将说明如何通过逻辑门实现逻辑表达式，以及如何分析这些电路的速度。
2.2 布尔表达式
布尔表达式处理的变量是真或假，所以它很适合描述数字逻辑。本节中定义一些布尔表达式中常用的术语，然后介绍如何为给定真值表的逻辑功能写出布尔表达式。
2.2.1 术语
一个变量A的非（complement），是它的取反，记为A。一个变量或它的取反被称为项（literal）。比如，A、A、B和B是项。我们称A为变量的真值形式（true form，也称为真形式），A为取反形式（comp-lementary form，也称为假形式）。“真值形式”不表示A为真，仅仅是A的上面没有线。
一个或者多个项的“与”被称为乘积项（product）或者蕴涵项（implicant）。AB、ABC和B都是3变量函数的蕴涵项。最小项（minterm）是包含全部输入变量的乘积项。ABC是输入为A、B、C的3变量函数的一个最小项，但是AB不是最小项，因为它不包含C。同样，一个或者多个项的“或”被称为求和项（sum）。最大项（maxterm）是包含全部输入项的和。A+B+C是输入为A、B、C的3变量函数的一个最大项。
在解释布尔表达式时，其顺序很重要。布尔表达式Y=A+BC表示Y=(A OR B) AND C，还是表示Y=A OR (B AND C)？在布尔表达式中，“非”的优先级最高，接着是“与”，最后是“或”。对于一个普通的等式，乘积在求和之前执行。所以，等式被读为Y=A OR (B AND C)。式（2.1）给出了解释顺序的另外一个例子。
2.2.2 与或式
有N个输入的真值表包含2N行，每一行对应了输入变量的一种可能取值。真值表中的每一行都与一个为真的最小项相关联。如图2-8所示为一个有2个输入A和B的真值表，给出了每一行对应的最小项。比如，第一行的最小项是AB，这是因为当A=0，B=0时，AB取值为真。最小项从0开始标号，第一行对应最小项0（m0），紧接着下面一行对应最小项1（m1），依此类推。
可以用输出Y为真的所有最小项之和的形式写出任意一个真值表的布尔表达式。比如，在图2-8圈起来的区域中仅仅存在一行（一个最小项）Y的输出为真，即Y=AB。图2-9的真值表中有多行Y的输出为真。取每一个被圈起来的最小项之和，可以得出：Y=AB+AB。
因为这种形式是由若干积（“与”构成了最小项）的和（“或”）构成，所以被称为一个函数的与或式（sum-of-products）范式。虽然有多种形式表示同一个函数，比如图2-9的真值表可以写为Y=BA+BA，但可以将它们按照在真值表中出现的顺序进行排序，因此同一个真值表总是能写出唯一的布尔表达式。
与或式范式也可以使用求和符号写成连续相加的形式。应用这种表示法，图2-9表达的函数可以写成如下形式：
或
例2.2 与或式。Ben正在野炊，如果天气下雨或者那儿有蚂蚁，Ben将不能享受到野炊的快乐。设计一个电路，当其输出为真时表示Ben可以享受野炊。
解：首先定义输入和输出。输入为A和R，它们分别表示有蚂蚁和下雨，有蚂蚁时A是真，没有蚂蚁时A为假。同样，下雨时R为真，不下雨时R为假。输出为E，表示Ben可以享受野炊。如果Ben享受野炊，E为真，如果Ben没能去野炊，E为假。图2-10表示Ben野炊经历的真值表。
使用与或式，我们写出的等式如下：。可以用2个反向器和2个与门来实现等式，如图2-11a所示。读者可能发现这个真值表是1.5.5节中出现的或非函数：E=A NOR
。图2-11b表示或非操作。在2.3节中，我们将介绍
和
这两个等式是等价的。
对具有任何多变量的真值表可以用与或式写出唯一的布尔表达式。图2-12表示一个3输入真值表。它的逻辑函数的与或式如下：
但是，与或式并不一定能产生最简等式。在2.3节中，我们将介绍如何用较少的项写出同样的函数。
2.2.3 或与式
布尔函数的第二种表达式是或与式（product-of-sums）范式。真值表的每一行对应了为假的一个最大项。比如，2输入真值表的第一行的最大项为(A+B)，这是因为当A=0，B=0时，(A+B)为假。我们可以直接通过真值表中每一个输出为假的最大项相与而得到电路的布尔表达式。或与式范式也可以使用求积符号写成连续相乘的形式。
例2.3 或与式。为图2-13中的真值表写出一个或与式的表达式。
解：真值表中有2个行输出为假，所以函数可以写成或与式：Y=(A+B)(A+B)，或者使用符号表示，Y=(M0, M2)或Y=(0, 2)。第一个最大项为(A+B)，在A=0且B=0时，任何值与0相与都等于0，这保证了Y=0。同样，第二个最大项为(A+B)，在A=1且B=0时，保证了Y=0。图2-13和图2-9是相同的真值表，表明可以用多种方法写出同一个函数。
同样，图2-10表示Ben野炊的布尔表达式，可以将圈起来的三个为0的行写成或与式，得到E=(A+R)(A+R)(A+R)或E=(1, 2, 3)。它比与或式的E=AR要复杂，但这两个等式在逻辑上是等价的。
当真值表中只有少数行输出为真时，与或式可以产生较短的等式。当真值表中只有少数行输出为假时，或与式比较简单。
2.3 布尔代数
前面的章节中学习了如何通过给定的真值表写出布尔表达式。但是，表达式不一定能导出一组最简逻辑门。就像用代数来化简数学等式一样，也可以用布尔代数来化简布尔表达式。布尔代数的法则很类似于普通的代数，而且在某些情形下更加简单，这是因为变量只有0和1这两种可能的值。
布尔代数以一组事先假定正确的公理为基础。公理是不用证明的，在某种意义上说，就像定义不能被证明一样。通过这些公理，我们可以证明布尔代数的所有定理。这些定理有较大的实用意义，因为它们指导我们如何去化简逻辑来生成较小而且成本更低的电路。
布尔代数的公理和定理都服从对偶原理。如果符号0和1互换，运算符·（AND）和+（OR）互换，表达式将依然正确。我们用上标来表示对偶式。
2.3.1 公理
表2-1给出了布尔代数的公理。这5个公理和它们的对偶式定义了布尔变量，以及非、或、与的含义。公理A1表示布尔变量B要么是1，要么是0。公理对偶式A1表示变量要么是0，要么是1。A1和A1告诉我们只能对布尔量（二进制量）0和1进行操作。公理A2和A2定义了非操作。公理A3到A5定义了与操作，它们的对偶式A3到A5定义了或操作。
2.3.2 单变量定理
表2-2中的定理T1到T5描述了如何化简包含一个变量的等式。
同一性定理T1表示对于任何布尔变量B，B AND 1=B，它的对偶式表示B OR 0=B。如图2-14所示的硬件中，T1的意思是在2输入与门中如果有一个输入总是为1，可以删除与门，用连接输入变量B的一条导线代替与门。同样，T1的意思是在2输入或门中如果有一个输入总是为0，可以用连接输入变量B的一条导线代替或门。一般说来，逻辑门要花费成本、功耗和延迟，用导线来代替门电路是有利的。
零元定理T2表示B和0相与总是等于0。所以，0被称为与操作的零元，因为它使任何其他输入的影响无效。对偶式表明，B和1相或总是等于1。所以，1是或操作的零元。在硬件电路中，如图2-15所示，如果一个与门的输入是0，我们可以用连接低电平（0）的一条导线代替与门。同样，如果一个或门的输入是1，我们可以用连接高电平（1）的一条导线代替或门。
重叠定理T3表示变量和它自身相与就等于它的本身值。同样，一个变量和它自身相或等于它的本身值。从拉丁语语源给出了定理的名字：同一的和强有力的。这个操作返回和输入相同的值。如图2-16所示，重叠定理也允许用一根导线来代替门。
回旋定理T4说明对一个变量进行两次求补可以得到原来的变量。在数字电子学中，两次错误将产生一个正确结果。串联的两个反相器在逻辑上等效于一条导线，如图2-17所示。T4的对偶式是它自身。
互补定理T5（图2-18）表示一个变量和它自己的补相与的结果是0（因为它们中必然有一个值为0）。同时，对偶式表明一个变量与它自己的补相或的结果是1（因为它们中必然有一个值为1）。
2.3.3 多变量定理
表2-3中的定理T6～T12描述了如何化简包含多个变量的布尔表达式。
交换律T6和结合律T7与传统代数相同。交换律表明“与”或者“或”函数的输入顺序不影响输出的值。结合律表明特定输入的分组不影响输出结果的值。
分配律T8与传统代数相同。但是它的对偶式T8不同。在T8中“与”的分配高于“或”，在T8中“或”的分配高于“与”。在传统代数中，乘法分配高于加法但是加法分配不高于乘法。于是(B+C)×(B+D)≠B+(C×D)。
吸收律T9、合并律T10和一致律T11允许消除冗余变量。读者应能通过思考自己证明这些定理的正确性。
德·摩根定理T12是数字设计中非常有力的工具。该定理说明，所有项的乘积的补等于每个项各自取补后相或。同样，所有项求或的补等于每个项各自取补后相与。
根据德·摩根定理，一个与非门等效于一个带反相输入的或门。同样，一个或非门等效于一个带反相输入的与门。图2-19显示了与非门和或非门的德·摩根等效门。每个函数的这两种表达式称为对偶式。它们是逻辑等效的，可以相互替换。
反相圆圈也可称为气泡（bubble）。你可以直观地设想，推一个气泡通过一个门使它从门一边输入，在另一边输出，可以将与门替换成或门，反之亦然。例如，图2-19中的与非门是在输出端包含气泡的与门。推一个气泡到左边会导致一个输入端带有气泡，并将与门变成或门。下面是推气泡的规则：
- 向后推输出端的气泡或者向前推输入端的气泡，需要将与门换成或门，反之亦然；
- 从输出端推气泡返回到输入端，把气泡放置在门的输入端；
- 在所有门的输入端向前推气泡，把气泡放置在门的输出端。
2.5.2节中将使用推气泡的方法分析电路。
例2.4 推导或与式。图2-20给出布尔函数Y的真值表，以及它的反。使用德·摩根定理，通过
的与或式，推导出Y的或与式。
解：图2-21圈起来的部分表示了中的最小项，
的与或式为：
等式两边同时取反，并应用德·摩根定理两次，我们可以得到
2.3.4 定理的统一证明方法
好奇的读者可能想知道如何证明定理的正确性。在布尔代数中，证明有限变量定理的方法很简单：只需要证明针对变量的所有可能取值定理都保持正确。这个方法叫作完全归纳法，可以通过一个真值表完成证明。
例2.5 使用完全归纳法证明一致性定理。证明表2-3中的一致性定理T11。
解：核对等式两边的B、C和D的8种组合。图2-22中的真值表列出了它们的组合。由于在所有可能中均有，定理得证。
2.3.5 等式化简
布尔代数定理有助于化简布尔表达式。例如，考虑图2-9中的真值表的与或式：Y=AB+ AB。应用定理T10，等式可以化简为Y=B。这在真值表中是显而易见的。通常情况下，针对较复杂的式子需要多个步骤分步化简。
化简与或式的基本原则是使用关系PA+PA=P来合并项，其中P可以是任意蕴涵项。一个等式可以化简到什么地步呢？我们称使用了最少蕴涵项的等式为最小的与或式。对于蕴涵项数量一样的多个等式，含有最少项的为最小与或式。
如果蕴涵项不能和其他任意的蕴涵项合并生成一个含有更少变量的形式，那么此蕴涵项称为主蕴涵项。最小等式中的蕴涵项必须都是主蕴涵项。否则，就可以合并来减少项的数量。
例2.6 化简等式。化简表达式（2.3）：。
解：我们从原等式开始，如表2-4所示一步一步地运用布尔定理。
在这个起点上我们完全化简等式了吗？让我们进一步仔细分析。通过原等式，最小项仅仅在变量A上不同，于是我们可以合并最小项为
。继续观察原等式，我们注意到最后两个最小项
同样只有一个项不同（C和
）。因此，应用相同的方法可以合并这两个最小项为
。我们称蕴涵项
共同分享了最小项
。
于是，我们是仅仅化简这两个最小项对中的一个，还是都进行化简？应用重叠定理，可以复制我们想要的项：B=B+B+B+B…。运用这个原理，我们可以完全化简等式为两个主蕴涵项BC+AB，如表2-5所示。
展开一个蕴涵项（比如，将AB变成）是化简表达式的常用技巧（虽然它有一点违反直觉）。通过展开一个蕴涵项，可以重复一个展开的最小项和其他的最小项合并。
读者可能注意到，完全使用布尔代数定理来化简布尔表达式可能带来很多错误。2.7节介绍的称为卡诺图的化简技术会使处理简单一些。
为什么要花费精力化简逻辑表达式呢？化简减少了物理实现逻辑功能所需门的数量，从而使得实现电路更小、更便宜，可能还更快。下一节将介绍如何用逻辑门实现布尔表达式。
2.4 从逻辑到门
电路原理图（schematic）描述了数字电路的内部元件及其相互连接。例如，图2-23中的原理图表示了前面所讨论过的逻辑函数（式（2.3））的一种可能硬件实现。
原理图需要遵循一致的风格，使得它们更加易于阅读和检查错误，通常遵循以下准则：
- 输入在原理图的左边或者顶部；
- 输出在原理图的右边或者底部；
- 无论何时，门必须从左至右流；
- 最好使用直线而不是有很多拐角的线（交错的线需要浪费精力考虑如何走线）；
- 走线总是在T交叉点连接；
- 在两条线交叉的地方有一个点，表示它们之间有连接；
- 在两条线交叉的地方没有点，表示它们没有连接。
图2-24图示了后三条准则。
任何布尔表达式的与或式可以用系统的方法画成与图2-23相似的原理图。按列画出输入，如果有需要，在相邻列之间放置反相器提供输入信号的补。画一行与门实现每个最小项。为每一个输出画一个或门来连接和输出有关的最小项。因为反相器、与门和或门按照系统的风格排列，这种设计称为可编程逻辑阵列（Programmable Logic Array，PLA），将在5.6节讨论。
图2-25给出了例2.6中布尔代数化简后的实现。与图2-23相比，简化后的电路所需硬件明显减少。而且因其逻辑门的输入更少，简化电路的速度可能会更快。
可以通过利用反相门替代单独反相器的方法进一步减少门的数量。注意到BC是一个带反相输入的与门。图2-26给出了消除C上反相器的优化实现原理图。利用德·摩根定理，带反相输入的与门等效于一个或非门。基于不同的实现技术，使用更少的门或者某几种适合特定工艺的门会更加便宜。例如，在CMOS实现中与非门和或非门优先于与门和或门。
许多电路有多个输出。针对每一个输出分别计算输入的布尔函数。我们可以分别写出每个输出的真值表。但更方便的方法是在一个真值表中写出所有输出，并画出带所有输出的原理图。
例2.7 多输出电路。院长、系主任、助教和寝室室长有时都会使用礼堂。遗憾的是，他们偶尔会发生冲突。比如系主任和一些理事正在礼堂召开一个会议，同一时间，寝室室长正在举行狂欢会。Alyssa要设计一个会议室的预定系统。
这个系统有4个输入量A3，…，A0以及4个输出量Y3，…，Y0。这些信号也可以写成A3:0和Y3:0。当用户要求预定明天的礼堂时将其对应输入设置为真。系统给出的输出中最多有一个为真，从而将礼堂的使用权给优先级别最高的用户。院长在系统中的优先级别最高（3），系主任、助教和室长的优先级别递减。
为系统写出真值表和布尔表达式，画电路来实现这个功能。
解：这个功能称为4输入优先级电路。它的电路符号和真值表如图2-27所示。
可以写出每个输出的与或式，并使用布尔代数来化简等式。根据函数表达式（和真值表）可以很清楚地检查化简后的等式：当A3有效时，Y3是真，于是Y3=A3。当A2有效且A3无效时，Y2是真，所以，。如果A1有效且没有更高优先级的信号有效，Y1为真：
。当A0有效且没有其他信号有效的时候，Y0为真，所以
。图2-28给出了原理图。一个有经验的设计师经常通过观察来实现逻辑电路。对于给定的设计规范，简单地把文字变成布尔表达式，再把表达式变成门电路。
注意到优先级电路中如果A3为真，输出不用考虑其他输入量。我们用符号X表示不需要考虑输出的输入。图2-29中带无关项的4输入优先级电路真值表变得更小了。这个真值表通过无关项X可以很容易地读出布尔表达式的与或式。无关项也能出现在真值表的输出项中，这将在2.7.3节中讨论。
2.5 多级组合逻辑
与或式称为二级逻辑，因为它在一级与门中连接所有的输入信号，然后再连接到一级或门。设计师经常用多于两个级别的逻辑门建立电路。这些多级组合电路使用的硬件比两级组合电路更少。推气泡方法在分析和设计多级电路中尤其有帮助。
2.5.1 减少硬件
当使用两级逻辑时，一些逻辑函数要求数量巨大的硬件。一个典型的例子是多输入的异或门函数。例如，采用我们所学的方法用两级逻辑建立一个3输入的异或门电路。
注意到对于一个N输入异或门，当有奇数个输入为真时输出为真。图2-30表示一个3输入异或门真值表，其中圈起来的行输出为真。通过真值表，可以读出布尔表达式的与或式形式，如等式（2.6）所示。遗憾的是，没有办法来化简这个等式为较小的蕴涵项。
另一方面，A⊕B⊕C=(A⊕B)⊕C（如果有疑问，可以通过归纳法证明）。因此，3输入异或门可以通过串联两个2输入异或门构造，如图2-31所示。
同样，一个8输入异或门的两级与或式逻辑实现需要128个8位输入的与门和一个128位输入的或门。一个更好的选择是使用2输入异或门树，如图2-32所示。
选择最好的多级结构来实现特定逻辑功能不是一个简单的过程。而且，最好的标准有多重含义：门的数量最少、速度最快、设计时间最短、花费最少或功耗最低等。第5章中将看到，在某种工艺中最好的电路在另一种工艺中并不是最好的。比如，我们经常使用的与门和或门，但是在CMOS电路中与非门和或非门更加高效。通过积累一些设计经验，读者对大多数的电路可以通过观察的方法来设计一个好的多级方案。通过学习本书后续部分的电路实例，读者可以获得一些经验。在学习过程中，将探讨各种不同的设计策略并且权衡选择。计算机辅助设计（CAD）工具通常也可以有效地发现更多可能的多级设计，并且按照给定的限制条件寻找一个最好的设计。
2.5.2 推气泡
回忆1.7.6节中介绍的CMOS电路，其与非门和或非门的实现优于与门和或门。但是从带有与非门和或非门的多级电路读出布尔表达式，可能会相当头疼。难以立刻通过观察方法得到图2-33中多级电路的布尔表达式。推气泡可以帮助重画这些电路，消除气泡，并比较容易地确定逻辑功能。根据2.3.3节中的原则，推气泡方法如下：
- 从电路的输出端开始向输入方向推；
- 将气泡从最后的输出端向输入端推，这样读出输出（Y）的布尔表达式，而非输出的补（
）的表达式。
- 继续向后推，以消除每个门的气泡。如果当前的门有一个输入的气泡，则前面门的输出加上气泡。如果当前的门不带输入气泡，前面的门也不带输出气泡。
图2-34显示了如何根据推气泡的规则重画图2-33。从输出Y开始，与非门的输出带有气泡，我们希望去除它。将输出气泡向后推，而产生一个带反相输入的或门，如图2-34a所示。继续向左看，最右边的门有一个输入的气泡，从而可以删除中间与非门的输出气泡，因此这个与非门就不需要变化，如图2-34b所示。中间的门没有带输入气泡，于是可将最左边的门转变成不带输出气泡的，如图2-34c所示。现在电路中除了输入以外的所有气泡都删除了，于是可以通过观察产生基于输入原值或互补值并采用AND或OR方式构成表项。其表达式为：。
为了强调最后一点，图2-35显示了和图2-34电路等效的逻辑电路。内部节点的函数用灰色表示。气泡是串联删除的，可以忽略中间门的输出气泡和最右边门的输入气泡，而产生一个逻辑等效电路图，如图2-35所示。
例2.8 为CMOS逻辑推气泡。很多设计师按照与门和或门来思考，但是假设你需要用CMOS来实现如图2-36所示的逻辑电路，而CMOS逻辑电路偏向于使用与非门和或非门。使用推气泡将电路转变为使用与非门、或非门和非门实现。
解：一个解决方案是用与非门和非门代替每一个与门，用或非门和非门代替每一个或门，如图2-37所示。这种方法需要8个门。注意到这里非门的气泡被画在前面而不是后面，以重点讨论如何删除这些非门。
一个较好的解决方案是：注意到气泡可以添加到门的输出和下一个门的输入而不改变逻辑功能，如图2-38a所示。最后一个与门被改变成一个与非门和一个非门，如图2-38b所示。这个解决方案仅仅需要5个门。
2.6 X和Z
布尔代数被限制为0和1。然而，真实的电路中会出现非法值和浮空现象，分别用X和Z来表示。
2.6.1 非法值X
符号X表示电路节点的值未知（unknown）或非法（illegal），通常发生在此节点同时被0和1驱动的情况下。图2-39显示了这种情况，节点Y同时被高电平和低电平驱动，称为竞争（contention），是必须避免的错误。在竞争节点上的真实电压可能处于0和VDD之间，取决于驱动高电平和低电平两个门的相对强度。它经常但也不总是处于禁止区域。竞争也能导致大电流在两个竞争的门之间流动，使得电路发热并可能损坏器件。
X值有时也被电路模拟器用来表示一个没有初始化的值。比如，忘了明确说明一个输入的值，模拟器将假定它的值是X而发出警告。
回忆2.4节的内容，数字设计师经常使用符号X来表示在真值表中不用关心的值。一定不要混淆这两种意义。当X出现在真值表中时，它表示不重要的值。当X出现在电路中时，它的意思是电路节点有未知或者非法的值。
2.6.2 浮空Z
符号Z表示节点既没有被高电平驱动也没有被低电平驱动。这个节点被称为浮空（floa-ting）、高阻态（high impedance）或者高Z态。一个典型的误解是将浮空或未被驱动的节点和逻辑0等同。事实上，这个浮空的节点可能是0也可能是1，也有可能是在0和1之间的电压。这取决于系统先前的状态。一个浮空节点并不意味着电路出错，一旦有其他电路元件将这个节点驱动到有效电平，这个节点上的值就可以参与电路操作。
产生浮空节点的常见原因是忘记将电压值连接到输入端，或者假定这个没有连接的输入为0。当浮空输入在0和1之间随机变化时，这种错误可能导致电路的行为不确定。实际上，人接触电路时，体内的静电可能足够触发改变。我们就曾经发现只有在学生把一个手指压在芯片上时，电路才能正确运行。
图2-40所示的三态缓冲器（tristate buffer）有3种可能输出：高电平（1）、低电平（0）和浮空（Z）。三态缓冲器有输入端A、输出端Y和使能端E。当使能端为真时，三态缓冲器作为一个简单的缓冲器，传送输入值到输出端。当使能端为假的时候，输出被置为高阻态（Z）。
图2-40中三态缓冲器的使能端是高电平有效：使能端为高电平（1）时缓冲器使能。图2-41给出了低电平有效使能端的三态缓冲器：使能端为低电平（0）时缓冲器使能。为表示信号在低电平时有效，通常在输入上放置一个气泡，也经常在它的名字上面画一条横线（E），或者在它的名字之后添加字母“b”或者单词“bar”（Eb或者Ebar）。
三态缓冲器经常在连接多个芯片的总线中使用。例如，微处理器、视频芯片和以太网芯片都可能需要和个人计算机的存储器通信，每个芯片可以通过三态缓冲器连接共享的存储总线，如图2-42所示。在某个时刻只允许有一个芯片的使能信号有效，并向总线驱动数据。而其他芯片的输出必须为浮空，以防止它们和正与存储器通信的芯片产生竞争。任何芯片在任何时刻都可以通过共享总线来读取信息。这样的三态总线曾经非常普遍。但是，在现代计算机中需要点到点连接（point-to-point link）以获得更高的速度。此时芯片之间就是直接互连而不再通过共享的总线了。
2.7 卡诺图
通过使用布尔代数对几个布尔表达式进行化简，我们发现：如果不小心，有时会得到完全不同的表达式结果，而非最简的表达式。卡诺图（Karnaugh map，K-map）是一个图形化的化简布尔表达式的方法，由贝尔实验室的电信工程师Maurice Karnaugh在1953年发明。卡诺图对处理最多4个变量的问题非常好。更重要的是，它给出了布尔表达式操作的可视化方法。
回忆逻辑化简过程中需要组合不同的项。如果两个项包含同一个蕴涵项P，并包含其他变量A的真和假形式，这两项就可以合并并消去A：PA+PA=P。卡诺图将这些可以合并的项放在相邻的方格中，使得它们很容易被看到。
图2-43显示一个3输入函数的真值表和卡诺图。卡诺图的最上一行给出了输入值A、B的4种可能值。最左边列给出了输入值C的2种可能值。卡诺图中的每一个方格与真值表一行中的输出值Y相对应。比如，最高最左的方格与真值表中的第一行对应，表示当ABC=000时，输出Y=1。就像真值表的每一行一样，卡诺图中的每一个方格代表了一个最小项。图2-43c显示了和卡诺图中每一个方格相对应的最小项。
每一个方格（最小项）和相邻的方格中有一个变量的值不同。这意味着相邻的方格除了一个变量不同以外其他的变量相同，这个变量在一个方格中为真，而在另一个方格中为假。比如，相邻的两个方格代表了最小项ABC和ABC，它们仅仅是变量C不同。读者可能已经注意到在最高行中，A和B按照特殊的顺序组合：00、01、11、10。这种顺序称为格雷码。它与普通的二进制顺序（00、01、10、11）不同，在相邻的项中只有一个变量不同。比如，在格雷码中01到11仅仅是A从0变化成1，在普通的二进制顺序中01到10则是A从0变化成1和B从1变化成0。所以，按照普通二进制的顺序写出组合项不具有相邻方格中只有一个变量不同的性质。
卡诺图也是环绕的。最右边的方格可以和最左边的方格按照只有一个变量A不同的方式进行有效的连接。换句话说，可以拿起图将其卷成一个圆柱体，连接圆柱体的末端成一个圆环，仍然保证了相邻的方格只有一个变量不同。
2.7.1 画圈的原理
图2-43的卡诺图中，仅仅在左边出现了两个为1的最小项ABC和ABC。从卡诺图中读取最小项的方法与直接从真值表读与或式的方法完全相同。
之前，我们用布尔代数将等式化简成与或式。
卡诺图中可用如图2-44所示的图解法化简：将值为1的相邻方格圈起来。对于每一个圈可以写出相应的蕴涵项。2.2节指出，蕴涵项是一个或者多个项的乘积。在同一个圈中同时包含了某个变量的真和假时，该变量可以从蕴涵项中删除。在这种情况下，在圈中变量C的真形式（1）和假形式（0）都在圈中，因此它不包含在蕴涵项中。换句话说，当A=B=0时Y为真，与C的值无关。于是蕴涵项为AB。卡诺图给出了利用布尔代数获得的相同结果。
2.7.2 卡诺图化简逻辑
卡诺图提供了一种简单直观的方式化简逻辑。用尽可能少的圈来圈住卡诺图中所有为1的方格。每一个圈应该尽可能大，然后读取每个圈的蕴涵项。
更加正式地说，布尔表达式写成最少数量的主蕴涵项相或时，布尔表达式得到最终化简。卡诺图中的每一个圈代表一个蕴涵项。最大的圈是主蕴涵项。
例如，图2-44所示的卡诺图中ABC和ABC是蕴涵项，但不是主蕴涵项，只有AB是主蕴涵项。从卡诺图中得到最简化等式的规则如下：
- 用最少的圈来圈住所有的1；
- 圈中的所有方格必须都为1；
- 每一个圈必须是矩形，其每边长必须是2的整数次幂（即1、2或者4）；
- 每一个圈必须尽可能大；
- 圈可以环绕卡诺图的边界；
- 如果可以使用更少数量的圈，卡诺图中一个为1的方格可以被多次圈住。
例2.9 用卡诺图化简3变量函数。假设有一个函数Y=F(A，B，C)，其卡诺图如图2-45所示。用卡诺图化简等式。
解：用尽可能少的圈来圈住卡诺图中为1的值，如图2-46所示。卡诺图中的每个圈代表了一个主蕴涵项，每一个圈的边长都是2的整数次幂（2×1和2×2）。可以通过写出包含在圈中仅仅出现真或假形式的变量来确定每一个圈的主蕴涵项。
例如，在2×1的圈中，B为真和为假的形式包含于圈中，于是主蕴涵项中不包含B。仅仅A的真（A）和C的假（）在这个圈中，可以得出这些变量的主蕴涵项为
。同样，在2×2的圈中圈住了B=0的全部方格。于是主蕴涵项为
。
注意，为了使主蕴涵项最大，右上角的方格（最小项）被覆盖了两次。这等效于布尔代数*享最小项来减少蕴涵项大小的化简技术。同样需要注意的是卡诺图边上4个方格的圈。
例2.10 7段数码管显示译码器。7段数码管显示译码器（seven-segment display decoder）通过4位数据的输入D3:0，产生7位输出以控制发光二极管来显示数字0～9。这7位输出一般称为段a到段g，或者Sa～Sg，如图2-47所定义。这些数字的显示由图2-48给出。写出针对输出Sa和Sb的4输入真值表，并用卡诺图化简布尔表达式。假设非法的输入值（10～ 15）不产生任何显示。
解：表2-6给出了真值表。例如，输入为0000将点亮除Sg以外所有的数码管。
这7个输出分别是关于4个变量的独立函数。输出Sa和Sb的卡诺图如图2-49所示。注意行和列都按照格雷码顺序排列：00、01、11、10，因此相邻方格中只有一个变量不同。在方格中写输出量时，也必须记住这个顺序。
接着，圈住主蕴涵项。用最少数量的圈来圈住所有的1。一个圈可以圈住边缘（水平方向和垂直方向），一个1可以被圈住多次。图2-50显示了主蕴涵项和化简的布尔表达式。
注意包含最少变量的主蕴涵项不是唯一的。比如，在Sa的卡诺图中0000项可以沿着1000项圈起来，以产生最小项。这个圈也可以用0010代替，产生最小项
，如图2-51中的虚线所示。
图2-52描述了一个产生非主蕴涵项的常见错误：用一个单独的圈来圈住左上角的1。这个最小项是，它给出的与或式不是最小的。这个最小项应该和相邻的较大圈组合，如之前的图2-50和图2-51所示。
2.7.3 无关项
2.4节中介绍了真值表无关项。当一些变量对输出没有影响时可以减少表中行的数量。无关项表示成符号X，它的意思是输入可能是0或者1。
当输出的值不重要或者相对应的输入组合从不出现时，无关项也会出现在真值表的输出中。由设计师决定这些输出是0还是1。
在卡诺图中，无关项可以进一步帮助化简逻辑。如果可以用较少或较大的圈覆盖1，这些无关项也可以被圈起来。但如果它们没有用，也可以不被圈起来。
例2.11 带有无关项的7段数码管显示译码器。不考虑非法输入值10～15产生的输出，重复例2.10。
解：卡诺图如图2-53所示，X表示无关项。因为无关，所以可以为0或者1，如果它允许用较少或较大的圈来覆盖住1，我们就圈住这些无关项。被圈起来的无关项被认为是1，反之，没有被圈起来的无关项为0。观察Sa中环绕四个角的2×2方格是如何圈起来的，利用无关项可以很好地来化简逻辑式。
2.7.4 小结
布尔代数和卡诺图是两种逻辑化简方法。最终的目标都是找出开销最低的特定逻辑函数实现方法。
在现代的数字设计实践中，逻辑综合（logic synthesis）软件通过逻辑函数的描述来产生化简电路，这将在第4章中介绍。对于大的问题，逻辑综合比人工方法更高效。对于小问题，有经验的设计者可以通过观察的方法来找出好的解决方案。作者在现实工作中没有使用卡诺图来解决实际问题。但是通过卡诺图获得的洞察力很有价值，并且卡诺图也经常出现在工作面试中。
2.8 组合逻辑模块
组合逻辑电路经常被组成一个更大的模块以实现更复杂的系统。这是抽象原理的一个应用：隐藏不重要的门级细节，把重点放在模块的功能上。我们已经学习了三种组合逻辑模块：全加器（2.1节）、优先电路（2.4节）和7段显示译码器（2.7节）。在这一节，我们将介绍两种更常用的组合逻辑模块：多路选择器和译码器。第5章中将介绍其他的组合逻辑模块。
2.8.1 多路选择器
多路选择器（multiplexer）是一种最常用的组合逻辑电路。它根据选择（select）信号的值从几个可能的输入中选择一个作为输出。多路选择器有时简称为mux。
1. 2:1多路选择器
图2-54中给出了2:1多路选择器的原理图和真值表。它有两个输入D0和D1、一个选择输入S和一个输出Y。多路选择器根据选择信号的值在两个输入数据中选择一个作为输出：如果S=0，Y=D0；如果S=1，Y=D1。S也称为控制信号（control signal），因为它控制多路选择器如何操作。
一个2:1多路选择器可以由与或逻辑实现，如图2-55所示。多路选择器的布尔表达式可以通过卡诺图或者通过分析得到（如果S=1 AND D1=1或者S=0 AND D0=1，则Y=1）。
多路选择器也可以由三态缓冲构建，如图2-56所示。安排三态门使能信号使得在任何时刻仅有一个三态缓冲有效。当S=0时，三态门T0有效，允许D0输出到Y；当S=1时，三态门T1有效，允许D1输出到Y。
2.更宽的多路选择器
一个4:1多路选择器有4个数据输入和1个输出，如图2-57所示。需要2位选择信号以在4个输入数据中进行选择。4:1多路选择器可以使用与或逻辑构建，也可以使用三态门或多个2:1多路选择器构建，如图2-58所示。
三态门的使能项可以用与门和非门组成，也可以用2.8.2节中介绍的译码器组成。
8:1和16:1等更宽的多路选择器可以由如图2-58所示的扩展方法构造。总之，N:1多路选择器需要log2 N位选择线。好的实现选择还是取决于具体的实现技术。
3.用多路选择器实现逻辑
多路选择器可以用查找表（lookup table）的方式实现逻辑功能。图2-59中用一个4:1多路选择器实现2输入的与门。输入A和B作为选择信号。多路选择器的数据输入根据真值表中相应行的值（0或者1）相连。总之，一个2N个输入的多路选择器可以通过将合适的输入连接到0或者1的方法实现任何的N输入逻辑函数。此外，通过改变数据的输入，多路选择器可以被重新编程来实现其他的函数。
稍微考虑一下，我们能够将多路选择器的大小减少一半：仅仅使用一个2N-1个输入的多路选择器来实现任何N输入逻辑函数。方法是将一个变量像0或1一样作为多路选择器的输入。
图2-60进一步说明了这个原理。该图用2:1多路选择器分别实现了2输入与函数和异或函数。我们从一个普通的真值表开始，然后合并成对的行，通过用变量表示输出来消除最右边的输入变量。比如，与门的情况，当A=0时，不管B取何值，Y=0；当A=1时，如果B=0，则Y=0，如果B=1，则Y=1，于是可以得到Y=B。按照这个更小的新真值表，我们可以将多路选择器作为一个查找表来使用。
例2.12 用多路选择器实现逻辑。Alyssa需要实现函数完成她的毕业设计。但是，当她查看实验工具箱时，发现只剩下一个8:1多路选择器。她如何实现这个函数？
解：如图2-61所示，Alyssa使用一个8:1多路选择器来实现这个函数。多路选择器充当了一个查找表，真值表中的每一行和多路选择器的一个输入相对应。■
例2.13 再次用多路选择器实现逻辑。在期末报告前，Alyssa打开电路的电源，结果将8:1多路选择器烧坏了（由于前一天整晚没有休息，她意外地用20V电压代替5V电压供电）。她请求她的朋友将余下的元器件给她。他们给了她一个4:1多路选择器和一个非门。她如何只用这些部件构造新电路？
解：通过让输出取决于C的值，Alyssa将真值表减少到4行。（她也尝试过重新排列真值表的列，使输出取决于A或B的取值。）图2-62给出了新的设计。
2.8.2 译码器
译码器有N个输入和2N个输出。它的每一个输出都取决于输入的组合。图2-63给出了一个2:4译码器。当A1:0=00时Y0=1，当A1:0=01时Y1=1，等等。输出称为独热（one-hot）状态，因为在给定的条件下恰好只有一个输出为高电平。
例2.14 译码器的实现。用与门、或门和非门实现一个2:4译码器。
解：使用4个与门来实现一个2:4译码器的电路如图2-64所示。每一个门输出依赖于所有输入的真或假形式。总之，一个N:2N的译码器可以由2N个N输入的与门通过接收所有输入的真或者假形式的各种组合值构成。译码器的每一个输出代表了一个最小项。比如，Y0代表最小项。这在和其他数字模块一起使用时会很方便。
用译码器实现逻辑
译码器可以和或门组合在一起来实现逻辑函数。图2-65显示了用一个2:4译码器和一个或门来实现一个2输入XNOR函数。由于译码器的每一个输出都代表一个最小项，函数将以所有最小项的或形式来实现。在图2-65中，Y=AB+AB=A⊕B。
当使用译码器来构造逻辑电路时，很容易将函数表示成真值表的形式或者标准与或式。一个包含了M个输出为1的N输入函数，可以通过一个N:2N译码器和M输入或门实现。在5.5.6节中，这个概念将应用到只读存储器中。
2.9 时序
本章前面我们主要关心在使用最少数量门的理想状态下电路是否工作。但是，任何经验丰富的电路设计师都认为电路设计中最具有挑战性的问题是时序（timing）：如何使电路运行得最快。
一个输出响应输入的改变而改变需要一定时间。图2-66显示了缓冲器的一个输入改变和随后输出的改变之间的延迟。这个图称为时序图（timing diagram），描绘了输入改变时缓冲器电路的瞬间响应（transient response）。从低电平到高电平的转变称为上升沿。同样，从高电平到低电平的转变称为下降沿（在图中没有显示）。灰色的箭头表示Y的上升沿由A的上升沿所引起。在输入信号A的50%点到输出信号Y的50%点之间测量延迟。50%点是信号在转变过程中电压处于高电平和低电平之间中间点的位置。
2.9.1 传输延迟和最小延迟
组合逻辑电路的时序特征包括传输延迟（propagation delay）和最小延迟（contamination delay）。传输延迟tpd是输入改变直到对应的一个或多个输出达到最终的值所经历的最长时间。最小延迟tcd是一个输入发生变化到任何一个输出开始改变的最短时间。
图2-67用深灰色和浅灰色分别显示了一个缓冲器的传输延迟和最小延迟。图中显示在特定时间内A的初值是高电平或者低电平，并开始变化为另一状态。我们只对值的改变过程感兴趣，而不关心值是多少。Y在稍后时间将对A的变化做出响应，并产生变化。弧形表示在A发生转变tcd时间后Y开始改变，在tpd时间后Y的新值稳定下来。
电路产生延迟的深层次原因包括：电路中电容充电所需要的时间和电信号以光速传播。为此，tpd和tcd的值可能不同，包括：
- 不同的上升和下降延迟。
- 多个输入和输出之间的延迟可能有所不同。
- 当电路较热时速度会变慢，较冷时会变快。
计算tpd和tcd需要更低抽象级的知识，超出了本书的范围。但是芯片制造商通常提供数据手册以说明每个门的延迟。
根据已经列举出的各种因素，传输延迟和最小延迟也可以由一个信号从输入到输出的路径来确定。图2-68给出了一个4输入逻辑电路。关键路径（critical path）是从A或者B到输出Y。因为输入通过了3个门才传输到输出，所以它是最长的一条路径，也是最慢的路径。这个路径成为关键路径，是因为它限制了电路运行的速度。最短路径（short path）是从输入D到输出Y。因为从输入通过1个门就到输出，所以此路径是最短的路径，也是通过电路的最快路径。
组合电路的传输延迟是关键路径上每一个元件的传输延迟之和。最小延迟是最短路径上每个元件的最小延迟之和。这些延迟如图2-69所示，也可由下列等式描述：
例2.15 延迟计算。Ben需要计算图2-70中的传输延迟和最小延迟。根据数据手册，每个门的传输延迟和最小延迟分别为100ps和60ps。
解：Ben首先确定电路中的关键路径和最短路径。关键路径是从输入A或者B通过3个门到输出Y，在图2-71中用灰色（粗线）标出。所以，tpd是单个门传输延迟的3倍，即300ps。
最短路径是从输入C、D或者E通过2个门到达输出Y，在图2-72中用灰色（粗线）标出。在最短路径上有2个门，所以tcd是120ps。
例2.16 多路选择器的时序：比较控制关键路径和数据关键路径。比较2.8.1节中图2-58所示3种4输入多路选择器的最坏情况时序。表2-7列出了元件的传输延迟。每一种设计的关键路径是什么？选择一个你认为好的设计，并且给出时序分析。
解：如图2-73和图2-74所示，3种设计方法的关键路径都用灰色标出。tpd_sy表示从输入S到输出Y的传输延迟；tpd_dy表示从输入D到输出Y的传输延迟；tpd是这两个延迟的最坏情况，即max(tpd_sy，tpd_dy)。
图2-73中的两个设计都用两级逻辑电路和三态门实现。关键路径都是从控制信号S到输出信号Y：tpd=tpd_sy。因为关键路径是从控制信号到输出的，所以它是控制关键（control critical）电路。任何对控制信号的附加延迟都将直接增加最坏情况下的延迟。图2-73b中从D到Y的延迟只有50ps，对比从S到Y的延迟有125ps。
图2-74显示了用两级2:1多路选择器分层实现一个4:1的多路选择器。关键路径是任意一个D输入到输出Y。其关键路径是从数据输入到输出（tpd=tpd_dy），所以它是数据关键（data critical）电路。
如果数据输入在控制输入之前到达，我们将倾向于具有最短控制-输出延迟的设计（图2-74中分层的设计）。同样，如果控制信号在数据信号之前到达，我们将选择具有最短数据-输出延迟的设计（如图2-73b中的三态设计）。
最好的设计选择不仅取决于通过电路的关键路径和输入到达的时间，而且取决于功耗、成本、可用性等诸多因素。
2.9.2 毛刺
到目前为止，我们已经讨论了一个输入信号的改变导致一个输出信号的改变。但是，一个输入信号的改变可能会导致多个输出信号的改变。这被称为毛刺（glitch）或者冒险（hazard）。虽然毛刺通常不会导致什么问题，但是了解它们的存在和在时序图中识别它们也是很重要的。图2-75显示了一个会产生毛刺的电路和其卡诺图。
布尔表达式的最小化是正确的，考察图2-76中当A=0，C=1，B从1变成0时会发生什么情况。最短的路径（用浅灰色显示）通过与门和或门两个门。关键路径（用深灰色显示）通过一个反相器以及与门和或门两个门。
当B从1变成0，n2（在最短路径上）在n1（在关键路径上）上升之前下降。直到n1上升前，两个输入到或门都是0，输出Y下降到0。当n1最后上升后，Y的值回到1。时序图如图2-76所示，Y的值从1开始，结束时也为1，但是存在暂时为0的毛刺。
只要读取输出之前的等待时间和传输延迟一样长，出现毛刺就不会有问题，这是因为输出最终将稳定在正确的值。
可以在已有实现中增加门电路来避免毛刺。这从卡诺图中最容易理解。图2-77显示了从ABC=011变成ABC=001时B上输入的改变使得从一个主蕴涵项圈移到另外一个。这个变化穿过了卡诺图中两个主蕴涵项的边界，从而可能会产生毛刺。
从时序图2-76中可以看出，在一个主蕴涵项的电路开启之前，如果另一个主蕴涵项的电路关闭，就会产生毛刺。为了去除毛刺，可以增加一个新的覆盖主蕴涵项边缘的圈，如图2-78所示。根据一致性定理，新增加的项AC是一致的或者多余的。
图2-79是一个防止毛刺出现的电路，其中增加了一个灰色的与门。现在当A=0和C=1时，即使B变化也不会输出毛刺，这是因为在整个变化过程中这个与门始终输出为1。
总之，一个信号的变化在卡诺图中穿越两个主蕴涵项的边缘时会导致毛刺。我们能够通过在卡诺图中增加多余的蕴涵项盖住这些边缘以避免毛刺。这当然以增加额外的硬件成本为代价。
然而，多个变量同时发生变化也会导致毛刺。这些毛刺不能通过增加硬件来避免。由于多数系统都会有多个输入同时发生（或者几乎同时发生）变化，毛刺在大多数电路中都存在。我们虽然已经介绍了一种避免毛刺的方法，但讨论毛刺的关键不在于如何去除它们，而是要意识到毛刺的存在。这一点在示波器和模拟器上看时序图时非常重要。
2.10 总结
数字电路是一个带离散电压值输入和输出的模块。它的规范描述了模块实现的功能和时序。这一章我们将重点放在组合电路上，其输出仅仅取决于当前的输入量。
组合电路的功能可以通过真值表或者布尔表达式确定。每个真值表的布尔表达式可以通过系统地使用与或式或者或与式获得。与或式中，布尔表达式写成一个或者多个蕴涵项的或（OR）。蕴涵项是各个项的与（AND）。项是输入变量的真值或取反形式。
布尔表达式可以使用布尔代数中的规则化简。特别是，组合包含了某个变量的真值和取反形式的两个蕴涵项可以化简成最简的与或式：PA+PA=P。卡诺图是化简最多含4个变量函数的图形化方法。通过训练，设计师总是能够将布尔表达式化简成只含最少变量的形式。计算机辅助设计工具也常用于处理更加复杂的函数，我们将在第4章中介绍更多的这类方法和工具。
连接逻辑门来构造组合电路，实现所希望的功能。任何表达式的与或式可以通过两级逻辑实现：非门实现输入的取反，与门实现变量的与，或门实现变量的或。根据不同的功能和可用的模块，以各种类型的门为基础的多级逻辑实现会更加高效。例如，CMOS电路更加有利于与非门和或非门，因为这些门可以直接用CMOS晶体管来实现而不需要额外的非门。当使用与非门和或非门时，推气泡有助于跟踪取反的过程。
逻辑门可以组合在一起构造更大规模的电路，例如多路选择器、译码器和优先级电路等。多路选择器根据选择信号来选择输出一个输入数据。译码器根据输入将多个输出中的一个设置为高电平。优先级电路产生表示最高优先级输入的输出。这些电路都是组合电路模块的例子。第5章将介绍更多的组合逻辑模块，包括多种算术电路。这些模块将在第7章微结构中得到广泛的运用。
组合电路的时序包含了电路的传输延迟和最小延迟，它们说明了输入改变和随后的输出改变之间的最长和最短时间。计算电路的传输延迟需要首先确定电路中的关键路径，然后将路径上每一个元件的传输延迟相加。实现复杂的组合逻辑电路有很多方式，这些方式在速度和成本上各有侧重。
下一章将介绍时序电路，它的输出取决于先前的输入和当前的输入。换句话说，时序电路对过去的状态有记忆能力。
习题
2.1 写出图2-80中每个真值表的与或式形式的布尔表达式。
2.2 写出图2-81中每个真值表的与或式形式的布尔表达式。
2.3 写出图2-80中每个真值表的或与式形式的布尔表达式。
2.4 写出图2-81中每个真值表的或与式形式的布尔表达式。
2.5 最小化习题2.1中的布尔表达式。
2.6 最小化习题2.2中的布尔表达式。
2.7 画一个相对简单的组合电路实现习题2.5中的每一个函数。相对简单表示不浪费逻辑门，但也不要浪费大量的时间来检验每一种可能的实现电路。
2.8 画一个相对简单的组合电路实现习题2.6中的每一个函数。
2.9 只使用非门、与门和或门来重做习题2.7。
2.10 只使用非门、与门和或门来重做习题2.8。
2.11 只使用非门、与非门和或非门来重做习题2.7。
2.12 只使用非门、与非门和或非门来重做习题2.8。
2.13 使用布尔代数方法化简下列布尔表达式。用真值表或者卡诺图检验其正确性。
2.14 使用布尔代数方法化简下列布尔表达式。用真值表或者卡诺图检验其正确性。
2.15 画一个相对合理的组合电路实现习题2.13中的每一个函数。
2.16 画一个相对合理的组合电路实现习题2.14中的每一个函数。
2.17 化简下列布尔表达式，画一个相对简单的组合电路来实现化简后的等式。
2.18 化简下列布尔表达式，画一个相对简单的组合电路来实现化简后的等式。
2.19 给出一个行数在30亿和50亿之间的真值表，而此真值表可以用少于40个（至少1个）的2输入门来实现。
2.20 给出一个带有环路但仍然是组合电路的例子。
2.21 Alyssa说任何布尔函数都可以写成最小与或式作为函数的所有主蕴涵项的或。Ben说存在一些函数，它们的最小等式不含有所有的主蕴涵项。解释为什么Alyssa是正确的或者提供一个反例来证明Ben的观点。
2.22 使用完全归纳法证明下列定律。不需要证明它们的对偶式。
（a）重叠定理（T3） （b）分配律（T8） （c）合并律（T10）
2.23 用完全归纳法证明3个变量B2、B1、B0的德·摩根定理（T12）。
2.24 写出图2-82电路中的布尔表达式。不必最小化表达式。
2.25 最小化习题2.24中的布尔表达式，画出一个具有相同功能的改进电路。
2.26 使用德·摩根定理等效门和推气泡方法，重画图2-83中的电路，从而可以通过观察来写出布尔表达式。写出布尔表达式。
2.27 对图2-84中的电路，重做习题2.26。
2.28 写出图2-85中函数的最小布尔表达式，记得要利用无关项。
2.29 画出习题2.28中函数对应的电路图。
2.30 当有一个输入改变的时候，习题2.29中的电路有潜在的毛刺吗？如果没有，解释为什么没有。如果有，写出如何修改电路来消除这些毛刺。
2.31 写出图2-86中函数的最小布尔表达式，记得要利用无关项。
2.32 画出习题2.31中函数对应的电路图。
2.33 Ben将在没有蚂蚁的晴天去野炊。如果他看到蜂鸟，即使野炊的地方有蚂蚁和瓢虫，他也会去野炊。根据太阳（S）、蚂蚁（A）、蜂鸟（H）和瓢虫（L）写出他去野炊（E）的布尔表达式。
2.34 完成7段译码器段Sc到Sg的设计（参考例2.10）：
（a）假设输入大于9时输出均为0，写出输出Sc到Sg的布尔表达式。
（b）假设输入大于9时输出是无关项，写出输出Sc到Sg的布尔表达式。
（c）对（b）画出合理而简单的门级实现。多重输出在合适的地方可以共享门电路。
2.35 一个电路有4个输入、2个输出。输入是A3:0，代表从0～15的一个数。如果输入的数是素数（0和1不是素数，但是2、3、5等都是素数），则输出P为真。如果输入的数可以被3整除，则输出D为真。给出并化简每个输出的布尔表达式，画出电路图。
2.36 一个优先级编码器有2N个输入。它将产生N位二进制输出表示输入为真的最高位，或者在没有任何输入为真时输出0。它还将产生一个输出NONE，在没有输入为真时，该输出为真。设计一个8输入的优先级编码器，输入为A7:0，输出为Y2:0和NONE。例如，输入为00100000时，输出Y将为101，NONE为0。写出并化简每个输出的布尔表达式，画出电路图。
2.37 设计一个新的优先级编码器（参见习题2.36）。它有8位输入A7:0，产生2个3位输出Y2:0和Z2:0。Y指示输入为真的最高位。Z指示输入为真的第二高位。如果没有一个输入为真，则Y为0；如果不多于一个输入为真，则Z为0。给出每一个输出的布尔化简等式，并且画出原理图。
2.38 一个M位温度计码（thermometer code）在最低k位上为1，在最高M-k位上为0。二进制-温度计码转换器（binary-to-thermometer code converter）有N个输入和2N-1个输出。它为输入的二进制数产生一个2N-1位的温度计码。例如，如果输入是110，则输出是0111111。设计一个3:7二进制-温度计码转换器。写出并化简每一个输出的布尔表达式，画出原理图。
2.39 写出图2-87中电路对应函数的最小布尔表达式。
2.40 写出图2-88中电路对应函数的最小布尔表达式。
2.41 请使用下列器件实现图2-80b中的函数：
（a）一个8:1多路选择器
（b）一个4:1多路选择器和一个非门
（c）一个2:1多路选择器和两个其他的逻辑门
2.42 请使用下列器件实现习题2.17（a）中的函数：
（a）一个8:1多路选择器
（b）一个4:1多路选择器和不用任何其他的逻辑门
（c）一个2:1多路选择器、一个或门和一个非门
2.43 确定图2-83中电路的传输延迟和最小延迟。在表2-8中给出了所使用门的延迟。
2.44 确定图2-84中电路的传输延迟和最小延迟。在表2-8中给出了所使用门的延迟。
2.45 画一个快速3:8译码器的原理图。假定门的延迟在表2-8中给出（并且只能使用表2-8中的逻辑门）。设计一个具有最短关键路径的译码器，并指出这些路径是什么。电路的传输延迟和最小延迟是多少？
2.46 设计一个从数据输入到数据输出延迟尽可能小的8:1多路选择器。可以使用表2-7中的任何门。画出电路原理图。基于表2-7中给出的门的延迟，确定电路的延迟。
2.47 重新为习题2.35设计一个尽可能快的电路。只能使用表2-8中的逻辑门。画出新的电路并且说明关键路径。电路的传输延迟和最小延迟是多少？
2.48 重新为习题2.36设计一个尽可能快的优先级编码器。可以使用表2-8中的任何门。画出新的电路并且说明关键路径。电路的传输延迟和最小延迟是多少？
面试问题
2.1 只使用与非门画出2输入或非门函数的原理图，最少需要使用几个门？
2.2 设计一个电路，它将得出一个输入的月份是否有31天。月份用4位输入A3:0指定。比如，输入0001表示1月，输入1100表示12月。当输入的月份有31天时，电路输出Y将为高电平。写出最简等式，使用最少数量的门画出电路图。（提示：记住利用无关项。）
2.3 什么是三态缓冲器？如何使用它？为什么使用它？
2.4 如果一个或者一组门可以构造出任何布尔函数，那么这些门就是通用门。比如，{与门，或门，非门}是一组通用门。
（a）与门是通用门吗？为什么？
（b）{或门，非门}是一组通用门吗？为什么？
（c）与非门是通用门吗？为什么？
2.5 解释为什么电路的最小延迟可能小于（而不是等于）它的传输延迟。