4. 状态表压缩技术：状态合并、无关项优化与层次化设计

大家好，欢迎来到状态机性能优化的第四讲。

上一讲我们聊了状态编码对性能的影响。今天的话题更直接——如何让状态机本身变得更小。

你可能会问：状态数量少了，性能自然就上去了，这道理谁都懂。但问题是，怎么在保证功能不变的前提下，把状态数量砍下来？

嗯，这就是我今天要分享的核心：状态表压缩技术。

说白了，就是三招：状态合并、无关项优化、层次化状态机。

---

4.1 状态合并：把长得像的状态捏在一起

先讲最直观的一招——状态合并。

我在项目中遇到过这样一个场景：一个通信协议解析器，光接收状态就写了8个。后来仔细一看，其中3个状态的行为几乎一模一样，只是等待的字节数不同。

这其实很常见。很多工程师写状态机时，习惯性地为每个细微的差异都创建一个新状态。结果状态表越写越臃肿。

状态合并的核心原则：如果两个状态在相同的输入下，产生相同的输出，并且转移到相同的下一个状态，那它们就是等价的，可以合并。

来看一个例子：

// 合并前
State S0: if (cmd == READ)  -> S1, output = FETCH
State S1: if (cmd == READ)  -> S2, output = FETCH
State S2: if (cmd == READ)  -> S3, output = FETCH

// 合并后
State S_READ: if (cmd == READ) -> S_READ, output = FETCH

你想想看，S0、S1、S2这三个状态，输入都是READ，输出都是FETCH，转移目标也相同。那它们本质上就是同一个状态的不同副本而已。

当然，实际项目中很少有这么完美的等价状态。更多时候是部分等价——两个状态在大部分输入下行为一致，只在少数输入下有差异。

这时候，我们可以引入默认转移来处理公共部分，把差异点单独拎出来。

// 部分合并技巧
State S_IDLE:
    default: -> S_IDLE
    if (start) -> S_PROCESS

State S_PROCESS:
    default: -> S_PROCESS
    if (done)  -> S_IDLE, output = COMPLETE
    if (error) -> S_ERROR, output = FAULT

我个人习惯是：先画出完整的状态转移图，然后用等价类划分的方法，把行为相同的状态圈出来。这一步用纸笔做，比用工具更直观。

---

4.2 无关项优化：别让状态机做无用功

第二招，无关项优化。这名字听着有点学术，其实道理很简单——状态机不需要关心所有输入组合。

举个例子。一个简单的按键消抖状态机，它只关心按键是否按下。至于CPU此时在做什么运算、内存地址是多少——这些输入对状态机来说就是无关项。

为什么要利用无关项？

因为状态表的规模，取决于输入变量的数量。每多一个输入变量，状态表行数翻一倍。如果能把这些无关输入标记为"don't care"，状态表就能大幅简化。

我曾经接手过一个同事写的状态机，输入信号有12个，状态表写了400多行。我花了两天时间做无关项分析，发现其中5个输入在大部分状态下根本用不到。优化后，状态表缩减到80行，综合后的逻辑门数减少了60%。

这里要特别提醒一点：硬件实现中，无关项优化效果尤其明显。因为FPGA或ASIC的组合逻辑面积，直接取决于状态转移表达式的复杂度。无关项能让综合工具生成更简洁的逻辑电路。

但在软件实现中，无关项优化的收益相对有限。因为软件状态机通常用switch-case实现，编译器已经做了不少优化。

// 无关项优化示例（硬件描述风格）
// 输入：a, b, c（其中c在状态S0下是无关项）
// 优化前
always @(*) begin
    case (state)
        S0: if (a & b & c) next = S1;  // c在这里是多余的
        S1: if (a | c)     next = S2;
    endcase
end

// 优化后
always @(*) begin
    case (state)
        S0: if (a & b)     next = S1;  // 去掉c
        S1: if (a | c)     next = S2;
    endcase
end

---

4.3 层次化状态机：用"套娃"的思路解决问题

第三招，也是我个人认为最强大的一招——层次化状态机（HSM）。

你想想看，一个复杂系统往往有多个工作模式。每个模式下又有若干子状态。如果全部平铺开来，状态数量会爆炸式增长。

层次化状态机的思路是：把公共行为提取到父状态中，子状态只关注自己的特殊行为。

举个例子。一个通信协议栈，有"空闲"、"连接中"、"已连接"、"断开中"四个大状态。其中"已连接"状态下，又分为"等待数据"、"接收数据"、"发送数据"三个子状态。

如果用平面状态机，你需要为每个子状态都处理"超时"、"错误"等公共事件。但用层次化设计，这些公共事件只需要在父状态中处理一次。

// 层次化状态机伪代码
State CONNECTED:  // 父状态
    entry: start_keepalive_timer()
    exit:  stop_keepalive_timer()
    
    // 公共事件处理
    on timeout: -> DISCONNECTING
    on error:   -> IDLE
    
    // 子状态
    substate WAITING:
        on data_received: -> RECEIVING
    
    substate RECEIVING:
        on packet_complete: -> WAITING
    
    substate SENDING:
        on send_done: -> WAITING

这样做的好处很明显：

• 状态数量减少：公共逻辑只写一次，不用在每个子状态重复
• 可维护性提升：修改公共行为只需改父状态
• 代码复用：子状态可以继承父状态的入口/出口动作

我记得在做一个物联网网关项目时，设备状态机有6个大模式，每个模式下又有5-8个子状态。如果用平面设计，状态总数接近50个。用层次化设计后，核心状态只有15个左右，代码量减少了三分之二。

---

4.4 三种技术的对比与选择

说了这么多，你可能想问：这三种技术到底该用哪个？

我的建议是：组合使用，但各有侧重。

技术	适用场景	效果	实现难度
状态合并	状态行为高度相似	中等	低
无关项优化	输入信号多，但大部分无关	高（硬件）	中
层次化状态机	系统有明确的工作模式分层	高	中高

我个人习惯是：先做层次化设计，再做状态合并，最后用无关项优化收尾。

为什么是这个顺序？

因为层次化设计是从架构层面解决问题，效果最显著。状态合并是在同一层级内做精简。无关项优化则是最后的精细化调整。

---

4.5 实战案例：一个简化版的状态表压缩过程

最后，用一个实际案例来串联今天的内容。

假设我们要设计一个简单的ATM取款机状态机。原始设计有12个状态：

IDLE, CARD_INSERTED, PIN_ENTERING, PIN_VERIFYING, 
MENU, BALANCE_CHECK, WITHDRAW_AMOUNT, WITHDRAW_PROCESSING,
DISPENSING, PRINT_RECEIPT, EJECT_CARD, ERROR

第一步：层次化

我们发现"交易中"这个模式下有多个子状态。于是提取出父状态TRANSACTION，把公共的"超时处理"和"取消操作"放到父状态中。

第二步：状态合并

PIN_ENTERING和WITHDRAW_AMOUNT都是"等待用户输入"的行为，只是输入内容不同。合并为WAITING_INPUT状态，用内部变量区分输入类型。

第三步：无关项优化

在IDLE状态下，只有"插卡"事件有意义。其他所有输入（按键、触摸等）都是无关项，直接忽略。

最终，状态数量从12个压缩到7个，逻辑复杂度降低了40%以上。

---

好了，今天的内容就到这里。状态表压缩不是一蹴而就的，需要你在实际项目中不断积累经验。下次遇到臃肿的状态机，不妨试试这三招，效果立竿见影。