Menu Close

状态机概述

在日常生活或工作中希望在特定条件下有步骤的做事,计算机或数字系统同样也类似的需求,这样才能充分利用软硬件系统更好的为人类服务。在特定条件下有步骤执行任务就会用到状态机的概念,那么到底什么是状态机呢?通俗的讲,状态机就是状态转移机制,一般涉及到状态和状态转移两个概念,状态转移一般在特定的条件下发生。在日常生活中状态机几乎无处不在。如手机的运行状态,作息时间表,小学及中学课表,农民的一年四季劳作安排等。下面以手机的运行状态为例介绍常见的状态机描述。

%title插图%num

图1 状态机及状态转移图

在图1中,将手机的运行加以概括,并抽象为状态机的方式进行描述。

1.状态机组成

  • 状态

状态是将事务的发展过程加以抽象和概括,是事务发展的标志性阶段。例如可将手机的运行状态抽象为5个状态,分别为:关机,待机、呼叫、响铃、通话。

  • 状态转移及转移条件

状态转移是指事物的发展过程,是动态的,简单的说就是从一种状态转换到另一种状态所经历或发生的事情。一般状态转移需要一定的条件,条件满足才会从一种状态到另一种状态转换(转移)。状态转移可以是单向的也可以是双向的。图1中手机状态转移描述如下:

  • 关机<–>待机 (双向)

状态转移           转移条件

    • 关机–>待机 ,  按开机键
    • 待机–>关机,   按关机键
  • 待机<–>呼叫(双向)

状态转移           转移条件

    • 待机–>呼叫,    拨号
    • 呼叫–>待机 ,  未接通
  • 待机<–>响铃(双向)

状态转移            转移条件

    • 待机–>响铃          来电
    • 响铃–>待机          未接
  • 响铃–>通话(单向)

状态转移             转移条件

    • 响铃–>通话              接听

2. 状态机分类

  • 状态机按照状态的数量可分为有限状态机和无限状态机。
    • 有限状态机(FSM ,finite state machine)

有限状态机是指状态是有限的,如图1中手机的运行状态只有五种,尽管这五种状态转换是可循环的。在数字逻辑电路设计过程中,有限状态机(FSM)主要用来描述复杂的时序关系,是时序电路设计的重要手段之一。状态机的抽象及数学模型如图1所示,其中输入I是可选的,此时状态机的状态转移是无条件的(只与状态本身有关,与外部输入无关)。

%title插图%num

图2 FSM模型

    • 无限状态机(ISM infinite state machine)

无限状态机的状态是无限多个,如图2,汽车从起点到终点时间和路程上都是连续的,如果以时间的t每一时刻作为一种状态,则将会有无限个状态。同样如果以路程为参考s也是连续的变量,因此状态也是无限的。

%title插图%num

图3 ISM模型

实际上不仅连续域的状态是无限状态,离散域的状态也可以为无限状态机,比如大于0的整数为状态的状态机也是无限状态机。由于有限状态机易于实现,控制方便,而且易于实现数字集成电路,因此在实践中有限状态机获得极其广泛的应用,而无限状态机多用于理论研究,无限状态机经过简化和抽象后可以转化成有限状态机,因此,一般在实际应用中以有限状态机设计为主要目标。无限状态机到有限状态机的转换,如图3,如果假定总路程为20公里,每公里进行一次胎压测试,则把无限的状态变成有限的20个状态。

  •  在数字时序逻辑设计中,按照输出是否和输入直接有关可以分为梅利机(Mealy)和摩尔机(Moore)
    • 梅利机(Mealy)

 系统输出不仅与状态有关,还与输入有直接的关系,这种状态机称为梅利机。

    • 摩尔(Moore)机

系统输出只与状态有关,与输入没有关系,这种状态机称为摩尔机。

%title插图%num

图4  梅利机与摩尔机模型

  • 按照状态机的组织结构可以分为:
    • 一段式状态机
    • 两段式状态机
    • 三段式状态机

有关一段式状态机,两段式状态机及三段式状态机的详细内容,在后续章节中会展开讲解。

3.  状态机常用的表示方法

    • 状态图

如图1所示,将事务的发展过程抽象成状态和状态转移,绘制成状态转移图。

    • 状态转移表

将状态和状态转移以表格的方式呈现,表中分为现态(当前状态),次态(下一个状态),以及现态到次态的转换条件。将图1的状态转化成状态表,如表1

表1

序号 现态 次态 转移条件
1 关机 待机 开机
2 待机 关机 关机
3 待机 呼叫 拨号
4 呼叫 待机 未接通
5 呼叫 通话 接通
6 通话 待机 通话结束
7 待机 响铃 来电
8 响铃 通话 接通

4. 状态机实现的方法

  • 软件设计

软件设计中也经常将事务的发展抽象成状态机,进行软件设计,例如windows,linux等操作系统的调度就是状态机的典型应用。

  • 数字时序电路设计

复杂数字时序电路设计中最常用的方法是将事务的发展抽象成状态机,进行数字系统建模,并用触发器的输出Q表示状态,Qn表示现态,Qn+1表示次态,根据现态输出以及外部输入写出从现态到次态的状态转移真值表,并进行逻辑化简,最终得到代表状态机的数字电路。例如交通灯控制的设计。

  • 硬件描述(HDL)语言描述

在FPGA及数字集成电路设计中,经常会用硬件描述语言进行数字逻辑描述,状态机也是最做常用设计方法,例1中就关于如何将普通的计数器以状态机的方式进行抽象及描述。

5. 状态机的应用

状态机几乎无处不在,特别是在软件设计,数字时序电路设计,FPGA,IC设计等领域被广泛使用。如图4,就是一个典型数字时序电路状态机的模型。在数字时序电路中,由于触发器的翻转是受时钟和输入控制,触发器的输出可以很好的表达状态机的状态,所以许多日常生活中的状态都可以用时序电路描述,我们称这种行为为时序电路状态机建模。本课程主要讨论如何利用Verilog HDL进行状态机建模。

例1: 数字识别,对0~9的十进制计数器的数字4和6进行识别,如果有4或6出现就输出为1,其它数字输出为0;

常规程序设计如下:

module num_recognition
(
    input      clk,
    input      rst,
    output reg num_recog
);
 
reg   [3:0]   count;
 
always@(posedge clk or posedge rst)
if(rst) 
begin
    count <= 0;
    num_recog <= 0;
end
else 
begin
    if(count == 9)
        count <= 0;
    else 
        count <= count + 1;
 
    if( (count == 4) || (count == 6) )
        num_recog <= 1'b1;
    else 
        num_recog <= 1'b0;
end
endmodule

 

例1中的设计很简单,只要学过Verilog语法及计数器设计,很快就能完成。由于上例过于简单,可能都不会想到与状态机有任何关联。其实只要分析就可以看出,该问题完全可以用状态机来描述。以计数器的输出为状态,因此总共有0-9十个状态,状态转换是按顺序无条件的。可以将上面的设计程序改写如例2所示:

例2,将例中的程序修改,用case语句实现计数与数字选择。

module num_recognition
(
    input      clk,
    input      rst,
    output reg num_recog
);
 
reg   [3:0]   count;
 
always@(posedge clk or posedge rst)
if(rst) 
begin
    count <= 0;
    num_recog <= 0;
end
else 
begin
    case(count)
    0,1,2,3,5,7,8:  
    begin
        count <= count + 1;
        num_recog <= 1'b0;
    end
    4,6 :
    begin
        count <= count + 1;
        num_recog <= 1'b1;   
    end
    9:
    begin   
        count <= 0;
        num_recog <= 1'b0;
    end
    default:    
    begin   
        count <= 0;
        num_recog <= 1'b0;
    end
    endcase
end
endmodule

 

从上面的程序可以看出,总共0-9 十个状态,用变量count表示,其中0,1,2,3,5,7,8,9状态时num_recog输出为0,而4,6状态时num_recog输出为1。状态转换除了状态9时,状态返回0以外,其它都是通过 “count <=count+1;” 实现。例2比较容易看出,count的变化与文章中描述的状态机模型相吻合,是简化版的模型(状态转移与输入无关)。那么是否可以认为只有经过case语句描述的过程才是状态机描述呢?答案是否定的,状态机及状态转移是事物抽象的模型,而时序电路中case或if语句描述只是状态机的一种实现手段,因此从这个角度看,例1与例2对状态机的描述是一致的,只是例2对状态的描述更清晰。回顾我们所学过的时序电路部分,可以看出状态机几乎无处不在。

当然状态机的设计还可以通过状态转移表,求出次态的逻辑方程,然后以数字电路的方式完成上例设计,这里不再累述,相关内容可以参考数字电路相关内容。

 

Posted in FPGA, FPGA, Quartus II, Verilog, Verilog, 教材与教案, 文章

发表评论

相关链接