Lecture 5

Abstract

我们用反馈构造锁存器和触发器，把它们扩展为寄存器与按地址读写的存储器，再以交通灯为例推导有限状态机的状态转移、编码和输出逻辑。

我们先把上一次建立起来的几个概念连在一起。一个 CMOS 反相器由上方的 PMOS 和下方的 NMOS 组成：上拉网络把输出拉高，下拉网络把输出拉低。把这样的门组成更复杂的组合电路后，输入的变化需要经过一段时间才能传播到输出。传播延迟 $t_{pd}$ 给出最终值稳定的最晚界限，污染延迟 $t_{cd}$ 给出输出最早可能开始变化的界限。沿输入到输出的各条路径累计门延迟，最大的一条就是关键路径。我们今天要利用这些门构造存储单元，再把计算和存储组织成能够一步一步运行的系统。

1. 毛刺：暂时变化不一定是最终答案

在进入存储之前，我们再看一个现象，叫 glitch 或 hazard，通常称为毛刺或冒险。假设一个输出按逻辑功能应当保持高电平，但在电路转换过程中，它短暂地掉到低电平，过一会儿又恢复高电平。这段额外变化没有实现我们需要的新功能，却是真实发生的电平跳变。

为什么会这样？组合电路中，不同路径的传播时间可能不同。一些信号先到，另一些还没到，输出就可能经历短暂的中间状态。这也是我们不能在污染延迟一过就把输出当成正确答案的原因。最终的稳定值需要等到传播延迟给出的界限以后才有保证。

毛刺还有功耗代价。晶体管切换要给电容充放电，高到低、低到高都会涉及能量消耗；即便这些切换最终互相抵消，消耗过的能量也不会回来。我们可以记住，毛刺带来的额外开关活动可能占据不可忽略的功耗。课堂把这一点作为了解内容，不作为这次展开的考试重点。

课堂以约 20%—30% 说明毛刺额外功耗的量级；课件印刷第 10 页另列 20%—70%。

2. 二餐入口的计数器，为什么需要记忆

我们先考虑一个简单的设计问题：假设二餐只开放一个入口，我们想记录每天有多少顾客进入。门口的人每见一个顾客就按一下计数器，显示数便增加 1；另一个按钮可以把它复位到 0。输入是按钮或相应的进入信号，输出是目前的总人数。

如果只有组合逻辑，能不能实现这个计数器？加法器当然已经会做加法，但它只能根据眼前的输入给出输出。要得到新总数，我们需要两项输入：本次增加量，以及上一次的总数。后一项必须在两次事件之间保存下来。于是结构应该是：把当前保存的结果取出来，与新输入相加，再把新结果保存回去。

若用 $q$ 表示已保存的计数，$u$ 表示本次是否加一，那么这个过程可以写成

$$q_{\mathrm{next}}=q+u.$$

组合逻辑加上存储单元，就有了时序逻辑的基本结构。它的行为依赖当前输入，也依赖过去输入留下来的状态。

3. 交叉耦合反相器怎样保存一位

最简单的起点是两个反相器交叉耦合。我们把第一个反相器的输出接到第二个的输入，再把第二个的输出接回第一个的输入。用 $Q$ 和 $\overline Q$ 标记两个节点，它们在有效稳定状态下满足

$$Q=\neg\overline Q,\qquad \overline Q=\neg Q.$$

这对关系有两种数字稳定解：$Q=0,\overline Q=1$，或 $Q=1,\overline Q=0$。例如现在 $Q=1$，它经过一个反相器产生 0，再经过另一个反相器又得到 1，反馈回来的值与原值一致。$Q=0$ 时也一样能够自洽。因此，只要供电维持且电路已进入相应的稳定状态，这个闭环就能保持一个 bit。

但存下来还不等于能够方便地使用。我们可以从 $Q$ 引出所存的值，却还没有一个明确的数据输入端，让外部决定下一次要写入 0 还是 1。这就像有了一个能保持的容器，还要给它设计可控的写入方式。

我们也借此区分几类常见存储：处理器内部的寄存器速度快，但资源有限、成本较高；缓存通常使用 SRAM；主存通常使用 DRAM；关机后仍能保存数据的 SSD 又是另一类实现。我们这次沿着交叉耦合结构去理解寄存器的构造，SRAM 和 DRAM 的具体结构留待后面。

4. R-S 锁存器：能置位、能复位、能保持

我们把刚才的两个反相器扩展为交叉耦合的 NOR 门，每个门在反馈输入之外再加一个外部输入，就得到 R-S 锁存器。$R$ 是 reset，复位；$S$ 是 set，置位。按课件中 $Q$ 的标记，其关系可以写成

$$Q=\overline{R+\overline Q},\qquad \overline Q=\overline{S+Q}.$$

先问怎样让 $Q=1$。我们设 $S=1,R=0$。因为 $S=1$，产生 $\overline Q$ 的 NOR 门必定输出 0；这个 0 反馈给另一门，与 $R=0$ 一起经过 NOR，得到 $Q=1$。于是这不是凭空猜一个结果，而是输入先强制一边，再由反馈确定另一边。

如果要让 $Q=0$，利用电路的对称性，设 $R=1,S=0$。$R=1$ 直接把 $Q$ 压到 0，随后另一边得到 $\overline Q=1$。写完之后还需要保持：把 $R,S$ 都恢复为 0，两个 NOR 门便分别相当于对反馈信号取反，回到交叉耦合反相器的行为。无论之前存的是 0 还是 1，都可以继续保持。

最后一行为什么不允许？如果 $R=S=1$ 持续存在，两个 NOR 门都会被外部的 1 强制输出 0，因此 $Q$ 和标作 $\overline Q$ 的节点同时为 0，破坏了互补关系。两个输入再一起撤销时，最终恢复到哪一个有效存储状态也没有得到可靠规定。

纠错：口述称 $R=S=1$ 时会持续振荡；按两个 NOR 门的真值关系，输入持续为 1 时两输出均为 0，撤销输入后的存储结果不可靠。

现在我们确实有保持、写 1、写 0 三种功能了，但接口还不够方便。若问“我们要写什么”和“什么时候允许写”，R-S 输入把这两件事混合在了一起。我们更希望有一个单独的数据 $D$，$D=0$ 就表示要写 0，$D=1$ 就表示要写 1；另外再用一个控制信号决定这次到底写不写。

5. 另一种实现：NAND 型 R-S 锁存器

在改进接口以前，我们先看一个容易混淆的变体。同样可以用交叉耦合 NAND 门实现 R-S 锁存器，不过控制极性与 NOR 型相反。为了区分，我们把它们记成低有效输入 $\overline R,\overline S$：

课件把这些输入直接标成 R 和 S；这里加上横线只是为了清楚表达“低电平有效”。不要把两种实现的表混用：NOR 型是两个 0 时保持、两个 1 禁止；NAND 型是两个 1 时保持、两个 0 禁止。判断它们时，仍然可以回到门的真值关系逐步推导，而不是仅靠名称记忆。

6. D 锁存器：把数据与写入控制分开

我们回到 NOR 型 R-S 锁存器，在前面加两个 AND 门和一个反相器。数据输入叫 $D$，控制输入叫 $C$，让

$$S=CD,\qquad R=C\overline D.$$

这样设计的巧妙之处有两点。第一，$C=1$ 时，R-S 的置位或复位由 $D$ 决定；第二，$C=0$ 时，无论 $D$ 是什么，$R=S=0$，总是进入保持状态。两个 R-S 输入在稳定布尔值下不会同时为 1，因为 $D$ 与 $\overline D$ 不可能同时为 1。

我们把四种情况都推一遍。当 $C=1,D=1$ 时，$S=1,R=0$，所以 $Q=1$。当 $C=1,D=0$ 时，$S=0,R=1$，所以 $Q=0$。当 $C=0,D=1$ 时，两个与门都输出 0，所以 $Q$ 保持旧值；当 $C=0,D=0$ 时还是一样。于是得到

或者简洁写成

$$Q_{\mathrm{next}}=CD+\overline C Q.$$

这就是 D latch，数据锁存器。数据是什么由 $D$ 决定，允许不允许写由 $C$ 决定。门电路图可以进一步抽象成一个方框，标出 D、控制端以及 $Q,\overline Q$ 输出。课件中也把控制端标成 CLK，因为后面我们会用时钟来控制它。

这里必须把上次的延迟概念带进来。$D$ 的变化经过与门及反馈门才能到达 $Q$，所以写入不能靠一个任意短的控制脉冲。我们需要给电路足够的传播时间，让要写入的值确实到达并稳定；再把 $C$ 拉低，才把它锁住。

当 $C=1$ 时，D 锁存器是 transparent，透明的。透明不是没有物理延迟，而是说输入的变化在传播后会跟随到输出；在整个高电平有效期间，$D$ 变，$Q$ 就可能跟着变。$C=0$ 时，输入的后续变化才被挡住，$Q$ 保持先前值。所以它是电平敏感的，课堂称为 level-triggered，不能把它理解成只在 $C$ 上升的那一瞬间写一次。

7. 透明期间的毛刺为什么会成为问题

我们画三条波形：CLK、输入 D、输出 Q。高电平有效的 D 锁存器在 CLK 为低时保持，在 CLK 为高时跟随输入。假设 D 先从 0 变成 1，而那时 CLK 正低，Q 不动；等 CLK 变高，输入才传到输出。若高电平期间 D 又出现一个小的下凹，Q 也可能跟着下凹；若 D 在 CLK 仍高时从 1 变成 0，Q 也会在传播延迟后变成 0。

课堂波形为突出功能，常把输入输出的转换画在同一竖线上，但物理上输出应比输入晚一些。还有一个问题是，若 D 在锁存器快要关闭时改变，输入的传播与控制关闭可能重叠，就不能仅靠理想波形判断这次究竟保存了哪一值。我们现在不展开更细的时序参数，只记住：既要留传播时间，也不能把“关闭附近随便变化”当作可靠操作。

我们想要一种更便于控制的行为：在规定的时刻取一次输入，此后无论输入在这个周期内怎样变化，已保存的输出都不跟着变化。这样就引出了 D 触发器。

8. D 触发器：在时钟上升沿采样

D flip-flop，也叫数据触发器，在本课使用的是上升沿触发类型。它只在时钟由 0 变成 1 的上升沿采样 D，然后在自身传播延迟后更新 Q；在相邻有效沿之间，输出保持稳定。我们常用

$$Q^{+}=D\quad\text{在有效上升沿采样}$$

来表示它的功能。这里的 $Q^{+}$ 表示更新后的存储值，并不是说输出在数学意义上零时间完成变化。

回看刚才的波形：D 在两个上升沿之间出现短暂变化，若没有影响到采样时刻，它不会被输出跟随。D 已经稳定成新的值后，只有下一个上升沿到来，Q 才捕获这个新值。我们希望控制采样时刻，使组合电路有时间完成计算，再取它的最终结果。触发器不会自动辨认“这是不是毛刺”；可靠性仍依赖采样时刻安排正确。

课件用两个 D 锁存器说明实现：前一个叫 master，后一个叫 slave，中间节点连接前者输出与后者输入；两个控制端接互补的时钟。上升沿触发的图中，master 使用反相时钟，slave 使用原时钟。

为了读懂这张图，我们可以补上如下工作过程。CLK 为低时，master 打开跟随 D，slave 关闭而保持旧输出；CLK 上升时，master 关闭并保存刚才的 D，slave 打开，把 master 保存的值传到最终 Q。CLK 高电平期间，master 已经关住，即使外部 D 继续变化，也不能穿过 master 改变最终结果；CLK 下降时 slave 又关住。课堂展示了结构而没有逐项展开内部时序，这个过程是帮助理解结构的补全。

在电路符号上，我们用时钟端的小三角表示边沿触发。它与只画电平控制端的锁存器要区分开。今天用这种边沿触发存储单元来理解寄存器。

9. 从一位触发器扩展为多位寄存器

一个触发器保存一个 bit。若要保存四位数据，我们并排放四个触发器，分别接 $D_0,D_1,D_2,D_3$，输出为 $Q_0,Q_1,Q_2,Q_3$，把它们的时钟端接到同一个控制信号。这样在同一个有效沿，四位数据一起更新；其他时间则一起保持，构成一个 4-bit register。

更多位的寄存器也是同一思路：增加一位存储就增加对应的一位触发器。控制共享，数据各有各的通路。后面图中的一条线上画一个斜杠再写数字，表示这里实际上是一束多位信号，例如 $k$ 位状态或者 $M$ 位输入，而不是只有一根一位导线。

10. 地址空间与可寻址单位

再向上看，memory 不仅要存数据，还要能指明“我们要访问哪一个位置”。它由若干可以写入或读出的 location 组成，每个位置有唯一的 address。如果有四个位置，需要两位地址才能区分它们：00、01、10、11。一般地，$2^a$ 个位置需要 $a$ 位地址。

还有一个独立的量叫 addressability，可寻址单位的位数，也就是每一个地址所对应的位置保存多少位信息。课件例子中每个位置存 8 位，所以 addressability 是 8 bits。x86 中一个地址通常标识一个字节，这就是按字节寻址。地址有几位与每个地址对应几位数据，不能混在一起。

例如四个位置、每位置八位，地址位宽是 2，总数据容量则是 $4\times8=32$ 位。若位置数不是 2 的整数次幂，表示所有位置至少需要 $\lceil\log_2N\rceil$ 位，并要处理多出来的编码；课堂以下使用的都是二的幂，因而没有这项额外问题。

11. 搭一个总共六位的存储器

现在我们设计一个小到可以完全画出来的存储器：总共 6 bits，addressability 是 3 bits，所以只有两个地址位置。地址 0 存三位，地址 1 也存三位。我们需要一位地址 $a$，以及两行、每行三个一位存储单元。

先考虑读。输入是地址，输出是对应位置中的三位数据。我们要每次选中一行，屏蔽另一行。上一节的解码器正好做行选择：

$$x_0=\overline a,\qquad x_1=a.$$

当 $a=0$，$x_0=1,x_1=0$；当 $a=1$ 则相反。对每一列 $j\in\{0,1,2\}$，让选行信号与该行数据 AND，再将两行结果 OR：

$$Y_j=x_0Q_{0,j}+x_1Q_{1,j} =\overline aQ_{0,j}+aQ_{1,j}.$$

于是，被选中一行的数据乘 1 后通过，未被选中一行的数据乘 0 后消失。三个列电路并行工作，就一次读出一个三位字。把这段电路抽象起来，前面是 decoder，后面是 MUX。

再考虑写。我们需要三位输入数据 $B_2B_1B_0$，还有一个 Write Enable 信号，记为 $WE$。数据可以接到两行对应列的数据端，但写入控制不能无差别地接给所有行，否则同一次写会同时覆盖两个地址。我们应当把全局写使能与各行选择相结合：

$$WE_0=WE\,\overline a,\qquad WE_1=WE\,a.$$

只有“本次允许写”且“本行被地址选中”，该行才更新；另一行保留原值。如果 $WE=0$，无论地址选哪一行，都不写入。

扩大到四行或更多行，存储单元、地址译码、数据选择这三个角色没有改变，只是地址更多、decoder 和 MUX 也更复杂。真实主存不一定用寄存器阵列实现；这里通过一个小阵列，把“按地址读”和“按地址写”怎样由已有积木完成讲清楚。

12. 有限状态机：计算逻辑与状态寄存器的闭环

现在回到计数器。我们已经有能计算的组合逻辑，也有能保存中间结果的寄存器，于是“存储上一结果”的那个神秘盒子不再神秘。寄存器保存当前状态，组合逻辑根据当前状态与外部输入算出下一状态，时钟到来再把下一状态保存起来。单独的组合逻辑缺少的正是对状态信息的保存。

我们用 FSM，Finite State Machine，有限状态机来描述这种系统。每个状态是系统在某个离散时刻所有相关信息的一份快照。交通灯、电梯、风扇控制器乃至微处理器，都可以从状态和状态转移的角度理解。

要把一个状态机定义清楚，需要说明有限的状态集合、外部输入、外部输出、完整的状态转移规则，以及每个外部输出由什么决定。画出状态图时，圆圈表示状态，带条件的箭头表示满足什么输入时转到哪一个状态。状态名只是描述，真正实现还需要编码成 bit。

硬件框图可以分成三部分：next-state logic、state register、output logic。若当前状态是 $k$ 位向量 $q$，外部输入是 $M$ 位向量 $x$，则下一状态逻辑计算

$$q^{+}=F(q,x).$$

下一状态送到 $k$ 位寄存器的数据端，有效时钟沿更新后，又从寄存器的输出反馈给下一状态逻辑。课件中的输出逻辑只由当前状态产生输出：

$$y=G(q),$$

其中 $y$ 是 $N$ 位输出。这样的输出组织属于 Moore 型。我们接下来的交通灯就是这种结构：知道当前状态，就已经知道两组灯应是什么颜色。

13. 交通灯例子：先把需求变成状态图

考虑两条相交道路 Academic Avenue 和 Bravado Boulevard。用 A、B 简记它们。每条路有一个传感器：$T_A=1$ 表示 A 路上有人，$T_A=0$ 表示无人；$T_B$ 同理。两组灯分别记为 $L_A,L_B$，每组可取绿、黄、红三种颜色。

当前获得绿灯的一条路只要还有人，就继续保留绿灯；一旦无人，先进入该方向黄灯状态，再把通行权交给另一条路。每次时钟更新决定下一个状态。

我们定义四个状态：

复位先进入 $S_0$。在 $S_0$，只要 $T_A=1$ 就留在 $S_0$；$T_A=0$ 才转到 $S_1$。在 $S_1$，下一次无条件转到 $S_2$。在 $S_2$，只要 $T_B=1$ 就保持，$T_B=0$ 才转到 $S_3$。在 $S_3$，下一次无条件回到 $S_0$。

这个策略还有两个值得读懂的结果：若两条路都无人，它会不断经过四种状态循环；若当前绿灯方向持续有人，它就一直占有绿灯，即使另一条路也有人。

把状态图整理成表格：

这里的 $X$ 表示该输入不影响这一行的转移结果，不是一个“未知的物理电平”。例如当前在 $S_0$ 时，只看 $T_A$，$T_B$ 为 0 或 1 都不改变本行结论。

14. 状态编码：把转移表变成布尔表达式

四个状态至少需要两位编码。我们使用最直接的一种：$S_0=00,S_1=01,S_2=10,S_3=11$。为避免把状态名 $S_0$ 和某个编码位混淆，下面用小写 $s_1,s_0$ 表示当前状态的高、低位，用 $s_1',s_0'$ 表示下一状态的两位。

一旦有了这张表，我们就能用上次的 SOP 方法。先看高位 $s_1'$：当前状态为 01 时，下一状态是 10，高位为 1；当前状态为 10 时，无论 $T_B$ 是什么，下一状态高位也都为 1。写成课件展开的形式就是

$$s_1'=s_0\overline{s_1} +s_1\overline{s_0}\,\overline{T_B} +s_1\overline{s_0}T_B.$$

后两项合并时用到 $\overline{T_B}+T_B=1$，所以

$$s_1'=\overline{s_1}s_0+s_1\overline{s_0}=s_1\oplus s_0.$$

这也可以直接读出来：当前状态两位不同，高位下一次为 1；两位相同，高位下一次为 0。

再看低位 $s_0'$。只有两种条件使它为 1：当前状态为 00 且 $T_A=0$，或者当前状态为 10 且 $T_B=0$。所以正确的式子是

$$s_0'=\overline{s_1}\,\overline{s_0}\,\overline{T_A} +s_1\overline{s_0}\,\overline{T_B}.$$

课件公式纠错：Lecture 6 的 PDF 物理第 241—242 页（印刷第 69—70 页）把这个式子首项的 $\overline{s_1}$ 写成了 $s_1$。这不是抽取时丢失横线：原 PDF 页面也是如此。按状态表第一行，$s_1s_0=00,T_A=0$ 必须有 $s_0'=1$，所以首项必须含 $\overline{s_1}$。此外较早动画页 238—239（印刷 66—67）把状态 10 的传感器条件列错放到 $T_A$ 下，后续页已改回 $T_B$；本篇统一按状态图及后续正确的表格整理。

我们可以用两行快速检查：在 00、$T_A=0$ 时，首项为 1，下一状态得到 01；在 10、$T_B=0$ 时，第二项为 1，高位也为 1，得到 11。这样公式与原来的状态图逐行吻合。

15. 输出编码：状态决定灯色

现在还需要把绿、黄、红变成控制电路能处理的位模式。三种颜色至少要两位，我们约定绿为 00，黄为 01，红为 10。于是两组灯分别有两位输出 $L_{A1},L_{A0}$ 和 $L_{B1},L_{B0}$。

按每一列找 1，就可以读出

$$L_{A1}=s_1,\qquad L_{A0}=\overline{s_1}s_0,$$

$$L_{B1}=\overline{s_1},\qquad L_{B0}=s_1s_0.$$

例如 A 灯高位为 1 的两行恰好都是 $s_1=1$；A 灯低位只在状态 01 为 1，因此是 $\overline{s_1}s_0$。B 灯也是同样按列推导。我们由此确定了输出逻辑，而下一状态的两个式子确定了状态更新逻辑。

到这里，这个状态机的输入、状态、下一状态及输出已经都能用 bit 和布尔函数表达。我们可以给定当前状态及两条路的传感器值，算出下一状态；也可以只根据当前状态，算出两组灯的控制编码。把这些逻辑实际接到状态寄存器周围的完整电路图，是后续继续做的内容。

来源与补全：据 2026-09-29 A、B 完整转写，核对 Lecture 6 PDF 至约 253 页；完整 FSM 原理图接下一课。主从结构的逐阶段工作过程、计数关系和位宽计算为编者补全；NOR 与 FSM 原式错误就地纠正。截图沿用已核实的回放帧。