如何设计最优化的状态机.doc

如何设计最优化的状态机
前言：数字电路通常分为组合逻辑电路和时序电路，
组合逻辑电路 outputs = F(current inputs)
时序电路     outputs = F(current inputs,past inputs)
有限状态机就是时序电路的数学抽象，一个有限状态机系统包括inputs ,outputs, states .状态机分为同步状态机（synchronous）和异步状态机(asynchronous),异步状态机由于输出信号不稳定，所以不详细讨论，对绝大多数设计来说，用的最广泛的是同步状态机。下面主要讨论了同步状态机的设计。

一．状态机的基础知识
1．1. moore状态机和mealy状态机的区别：
2．1．1moore状态机输出只依赖于及其的当前状态，与输入信号无关。这是moore状态机的优点。下面是moore状态机的模型：

moore状态机比较容易用数学的方式来分析，因此被更广泛的用在代数状态机理论中（algebraic FSM theory）。

Mealy状态机输出依赖于机器现在的状态和输入的值，如果输入改变，输出可以在一个时钟周期中将发生了改变。其模型如下：

图的说明：state memory :保存现在的状态(current state  s(t) )
          state transistion function :根据现态和输入x(t),s(t+1)来决定下一个状态。
          Output function :根据s(t)和x(t)来决定最后的输出。
Mealy 状态机通常可以有更少的状态变量，因此在工程领域有更为广阔的应用，
状态变量越少，则所需的存储单元就越少。

下面用简单的实例来具体说明两者编程的区别，和综合出来的结果的不同：

Mealy状态机的简单例子：
1．    源程序：
   demo_process:process(clk,reset)
   begin
       if(reset = '1')then
         state    <= s0;
         out1    <= (others=>'0');
       elsif rising_edge(clk) then
         case state is
             when s0 => if(in1 = '1')then
                         state <= s1;
                         out1  <= "1000";
                         end if;
             when s1 => if(in1 = '0')then
                         state <= s2;
                          out1 <= "1001";
                       end if;
             when s2 => if(in1 = '1')then
                         state <= s3;
                         out1 <= "1100";
                       end if;
             when s3 => if(in1 = '0')then
                         state <= s0;
                         out1 <= "1111";
                       end if;
             when others =>
                       null;
             end case;
        end if;
end process;

modelsim仿真结果：

synplify综合结果：

1．模块表示图：

在这张综合图上可以明显得看出红线即input所参与决定的是状态的产生和输出。而且输出out1为了防止输出的波形不好（因为通过组合电路输出的波形不稳定），所以加了一个触发器。
2．门级综合结果（仅作参考）：

其中状态机模块编码采用两个触发器，见下图：

所以如果在语言中没有对状态进行编码，那么综合器会自动将编码方式设为顺序编码。

Moore状态机的简单例子：
1源程序：
  demo_process:process(clk,reset)
  begin
       if(reset = '1')then
            state    <= s0;
            out1        <= (others=>'0');
elsif rising_edge(clk) then
            case state is
                  when s0 => if(in1 = '1')then
                              state <= s1;
                            end if;
                            out1  <= "1000";
                  when s1 => if(in1 = '0')then
                              state <= s2;
                             end if;
                            out1 <= "1001";
                  when s2 => if(in1 = '1')then
                              state <= s3;
                            end if;
                            out1 <= "1100";
                  when s3 => if(in1 = '0')then
                              state <= s0;
                            end if;
                            out1 <= "1111";
              when others =>
                            null;
              end case;
          end if;
end process;

2．Modelsim仿真结果：

3．    ynplfy综合结果：
1．原理图模块：

从图中可以看出红线即输入仅仅参与决定了状态机产生状态。
  2．门级综合结果：（仅作参考）

从以上两种状态机的例子可以看出，同一周期对同样的输入，两种仿真结果一致，只是在综合上有所区别。

1．2 创建状态图或者状态转换表。
设计者通常可以用两种工具来简化状态表的建立过程:状态图和转换表。状态图提供了一种图形化的，易理解的对FSM操作的描述，但限制于相对较小的设计，当设计太复杂而无法创建状态图时，应使用转换表。     

2．2．1 创建状态图
状态图应该从复位状态开始，每一个圈表示一个状态，状态图是有向图，圈内部应标上状态的名称和此状态的输出赋值，两个状态之间的转变通过一个有向线段表示，转变条件应标志在有向线段上面，该条件与时钟的上升沿同步。
  下面是一个简单的图例：

1．2．2 创建转换表
状态图是帮助理解状态之间关系的有效一种方法，然而对于许多状态的大电路，状态会变得凌乱，极难画出可用的形式。这时，普遍采用一种称作转换表的文本描述方式，创建转换表的方法与状态图相同，不同的是转换列在一个表中。
上图的转换表如下：
From state    condition    Next state     Out put      Data operate
State0    In1 = ‘1’    State1    Out1<=”0001”    none
State1    In1 = ‘0’    State2    Out1<=”0010”    none
State2    In1 = ‘1’    State3    Out1<=”0100”      none
State3    none    State4    Out1<=”1000”      none
State4    None    State0    Out1<=”1111”      none

注意：在写状态图或者转换表的时候要坚持互斥原则，离开任何节点的线段上的逻辑表达式必须成对互斥，即没有在离开同一节点不同线段上的两个表达式同时为真的情况，如果两个这样的表达式同时是逻辑1，那么状态机就进入了两个不同的次状态，这是不容许的。
互斥测试的是离开同一节点的两个表达式的逻辑and必须为逻辑0。
1．4 状态的编码方式
    在vhdl原码中是否对状态机编码作出规定并不影响状态机的功能，综合工具提供状态优化器，他可以在综合过程中确定状态编码。
  状态编码主要有5种编码方式：
  1．顺序编码。
  2．格雷码编码。
  3．单热编码（one-hot）。
  4．随机编码。
  5．自动编码（面积最小化）。
   状态机在传统上是按二进制编码的。然而采用Gray编码，相邻状态可减少瞬变的次数。有时不可能在所有状态中使用Gray编码，则应在状态矢量中增加触发器的数量以减少开关的次数。另一种方法是使用one-hot编码，虽然该编码使用的触发器较多，即可减少组合逻辑的使用，在带多个输出且每个输出是几个状态的函数的状态机中更是如此。根据状态机的形式，设计者可在Gray、One-hot或二进制间进行选择。

现在就详细说一下one-hot 状态机：
1．ne-hot编码：s0 = “0001” ; s1 = “0010”; s2 = “0100”; s3 = “1000”;
                每一个状态用掉一个触发器，状态数等于触发器的数目。这就意味着触发器数目增加，而状态译码组合电路被优化掉了。对于寄存器资源丰富的xilinx器件来说，是非常适合的。

2．one-hot 状态机的好处：
     现在的FPGA每一个逻辑块中都包含了一个和多个触发器，对于仅需要触发器的one-hot编码解码来说，提供了很好的条件。下面列举了一些用one-hot 设计的好处:
a)    对寄存器资源丰富xilinx fpga 来说更易于适配和布线。
b)    one-hot状态机是典型的相当快速的状态机。他的速度与状态的个数没有任何关系，仅仅决定于状态变迁到一个特殊状态的这种转换的数量（instead depend only on the number of transitions into a particular state）。
c)    不用担心你会在发现最佳的状态机编码方式。因为其他设计的状态机如果在加入一些 状态或者改变其他一些什么的话，那就可能不再最优了。One-hot 编码方式在所有状态机中是最佳的，最优的。
d)    one-hot 状态机很容易设计。状态图能够直接被画成原理图或者被直接用vhdl语言写出来，而不用编码成状态表。
e)    修改起来简单明了。增加和删掉一些状态或者改变一些敏感量等式能被综合器很容易的执行，而不会影响余下的状态机。
f)    很容易从vhdl 或者 verilog 综合。
g)    比其他一些高性能的状态机没有任何的布线面积的浪费。
h)    能够用静态时序分析的方法很容易的找出危险的不合理的状态机转换路径。

3． 举例说明：
  type STATE_TYPE is (s0, s1, s2, s3);
attribute ENUM_ENCODING: STRING;
attribute ENUM_ENCODING of STATE_TYPE: type is "0001 0010 0100 1000";

signal CS, NS: STATE_TYPE;

begin
  -- build the state flops
  SYNC_PROC: process (clk, reset)
    begin
      if (reset='1') then
        CS <= s0;
      elsif rising_edge(clk) then
        CS <= NS;
      end if;
    end process;

-- state machine
    COMB_PROC: process (CS,in1)
    begin
       case CS is
         when s0 =>out1 <= (others=>'0');
if(in1 = '1')then
                    NS <= s1;
                    out1  <= "1000";
                  end if ;

  when s1 => if(in1 = '0')then
                    NS <= s2;
                     out1 <= "1001";
                  end if;

            when s2 => if(in1 = '1')then
                    NS <= s3;
                    out1 <= "1100";
                  end if;

        when s3 => if(in1 = '0')then
                    NS <= s0;
                    out1 <= "1111";
                  end if;

        when others =>
                  null;
              end case;
end process;
在s0状态里，有一个细节，out1 <= (others=>'0');这句话在if外面，和在if里面的out1  <=
"1000";这句话不会自相矛盾。第一句话是s0状态的输出。而第二句话则是s1状态的输出。

Modelsim仿真结果：

上例输出赋值随着时钟的跳变而赋值，这样在输出时就放了一个触发器。
如果在output中不想加入触发器的话，那么，就可以把输出单独拿出来，输出就直接经过组合逻辑，不经过触发器。
     process(cs)
     begin
          case cs is
               when s0 => out1 <= "0000";
                    when s1 => out1  <= "1000";
                    when s2 =>   out1 <= "1001";
                    when s3 =>   out1 <= "1100";
                  when others => null;
             end case;
     end process;

如果在程序中不对状态进行one-hot编码的话，那么有综合器生成的编码方式只能是顺序编码，或者格雷码，所以尽量在程序中确定编码的格式。
二．状态机的设计步骤：
1．    深入的理解问题（Understand the problem）。用非常严谨的风格去解释问题的描述是非常重要的。对于状态机，你必须搞清楚什么样的输入会产生什么样的输出。

2．    获得一个对状态机的理论性的描述（Obtain an abstract representation of the FSM）。一旦你理解了问题，你必须用一种易于操作的形式表达出来，状态图是一种比较好的表示方法。

3．    对状态机进行优化（Perform state minimization. ）。从上一步过来，通常会导致很多状态，很多状态会有相同的行为描述，这些状态应该被优化成同一个状态。

4．    进行状态编码的赋值（Perform state assignment）。编码方式好坏决定了执行的速度。

5．    选择何种类型的触发器来实现状态机（Choose flip-flop types for implementing the FSM's state），J－K触发器会减少门，但会改变转换表。D触发器是比较简明的实现过程。

6．    实现有限状态机（Implement the finite state machine）。
三．具体实例：
为了说明以上的设计步骤，我们设计并综合一个状态机的来控制一个简单的自动售货机。
下面是怎样控制自动售货机去工作：
当自动售货机收到15分硬币时，它就送出一包口香糖。售货机只有一个口来接收五分的硬币和一角的硬币，而且每次只能有一个硬币投入。一个机械传感器可以指示出这个口中投入的是五分的或是一角的硬币，控制器的输出控制着单包的口香糖通过出物口送到消费者的手里。