第6章 同步时序电路（状态机设计）
一、导读
1.1 本章学习目标
理解同步时序电路的基本结构：触发器组（状态寄存器）+ 组合逻辑（次态逻辑和输出逻辑）
掌握有限状态机（FSM）的概念，区分Mealy型和Moore型状态机
学会使用状态图（State Diagram）和状态表（State Table）描述状态机行为
掌握状态化简（State Minimization）的方法，通过合并等价状态减少电路复杂度
理解状态编码（State Encoding）的策略：二进制编码、格雷码编码和独热编码
能够根据功能需求完成从状态图到电路实现的完整设计流程
了解状态机在序列检测器、控制器等实际应用中的设计方法
认识状态机设计中的关键问题：死锁、不可达状态和自启动
1.2 为什么本章如此重要
有限状态机是数字系统设计中最核心、最普遍的设计范式。从简单的交通灯控制器到复杂的CPU指令流水线控制，从串行通信协议到用户界面逻辑，状态机无处不在。可以说，掌握了状态机设计，就掌握了数字系统设计的核心方法论。
状态机之所以如此重要，是因为它提供了一种系统化的方法来描述和设计具有"记忆"和"决策"能力的系统。任何可以根据当前状态和输入来确定行为和下一步状态的系统，都可以用状态机模型来描述。这种模型的强大之处在于：它是有限的（状态数量有限）、确定的（给定状态和输入，行为唯一确定）、可分析的（可以用数学方法验证正确性）。
在工程实践中，状态机设计的好坏直接决定了系统的可靠性、可维护性和可扩展性。一个设计良好的状态机应该具有清晰的语义、完备的状态覆盖、合理的状态转移和优雅的错误处理。状态化简和状态编码的选择则影响着最终电路的面积和速度。本章将帮助你建立从需求分析到电路实现的完整状态机设计能力。
1.3 核心问题引导
同步时序电路由哪几个部分组成？每个部分的功能是什么？
Mealy型状态机和Moore型状态机有什么区别？各有什么优缺点？
状态图和状态表如何相互转换？它们各自适合描述什么样的系统行为？
什么是等价状态？如何通过状态化简来减少状态机的复杂度？
不同的状态编码方式对电路性能有什么影响？如何选择合适的编码方案？
如何确保状态机不会出现死锁或进入不可达状态？
从功能需求到完整的状态机电路，设计流程包含哪些步骤？
二、核心概念详解
2.1 同步时序电路的基本结构
同步时序电路（Synchronous Sequential Circuit）由三个核心部分组成：状态寄存器（State Register）、次态逻辑（Next-State Logic）和输出逻辑（Output Logic）。状态寄存器由一组触发器组成，存储电路的当前状态。次态逻辑是组合电路，根据当前状态和输入计算下一个状态。输出逻辑也是组合电路，根据当前状态（Moore型）或当前状态和输入（Mealy型）产生输出。
在时钟上升沿，次态逻辑计算出的下一个状态被锁存到状态寄存器中，成为新的当前状态。这个过程在每个时钟周期重复，形成状态的序列演进。由于所有触发器共享同一个时钟信号，状态的变化是同步发生的——在同一个时钟边沿，所有触发器同时更新。
这种结构的优势在于时序行为的高度可预测性。所有的状态变化都发生在时钟边沿，组合逻辑有整整一个时钟周期来完成计算。设计者可以通过静态时序分析精确地验证电路是否满足建立时间和保持时间的约束，从而确保电路在目标频率下正确工作。
同步时序电路的设计流程通常包括：(1) 根据功能需求画出状态图或状态表；(2) 进行状态化简，合并等价状态；(3) 进行状态编码，为每个状态分配二进制编码；(4) 根据编码后的状态表推导次态逻辑和输出逻辑的布尔表达式；(5) 使用卡诺图或EDA工具化简表达式；(6) 画出逻辑电路图或使用HDL描述。
2.2 Mealy型与Moore型状态机
Mealy型状态机的输出取决于当前状态和当前输入：Output = f(Current State, Input)。Moore型状态机的输出仅取决于当前状态：Output = g(Current State)。这两种模型可以相互转换，但各有特点。
Mealy型状态机的优势在于：对于相同的功能，Mealy型通常需要更少的状态，因为输出可以直接响应输入变化，无需通过状态转移来体现。此外，Mealy型对输入的响应更快——输入变化后，输出可以立即通过组合逻辑改变，无需等待下一个时钟边沿。
然而，Mealy型也有缺点：输出可能在时钟周期内随输入变化而多次变化（如果输入不稳定），容易产生毛刺（Glitch）。在异步输入环境中，Mealy型的输出可能出现不可预测的短暂脉冲。
Moore型状态机的输出仅与状态相关，因此输出在每个时钟周期内是稳定的（只在时钟边沿变化）。这种特性使得Moore型更容易与同步系统集成，输出信号更干净。但Moore型通常需要更多的状态来实现相同的功能，因为某些需要立即响应的行为必须通过额外的状态转移来实现。
在实际设计中，选择Mealy型还是Moore型取决于具体需求。如果输出需要快速响应输入且可以容忍组合逻辑延迟，选择Mealy型；如果输出的稳定性更重要，选择Moore型。许多实际的状态机设计会混合使用两种模型：大部分输出使用Moore型，少数需要快速响应的输出使用Mealy型。
2.3 状态图与状态表
状态图（State Diagram）是状态机最直观的图形化表示。每个状态用一个圆圈（或圆角矩形）表示，状态之间的转移用带箭头的有向边表示。边上标注着触发转移的输入条件和产生的输出。在Mealy型状态图中，标注格式为"输入/输出"；在Moore型状态图中，输出标注在状态圆圈内部，转移边上只标注输入条件。
状态表（State Table）是状态机的表格化表示。表的列包括：当前状态、输入、次态和输出。每一行描述在特定当前状态和输入组合下的行为。状态表与状态图完全等价，可以相互转换。状态表的优势在于其系统性和完备性——每一行对应一种状态-输入组合，不会遗漏任何情况。
状态表可以进一步分解为次态表和输出表。次态表列出每种状态-输入组合下的下一个状态；输出表列出每种状态（Moore型）或状态-输入组合（Mealy型）下的输出值。这种分解使得从状态表推导逻辑表达式更加方便。
绘制状态图时的关键原则：(1) 明确起始状态（Initial State），通常用箭头指向第一个状态来表示；(2) 确保每个状态在所有可能的输入组合下都有明确的转移目标（完备性）；(3) 避免不必要的状态，通过状态化简来优化。
2.4 状态化简
状态化简（State Minimization）的目标是找到等价的状态机中状态数量最少的版本。减少状态数量意味着减少状态寄存器的触发器数量和简化次态逻辑，从而降低电路面积和功耗。
两个状态Si和Sj是等价的，当且仅当对于所有可能的输入序列，从Si出发和从Sj出发产生的输出序列完全相同。判断等价性的实用方法是隐含表法（Implication Table Method）：首先检查两个状态在每种输入下的输出是否相同（如果不同则必然不等价），然后检查它们的次态对是否等价（形成等价性隐含关系）。通过迭代排除不等价的状态对，最终找到所有等价状态组。
化简的步骤：(1) 构建隐含表，列出所有状态对；(2) 对于每对状态，检查在每种输入下的输出是否一致，不一致的标记为不等价并划去；(3) 对于剩余的状态对，检查它们的次态对是否等价。如果次态对已被标记为不等价，则该状态对也不等价；(4) 重复步骤3直到没有新的不等价对被发现；(5) 将所有等价状态合并为一个状态。
状态化简的结果不是唯一的——可能存在多个等价的最简状态机，它们的状态数量相同但状态定义不同。此外，某些状态化简算法可能无法找到全局最优解。但对于大多数实际的状态机设计，隐含表法可以得到最优或接近最优的结果。
2.5 状态编码
状态编码（State Encoding / State Assignment）是为每个状态分配唯一的二进制编码的过程。对于一个有n个状态的状态机，需要ceil(log2(n))个触发器。编码方式的选择对电路的面积和速度有显著影响。
二进制编码（Binary Encoding）：按自然二进制数顺序为状态分配编码（S0=000, S1=001, S2=010, ...）。优点是使用的触发器数量最少；缺点是相邻状态之间的编码可能有多位不同，导致次态逻辑复杂。
格雷码编码（Gray Code Encoding）：相邻状态的编码只有一位不同。这种编码方式可以简化次态逻辑，因为每次状态转移只需要改变一个触发器的值。格雷码特别适合状态转移主要发生在相邻状态之间的状态机（如计数器）。
独热编码（One-Hot Encoding）：使用n个触发器表示n个状态，每个状态只有一个触发器为1，其余为0（S0=0001, S1=0010, S2=0100, S3=1000）。优点是次态逻辑非常简单（每个触发器的次态方程只涉及少数项），状态转移速度快；缺点是使用的触发器数量多。在FPGA设计中，由于触发器资源丰富，独热编码往往是首选方案。
选择编码方案时需要综合考虑：触发器数量、次态逻辑的复杂度、目标器件的资源特点（FPGA vs ASIC）以及功耗要求。现代EDA工具可以自动进行状态编码优化，但理解各种编码的特点有助于设计者做出合理的初始选择和约束设置。
三、深入分析与讨论
3.1 Mealy型与Moore型的等价转换
Mealy型和Moore型状态机可以相互转换，但转换过程中状态数量可能发生变化。将Mealy型转换为Moore型时，如果同一个状态在不同输入下产生不同的输出，则需要将该状态分裂为多个状态，每个状态对应一种输出值。这可能导致状态数量增加。
例如，一个Mealy型状态机有状态A，在输入X=0时输出0，在输入X=1时输出1。转换为Moore型时，需要将A分裂为A0（输出0）和A1（输出1）两个状态。所有原来转移到A且伴随X=0的转移现在指向A0，伴随X=1的转移指向A1。
将Moore型转换为Mealy型时，状态数量通常不会增加（可能减少），因为Mealy型的输出可以直接响应输入，不需要额外的状态来体现输出变化。但转换后的Mealy型可能在某些情况下产生输出毛刺。
在实际设计中，有时会根据需要混合使用两种模型。例如，状态机的核心控制逻辑使用Moore型以确保输出稳定性，而某些需要快速响应的信号（如握手信号）使用Mealy型以减少延迟。
3.2 状态机设计中的自启动问题
在实际的硬件电路中，由于上电时的不确定状态或运行中的辐射干扰（SEU, Single Event Upset），状态机可能进入设计时未定义的非法状态。自启动（Self-Starting）设计确保状态机能够从任何非法状态自动恢复到合法的状态序列中。
处理非法状态的常见方法：(1) 将所有未使用的状态编码的次态都指向初始状态。这样，无论状态机进入哪个非法状态，都会在下一个时钟周期自动回到初始状态。(2) 使用"看门狗"（Watchdog）定时器监控状态机的运行，如果状态机在某个状态下停留超过预设时间，则强制复位。(3) 在状态转移图中为每个合法状态检查所有可能的输入组合是否都有明确的转移目标。
在FPGA实现中，综合工具可能会优化掉"未使用状态"的处理逻辑（因为这些状态在仿真中永远不会到达）。因此，设计者需要明确添加约束或使用特定的编码方式来确保自启动逻辑不被优化掉。
四、实践案例
4.1 序列检测器设计
设计一个Mealy型序列检测器，检测输入序列中是否出现"1101"模式。当检测到完整的"1101"序列时，输出Z=1。
状态定义：S0（初始状态，等待第一个1）；S1（已接收到"1"）；S2（已接收到"11"）；S3（已接收到"110"）；S4（已接收到"1101"，检测到目标序列）。
状态转移分析：
- S0: X=0 -> S0(Z=0), X=1 -> S1(Z=0)
- S1: X=0 -> S0(Z=0), X=1 -> S2(Z=0)
- S2: X=0 -> S3(Z=0), X=1 -> S2(Z=0)（连续1保持在S2）
- S3: X=0 -> S0(Z=0), X=1 -> S4(Z=1)
- S4: X=0 -> S0(Z=0), X=1 -> S1(Z=0)（检测完成后重新开始）
共5个状态，需要3个触发器。进行状态化简：检查各状态对在相同输入下的输出和次态，确认没有等价状态可以合并。
使用格雷码编码：S0=000, S1=001, S2=011, S3=010, S4=110。根据编码后的状态表推导次态方程和输出方程，使用卡诺图化简后得到组合逻辑表达式，完成电路设计。
4.2 交通灯控制器设计
设计一个十字路口交通灯控制器。主干道（A方向）和支路（B方向）各有一组红、黄、绿灯。控制规则如下：
正常情况下，A方向绿灯通行。当B方向有车辆等待时（传感器信号B_req），A方向绿灯持续至少30秒后变黄，黄灯持续5秒后变红，然后B方向绿灯通行。B方向绿灯持续至少20秒后变黄，黄灯5秒后变红，A方向恢复绿灯。如果B方向没有车辆等待，A方向保持绿灯。
状态定义：A_GREEN（A方向绿灯）、A_YELLOW（A方向黄灯）、B_GREEN（B方向绿灯）、B_YELLOW（B方向黄灯）。这是一个Moore型状态机，输出仅取决于当前状态。
定时器设计：每个状态需要一个计数器来记录停留时间。可以使用一个共享的定时计数器，在不同状态下比较不同的阈值（30秒、5秒、20秒）。
状态转移条件：
- A_GREEN -> A_YELLOW：B方向有车等待 且 A方向绿灯已持续>=30秒
- A_YELLOW -> B_GREEN：黄灯已持续>=5秒
- B_GREEN -> B_YELLOW：B方向绿灯已持续>=20秒
- B_YELLOW -> A_GREEN：黄灯已持续>=5秒
这个设计展示了状态机在实际控制系统中的应用。状态机的每个状态对应交通灯的一种配置，状态转移由定时条件和传感器输入共同决定。
五、常见误区与注意事项
状态图不完备：每个状态在所有可能的输入组合下都必须有明确的转移目标。遗漏某些输入组合的转移会导致综合工具产生意外的行为。建议在状态图中明确标注所有转移，包括"其他情况"的默认转移。
Mealy型输出的异步特性：Mealy型状态机的输出是组合逻辑的直接结果，可能在输入变化后立即改变，无需等待时钟边沿。如果输入信号不稳定或有毛刺，输出也会跟着出现毛刺。在需要稳定输出的场合，可以对Mealy型输出添加输出寄存器（变为Moore型或注册输出）。
状态化简时忽略输出一致性：两个状态等价的前提是在所有输入下的输出都相同。仅检查次态是否相同是不够的——即使次态相同，如果输出不同，两个状态也不能合并。
独热编码的非法状态处理：独热编码中，合法状态只有n个（n个触发器中恰好1个为1），但总共有2^n种可能的编码。大多数编码是非法的。必须确保电路能够从非法状态恢复到合法状态。
状态编码影响可测试性：某些状态编码方案可能使得扫描链（Scan Chain）测试更加复杂。在可测试性设计（DFT）中，通常倾向于使用二进制编码或格雷码编码，以减少扫描链的开销。
六、本章小结
本章全面介绍了同步时序电路和有限状态机的设计方法论。同步时序电路由状态寄存器、次态逻辑和输出逻辑三部分组成，所有状态变化在统一时钟边沿发生，确保了时序的可预测性。Mealy型和Moore型是状态机的两种基本模型，前者输出响应更快但可能不稳定，后者输出稳定但可能需要更多状态。状态图和状态表是描述状态机行为的两种等价工具，各有优势。状态化简通过合并等价状态来减少电路复杂度，隐含表法是系统化的化简方法。状态编码的选择——二进制编码、格雷码编码或独热编码——对电路的面积和速度有直接影响。从需求分析到电路实现的完整设计流程包括：画状态图、状态化简、状态编码、推导逻辑表达式、化简和实现。状态机是数字系统设计的核心范式，掌握这一方法论是成为合格数字设计工程师的必经之路。
七、思考题与练习
设计一个Moore型状态机，检测输入序列中连续3个或更多1的出现。当检测到连续3个1时输出Z=1，否则Z=0。画出状态图和状态表。
将以下Mealy型状态机转换为等价的Moore型状态机。原Mealy型有3个状态S0, S1, S2，输入X，输出Z：S0(X=0)->S0(Z=0), S0(X=1)->S1(Z=0), S1(X=0)->S2(Z=1), S1(X=1)->S0(Z=0), S2(X=0)->S0(Z=0), S2(X=1)->S1(Z=1)。转换后需要多少状态？
使用隐含表法化简以下状态表：
| 当前状态 | X=0 次态/输出 | X=1 次态/输出 |
|---------|-------------|-------------|
| A | D/0 | B/1 |
| B | A/0 | C/1 |
| C | D/0 | B/1 |
| D | D/0 | B/1 |
| E | A/0 | C/0 |
找出所有等价状态对，给出化简后的状态表。
对于一个6状态的状态机，分别使用二进制编码、格雷码编码和独热编码，计算所需的触发器数量。分析每种编码方式下次态逻辑的大致复杂度。
设计一个自动售货机的控制状态机。商品价格为25分，接受5分和10分硬币。当投入金额达到或超过25分时，输出商品并找零（如果需要）。画出状态图并进行化简。
解释为什么在FPGA设计中独热编码通常是首选的状态编码方案，而在ASIC设计中可能更倾向于二进制编码或格雷码编码。
设计一个UART接收器的状态机。UART帧格式：1位起始位（低电平）、8位数据位、1位停止位（高电平）。状态机需要检测起始位、逐位移入数据位、检测停止位并输出接收完成的标志。
讨论状态机设计中的"死锁"问题。什么情况下状态机可能进入死锁？如何通过设计来避免死锁？给出一个具体的例子。