CS110 计算机体系结构 7 时序电路与有限状态机

上一章中我们了解了组合电路相关内容，但要组合成一台计算机，只有组合电路是不够的：因为组合电路除去机械延迟以外，几乎可以“瞬间”完成运算，但这个“运算”的结果是表示为高电平/低电平的，而无法有效地把这种状态保存下来并参与后面的运算。正因如此，我们需要一种能够保存信息的元器件——寄存器。我们把这种输出不仅取决于当前输入，还取决于电路过去状态的数字逻辑电路叫作时序电路（或同步电路）。

DFF 与寄存器

寄存器由多个 D-触发器 D flip-flops，简称 DFF 组成。一个 DFF 可以看成一个一位的寄存器。

一个 DFF 有一个 1 位输入接口、一个 1 位输出接口、一个重置 rst 接口以及一个时钟 clk 接口，因此只能暂存 1 位 0/1 数据。如上图，在时序电路中，clock 是一个近似方波的信号，在一个时钟周期 period 内完成一次高电平 - 低电平翻转。**这种从低电平到高电平的过程被称为上升沿，反之则称为下降沿。**对于 DFF 而言，当时钟信号处于上升沿（也可以是下降沿，但是本课程中统一为上升沿）时，DFF 会从输入接口读入值，并存储在 DFF 中，极短的一段时间后，DFF 的输出接口会更新为新值。另外，当重置 rst 接口输入为 1 时，DFF 将保持自己的值为 0。寄存器就是把多个共享 rst 接口、clk 接口的 DFF 组合起来，可以认为是一个输入、输出都有多位的 DFF。

上图是一个寄存器的输入输出示例。在上图的示例中，在第一个时钟上升沿（左侧的蓝色虚线处）时，寄存器读入输入的值 8，并在短暂延迟后把输出接口的值更新为 8；在第二个时钟上升沿时，寄存器读入更新后的输入值 16，并在短暂延迟后把输出接口的值更新为 16，以此类推。

有限状态机 Finite State Machine, FSM

有限状态机是一种计算用的数学模型，简单来说就是一些圈（表示状态）和一些箭头（表示一个状态转移到另一个状态）。显然，在任何时间，状态机只能处于有限种状态中的一种，在接收到输入后会改变状态。在本课程中，我们将状态机分为两种：摩尔状态机 Moore Machine 和梅利状态机 Mealy Machine，接下来我们分别说明。

Moore Machine

Moore 状态机的特征是：输出仅由当前状态决定，与当前输入无关。

想象一个自动门，状态只有[开]和[关]两种。当检测到有人时，如果当前自动门处于[关]的状态，它会试图转移到[开]的状态，但是这个过程不是瞬间完成的——如果此时你试图通过这扇门，你必须等到它状态切换到[开]后才能通过。这扇门的状态就可以用以下的 Moore 状态机来描述：

[开]的门能够通过，[关]的门无法通过，这与有没有检测到人无关——这就是 Moore 状态机。

讲完了 Moore 状态机的原理，我们应该如何用时序电路实现一个 Moore 状态机呢？这里有模板可以直接抄：

Mealy Machine

Mealy 状态机的特征是：输出由当前状态和当前输入决定。

想象一个自动饮料机，会售卖可乐和雪碧两种饮料。当你投入硬币后，如果你选择可乐，它就会吐出一听可乐；如果你选择雪碧，它就会吐出一罐雪碧，然后进入[售卖完成]状态；当它发现你已经取走了饮料，它就会自动进入[初始]状态。这个自动饮料机就可以用以下的 Mealy 状态机来描述：

同样是从[初始]状态转移到[售卖完成]状态，不同的输入（选择可乐还是雪碧）会产生不同的输出（吐出可乐还是雪碧），输出与当前状态和输入均有关（还没取走上一瓶或没投钱就不会吐出饮料）——这就是 Mealy 状态机。

和 Moore 状态机类似，用电路实现 Mealy 状态机时，只是比 Moore 状态机多连接一根线：

设计一个时序电路

以上说了那么多，我们动手来设计一个时序电路来解决一个问题吧。

在一串二进制输入中，不重叠地检测子串 010，当检测到后在下一位输出 1，否则输出 0。以下为一组样例：

1 2	Input: 0 1 0 0 1 0 1 0 1 1 0 Output: 0 0 0 1 0 0 1 0 0 0 0

要解决这个问题，我们先根据题目的逻辑画出状态机。显然这里我们应该选择 Moore 状态机，因为在检测到目标子串后在下一位才响应，说明输出仅取决于当前状态。

接下来，我们给上图中的每个状态进行编码，上图中展示了一种编码方式：把“什么也没有检测到”编码为 00，把“检测到第一个 0”编码为 01，把“检测到一组 01”编码为 10，把“成功检测到 010”编码为 10。如果你用其它的编码方式，当然也是可以的。

在编码完成后，我们把这个状态机转换为一张真值表：其中 S[1]S[0] 表示状态机的一个状态的两位编码，input 表示当前输入，output 表示当前状态对应的输出。这样，你可以得到如下的真值表：

下一步，观察真值表，把这里前三列看作输入，后三列看作输出，通过上一章提到的“最小项之和”把真值表提取为布尔逻辑运算，然后化简为最简形式：

有了这个化简后的表达式，我们就可以绘制电路图了。下图中为了展示方便，把一个两位寄存器拆成了两个 DFF 来绘制：

这样，我们就走完了一个时序电路的设计全过程。这个过程请读者自行多做练习，在考试中几乎必然出现。（请读者思考并练习：如果以上例子中改为重叠地检测，电路图会是什么样的？）

延迟

时序电路的心跳来源于一个固定频率工作的时钟，计算机的计算速度正比于时钟频率，所以时钟频率越大越好。然而，我们知道，电子元件多多少少有一些非理想效应，信号传输延迟就是其中之一。不同元件的延迟累积起来，如果超过了一个时钟周期，就会导致信号传递出现错误。要在避免这种错误的前提下设计尽可能大的时钟周期，我们需要能够计算一个电路的延迟。

在普通的组合电路中，不同的逻辑门各有各的延迟，而整个电路的延迟自然就是遵循“木桶效应”的取不同路径的最长延迟，这条最长延迟的路径被称为关键通路 critical path。

然而，在一个带 DFF 的时序电路中，如何定义一个 DFF 的延迟？首先，我们应该定义一个 DFF 本身处理信号的延迟：时钟到输出延迟：从时钟上升沿（的正中间）到 DFF 输出信号稳定所需要的时间（读者不必计较上升沿的宽度，在本课程中可以忽略这一小段时间）。然后，我们还需要定义一个 DFF 能接受信号的“准备时间”：建立时间 Setup Time：从输入信号稳定到上升沿（的正中间）的时间；当然，我们还需要定义信号在上升沿之后需要继续保持的时间：保持时间 Hold Time。下图比较清楚地展示了这三个概念：

从外部看，一个 DFF 真正产生的延迟，其实是 ——从前一步准备好需要输入的数据，到 DFF 自己的输出达到稳定的时间。从这个角度看，我们可以把这两个延迟加起来作为一个 DFF 的延迟。当然，时序电路常用于解决有限状态机的问题，而这样的时序电路都是环状的，一个最小时钟周期是从一个上升沿到下一个上升沿的最短时间，所以理解成这一周期 DFF 的加上组合电路的延迟再加上下一周期 DFF 的也是合理的理解，如下图：