K_FSM有限状态机

FPGA

有限状态机的概念

  1. 表示有限个状态以及在这些状态之间转移和动作等行为的数字模型(来自度娘百科)

  2. 有限状态机FSM是一种常用的电路设计方法，可以把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合数字逻辑的工作特点。(来自老师)

  3. 举例:

    　　红绿灯: 红绿灯运作的原理相当简单，从一开始绿灯，经过一段时间后，将变为黄灯，再隔一会儿，就会变成红灯，如此不断反覆。
    fsm1

基本术语概念

  1. 状态（State）指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象必然会满足某些条件 、执行某些动作或者是等待某些事件。
  1. 事件（Event）是指在时间和空间上占有一定位置，能影响有限机状态的那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。
  1. 转换（Transition）指的是两个状态之间的一种关系，表明对象将在第一个状态中执行一定的动作，并将在某个事件发生同时某个特定条件满足时进入第二个状态。
  1. 动作（Action）指的是状态机中可以执行的那些原子操作，所谓原子操作指的是它们在运行的过程中不能被其他消息所中断，必须一直执行下去。
  1. 有限状态机是由寄存器组和组合逻辑构成的硬件时序电路；其状态（即由寄存器组的1和0的组合所构成的有限个状态）只能在同一时钟跳变沿的情况下才能从一个状态转向另一个状态；状态机可用于产生在时钟跳变沿时刻开关的复杂的控制逻辑，是数字逻辑的控制核心。

状态机的结构

FSM在结构上主要包括三部分:

  1. State register (状态寄存器)：记忆状态机当前所处的状态，n个触发器可以记忆2n个状态
  2. Combination logic to generate next state (产生下一个状态的组合逻辑)：根据输入信号和当前状态，决定下一个状态
  3. Output Logic (输出逻辑)：由当前状态和输出信号决定当前状态的输出。

状态机的种类

按照输出逻辑可以将FSM分为:

  1. Mealy状态机
    时序逻辑的输出不仅取决于当前状态，还取决于输入。

  2. Moore状态机
    时序逻辑的输出只取决于当前状态。

fsm2
fsm3

状态机的设计的一般步骤和风格

设计步骤

  1. 逻辑抽象，得出状态转换图
  2. 状态化简
  3. 状态编码
  4. 用Verilog HDL来描述有限状态机，使用always块语句和case（if）等条件语句及赋值语句即可方便实现

设计风格

  1. 单always块
    一段式将状态转移寄存、状态译码和输出放在一个always块中
  2. 两always块
    一个完成状态转移寄存、另一个完成状态译码和输出；

状态的编码

fsm4

Binary、gray-code编码使用最少的触发器，较多的组合逻辑资源，而one-hot编码反之。
另一方面，对于小型设计使用Binary、gray-code更有效，而大型状态机使用one-hot编码更高效。

FPGA设计建议采用独热编码。

状态机设计举例

fsm5

  1. 上面的状态转移图表示了一个四状态的有限状态机，它的同步时钟是Clock,输入信号是 A 和 Reset,输出信号是 K1 和 K2。
    状态的转移只能在同步时钟（Clock）的上升沿时发生，往哪个状态的转移则取决于目前所在的状态和输入的信号（Reset 和 A）。

  2. 设计步骤：
    1) Define module name and I/O port;（定义模块名和输入输出端口）
    2) Define input, output variable or register;（定义输入、输出变量或寄存器）
    3) Define clock and reset Signal ;（定义时钟和复位信号）
    4) Define State variable and state register;（定义状态变量和状态寄存器）
    5) Use clock edge triggered always block to reprsent procedure of state transaction;（用时钟沿触发的always块表示状态转移过程）
    6) Assign Value to state register when reset signal is active;（在复位信号有效时给状态寄存器赋初始值）
    7) Description state transaction, if it meet conditions，state is change from one to another;（描述状态的转换过程：符合条件，从一个状态到另外一个状态，否则留在原状态）
    8) Verify crection of state transaction, it must be comprehensive;（验证状态转移的正确性，必须完整和全面）

  3. 代码示例

1) 一个always块风格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
module  fsm (Clock, Reset, A,  K2, K1);
input Clock, Reset, A;    //定义时钟、复位和输入信号
output K2, K1;        //定义输出控制信号的端口
reg K2, K1;              //定义输出控制信号的寄存器
reg [1:0] state ;       //定义状态寄存器

////////////定义状态变量参数值
parameter   Idle  = 2’b00,  Start = 2’b01,  
            Stop = 2’b10,   Clear = 2’b11;

always @(posedge Clock)
    if (!Reset)
      begin    //定义复位后的初始状态和输出值
        state <= Idle;  K2<=0; K1<=0; 
      end

else
  case (state)
    Idle:  begin 
            if (A)  begin 
                        state <= Start;
                            K1<=0;
                    end
              else       state <= Idle;
           end
    Start: begin 
             if (!A)   state <= Stop;
                 else    state <= Start;
             end
    Stop:  begin   //符合条件进入新状态，否则留在原状态
              if (A)  begin  
                      state <= Clear;
                          K2<= 1; end
           else   state <= Stop;
             end
    Clear: begin 
            if (!A)  begin  
                        state <= Idle;
                            K2<=0;  K1<=1; end
           else   state <= Clear;
          end
   endcase
endmodule 


/*
用独热码表示状态

parameter   Idle     =  4’b1000,  
            Start    =  4’b0100,  
            Stop     =  4’b0010, 
            Clear    =  4’b0001;
*/

2) 两个always块风格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
module  fsm (Clock, Reset, A,  K2, K1);
input Clock, Reset, A;
output K2, K1;
reg K2, K1;
reg [1:0] state, nextstate ;
 
parameter   
Idle     =  2'b00,  
Start    =  2'b01,  
Stop     =  2'b10, 
Clear    =  2'b11;

//----每一个时钟沿产生一次可能的状态变化---- 
always @(posedge Clock)
  begin
     if (!Reset)
            state <= Idle; 
    else
            state <= nextstate; 
  end
//-------------------------------------------

//---- 产生下一状态的组合逻辑 ------     
always @(state or A)
     case (state)
        Idle:  if (A)    
                 nextstate = Start;      
               else  nextstate = Idle;
       Start:  if (!A)  nextstate = Stop;
               else   nextstate = Start;
       Stop:  if (A)  nextstate = Clear;
              else  nextstate = Stop;
       Clear:  if (!A)   nextstate = Idle;
               else   nextstate = Clear;
      default:  nextstate = 2'bxx;
  endcase

//---- 产生输出K1的组合逻辑 --------------
always @(state or Reset or A) 
  if (!Reset) K1=0;
    else
       if (state == Clear && !A)  //从Clear转向 Idle
          K1=1;
       else   K1= 0;        
//--- 产生输出K2的组合逻辑 ---------------
always @(state or Reset or A ) 
   if (!Reset) K2 = 0;
   else
      if (state == Stop && A)  // 从Stop转向 Clear
        K2 = 1;
      else K2 = 0;
//------------------------------------------
endmodule

3) 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
`timescale 1ns/1ns
module t;
   reg a;
   reg clock,rst;
   wire k2,k1;
initial              // initial常用于仿真时信号的给出。
     begin 
       a=0;
       rst = 1;       //给复位信号变量赋初始值
       clock = 0;      //给时钟变量赋初始值
       #22 rst = 0;    //使复位信号有效
       #133 rst = 1;   //经过一个多周期后使复位信号无效
     end
 
always #50 clock = ~clock; //产生周期性的时钟
always @ (posedge clock)   //在每次时钟正跳变沿时刻产生不同的a 
  begin   
    #30 a = {$random}%2;   // 每次a是 0还是1是随机的。
    #(3*50+12);  // a 的值维持一段时间
  end
  
initial
    begin   #100000   $stop;  end   
            //系统任务，暂停仿真以便观察仿真波形。
 
//----------- 调用被测试a'c模块 ----------
 fsm  m(.Clock(clock), .Reset(rst),.A(a),.K2(k2),.K1(k1));    
    
endmodule

  1. 仿真波形
    fsm6

附:序列检测器