原创 FSM的最佳描述——输出同步的Mealy型状态机

 2008-1-5 08:51  9676 9 11 分类: FPGA/CPLD

在上一篇关于FSM的blog中，我分析了状态机输出同步对状态机运行性能的影响——结论是，输出同步可以带来运行性能的提升。 riple

这一结论是通过分析一个简单的Mealy型FSM得到的。该结论是否也适用于Moore型状态机呢？对于Moore型状态机，输出同步会不会带来更差的响应延时呢？采用HDL，该如何描述Mealy和Moore混合型FSM呢？在这一篇关于FSM优化的blog中，我就尝试给出上述问题的答案。 riple

一、同步Mealy型和Moor型描述的优点 riple

对于Mealy型状态机，输出同步不仅会带来运行性能的提升，还会增加系统的稳定性：防止输出信号出现毛刺，防止组合回路的产生。原理：给Mealy型FSM的输出增加同步寄存器，把异步电路变为同步电路，从而避免了异步电路的缺点，增加了同步电路的优点。结论：在同步电路设计中，Mealy型状态机的输出同步是必不可少的。采用输出同步的Mealy型FSM被称为“同步Mealy”（Synchronous Mealy machine）或“输出流水型Mealy”（Mealy machine with pipelined outputs）。 riple

对于Moore型状态机，不采用输出同步，电路本质上仍然是同步的。原理：Moore型FSM的输出是仅由状态寄存器驱动的，由于状态寄存器是同步的，所以由其驱动的输出逻辑也是同步的。进一步，Moore型FSM的输出逻辑相对于Mealy型FSM的输出逻辑简单了许多，仅仅是对状态寄存器进行译码的组合逻辑。再进一步，通过对Moore型FSM的状态寄存器进行恰当地编码，可以简化对状态寄存器进行译码的组合逻辑，得到更加简单的输出逻辑。结论：给Moore型状态机增加输出同步寄存器，有画蛇添足之嫌。 riple

用HDL描述异步Mealy型和Moore型FSM，可以统一采用三段式： riple

状态寄存器现态赋值（时序逻辑） riple
状态寄存器次态赋值（组合逻辑） riple
输出寄存器次态赋值（组合逻辑） riple

用HDL描述同步Mealy型FSM，需要采用四段式： riple

状态寄存器现态赋值（时序逻辑） riple
状态寄存器次态赋值（组合逻辑） riple
输出寄存器现态赋值（时序逻辑） riple
输出寄存器次态赋值（组合逻辑） riple

比较上述两组公式，第二组公式去除第三项后就可以得到第一组公式。也就是说，从异步Mealy型HDL描述转化为同步Mealy型HDL描述只需要增加一项即可，其余三项可以原封不动地保留。 riple

这样一来，从异步Mealy型FSM的HDL描述风格改到同步Mealy型描述就容易多了。 riple

二、采用同步Mealy型方法描述混合型FSM riple

总结一下前面的内容，接下来就是本篇blog的关键转折点了。Moore型FSM不需要采用输出同步，得到的电路就是近似最佳的，可以延用三段式描述；Mealy型FSM必须采用输出同步，需要采用四段式描述。 riple

那么，如果设计的FSM是Moore和同步Mealy混合型的，我们该如何描述呢？对于已有的Moore和异步Mealy混合型FSM，该如何简单过渡到Moore和同步Mealy混合型呢？再进一步，有没有可以统一描述Moore和同步Mealy型FSM的HDL描述风格呢？如果有的话，记忆起来不就更加方便了吗？ riple

对于上述问题，可以有两种解决方案。 riple

先说第一种，也是最普通，最容易实施的。再次比较上述两组公式，两组公式的前两项完全相同。可以得到这样的结论：对于Moore型、异步Mealy型、同步Mealy型三种FSM，状态寄存器的现态逻辑和次态逻辑描述是完全一致；三者的差异仅存在于输出逻辑的描述上。 riple

结论：输出逻辑的描述是区分三种FSM的唯一信息。所谓的状态机分类，其实是输出逻辑的分类。 riple

有了上述结论，我们就很容易得到第一种解决方案：对于混合型FSM，对所有输出信号进行分类，可以划分成Moore型、异步Mealy型、同步Mealy型三种输出，对三种输出分别进行描述；Moore型输出保持不变；把异步Mealy型输出的描述通过增加一级寄存器转化为同步Mealy型输出；最后合并原有的同步Mealy型和新得到的同步Mealy型描述。 riple

这样一来，就可以得到Moore和同步Mealy混合型FSM的描述。 riple

三、同步Mealy型描述可以统一所有的FSM描述方法 riple

上述的方法很简单，也很清晰，可以解决前述的前两个问题。但是没有解决最后一个：有没有统一的描述方法。 riple

第二种方案就给出了统一的描述方法，也就是本篇blog的题目:输出同步的Mealy型状态机——最佳的FSM描述。 riple

比较Moore型和同步Mealy型FSM，两种电路具有共同的特点：都是同步电路。 riple

同步Mealy型在同步这一点上比Moore型做得更彻底——所有的输出都是寄存器直接驱动。而Moore型在状态寄存器和输出信号之间还会存在一些状态译码组合逻辑。 riple

在前面对Moore型FSM的分析中，我提到：通过恰当地改变Moore型FSM的状态编码，可以简化状态寄存器和输出信号之间的译码逻辑。再进一步，通过增加状态寄存器和恰当的状态编码，可以把状态寄存器和输出信号之间的译码逻辑全部化简掉——也就是说，我们可以得到一种Moore型状态机，其所有输出逻辑是由状态寄存器直接驱动的，状态寄存器与输出信号之间没有任何组合逻辑。 riple

这样的Moore型FSM的输出是最优化的，可以得到最快的输出。这样的Moore型FSM被称为“针对输出优化进行状态编码”的Moore型FSM（Moore machine with output-encoded state assignment）。下文简称“最优”Moore型FSM。 riple

把这样得到的最优Moore型FSM与同步Mealy型比较，可以发现二者具有完全一样的特性：同步电路 + 寄存器直接驱动输出信号。 riple

进一步，通过采用“前瞻”（look-ahead）式描述方法，可以用同步Mealy型方式描述最优Moore型输出。在最优Moore型输出的描述中，输出信号仅是当前状态的函数；与之等价的“前瞻”式的同步Mealy型描述中，输出信号是进入当前状态的多个“前一”状态和输入信号的函数。由于电路原本是Moore型的，而且状态寄存器与输出信号之间不存在任何组合逻辑——就用一根线连接，所以这样等价变换后得到的HDL描述是存在冗余的：输出信号次、现态逻辑与状态寄存器的次、现态逻辑完全一致。这一冗余在经过综合工具处理后可以被优化掉，仅剩下状态寄存器的次、现态逻辑，输出信号直接连接到状态寄存器的输出端口上——经过综合优化的电路又还原为最优Moore型电路。所以，最优Moore和同步Mealy型状态机是同一电路的两种不同描述。 riple

上述变换过程可以表述为：普通Moore型描述 => 最优Moore型描述 <=> 同步Mealy型描述 <=> 最优Moore型描述。 riple

既然最优Moore型和同步Mealy型描述是等价的，而最优Moore型又可以由普通Moore型转化得来，我们就得到第二种解决方案：采用同步Mealy型描述方法描述所有类型的状态机。这样就不存在前述的前两个问题和最后一个问题——Moore型描述和同步Mealy型描述统一了。 riple

这一方法不是我的发明，在StateCAD生成的代码中早已采用了这样的描述方法。对于一个自动代码生成工具来说，采用一种算法描述所有的状态机，并得到最优的代码，无疑是效率最高的方式。对于我们手工编码来说，一种统一的描述方法也是最容易记忆的。 riple

其实，通过掌握前述的同步Mealy型四段式描述方法，可以很容易地掌握Moore型和异步Mealy型描述方法。所以可以说，“四段式”描述是一种统一的FSM描述方法。推荐大家掌握这种描述方法。 riple

四、同步Mealy型和最优Moore型描述的缺点： riple

对于Moore型描述，手工化简输出逻辑得到最优Moore型描述是很繁琐的，如非必要不要采用手工化简方式。采用同步Mealy型描述可以得到等价最优Moore型描述，虽然复杂一些。 riple

由于“前瞻”式描述的复杂性，手工编写FSM最好采用上述的第一种方案，Moore型输出和同步Mealy型输出分开描述；采用StateCAD可以自动得到完备的“前瞻”式描述（这一点是Altera的FSM生成工具不具备的）。 riple

输出最优的Moore和等价的同步Mealy型状态机会引入较多的寄存器，在资源的使用效率上是较低的。所以更加适合FPGA的器件结构，而不适用于CPLD的器件结构（Altera的MAX II系列除外）。 riple

相关资料：State Machine Coding Styles for Synthesis

Coding And Scripting Techniques For FSM Designs With Synthesis-Optimized, Glitch-Free Outputs

Synthesizable Finite State Machine Design Techniques Using the New SystemVerilog 3.0 Enhancements

PS：

引发我思考上述问题的缘由，是半年前和一名同事一起分析StateCAD生成的Verilog代码时，发现对于Moore型FSM描述，StateCAD生成的代码既做到了同步输出，还做到了响应速度最快（没有Moore型输出逻辑寄存引入的一个时钟周期的延迟，其实是与输出编码的Moore型等价的同步Mealy型代码）。这一事实的发现，引发了我对FSM的描述方法的进一步思考。 riple

在这半年里，我查找了很多数电教材。其中《Digital Design: Principles & Practices（Third Edition）》和《Contemporary Logic Design（Second Edition）》两本书里分析了同步Mealy型描述的原理和优点，给出了同步Mealy和Moore型描述的等价原理。但是，这两本书都没有明确建议所有状态机都采用同步Mealy型描述方法（但是强烈反对异步Mealy型描述方法），而是建议根据实际情况选择描述方式。我在上文中建议采用统一描述方法的原因是这一方法可以推而广之得到其他各种描述方法，而且对于FPGA设计工作者来说是最适用的。 riple

此外，对于Xilinx的StateCAD工具的使用，《Advanced FPGA Design：Architecture Implementation and Optimization》一书里虽然没有分析自动生成代码的结构和优势，但是明确建议所有的状态机都采用StateCAD设计，而最终的状态编码和逻辑优化交给后端实现工具进行，这样的设计流程省去了手工编写代码的工作，还避免了手工编写代码风格不一致、容易出错的问题，易于其他设计者理解设计意图。在我看来，这样的设计流程最突出的优点是有利于设计文档和设计代码的实时同步，因为StateCAD设计文件是最好的“可执行文档”（executable document）。我在实际工作中，采用StateCAD已经设计了50多个状态机，对于这一工具的效率和稳定性有很大的信心。 riple

写原创有奖励！2024面包板原创奖励正在进行中