加油站| 如何搞定状态机问题（大疆FPGA逻辑岗A卷）

达尔闻加油站，充分利用你的碎片时间涨知识。

加油站系列是此前达尔闻求职系列的延续，秋招季以来该系列已经分享了众多笔试题解析，覆盖华为硬件逻辑岗、大华硬件岗、海康威视等。今后，达尔闻将继续给大家带来最新鲜的笔试题目解析，通过这种方式查漏补缺，检测水平，补充完善你的知识库。

本期加油站解析题目来源大疆硬件逻辑岗，共1道问答题，涉及知识点包含：状态机问题以及画出状态转移图。

今天解析的题目是大疆FPGA逻辑岗A卷的1道问答题，和状态机相关且是以往较为少见的类型。通过解析这道题，把状态机相关的内容都说全。看完此文，状态机学习绝对不是问题。

2、用moore型状态机实现序列“1101”从右到左的不重叠检测。（注：典型的状态机设计分为moore与mealy两大类，其中mealy状态机的输出不仅与当前状态值有关，而且与当前输入有关；moore状态机的输出仅与当前状态值有关，而与此时的输入无关）（大疆FPGA逻辑岗A卷）

1）请画出状态转移图，图中状态用S0, S1, S2, ...标识

2）针对这个具体设计如何衡量验证的完备性？

解析：该题目是和状态机相关的题目，且有两个小问。问题一定要先明确：第一问是只让画出状态转移图，没说让编写代码，在答题的时候一定要看仔细，时间宝贵千万不要多做无用功；第二问是让衡量验证的完备性，大概就是要评估对状态机验证的好坏。初步明确问题后，就可以细读题干了。

先读题，该题目的主要题干就一句话，后面括号里的内容都是补充解释的。大多数公司出的状态机相关的题目几乎都是根据题目的设定编写RTL代码，而这里却只让画状态转移图。要知道编写状态机的代码一定要先画出状态转移图，这看上去是减少了工作量，其实是出题人挖的一个坑。题干表面上让人感觉是一道简单的序列检测题，其实有三个点需要特别注意：

①要用moore型状态机实现；

②不重叠检测；

③检测序列的顺序，题目中给的序列是“1101”，从右到左检测序列就是“1011”。

以上三个点如果有一个没有关注到，那么一定会出问题的。

首先是第一个点，很多同学只记得课本中有moore型状态机和mealy型状态机这么回事儿，具体有什么区别都忘记了，包括自己在设计状态机的时候都没有关注过这种个之间的不同，概念不懂不要担心，因为题干后的括号给出了解释：mealy状态机的输出不仅与当前状态值有关，而且与当前输入有关；moore状态机的输出仅与当前状态值有关，而与此时的输入无关。不知道大家能从这句话中体会到多少，虽然这是moore型状态机和mealy型状态机最主要的区别，但对于有些同学来说并没有从这句话中得到什么有用的信息，或者还是不知道如何绘制moore型状态机的状态转移图（后面我们会对比着把两种类型都详细说明）。

其次是第二个点，什么是不重叠检测？不重叠的意思是每次检测到的1011序列都是独立的组，不能够重复。例如：有一串序列1011011需要我们检测出1011的个数，而在这串序列中我们找到两个1011，但是第一个的1011和第二个的1011有一个共用的“1”，这就是重复检测了，这是我们本题目中所不允许的。所以当检测序列1011011中1011的个数时只会检测到有一个1011，而不是两个，这就是重复检测和不重复检测的区别。

下面我们按照思考的过程开始详细的解析。

因为状态转移图的画法太多，所以在此之前我们先规定一下状态机的状态转移图该如何表示，下面的这种表示方法对以后的代码编写十分有利。对于状态机的设计，其重点肯定是状态转移图的设计，如图1所示的例子，每个近似椭圆的框表示一个状态（也可以用其他图形表示），每个状态之间都有一个指向的箭头，表示的是状态跳转的过程，箭头上有标注的一组数字，斜杠（/）左边表达的是状态的输入，斜杠（/）右边表达的是状态的输出，结构非常的简单，各状态之间的功能、跳转的条件、输入输出都能够在状态转移图中非常清楚的表达出来。

图1

绘制状态转移图需要知道以下三个要素：

①输入：根据输入可以确定是否需要进行状态跳转以及输出，是影响状态机系统执行过程的重要驱动力；

②输出：根据当前时刻的状态以及输入，是状态机系统最终要执行的动作；

③状态：根据输入和上一状态决定当前时刻所处的状态，是状态机系统执行的一个稳定的过程。

接下来套用上面的总结分析本题的状态转移图是如何绘制的。首先要将题目中的对“1011”序列的检测过程抽象成绘制状态转移图所需要的元素，找出状态转移图所必须的输入、输出和状态分别代对应着哪些部分，详细的分析如下：

①输入：每次输入0或1；

②输出：检测到1011就输出1，未检测到就输出0；

③状态：接收的到值为0，接收的到值为1，接收的到值为10，接收的到值为101，接收的到值为1011。

根据这些抽象出的要素我们就可以绘制状态转移图了，首先我们根据分析的状态数先画出5个状态，如图2所示，每个状态我们取一个状态名（题目中有要求用S0, S1, S2, ...标识）：接收的到值为0的状态我们取名为S0，该状态也成为初始状态；

接收的到值为1的状态我们取名为S1；

接收的到值为10的状态我们取名为S2；

接收的到值为101的状态我们取名为S3；

接收的到值为1011的状态我们取名为S4。

图2

从第一个S0状态开始分析，从初始状态开始进行跳转。如图3所示，在S0状态下有两种跳转情况：一种情况是输入为0，没有任何有用的序列值，状态继续维持在S0；另一种情况是输入为1，序列值变为1，状态跳转到S1。

图3

接着分析S1状态跳转的情况。如图4所示，在S1状态下同样有两种跳转情况：一种情况是输入为0，序列值变为10，状态跳转到S2；另一种情况是输入为1，序列值变为11，状态还是继续维持在S1，相当于是之前输入的1被抛弃，新输入的1进入序列的检测。

   图4

继续分析S2状态跳转的情况。如图5所示，在S2状态下同样有两种跳转情况：一种情况是输入为0，此时序列变为100，所有的值都没用了，状态跳转到初始状态S0；另一种情况是输入为1，序列变为101，状态跳转到S2。

图5

下面该分析S3状态跳转的情况了。如图6所示，在S3状态下依然也有两种跳转情况：一种情况是输入为0，此时序列变为1010，状态回到S2，相当于是之前输入的10被抛弃，新组合成的10进入序列的检测；另一种情况是输入为1，即在S3状态下的输入为1，此时的序列为1011，已经满足了我们题目中的序列检测的要求了，可以有输出了。

图6

所以很多人就有疑问了为什么又多出来一个S4状态呢？所以在绘制状态转移图的时候把最初分析得到的S4状态去掉，实现了所谓的“化简”，变为如图7所示的状态转移图，其实不知这里就是moore型状态机和mealy型状态机的分水岭。有的同学会问到，之前分析的5种状态的状态转移图是错误的吗？我们先继续把5种状态的状态转移图绘制完，再告诉大家答案和产生的原因。

按照上面5种状态的状态转移图来继续分析，S3状态下的第二种情况时虽然满足了1011的序列，但是我们先不输出，而是跳转到S4状态，再继续分析S4状态的跳转情况。如图8所示，在S4状态下依然也有两种跳转情况：一种情况是输入为0，序列变为10110，输出1表示检测到了1011序列，同时状态跳转到S0；另一种情况是输入为1，序列变为10111，也会输出1表示检测到了1011序列，但状态会跳转到S1，因为最后输入的1还可以进行下一次1011序列的检测。

图7

图8

图7和图8这两种状态转移图差别很大但都是对的。因为不要忘记状态机有两种，一种是Moore型状态机，一种是Mealy状态机。仔细回忆前面提到的两种状态机的特点，如果最后的输出只和当前状态有关而与输入无关则称为moore型状态机：图8所表达的状态转移图就是moore型的，因为在S4状态下无论输入是0还是1都已经检测到了1011序列，都会有输出，显然和输入时无关的。如果最后的输出不仅和当前状态有关还和输入有关则称为mealy状态机：图7所表达的状态转移图就是mealy型的。平时大家在绘制状态转移图的时候往往更喜欢把状态的个数化简到最简的状态，也有助于在代码实现的状态编码中节省相应的寄存器资源，所以一直没有注意其中的差别，这里就完全讲明白了，第一问也就完成了。很多时候大家比较头疼状态跳转会有遗漏，这里给大家总结一个小技巧：大家可以观察到，输入的情况有多少种（本题是两种情况，输入0或者1），每个状态的跳转就有多少种情况（每个状态都有两种跳转情况），这样就能够保证不漏掉任何一种状态跳转。

虽然本题目没有要求编写代码，但是作为讲解我们尽可能多补充一些内容，由于篇幅有限，本章中我们只把代码附上，如何根据状态转移图来编写代码也有非常详细的套路，遇到相关题目再详细展开。

moore型状态机的RTL功能代码如下所示：

//----------------------------------------------

01module  moore_fsm(

02     input  wire   sys_clk    ,   //系统时钟50MHz

03     input  wire   sys_rst_n  ,   //全局复位

04     input   wire   data_in    ,   //外部输入的序列

05    

06     output  reg   data_out      //检测到1011序列后的输出信号

07);

08

09//只有5种状态，使用独热码

10parameter S0 =5'b00001;

11parameter S1 =5'b00010;

12parameter S2 =5'b00100;

13parameter S3 =5'b01000;

14parameter S4 =5'b10000;

15

16reg[4:0] state;

17

18//第一段状态机，描述当前状态state如何根据输入跳转到下一状态

19always@(posedge sys_clk  ornegedge sys_rst_n)   

20     if(sys_rst_n ==   1'b0) 

21         state <= S0;

22     else   case(state)              

23                 S0      :   if(data_in ==1'b1)

24                                 state <= S1;

25                             else

26                                 state <= S0;

27                

28                 S1      :   if(data_in ==1'b0)

29                                 state <= S2;

30                             else

31                                 state <= S1;

32                

33                 S2      :   if(data_in ==1'b1)

34                                 state <= S3;

35                             else

36                                 state <= S0;

37                

38                 S3      :   if(data_in ==1'b1)

39                                 state <= S4;

40                             else

41                                 state <= S2;

42                                

43                 S4      :   if(data_in ==1'b1)

44                                 state <= S1;

45                             else

46                                 state <= S0;

47                          

48                 default:     state <= S0;

49             endcase

50

51//第二段状态机，描述当前状态state和输入如何影响输出

52always@(posedge sys_clk  ornegedge sys_rst_n)   

53     if(sys_rst_n ==   1'b0) 

54         data_out <=1'b0;

55     else   if((state == S4 && data_in ==1'b0)||(state == S4 && data_in ==1'b1)) 

56         data_out <=1'b1;

57     else  

58         data_out <=1'b0;   

59        

60endmodule

//----------------------------------------------

代码编写后用Quartus软件综合出的状态转移图如图9所示。

图9

mealy型状态机的RTL功能代码如下所示：

//----------------------------------------------

01module  mealy_fsm(

02     input  wire   sys_clk    ,   //系统时钟50MHz

03     input  wire   sys_rst_n  ,   //全局复位

04     input   wire  data_in    ,   //外部输入的序列

05    

06     output  reg   data_out      //检测到1011序列后的输出信号

07);

08

09//只有4种状态，使用独热码

10parameter S0 =4'b0001;

11parameter S1 =4'b0010;

12parameter S2 =4'b0100;

13parameter S3 =4'b1000;

14

15reg[3:0] state;

16

17//第一段状态机，描述当前状态state如何根据输入跳转到下一状态

18always@(posedge sys_clk  ornegedge sys_rst_n)   

19     if(sys_rst_n ==   1'b0) 

20         state <= S0;

21     else   case(state)              

22                 S0      :   if(data_in ==1'b1)

23                                 state <= S1;

24                             else

25                                 state <= S0;

26                

27                 S1      :   if(data_in ==1'b0)

28                                 state <= S2;

29                             else

30                                 state <= S1;

31                

32                 S2      :   if(data_in ==1'b1)

33                                 state <= S3;

34                             else

35                                 state <= S0;

36                

37                 S3      :   if(data_in ==1'b1)

38                                 state <= S0;

39                             else

40                                 state <= S2;

41                

42                 default:     state <= S0;

43             endcase

44

45//第二段状态机，描述当前状态state和输入如何影响输出

46always@(posedge sys_clk  ornegedge sys_rst_n)   

47     if(sys_rst_n ==   1'b0) 

48         data_out <=1'b0;

49     else   if(state == S3 && data_in ==1'b1)

50         data_out <=1'b1;

51     else  

52         data_out <=1'b0;

53        

54endmodule

//----------------------------------------------

代码编写后用Quartus软件综合出的状态转移图如图10所示。

图10

moore型状态机的Testbench仿真代码如下（mealy型状态机的Testbench仿真代码可根据下面的代码稍微变化即可，这里不再列出）：

//-----------------------------------------------

01module  tb_moore_fsm();

02

03reg     sys_clk;

04reg     sys_rst_n;

05reg     data_in;

06

07wire    data_out;

08

09//初始化系统时钟、全局复位

10initial    begin

11      sys_clk     =1'b1;

12      sys_rst_n <=1'b0;

13      #20

14      sys_rst_n <=1'b1;

15end

16

17//sys_clk:模拟系统时钟，每10ns电平翻转一次，周期为20ns，频率为50MHz

18always#10 sys_clk =~sys_clk;

19

20//data_in:产生输入随机数，模拟序列的输入

21always@(posedge sys_clk ornegedge sys_rst_n)

22      if(sys_rst_n ==1'b0)   

23         data_in <=1'b0;

24      else

25         data_in <={$random}%2;    //取模求余数，产生非负随机数0、1

26    

27//----------------------------------

28wire[4:0] state = moore_fsm_inst.state;   //将RTL模块中的内部信号引入到Testbench模块中进行观察

29

30initialbegin

31$timeformat(-9,0,"ns",6);

32$monitor("@time %t: data_in=%bstate=%b data_out=%b",$time, data_in, state, data_out);

33end

34//-----------------------------------------

35    

36//----------moore_fsm_inst--------------

37 moore_fsm  moore_fsm_inst(

38      .sys_clk   (sys_clk   ),  //input    sys_clk      

39      .sys_rst_n (sys_rst_n ),  //input    sys_rst_n 

40      .data_in   (data_in   ),  //input    data_in   

41               

42      .data_out  (data_out  )   //output   data_out     

43);

44

45endmodule

//-----------------------------------------

我们通过仿真出的波形和“Transcript”界面打印的信息都可以看出我们设计的状态机是符合要求的。

图11

图12

如果题目中说要求重叠检测，其状态转移图如图13所示（RTL功能代码和Testbench仿真代码我们就不给出了，可以自己练习）：

图13

2）第二问是针对上面具体的设计分析如何衡量验证的完备性。也就是要衡量测试的好坏，其中一个重要指标就是覆盖率。因为设计的是状态机，所以如果我们的测试能够证明上面设计的moore型状态机的所有状态是完备的，不会进入死循环和不确定状态，且进入异常状态也能恢复到正常状态就说明该验证的完备性（针对该小问，回答出这些内容即可）。

当然也可以通过ModelSim等仿真工具辅助测试验证的完备性，图14为使用ModelSim做的代码覆盖率的部分截图，需要大家格外注意的是任何覆盖率达到100%并不代表设计的Bug已消除，想了解更多可以参考IC验证相关方面的资料。

图14

下期预告

下一期将对大疆FPGA逻辑岗B卷的问答题进行解析，这道题看上去很简单，其实已经埋下了比较深的坑，需要仔细思考一番才能够做对，还是有点挑战性的。大家可以提前看一下题目，尝试着做一做，详细解析敬请期待……

3、设计一个电路，使用时序逻辑对一个单bit信号进行毛刺滤除操作。高电平或者低电平宽度小于4个时钟周期的为毛刺。用Verilog或者VHDL写出代码。（大疆FPGA逻辑岗B卷）

END

目前，我们正在通过大疆硬件岗和FPGA逻辑岗的题目，为大家带来笔试题的解析，以及知识的补充。如果有想要解析的题目，可以发给达尔闻安排。同时，欢迎加入达尔闻求职技术交流群，进群方式：添加妮姐微信（459888529），并备注求职，即可邀请进群。

达尔闻求职“加油站”系列：

达尔闻 求职“笔试经”系列：

达尔闻 求职“面试经”系列