第 13 章　利用逻辑设计计算机元件

优质

小牛编辑

130浏览

2023-12-01

在本章中我们会看到第12章中学习的命题逻辑可以应用到数字电子电路的设计中。这样的电路在每台计算机上都能找到，它们使用两种电压电平（“高”和“低”）表示二进制数值1和0。除了了解设计过程之外，我们还将看到算法设计技巧，比如“分治法”，也可以应用到硬件上。其实，务必意识到设计执行给定逻辑函数的数字电路的过程，从本质上讲与设计执行给定任务的计算机程序的过程是非常类似的。不过二者所使用的数据模型却差异明显，一般来说电路会被设计成并行（同时）处理很多事务，而一般的编程语言都是顺序（一次一步地）执行它们的步骤。不过，像模块化设计这样的通用程序设计技巧也是适用于电路的。

13.1　本章主要内容

本章涵盖了数字电路设计中的以下概念。

门的概念，门是执行某一逻辑运算的电子电路（13.2节）。
门如何被组织成电路（13.3节）。
某些被称为组合电路的电路，它们是逻辑表达式的电子等价物（13.4节）。
电路设计所受的物理约束，以及电路要快速产生答案所必须具备的属性（13.5节）。
两个有趣的电路示例：加法器和多路复用器。13.6节和13.7节展示了如何利用分治法为这两个问题设计执行迅速的电路。
存储单元是一种可以记住其输入的电路，而组合电路则不能记住它之前接收的输入（13.8节）。

13.2　门

门是具有一个或更多输入的电子设备，可以假设各输入要么是值0要么是值1。正如之前提过的，逻辑值0和1通常使用两个不同的电压电平表示，不过这种物理表示方法并不会对我们产生影响。门通常具有一路输出，它是输入的函数，而且它的值也是0或1。

每个门都会计算某个特定的布尔函数。大多数电子“技术”（制造电子电路的方法）有利于为某些布尔函数而不是其他布尔函数构建门。特别要说的是，AND门（与门）和OR门（或门）通常是很容易构建的，NOT门（非门，也称反相器）也是。虽然像13.5节中要讨论的，AND门和OR门可以具有任意数量的输入，但通常会对门所具有的输入加以实际的限制。如果AND门的所有输入都是1，它的输出就是1，而如果它的输入中至少有一个0，则其输出为0。同样，如果OR门的输入中至少有一个是1，那么它的输出是1，如果所有输入都是0，则其输出为0。反相器（NOT门）只有一路输入，如果它的输入是0，那么它的输出为1，而如果其输入为1，则输出是0。

我们还发现，在大多数技术中NAND门（与非门）和NOR门（或非门）也是很容易实现的。只有NAND门的所有输入都是1才产生输出0，否则输出就是1。当NOR门的所有输入为0时，其输入是1，否则它的输入是0。比较难以通过电子方式实现的逻辑函数是等价，该函数接受两路输入x 和y，而且如果x 和y 都是1或都是0，那么产生的输出就是1。而当x 和y 中刚好有一个是1时，输出就是0。不过，我们可以通过实现能够识别逻辑函数 $xy+\overline{x}\ \overline{y}$ 的电路，用AND门、OR门和NOT门构建等价电路。

表示我们提到的门的符号如图13-1所示。除了反相器（NOT门）之外，所示的每种门都具有两路输入。不过，通过添加额外的线，很容易给出两个以上的输入。单输入的AND门和OR门也是可行的，但它们没有什么实际作用，只是把它的输出传递给输出。单输入的NAND门和NOR门其实就是反相器。

图 13-1　表示门的符号

13.3　电路

通过连接某些门的输出与其他门的输入，就可以把门组合成电路。整个电路可能有一个或更多输入，每路输入都可能是电路中若干个门的输入。而一个或多个门的输出会被指定为电路的输出。如果存在多路输出，那么还必须为输出的门指定次序。

示例 13.1

图13-2展示了产生输入x 和y 的等价函数作为输出z 的电路。约定而言，我们把输入放在顶部。输入x 和y 都是提供给门A的，它是个AND门，所以当（且仅当）x+y=1时会产生输出1。此外，x 和y 会分别被NOT门反相，而且这些反相器的输出会被提供给AND门D。因此，当且仅当x 和y 都是0时，门D 的输出是1。因为门A 和门D 的输出会提供给OR门E，我们可以看到当且仅当x=y=1或x=y=0时门E 的输出是1。图13-3中的表给出了对应各门输出的逻辑表达式。

因此，当且仅当逻辑表达式 $xy+\overline{x}\ \overline{y}$ 的值为1时，该电路的输出z（就是门E 的输出）是1。因为该表达式等价于表达式x≡y，我们看到电路的输出是这两路输入的等价函数。

图 13-2　等价电路：z 是表达式x≡y

门	门的输出
A	xy
B	$\overline{x}$
C	$\overline{y}$
D	$\overline{x}\ \overline{y}$
E	$xy+\overline{x}\ \overline{y}$

图 13-3　图13-2中各门的输出

13.3.1　组合电路和时序电路

我们可以利用AND、OR和NOT这样的一系列逻辑运算符写出表达式，而这类表达式与可以用执行同一组运算符的门构建的电路之间存在着密切关系。在继续讲述之前，我们先把注意力集中在一类称为组合电路（combinational circuit）的重要电路上。这些电路是无环的，这种情况下门的输出不能到达其输入，即便是经过一系列中间门。

我们可以利用图的知识来精确定义想通过组合电路表示的含义。首先，画出图中节点对应电路中的门的有向图。如果门u 的输出直接连接到门v 的任何输入，就添加一条弧u →v。如果电路的图中没有环路，那么该电路就是组合电路，否则它就是时序电路。

示例 13.2

在图13-4中，我们看到根据图13-2所示电路画出的有向图。例如，存在弧A→E，因为门A 的输出被连接到门E 的输入。图13-4所示的图显然不含环路，其实，它是以E 为根节点，方向倒置的树。因此，可以得出结论：图13-2所示的电路是组合电路。

图 13-4　根据图13-2中的电路构建的有向图

另一方面，考虑图13-5a的电路。在那幅图中，门A 的输出是门B 的输入，而门B 的输出又是门A 的输入。对应该电路的图如图13-5b所示，它显然具有环路，所以该电路是时序电路。

图 13-5　时序电路及其对应的图

假设该电路的输入x 和y 都是1，那么B的输出就肯定是1，这样AND门A 的两路输入都是1。因此，该门会产生输出1。现在我们可以设输入y 是0，而OR门B 的输出仍然是1，因为它的另一路输入（来自A 的输出的那路输入）是1。因此，A 的输入仍然都是1，而它的输出也还是1。

不过，假设x 变为0，而不管y 是不是0。那么门A 的输出以及电路的输出z 一定是0。如果在过去的某个时刻，x 和y 都是1，而且因此x（但y 不一定）仍然是1，就可以把电路输出z 描述为1。图13-6把若干输入值组合对应的输出表示成了时间的函数，低电平表示0，高电平表示1。

图 13-6　图13-5a所示电路的输出，表示为时间的函数

时序电路和自动机
在第10章讨论过的确定有限自动机与时序电路之间存在密切关系。尽管该主题不在本书要讨论的范围之内，但给定任何确定自动机，我们都可以设计这样一个时序电路。只有当自动机的输入序列被接受时，该电路才输出1。更精确地讲，可能来自任意字符集合的自动机输入，一定要经过合适数量的逻辑输入进行编码，电路的k 个逻辑输入最多可以编码2^k 个字符。

我们将会在本章结尾部分简要讨论一下时序电路。正如我们在示例13.2中看到的，时序电路具备一种能力，可以记住与目前为止所见输入序列有关的重要事项，因此像主存和寄存器这样的计算机关键元件需要它们。另一方面，组合电路可以计算逻辑函数的值，但它们必须处理输入的单个设置，而且没法记住之前的输入被置为什么。不过，组合电路也是计算机的关键元件。组合电路为许多任务所需要，比如把数字相加，把指令解码成使计算机可以执行这些指令的电子信号等。在接下来的几节中，我们将把大多数精力放在组合电路的设计上。

13.3.2　习题

1. 设计产生以下输出的电路，可以利用如图13-1所示的任何门。

(a) 输入x 和y 的奇偶校验（或者说和mod2）函数，当且仅当x 和y 中刚好有一个是1时输出为1。

(b) 输入w、x、y 和z 的多数（majority）函数，当且仅当输入中有3个或3个以上为1时输出是1。

(d) 12.4节习题7中讨论过的异或函数⊕。

2. * 假设图13-5a的电路被修改为门A 和门B 都是AND门，而且输入x 和y 一开始都是1。随着输入改变，在什么情况下输出会是1？

3. * 如果两个门都是OR门，重复习题2。

13.4　逻辑表达式和电路

要构建输出（表示为其输入的函数）与给定逻辑表达式输出相同的电路是相当简单的。反过来，给定组合电路，我们也可以为电路的各路输出（表示为其输入的函数）找到相应的逻辑表达式。而正如我们在示例13.2中看到的，同样的做法并不适用于时序电路。

13.4.1　从表达式到电路

给定具有某些逻辑运算符的逻辑表达式，我们可以根据它构建一个组合电路，该电路使用具有相同运算符的门，而且可以识别相同的布尔函数。我们构造的电路总是具有树的形式，所以可以通过对表达式的表达式树进行结构归纳以构造电路。

依据。如果表达式树是单个节点，该表达式只能是一路输入，比方说x。而该表达式对应的“电路”就会是电路输入x 本身。

图 13-7　对应表达式θ (E₁,E₂,…,E_n )的表达式树

归纳。而对归纳部分，假设所考虑的表达式树像图13-7这样。在根节点位置存在某个被称为θ 的逻辑运算符，例如θ 可以是AND或OR。根节点有n 棵子树，而且要对各子树的结果应用运算符θ 以产生整棵树的结果。

因为我们在进行结构归纳，所以可以假定归纳假设适用于子表达式。因此，存在对应表达式E₁的电路C₁、对应E₂的电路C₂，等等。

要为E构建电路，就要为运算符θ 选择一个门，并为该门提供n 路输入，其中各路输入按照次序分别是电路C₁、C₂、…、C_n的输出。而对应E 的电路的输出来自刚介绍的θ 门，电路构造如图13-8所示。

图 13-8　表示θ(E₁,…,E_n)的电路，其中C_i 是表示E_i 的电路

我们所构建的电路是以显见的方式计算表达式的。不过，也可能存在产生相同输出函数但所使用的门更少或电路层级更少的电路。例如，如果给定的表达式是 $(x+y)z+(x+y)\overline{w}$ ，那么我们构建的电路就会出现两个识别相同表达式x+y 的子电路。我们可以重新设计该电路，从而只使用一个这样的子电路，并为用到子表达式x+y 的其他地方提供该子电路的输出。

要改进电路设计，还可以进行其他更为疯狂的变形。就像高效算法的设计一样，电路设计也是门艺术，而且我们还将在本章后续的内容中看到一些和电路设计有关的重要技巧。

13.4.2　从电路到逻辑表达式

现在来考虑一下相反方向的问题，为组合电路的输出构造逻辑表达式。因为我们知道组合电路的图是无环的，所以可以选定其节点（即电路中的门）的拓扑次序，而且具有如下属性：如果该次序中第i 个门的输出被提供给第 j 个门的输入，那么i 一定小于j。

示例 13.3

图13-2所示电路中的门可能的拓扑次序之一是ABCDE，而另一拓扑次序是BCDAE。不过ABDCE不是拓扑次序，因为门C 要为门D 提供输入，但该序列中D 却出现在C 之前。

要从电路构建表达式，就要使用归纳构造。这里将通过对i 的归纳证明如下命题。

命题 S(i )。对拓扑次序中的前i 个门来说，存在与这些门的输出对应的逻辑表达式。

依据。依据是i=0。因为要考虑的是0个门，就没什么要证明的，所以依据部分是成立的。

归纳。而对于归纳部分，要看看拓扑次序中的第i 个门。假设门i 的输入是I₁、I₂、…、I_k 。如果I_j 是电路的输入x，那么令对应输入I_j 的表达式E_j 是x。如果I_j 是其他某个门的输出，那么该门在该拓扑次序中一定先于第i 个门，这表示我们已经为该门的输出构建了某个表达式E_j。设与门i 相关联的运算符为θ，那么对应门i 的表达式就是θ(E₁,E₂,…,E_k )。在θ 是约定使用中缀表示法的二元运算符的一般情况下，门i 的表达式就可以写为(E₁)θ (E₂)。虽然根据运算符的优先级这两个括号也有可能是不必要的，但为了安全起见还是用了括号。

示例 13.4

现在要利用门的拓扑次序ABCDE 为图13-2所示的电路确定输出表达式。首先，我们要看看AND门A，它的两路输入来自电路的输入x 和y，所以与A 的输出对应的表达式就是xy。

门B 是输入x 的反相器，所以它的输出是 $\overline{x}$ 。同样，门C 的输出是 $\overline{y}$ 。现在可以处理AND门D 了，它的输入是B 和C 的输出。因此，对应门D 输出的表达式为 $\overline{x}\ \overline{y}$ 。最后，门E是OR门，它的输入是A 和D 的输出。因此要把这两个门的输出用OR运算符连接起来，从而得到表达式 $xy+\overline{x}\ \overline{y}$ ，作为对应门E 输出的表达式。因为E 是电路唯一的输出门，所以该表达式也是电路的输出。回想一下，图13-2所示的电路整数是用来识别布尔函数x≡y 的。很容易验证我们为门E 得出的这个表达式与x≡y 是等价的。

示例 13.5

在之前的例子中，我们的电路都只有一路输出，而且电路本身就构成了一棵树。但这些条件一般而言是不成立的。我们现在要介绍一个设计多输出电路的例子，而且其中一些门的输出会用作若干个门的输入。回想一下，第1章中讨论过用一位加法器构建一个计算二进制数字加法的电路。一位加法器电路有表示要相加的两个数字中某一特定位的两路输入x 和y。除此之外，它还有第三路输入c，表示从其右侧相邻位置（低一位的位置）到该位的进位输入。而一位加法器会生成以下两位作为输出。

1. 和值位z，当x、y 和c 中有奇数个是1时它的值为1。

2. 进位输出位d，当x、y 和c 中有两个或三个是1时它的值为1。

在图13-9中，我们看到了对应一位加法器和值函数z 与进位输出函数d 的卡诺图。在8个可能的最小项中，其中有7个出现在对应z 或d 的函数中，而只有一个xyc 是同时出现在两者之中。

{%}

图 13-9　对应和值函数和进位输出函数的卡诺图

图13-10展示了为一位加法器系统设计过的电路。首先要利用顶部的3个反相器为电路的输入反相。然后为输出中所需的各个最小项构建AND门。这些门编号为1到7，而且这些整数表明了它的输入中按次序有哪些是“为真”的电路输入x、y、c，以及有哪些是“互补的”输入， $\overline{x}$ 、 $\overline{y}$ 、 $\overline{c}$ 。也就是说，把这个整数写成3位的二进制数字，并用这几位按次序表示x、y 和c。例如，门4，或者说是(100)_z，其输入x 为真，而输入y 和c 是互补的，也就是说，它产生的输出表达式是 $x\overline{yc}$ 。请注意，这里是没有门0的，因为每路输出都不需要最小项 $\overline{xy}\ \overline{c}$ 。

图 13-10　一位加法器电路

最后，电路的输出z 和d 是由底部的OR门组合的。对应z 的OR门的输入来自最小项中z 为真的各个AND门的输出，而对应d 的OR门的输入也是用类似方式选择的。

现在来为图13-10所示的电路求输出表达式。我们所使用的拓扑次序是反相器在前，接着是AND门1、2、…、7，以及最后的对应z 和d 的OR门。首先，这3个反相器的输出表达式显然是 $\overline{x}$ 、 $\overline{y}$ 和 $\overline{c}$ 。然后，我们已经提过如何为这些AND门选择输入，以及各门输出对应的表达式与门编号的二进制表示之间是如何相关联的。因此，门1的输出表达式就是 $\overline{x}\ \overline{y}c$ 。最后，OR门z 的输出是对门1、2、4、7的输出表达式求OR，也就是

$\overline{x}\ \overline{y}c+\overline{x}y\overline{c}+x\overline{y}\ \overline{c}+xyc$

同样，对应d 的OR门的输出是对门3、5、6、7的输出表达式求OR，即

$\overline{x}yc+x\overline{y}c+xy\overline{c}+xyc$

这里留一道习题给大家，证明该表达式与如下表达式是等价的。

yc+xc+xy

提示一下，如果我们从对应d 的卡诺图着手，就能得到该表达式。

电路图的约定
如果电路像图13-10中所示的那样复杂时，就要拿出一项实用的约定来简化绘图。我们经常需要让“电线”（输出和输入之间的线）交叉，又不表示这些交叉的线是同一条线。因此，电路的标准约定是这样的：除非在线路相交的位置画上一个点，否则相交的线路不是连通的。例如，虽然从电路输入y 出发的垂直线与标号x 或 $\overline{x}$ 的水平线有交叉，但它们是不连通的。它与标号为y 的水平线是连通的，因为在相交的位置画上了点。

13.4.3　习题

1. 为以下布尔函数设计电路。如果可以把由相同运算符连接的3个或更多操作数组合在一起，就不需要限制自己只使用2路输入的门。

(a) x+y+z。提示：将该表达式视为OR(x,y,z)。

(b) xy+xz+yz。

2. 为图13-11中的各电路计算对应各个门的逻辑表达式。电路输出的逻辑表达式又是什么？为电路(b)构造只使用AND、OR和NOT门的等价电路。

3. 证明示例13.4和13.5中用到过的以下重言式。

(a) $(xy+\overline{x}\ \overline{y})\equiv(x\equiv y)$

(b) $(\overline{x}yc+x\overline{y}c+xy\overline{c}+xyc)\equiv(yc+xc+xy)$

芯片
芯片通常含有若干结合起来可用于构建门的材料“层”。线路可以在任何一层布设，把门相互连接起来，不同层上的线路通常可以交叉而不互相影响。在1994年，芯片的“特征尺寸”（大体上就是电线的最小宽度）通常小于二分之一微米（1微米是0.001毫米，或者说大约0.00004英寸）。门可以构建在这若干微米见方的区域中。1
制造芯片的过程是很复杂的。例如，有一步是把薄薄一层光致抗蚀剂（photoresist）沉积在整个芯片上。然后要用到某层上所需功能的底片。通常用光或是电子束照射底片，被电子束直接照射到的那层会被蚀刻掉，只留下所需的电路。

1当今的芯片制造工艺已经达到纳米级的水平。——译者注

图 13-11　习题2的电路

13.5　电路的一些物理限制

现在，很多电路都是以“芯片”或者说集成电路的形式构建的。大量的门，可能有多达数百万的门，以及连接这些门的线路，被构建在一块一厘米见方的半导体和金属材料上。构建集成电路的各种“技术”或者说方法都为设计高效电路之路施加了不少约束。例如，正如我们之前提到的，某些类型的门，比如AND、OR和NOT，就要比其他类型的门更容易构建。

13.5.1　电路速度

对每个门而言，在接收到输入的时间和发送出输出的时间之间都存在延迟。这一延迟可能只有几纳秒（1纳秒是10^-9秒），不过在复杂的电路，比如在计算机的中央处理器中，即便是在执行简单指令时，信息也会在很多层门之间传送。由于现代计算机能在远小于1微秒（即10^-6秒）的时间内执行指令，因此值在传递过程中必经之门的数量显然必须控制到最低限度。

因此，对组合电路而言，任何从输入到输出的路径上安放门的最大数量都是一种衡量性能的标准，就类似于程序的运行时间那样。也就是说，如果我们希望电路能迅速计算输出，就必须把表示电路的图中最长路径的长度减少到最小。电路的延迟是最长路径上门的数量，也就是说，该最长路径的长度加1就是延迟。例如，图13-10所示的加法器延迟是3，因为从输入到输出的最长路径经过了一个反相器，然后是一个AND门，最后经过了一个OR门，这样的路径在该电路中有很多条。

请注意，和运行时间一样，电路延迟也只是一种“数量级”的量。不同的技术会让接受某个门的输入以产生该门输出的过程花费不同的时间。因此，如果有两个延迟分别为10和20的电路，那么可知，如果它们是用相同技术实现，而且其他因素也都相同，那么第一个电路所花的时间就是第二个电路的一半。不过，如果用更快的技术实现第二个电路，那么它有可能战胜用原技术实现的第一个电路。

13.5.2　大小限制

构建电路的开销大致上是与电路中门的数量成正比的，因此我们很乐意减少门的数量。此外，电路的大小也会影响到它的速度，而且小型电路往往运行得更快。一般来说，电路所具有的门越多，芯片上被占据掉的面积就越大。使用较大面积至少有如下两项负面影响。

1. 如果面积较大，就需要较长的线路来连接相隔较远的门。线路越长，信号从线路一端传导到另一端所需的时间就越长。这种传播延迟（propagation delay）是电路中除了门“计算”输出所花时间之外的另一个延迟来源。

2. 芯片的大小也是有限制的，因为芯片越大，就越有可能存在导致芯片不合格的瑕疵。如果把电路分散在若干芯片中，那么连接这些芯片的线路会带来严重的传播延迟。

结论就是，把电路中门的数量控制在较低水平会带来明显的好处。

13.5.3　扇入和扇出限制

电路设计中的第三个限制源自物理现实。如果门具有过多输入，或者门的输出连接到过多的输入，就会为此付出代价。门的输入数被称为扇入（fan-in），而门的输出所连接到的输入的数量就叫作扇出（fan-out）。尽管原则上讲扇入或扇出是存在限制的，但实际应用中，具有较大扇入和（或）扇出的门要比那些扇入和扇出较小的门更慢。因此，我们要试着在设计电路时对扇入和扇出加以限制。

示例 13.6

假设某计算的寄存器是32位的，而且我们想用电路实现COMPARE机器指令。必须构建的内容之一是测试寄存器是否全为0的电路。这一测试使用具有32路输入的OR门实现，每路输入对应寄存器的一位。输入为1就表示该寄存器存放的并不是0，而输出0就意味着它存放的是0。2如果要用1来表示问题“寄存器是否存放着0”的肯定回答，那么就要用反相器或者NOR门来为输出求补。

2严格地讲，这一结论只有在2的补码表示中才成立。在一些其他的表示法中，存在两种表示0的方法。例如，如果用符号幅度来表示，就只需要测试后31位是否为0。

不过，扇入达到32一般来说远高于我们想要的值。假设要限制自己只使用扇入为2的门。这个限制可能太低了，不过这里只是为了举例说明问题。首先要问，如果需要计算n 路输入的OR，那么需要多少个两输入的OR门？显然，每个两输入的门都会把两个值结合成一个值（它的输出），因此会把我们计算n 路输入的OR所需的输入数减1。在使用了n-1个门之后，我们会得到一个值，如果电路设计得当的话，这个值就是所有n 个原来的值的OR。因此，至少需要31个门来计算x₁、x₂、…、x₃₂这32位的OR。

图13-12展示了实现这种OR的一种简单做法。在这种方法中，我们用左结合的方式为这些位分组。各个门的输出会提供给下一个门作为输入，该电路的图中有一条含31个门的路径，因此该电路的延迟是31。

图 13-12　为32位取OR的缓慢方式

图13-13展示了一种更好的方式。具有5层的完全二叉树使用了同样的31个门，不过延迟只有5。因此可以预期图13-13所示电路的运行速度是图13-12所示电路的6倍。其他影响速度的因素可能让这个倍数比6小，但是即便是对32位这样“小”的位数来说，这种聪明设计也明显要比之前的简单设计来得快。

如果不能马上“看出”使用完全二叉树作为电路的技巧，也可以利用分治范例得出图13-13所示的电路。也就是说，要取2^k 位的OR，可以把这些位等分成各含2^k-1位的两组。这两组所对应的电路通过最终的OR门，如图13-14所示。当然，对应依据情况k=1（即两路输入）的电路不是用分治法得到的，而是使用单个两输入的OR门。

{%}

图 13-13　OR门的完全二叉树

图 13-14　把分治法用于电路设计

13.5.4　习题

1. * 假设我们使用扇入为k 的OR门，并且想为n 路输入取OR，其中n 是k 的乘方。这种电路可能达到的最小延迟是多少？如果使用如图13-12所示朴素的“级联”电路，延迟会是多少？

2. * 设计分治电路执行以下运算。每种电路的延迟各是多少？

(a) 给定输入x₁、x₂、…、x_n，当且仅当所有输入都是1时产生输出1。

(b) 给定输入x₁、x₂、…、x_n 和y₁、y₂、…、y_n，当且仅当对i =1、2、…、n 有x_i =y_i 时，输出是1。提示：使用图13-2所示电路测试两路输入是否相等。

3. * 即使输入数不是2的乘方，图13-14中的分治法也是起作用的。那么依据就一定要包括两输入或三输入的集合，三输入集合是由两个OR门处理的，假设我们要把门的扇入严格限制为2，就要用一个门的输出作为另一个门的一路输入。这种电路的延迟是多少，将其表示为输入数量的函数。

4. 正选突击队准备就绪、意志坚定并能够出击。假设有n 个突击队员，而且电路输入r_i、w_i 和a_i 分别表示第i 个突击队员是否准备就绪、意志坚定并能够出击。只有当所有突击队员准备就绪、意志坚定并能够出击时，我们才派该突击队发动袭击。设计分治电路，表示我们能否派该突击队发动袭击。

5. * 候补突击队（顺着习题(4)的思路）没有这么专业。如果各突击队员处在准备就绪、意志坚定或能够出击的状态，就派这支队伍发动袭击。其实，即便至多有一个突击队员既没有准备就绪，也不意志坚定，并且不能够出击，我们也派出这支队伍。使用与习题4一样的输入，设计能表示我们能否派候补突击队发动袭击的分治电路。

13.6　分治加法电路

将两个数字相加的电路是计算机的关键部分之一。尽管实际的微处理器电路所做的事更多，但我们这里要通过设计将两个非负整数相加的电路，研究该问题的本质。这一问题是一个相当有启发性的分治电路设计示例。

我们可以按照若干种连接方法中的某一种，用n 个一位加法器构建n 位数字的加法器。假设使用图13-10所示电路作为一位加法器电路。该电路的延迟是3，接近我们能达到的最低延迟。3最简单的加法器构建方式是我们在1.3节中看到过的行波进位加法器。在该电路中，各一位加法器的输出都要称为下一个一位加法器的输入，所以把两个n 位数字相加会带来3n 的延迟。例如，如果是n=32的情况，那么该电路的延迟就是96。

3通过在全加器之外为所有输入求补，然后在全加器中计算进位和它的补数，就可以设计更为复杂但延迟为2的一位加法器电路。

13.6.1　递归加法电路

如果使用分治策略，设计处理n /2位的电路，并使用两个这样的电路以及其他一些补充电路构成n 位加法器，就可以让设计出的加法器电路的延迟显著减少。在示例13.6中，我们讨论过使用两输入OR门为很多位取OR的分治电路。这是个特别简单的分治法应用示例，因为各个更小的电路执行的刚好是所需的功能（OR），而且子电路的输出组合是非常简单的（它们被提供给OR门）。这两个大小减半的电路可以同时（并行）处理它们的工作，所以它们的延迟不会叠加。

对加法器来说，我们需要完成一些更微妙的工作。比较简单的做法是使用同样的大小减半的加法器电路将左半部分的位（高序位）相加，并把右半部分的位（低序位）相加。不过，与n 位OR的例子中可以独立地处理左半部分和右半部分不同的是，对加法器来说，似乎要在右半部分完成计算，并如图13-15所示把进位传递给左半部分的最右位之后，左半部分才可以开始计算。如果这样的话，我们会发现，这种所谓的“分治”电路其实就和行波进位加法器是一样的，而且根本没有改善延迟。

{%}

图 13-15　无效的加法器分治设计

我们需要认识到的加法“诀窍”是，在要计算的不仅是和的条件下，我们可以在不知道右半部分进位输出的情况下计算左半部分。这里就需要回答两个问题。第一个，如果没有进位进入左半部分的最右位置，和会是多少，以及第二个，如果存在进位输入，和会是多少？4然后就可以让电路的左半部分和右半部分同时计算它们的答案。一般两个部分的计算都已完成，就可以弄清是否有从右半部分到左半部分的进位。这会告诉我们哪个结果是正确的，而且再经过三个单位的延迟，就可以为左边选出正确答案。因此，把n位相加的延迟只比把n/2位相加的延迟多3，这样就使电路的延迟是3(1+log₂n)。对n=32来说，这要比行波进位加法器好很多了，分治加法器的延迟是3(1+log₂32)=3(1+5)=18，而行波进位加法器的延迟是96。

4请注意，“存在进位输入”表示进位输入是1，而“没有进位输入”意味着进位输入是0。

更为准确地讲，我们将n 位加法器定义为具有表示两个n 位整数的输入x₁、x₂、…、x_n 和y₁、y₂、…、y_n 以及如下输出的电路。

1. s₁、s₂、…、s_n，输入的n 位和（不包括最左位置的进位输出，即不包括超出属于x₁和y₁的位置），假设最右的位置（x_n 和y_n 的位置）没有进位输入。

2. t₁、t₂、…、t_n，输入的n 位和，假设最右的位置有进位输入。

3. p，进位传送位（carry-propagate bit），在假设最右位置有进位输入的情况下，如果最左位置存在进位输出，则它的值是1。

4. g，进位发生位（carry-generate bit），即便最右位置没有进位输入，如果最左位置有进位输出，其值为1。

要注意到有g→p，也就是说，如果g 是1，则p 一定是1。不过，g 可以是0，而同时p 仍是1。例如，如果x 是1010…，而y 是0101…，那么g=0，因为在没有进位输入时，求出的和全是1，而且最左位置没有进位输出。另一方面，如果最右位置有进位输入，那么后n 位的和全部是0，而且最左位置有进位输出，因此p=1。

我们要为2的乘方n 递归地构建n 位加法器。

依据。考虑n=1的情况。这里有两路输入，x 和y，而且需要利用以下逻辑表达式计算四路输出s、t、p 和g：

$\begin{align*}&s=x\overline{y}+\overline{x}y\\&t=xy+\overline{x}\ \overline{y}\\&g=xy\\&p=x+y\end{align*}$

要知道这些表达式为什么是正确的，首先要假设所考虑的这个位置没有进位输入。当x、y 和进位输入中有奇数个1时就是1的和值位，在x 和y 中刚好有一个是1的情况下才是1。上述对应s 的表达式显然具有这一属性。此外，在没有进位输入的情况下，只有在x 和y 都是1时才会有进位输出，这就解释了上面对应g 的表达式。

图 13-16　依据情况：一位加法器

现在假设存在进位输入。那么对x、y 和进位输入中有奇数个1的情况，就一定是x 和y同为1或同不为1，这解释了对应t 的表达式。还有，现在如果x 和y 中有一个是1或者两个全是1，就会有进位输出了，这就说明了对应p 的表达式是正确的。对应该依据情况的电路如图13-16所示。它从思路上讲与图13-10所示的全加器是类似的，不过实际上它多少要简单一些，因为它只有两路输入。

归纳。归纳步骤如图13-17所示，其中用两个n 位加法器构建了一个2n 位加法器。2n 位加法器是由两个n 位加法器，加上两块图13-17所示的标号为FIX的电路组成的，其中FIX电路是用来处理以下两个问题的。

1. 为2n 位加法器计算进位传送位和进位发生位。

2. 调整s 和t 的左半部分，以考虑是否具有从右半部分到左半部分的进位。

图 13-17　分治加法器设计草图

首先，假设2n 位加法器整个电路的右端有进位输入。然后，如果以下两个条件有任何一个成立，那么整个电路左端会有进位输出。

(a) 加法器的左半部分和右半部分都会传送进位，也就是说，p^Lp^R 为真。请注意，这一表达式包含了右半部分产生进位，而左半部分传送该进位的情况。那么p^Lp^R 为真，但g^R→p^R，所以(p^Lp^R+p^Lp^R)≡p^Lp^R。

(b) 左半部分产生进位，也就是说，g^L 为真。在这种情况下，左端进位输出的出现并不取决于右端是否有进位输入，也不取决于右半部分是否产生了进位。

因为，对应2n 位加法器的进位传送位p 的表达式是

p=g^L+p^Lp^R

现在假设2n 位加法器的右端没有进位输入。那么只有出现了以下两种情况之一，2n 位加法器的左端才会有进位输出。

(a) 右半部分产生了进位，而且左半部分传送了该进位；

(b) 左半部分产生了进位。

因此，对应g 的逻辑表达式是

g=g^L+p^Lg^R

现在把注意力转到这些s_i 和t_i 上。首先，右半部分的位与右侧n 位加法器的输出相比没有改变，因为左半部分的出现不会对右半部分造成影响。因此，对i=1、2、…、n，有 $s_{n+i}=s_i^R$ ，而且 $t_{n+i}=t_i^R$ 。

不过，左半部分的位必须经过修改，从而把右半部分产生进位的情况考虑在内。首先，假设2n 位加法器的右端没有进位。这种情况应该是由s_i 告诉我们，从而可以为左半部分的s_i（也就是s₁、s₂、…、s_n）设计表达式。因为右半部分没有进位输入，所以只有在右半部分生成了进位的情况下，左半部分才有进位输入。因此，如果g^R 为真，那么 s_i=t_i^L （因为 t_i^L 会告诉我们当左半部分有进位输入时会发生什么）。我们可以将其写为逻辑表达式

$s_i=s^L_i\overline{g}^R+t^L_ig^R$

其中，i=1、2、…、n。

最后，要考虑当2n 位加法器的右端有进位输入时会发生什么。现在可以按照如下方式解决左半部分t 的值的问题。如果右半部分传送了进位的话，也就是如果p^R=1，左半部分就会有进位输入。因此，如果p^R 为真，则t_i 会接受 t_i^L 的值，而如果p^R 为假，t_i 就会接受 s_i^L 的值。写成逻辑表达式就是

$t_i=s^L_i\overline{p}^R+t^L_ip^R$

概括起来，图13-17中标有FIX的方框所表示的电路会计算如下表达式

p=g^L+p^Lg^R
g=g^L+p^Lg^R
$s_i=s^L_i\overline{g}^R+t^L_ig^R$ ，其中i=1、2、…、n。
$t_i=s^L_i\overline{p}^R+t^L_ip^R$ ，其中i=1、2、…、n。

这些表达式各自能被不超过3层的电路识别。例如，最后那个表达式只需要图13-18所示的电路。

图 13-18　FIX电路的一部分

13.6.2　分治加法器的延迟

设D(n)是我们刚设计的n位加法器的延迟，可以按照以下方式写出表示D的递推关系。对依据情况n=1来说，查看图13-16中的依据电路，可以得出延迟是3。因此，D(1)=3。

现在要看看图13-17中电路的归纳构造。该电路的延迟是n位加法器电路的延迟，加上FIX电路的延迟。n位加法器的延迟是D(n)。而为FIX电路设计的各表达式都会带来一个不超过3层的简单电路。图13-18就是个典型的例子。因此，D(2n)要比D(n)多3。所以对应D(n)的递推关系是

D(1)=3
D(2n)=D(n)+3

对那些为2的乘方的位数来说，该递推关系的解有D(1)=3，D(2)=6，D(4)=9，D(8)=12，D(16)=15，D(32)=18，等等。对2的乘方n来说，该递推关系的解是

D(n)=3(1+log₂n)

大家可以用3.11节的方法检验。特别要说的是，请注意，对32位加法器而言，延迟18要远少于32位行波进位加法器的延迟96。

13.6.3　分治加法器使用的门的数量

我们还应该验证门的数量是否合理。设G(n)是n 位加法器电路使用的门的数量。依据是G(1)=9，数出图13-16所示电路中门的数量就可以得出这一数字。然后看到图13-17所示电路，也就是归纳情况，在两个n 位加法器的子电路中有2G(n)个门。除了这个量之外，还必须加上FIX电路中门的数量。可能要反转g^R 和P^R 一次，然后n 个s_i 和t_i 各需要3个门（两个AND和一个OR）来计算，也就是总共要6n 个门。在这个量之上，要加上为g^R 和P^R 设置的两个反相器，还必须加上计算g 和p 各自需要的两个门。因此FIX电路中门的总数量是6n+6。这样对应G 的递推关系是

G(1)=9
G(2n)=2G(n)+6n+6

这里的函数还是只为2的乘方n 定义。G 的前6个值如图13-19中的表所示。对n=32，我们看到电路需要954个门。对2的乘方n 来说，表示G(n)的解析式是3n log₂n+15n-6，大家可以利用3.11节中的技巧来证明该表达式是正确的。

n	G(n)
1	9
2	30
4	78
8	186
16	426
32	954

图 13-19　多种n 位加法器所使用的门的数量

事实上，如果所需要的只是32位加法器，完全可以用更少的门来实现电路。这样的话，可知在第32位的右边没有进位输入，因此在电路的最后阶段不需要计算p 以及t₁、t₂、…、t₃₂的值。同样，右半部分的16位加法器也不需要计算它的进位传送和16个t 的值，而右侧16位加法器右半部分的8位加法器不需要计算它的p 和t，等等。

把分治加法器使用的门的数量与行波进位加法器使用的门的数量相比是很有意思的。我们在图13-10中设计的全加器电路使用了12个门。因此，n 位行波进位加法器使用了12n 个门，而对n=32来说，这个数字就是384。如果记得最右位的进位输入是0，还可以省掉一些门。

可以看到，对这种有意思的情况，也就是对n=32的情况而言，行波进位加法器尽管要慢很多，但使用的门的数量却不到分治加法器的一半。此外，后者的增长率O(n logn)要高于行波进位加法器的增长率O(n)，所以随着n的增加，门数量的差别会越来越大。不过，这个比率只是O(logn)而已，所以门数量的差别并不严重。由于这两种电路所需时间（分别是O(n)和O(logn)）的差别要更为明显，某种分治加法器几乎用在所有的现代计算机中。

13.6.4　习题

1. 按照本节介绍的设计方法，画出把4位（bit）的数字相加的分治电路。

2. 设计类似图13-18的电路，计算图13-17中加法器的其他输出，也就是p、g 和那些s_i 。

3. ** 设计接受十进制数字输入的电路，其中各位数字是4个给出与该十进制数字等价的二进制数字的输入表示的。而输出的是与之等价的二进制表示数字。大家可以假设数字（digit）的数量是2的乘方，并使用分治法。提示：左半部分的电路（高位数字）需要来自右半部分（低位数字）的哪些信息？

4. * 证明，对2的乘方n 而言，如下递推关系的解是D(n)=3(1+log₂n)。

D(1)=3

D(2n)=D(n)+3

5. * 证明，对2的乘方n 而言，如下递推关系的解是G(n)=3n log₂n+15n-6。

G(1)=9

G(2n)=2G(n)+6n+6

6. ** 我们注意到，如果所需要的只是32位加法器，就不需要图13-19给出的全部954个门。原因在于，可以假设32位中最右的位置没有进位输入。那么实际上需要多少个门？

13.7　多路复用器的设计

多路复用器（multiplexer）通常简写为MUX，是一种常见的计算机电路，它接受d 路控制输入，比方说是x₁、x₂、…、x_d，以及2^d 路数据输入，比方说是y₀、y₁、…、y_2^d-1，如图13-20所示。MUX的输出等于特定的数据输入，输入y_{(x₁x₂…x_d )₂}。也就是说，把控制输入当作0到2^d-1范围内的二进制整数，该整数是要传递给输出的数据输入的下标。

图 13-20　多路复用器电路概要图

示例　13.7

分治加法器中计算s_i 和t_i 的电路就是d=1的多路复用器。例如对应s_i 的公式是 $s^L_i\overline{g}^R+t^L_ig^R$ ，而它的电路概要图就如图13-21所示。这里，g^R所扮演是控制输入x₁的角色， s^L_i 则是数据输入y₀，而 t^L_i 是数据输入y₁。

再举个例子，具有两个控制输入x₁和x₂，以及4个数据输入y₀、y₁、y₂和y₃的MUX的输出公式是

$y_0\overline{x}_1\overline{x}_2+y_1\overline{x}_1x_2+y_2x_1\overline{x}_2+y_3x_1x_2$

{%}

图 13-21　1-复用器

这里对应各数据输入的都分别只有一项。而具有数据输入y_i 的项也含有两个控制输入，要么是否定的，要么是非否定的。通过把i 写为d 位的二进制整数，我们可以推断出哪些控制输入是否定的。如果二进制的i 第j 个位置是0，那么x_j 就是否定的，而如果第j 个位置是1，就不为x_j 取反。请注意，这一规则对任意数量d 的控制输入都是有效的。

一种简单的多路复用器设计是使用具有3级门的电路。在第一级中，要计算各控制位的否定。接下来的一级是一行AND门。第i 个门会把数据输入y_i 与恰当的控制输入及取反控制输入组合结合起来。因此，除了控制位被置为i 的二进制表示时第i 个门的输出是y_i，其他情况下该门的输出总是0。最后一级是一个OR门，它的输入来自上一级的各AND门。因为所有AND门中除了一个之外输出都是0，而这唯一一个输出不为0的AND门，比方说是第i 个，它的输出是y_i，所以电路的输出就等于y_i 。d=2时该电路的样子如图13-22所示。

图 13-22　d=2的多路复用器电路

13.7.1　分治多路复用器

图13-22所示电路的最大扇入是4，一般来说这是可以接受的。不过随着d 逐渐变大，OR门的扇入2^d之大就变得不可接受了。即便是各自只有d+1路输入的AND门，也开始有着无法让人满意的大扇入。好在基于对控制位对半分割的分治法让我们可以用扇入至多为2的门来构建这样的电路。此外，假如要求所有电路都是用具有相同扇入限制的门构建的，这一电路使用的门就会少很多，而且几乎和图13-22所示的一般电路一样快。

我们把具有d 路控制输入和2^d 路数据输入的多路复用器称为d-MUX，那么这类多路复用器电路的归纳构建如下所述。

依据。依据是d=1时的多路复用器电路，也就是1-MUX，如图13-23所示。它由4个扇入被限制为2的门组成。

图 13-23　依据电路，d=1时的多路复用器

归纳。归纳是由图13-24所示电路进行的，它是用2^d+1个d-MUX构建了一个2d-MUX。请注意，尽管控制输入的数量只是翻倍，数据输入的数量却变为之前的平方，因为2^2d=(2^d)²。

假设2d-MUX的控制输入需要数据输入y_i，也就是

i=(x₁x₂…x_2d )₂

图13-24中顶部那行d-MUX接受一组从某个y_j 开始的2^d 路数据输入，这里j 是2^d 的倍数。因此，如果用低序的d 个控制位x_d+1、…、x_2d 来控制各个d-MUX，所选择的输入就是各组中的第k 个（各组中最左侧的输入被记为输入0），其中

k=(x_d+1…x_2d )₂

也就是说，k 是由低序那一半中的位表示的整数。

{%}

图 13-24　分治多路复用器

底部d-MUX的输入是顶部那行d-MUX的输出，我们刚得出它们是y_k、y_2^d+k 、y_2×2^d+k 、…、y_(2^d-1)2^d+k 。底部的d-MUX是由x₁…x_d 控制的，它表示某个二进制整数j，也就是j=(x₁…x_d )₂。因此底部的多路复用器会选择它的第j 个（最左侧的输入被记作输入0）输入作为其输出。因此被选定的输入是y_{j 2^d+k} 。

可以按照如下方式证明 j 2^d+k=i。请注意，用 j 乘以2^d会把 j 的二进制表示向左移动d 个位置。也就是说 j 2^d=(x₁…x_d 0…0)₂，其中这串0的长度是d。因此，j 2^d+k 的二进制表示就是(x₁…x_dx_d+1…x_2d )₂。这是因为k 的二进制表示是(x_d+1…x_2d )₂，而且当这个数字被加到最后是d 个0的 j 2^d 时，从右起的第d 位显然没有进位输出。现在可知 j 2^d+k=i，因为它们有着相同的二进制表示。因此图13-24所示的2d-MUX正确地选出了x_i，其中i=(x₁…x_2d )₂。

13.7.2　分治MUX的延迟

可以通过写出适当的递推关系来计算所设计多路复用器电路的延迟。设D(d )是d-MUX的延迟。观察图13-23可知，对d=1，延迟是3。不过，要得到更紧密的边界，就要假设所有的控制输入都要经过MUX外的反相器，而且它们不能算在图13-23所示反相器的那层中。所以在确定了电路其余部分的延迟之后，要在总延迟上加1，从而把所有控制输入的反相产生的延迟计算在内。因此，我们的递推关系是从D(1)=2开始的。

对于归纳部分，我们注意到经过图13-24所示电路的延迟是经过上方那行MUX中任何一个的延迟，加上经过最后一个MUX的延迟。因此，D(2d)就是D(d)的两倍，所以递推关系为

D(1)=2
D(2d )=2D(d )

解是很容易得出的。我们有D(2)=4，D(4)=8，D(8)=16，而一般来说就是D(d )=2d。当然，严格地讲，这一公式只有在d 是2的乘方时才成立，不过同样的思路也可以用于任意数量的控制位d。因为我们必须加上为控制输入反相所造成的延迟1，所以该电路的总延迟就是2d+1。

现在考虑简单多路复用器电路（每个数据输入对应一个AND门，其输出都提供给一个OR门）。正如之前所说的，它的延迟是3，与d 无关，不过一般来说不可能这样构建电路，因为最终那个OR门的扇入是不现实的。如果坚持将扇入限制为2会怎样呢？这样一来，有着2^d 路输入的最后那个OR门会被有着d 层的完全二叉树替代。回想一下，这样一棵树将会有2^d 个叶子节点，刚好就是正确的数量，而这棵树的延迟是d。

我们还要用由扇入为2的AND门构成的树替代这些AND门，因为一般来说这些AND门具有d+1路输入。回想一下，在使用具有两路输入的门时，每使用一个门就会将输入的数量减少1，所以需要d 个扇入为2的门才能把d+1路输入减少到1路输入。如果将门安排成AND门构成的平衡二叉树，就需要log₂d+1层。在加上为控制输入反相的一层之后，就得到总延迟是d+1+(log₂d+1)。如图13-25中的表所示，虽然这与分治MUX那2d+1的延迟相比差别不大，但该图还是好意地对其进行了比较。

延迟
d	分治MUX	简单MUX
1	3	3
2	5	5
4	9	8
8	17	13
16	33	22

图 13-25　两种不同多路复用器设计的延迟

13.7.3　门的数量

本节中要比较简单MUX和分治MUX中门的数量。我们会看到，随着d 的增加，分治MUX所含的门明显要更少。

要计算分治MUX中门的数量，可以暂时忽略反相器。我们知道，这d 路控制输入各要被反相一次，所以最后再在得出的数量上加d 就行了。设G(d )是d-MUX中（除反相器之外的）用到的门的数量。那么可以按照如下方式给出它的递推关系。

依据。依据情况是d=1的情况，如图13-23中的电路那样，除了反相器之外有3个门。因此G(1)=3。

归纳。对归纳部分来说，图13-24中的2d-MUX是用2^d+1个d-MUX构建的。

因此，递推关系就是

G(1)=3

G(2d )=(2^d+1)G(d )

正如我们在3.11节中看到过的，该递推关系的解是

G(d )=3(2^d-1)

这一递推关系的前几个值分别是G(2)=9，G(4)=45和G(8)=765。

现在来考虑在只使用扇入为2的门时，简单MUX使用的门的数量。和之前一样，我们会忽略为控制输入反相所需的d 个反相器。最后的OR门要用一棵有2^d-1个OR门的树代替。2^d个AND门各会被一棵有d 个AND门的树替代。因此，总的门数量就是2^d(d+1)-1。该函数要比分治MUX中门的数量多，多的幅度大约是(d+1)/3。图13-26比较了两种MUX中门的数量，每种情况都不包括d 个反相器。

门数量
d	分治MUX	简单MUX
1	3	3
2	9	11
4	45	79
8	765	2303
16	196605	1114111

图 13-26　两种不同多路复用器设计（不包括反相器）的门数量

有关分治的更多内容
本节的多路复用器设计所表示的这种分治算法是一种虽很少见但很强大的形式。大多数分治的例子都会把问题一分为二。这些例子包括归并排序、13.6节中设计的快速加法器，以及用来计算大量位的AND或OR的完全二叉树。在多路复用器中，是用d+1个更小的MUX来构建一个2d-MUX。换句话说，具有n=2^2d 路数据输入的MUX是由 $\sqrt{n}+1$ 个小MUX构建的。

13.7.4　习题

1. 利用本节介绍的分治技巧，构建

(a) 2-MUX

(b) 3-MUX

2. * 大家会如何构建那些数据输入的数量不是2的乘方的多路复用器？

3. * 利用分治技巧设计独热码解码器（one-hot-decoder）。该电路接受d 路输入x₁、x₂、...、x_d，并有 2^d 路输出y₀、y₁、...、y_2^d-1。这些输出中刚好有一个是1，具体来说就是满足i=(x₁,x₂,…,x_d )₂的y_i 。那么该电路的延迟（表示为d 的函数）是多少？它要使用多少个门（表示为d 的函数）？提示：有多种方法。一种电路设计方式是为前d-1路输入使用一个独热码解码器，并将该解码器的各输出分成基于最后一个输入x_d 的两路输出。第二种方式是假设d 是2的乘方，从两个独热码解码器开始，一个对应前d/2路输入，而另一个则对应后d/2路输入。然后恰当地将这些解码器的输出结合起来。

4. * 通过为各路输出创建一个AND门，并为这些门提供恰当的输入或反相的输入，可以构建出一种独热码解码器，大家在习题(3)中设计的电路与这种显见的设计相比，延迟和门的数量各是多少？如果将大扇入的AND门用两输入的门代替，那么本题中的电路与习题3中设计的电路相比又是什么情况？

5. * 多数电路（majoritycircuit）接受2d-1路输入，并只有一路输出。如果有d 路或d 路以上的输入是1，那么它的输出是1。设计分治多数电路。延迟和门的数量各是多少（表示为d 的函数）？提示：和13.6节中的加法器一样，利用计算比我们所需更多的电路能最好地解决该问题。特别要指出的是，可以设计接受n 路输入并具有n+1路输出y₀、y₁、…、y_n 的电路。如果刚好有i 个输入是1，输出y_i 就是1。然后可以用习题(3)中提到的两种方式中的任意一种归纳地构建多数电路。

6. * 有一种幼稚的多数电路设计，它是通过为每个d 路输入组设置一个AND门来构建的。这种多数电路的输出是所有这些AND门的OR。与习题(5)设计的分治电路相比，这种幼稚设计的延迟和门的数量各是多少？如果用两输入门代替这种幼稚设计中的门呢？

13.8　存储单元

在结束逻辑电路这一主题之前，我们还要考虑一类非常重要的时序电路。存储单元（memory element）是由一系列的门构成的电路，它可以记住它的上一个输入，并将这个输入作为它的输出，不管这个输入已经给定多久。计算机的主存是由一些特定的位组成的，这些位可以存入值而且会保留它们的值直到另一个值被存入。

{%}

图 13-27　存储单元

图13-27就展示了一个简单的存储单元。它是由称为load 的输入控制的。一般来说，load 的值是0。在这种情况下，反相器a的输出就是1。因为只要有一路输入是0，AND门的输出就是0，所以只要load 是0，则AND门c 的输出一定是0。

如果load=0而且门d 的输出（也就是该电路的输出）是1，那么门b 的两路输入都是1，这样它的输出也是1。因此，OR门d 的输入之一是1，这样它的输出就仍然是1。另一方面，假设d的输出是0。那么AND门b 的某一输入是0，这意味着它的输出是0。这使得d 的两路输入都是0，所以只要load=0，d 的输出就会保持为0。于是可以得出结论：只要load=0，电路的输出就可以保持它原来的样子。

真正的存储芯片
我们不应该认为图13-27精确地表示了典型的寄存器位，但它也不是很不靠谱。尽管它也表示了主存的位，至少原则上讲如此，但它们之间还是存在着明显的区别，而且很多与存储芯片设计有关的内容都涉及远超本书范围的电子学细节。
因为在计算机和其他类型的硬件中会用到海量的存储芯片，它们的大规模生成已经让一些存储百万位或更多位的微妙芯片设计变为现实。想知道存储芯片的致密性，可以回想一下它的面积大约是1平方厘米（10^-4平方米）。如果在这样的芯片上有1600万位，那么每一位所占据的面积就等于6×10^-12平方米，或者说是2.5微米见方的一块面积，记住，1微米是10^-6米）。如果线路的最小宽度，或者说线路间的空间是0.3微米，这没有留多少空间给电路构建存储单元。更糟的是，我们不止要存储位，还要从这1600万位中选出一位接收值，或是读取这1600万位中某一位的值。这一选择电路还要占据芯片上不少空间，留给存储单元的空间就更少了。

现在考虑load=1时的情况。反相器a 的输出现在是0，这样一来，AND门b 的输出也将是0。另一方面，AND门c 的第一路输入是1，所以c 的输出就与输入in 是相同的。同样，因为OR门d 的第一路输入是0，所以d 的输出和c 的输出是一样的，这和电路输入in 也是相同的。因此，将load 置为1会使电路的输出变成in。在把load 变回0时，电路输出会继续在门b 和d 之间来回，正如前文讨论过的。

如果把“电路输入”解释为load 为1时in 的值，就可以说图13-27中的电路具有与存储单元相似的行为。如果load 是0，那么可以说不管in 的值是什么，都不存在电路输入。通过把load 置为1，可以让该存储单元接受新值。只要load 是0，也就是说，只要此电路没有新的输入，该单元就会保留这个值。

习题

1. 为图13-27所示的存储单元电路画出类似图13-6的时间图。

2. 描述一下，在如图13-27所示的存储单元中，如果一个a 粒子击中反相器，并让门a 的时间在一段很短的时间内与输入相同（这段时间很短，并不足以让信号传遍整个电路），该电路的行为会是怎样的。

13.9　小结

阅读本章之后，大家应该更加熟悉计算机中的电路以及逻辑是如何用来设计这种电路的。特别要说的是，本章涵盖了以下要点：

什么是门，以及门是如何组合起来形成电路的；
组合电路与时序电路间的区别；
如何根据逻辑表达式设计组合电路，以及如何用逻辑表达式表示组合电路的模式；
诸如分治法这样的算法设计技巧是如何用来设计加法器和多路复用器这样的电路的；
设计快速电路要考虑的一些因素；
简要表示了计算机是如何在它的电子电路中存储二进制位的。

13.10　参考文献

Shannon [1938]首先注意到布尔代数可以用来描述组合电路的行为。要更加全面地了解组合电路的理论与设计，参见Friedman and Menon [1975]。

Mead and Conway [1980]描述了用于构建超大规模集成电路的技术。Hennessy and Patterson [1990] 讨论了计算机体系结构以及用于组织其电路元件的技术。

Friedman, A. D. , and P. R. Menon [1975]. Theory and Design of Switching Circuits, Computer Science Press, New York.

Hennessy, J. L. , and D. A. Patterson [1990]. Computer Architecture: A Quantitative Approach, Morgan Kaufmann, San Mateo, Calif.

Mead, C., and L. Conway [1980]. Introduction to VLSI Systems, Addison-Wesley, Reading, Mass.

Shannon, C. E. [1938]. “Symbolic analysis of relay and switching circuits,” Trans. of AIEE 57, pp. 713–723.

第 13 章 利用逻辑设计计算机元件

13.1 本章主要内容

13.2 门

13.3 电路

示例 13.1

13.3.1 组合电路和时序电路

示例 13.2

13.3.2 习题

13.4 逻辑表达式和电路

13.4.1 从表达式到电路

13.4.2 从电路到逻辑表达式

示例 13.3

示例 13.4

示例 13.5

13.4.3 习题

13.5 电路的一些物理限制

13.5.1 电路速度

13.5.2 大小限制

13.5.3 扇入和扇出限制

示例 13.6

13.5.4 习题

13.6 分治加法电路

13.6.1 递归加法电路

13.6.2 分治加法器的延迟

13.6.3 分治加法器使用的门的数量

13.6.4 习题

13.7 多路复用器的设计

示例 13.7

13.7.1 分治多路复用器

13.7.2 分治MUX的延迟

13.7.3 门的数量

13.7.4 习题

13.8 存储单元

习题

13.9 小结

13.10 参考文献