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。以下为一组样例：

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 来绘制：

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

---

延迟

【施工中】

---

回到目录