第6章 时序逻辑设计（状态机）

一、导读

1.1 本章学习目标

理解时序逻辑电路与组合逻辑电路的根本区别：记忆功能和状态依赖性

掌握各种触发器（D、JK、T、SR）的特性、工作原理和转换方法

深入理解有限状态机（FSM）的概念、分类和设计方法

熟练运用状态图（State Diagram）和状态表（State Table）描述状态机行为

掌握Mealy型和Moore型状态机的区别及其设计权衡

理解状态化简和状态分配的方法及其对电路复杂度的影响

掌握同步时序电路的完整设计流程

了解状态机在实际控制系统中的典型应用模式

1.2 为什么本章如此重要

时序逻辑是数字设计中将系统从"被动响应"提升到"主动控制"的关键。组合逻辑电路只能根据当前输入被动地产生输出，而时序逻辑电路具有记忆能力，能够根据当前输入和历史状态做出决策。这种记忆功能使得数字系统能够跟踪过程、维护状态、实现复杂的控制逻辑——这些正是现代计算机、通信设备和智能控制系统的核心能力。

有限状态机（Finite State Machine，FSM）是时序逻辑设计的核心范式。状态机用有限的离散状态来描述系统的行为，通过状态转移规则来定义系统如何响应输入和环境变化。从简单的交通灯控制器到复杂的CPU指令流水线，从通信协议的数据链路层到用户界面的交互逻辑，状态机模型无处不在。掌握状态机的设计方法，就是掌握了描述和控制复杂系统行为的核心工具。

触发器是构建时序逻辑的基本存储元件。D触发器在时钟边沿捕获输入数据并保持到下一个时钟周期，是构建寄存器、计数器和状态机的基础。理解触发器的建立时间、保持时间、传播延迟等时序参数，是设计可靠时序电路的前提。

状态机的设计质量直接影响系统的性能、可靠性和可维护性。一个设计良好的状态机应该具有清晰的状态定义、完备的转移覆盖、合理的状态编码和可预测的行为。状态化简可以减少硬件资源的使用，状态分配则影响组合逻辑的复杂度和最终电路的速度。

1.3 核心问题引导

时序逻辑电路为什么需要时钟信号？时钟在同步时序电路中起什么作用？

D触发器和JK触发器各有什么特点？为什么现代设计中最常用的是D触发器？

Mealy型状态机和Moore型状态机有什么本质区别？各自适合什么应用场景？

为什么状态化简是必要的？如何判断两个状态是等价的？

状态分配（状态编码）的选择如何影响最终电路的复杂度和性能？

如何确保状态机不会进入无效状态？如果进入了无效状态应该怎么办？

在实际工程中，状态机通常用什么方式实现？HDL描述与原理图设计各有什么优势？

二、核心概念详解

2.1 触发器与时序存储元件

触发器（Flip-Flop）是时序逻辑电路的基本存储元件，能够在时钟信号的控制下捕获并保持一位二进制信息。触发器的核心特性是它有两个稳定状态（0和1），可以在外部信号的作用下从一个稳态切换到另一个稳态，并在没有外部作用时保持当前状态。

D触发器（D Flip-Flop）是最常用的触发器类型。它在时钟的有效边沿（上升沿或下降沿）捕获D输入的值，并将其传送到Q输出。在时钟边沿之间，Q输出保持不变。D触发器的特性方程为Q(t+1) = D，即下一个状态直接等于当前D输入值。这种简单直观的特性使得D触发器在数字设计中最为流行。

JK触发器（JK Flip-Flop）功能更为灵活。当J=K=0时保持状态，J=K=1时翻转状态，J=1,K=0时置1，J=0,K=1时置0。JK触发器的功能完整性使其在早期设计中广泛使用，但由于其特性方程较复杂，在现代基于HDL的设计中已较少直接使用。

T触发器（T Flip-Flop）是JK触发器的简化版本，当T=1时在时钟边沿翻转，T=0时保持。T触发器是构建计数器的理想元件。SR触发器（SR Flip-Flop）是最基本的触发器类型，但存在S=R=1的不确定状态，在实际设计中通常需要额外的约束逻辑。

2.2 有限状态机的基本概念

有限状态机（Finite State Machine，FSM）是一种数学模型，用于描述具有离散状态和状态转移行为的系统。一个完整的FSM由五个要素组成：有限个状态集合S、有限个输入集合I、有限个输出集合O、状态转移函数delta（下一状态函数）和输出函数lambda。

状态转移函数delta定义了在当前状态和当前输入下，系统将转移到哪个下一状态：S(t+1) = delta(S(t), I(t))。输出函数lambda定义了系统的输出。根据输出函数的定义方式，状态机分为两种基本类型。

Moore型状态机的输出仅取决于当前状态：O(t) = lambda(S(t))。Moore型状态机的输出在状态改变时才会变化，与输入的变化无关。这种特性使得Moore型状态机的输出更加稳定，不容易受输入毛刺的影响。

Mealy型状态机的输出取决于当前状态和当前输入：O(t) = lambda(S(t), I(t))。Mealy型状态机可以对输入变化做出更快的响应（不需要等到状态改变），但输出可能随输入的瞬时变化而波动。

2.3 状态图与状态表

状态图（State Diagram）是状态机最直观的图形化表示方法。在状态图中，每个状态用一个圆圈或圆角矩形表示，状态之间的转移用带箭头的有向边表示。每条转移边上标注触发该转移的输入条件和产生的输出（格式为"输入/输出"）。

Moore型状态机的输出标注在状态节点内部（因为输出只取决于状态），Mealy型状态机的输出标注在转移边上（因为输出取决于状态和输入的组合）。

状态表（State Table）是状态机的表格化表示。状态表的列包括：当前状态、输入、下一状态和输出。每一行描述在特定当前状态和输入组合下的完整行为。状态表与状态图是等价的表示方式，可以相互转换。

状态表的优点是可以系统性地检查所有状态和输入组合的完备性，便于发现遗漏的转移条件。状态图的优点是直观形象，便于理解系统的整体行为逻辑。在实际设计中，通常先用状态图进行概念设计，再转换为状态表进行详细实现。

2.4 状态化简与状态分配

状态化简（State Minization）的目标是找到等价的状态机中状态数最少的版本。减少状态数意味着需要更少的触发器和更简单的组合逻辑，从而降低硬件成本。两个状态是等价的，当且仅当对于所有可能的输入序列，从这两个状态出发产生的输出序列完全相同。

状态化简的常用方法是隐含表法（Implication Table Method）或分区法（Partitioning Method）。基本思路是：首先找出所有可能在相同输入下产生不同输出的状态对，将它们标记为不等价；然后迭代检查，如果两个状态在某个输入下转移到已知不等价的状态对，则它们也不等价。最终未被标记为不等价的状态对可以合并。

状态分配（State Assignment）是为每个状态分配唯一的二进制编码的过程。对于n个状态，需要至少ceil(log2(n))个触发器。状态分配的选择直接影响下一状态逻辑和输出逻辑的复杂度。

常用的状态编码方式包括：二进制顺序编码（000, 001, 010, ...）、Gray码编码（相邻状态只有一位不同）和独热编码（One-Hot，每个状态只有一个触发器为1）。独热编码虽然使用更多触发器，但状态转移逻辑最简单，在FPGA实现中通常是优选方案。

2.5 同步时序电路的设计流程

同步时序电路的完整设计流程包括以下步骤：第一步，根据需求描述建立原始状态图或状态表；第二步，进行状态化简，消除等价状态；第三步，进行状态分配，为每个状态指定二进制编码；第四步，根据状态表和编码确定触发器类型，写出下一状态方程和输出方程；第五步，使用卡诺图或其他方法化简逻辑表达式；第六步，画出逻辑电路图。

在整个设计过程中，还需要考虑自启动（Self-Starting）问题。如果状态机由于噪声或故障进入了无效状态（未分配的状态编码），它应该能够在有限个时钟周期内自动返回有效状态循环。设计时需要检查所有无效状态的转移路径，确保不存在"死胡同"。

三、深入分析与讨论

3.1 Mealy型与Moore型的工程权衡

Mealy型和Moore型状态机各有优劣，选择哪种类型取决于具体的应用需求。Mealy型状态机的优势在于响应速度快——输出可以在输入变化的同一个时钟周期内就做出反应，不需要等待状态转移完成。这意味着Mealy型状态机通常可以用更少的状态实现相同的功能。

然而，Mealy型状态机的输出直接依赖于输入，如果输入信号存在毛刺或不稳定，输出也会受到影响。在异步输入环境中，这可能导致输出的短暂错误。此外，Mealy型状态机的调试和验证通常比Moore型更复杂，因为输出行为同时取决于状态和输入。

Moore型状态机的输出只取决于状态，因此更加稳定和可预测。输出只在状态转移后的时钟边沿才可能变化，这为时序分析提供了更好的确定性。但Moore型状态机通常需要更多的状态来实现相同的功能，因为某些需要快速响应输入变化的行为需要额外的状态来表达。

在实际设计中，两种类型可以混合使用。对于需要快速响应的输出使用Mealy型，对于需要稳定输出的使用Moore型。

3.2 状态机编码策略的深入比较

不同的状态编码策略对电路性能有显著影响。二进制顺序编码使用最少的触发器（ceil(log2(n))个），但相邻状态之间可能有多位同时变化，导致下一状态逻辑复杂且可能产生冒险。

Gray码编码确保相邻状态之间只有一位变化，减少了冒险风险，也简化了部分转移逻辑。但对于非相邻状态之间的转移，Gray码不一定比二进制编码更优。

独热编码（One-Hot Encoding）使用n个触发器表示n个状态，每个状态恰好有一个触发器为1。独热编码的优势在于：状态转移逻辑极其简单（每个触发器的下一状态方程只涉及少数几个项）；状态检测非常容易（直接观察哪个触发器为1）；状态机更容易修改和扩展。缺点是触发器数量多，在触发器资源有限的场合不适用。但在FPGA中，触发器资源通常很丰富，独热编码是最常用的选择。

四、实践案例

4.1 交通灯控制器的状态机设计

设计一个十字路口交通灯控制器，控制东西方向和南北方向的红、黄、绿三色灯。设计要求：绿灯持续30秒，黄灯持续5秒，红灯持续35秒。东西方向和南北方向交替通行。

状态定义：S0（东西绿+北红）、S1（东西黄+北红）、S2（东西红+北绿）、S3（东西红+北黄）。这是一个Moore型状态机，输出（灯的颜色）只取决于当前状态。状态转移条件为定时器到达指定时间。状态图是一个简单的环形结构：S0->S1->S2->S3->S0。

使用二进制编码（2个触发器），状态分配为S0=00, S1=01, S2=10, S3=11。写出下一状态方程和输出方程后，可以用最少的逻辑门实现。

4.2 序列检测器的设计

设计一个Mealy型序列检测器，检测输入序列中是否出现"1101"模式。当检测到完整的"1101"序列时，输出Z=1。

状态定义：S0（初始状态，等待第一个1）、S1（收到第一个1）、S2（收到连续的11）、S3（收到110）、检测到1101时回到S2（因为"1101"的最后两位"01"中的"1"可能是新序列的开始——实际上回到S0因为最后一位是1...需要仔细分析重叠情况）。

这是一个典型的Mealy型应用，因为输出需要在接收到最后一个输入位时立即产生，而不需要等到下一个时钟周期。使用Mealy型可以用更少的状态（4个而非5个）实现该功能。

五、常见误区与注意事项

误区一：状态数越少，设计一定越好。 状态化简减少了触发器数量，但可能增加组合逻辑的复杂度。在某些情况下，保留一些冗余状态可以简化状态转移逻辑，降低冒险风险，提高电路速度。特别是在FPGA实现中，触发器资源通常不是瓶颈，过度追求状态数最小化可能适得其反。

误区二：Mealy型和Moore型不能相互转换。 任何Mealy型状态机都可以等价地转换为Moore型状态机，反之亦然。但转换可能导致状态数增加。从Mealy到Moore的转换通常需要为每个"状态+输出"组合创建新的Moore状态。

误区三：状态机设计完成后不需要考虑无效状态。 实际电路中，由于噪声、辐射或电源波动，触发器可能意外翻转，导致状态机进入无效状态。如果不处理这种情况，状态机可能永远困在无效状态中，导致系统死锁。设计时必须确保所有无效状态都有返回有效状态的路径。

误区四：所有触发器必须使用同一种类型。 虽然大多数现代设计统一使用D触发器，但在某些特殊情况下，混合使用不同类型的触发器可能更优。例如，计数器中的触发器可以使用T触发器（简化翻转逻辑），而状态机中的触发器使用D触发器。不过，使用统一的D触发器有利于标准化和HDL描述。

六、本章小结

本章深入讲解了时序逻辑电路和有限状态机的设计方法。触发器是时序逻辑的基本存储元件，D触发器因其简单直观的特性成为最广泛使用的类型。有限状态机是描述时序系统行为的标准模型，分为Mealy型和Moore型两种基本类型。状态图和状态表是状态机的两种等价描述方式，可以相互转换。状态化简减少硬件资源的使用，状态分配影响电路的复杂度和性能。完整的同步时序电路设计流程从需求分析到电路实现，每一步都需要仔细处理。状态机设计是数字控制系统的核心技能，为后续章节中更复杂的时序电路实践奠定了理论基础。

七、思考题与练习

设计一个D触发器构成的四位寄存器，具有并行加载和异步清零功能。画出电路图，写出控制逻辑。

将给定的JK触发器转换为等效的D触发器。画出转换电路，推导JK输入端关于D输入的函数表达式。

设计一个Moore型状态机，实现一个自动售货机的控制逻辑。该售货机接受5角和1元两种硬币，商品价格为2.5元，找零只退5角。画出状态图并写出状态表。

对以下状态表进行化简，找出所有等价状态并合并：（给出一个6状态的状态表）。化简后画出状态图。

比较二进制编码、Gray码编码和独热编码在实现4状态和8状态状态机时的优缺点。从触发器数量、组合逻辑复杂度和抗冒险能力三个维度进行分析。

设计一个Mealy型序列检测器，检测输入序列中的"1011"模式（允许重叠）。画出状态图，验证当输入序列为10110111时，输出序列是否正确。

解释状态机中"自启动"的含义。设计一个使用二进制编码的3状态状态机（需要2个触发器），确保无效状态11能在一个时钟周期内返回到有效状态00。

查阅资料，了解状态机在通信协议（如UART接收器或SPI控制器）中的应用。设计一个简单的UART接收器状态机，能够接收8位数据帧（1位起始位+8位数据位+1位停止位）。