带你了解《数字设计与计算机体系结构》（原书第 2 版--ARM 版）第 3 期：定时逻辑设计

点击查看第一章
点击查看第二章

第3章

时序逻辑设计

3.1　引言

时序（sequential）逻辑。时序逻辑输出取决于当前的输入值和之前的输入值，所以说时序逻辑具有记忆功能。时序逻辑可能明确地记住某些先前的输入量，也可能从先前的输入量中提取更小一部分信息，称为系统的状态（state）。时序逻辑电路的状态由一组称为状态变量（state variable）的位构成，包含了用于解释未来电路行为的所有过去信息。
这一章中，我们将首先学习锁存器和触发器，它们是能够存储一位状态的简单时序逻辑电路。通常，时序逻辑电路的分析很复杂。为了简化设计，我们将只涉及同步时序逻辑电路，其由组合逻辑和一组表示电路状态的触发器组成。此章中还将介绍有限状态机，它是设计时序电路的一种简单方法。最后，我们将分析时序电路的速度，讨论提高时钟速度的并行方法。

3.2　锁存器和触发器

存储器件的基本模块是一个双稳态（bistable）元件。这个元件有两种稳定的状态。如图3-1a所示，一对反相器组成的环路构成了一个简单的双稳态元件。图3-1b重画了相同的电路，以突出其对称性。这两个反相器交叉耦合（cross-coupled），即I1的输入是I2的输出，反之亦然。这个电路没有输入，但是它有两个输出，Q和。这个电路的分析与组合电路不同，因为它是循环的：Q取决于，反过来又取决于Q。

考虑两种情况，Q=0或者Q=1。针对每一种情况的结果，我们可以得到：

• 情况Ⅰ：Q=0。
  如图3-2a所示，I2输入Q=0，则在上的输出为1。I1输入为=1，则在Q上的输出为0。这和原来假设的Q=0是一致的，于是这种情况被称为稳态。
• 情况Ⅱ：Q=1。
  如图3-2b所示，I2输入为1，则在上输出为0。I1输入为0，在Q上输出为1，这也是一种稳态。

因为交叉耦合的反相器有两种稳定状态：Q=0和Q=1，所以电路被称为双稳态。隐含的一点是电路可能存在第三种状态，其两个输出均处于0和1之间的一半。这种状态称为亚稳态（metastable），我们将在3.5.4节中再进行讨论。
具有N种稳态的元件可以表示log2 N位的信息，所以双稳态元件可以存储一位信息。耦合反相器状态包含在二进制状态变量Q中。Q的值保持了用以解释电路未来行为的过去信息。在此例子中，如果Q=0，它将永远保持0值，如果Q=1，它将永远保持1值。如果Q已知，则也已知，所以电路的另外一个节点不包含其他任何信息。另一方面，也可以作为一个有效的状态变量值。
当第一次加电到此时序电路时，它的初始状态往往未知和不可预料。电路每一次启动的初始状态都有可能不同。
虽然交叉耦合反相器可以存储一位信息，但因为没有用于控制状态的输入，它并没有什么实用价值。其他的双稳态元件，比如锁存器和触发器，提供了可以控制状态变量值的输入，本节下面部分将介绍这些电路。

3.2.1　SR锁存器

SR锁存器是一个最简单的时序电路。如图3-3所示，它由一对耦合的或非门组成。SR锁存器有两个输入S和R，两个输出Q和Q。SR锁存器与耦合的反相器相似，但是它的状态可以通过输入量S和R来控制，可以置位（set）或复位（reset）Q的输出。

通过真值表可以理解陌生的电路。或非门中只要有一个输入为1，则输出为0。考虑S和R的4种可能组合。

• 情况Ⅰ：R=1，S=0。
  N1至少有一个R=1的输入，则输出Q=0，N2的输入Q=0和S=0，则输出=1。
• 情况Ⅱ：R=0，S=1。
  N1输入0和，因为我们还不知道的值，所以我们不能确定输出的Q值。N2至少有一个S=1的输入，则输出=0。再次研究N1，可以知道它的两个输入都为0，所以输出Q=1。
• 情况Ⅲ：R=1，S=1。
  N1和N2至少有一个的输入（R或者S）为1，于是分别产生一个为0的输出。所以Q和同时为0。
• 情况Ⅳ：R=0，S=0。
  N1的输入为0和。因为还不知道的值，所以不能确定输出的值。N2的输入为0和Q。因为不知道Q的值，所以也不能确定输出的值。我们在这里被卡住了。这很像耦合的反相器。但是我们知道Q必须为0或者为1。于是，可以通过考察每一种子情况的方法来解决这个问题。
• 情况Ⅳa：Q=0。
  因为S=0，Q=0，则N2在上的输出为1，如图3-4a所示，现在N1的输入为1，于是它的输出Q=0，这和原来假设是一致的。
• 情况Ⅳb：Q=1。
  因为Q=1，则N2在上的输出为0，如图3-4b所示，现在N1的两个输入R=0，=0，于是它的输出Q=1，这和原来假设是一致的。

综上所述，假设Q的初值已知，记为Qprev。在我们进入情况Ⅳ之前，Qprev为1或者为0表示系统状态。当R=S=0时，Q将保持初值Qprev不变，Q将取Q初值的反值（Qprev）。这个电路有记忆功能。
图3-5中的真值表总结了4种情况。输入S和R表示置位和复位。置位表示将一个位设为1，复位表示将一个位设为0。输出Q和Q通常为互相取反的值。当R有效时，Q被复位为0，Q=1。当输入均为无效时，Q将保持初值Qprev不变，R和S同时有效是没有意义的，因为锁存器不可能同时被置位或者复位，这样会产生两个输出为0的混乱电路响应。

SR锁存器的符号表达式如图3-6所示。使用符号表示SR锁存器是抽象化和模块化的一个运用。有很多方法可以构造SR锁存器，包括使用不同的逻辑门或者晶体管。满足图3-5的真值表给定关系的电路元件都被称为SR锁存器，并采用图3-6中的符号表示。
和耦合的反相器一样，SR锁存器是一个在Q上存储一位状态的双稳态元件。但是Q的状态可以通过输入S和R控制。R有效时状态被复位为0，S有效时状态被置位为1。当S和R都无效时，状态保持初值不变。注意，输入的全部历史可以由状态变量Q解释。无论过去置位或复位是如何发生的，都需要通过最近一次置位或复位操作来预测SR锁存器未来行为。

3.2.2　D锁存器

当SR锁存器中S和R同时取真值时，其输出不确定，使用起来很不方便。而且，输入S和R混淆了时间和内容。输入有效时不仅需要确定是什么内容，而且需要确定将在何时改变。将内容和时间分开考虑会使电路设计变得简单。如图3-7a所示的D锁存器解决了这些问题。它有2个输入：数据输入D用以控制下一个状态的值；时钟输入CLK用以控制状态发生改变的时间。
我们同样通过图3-7b中的真值表分析D锁存器。为了方便，我们先考虑外部的节点、S和R。如果CLK=0，则S=R=0，D的值无任何意义。如果CLK=1，根据D的不同取值，一个与门输出为1，而另外一个与门输出为0。给定S和R，Q和的值可以根据图3-5确定。注意到CLK=0时，Q将保持原来的值Qprev不变；当CLK=1时，Q=D。在所有的情况中，的值始终是Q的取反，符合逻辑。D锁存器避免了S和R同时有效而造成的奇怪情况。
综上所述，时钟可以控制数据通过锁存器。当CLK=1时，D锁存器是透明的（trans-parent）：数据D通过D锁存器流向Q，D锁存器就像是一个缓冲器。当CLK=0时，D锁存器是阻塞的（opaque）：它阻止了新的数据D通过D锁存器流向Q，Q保持原来的值不变。所以D锁存器有时被称为透明锁存器或者电平敏感锁存器。D锁存器的电路符号如图3-7c所示。

当CLK=1时，D锁存器不断更新它的状态。在本节的后面部分将看到，如何在特定的时刻更新状态。下一节将介绍D触发器。

3.2.3　D触发器

一个D触发器可以由两个反相时钟控制的背靠背的D锁存器构成，如图3-8a所示。锁存器L1称为主锁存器。第二个锁存器L2称为从锁存器。它们之间的节点为N1。图3-8b给出了D触发器的电路符号。当不需要输出Q时，D触发器的符号可以简化成图3-8c所示。

当CLK=0时主锁存器是透明的，从锁存器是阻塞的。所以D的值将无条件传送到N1。当CLK=1时，主锁存器变成阻塞的，从锁存器变成透明的。N1的值将传送到Q，但是N1和D之间被切断。所以，在时钟从0上升到1之前并且在时钟开始上升之后，D值立即被复制到Q。在其他任何时刻，因为总有一个阻塞的锁存器来阻断D到Q的通路，Q将保持原来的值不变。
换句话说，D触发器在时钟上升沿时将D值复制到Q，在其他时间D触发器保持原有的状态。一定要记住这个定义，一个刚入门的数字设计师经常忘掉了某个触发器的功能。时钟的上升沿也经常简称为时钟沿（clock edge）。输入D确定了新的状态，时钟沿确定了状态发生改变的时间。
D触发器也常称为主从触发器（master-slave flip-flop）、边沿触发器（edge-triggered flip-flop）或者正边沿触发器（positive edge-triggered flip-flop）。电路符号中的三角表示触发器使用时钟边沿触发。当不需要输出Q时，经常被省略。
例3.1　计算触发器的晶体管数量。构成一个本节介绍的D触发器需要多少个晶体管？
解：构成一个与非门或者一个或非门需要用4个晶体管。一个非门需要用2个晶体管。一个与门可以由一个与非门和一个非门组成，所以它将用6个晶体管。一个SR锁存器需要用2个或非门或8个晶体管。一个D锁存器需要用一个SR锁存器、2个与门和一个非门或22个晶体管。一个D触发器需要用两个D锁存器和一个非门或46个晶体管。3.2.7节中介绍了一种使用传输门的更高效的CMOS实现方法。

3.2.4　寄存器

一个N位的寄存器由共享同一时钟的一排N个触发器组成，所以寄存器的所有位同时被更新。寄存器是组成时序电路的关键结构。图3-9中给出了其原理图和一个4位输入寄存器的电路符号，其输入是D3:0，输出是Q3:0，均为4位总线。

3.2.5　带使能端的触发器

带使能端的触发器增加了另外一个输入EN（ENABLE），用于确定在时钟沿是否载入数据。当EN=1时，带使能端的触发器和普通的D触发器一样。当EN=0时，带使能端的触发器忽略时钟，保持原来的状态不变。当我们希望在某些时间（而不是在每一个时钟沿时）载入一个新值到触发器中时，带使能端的触发器非常有用。
图3-10给出了用一个D触发器和一个额外的门组成一个带使能端触发器的两种方法。在图3-10a中，如果EN=1，一个输入多路器选择是否传递D的值。如果EN=0，再次循环Q原来的状态。在图3-10b中，时钟被门控（gated）。如果EN=1，CLK像通常一样作为开关来控制触发器。如果EN=0，CLK=0，则触发器保持原来的值不变。注意，当CLK=1时，EN不能改变，以免触发器出现一个时钟毛刺（在不正确的时间进行切换）。一般而言，在时钟上设置逻辑不是一个好的主意。时钟门控可能使时钟延迟而导致时序错误，我们将在3.5.3节中进一步介绍。只有当你确实知道要做什么时，才能这样做。带使能端的触发器电路符号如图3-10c所示。

3.2.6　带复位功能的触发器

带复位功能的触发器增加了一个输入RESET。当RESET=0时，带复位功能的触发器和普通的D触发器一样。当RESET=1时，带复位功能的触发器忽略D并且将输出Q复位为0。当系统加电需要将触发器设置为已知状态（即0）时，带复位功能的触发器十分有用。
触发器可能是异步（asynchronously）复位或者同步（synchronously）复位。同步复位功能的触发器仅仅在时钟上升沿时进行复位。异步复位的触发器只要RESET=1就可以对它进行复位操作，而与CLK无关。
图3-11a显示了如何用D触发器和与门构造一个同步复位触发器。当RESET=0时，与门将0输入到触发器。当RESET=1时，与门将D输入到触发器。在这个例子中，RESET是一个低电平有效（active low）信号，即复位信号为0时执行对应操作功能。通过增加一个反相器，电路中的RESET可以用高电平有效的复位信号RESET代替。图3-11b和图3-11c是高电平有效复位触发器的符号。

异步复位的触发器需要调整触发器的内部结构，留在习题3.13中。它们也是设计师们经常要用到的基本元件。
带置位功能的触发器也偶尔被使用。置位时，触发器被置为1。它们以同步或异步的方式完成置位操作。带置位和复位功能的触发器可以带有使能输入端，也可以组成N位寄存器。

3.2.7　晶体管级的锁存器和触发器的设计

例3.1说明通过逻辑门构造锁存器和触发器需要大量的晶体管。但是锁存器的基本作用是穿透或者阻塞，类似一个开关。回忆1.7.7节内容，传输门是构成CMOS开关的高效方法，可以利用传输门的优点来减少晶体管的数量。
一个简洁的D锁存器可以用一个传输门构成，如图3-12a所示。当CLK=1和CLK=0时，传输门是开放的，于是D传输到Q，D锁存器是透明的。当CLK=0和CLK=1时，传输门是关闭的，于是D和Q之间隔离，D锁存器是阻塞的。这种锁存器有两个主要缺点：

• 输出节点浮空：当锁存器被阻塞，Q的值没有被任何一个门钳住。所以Q被称为浮空（floating）节点或者动态（dynamic）节点。经过一段时间后，噪声和电荷泄漏将扰乱Q的值。
• 没有缓冲：缺少缓冲将在众多商业的芯片中导致故障。即使在CLK=0时，如果噪声尖峰将D值拉成一个负电压，也可以打开nMOS晶体管，而使得锁存器导通。同样，当D的噪声尖峰超过VDD时也可以使得pMOS晶体管导通。由于传输门是对称的，所以这使得在Q上的噪声可能反向驱动而影响输入D。一般的规则是传输门的输入或时序电路的状态节点都不应暴露在有噪声的外部世界中。

图3-12b是在现代商业芯片中由12个晶体管构成的一个D锁存器。它也可以用时钟控制的传输门来构成，但是它增加了反相器I1和I2作为对输入和输出的缓冲。锁存器的状态被钳在节点N1上。反相器I3和三态缓冲T1，给N1提供反馈，使N1的值固定。当CLK=0时，如果在N1上产生一个小的噪声，T1将驱动N1回到有效的逻辑值。
图3-13中D触发器可以通过两个由CLK和CLK控制的静态锁存器构成，同时去除了多余的内部反相器，所以这个触发器仅需要20个晶体管。

3.2.8　小结

锁存器和触发器是构成时序电路的基本模块。记住，D锁存器是电平敏感的，D触发器是边沿触发的。当CLK=1时，D锁存器可以是透明的，允许输入D传输到输出Q。D触发器在时钟边沿时刻将D值复制到Q。在其他时候，锁存器和触发器保持原来的状态不变。寄存器由排成一排的几个D触发器共享同一个CLK信号构成。

例3.2　触发器和锁存器比较。如图3-14所示，Ben在一个D锁存器和一个D触发器上给定D和CLK输入。帮助Ben确定每一种设计下Q的输出值。

解：图3-15给出了输出波形。假设在相应输入值变化时，输出Q上有一个小的延迟。箭头表示导致输出的改变的原因。Q的起始值未知，可能是0或者1，用一对水平线表示。首先考虑D锁存器。在第一个CLK的上升沿，D=0，所以Q值肯定变成0。当CLK=1时，每一次D值的改变都会导致Q值的改变。当CLK=0时，D值改变，Q值不变。接着考虑D触发器。在每一个CLK时钟上升沿到来时，D的值被复制到Q。在其他时间，Q值保持原来的状态不变。

3.3　同步逻辑设计

一般而言，所有不是组合电路的电路都可以称为时序电路，因为这些电路的输出不能简单地通过观察当前输入的值来确定。一些时序电路比较奇特。这一节将考察这些电路，然后介绍同步时序电路的概念和动态约束。我们将注意力集中在同步时序电路方面，这将使我们找到一种简易而系统的时序电路系统设计和分析方法。

3.3.1　一些有问题的电路

例3.3　非稳态电路。Alyssa遇到了三个设计很拙劣的反相器，它们以环状连接在一起，如图3-16所示。第三个反相器的输出反馈到第一个反相器的输入。每一个反相器都有1ns的传输延迟。确定电路的功能。
解：假设节点X的起始值是0。这使得Y=1，Z=0，所以X=1，这和我们刚开始的假设不一致。这个电路没有稳定的状态，称为不稳定态（unstable）或者非稳态（astable）。电路的行为如图3-17所示。如果X在0时刻上升，Y将在1ns时刻下降，Z将在2ns时刻上升，X将在3ns时刻下降。接着，Y在4ns时刻上升，Z将在5ns时刻下降，X将在6ns时刻再次上升，这个模式将一直重复下去。每一个节点以6ns为周期在0和1之间摆动。这个电路称为环形振荡器（ring oscillator）。

环形振荡器的周期取决于反相器的传输延迟。这个延迟时间又取决于反相器的制造工艺、电源电压，甚至工作温度等诸多因素。所以环形振荡器的周期很难准确预测。简而言之，环形振荡器是无输入和一个周期性改变输出的时序电路。
例3.4　竞争情况。Ben设计了一个新的D锁存器，并宣布这个设计比图3-17中的D锁存器要好。因为在这个电路中门的数量更少。他写出了真值表以确定输出Q的值，其中包括D和CLK两个输入以及锁存器的原始状态Qprev。根据这个真值表，Ben得出了布尔等式。他通过输出Q反馈得到了Qprev，设计如图3-18所示。不考虑每一个门的延迟，他的锁存器工作是否正确？

解：如图3-19所示，当某些门比其他的门速度慢时，电路有一个竞争情况将导致电路错误。假设CLK=D=1。锁存器可以是透明的，将D传送到Q，Q=1。现在CLK下降。锁存器将保持原来的状态，Q=1。但是，假设从CLK到CLK通过反相器的延迟比与门和或门的延迟要长。所以在CLK上升之前，N1和Q将同时下降。在这种情况下，N2将不能上升，Q值将被钳为0。

这是一个输出直接反馈到输入的异步电路设计例子。异步电路中经常会出现竞争情况而难以掌握。之所以出现竞争情况，是因为其电路的行为取决于两条通过逻辑门的路径中哪条最快。这样的电路可能可以工作，但是对于从表面上看是相同的电路，如果用几个延迟稍微不同的门替换，可能就无法正常工作。或者，这样的电路只能在一定的温度和电压下正常工作，只有在这个特定的条件下其逻辑门的延迟才刚好正确。这种错误是极其难以被查出的。

3.3.2　同步时序电路

前面的两个例子包含了环，也称为环路（cyclic path），其输出直接反馈到输入。它们是时序电路而不是组合电路。组合逻辑没有环路和竞争。特定值输入组合逻辑中，输出将在传输延迟内稳定为一个正确的值。但是，包含环路的时序电路存在不良的竞争和不稳定的动作。分析这样的电路十分耗时，很多聪明的人都会犯错误。
为了避免这些问题，设计师们在环路中插入寄存器以断开环路。这将电路转变成了组合逻辑电路和寄存器的组合。寄存器包含系统的状态，这些状态仅仅在时钟沿到达时发生改变，所以状态同步（synchronized）于时钟信号。如果时钟足够慢，在下一个时钟沿到达之前输入寄存器的信号都可以稳定下来，所有的竞争都被消除。根据在反馈环路上总是使用寄存器的原则，可以得到同步时序电路的一个规范定义。
通过电路的输入端、输出端、功能和时序说明可以定义一个电路。一个时序电路有一组有限的离散状态{S0，S1，…，Sk-1}。同步时序电路（synchronous sequential circuit）有一个时钟输入，它的上升沿表示时序电路状态发生转变的时间。我们经常使用当前状态（current state）和下一个状态（next state）这两个术语来区别目前系统的状态和下一个时钟沿系统将进入的状态。功能说明详细说明了在当前状态和输入值的各种组合下，此电路的下一个状态和输出值。时序说明包括了上界时间tpcq和下界时间tccq，即从时钟的上升沿直到输出发生改变的时间；建立时间tsetup和保持时间thold，即输入相对于时钟上升沿的稳定时间。
同步时序电路的组成规则告诉我们，如果一个电路是同步时序电路，它必须由相互连接的电路元件构成，且需要满足以下条件：

• 每一个电路元件要么是寄存器要么是组合电路；
• 至少有一个电路元件是寄存器；
• 所有寄存器接收同一个时钟信号；
• 每一个环路至少包含一个寄存器。

非同步时序电路称为异步（asynchronous）电路。
单个触发器是一个最简单的同步时序电路。它包含了一个输入D、一个时钟CLK、一个输出Q和{0，1}两种状态。一个触发器的功能规范是：下一个状态是D，输出Q是当前的状态，如图3-20所示。

我们经常称当前状态为变量S，称下一个状态为变量S。在这种情况下，S之后的撇号表示下一个状态，而不是取反的值。3.5节中将分析时序电路的时序关系。
两种常见的同步时序电路称为有限状态机和流水线。这将在后面的章节中介绍。
例3.5　同步时序电路。图3-21中哪些电路是同步时序电路？
解：图3-21a的电路是组合逻辑电路，不是时序逻辑电路，因为它没有一个寄存器。图3-21b的电路是一个不带反馈回路的简单时序电路。图3-21c的电路既不是组合电路也不是时序电路，因为它有一个锁存器，这个锁存器既不是寄存器也不是组合逻辑电路。图3-21d和图3-21e的电路是同步时序逻辑电路；它们是有限状态机的两种形式，将在3.4节中讨论。图3-21f的电路既不是组合电路也不是时序电路，因为它有一个从组合逻辑电路的输出端电路反馈到同一逻辑电路输入端的回路，但是在回路上没有寄存器。图3-21g的电路是同步时序逻辑电路的流水线形式，将在3.6节中讨论。图3-21h的电路严格地说不是一个同步时序电路，因为两个寄存器的时钟信号不同，它们有两个反相器的延迟。

3.3.3　同步和异步电路

从理论上讲，异步电路设计要比同步电路设计更为通用，因为系统时序不由时钟控制的寄存器所约束。正如能使用任意电压的模拟电路比数字电路更为通用，能够使用各种反馈的异步电路似乎比同步电路具有更强的通用性。然而，同步电路比异步电路更加容易设计，就类似于数字电路比模拟电路更加容易。尽管异步电路进行了数十年的研究，但实际上几乎所有的系统本质上都是同步的。
当然，在两个不同时钟的系统之间进行通信时，或者在任意的时刻接收输入时，异步电路偶尔也很重要。类似地，模拟电路在连续电压的真实世界中通信很重要。此外，异步电路的研究继续产生一些有趣的知识，其中的一些也将有利于改进同步电路。

3.4　有限状态机

同步时序电路可以描绘成图3-22的形式，称为有限状态机（Finite State Machine，FSM）。这个名字源于具有k位寄存器的电路可以处于2k种状态中的某一种唯一状态。一个有限状态机有M位输入、N位输出和k位状态，同时还具有一个时钟信号和一个可选的复位信号。有限状态机包含两个组合逻辑块：下一状态的逻辑（next state logic）和输出逻辑（output logic），以及一组用于存储状态的寄存器。在每一个时钟沿，有限状态机进入下一状态。这个下一状态是根据当前的状态和输入值计算出来的。根据有限状态机的特点和功能，通常被分为两类有限状态机。在Moore型有限状态机中，输出仅仅取决于当前的状态。在Mealy型有限状态机中，输出取决于当前的状态和输入值。有限状态机提供了系统的方法来设计给定功能说明的同步时序逻辑电路。这一章的后续部分将由一个实例开始介绍这种方法。

3.4.1　有限状态机设计实例

为了解释有限状态机的设计，我们考虑在校园中繁忙的十字路口建立一个交通灯控制器。工程系学生在宿舍和实验室之间的Academic大道上漫步。他们正在阅读关于有限状态机的教科书，而没有看前面的路。足球运动员们正喧嚷地拥挤在运动场和食堂间的Bravado大道上。他们正在向前和向后投球，也没有看他们前面的路。在两条大道上的十字路口发生了一些严重的事故。为了防止事故再次发生，系主任要求Ben安装一个交通灯。
Ben决定用有限状态机来解决这个问题。他分别在Academic大道和Bravado大道上安装了两个交通传感器TA和TB。传感器上输出1时，表示此大道上有学生出现；输出0时，表示大道上没有人。Ben又安装了两个交通灯LA和LB来控制交通。每一个灯接收数字信号输入，以确定显示绿色、黄色或红色。所以，有限状态机有TA和TB两个输入，LA和LB两个输出。十字路口的灯和传感器如图3-23所示。Ben采用了一个周期为5秒的时钟。在每一个时钟上升沿，灯将根据传感器改变。同时，Ben还设计了一个复位按键以便技术员在打开交通灯时将控制器设置为一个已知的起始状态。状态机的黑盒视图如图3-24所示。

Ben的第二步是画出状态转换图（state transition diagram），如图3-25所示。此图说明了系统中每一种可能的状态和两种状态之间的转换。当系统复位时，Academic大道上的灯是绿色，Bravado大道上的灯是红色。每5秒，控制器检查交通模式并决定下一步该如何处理。此时，若在Academic大道有交通，灯就不再改变。当Academic大道上没有交通时，此大道上的灯变成黄色并保持5秒，然后再变成红色，同时Bravado大道上的灯变成绿色。同样，在Bravado大道上有交通的时候，此大道上的灯保持绿色，然后变成黄色，最后变成红色。

在状态转换图中，圆圈代表状态，圆弧代表两种状态之间的转换。转换发生在时钟上升沿。时钟总是出现在同步时序逻辑电路中，而且仅仅根据状态转换图中发生状态转换的位置来控制何时发生状态转换，所以为简化起见，在状态转换图中不画出时钟。标有Reset的圆弧从外部进入S0状态，这说明不管当前是什么状态，系统复位时都应该进入的状态。如果一个状态有多个离开它的圆弧，这些圆弧标有触发每个状态转换的输入条件。例如，在S0状态，如果TA为真，系统将保持当前状态；如果TA为假，将转换成S1状态。如果状态只有一个离开它的圆弧，不管输入是什么，转换都会发生。例如，在S1状态，系统将总是转换到S2状态。在特定状态下的输出值也在状态中给出。例如，在S2状态，LA是红色，LB是绿色。
Ben将状态转换图重写为状态转换表（state transition table），如表3-1所示。它说明了每一种状态和输入值所产生的下一个状态S。表中使用了无关项（X），这表示下一个状态并不依赖于特定的输入。同时，在表中忽略了复位。实际上，可以使用带复位功能的触发器使得复位后总是进入S0状态，而不用考虑输入。
状态转换图中使用了抽象的状态标记{S0，S1，S2，S3}和输出标记{红灯，黄灯，绿灯}。为建立一个真实的电路，状态和输出必须按照二进制编码。Ben选择了简单的编码方式，如表3-2和表3-3所示。每种状态和每种输出都被编码成2位：S1:0、LA1:0和LB1:0。

Ben接着用二进制编码更新状态转换表，如表3-4所示。这个改进的状态转换表是一个可以确定下一个状态的逻辑真值表，定义了根据当前状态S和输入确定下一个状态S的逻辑函数。
通过这些表，可以直接读出下一个状态的与或式布尔表达式。

这些式子可以用卡诺图化简，但是使用观察方法化简更容易。例如，在S1的等式中的TB和项明显是多余的。所以S1可以简化成一个异或操作。式（3.2）给出了下一个状态的逻辑表达式。

同样，Ben针对每一个状态指出的输出写出了输出表，如表3-5所示。也可以直接读出这些输出的化简布尔表达式。例如，观察到仅仅在S1的行为真时，LA1为真。

最后，Ben以图3-22a的形式绘制了Moore型有限状态机的电路图。首先，画了一个2位的状态寄存器，如图3-26a所示。在每一个时钟沿，这个状态寄存器复制下一个状态S1:0到状态S1:0。这个状态寄存器在启动时收到一个同步或异步复位信号，初始化有限状态机。然后，根据等式（3.2）画出了下一个状态逻辑的电路图，这部分逻辑根据当前的状态和输入值计算出下一个状态的值，如图3-26b所示。最后，根据等式（3.3）画出了输出逻辑的电路图，这部分逻辑根据当前的状态计算输出值，如图3-26c所示。
图3-27给出了一个用于解释交通灯控制器经过一系列状态运行的时序图。图中显示了CLK、Reset、输入TA和TB、下一个状态S、当前状态S、输出LA和LB。箭头表明了因果关系，例如，当前状态的改变导致输出的改变，输入的改变导致下一个状态的改变。虚线表示在CLK的上升沿状态改变。
时钟的周期是5秒，所以交通灯最多每5秒改变一次。当这个有限状态机第一次启动时，它的状态是未知的，如图中的问号所示。所以系统应被复位到一个已知的状态。在这个时序图中，S被立即复位成S0，说明使用了带复位功能的异步触发器。在状态S0，LA是绿灯，LB是红灯。

此例中，复位后Academic大道上已经有交通。所以，控制器保持在S0状态，并保持LA是绿灯。此时Bravado大道上尽管有交通到达，也将开始等待。15秒之后，在Academic大道上的通行都通过了，TA开始下降。在随后的时钟沿，控制器将进入S1状态，LA变成黄灯。在下一个5秒之后，控制器进入S2状态，LA变成红灯，LB变成绿灯。控制器在状态S2上等待，直到在Bravado大道上的通行都通过了。它将进入状态S3，LB变成黄灯。5秒之后，控制器将进入状态S0，LB变成红灯，LA变成绿灯，这个过程重复进行。

3.4.2　状态编码

在先前的例子中，状态和输出的编码的选择是任意的。不同的选择将产生不同的电路。一个自然而然的问题是，如何确定一种编码，使之能够产生一个逻辑门数量最少或传输延迟最短的电路。遗憾的是，没有一种简单的方法可以找出最好的编码。现有的方法是尝试所有的可能情况，但当状态的数量很大时这也是不可行的。往往，可以通过观察的方法使得相关的状态或输出共享某些位从而来选择一种好的编码方式。计算机辅助设计工具也可以寻找可能的编码集合，并选择一种合理的编码。
在状态编码中，一种重要的决策是选择二进制编码还是选择独热编码。交通灯控制器的例子中使用了二进制编码（binary encoding），其中一个二进制数代表一种状态。因为log2 K位可以表示K个不同的二进制数，所以一个有K种状态的系统只需要log2 K位状态。
在独热编码（one-hot encoding）中，状态编码中的每位表示一种状态。它被称为独热编码，是因为在任何时候只有一个位是“热”或真。例如，一个有三个状态有限状态机的独热编码为001、010和100。状态的每一位要储存在一个触发器中，所以独热编码比二进制编码需要更多的触发器。但使用独热编码时，下一个状态和输出逻辑通常会更简化，需要的门电路也更少。最佳的编码方式取决于具体的有限状态机。
例3.6　有限状态机状态编码。一个N分频计数器有一个输出，没有输入。每循环N个时钟后，输出Y产生一个周期的高电平信号。换句话说，输出是时钟的N分频。3分频计数器的波形和状态转换图如图3-28所示。使用二进制编码和独热编码画出这个计数器的草图。

解：表3-6和表3-7给出了编码前的抽象状态转换表和输出表。

表3-8比较了三种状态的二进制编码和独热编码。

二进制编码使用2位状态。使用这种编码的状态转换表如表3-9所示。注意，这里没有输入；下一个状态只取决于当前的状态。输出表作为练习留给读者完成。下一个状态和输出的等式如下：

独热编码使用3位状态。这种编码的状态转换表如表3-10所示，输出表作为练习留给读者完成。下一个状态和输出的等式如下：

图3-29给出了每一种设计的原理图。二进制编码设计的硬件可以通过使Y和S0共享相同的门电路进行优化。同样，独热编码设计需要可置位（s）和可复位（r）的触发器来在复位时对状态机的S0进行初始化。最好的实现选择取决于门电路和触发器的相对成本，独热编码设计在这个特定的例子中更加可取。■

一种相关的编码方式是独冷编码，K个状态通过K位表示，其中的一位恰好为FALSE。

3.4.3　Moore型状态机和Mealy型状态机

迄今为止，我们已经介绍了Moore型状态机的例子，它的输出只取决于系统的状态。所以在Moore型状态机的状态转换图中，输出被标在圆圈内。Mealy型状态机和Moore型状态机很相似，但是输出取决于输入和当前的状态，所以在Mealy型状态机的状态转换表中，输出被标在圆弧上面而不是圆圈内。一个组合逻辑模块可以用输入和当前状态计算出输出，如图3-22b所示。
例3.7　Moore型状态机和Mealy型状态机的对比。Alyssa有一个带有限状态机大脑的机器宠物蜗牛。蜗牛沿着纸带从左向右爬行。这个纸带包含1和0的序列。在每一个时钟周期，蜗牛爬行到下一位。蜗牛爬行在纸带上，如果最后经过的2位是01时，蜗牛会高兴得笑起来。设计一个有限状态机计算蜗牛何时会发笑。蜗牛触角下面的位是输入A。当蜗牛发笑时，输出的Y为TRUE。比较Moore型状态机和Mealy型状态机设计。画出包含输入、状态和输出的每种设计时序草图。蜗牛爬行的序列是0100110111。
解：Moore型状态机需要3个状态，如图3-30a所示，确信你自己的状态转换图是正确的。特别是，当输入为0时为什么从S2到S1要画一个圆弧？
与Moore型状态机相比，Mealy型状态机只需要2个状态，如图3-30b所示。每一个圆弧被标注成A/Y。A是引起转换的输入值，Y是输出值。

表3-11和表3-12给出了Moore型状态机的状态转换图和输出表。Moore型状态机至少需要2位的状态。考虑使用以下二进制状态编码：S0=00，S1=01，S2=10。表3-13和表3-14重新写出了二进制状态编码的状态转换图和输出表。

通过这些表，可以找出下个状态和输出的表达式。注意，因为此状态机中不存在11这个状态，所以可以进一步化简这些表达式。这些不存在的状态对应的状态和输出可以不用考虑（在表中没有显示）。我们使用无关项来最小化等式。

表3-15给出了Mealy型状态机的状态转换和输出表。Mealy型状态机只需要1位状态。考虑使用二进制编码：S0=0，S1=1。表3-16重新写出了二进制状态编码的状态转换图和输出表。

对于这些表，可以通过观察得到下个状态和输出的表达式。

Moore型状态机和Mealy型状态机的电路原理图如图3-31所示。每种状态机的时序图如图3-32所示。两种状态机的状态序列有所不同。然而，Mealy型状态机的输出上升要早一个周期。这是因为其输出直接响应输入，而不需要等待状态的变化。如果Mealy型状态机的输出通过触发器产生延迟，它的输出将和Moore型状态机一样。在选择有限状态机设计类型时，需要考虑何时需要到输出响应。

3.4.4　状态机的分解

简化复杂有限状态机设计的一个方法是将一个复杂的有限状态机分解成多个互相作用的简单状态机，其中一些状态机的输出是另外一些状态机的输入。这种应用层次结构和模块化的方法称为状态机的分解（factoring）。
例3.8　不分解的状态机和分解后的状态机。修改3.4.1节中的交通灯控制器，以增加一个游行模式。当观众和乐队以分散的队形漫步到足球比赛时进入游行模式，此时保持Bravado大道上的灯是绿色。控制器需要增加两个新的输入：P和R。P保持至少一个周期有效以进入游行模式，R保持至少一个周期以退出游行模式。游行模式下，控制器按照平常时序运行直到LB变成绿色，然后保持LB为绿色这种状态直到游行模式结束。
首先，画出单个有限状态机的状态转换图，如图3-33a所示。然后，画出2个相互作用有限状态机的状态转换图，如图3-33b所示。在进入游行模式时，模式有限状态机的输出M为有效。灯控制有限状态机根据M的值、交通传感器TA和TB控制灯的颜色。

解：图3-34a给出了单个有限状态机的设计。状态S0到状态S3处于普通模式。状态S4到状态S7处于游行模式。这两个部分基本上相同，但是在游行模式下，有限状态机保持在状态S6，此时Bravado大道上的灯为绿色。输入P和R控制了在两个部分之间的转移。其有限状态机设计很杂乱。图3-34b显示了分解设计的有限状态机。模式有限状态机有2种状态，以跟踪处于正常模式或游行模式。当M为真，灯控制有限状态机将修改成保持在S2状态。

3.4.5　由电路图导出状态机

由电路图推导出状态转换图采用几乎与有限状态机设计相反的过程。这个过程是有必要的，比如承担一个没有完整文档的项目或者开展基于他人系统的逆向工程。

• 检查电路，标明输入、输出和状态位；
• 写出下一状态和输出布尔表达式；
• 构造下一状态和输出真值表；
• 删除不可能到达的状态以简化下一状态真值表；
• 给每个有效的状态位组合指定状态名称；
• 结合状态名称重写下一状态和输出真值表；
• 画出状态转换图；
• 使用文字阐述该有限状态机的功能。

在最后一步里，注意简洁地描述该有限状态机的主要工作目标和功能，而不是简单地重述状态转换图的每个转换。
例3.9　由电路导出有限状态机。Alyssa家门的键盘锁已经重装，因此她的旧密码不再有效。新键盘锁的电路图如图3-35所示。Alyssa认为这个电路可能是一个有限状态机，因此她决定由该电路图推导出状态转换图，从而打开门锁。

解：Alyssa首先检查电路，确定了电路的输入是A1:0，输出是Unlock。图3-35已经表明了状态位。由于电路的输出只取决于状态位，因此这是一个Moore型状态机。Alyssa写出该电路对应的下一状态和输出布尔表达式如下：

接下来，她写出下一状态和输出真值表，如表3-17和表3-18所示。她先根据式（3.12）标注真值表中取值为1的位置，其余位置标注为0。

然后，Alyssa通过去除未使用状态和利用无关项合并等方法简化真值表。S1:0=11这个状态从未在表3-17中被列为可能的下一状态，因此以这个状态作为当前状态的行都可以去除。对于当前状态S1:0=10，下一状态总是S1:0=00，这结果与输入无关，因此在真值表对应的输入栏填上无关项。简化真值表如表3-19和表3-20所示。

Alyssa为每个状态位组合取名：S0是S1:0=00，S1是S1:0=01，S2是S1:0=10。表3-21和表3-22展示了使用状态名称的下一状态和输出真值表。

Alyssa通过表3-21和表3-22画出如图3-36所示的状态转换图。通过审视状态转换图，她得知该有限状态机的工作原理：该状态机在检测到A1:0的输入值是一个3跟着一个1时就会将门解锁，然后门会再次关闭。Alyssa尝试在门锁键盘上输入该数字串，成功将门打开。

3.4.6　小结

有限状态机是根据给定规范设计同步时序电路的强有力的系统化方法。设计有限状态机的步骤如下：
确定输入和输出；

• 画状态转换图；

• 对于Moore型状态机：

  • 写出状态转换表；
  • 写出输出表；

• 对于Mealy型状态机：

  • 写出组合的状态转换和输出表；
• 选择状态编码—这个选择将影响硬件设计；
• 为下一个状态和输出写出布尔表达式；
• 画出电路草图；

本书将反复使用有限状态机来设计复杂的数字系统。

3.5　时序逻辑电路的时序

我们知道，一个触发器在时钟上升沿到达时将D复制到输出Q。这个过程称为在时钟沿对D进行采样（sampling）。当时钟上升沿时，如果D是0或1的稳定状态，这个动作定义很清晰。但是，如果D在时钟上升时发生了变化，将会发生什么情况？
这个问题类似于面对一个正在捕捉图片的照相机。设想这样一幅图片，一只青蛙正在从一个睡莲上跳入湖水里。如果你在青蛙跳之前拍照，你将看到一只在睡莲上的青蛙。如果你在青蛙跳过之后拍照，你将看到水面上的波纹。如果你刚好在青蛙跳的时候拍照，你将看到一只伸展的青蛙从睡莲跳入湖水的模糊影像。照相机的特征由孔径时间（aperture time）刻画，在此时间内一个物体必须保持不动，照相机才能获得清晰的图像。同样，一个时序元器件在时钟沿附近也有孔径时间。在孔径时间内输入必须稳定，触发器才能产生明确定义的输出。
时序元件的孔径时间分别用时钟沿前的建立时间（setup time）和时钟沿后的保持时间（hold time）定义。正如静态约束限制我们使用在禁区外的逻辑电平，动态约束限制我们在外部孔径时间中使用改变信号。利用动态约束，我们可以认为时间是基于时钟周期的离散单元，正如我们将信号的电平认为是离散的1和0。一个信号可以有毛刺，也可以在有限时间内反复振荡。在动态约束下，我们仅关心一个时钟周期最后时的最终值，这是一个稳定下来的值。所以，我们可以简单地用A[n]表示在第n个时钟周期结束时信号A的值，其中n是一个整数，而不再考虑t时刻A的值A(t)，其中t是一个实数。
时钟周期应该足够长使所有的信号都稳定下来。这限制了系统的速度。在真实的系统中，时钟不能准确地同时到达所有的触发器。这个时间变量称为时钟偏移（clock skew），从而进一步增加必要的时钟周期。
在面对真实的世界时，动态约束往往是不可能满足的。比如考虑一个通过按键输入的电路。一只猴子可能在时钟上升时按下了按键。此时触发器捕获了一个在0和1之间的值，这个值不可能稳定到一个正确的逻辑值，这称为亚稳态现象。解决这种异步输入的方法是使用同步器，这个同步器产生非法逻辑值的概率非常小（但是不为0）。
我们将在下面的章节里展开讨论这些问题。

3.5.1　动态约束

到目前为止，我们将重点放在时序电路的功能规范上。触发器和有限状态机等同步时序电路也有时序规范，如图3-37所示。当时钟上升时，输出在时钟到Q的最小延迟tccq之后开始改变，并在时钟到Q的传播延迟tpcq之后达到稳定值。它们分别代表了通过电路的最快和最慢的延迟。为了电路对输入量正确采样，在时钟上升沿到来之前，输入必须在建立时间tsetup内保持稳定，在时钟上升沿之后，输入必须保持至少保持时间thold内保持稳定。建立时间和保持时间合在一起称为电路的孔径时间，为输入保持稳定状态的时间总和。

动态约束（dynamic discipline）是指同步时序电路的输入在时钟沿附近的建立和维持孔径时间内必须保持稳定。为了满足这个要求，要保证触发器在对信号进行采样时，信号不能变化。因为在采样时仅关心最终的输入值，从而可以将信号认为是在时间和逻辑电平上都是离散的量。

3.5.2　系统时序

时钟周期或者时钟时间Tc是重复的时钟信号中上升沿之间的时间间隔。它的倒数fc=1/ Tc是时钟频率。在其他情况一样时，提高时钟的频率可以增加数字系统在单位时间内完成的工作量。频率的单位是Hz，或者是每秒的周期数：1MHz=106Hz，1GHz=109Hz。
图3-38a给出了同