状态机原理及设计实例
状态机原理及设计实例
状态机（Finite State Machine，FSM）是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型，在计算机科学和电子工程领域有着广泛的应用。本文将通过两个具体的FPGA设计实例，帮助读者深入理解状态机的基本原理和设计方法。
前言
状态机全称是有限状态机（Finite State Machine、FSM），也称同步有限状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。本文对状态机相关概念的学习，并使用FPGA设计的状态机实现特定字符串的检测。
一、从一个实例来认识状态机
有这样一个可乐机，需要投入三枚硬币才能吐出一瓶可乐。这就涉及到三个部分：
- 输入：投入一元硬币
- 输出：可乐机吐出可乐/可乐机不吐出可乐
- 状态：投入0/1/2/3枚一元硬币
如下图1所示状态转移图，分为3个状态：IDIE,无投入硬币；ONE,投入一枚硬币；TWO，投入两枚硬币。（投入3枚硬币后，吐出可乐，回到无投入硬币状态）。x/x：左边x为1表示投入硬币,0表示无投入硬币；右边x为0表示可乐机没有吐出可乐，为1 表示吐出可乐。
图1 可乐机状态转移图建立可乐机工程。
图2 可乐机示意图
这里给出波形图。
图3 可乐机波形图Pi_money高电平表示投入硬币，当Pi_money处于高电平时，在下一个时序state发生改变。 Po_cola高电平表示吐出可乐。
状态机描述方式可分为一段式、二段式和三段式。
一段式：整个状态机写到一个always模块里面。在该模块中既描述状态转移，又描述状态的输入和输出。
二段式：用两个always模块来描述状态机。其中一个always模块采用同步时序描述状态转移，另一个模块采用组合逻辑判断状态转移条件，描述状态转移规律及其输出。
三段式：在两个always模块描述方式基础上，使用三个always模块。一个always模块采用同步时序描述状态转移，另一个模块采用组合逻辑判断判断状态转移条件，描述状态转移规律，另一个always模块描述状态输出（可以用组合电路输出，也可以时序电路输出）。
这里采用二段式进行编程描述。
module simple_fsm
(
input wire clk ,
input wire rst_n ,
input wire Pi_money,
output reg Po_cola
);
parameter IDIE = 3'b001;
parameter ONE = 3'b010;
parameter TWO = 3'b100;
reg [2:0] state;
//描述状态转移
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
state <= IDIE;
else case(state)
IDIE: if(Pi_money == 1)
state <= ONE;
else
state <= IDIE;
ONE: if(Pi_money == 1)
state <= TWO;
else
state <= ONE;
TWO: if(Pi_money == 1)
state <= IDIE;
else
state <= TWO;
default:state <= IDIE;
endcase
//判断状态转移条件
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
Po_cola <= 0;
else if((state == TWO) && (Pi_money == 1))
Po_cola <= 1;
else
Po_cola <= 0;
endmodule
建立仿真验证工程。
`timescale 1ns/1ns
module simple_fsm_tb();
reg clk;
reg rst_n;
reg Pi_money;
wire Po_cola;
initial
begin
clk = 1;
rst_n <= 0;
#20
rst_n <= 1;
end
always #10 clk = ~clk;
//随机投入硬币
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
Pi_money <= 0;
else
Pi_money <= {$random} % 2;
wire [2:0] state = simple_fsm_inst.state;
initial
begin
$timeformat(-9,0,"ns",6);//设置时间格式
$monitor("@time %t:Pi_money = %b,state = %b,Po_cola = %b",$time,Pi_money,state,Po_cola);//打印
end
simple_fsm simple_fsm_inst
(
.clk (clk),
.rst_n (rst_n),
.Pi_money(Pi_money),
.Po_cola(Po_cola)
);
endmodule
查看仿真验证。
在第二个时钟信号时，Pi_money处于高电平，表示投入一枚一元硬币，在下个时钟序列，state发生改变，随后一直投入硬币（Pi_money一直为高电平），当state处于“2”状态，继续投入硬币，在下一个时钟序列可乐机吐出可乐，Po_cola为高电平，验证完毕。
二、稍微复杂点的状态机
现在跟上一章的可乐机增加点难度：可乐机现在需要2.5元一瓶。因此假设人现在可以投币的选项为投入0.5元和1元。设计复杂可乐机工程示意图如下：
输入：Pi_money_half表示是否投入0.5元硬币；Pi_money_one表示是否投入1元硬币.
输出：Po_cola表示是否吐出可乐；Po_money表示是否找零。
状态：0、0.5、 1、 1.5、 2、 2.5、 3.
输入端有三种情况，以00、 01、 10分别表示不投硬币、投入0.5元硬币、投入1元硬币；输出端也有三种情况，以00、 10、 11分别表示不出可乐/不找零、出可乐/不找零、出可乐/找零。
构造复杂可乐机的状态转移图。
同样采用二段式进行描述
module complex_fsm
(
input wire clk ,
input wire rst_n ,
input wire Pi_money_half,
input wire Pi_money_one,
output reg Po_money,
output reg Po_cola
);
//独热码定义状态
parameter IDIE = 5'b00001;
parameter HALF = 5'b00010;
parameter ONE = 5'b00100;
parameter ONE_HALF = 5'b01000;
parameter TWO = 5'b10000;
wire [1:0] Pi_money; //定义组合逻辑
reg [4:0] state;
assign Pi_money = {Pi_money_one, Pi_money_half};
//描述状态转移
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
state <= IDIE;
else case(state)
IDIE: if(Pi_money == 2'b01)
state <= HALF;
else if(Pi_money == 2'b10)
state <= ONE;
else
state <= IDIE;
HALF: if(Pi_money == 2'b01)
state <= ONE;
else if(Pi_money == 2'b10)
state <= ONE_HALF;
else
state <= HALF;
ONE: if(Pi_money == 2'b01)
state <= ONE_HALF;
else if(Pi_money == 2'b10)
state <= TWO;
else
state <= ONE;
ONE_HALF: if(Pi_money == 2'b01)
state <= TWO;
else if(Pi_money == 2'b10)
state <= IDIE;
else
state <= ONE_HALF;
TWO: if(Pi_money == 2'b01)
state <= IDIE;
else if(Pi_money == 2'b10)
state <= IDIE;
else
state <= TWO;
default:state <= IDIE;
endcase
//判断状态转移条件
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
Po_cola <= 0;
else if((state == ONE_HALF) && (Pi_money == 2'b10)
||(state == TWO) && (Pi_money == 2'b01)
||(state == TWO) && (Pi_money == 2'b10))
Po_cola <= 1;
else
Po_cola <= 0;
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
Po_money <= 0;
else if((state == TWO) && (Pi_money == 2'b10))
Po_money <= 1;
else
Po_money <= 0;
endmodule
建立仿真
`timescale 1ns/1ns
module complex_fsm_tb();
reg clk;
reg rst_n;
reg Pi_money_half;
reg Pi_money_one;
reg random_data;
wire Po_cola;
wire Po_money;
initial
begin
clk = 1;
rst_n <= 0;
#20
rst_n <= 1;
end
always #10 clk = ~clk;
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
random_data <= 0;
else
random_data <= {$random} % 2;
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
Pi_money_half <= 0;
else
Pi_money_half <= random_data;
always@(posedge clk or negedge rst_n)
if(rst_n == 0)
Pi_money_one <= 0;
else if(random_data == 1)
Pi_money_one <= 0;
else
Pi_money_one <= {$random} % 2;
wire [1:0] Pi_money = complex_fsm_inst.Pi_money;
wire [4:0] state = complex_fsm_inst.state;
initial
begin
$timeformat(-9,0,"ns",6);//设置时间格式
$monitor("@time %t:Pi_money_half = %b,Pi_money_one = %b,state = %b,Po_cola = %b,Po_money = %b",
$time,Pi_money_half,Pi_money_one,state,Po_cola,Po_money);//打印
end
complex_fsm complex_fsm_inst
(
.clk (clk),
.rst_n (rst_n),
.Pi_money_half(Pi_money_half),
.Pi_money_one(Pi_money_one),
.Po_cola(Po_cola),
.Po_money(Po_money)
);
endmodule
仿真结果如上所示，在第一个时钟序列，state为00001,即IDIE状态，当投入一元硬币时，在下一个序列，状态变为ONE(00100)。在第4个序列为TWO，再投入一枚0.5元硬币时，在下个序列，Po_cola为高，吐出可乐，状态返回IDIE状态。在Two状态，投入一元硬币，可乐机在下个序列吐出可乐，也找零，如第8个序列到第9个序列。