第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和 - 情况Ⅲ：R=1，S=1。
N1和N2至少有一个的输入（R或者S）为1，于是分别产生一个为0的输出。所以Q和 - 情况Ⅳ：R=0，S=0。
N1的输入为0和 - 情况Ⅳa：Q=0。
因为S=0，Q=0，则N2在 - 情况Ⅳb：Q=1。
因为Q=1，则N2在
综上所述，假设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给出了同步时序电路中一条普通路径，我们所希望计算其时钟周期。在时钟的上升沿，寄存器R1产生输出Q1。这些信号进入一个组合逻辑电路产生D2，并作为寄存器R2的输入。时序图如图3-38b所示，每一个输出信号在输入信号发生改变的最小延迟后开始改变，在输入信号稳定之后的传输延迟时间内输出信号稳定到最终的值。灰色箭头表示通过R1和组合逻辑块的最小延迟，灰色的箭头代表通过R1和组合逻辑块的传输延迟。我们对第二个寄存器R2的建立时间和保持时间来分析时序约束。
1.建立时间约束
图3-39只显示了路径的最大延迟时序图，用灰色的箭头指示。为了满足R2的建立时间，D2应在不迟于下一个时钟沿之前的建立时间前稳定。所以我们得出了最小时钟周期的等式：
在商业设计中，时钟周期经常由研发总监和市场部提出（以确保产品的竞争性）。而且，制造工艺确定了触发器时钟到Q的传输延迟tpcq和建立时间tsetup。可以重写式（3.13）以确定通过组合逻辑的最大传输延迟，这是设计师经常只能控制的一个变量。
在圆括号内的项tpcd+tsetup称为时序开销（sequencing overhead）。理想状态下，整个周期时间Tc都应用于有用的组合逻辑计算，其传播延迟为tpd。但是触发器的时序开销占用了周期时间。式（3.14）称为建立时间约束（setup time constraint）或最大延迟约束（max-delay constraint），因为它取决于建立时间，并限制了组合逻辑的最大延迟时间。
如果组合逻辑的传输延迟太大，D2有可能在R2对其采样时稳定不到它的最终值。所以，R2可能采样到一个不正确的结果或者一个处于禁止区域的非法电平。在这种情况下，电路将出现故障。解决这个问题的方法有两个：增加时钟周期或重新设计组合逻辑以缩短传输延迟。
2.保持时间约束
图3-38a中的寄存器R2也有保持时间约束。在时钟上升沿之后的保持时间（thold）内，它的输入D2必须保持不变。根据图3-40，D2在时钟上升沿之后tccq+tcd内可能会变化。所以，我们可以得到
tccq和thold是触发器的属性，不能被设计者控制。重新排列等式，可以得到组合逻辑的最小延迟：
式（3.16）也称为最小延迟约束（min-delay constraint），它限制了组合逻辑的最小延迟。
我们假定任何逻辑元件都可以互连而不会导致时序问题。尤其是希望如图3-41所示的2个触发器可以直接级连，而不导致保持时间问题。
在此情况中，因为在触发器之间没有组合逻辑，所以tcd=0。带入式（3.16）得出下列等式：
换句话说，一个可靠触发器的保持时间要比它的最小延迟短。触发器经常被设计成thold=0，于是式（3.17）总是可以满足。除非特别注明，本书中经常假定和忽略保持时间约束。
然而，保持时间约束又非常重要。如果它们不能满足，唯一的解决办法是需要重新设计电路以增加组合逻辑的最小延迟。与建立约束不同，它们不能通过调整时钟周期来改正。以目前的技术水平，重新设计和制造一个集成电路需要花费数月的时间和上千万美元，所以违反保持时间约束将产生非常严重的后果。
3.小结
时序电路中的建立时间和保持时间约束了触发器之间组合逻辑的最大延迟和最小延迟。现代的触发器经常设计为可以使得组合逻辑的最小延迟是0，即触发器可以背靠背地放置。因为高速电路中高时钟频率意味着短的时间周期，最大延迟约束限制了其关键路径上串联门的个数。
例3.10 时序分析。Ben设计了图3-42所示的电路。根据组件的数据手册，触发器的时钟到Q最小延迟和传输延迟分别为30ps和80ps。它们的建立时间和保持时间分别为50ps 和60ps。每一个逻辑门的传输延迟和最小延迟分别为40ps和25ps。帮助Ben确定最大的时钟周期，是否能满足保持时间约束。这个过程被称为时序分析（timing analysis）。
解：如图3-43a所示为信号变化时的波形图。输入A到D被寄存，所以它们只在CLK上升后立刻改变。
关键路径发生在B=1，C=0，D=0，且A从0上升为1，触发n1上升，X上升，Y下降，如图3-43b所示。这条路径含有3个门的延迟。对于关键路径，我们假定对于每一个门都需要它全部的传输延迟。Y必须在下一个时钟上升沿到来之前建立。所以最小的周期是
最大的时钟频率是fc=1/Tc=4GHz。
在最短路径上，当A=0，C上升，导致X上升，如图3-43c所示。对于最短路径，我们假定每个逻辑门仅在最小延迟之后翻转。这条路径只包含一个门的延迟，所以它将在tccq+tcd=30+25=55ps之后发生。但是这个触发器需要60ps的保持时间，意味着X必须在时钟上升沿到来之后的60ps内保持稳定，X触发器才可以可靠地对它的值进行采样。在这种情况下，在第一个时钟上升沿的时候，X=0，所以我们希望触发器捕获X=0。因为X不能保持稳定的状态足够长的时间，所以X的实际值不可预测。这个电路违反了保持时间约束，在任何时钟频率下其动作都可能不正确。
例3.11 解决保持时间约束违反问题。Alyssa打算通过增加缓冲器降低最短路径速度以修复Ben的电路，如图3-44所示。缓冲器和其他的门有相同延迟。确定电路最大的时钟频率，是否会发生保持时间问题。
解：图3-45显示了信号变化的波形图。从A到Y的关键路径不受影响，因为它没有通过任何缓冲器。所以最大的时钟频率依然是4GHz。但是，最短路径被缓冲器的最小延迟变慢了。X在tccq+2tcd=30+2×25=80ps之前都保持不变。这是在保持时间60ps之后，所以电路运行正常。
这个例子用了一个不常见的长保持时间来说明保持时间问题。很多触发器被设计成thold＜ tccq来避免这类问题。但是，一些高性能的微处理器（包括奔腾4）在触发器中使用了称为脉冲锁存器（pulsed latch）的组件。脉冲触发器的行为类似于触发器，但是它的时钟到Q延迟很短，而保持时间很长。总之，增加缓冲器通常（但并不总是）能在不降低关键路径速度的同时解决保持时间问题。
3.5.3 时钟偏移
在之前的分析中，我们假设时钟总是在同一时刻到达各个寄存器。在现实中，每个寄存器的时钟到达时间总是有所不同的。这个时钟沿到达时间的变化称为时钟偏移（clock skew）。例如，从时钟源到不同的寄存器之间的连线长度不同，导致了延迟的微小差异，如图3-46所示。噪声同样也可以导致不同的延迟。3.2.5节中介绍的时钟门控也可以进一步延迟时钟。如果一些时钟经过门控，而另外一些没有，则门控时钟和非门控时钟之间就一定会存在偏移。图3-46中的CLK2相对于CLK1要早，因为在两个寄存器之间的时钟线上有一条通路。如果时钟的布线不同，CLK1也可能会早一些。在进行时序分析时，需要考虑最坏的情况，以保证电路在所有的环境下都可以工作。
图3-47是在图3-38上增加了时钟偏移后的时序分析。粗时钟线表示时钟信号到达每个寄存器的最迟时间，虚线表示时钟可能提前tskew时间到达。
首先考虑在图3-48中的建立时间约束。在最坏的情况下，R1收到最迟偏移时钟，R2收到最早偏移时钟，而留下一点时间在两个寄存器之间进行数据传输。
数据通过寄存器和组合逻辑传输，并必须在R2采样之前建立。所以可以得到：
下一步考虑图3-49的保持时间约束。在最坏的情况下，R1接收最早偏移时钟CLK1，R2接收最迟偏移时钟CLK2。数据通过寄存器和组合逻辑传输，且必须在经过慢时钟的保持时间后到达，所以可以得到：
总之，时钟偏移显著增加了建立时间和保持时间。它将加到时序总开销上，减少了组合逻辑的有效工作时间。它也增加了通过组合逻辑所需的最小延迟。如果thold=0，且tskew＞tccq，一对背靠背的触发器将不满足式（3.22）。为了防止严重的保持时间错误，设计者绝对不能允许太多的时钟偏移。当时钟偏移存在时，触发器有时被故意地设计成特别慢（即增大tccq），以防止保持时间问题。
例3.12 时钟偏移的时序分析。重新考虑例3.10，假定系统的时钟偏移为50ps。
解：关键路径保持一样，但因时钟偏移关系，建立时间显著增加了。所以，最小的周期时间是
最大的时钟频率是fc=1/Tc=3.33GHz。
最短的路径也保持不变，即55ps。因为时钟偏移，保持时间显著增加，60+50=110ps，它比55ps要大很多。所以，电路将违反保持时间约束，在任何频率都会发生故障。即使没有时钟偏移时，电路也违反保持时间约束。系统的时钟偏移会造成更严重的违反情况。
例3.13 调整电路以满足保持时间约束。重新考虑例3.11，假设系统的时钟偏移是50ps。
解：关键路径不受影响，所以最大的时钟频率仍然为3.33GHz。
最短路径增加到80ps。这仍然比thold+tskew的110ps小，所以电路仍然违反保持时间约束。
为了修复这个问题，需要插入更多的缓冲器。在关键路径上同样也需要增加缓冲器，从而降低时钟频率。作为选择，也可以选用其他保持时间更短的触发器。
3.5.4 亚稳态
如前所示，当输入来自外界时，到达时间可能在孔径时间内，而不能保证时序电路的输入总是稳定的。考虑一个按键连接到触发器的输入端，如图3-50所示。按键没有被按下时，D=0；按下时，D=1。一只猴子相对于时钟的上升沿随机地按按键。我们希望知道时钟上升沿后输出Q的值：
- 情况Ⅰ，当按键在CLK之前按下，Q=1。
- 情况Ⅱ，按键在CLK之后很久都没有按下，Q=0。
- 情况Ⅲ，当按键在CLK之前的tsetup和CLK之后的thold之间的某个时间按下，输入破坏了动态规则，输出将无法确定。
1.亚稳定状态
当触发器对在孔径时间内发生变化的输入进行采样时，输出Q可能随时地取在禁区内的0和VDD之间的一个电压。这被称为亚稳定状态。触发器最终将确定输出到0或者1的稳定状态。但是，到达稳定状态的分辨时间（resolution time）是*的。
触发器的亚稳定状态类似于一个放在两个山谷间山峰顶点的球，如图3-51所示。处于山谷中的球为稳定状态，因为它们在不受干扰的情况下可以一直保持它的状态。在山峰顶上的球为亚稳定状态，因为如果保持绝对的平衡，这个球将保持在山顶。但是没有绝对的平衡，球将最终滚落到一边或者另一边。发生这种改变所需时间取决于球在最初位置上的平衡程度。每一个双稳态的设备在两个稳定状态之间都存在一个亚稳定状态。
2.分辨时间
如果触发器在时钟周期内的任意时间发生改变，分辨时间tres为达到一个稳定状态所需要的时间，这也是一个随机的变量。如果输入在孔径时间外改变，则tres=tpcq。但是如果输入在孔径时间内发生改变，tres一定比较长。理论和实践上的分析（见3.5.6节）指出：分辨时间tres超过任意时间t的概率按t的指数方式减少：
其中，Tc为时钟周期，T0和由触发器的属性决定。此式仅在t比tpcq长的条件下有效。
直观地，T0/Tc表示了输入在最坏时间（即孔径时间）内发生改变的概率。这个概率随周期Tc而减少。是一个时间常量，说明了触发器从亚稳态移开的速度，这与触发器中耦合门的延迟有关。
总之，如果触发器等双稳态设备的输入在孔径时间内发生改变，输出在稳定到0或者1之前是一个亚稳态的值。到达稳定状态的时间是*的，因为对于任何的有限时间t，触发器仍处于亚稳态的概率都不会是0。但这个概率将随着t的增加按指数方式减少。所以，如果等待超过tpcq的足够长时间，触发器到达一个有效逻辑电平的概率将很高。
3.5.5 同步器
对于数字系统而言，来自真实世界的异步输入是不可能避免的。比如，人的输入就是异步的。如果处理不当，系统中这些异步输入将导致亚稳态电压，从而产生很难发现和改正的不稳定系统错误。数字系统设计师的目标是：对于给定的异步输入，确保遇到的亚稳态电压的概率足够小。“足够”取决于应用环境。对于数字移动电话，在10年间有一次失效是可以接受的。因为即使它锁定了，用户也可以关机，然后再打过去。对于医疗设备，在预期的宇宙生命（1010年）中才产生一次失效将是一个更好的指标。为了确保产生正确的逻辑电平，所有的异步输入必须经过同步器（synchronizer）。
图3-52给出了一个同步器。它接收异步输入信号D和时钟CLK。在有限的时间内，它产生一个输出Q；输出为一个有效逻辑电压的概率很高。如果在孔径时间内D是稳定的，Q将取和D一样的值。如果在孔径时间内D发生变化，Q可能取HIGH或者LOW。但是一定不会是亚稳定状态。
图3-53显示了用2个触发器建立同步器的简单方法。F1在CLK的上升沿对D进行采样。如果D在这个时刻发生改变，则输出D2将出现暂时的亚稳态。如果时钟周期足够长，D2在周期结束前成为一个有效逻辑电平的概率很高。F2接着对D2进行采样，它现在是稳定的，将产生一个好的输出Q。
如果同步器的输出Q为亚稳态，那么这个同步器将失效。产生这种情况的原因是D2在F2上所必须的建立时间之前没有变成有效的电平，即如果tres＞Tc-tsetup，由式（3.24），在随机时间内输出信号改变而导致同步器错误的失效概率是：
失效概率P(failure)是信号D改变时，输出Q为亚稳态的概率。如果D每秒钟改变一次，每秒钟失效的概率就是P(failure)。如果D每秒钟改变N次，则失效的概率就需要乘以N倍：
系统的可靠性通常由失效平均间隔时间（Mean time between failures，MTBF）衡量。根据定义可以看出，MTBF是系统失效之间的平均时间。它是系统失效概率的倒数：
式（3.27）指出MTBF按同步器延迟Tc的指数方式增加。对于多数系统，同步器等待一个时钟周期将提供给一个安全的MTBF。但在高速的系统中则不行，必须等待更多的周期。
例3.14 有限状态机输入的同步器。3.4.1节中的有限状态机交通灯控制器接收交通传感器的异步输入。假定同步器用于保证控制器得到稳定的输入信号。交通到达的次数是平均每秒钟0.2次。同步器中触发器的特性为：=200ps，T0=150ps，tsetup=500ps。这个同步器的时钟周期是多少才能使MTBF超过1年？
解：1年=×107秒。解等式（3.27）
这个等式没有封闭解，但是，通过猜想和检验很容易解答。在数据表中，尝试将一些Tc的值带入计算MTBF，直到Tc的值可以保证MTBF为1年：Tc=3.036ns。
3.5.6 分辨时间的推导
式（3.24）可以使用电路理论、差分方程和概率论等基础知识得到。如果读者对推导不感兴趣或对相关数学知识不了解，可以跳过此节。
一个触发器在给定时间t后处于亚稳态，即如果触发器对正在变化的输入（将产生亚稳态条件）进行采样，而且输出在时钟沿后的这段时间内没有达到稳定的电平。这个过程可以用数学方式描述为：
我们认为每个概率项都是独立的。异步输入信号在0和1之间切换，tswitch如图3-54所示。在时钟沿附近的孔径时间内输入发生改变的概率是
如果触发器以P（采样了正在改变的输入）的概率进入了亚稳态，从亚稳态到成为有效电平的时间取决于电路的内部工作原理。这个分辨时间确定了P（没有达到一个稳定的电平），即触发器在时间t之后没有成为有效电平的概率。本节后续部分将分析一个简单的双稳态装置模型来估计这个概率。
一个双稳态装置以正反馈方式存储。图3-55a给出了用一对反相器实现的正反馈；这个电路的行为代表了典型的双稳态元件。一对反相器的行为就像缓冲器。让我们以对称直流转换特征为之建模，如图3-55b所示，其斜率为G。缓冲器只能提供有限的输出电流；可以将其建模为一个输出电阻R。所有真实的电路都有必须被充电的电容C。通过电阻对电容充电形成RC延迟，阻止了缓冲器在瞬间进行切换。所以，完整的电路模型如图3-55c所示，其中vout(t)为双稳态装置传输状态的电压。
电路的亚稳态点是vout(t)=vin(t)=VDD/2；如果电路刚好在这一点开始工作，它将在没有噪声的情况下永远保持在这里。因为电压是连续变量，电路刚好在亚稳态这一点开始工作的机会非常小。但是，电路在0时刻可能处于亚稳态附近的开始位置，vout(0)=VDD/2+V，其中V是小偏移量。在这种情况下，如果V＞0，正反馈最终将驱动vout(t)到VDD，如果V＜0，将驱动vout(t)到0。到达VDD或0所需要的时间正是双稳态装置的分辨时间。
直流转换特征是非线性的，但它在我们感兴趣的亚稳态点附近表现出线性。特别是，如果vin(t)=VDD/2+V/G，当V很小时，则vout(t)=VDD/2+V。通过电阻的电流是i(t)=(vout(t)-vin(t)/R。电容充电的速率是dvin(t)/dt=i(t)/C。将这些综合到一起，我们可以得出输出电压的产生方程。
这是一个一阶线性微分方程。根据它们的初值vout(0)=VDD/2+V求解。
图3-56描绘了在不同给定起始点上电压vout(t)的轨迹。vout(t)按照指数方式远离亚稳态点VDD/2，直到它饱和为VDD或者0。输出电压最终将成为1或者0。所花费的时间取决于从亚稳态点VDD/2到最初电压的偏移量（V）。
解式（3.32），以求vout(tres)=VDD或者0时的分辨时间tres：
总之，如果双稳态装置有很大的电阻和电容将导致它的输出改变很慢，分辨时间会增加。如果双稳态装置有很大的增益G，分辨时间会缩短。当电路在紧挨着亚稳态的点开始（V→0），分辨时间也会成对数方式增加。
定义 。解式（3.34），求给定分辨时间tres下的∆V，以确定最初偏移量Vres：
假设双稳态装置在输入变化时进行采样。其输入电压vin(0)为在电压VDD和0之间。在时间tres之后输出没有成为合法值的概率取决于最初偏移量足够小的概率。尤其在vout上的最初偏移量小于Vres，所以在vin上的最初偏移量必须小于Vres/G。双稳态装置对输入进行采样时得到足够小的最初偏移量的概率为：
综上所述，分辨时间超过时间t的概率，下式给出
观察式（3.37），并按式（3.24）形式重写，T0=(tswitch+tsetup+thold)/G，=RC/(G-1)。总之，我们已经得出式（3.24），并证明T0和取决于双稳态装置的物理属性。
3.6 并行
系统的速度可以用延迟和通过系统的任务吞吐量来衡量。任务（token）定义为经过处理后能产生一组输出的一组输入。可以采用可视化的方法理解，即在电路图中输入这些任务，并通过电路得到结果。延迟（latency）是从开始到结束需要的时间。吞吐量（throughput）是系统单位时间内产生任务的数量。
例3.15 饼干的延迟和吞吐量。Ben决定举行一个牛奶和饼干晚宴来庆祝交通灯控制器成功安装。做好饼干并放入盘中需要花费5分钟。将饼干放入烤箱烤好需要花费15分钟。烤好一次饼干后，他开始做下一盘饼干。Ben做好一盘饼干的吞吐量和延迟是多少？
解：在这个例子中，一盘饼干是一个任务。每盘的延迟是1/3小时，吞吐量是3盘/小时。
读者可能会想到在同一时间内处理多个任务可以提高吞吐量。并行性（parallelism）有两种形式：空间和时间。空间并行（spatial parallelism）是提供多个相同的硬件，这样多个任务就可以在同一时间一起处理。时间并行（temporal parallelism）是一个任务被分成多个阶段，类似于流水装配线。多个任务可以分布到所有的阶段。虽然每一个任务必须通过全部的阶段，但在给定的时间内每段都有一个不同的任务，从而使得多个任务可以重叠起来。时间并行通常称为流水线（pipelining）。空间并行有时也称为并行，但是我们避免这种容易产生误解的命名约定。
例3.16 饼干并行。Ben有上百个朋友来参加他的晚宴，所以他要加快做饼干的速度。他考虑使用空间并行和时间并行。
空间并行：Ben请Alyssa提供帮助。Alyssa有她自己的饼干盘和烤箱。
时间并行：Ben拿来第二个饼干盘。他一旦把饼干盘放入烤箱，就开始卷饼干并放入另外的一个盘子里，而不是等着第一盘烤好。
使用空间并行和时间并行后的吞吐量和延迟是多少？两种方法同时使用后的吞吐量和延迟是多少？
解：延迟是完成一个任务从开始到结束所需要的时间。在所有情况下，延迟都是1/3小时。如果Ben开始时没有饼干，延迟是他完成第一盘饼干所需要的时间。
吞吐量是每小时烤好的饼干盘数量。使用空间并行的方法，Ben和Alyssa每20分钟完成一盘饼干。所以吞吐量是以前的2倍，即6盘/小时。使用时间并行的方法，Ben每15分钟就把一个新盘放入烤箱，吞吐量是4盘/小时。如图3-57所示。
如果Ben和Alyssa同时使用这两种并行技术，吞吐量是8盘/小时。
考虑一个延迟为L的任务。没有并行的系统中，吞吐量为1/L。在空间并行系统中有N个相同的硬件，则吞吐量为N/L。在时间并行系统中，任务可以理想地分成等长的N个步骤或阶段。在这种情况下，吞吐量也是N/L，且只需要一套硬件。但是饼干的例子显示：将任务分解为N个等长的阶段是不切实际的。如果最长的延迟为L1，则流水线的吞吐量为1/L1。
流水线（时间并行）特别有吸引力，因为它没有增加硬件就可以加速电路运行。方法是将寄存器放置在组合逻辑块之间将逻辑分成较短的阶段，使之可以以较快的时钟频率运行。寄存器用于防止流水线中某一级的任务赶上和破坏下一级的任务。
图3-58给出了一个没有流水线的电路的例子。它在寄存器间包含4个逻辑块。关键路径通过第2、3、4块。假设寄存器时钟到Q的传输延迟为0.3ns，建立时间为0.2ns。则周期是Tc=0.3+3+2+4+0.2=9.5ns。电路的延迟为9.5ns，吞吐量为1/9.5ns=105MHz。
图3-59给出了一个相同功能的电路，但在第3块和第4块之间加入一个寄存器，从而将电路分割成两阶段流水线。第一个阶段的最小延迟周期是0.3+3+2+0.2=5.5ns。第二阶段的最小周期是0.3+4+0.2=4.5ns。时钟必须足够慢，使得所有的阶段都能正确工作。所以，Tc=5.5ns。延迟为2个时钟周期，即11ns。吞吐量是1/5.5ns=182MHz。这个例子显示在真实的电路中，两级流水线通常可以得到几乎是双倍的吞吐量和稍微增加的延迟。相比之下，理想状态流水线的吞吐量可以提高一倍，而延迟不变。产生差别的原因在于电路不可能分割成完全相等的两半，而且寄存器引入了额外的时序开销。
图3-60给出来分割成3级流水线的相同电路。注意：需要2个以上的寄存器来存储在第一流水线结束后块1和块2的结果。周期被第三阶段限制为4.5ns。延迟为3个周期，即13.5ns。吞吐量为1/4.5ns=222MHz。再增加一个流水阶段提高了吞吐量，也增加了一些延迟。
虽然这些技术都很强大，但它们并不能运用到所有的情况。并行的克星是依赖关系（dependency）。如果当前的任务依赖于前一个任务的结果，而不是在当前任务中的前一步结果，此时只有前一个任务完成后，后一个任务才能开始。例如，Ben想在开始准备第二盘之前检查第一盘饼干的味道是否好。这就是一个阻止流水线或并行操作的依赖关系。并行性是设计高性能微处理器的重要技术。第7章中将进一步讨论流水线，并用例子说明如何处理依赖关系。
3.7 总结
本章介绍了时序逻辑电路的分析和设计。和输出只取决于当前输入的组合逻辑电路相比，时序逻辑电路的输出取决于当前和先前的输入。换句话说，时序逻辑电路记忆了先前的输入信息。这种记忆称为逻辑的状态。
时序逻辑电路很难分析，并容易产生设计错误，所以我们只关心小部分成熟的模块。需要掌握的最重要元件是触发器，它的输入为时钟和D，产生一个输出Q。触发器在时钟上升沿将D值复制到Q，其他时候保持原来的状态Q不变。共享同一个时钟的触发器称为寄存器。触发器还可以接收复位和使能信号。
虽然有很多种形式的时序逻辑，我们只考虑最容易设计的同步时序逻辑电路。同步时序逻辑电路包含了由时钟驱动寄存器隔开的组合逻辑块。电路的状态存储在寄存器中，仅在时钟沿到达时进行更新。
有限状态机是设计时序电路强有力的技术。为设计一个有限状态机，首先要识别状态机的输入和输出，画出状态转换图，说明状态和两个状态之间的转换。为状态选择一个编码，然后将状态转换图重写为状态转换表和输出表，指出给定当前状态和输入的下一个状态和输出。通过这些表，设计组合逻辑来计算下一个状态和输出，画出电路图。
同步时序逻辑电路的时序说明包括时钟到Q的传输延迟tpcq和最小延迟tccq，建立时间tsetup和保持时间thold。为了操作正确，在孔径时间内它们的输入必须稳定。建立时间在时钟上升沿之前开始，保持时间在时钟上升沿之后结束。系统的最小延迟周期Tc，等于通过组合逻辑块的传输延迟tpd，加上寄存器的tpcq+tsetup。为了操作正确，通过寄存器和组合逻辑的最小延迟必须大于thold。与常见的误解相反，保持时间不影响时间周期。
整个系统的性能可以用延迟和吞吐量来衡量。延迟是从任务开始到结束需要的时间。吞吐量是系统单位时间内处理任务的数量。并行可以提高系统的吞吐量。
习题
3.1 输入波形如图3-61所示，画出SR锁存器的输出Q。
3.2 输入波形如图3-62所示，画出SR锁存器的输出Q。
3.3 输入波形如图3-63所示，画出D锁存器的输出Q。
3.4 输入波形如图3-64所示，画出D锁存器的输出Q。
3.5 输入波形如图3-63所示，画出D触发器的输出Q。
3.6 输入波形如图3-64所示，画出D触发器的输出Q。
3.7 图3-65中的电路是组合逻辑电路还是时序逻辑电路？说明输入和输出之间的关系。如何称呼这个电路？
3.8 图3-66中的电路是组合逻辑电路还是时序逻辑电路？说明输入和输出之间的关系。如何称呼这个电路？
3.9 T触发器（toggle flip-flop）有一个输入CLK，一个输出Q。在每一个CLK上升沿，Q的值就变成它的前一个值取反。使用D触发器和反相器画出T触发器的原理图。
3.10 JK触发器（JK flip-flop）接收一个时钟，两个输入J和K。时钟上升沿时，输出值Q被更新。如果J、K同时为0，Q将保持原来的值不变。如果只有J=1，则Q=1。如果只有K=1，则Q=0。如果J=K=1，Q的值就切换成它的前一个值的取反。
（a）使用D触发器和一些组合逻辑构造JK触发器。
（b）使用JK触发器和一些组合逻辑构造D触发器。
（c）使用JK触发器构造T触发器（习题3.9）。
3.11 图3-67中的电路称为Muller C元件。请简要说明输入和输出之间的关系。
3.12 使用逻辑门设计一个带异步复位功能的D锁存器。
3.13 使用逻辑门设计一个带异步复位功能的D触发器。
3.14 使用逻辑门设计一个带同步置位功能的D触发器。
3.15 使用逻辑门设计一个带异步置位功能的D触发器。
3.16 假设由N个反相器以环连接而构成的一个环形振荡器。每一个反相器的最小延迟为tcd，最大延迟为tpd。如果N是奇数，确定这个振荡器的频率范围。
3.17 习题3.16中为什么N必须为奇数？
3.18 图3-68中的哪些电路是同步时序电路？为什么？
3.19 为一栋25层的建筑物设计一个电梯控制器。这个控制器有两个输入：UP和DOWN，以及指明当前电梯所在楼层的输出。没有13这个楼层。控制器的状态最少需要几位？
3.20 设计一个有限状态机来跟踪数字设计实验室里4个学生的心情。学生的心情有HAPPY（开心，电路正常工作）、SAD（忧愁，电路烧坏）、BUSY（忙碌，正在设计电路）、CLUELESS（愚笨，被电路所困扰）、ASLEEP（睡觉，趴在电路板上睡着）。这个有限状态机需要多少个状态？至少需要多少位来代表这些状态？
3.21 习题3.20中的有限状态机可以分解成多少个简单的状态机？每一个简单状态机需要多少个状态？分解后的设计总共需要多少最少位数？
3.22 说明图3-69状态机的功能。使用二进制编码，完成这个有限状态机的状态转换表和输出表。写出下一个状态和输出的布尔等式，并且画出这个有限状态机的原理图。
3.23 说明图3-70状态机的功能。使用二进制编码，完成这个状态机的状态转换表和输出表。写出下一个状态和输出的布尔等式，并且画出这个状态机的原理图。
3.24 在Academic大道和Bravado大道的十字路口上，交通事故还是时有发生。当灯B变成绿色的时候，足球队冲进十字路口。在灯A变成红色之前，他们和蹒跚在十字路口缺乏睡眠的CS硕士撞到了一起。扩展3.4.1节的交通灯控制器，在灯变成绿色之前，让两个灯保持红色5秒钟。画出改进的Moore型状态机状态转换图、状态编码、状态转换表、输出表，写出下一个状态和输出的布尔等式，并且画出这个有限状态机的原理图。
3.25 3.4.3节中Alyssa的蜗牛有一个女儿，它有一个Mealy型状态机的有限状态机大脑。当蜗牛女儿爬过1101或者1110时就会微笑。为这只快乐的蜗牛用尽可能少的状态画出状态转换图。选择状态的编码，使用你的编码画出组合的状态转换和输出表。写出下一个状态和输出等式，画出有限状态机原理图。
3.26 你将参与为部门休息室设计一个苏打汽水自动售货机。IEEE的学生会将给予不菲的奖学金，价格仅为25美分。机器接收5美分、一角硬币和二角五分硬币。当投入足够的硬币，苏打汽水自动售货机就会分配汽水和找零钱。为这个苏打汽水自动售货机设计一个有限状态机控制器。有限状态机的输入是Nickel（5美分）、Dime（一角）和Quarter（两角五分），表示硬币已经投入机器。假设在一个周期投一个硬币。输出是Dispense ReturnNickel、ReturnDime、ReturnTwoDime。当有限状态机到达25美分时，它将给出Dispense和相应的Return输出，需要传递合适的找零。接着它将准备开始接收硬币以售卖下一瓶苏打汽水。
3.27 格雷码有一个很有用的特点，在连续的数字中只有一个信号位位置不同。表3-23列出了3位的格雷码表示0～7的数字。设计一个没有输入，有3位输出的8取模格雷码计数器有限状态机。（N取模计数器指从0到N-1计数，并不断重复。例如，手表的分和秒是以60为模的计数器，从0～59计数。）当重启的时候，输出为000。在每一个时钟沿，输出进入下一个格雷码。当到达100后，它将从000开始重复。
3.28 扩展习题3.27中的8取模格雷码计数器，增加UP输入变成UP/DOWN计数器。当UP=1时，计数器进入下一个格雷码。当UP=0时，计数器退回到上一个格雷码。
3.29 设计一个有限状态机，它有2个输入A和B，产生1个输出Z。在周期n内的输出Zn是输入An 和前一个输入An-1的“与”或者“或”，其运算取决于另外一个输入Bn：
（a）根据图3-71给出的输入画出Z的波形图。
（b）它是Moore型状态机还是Mealy型状态机？
（c）设计这个有限状态机。画出状态转换图和编码状态转换表、下一个状态和输出等式，以及原理图。
3.30 设计一个有限状态机，它有1个输入A，2个输出X和Y。如果A有3个周期为1，则X为1（没有必要连续）。如果A在至少2个连续的周期内为1，则Y为1。画出你的状态转换图和编码状态转换表、下一个状态和输出等式，以及原理图。
3.31 分析如图3-72所示的有限状态机。写出状态转换和输出表，画出状态转换图。简短地介绍有限状态机的功能。
3.32 重复习题3.31，有限状态机如图3-73所示。注意寄存器的r和s输入分别表明复位和设置。
3.33 Ben设计了一个如图3-74的电路来计算4个寄存器输入的异或函数。每一个2输入异或门的传输延迟为100ps，最小延迟为55ps。每一个触发器的建立时间为60ps，保持时间为20ps，时钟到Q的最大延迟是70ps，时钟到Q的最小延迟是50ps。
（a）如果不存在时钟偏移，电路的最大运行频率是多少？
（b）如果电路必须工作在2GHz下，电路能够承受多大的时钟偏移？
（c）在电路满足保持时间约束的条件下，电路能够承受多大的时钟偏移？
（d）Alyssa说她能够重新设计在输入/输出寄存器间的组合逻辑，使其他更快，且能够承受更大的时钟偏移。她的改进电路也使用3个2输入的异或门，但是它们的排列不同。她的电路是什么？如果不存在时钟偏移，它的最大频率是多少？在满足保持时间约束条件下，电路能够承受多大的时钟偏移？
3.34 为RePentium处理器设计一个二位加法器。这个加法器由两个全加器构成，第一个加法器的进位输出连接到第二个加法器的进位输入，如图3-75所示。加法器有输入和输出寄存器，必须在一个周期内完成加法运算。每一个全加器中，从Cin到Cout或者到Sum(S)的传输延迟为20ps，从A或者B到Cout的传输延迟为25ps，从A或者B到S传输延迟为30ps。加法器中，从Cin到其他输出的最小延迟为15ps，从A或者B到其他输出的最小延迟为22ps。每一个触发器的建立时间是30ps，保持时间是10ps，时钟到Q的传输延迟是35ps，时钟到Q的最小延迟是21ps。
（a）如果不存在时钟偏移，电路的最大运行频率是多少？
（b）如果电路必须工作在8GHz下，电路能够承受多大的时钟偏移？
（c）在满足保持时间约束的条件下，电路能够承受多大的时钟偏移？
3.35 现场可编程门阵列（FPGA）使用可配置的逻辑块（CLB）而不是逻辑门来实现组合逻辑。Xilinx公司的Spartan 3 FPGA的每一个CLB的传输延迟和最小延迟分别是0.61ns和0.30ns。它包含的触发器的传输延迟和最小延迟分别是0.72ns和0.50ns。建立时间和保持时间分别是0.53ns和0ns。
（a）如果你设计一个系统需要运行在40MHz，在2个触发器之间需要使用多少个连续的CLB？假设在CLB之间没有时钟偏移，没有连线延迟。
（b）假设在触发器之间的所有路径上至少通过一个CLB。FPGA有多少时钟偏移而不破坏保持时间约束。
3.36 一对触发器建立的同步器，tsetup=50ps，T0=20ps，=30ps。它对一个异步输入进行采样，每秒钟改变108次。为了达到在失效之间的间隔时间是（MTBF）是100年，这个同步器的最小时钟周期是多少？
3.37 设计一个接收异步输入的同步器，其MTBF为50年。系统运行主频为1GHz，采用T0=110ps，=100ps，tsetup=70ps的触发器进行采样。同步器每秒收到0.5次的异步输入（即每2秒钟1次）。满足这个MTBF的失效概率是多少？在读出采样的输入信号之前你将等待多少周期以满足这个失效概率？
3.38 当你正在走廊下走路时遇见你的实验室伙伴正在朝另一个方向走。你们两个先朝一个方向走一步，仍然在彼此的道路上。然后你们两个朝另一个方向走一步，仍然在彼此的道路上。然后你们两个都等一下，希望对方走到一边。你可以用亚稳态的观点为这种情景建模，并将相同的理论应用到同步器和触发器中去。假设你为你和你的实验室伙伴建立了一个数学模型。你们在亚稳态状态中相遇。在时间t秒后，你保持这种状态的概率是，表示你的反应速度；今天你的大脑因为缺乏睡眠很模糊，=20秒。
（a）需要多长时间，在有99%的可能性下你将从亚稳态中出来（即指出如何穿过对方）？
（b）你不仅没有休息而且很饿。实际上，如果在3分钟内没到咖啡屋，你将饿死。你的实验室伙伴不得不把你推进太平间的概率是多少？
3.39 你使用T0=20ps，=30ps的触发器建立了一个同步器。你的老板需要将MTBF增加10倍，你需要将时钟周期增加多少？
3.40 Ben发明了一个改进的同步器，如图3-76所示。他宣布在一个周期内消除亚稳态。他解释在盒子M中的电路是一个逻辑亚稳态的检测器。如果输入电压在禁区VIL和VIH之间，产生一个为高电平的输出。通过检测，亚稳态检测器可以确定第一个触发器是否产生了一个亚稳态的输出D2。如果是，则它异步复位触发器使D2=0。第二个触发器对D2进行采样，在Q上总是可以产生一个有效的逻辑电平。Alyssa告诉Ben，电路中存在一个错误，因为消除亚稳态就像制造永动机一样不可能。谁是正确的？解释并说明Ben或Alyssa为什么错误。
面试问题
3.1 画一个状态机用于检测接收到的序列01010。
3.2 设计一个串行（每次一位）二进制补码有限状态机。它有两个输入Start和A，一个输出Q。输入A是一个从最低位开始的任意长度的二进制数。在同一周期内，Q输出相同的位。在最小的有效位输入之前，Start保持一个周期有效以初始化有限状态机。
3.3 锁存器和触发器有什么不同？它们各自在哪种环境中更加可取？
3.4 设计一个5位计数器有限状态机。
3.5 设计一个边沿检测电路。在输入从0转变成1后，在一个周期内输出为高电平。
3.6 描述流水线的概念，为什么使用流水线？
3.7 描述触发器中负的保持时间是什么意思？
3.8 如图3-77所示，给出了信号A的波形，设计一个电路，使它产生信号B。
3.9 考虑在两个寄存器之间的组合逻辑块。解释时序约束。如果你在接收器方（第二个触发器）的时钟输入加入一个缓冲器，建立时间约束是变好了还是变坏了？