第三讲 · 时序逻辑与有限状态机

对应材料：2025 计组复习提纲“时序逻辑”，包括有限状态机与计数器。

组合逻辑只看“现在的输入”，时序逻辑还要看“过去留下的状态”：

Qn+1=f(Qn,Xn),Yn=g(Qn,Xn).\begin{aligned} Q^{n+1}&=f(Q^n,X^n),\\ Y^n&=g(Q^n,X^n). \end{aligned}

这里 QnQ^n 是当前状态，Qn+1Q^{n+1} 是下一状态，XnX^n 是输入，YnY^n 是输出。这个简单模型会一路延伸到寄存器堆、PC、流水线寄存器乃至多周期控制器。

1. 为什么反馈会产生“记忆”

如果把组合逻辑的输出反馈到输入，电路就可能保留之前的状态。但随意反馈会造成竞争：门延迟、温度和电压稍有变化，最终状态都可能不同。

工程上不依赖“碰巧稳定”的直通环路，而使用经过设计的锁存器和触发器，并让状态只在规定的使能或时钟时刻改变。

2. 锁存器与触发器

2.1 D 锁存器

D 锁存器是电平敏感器件：

  • 使能有效时，QQ 跟随 DD；
  • 使能无效时，QQ 保持原值。

“有效期间一直跟随”意味着它是透明的。如果一个系统只希望状态在某一瞬间更新，就要使用边沿触发器。

2.2 D 触发器

D 触发器在时钟边沿采样输入：

Qn+1=D.Q^{n+1}=D.

在两个有效边沿之间，即使 DD 变化，QQ 也保持不变。CPU 中的 PC、通用寄存器和流水线寄存器都可以从这个模型理解。

2.3 JK 触发器

JK 触发器特性方程为

Qn+1=JQ‾n+K‾Qn.Q^{n+1}=J\overline Q^n+\overline K Q^n.
JJKK下一状态
00保持
01清零
10置一
11翻转

计数器中常利用 J=K=1J=K=1 让某一位每逢条件满足就翻转。

3. 建立时间、保持时间与时钟

触发器并不是在边沿到来时“瞬间、无限快”地读入数据：

  • 建立时间 tsetupt_{setup}：边沿到来前，输入必须稳定的时间；
  • 保持时间 tholdt_{hold}：边沿到来后，输入还要继续稳定的时间；
  • 时钟到输出延迟 tcqt_{cq}：边沿后，输出真正变化所需的时间。

两个寄存器之间放组合逻辑时，时钟周期至少满足

Tclk≥tcq+tcomb,max+tsetup.T_{clk}\ge t_{cq}+t_{comb,max}+t_{setup}.

这就是后面单周期 CPU “最长指令决定时钟周期”、流水线“最长一级决定时钟周期”的电路基础。

4. 有限状态机的两种类型

4.1 Moore 型

Moore 型输出只由当前状态决定：

Yn=g(Qn).Y^n=g(Q^n).

输出通常写在状态圆圈内。优点是输出稳定、逻辑清晰；代价是有时需要更多状态，并且输出往往到下一个时钟后才改变。

4.2 Mealy 型

Mealy 型输出同时由状态和输入决定：

Yn=g(Qn,Xn).Y^n=g(Q^n,X^n).

输出写在状态转移边上，常用“输入/输出”标记。它能更快响应输入、状态数可能更少，但组合输入毛刺可能直接影响输出。

5. 状态机设计的完整流程

课件给出的步骤可以整理为：

  1. 从需求中确定输入、输出和需要记住的历史；
  2. 定义状态及初始状态；
  3. 画状态转移图；
  4. 写状态转换表和输出表；
  5. 选择状态编码；
  6. 推导下一状态逻辑与输出逻辑；
  7. 用触发器和组合逻辑实现；
  8. 画时序图或仿真，检查所有输入序列。

不要一上来就写布尔表达式。状态图负责“把行为讲明白”，状态表负责“穷举不漏”，最后才是电路化简。

6. 例：不重叠检测序列 1101

用 Mealy 状态机记录“已经匹配了多长前缀”：

状态已匹配内容
S0S_0尚未匹配
S1S_11
S2S_211
S3S_3110

关键转移：

  • S0S_0 读到 1 去 S1S_1；
  • S1S_1 再读到 1 去 S2S_2；
  • S2S_2 读到 0 去 S3S_3；
  • S3S_3 读到 1 时输出 1，完成 1101 检测。

因为题目要求不重叠检测，完成后回到初始状态；如果允许重叠，就要根据末尾还能匹配哪个前缀来选择后继状态。这里真正困难的是失败以后保留多少有用历史，而不是画圆圈本身。

7. 状态编码

假设有 NN 个状态：

  • 二进制编码需要 ⌈log⁡2N⌉\lceil\log_2N\rceil 个触发器，触发器少，组合译码可能复杂；
  • 格雷编码让相邻状态尽量只变一位，可减少同时翻转；
  • 独热码每个状态占一位，需要 NN 个触发器，但下一状态逻辑常更简单。

编码会影响面积、速度和功耗，却不改变状态机的外部行为。复位后必须进入定义好的初始状态；未使用编码也要考虑如何回到合法状态，避免状态机“锁死”。

7.1 用 Verilog 描述状态机

课件的状态机例子还给出 Verilog 与仿真波形。代码结构最好直接对应状态机模型：

always @(posedge clk or posedge reset)
    if (reset) state <= S0;
    else       state <= next_state;

always @(*) begin
    next_state = state;
    output_flag = 1'b0;
    case (state)
        S0: if (in) next_state = S1;
        /* 其余状态按状态图填写 */
        default: next_state = S0;
    endcase
end

时钟块用非阻塞赋值保存状态；组合块先给默认值，再覆盖各分支，避免遗漏路径而推断出额外锁存。Moore 输出只按 state 决定，Mealy 输出还会在分支中读取 in。最后用仿真波形检查复位、正常序列、失败回退和非法状态。

8. 同步时序电路的分析

面对一张由触发器和组合逻辑构成的电路图：

  1. 写每个触发器输入端的激励方程；
  2. 代入触发器特性方程，得到状态方程；
  3. 写输出方程；
  4. 穷举当前状态和输入，列状态转换表；
  5. 画状态图或时序图；
  6. 用人话说明功能，并检查非法状态。

例如 D 触发器最直接：只要写出 DiD_i 的组合逻辑，就有 Qin+1=DiQ_i^{n+1}=D_i。JK 触发器则需要代入

Qin+1=JiQ‾in+K‾iQin.Q_i^{n+1}=J_i\overline Q_i^n+\overline K_iQ_i^n.

9. 同步计数器

同步计数器的所有触发器共用一个时钟，状态在同一边沿一起更新，因此不会逐级累积时钟传播延迟。

对 4 位同步二进制加法计数器，可让：

T0=1,T1=Q0,T2=Q1Q0,T3=Q2Q1Q0,\begin{aligned} T_0&=1,\\ T_1&=Q_0,\\ T_2&=Q_1Q_0,\\ T_3&=Q_2Q_1Q_0, \end{aligned}

其中 TiT_i 表示第 ii 位是否翻转。直观上：最低位每拍翻转；更高位只有在所有低位都为 1 时翻转。

设计模 MM 计数器时，必须把 MM 个有效状态和剩余非法状态都纳入状态表。若非法状态能自动回到有效循环，就称有自启动能力。

10. 异步计数器

异步计数器只把系统时钟送给最低位，后一位把前一位输出当作自己的时钟。它结构简单，但翻转会像波纹一样逐级传播：

系统时钟 → Q0 翻转 → Q1 翻转 → Q2 翻转 → Q3 翻转

所以中间可能短暂出现错误编码，位数增加后最高工作频率也明显下降。课件用模 16 异步加法计数器说明这种逐级传播现象。

11. 同步、异步与“组合/时序”的判断

问题组合逻辑同步时序异步时序
有状态吗无有有
状态何时变不适用统一时钟边沿由输入或前级变化触发
分析重点真值表状态方程、时序约束传播顺序、竞争冒险
典型部件MUX、ALU寄存器、同步 FSM脉动计数器

12. 一条贯穿 CPU 的主线

后面遇到 CPU 数据通路，可以这样拆：

  • PC、寄存器堆、流水线寄存器是状态元件；
  • ALU、扩展器、加法器、MUX 是组合逻辑；
  • 控制器根据指令和状态选择组合路径；
  • 时钟边沿把本周期计算出的下一状态一次性写入状态元件。

只要能分清“本周期用旧状态算什么”和“边沿后保存什么”，复杂 CPU 图就不再是一团线。

评论