日志

有限状态机的设计

已有 3946 次阅读| 2014-7-1 13:49

摩尔型有限状态机

摩尔型有限状态机（Moore machine）是输出只由当前状态自己（不直接依赖于输入）确定的有限状态自动机。摩尔型有限状态机的状态图对每个状态包含一个输出信号，相对于米利型有限状态机，它映射机器中的“转移”到输出。（同步型状态机）

米利型有限状态机

米利型有限状态机（Mealy machine）是基于它的当前状态和输入生成输出的有限状态自动机（更精确的叫有限状态变换器）。这意味着它的状态图将为每个转移边包括输入和输出二者。与输出只依赖于机器当前状态的摩尔有限状态机不同，它的输出与当前状态和输入都有关。但是对于每个 Mealy 机都有一个等价的 Moore 机，该等价的 Moore 机的状态数量上限是所对应 Mealy 机状态数量和输出数量的乘积加1（异步型状态机）

有限状态机设计的一般步骤

有限状态机作为设计一个系统的控制模块必用的方法，在设计中对其处理的好坏往往可以决定程序的可移植性；设计步骤主要有以下几个：

（1）逻辑抽象，得出状态转换图就是将给出的一个实际逻辑关系表示为时序逻辑函数，可以用状态转换表来描述，也可以用状态转移图来描述，这就需要：

a、分析给定的逻辑问题，确定输入变量、输出变量以及电路的状态数。通常是取原因或者条件作为输入变量，取结果作为输出变量。

b、定义输入输出逻辑状态的含义，并将电路状态顺序编号。

c、按照要求列出电路的状态转换表或者画出状态转换图

（2）状态化简如果在状态中出现了以下的两种情况，他们在相同的输入下转换到同一种状态去，并得到了一样的输出，则成为等价状态。显然等价状态是重复的，可以合并为一个。电路的状态数越少，存储电路也就越简单。状态化简的目的在于将等价状态尽可能地合并，以得到最简的状态转换图。

（3）状态分配状态分配又称为状态编码。通常有很多编码方法，编码方案选择得当，设计的电路可以简单，反之选择不当，设计的电路就会复杂很多。在实际设计中，须综合考虑电路的复杂度与电路性能之间的折中。在触发器资源丰富的FPGA或者ASIC设计中，采用独热码既可以使电路性能得到保证又可以充分利用其触发器数量多的优势，也可以采用输出编码的状态制定来简化电路结构，并提高状态机的运算速度。

（4）选定触发器的类型并求出状态方程、驱动方程和输出方程

（5）按照方程得出逻辑图用verilog HDL 来描述有限状态机，可以充分发挥硬件描述语言的抽象建模能力，使用always快语句和case if等条件语句及赋值语句就可以方便实现。具体的逻辑简化、逻辑电路到触发器映射都由计算机自动完成。从上述步骤的第二部 4 5 不再需要很多的认为干预，使电路设计工作得到简化，效率也有很大的提高。