基于FPGA的有限状态机浅析

  前言:状态机大法好,状态机几乎可以实现一切时序逻辑电路。

有限状态机(Finite State Machine, FSM),根据状态机的输出是否与输入有关,可分为Moore型状态机和Mealy型状态机。Moore型状态机输出仅仅与现态有关和Mealy型状态机不仅与现态有关,也与输入有关,所以会受到输入的干扰,可能会产生毛刺(Glith)的现象,所以我们通常使用的是Moore型状态机。

         状态机的编码,二进制编码(Binary),格雷码编码(Gray-code),独热码(One-hot)。不同的编码方式是防止在状态转移中发生突变,使得状态转移更为稳定,系统更加可靠,但是通常情况下我们直接采用的是二进制进行编码,除非系统对稳定性和状态编码有特殊要求。

         状态机的描述,一段式、二段式、三段式。

一段式状态机,将组合逻辑和时序逻辑混合在一起,这样的写法对于逻辑简单的状态机来说还是可以使用的,但是对于复杂的逻辑就不推荐了,如果状态复杂也会容易出错,而且一个always块中信号太多也不利于维护和修改。

 1 //状态参数声明
 2 parameter     S0    =    4'b0000,
 3             S1    =    4'b0001,
 4             s2    =    4'b0010;
 5 //FSM one segment
 6 reg     [3:0]    state;
 7 always @(posedge clk or negedge rst_n)begin
 8     if(!rst_n)
 9         state <= S0;
10     else begin
11         case(state)
12         S0:
13         S1:
14         S2:
15         .
16         .
17         .
18         default:
19         endcase 
20     end
21 end

两段式状态机也是一种常用的写法,它把组合逻辑和时序逻辑区分出来,第一段负责状态的转移,第二段是组合逻辑赋值,但是这种写法的缺点是,组合逻辑较容易产生毛刺等常见问题,关于组合逻辑较容易产生毛刺原因,下文会提到。

 1 //状态参数声明
 2 parameter     S0    =    4'b0000,
 3             S1    =    4'b0001,
 4             s2    =    4'b0010;
 5 //FSM two segment
 6 reg     [3:0]    pre_state;
 7 reg     [3:0]    next_state;
 8 //--------------------------------------
 9 //FSM one
10 always @(posedge clk or negedge rst_n)begin
11     if(!rst_n)
12         pre_state <= S0;
13     else 
14         pre_state <= next_state;
15 end
16 
17 //FSM two
18 always    @(*)begin
19     case(pre_state)
20     S0:
21     S1:
22     S2:
23     .
24     .
25     .
26     default:;
27     endcase
28 
29 end

三段式状态机就可以较好的解决一段二段的不足,我也是比较推荐的写法,第一段采用时序逻辑负责状态转移,第二段组合逻辑负责数据赋值,第三段时序逻辑负责输出,代码层次清晰,容易维护,时序逻辑的输出解决了两段式写法中组合逻辑的毛刺问题。但是资源消耗会多一些,此外,三段式从输入到输出会比一段式和二段式延迟一个时钟周期。在书写状态机的时候,一定要事先设计好状态转移图,将所有的状态都考虑到,避免状态进入死循环,或者跳到偏离态。

 1 //状态参数声明
 2 parameter     S0    =    4'b0000,
 3             S1    =    4'b0001,
 4             s2    =    4'b0010;
 5 //FSM three segment
 6 //--------------------------------------
 7 //FSM one
 8 always @(posedge clk or negedge rst_n)begin
 9     if(!rst_n)
10         pre_state <= S0;
11     else 
12         pre_state <= next_state;
13 end
14 
15 //FSM two
16 always    @(*)begin
17     case(pre_state)
18     S0:
19     S1:
20     S2:
21     .
22     .
23     .
24     default:;
25     endcase
26 end
27 
28 //FSM three
29 always    @(posedge clk or negedge rst_n)begin
30     if(!rst_n)
31         dout <= 'b0;
32     else begin
33         case(pre_state)
34         S0:    
35         S1:
36         S2:
37         .
38         .
39         .
40         default:;
41         endcase
42     end
43 end

         如下图,我通过一个实例来说明一下状态机的使用。下面是一个序列检测状态转移图,检测是的使1101这个序列,我们给这个序列的检测序列是11101 1101这一串数据。在这个序列检测器中,我们允许使用重复位。也就是说,前一个“1101”最后一位的1可以作为后一个“1101”序列的起始位。如果不允许重复为位,只需要将S4到S2的转移替换成S4到S1即可。

         首先,从输出状态S0开始检测,当S0检测到1时跳到S1,否则跳回S0,S1检测到1状态跳到S2,否则跳回S0,S2检测到0状态跳到S3,否则还停留在S2状态,因为这里我们的检测序列允许重复位,所以S1检测到的1与S2检测到的1保留,不舍弃作为一下组1101的前两位,所以只需要继续检测下一位数据即可。S3、S4的状态一次类推。这里举着个例子是为了说明状态机的状态跳转,在我们实际的设计中这种情况也是会遇到的。

         在使用状态机来描述时序电路的时候,首先应该做的是画出状态转移图,然后根据状态跳转来描述代码,最后便会事半功倍。这段序列检测的代码我也贴出来。当然这只是序列检测的一个应用了,我前面也说了状态机机会可以实现一切的时序电路。如果你遇到实在不好解决的设计,那么这个时候,你就可以考虑一下使用状态机了。

 1 module state(
 2     input                 mclk, 
 3     input                rst_n,
 4     input                din,
 5     output     reg         dout;
 6     );
 7      
 8 parameter         s0 = 3'b000,
 9                 s1 = 3'b001,
10                 s2 = 3'b010,
11                 s3 = 3'b011,
12                 s4 = 3'b100;//状态
13 //此为三段式状态机,还有一段式状态机,二段式状态机            
14 reg [2:0] present_state, next_state;
15 //用摩尔状态机设计1011序列检测器
16 //状态寄存器
17 always @(posedge mclk or negedge rst_n)
18 begin
19     if(!rst_n)
20         present_state <= s0;
21     else 
22         present_state <= next_state;
23 end
24 
25 //状态转换模块
26 always @(*)
27 begin
28     case(present_state)
29     s0: if(din==1)
30             next_state = s1;
31          else 
32             next_state = s0;
33     s1: if(din==0)
34             next_state = s2;
35         else 
36             next_state = s1;
37     s2: if(din==1)
38             next_state = s3;
39         else 
40             next_state = s0;
41     s3: if(din==1)
42             next_state = s4;
43         else 
44             next_state = s2;
45     s4: if(din==0)
46             next_state = s2;
47         else 
48             next_state = s1;
49     default: next_state = s0;
50     endcase
51 end
52 
53 always @(posedge clk or negedge rst_n)begin
54     if(!rst_n)
55         dout <= 1'b0;
56     else if(present_state ==s4)
57         dout <= 1'b1;
58     else
59         dout <= 1'b0;
60 end
61      
62
63 endmodule

         在状态机的设计中,一段式状态机用时序逻辑,二段式状态机第一段用时序逻辑,第二段用组合逻辑,三段式状态机第一段用时序逻辑,第二段用组合逻辑,第三段用时序逻辑。我在设计的时候,尝试把第二段写成时序逻辑,最终结果并没有影响,时序逻辑随时钟变化,组合逻辑是直接赋值,所以在第三段状态机进行输出时,输出结果肯定是稳定的,但是这样会限制fmax。如果用时序逻辑的主频率过高的话,可能不如第二段组合逻辑赋值来的稳定,这里就还需要考虑到时序分析了,暂且不谈。这里还需要提的是使用三段式状态机相较于一段二段式,会延迟一个时钟周期输出,就是因为第三段使用了时序逻辑的缘故。

         既然谈状态机的时候,说到了组合逻辑会产生毛刺的现象,那么这里就顺便整理一下,为什么组合逻辑会产生毛刺,组合逻辑的冒险与竞争分析。

         竞争(Competition)在组合逻辑电路中,某个输入变量通过两条或两条以上的途径传到输出端,由于每条途径延迟时间不同,到达输出门的时间就有先有后,这种现象称为竞争。把不会产生错误输出的竞争的现象称为非临界竞争。把产生暂时性的或永久性错误输出的竞争现象称为临界竞争。

冒险(risk)信号在器件内部通过连线和逻辑单元时,都有一定的延时。延时的大小与连线的长短和逻辑单元的数目有关,同时还受器件的制造工艺、工作电压、温度等条件的影响。信号的高低电平转换也需要一定的过渡时间。由于存在这两方面因素,多路信号的电平值发生变化时,在信号变化的瞬间,组合逻辑的输出有先后顺序,并不是同时变化,往往会出现一些不正确的尖峰信号,这些尖峰信号称为"毛刺"。如果一个组合逻辑电路中有"毛刺"出现,就说明该电路存在冒险

竞争冒险(Competition risk)产生原因:由于延迟时间的存在,当一个输入信号经过多条路径传送后又重新会合到某个门上,由于不同路径上门的级数不同,或者门电路延迟时间的差异,导致到达会合点的时间有先有后,从而产生瞬间的错误输出。

       首先看下面这个电路,使用了两个逻辑门,一个非门和一个与门,本来在理想情况下F的输出应该是一直稳定的0输出,但是实际上每个门电路从输入到输出是一定会有时间延迟的,这个时间通常叫做电路的开关延迟。而且制作工艺、门的种类甚至制造时微小的工艺偏差,都会引起这个开关延迟时间的变化。

         实际上如果算上非门的延迟的话,那么F最后就会产生毛刺。信号由于经由不同路径传输达到某一汇合点的时间有先有后的现象,就称之为竞争,由于竞争现象所引起的电路输出发生瞬间错误的现象,就称之为冒险,所以在设计中我们要注意避免这个现象,最简单的避免方法是尽量使用时序逻辑同步输出。

      这篇状态机和组合逻辑的冒险竞争就聊到这里,下次我们接着说时序逻辑的冒险竞争。

参考资料:百度百科,冒险竞争、《FPGA设计技巧与案例开发详解》、《FPGA数字逻辑设计教程——Verilog》、《深入浅出玩转FPGA》等网络文章。

转载请注明出处:NingHeChuan(宁河川)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

Quantum – NSA最强大的互联网攻击工具

作者 小禾才露尖尖角54 wired最近刊登了一篇详细描述有关Quantum的好文,披露了一些有关NSA Quantum系统的细节,其攻击能力令人印象深刻。 ...

16710
来自专栏CSDN技术头条

Weiflow:微博也有机器学习框架?

本文从开发效率(易用性)、可扩展性、执行效率三个方面,介绍了微博机器学习框架Weiflow在微博的应用和最佳实践。 在上期《基于Spark的大规模机器学习在微博...

2458
来自专栏祝威廉

MLSQL解决了什么问题

MLSQL提供了一套SQL的超集的DSL语法MLSQL,数据处理,模型训练,模型预测部署等都是以MLSQL语言交互,该语言简单易懂,无论算法,分析师,甚至运营都...

802
来自专栏木东居士的专栏

缓慢变化维度

1543
来自专栏大数据和云计算技术

Automatic Management of Data and Computation in Datacenters

image.png 最近在研究数据中心的数据管理和性能优化,看了一篇2010的论文Nectar:Automatic Management of Data and...

30410
来自专栏友弟技术工作室

Redis百亿级Key存储方案

由于工作中原因,最近在做数据缓存的东西。由于机器有限,每天的数据量又很大,考虑到既需要毫秒级的请求返回,又需要保证内存足够使用,自己的方案就是设置redis缓存...

4646
来自专栏菩提树下的杨过

一段oracle中的“复杂”分组统计sql

要求: 呼叫系统(Call Center)每天会有大量的电话进线数据,领导们要查看每天的进线数汇总,并且要求把 每天从上午8点到上午12点以及下午2点到晚上8点...

19210
来自专栏企鹅号快讯

Tensorflow:谷歌的一种深度学习框架/丹炉

懒人阅读:想要傻瓜式体验深度学习的请先绕开TF,可以考虑pytorch、keras。想要真正从事可部署产品研发的童鞋,TF可能是一个绕不开的存在。 写在前面:引...

2427
来自专栏技术专栏

《数据仓库工具箱》- 第三章零售业务中的知识点汇总

维度定义的是谁,什么时候,在哪的问题,作为聚合查询中的查询条件,分组条件,排序条件

872
来自专栏智能算法

TensorFlow Lite在Kika Keyboard中的应用案例分享

『基于 AI 技术变革沟通,让世界沟通更简单』一直是 Kika keyboard 最重要的使命。从2016年开始,Kika 技术团队一直致力于 AI 技术在移动...

1253

扫码关注云+社区