计算机系统概论第三章.doc

《计算机系统概论第三章.doc》由会员分享，可在线阅读，更多相关《计算机系统概论第三章.doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 数字逻辑结构 在第一章中，我们提到计算机是由数量巨大的非常简单的结构所组成。例如，Intel的Pentium 微处理器，2000年推向市场，是由超过4千2百万个MOS晶体管制造的。IBM Power PC 750 FX，2002年推出，是由超过3千8百万个MOS晶体管组成。在本章中，我们将解释MOS晶体管作为逻辑单元的工作原理，如何将这些晶体管连接起来组成逻辑门，以及逻辑门是如何被互相连接起来而组成更大的制造计算机所需的单元。在第四章，我们将把这些更大的单元连接起来组成计算机。 首先介绍晶体管。3.1 晶体管今天的大多数计算机，或者说是大多数微处理器（所对应的计算机的核心）是由MOS晶

2、体管组成的。MOS是金属氧化物半导体的英文缩写。关于半导体的电子特性超出了本书的范围，它位于本书所描述的最底层的抽象之下，也就是说，如果晶体管出现差错，我们就受其控制，无法解决该问题了。不过，也不太可能遇到晶体管出现问题的情况。在此，我们只需了解MOS晶体管的两种类型：P型和N型。它们都是进行逻辑运算的，其工作原理与墙上的电开关类似。图3.1显示了最基本的电子电路，包括电源、一个墙上的开关和一盏灯。为了让灯发光，电子必须流动；而为了使电子流动，必须存在一个从电源到灯、再回到电源的闭合电路。通过操作开关可以控制电路的合与开，进而使灯打开或关闭。我们使用一个N型或P型半导体晶体管来代替开关，控制电

3、路的闭合。图3.2是一个N型晶体管的示意图，（a）单独出现的晶体管（b）出现在电路中的晶体管。注意，在图3.2a中的晶体管有三个终端，它们分别被称为栅极、源极和漏极，其命名原因不在本书范围之内。如果N型晶体管的栅极被加以2.9伏电压，从源极到漏极的连接就相当于一段电线。使用电子术语来说就是：在源极和漏极之间存在一个闭合回路，即导通。如果N型晶体管的栅极被加以0伏电压，在源极和漏极之间的连接就被断开，在源极和漏极之间存在一个断路，即截止。图3.2b显示了一个包括一个N型晶体管、一个电池组和一个灯泡的电路。当栅极被加以2.9伏电压时，晶体管就相当于一段导线，从而形成回路，灯泡发光。当栅极被加以0伏

4、电压时，晶体管则相当于一个断路，电路被断开，灯泡不亮。 图3.2c为描述图3.2b中电路的速记表示法。电子工程师通常只显示电源端，而不总是显示出电源和完整的电路。事实上，电源本身对实现完整的电路的贡献是很容易理解的，所以通常不需显示出来。P型晶体管的工作原理与N型晶体管恰恰相反。图3.3是P型晶体管的示意图。当给栅极提供的电压为0伏时，P型晶体管像一段电线，构成闭合回路；当所提供的电压为2.9伏时，就出现断路。因为P型和N型晶体管以互补的方式工作，我们称既包含P型晶体管又包含N型晶体管的电路为CMOS电路，即互补金属氧化物半导体电路。3.2 逻辑门 晶体管之上是逻辑门。也就是说，我们只用MOS

5、晶体管就可以构建基本的逻辑结构。在第二章，我们学习了与、或、非函数的特性。在本章，我们将构建晶体管电路，以实现每一种逻辑函数，相应的电路我们分别称为与门、或门、非门。3.2.1 非门（或反相器）图3.4显示了在计算机中最简单的逻辑结构，它由两个MOS晶体管构成：一个P型晶体管和一个N型晶体管。图3.4a是其电路的示意表示。图3.4b显示了当输入电压为0伏时该电路的工作情况，注意：P型导通而N型截止，因此，输出与2.9伏一端连接。另一方面，如果输入为2.9伏，P型截止而N型导通，输出与地（即0伏）连接。电路的完整表现可以通过列表的方式描述，如图3.4c所示。如果我们使用符号0代替0伏，用符号1代

6、替2.9伏，就得到补或非函数的真值表（图3.4d），与第二章相同。我们已经显示了如何构建第二章所讨论的非函数的电子电路。我们称该电路为非门，或反相器。3.2.2 或门与非或门图3.5显示了一个非或门。图3.5a是实现非或门的电路示意图。它包含两个P型和两个N型晶体管。图3.5b显示了如果A被加以0伏，B被加以2.9伏时电路的表现。在这种情况下，两个P型晶体管下面出现一个断路，输出C与2.9伏的电源不相连。然而，最左边的N型晶体管的作用像一根电线，将输出C与0伏相连。注意如果A和B都被加以0伏，两个P型晶体管导通，输出C被连到2.9伏。同时可以注意到，既然两个N型晶体管的作用都是形成断路，所以C

7、与地不相连。ABC0伏0伏2.9伏0伏2.9伏0伏2.9伏0伏0伏2.9伏2.9伏0伏图3.5非或门如果给A或B提供2.9伏电压，则对应的P型晶体管为断路。那就足够切断从C到2.9伏电源的连接。然而提供给其中一个N型晶体管的栅极的2.9伏则足以使晶体管导通，使得C接地（即0伏）。图3.5c总结了图3.5a中电路的全部特性。它表明给A和B提供4组不同电压的电路特征。这四组分别为A=0伏 B=0伏A=0伏 B=2.9伏A=2.9伏 B=0伏A=2.9伏 B=2.9伏如果使用等价的逻辑值代替电压，就得到图3.5d所示的真值表。注意到C的输出恰恰就是与第二章中讨论的逻辑或函数相反的结果。实际上它是非或

8、函数，其缩写为NOR。我们把实现非或函数的电路叫做非或门。如果我们在输出端增加一个反相器，扩大图3.5a的电路，如图3.6所示，输出D就是逻辑函数或的结果。图3.6a 中的电路就是或门。图3.6b表示了如果输入变量A是0并且输入变量B是1时的电路结果。图3.6c显示了该电路的真值表。3.2.3 与门和非与门电路 图3.7显示了一个与门电路。注意，如果当A、B中有一个输入是0V的电压时，都有C直接连接到2.9V的电源上。C有2.9V的电压表明栅极与C相连的N型晶体管提供了一条从D到地的通路。因此，只要A、B中有一个为0，图3.7电路的输出D就为0。 同时，当A、B中至少有一个被提供0V电压时，表

9、明栅极和A或B相连的两个N型晶体管中至少有一个为断路，因此，C不接地。此外，C为2.9V意味着栅极和C相连的P型晶体管为断路，因此，D不与2.9V相连。 另一方面，当A、B都被供给2.9V的时候，和它们相对应的P型晶体管都是断路。然而，和它们相对应的N型晶体管就像电线，直接使C接地。因为C接地，所以最右端的P型晶体管就像闭合电路，让D有2.9V的电压。 图3.7b使用真值表总结了图3.7a中的电路特性。这个电路就是与门电路。而虚线里的电路（即输出是C）是一个非与门电路。 以上门电路在数字逻辑电路和数字计算机中应用非常普遍。在Pentium 微处理器里有上百万个反相器（非门）。为了方便起见，我们

10、使用图3.8中的标准符号来表示上面的每一种门电路。在反相器、非与门和非或门电路中的圈表示补（即非）函数。 从现在开始，我们将不再画那些显示出单个晶体管的电路，而是使用图3.8中的符号来表示，提升抽象的层次。3.2.4 德摩根定律 图3.9a中可以在进入门电路前先对输入做非函数。考虑两个输入的与门，如果我们把A和B应用了非函数后再输入门，并且与门的输出也取非的效果。与门电路输入前的圈表示A和B在输入与门之前就取了非。 图3.9b显示了A=0，B=1这一输入组合的结构特性。为了方便起见，我们把圈从与门电路的输入和输出上移开。这样，我们就可以很容易的看到每个值经过圈时发生了怎样的变化。 图3.9c采

11、用真值表的方式列出了图3.9a的逻辑电路中全部四种输入组合的特性。注意A取非用表示。 我们可以使用代数式来描述这个电路的特征：我们也可以使用语言来表述这一特征：“只有A和B都为假时，输出才为假”，等价于“A和B至少有一个为真时，输出就为真”。这个等式就是著名的德摩根定律。如果把或门的两个输入都取非，输出也取非，会有类似的结果吗？3.2.5 更大的门 在结束逻辑门这个主题之前，我们应当注意到存在更多输入的与门，或门，非与门，非或门的表示方法。比如，我们可以构建一个三个输入的与门或者四个输入的或门。一个有N个输入的与门仅当所有的输入变量都为1时，输出才为1。只要有一个为0结果就为0。一个有N个输入

12、的或门只要任何一个输入变量为1输出就为1。也就是说仅当所有的输入变量都为0时输出才为0。 图3.10是一个三个输入的与门。图3.10a给出了它的真值表。图3.10b给出了有三个输入的与门的符号表示。 你能画出一个有三个输入的与门的晶体管级的电路吗？一个有四个输入的或门呢？3.3 组合逻辑电路 我们已经理解了基本逻辑门的工作原理，下一步就是构建一些组成计算机微结构的重要组件的逻辑结构。 有两种基本的逻辑结构，一种包括信息的存储，另一种则不包括。在3.4、3.5和3.6节，我们将讨论存储信息的逻辑结构。这一节我们讨论另一种。这些结构有时被称为“判定元件”。通常，它们被称为组合逻辑结构，因为它们的输

13、出是仅由当前输入值的组合决定的。它们的输出不由任何过去的存储在其中的信息决定，因为信息不能被存储在组合逻辑电路中。我们现在来了解译码器，多路选择器，全加法器。3.3.1 译码器图3.11表示一个有两个输入的译码器的逻辑门描述。译码器的特性为：只有一个输出为1，其它全为0。输出为逻辑1的是对应于要被检测的输入组合的输出。通常，译码器有n个输入，2n个输出。被检测的输入组合的输出线被设定，即输出为1，所有其它的输出则为0。在图3.11中，在输入A和B的四种可能的组合中，在任意时刻，只有一个输出为1。在图3.11b中，译码器的输入是10，结果第三根输出线被设定。译码器用来判断如何解释一个位组合。我们

14、将在第五章中看到，在LC-3中每一条指令执行的工作是由一个4位的位组合决定的，它被称为操作码，是指令的一部分。一个4-16的译码器是一个简单的组合逻辑电路，它能识别出每一条指令执行的工作是什么。3.3.2 多路选择器 图3.12a表示一个有两个输入的多路器，或多路选择器的门级描述。这种多路选择器的功能就是选择其中一个输入，并把它连接到输出。选择信号（图3.12中的S）决定哪个输入是连接到输出的。图3.12的多路选择器工作如下：假设S=0，如图3.12b。因为除非所有的输入都为1，否则与门的输出就为0，那么，最右边的与门输出为1。并且，最左边的与门的输出与A的输入相同。那就是说，如果A=0，那么

15、最左边的与门是0；如果A=1，那么输出就为1。因为最右边的与门输出为0，所以对或门不起作用。因此，C处的输出与最左边的与门的输出一样。综上所述，如果S=0，那么C端的输出就是A端的输入。 另一方面，如果S=1，那么B与1做与运算，结果就是或门的输出将是B的值。 总之，C的输出要么与A的输入有关，要么与B的输入有关取决于选择线S的值。我们说S选择多路选择器的来源（A或者B）发送到输出端C。图3.12c显示了一个多路选择器的标准表示方法。 一般说来，一个多路选择器由n条选择线和2n个输入组成。图3.13a表示一个有四个输入的多路选择器的门级描述。它需要两条选择线。图3.13b显示一个四个输入的多路

16、选择器的标准表示方法。 你能构建一个有八个输入的多路选择器的门级表示方法吗？需要多少根选择线？3.3.3 全加法电路在第二章中，我们讨论了二进制加法。那个简单的加法运算与你经常做的十进制加法的算法是一样的，从右向左，一次一列，两个值中的两位和进位作加法，产生一个和位和一个向下一位的进位。区别只是它在1后得到进位而不是在9之后。图3.14是表示两个位操作数的某一列进行二进制加法的结果的真值表。每一列都有三个要做加法的值：两个操作数中各取一位，以及前一列来的进位。我们定义这三位分别为ai，bi和carryi。有两个输出，一个是和（si），另一个是向下一列的进位（carryi+1）。当ai，bi和c

17、arryi中只有一个数是1时，我们能得到和si为1，进位carryi+1为0。如果三个数中有两个等于1，我们能得到和为0而进位为1。如果三个数都等于1，和为3，在二进制的加法中对应和与进位都是1。图3.15是图3.14的真值表的门电路表示。注意图3.15中，对于ai，bi和carryi的8种输入组合之一，都有一个与门产生一个输出1。当输入组合是图3.14中Ci+1的输出为1的相应组合时，或门的输出Ci+1必为1。因此产生输出Ci+1的或门的输入，就是那些相应的组合经过与门产生的输出。类似的，产生输出Si的或门的输入，就是那些图3.14中 Si的输出为1的输入组合，经过与门产生的输出。注意，既然

18、输入组合000对于Si或Ci+1都不会产生值为1的输出，它对应的与门就不是任意一个或门的输入。我们称这个提供了3个输入（ai，bi和carryi）得到两个输出（和si与进到下一列的进位carryi+1）的图3.15中的逻辑电路为全加法器（full adder）。图3.16表示一个能做两个四位的二进制加法的逻辑电路图，由四个图3.15表示的全加法器组成。注意第i列的进位是第i1列进行加法运算的一个输入。3.3.4 可编程逻辑阵列（PLA）图3.17显示的是可以实现一个人想实现的任意逻辑函数的通用组件。这个组件被称为可编程逻辑阵列（PLA）。它由一组与门（被称为与阵列），以及后面的一组或门（被称为

19、或阵列）组成。与门的数目对应于真值表中输入组合（行）的数目。对于n个输入的逻辑函数，我们需要一个拥有2n个输入的与门的PLA。在图3.17中，我们共有23个3个输入的与门。或门的数目对应于真值表中输出的列数。实现算法就是对于真值表的输出列中产生一个输出1的对应的行，就简单的将该与门的输出与或门的输入相连，因此被称为可编程。也就是说，我们通过对与门的输出与或门的输入的连接进行编程，来实现我们想实现的逻辑函数。图3.15显示了8个与门连接到2个或门，因为我们需要3个输入变量来实现2个函数（和与进位）。图3.17显示的PLA可以实现3个变量的任意4种函数，通过适当的将与门的输出连接到或门的输入即可。

20、3.3.5 逻辑完备性（logical completeness）在我们结束组合逻辑电路的主题前，关于组成逻辑电路的组件有个值得注意的特性：逻辑完备性。在3.3.4中，我们想实现的任意逻辑函数都可以通过一个PLA来完成。我们看到PLA只由与门、或门和非门组成。这就意味着，我们想实现的任意逻辑函数，只要提供足够多的与门、或门、非门，都可以完成。我们说门集合与、或、非在逻辑上是完备的，因为我们不需要使用任何其他种类的门就可以实现任何一个真值表的电路。也就是说，由于一定量的与门、或门和非门足以构建实现任意真值表的逻辑电路，所以门集合与、或、非在逻辑上是完备的。门的数目可能很大，但关键是，我们不需要任

21、何其它种类的门就可以实现。3.4 基本存储单元在3.3节开头，我们介绍了两种不同的逻辑结构，一种能够存储信息，另一种不能。我们已经讨论了三个不存储信息的例子：译码器，多路选择器，全加法器。现在我们准备来讨论能够存储信息的逻辑结构。3.4.1 R-S锁存器 存储单元的一个简单例子就是R-S锁存器。它能存储一个比特的信息。R-S锁有很多种实现方式，其中最简单的如图3.18所示。两个有两个输入的非与门连在一起，其中任意一个的输出都是另外一个的一个输入。其余的输入R和S通常被赋以逻辑值1。R-S锁工作如下：我们从所谓的静止状态开始，即S和R输入都为逻辑值1。我们先考虑输出a为1的情况，那也意味A的输入

22、为1（同时我们知道R输入也为1，因为我们在静止状态），b输出一定为0。同时也意味着B的输入为0，因此导致输出a为1。只要R和S保持为1，该电路的状态就不会变。这样我们称R-S锁存储了一个值1（a输出的值）。另一方面，如果我们假设a的输出为0，则A输入必定为0，同时b输出一定为1，这样，接下来，B的输入为1，并结合输入S为1（因为我们在静止状态），这导致a输出的值为0。同样的，只要R和S的输入保持为1，这个电路的状态就不会改变。在这种情况下，我们说R-S锁存储了值0。我们可以通过保持R的值为1并将S的值瞬间设为0的方式把这个锁设为值1。类似地，这个锁可以通过将R瞬间设为0并保持S的值为1被设为0

23、。我们用“设置”来把一个变量设为0或1，如“设为0”或“设为1”。另外，我们常用“清空”来表示把一个变量设为0。如果我们清空S，则a等于1，这将引起A为1。因为R也为1，所以 b的值为0。这引起B的值为0，这样使a的值为1。如果我们把S的值返回到1，它将不会影响a的值，因为B的值仍为0，而且非与门的输入中只有一个值为0就可以确保非与门的输出为1。这样锁在S返回1后很久，仍能存储一个值1。同样的方式我们可以通过把R瞬间地设为0，清空这个锁（把它设为0）。我们也应该注意为了使R-S锁正常地工作，必须小心千万不要把R和S的值同时设为0。如果那种情况发生，则a和b的输出都为1，那么这个锁的最后状态将取

24、决于组成门的晶体管的电子特性而不是取决于被操作的逻辑值。而晶体管的电子特性如何决定最后的状态不属于本书的范围。3.4.2 门控D锁存器（The Gated D Latch）为了更具实用价值，我们有必要控制一个锁存器何时设置，何时清空，有一个简单的方法就是使用门控锁存器。.图3.19展示了一个实现一个门控D锁存器的逻辑电路。它包括在图3.18中显示的R-S锁存器，只是加了两个额外的门，使仅当WE被设置为1时，锁存器才能被设为D输入端的值。WE（Write Enable）代表写使能。当WE没有被设定为1时（即WE等于0）， S和R都等于1。因为S和R也是锁存器的输入端，如果它们的值是1，存储在锁存

25、器里的值就不会改变，这一点我们已经在3.4.1解释过了。一旦WE被设置为1，就是S或R中的一个输出值为0，这是由D的值决定的。如果D的值是1，则S的值为0。如果D等于0，则下面的非与门的两个输入值都为1，使R的值被设为0。就像我们在上面看到的那样，如果S设为0，则R-S 锁存器被设为1。如果R设为0，那么R-S 锁存器将设为0。因此，R-S 锁存器是1或0是由D的值是1或0决定的。当WE的值返回为0，S和R都将返回为1，则存储在R-S 锁存器的值将保持不变。3.4.3 寄存器 我们已经在第二章看到，处理由多位组成的数值是非常有用的。在第5章，我们会介绍LC-3计算机，在LC-3上绝大多数值都是

26、用16位表示的。所以有必要将多位的数据存储于一个独立的单元。寄存器就是这样一个把多位的数据“捆绑”成一个单元的结构。根据需要，寄存器可以包含很多位，也可以只包含一位。在LC-3中，我们将需要很多16位的寄存器，和少数几个1位的寄存器。图3.33介绍了LC-3的内部结构，PC，IR和MAR都是16位的寄存器，而N、Z和P是1位的寄存器。图3.20显示了一个由四个门控D锁存器组成的四位寄存器。四位数值被存放在寄存器中的Q3，Q2，Q1，Q0处。当WE被设为1时，D3，D2，D1，D0可以被写入寄存器中。注意：一个用来描述被标记为上述数字的位组合的通用的速记符号是Q3:0。也就是，每一位被指定各自的

27、数字。最右边的一位是0，并且从右向左编号。如果有n位，最左边的是n-1。例如，下面的16位组合，1111015是0，14是0，13是1，12是1，以此类推。我们用符号Ql：r表示这种组合的子单元，这里l是最左边一位，而r是最右边一位。我们称这种子单元为字段。在上述的16位组合中，如果A15:0是完整的16位组合，那么：A15：12是0011A13：7 是A2：0 是110A1：1 是1我们也要指出从右向左的编号方案是我们决定的。我们也可以简单地表示最左边的位为0，并且从左到右给它们编号。事实上，很多人是这样做的。因此，从左向右还是从右向左的编号方案并不重要。但是在一个给定的环境下编号方式必须一

28、致是很重要的，也就是说，它总是按照同一种方式编号。在本书中，我们一般从右向左编号。3.5 存储器的概念我们现在已经拥有所有我们需要的工具来描述可能是电子数字计算机中最重要的结构存储器。我们将在第四章看到存储器如何适应计算机处理的基本机制，你会看到在整本书中和你今后使用计算机工作时，存储器的概念对于计算来说是多么重要。存储器由一定数量（通常很多）的单元组成，每一个单元可唯一被识别，每一个单元都有存储一个数值的能力。我们把和每一个单元联系在一起的唯一的标识符看作它的地址。我们把存储在每一个单元中的信息的位数看作它的寻址能力。举例来说，一台个人计算机的广告可能为：“这台计算机有16兆字节的存储容量。

29、”事实上，大多数广告使用缩写16 MB。这表明，该计算机系统包含一千六百万个存储单元，每个单元包含一个字节的信息。3.5.1 地址空间我们把唯一可识别的单元总数称为存储器的地址空间。例如，一个16MB的存储器是指一个包含一千六百万个唯一可识别的存储单元的存储器。事实上，一千六百万只是一个相近的值，它取决于我们识别存储单元的方式。既然任何事物在计算机中被表示为0和1的序列，那么对存储单元使用二进制地址识别，也就不应感到奇怪。使用n位地址，我们能唯一识别出2n个单元。10位提供1024个单元，近似地表示为1000。如果我们有20位来表示每一个地址，我们有220唯一可识别的单元，近似地表示为一百万。

30、因此16兆对应于能够被24个地址位进行唯一识别的单元的数量。我们称地址空间是224，确切地说是个单元，而不是尽管我们通常看作1600万。3.5.2 寻址能力 存储在每个单元中的位数是存储器的寻址能力。一个16兆字节的存储器是一个包含个存储单元，每个单元包含1字节（8位）的存储器。大多数的存储器是字节可寻址的。这一点有历史原因：大多数计算机得到其原始操作数据，正如我们在第二章所看到的，是键盘上键入的某个字符对应的一个8位的ASCII码。如果存储器是字节可寻址的，每个ASCII码在存储器中就占用一个单元。因此，能够唯一识别每个字节所在的存储单元，就允许存储的信息中的各个字节易于更改。许多被设计用来

31、执行科学计算的计算机是64位可寻址的。这归咎于用于科学计算的数据常常使用64位的浮点数来表示的事实。回忆一下在第二章中讨论的浮点数数据类型。因为科学计算需要使用64位来表示数字，所以为了可以在每个独立的存储单元储存一个数字而设计的计算机是合情合理的。3.5.3 一个223位的存储器图3.21表示了一个223位大小的存储器。也就是说，这个存储器有4个单元的地址空间，3位的寻址能力。一个223位大小的存储器需要2位去说明一个地址。一个寻址能力为3的存储器在每个存储单元中存储3位的信息。访问存储器需要对地址位进行译码。注意，地址译码器根据输入A1:0的值，将4个输出之一设为1，该输出就是被寻址的“字

32、线”。在图3.21中，存储器的每一行对应于一个唯一的3位的字，术语“字线”由此得来。存储器可以通过输入地址A1:0来读取：被读的字线被设为1，注意存储器的每一位都与其“字线”进入与门，然后其输出再与其它字的相应的位进入或门，既然在某一时刻只有一个字线被设为1，这在效果上就是一个多路选择器译码器的输出为每一位提供了选择功能。这样，相应的字就被读取了。图3.22显示了读取单元3的过程。3的编码是11，地址A1:0=11被译码，最底下的字线被设为1。注意译码器的其它3个输出都没有被设置，即值都为0。存储在单元3中的值是101，这三位的每一位都与字线进入与门，产生输出值101，被提供给3个或门。注意，

33、或门的所有其它输入都是0，因为它们都是与值为0的字线进入与门产生的。结果D2:0=101。也就是说，存储在单元3中的值被或门输出。存储器可以以同样的方式去写。由A1:0所定义的地址被提供给地址译码器，从而导致正确的字线被设为1。随着WE的值被设为1，Di2:0这三位将被写入三个与该字线相对应的门控锁存器中。3.6 时序逻辑电路 在3.3节，我们讨论了输出仅取决于当前的输入的处理信息的数字逻辑电路（称为判定结构），例如多路选择器、译码器和全加法器。我们称这种结构为组合逻辑电路。在这些电路中没有过去的信息。事实上，它也没有能力存储任何之前产生的信息。在3.4和3.5节，我们描述了能够存储信息的结构

34、3.4节的基本的存储元件和3.5节的一个简单的223位的存储器。在本节中，我们将讨论既能处理信息（即判定）也能存储信息的数字逻辑电路。也就是说，这些结构不只根据现在的输入，而且基于之前发生的事（非常重要）做判定。这些结构通常被称为时序逻辑电路。它们与组合逻辑电路有显著区别，因为不同于组合逻辑电路，它们包含让它们记住之前的历史信息的存储元件。图3.23显示了一个时序逻辑电路的简图。注意存储元件，也注意输出既取决于现在的输入，也取决于存储在存储元件中的值。存储在存储元件中的值反映了以前发生的历史。时序逻辑电路被用来实现一种非常重要的被称为有限状态机的机制。在本质上，工程学的各分支都使用有限状态机。

35、例如，它们被用作电子系统、机械系统、航空系统等的控制器。交通灯控制器根据当前亮的灯（历史信息）和来自传感器，如道路上的管式导线和监视交通的光学设备的输入，将交通灯设为红、黄或绿色。当我们在第四章介绍计算机的冯诺伊曼模型时，我们将会看到位于计算机核心的是一个有限状态机控制器。3.6.1 一个简单的例子：密码锁使用一个简单的例子显示组合逻辑结构和时序逻辑结构之间的区别。假设一个人想用一把锁保护他的自行车，但是他又不想带钥匙。一个通用的解决方案就是密码锁。此人记住这个“密码”，用它来开锁。图3.24显示了两种类型的密码锁。在图3.24a中，锁由一个刻度盘组成，沿着周长等间隔的标着从0到30的数字。为

36、打开这把锁，必须知道其“密码”，例如密码可能是“右13-左22-右3”。如果这样的话，可以通过向右转动刻度盘两圈，直至拨号指向13，然后向左一圈，直至22，最后向右转直至3，锁即可打开。此时，锁被打开。重要的是转动的“顺序”。例如，如果向右转动刻度盘两圈，然后停在20，跟着向左转，以22结束，跟着向右转，以3结束，锁不会被打开。那就是说，即便刻度盘的最后位置是3，锁仍然不会被打开。为什么？因为这把锁存储了前面的旋转动作，根据当前的输入值（右3）和过去的操作历史，判定锁是否被打开。这个机制是一个时序逻辑结构的简单例子。另一类型的锁如图3.24b所示。该机制（通常）由4个轮子组成，每个轮子包含0到

37、9共10个数字。当数字被正确的排列时，锁就会被打开。锁是否被打开与4个轮子过去的旋转动作完全无关，锁完全不关心过去的旋转，唯一重要的就是4个轮子中的每个轮子的当前的值。这是一个组合逻辑结构的简单例子。用我们的平常的话来说，两种机制都被称为“组合锁”，令人好奇（英文combination lock字面上是“组合锁”）。事实上，只有图3.24b的锁是组合的锁。而图3.24a的锁最好被称为时序锁。3.6.2 状态的概念为了使图3.24a中的机制正常的工作，必须清楚打开这把锁的旋转顺序。尤其是要将正确的顺序“右13-左22-右3”与其他所有的顺序区分出来。例如，“右13-左29-右3”不允许打开锁。同

38、样的，“右10-左22-右3”也不允许打开锁。问题是在任意时刻，对于锁的唯一的外部输入就是当前的旋转。为了使图3.24a中的锁工作，必须识别出几个相关的情况，如下所示：A. 锁未被打开，没有实施相关的操作；B. 锁未被打开，但是用户只完成了右13的操作；C. 锁未被打开，但是用户只完成了右13，跟着左22的操作；D. 锁被打开。我们把这4种情况标为A, B, C和D。我们把每一种情况称为锁的状态。状态的概念在计算机工程，事实上在工程学的所有分支中都是非常重要的概念。一种机制的状态，更一般的说，一个系统的状态，就是系统中所有被明确表示的相关项目的一个瞬态图。即：一个系统的状态，就是系统中所有相关

39、的元素在一个瞬时的瞬态图。在图3.24a中的锁的情况下，有4个状态A, B, C和D。要么锁被打开（状态D），要么锁未被打开，我们已经实施了0个（状态A），1个（状态B），或2个（状态C）正确的操作。这是所有可能存在的状态的总数。问题：为什么？也就是说，对于那把号码锁，描述其第5个可能的状态的瞬态图是什么？有许多可以通过状态的方法来容易的描述系统的例子。篮球赛的状态可以通过篮球场上的记分牌来描述。图3.25显示了篮球赛的状态是得克萨斯73，俄克拉荷马68，下半场还剩下7分钟38秒，投篮秒表还剩下14秒，得克萨斯持球，两队都有4次犯规。这是篮球赛的一个瞬态图。它描述了篮球赛现在的状态。如果12秒

40、之后，一名得克萨斯队员投了一个2分的球，新的状态将被更新的记分牌所描述。即，得克萨斯75，俄克拉荷马68，下半场还剩下7分钟26秒，投篮秒表回到25秒，俄克拉荷马持球。井字游戏也可以通过状态的概念所描述。回忆这个被两个人玩的游戏（或者，我们以一个人和计算机对战的情况为例）。每当计算机让人走一步时游戏的瞬态图就是其状态。游戏玩法如下：图中有9个位置，人和计算机轮流在空位上放X（人）和O（计算机），人先放。第一个把3个符号（对于人是3个X，对于计算机是3个O）放为一条直线的就是赢家，直线可以是垂直的、水平的、或对角线方向。在人和计算机都没有开始时的初始状态如图3.26a所示。图3.26b显示的是如

41、果人在第一步在左上角放了一个X，当他被提示走第二步时，游戏的一个可能的状态。如状态所示，计算机在第一步在中间的方块里放了一个O。图3.26c显示的是如果人在第二步在右上角放了一个X（在左上角放了一个X之后），当他被提示走第三步时，游戏的一个可能的状态。如状态所示，计算机在上面中间的方块里放了第二个O。3.6.3有限状态机我们已经知道状态是在某一特定时刻，系统内所有相关部分的一个瞬态图。在其他时刻，系统可能处于其他状态。通常，系统的行为通过描述为有限状态机，可以更好的被理解。有限状态机由5个元素组成：1、 有限数目的状态；2、 有限数目的外部输入；3、 有限数目的外部输出；4、 明确定义的所有状

42、态转换；5、 明确定义的每个外部输入值的决定因素。状态的集合表示了系统中所有可能的状态（或瞬态图）。每一个状态转换描述了什么使一个状态转换到另一个状态。状态图有限状态机可以通过状态图被方便的表示出来。图3.27就是一个状态图的例子。状态图被画为一组圆（每一个圆对应于一个状态），和一些状态之间的一组连接（每个连接被画为一个箭头）。对于连接，更确切的术语是弧线。每一条弧线确定一个状态的转换。每条弧线的箭头说明系统从哪一个状态来，要到哪一个状态去。我们把系统来的状态称为当前状态，要去的状态称为下一个状态。图3.27的状态图表示的有限状态机由3个状态组成，有6个状态转换。注意，从状态Y到状态X没有状态

43、转换。通常对于一个当前状态，有多个到下一个状态的转换，发生哪一个状态转换取决于外部输入的值。在图3.27中，如果当前状态是X，外部输入的值是0，则下一个状态是Y；如果当前状态是X，外部输入的值是1，则下一个状态是Z。简而言之，下一个状态是由当前状态和当前的外部输入的组合决定的。系统的输出值仅由系统的当前状态决定，或者由当前状态和当前的外部输入的组合决定。在我们将研究的所有例子中，输出值仅由系统的当前状态决定。在图3.27中，当系统的状态是X时，输出是101；当系统的状态是Y时，输出是110；当系统的状态是Z时，输出是001。图3.28是图3.24a的密码锁的状态图，其正确的密码是“右13-左2

44、2-右3”。注意，4个状态被标为A, B ,C和D，表示锁被打开、或者锁未被打开，到目前为止，已经被实施的正确旋转的次数。外部的输入是可能的旋转操作。输出是“开”或“不开”。输出与每个状态明确相关，也就是说，在状态A, B 和C，输出是“不开”；在状态D，输出是“开”。再注意，从每一个状态出去的弧线都包含了当锁处于该状态时，一个人可能实施的所有操作。例如，在状态B时，所有可能的旋转可以被描述为（1）左22，和（2）除了左22之外的其他操作。注意，在图3.28中，从状态B发出的箭头有两条，对应于这两种情况。类似的，我们可以画出我们先前描述的篮球赛的状态图，每一个状态是记分牌的某个可能的情况。当裁

45、判吹哨或另一队得球时，就会发生状态转换。我们在前面显示，当得克萨斯投了一个2分球时，就会造成状态转换。很明显，描述篮球赛的有限状态机的状态数目将会是巨大的。同样明显的是，与一个人可以画出的任意一对状态之间的连接相比，从一个状态向另一个状态的合理转换的数目却很小。输入是自上一个转换发生后，发生在篮球场上的行为，一些输入值是：得克萨斯投了一个2分球，俄克拉荷马投了一个3分球，得克萨斯动球，俄克拉荷马成功抢得篮板球，等等。输出是球赛的最后结果，有3个输出值：球赛还在进行中，得克萨斯赢，俄克拉荷马赢。我们可以从得克萨斯30分、俄克拉荷马28分的状态，画一条弧线到得克萨斯、俄克拉荷马都是30分的不分胜负

46、的状态吗？有没有可能存在两个状态：一个是得克萨斯30-28领先，另一个是比分30-30，但是在二者之间没有弧线？时钟关于有限状态机的行为，还有一个重要的属性没有讨论触发状态向下一个转换的机制。在“时序”密码锁的例子中，这个机制就是以某一方向旋转刻度盘的完成，以及向可能的方向开始旋转触发。在篮球赛的例子中，该机制是通过裁判吹哨或某人得分，或另一队得球触发的。通常，触发状态从一个向下一个转换的机制是一个时钟电路。时钟电路，或更通用的说法，时钟，是发出的信号值在0伏和某个特殊的固定的电压之间交替，用数字逻辑术语来说，时钟是信号值在0和1之间交替。图3.29显示了时钟信号的值是时间的函数。时钟周期是指

47、重复的时间间隔序列的一个时间间隔，如图3.29所示。在有限状态机的电子电路实现中，从一个状态向另一个状态的转换发生于每一个时钟周期的开始。3.6.4例子：一个有限状态机的完整实现我们将以实现一个有限状态机的时序逻辑电路的逻辑说明来结束这一节。我们的例子是一个交通信号控制器，如图3.30所示。注意，信号是“危险、向右移”，信号还包括5个灯（用数字1到5标记）。与许多时序逻辑电路类似，控制器的作用是为了指挥系统的行动。在我们这个例子中，系统是一组交通信号灯，控制器的工作就是让这5盏灯按如下顺序开关：在第一个周期，所有灯关；下一周期，1和2灯开；再下一个周期，1，2，3和4灯开；在下面一个周期，所有

48、5个灯都开；然后，重复这个顺序：下一周期，所有灯关，跟着1和2开，跟着1，2，3和4开，等等。每一周期持续0.5秒。图3.31是描述交通信号行为的有限状态机。注意，有四个状态，每一个表示4个相关情况之一。注意，从每一个状态向下一个状态的转换，如果开关打开（输入=1），灯就按照描述的顺序闪亮，如果开关关上，状态总是立即转换到“全关”的状态。图3.32显示了实现图3.31有限状态机的时序逻辑电路的实现情况。图3.32a是简图，与图3.23类似。注意，有一个外部输入开关，决定灯是否可以亮；有3个外部输入，一个控制1和2灯何时亮，一个控制3和4灯何时亮，一个控制5灯何时亮。注意，有2个内部的存储元件，用来记住控制器处于哪一个状态，由交通危险信号的过去的行为决定了哪一个状态。最后注意，为了让状态转换每0.5秒发生，还有一个周期是0.5秒的时钟信号。