有限状态机
★ 2.1 FSM 的概念
一般来说,典型的数字电路都可以归结为以下两种基本结构,即便是较为复杂的电路也可以对其进行细化,最终肯定可以对应到其中一种结构上。
注意到电路中存在一个名为状态寄存器的特殊结构,该结构存储了电路当前的状态信息。设寄存器位宽为 n,则该电路的状态数量不会超过 \(2^n\),即其状态数量是有限的,因此这种电路结构称为有限状态机(Finate State Machine, FSM)。
顾名思义,有限状态机就是由一系列数量有限的状态组成的循环机制。它是由寄存器和组合逻辑构成的硬件时序电路。状态机通过控制各个状态的跳转来控制流程,使得整个代码看上去更加清晰易懂,在控制复杂流程的时候,状态机有着明显的设计优势。
2.1.1 Moore VS Mealy
有限状态机可分为两种。第一种输出信号只与当前状态有关,输入信号不会直接影响到输出信号,而是与当前状态(简称现态)信号一起生成下一状态(简称次态)信号,在时钟的上升沿之后次态转换为现态,才能影响到输出,这种结构称为摩尔型(Moore)有限状态机;另外一种其输出信号由现态与输入信号共同生成,输入信号可立刻对输出信号产生影响,这种结构称为米莉(Mealy)型有限状态机。
两种结构的有限状态机各有优缺点:Moore 型时序更好,但响应要慢一拍,Mealy 型响应最快,但时序上要差一些。一般来说,如果对电路相应速度要求不是非常苛刻的话,推荐使用 Moore 型有限状态机。
2.1.2 设计 FSM
设计 FSM 的基本步骤可以概括如下:
(1)画出状态转移图
把实际系统进行逻辑抽象,即实际问题转化为设计要求。首先确定电路输入输出引脚;然后根据实际需要列出所有的状态情况,并对状态顺序进行编号;最后根据状态转移条件画出状态转移图。
(2)确定状态编码和编码方式
编码方式的选择对所设计的电路复杂与否起着重要作用,要根据状态数目确定状态编码和编码方式。
(3)给出状态方程和输出方程
列写状态转移表,选定触发器类型,通过卡诺图化简给出状态方程和输出方程。(此步在 FPGA 编程中可省略)
(4)编写 Verilog 代码
按照步骤(1)~(2)编写具有可综合的 Verilog 代码。
★ 2.2 Verilog 实现 FSM
通过分析有限状态机的结构图,我们可以发现其包含三个部分,第一部分为纯组合逻辑,通过现态和输入信号生成次态信号,第二部分为时序逻辑,该时序逻辑非常简单,只包含一个带有复位功能的寄存器单元,复位时现态信号变为初始值,否则在每个时钟的上升沿将次态信号赋值给现态信号。第三部分为组合逻辑,该部分通过现态信号生成各输出信号。
其对应的代码结构为:
FSM.v | |
---|---|
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
|
注意
有的时候状态机内的输出信号不止一种,为了保证低耦合性,避免可能发生的错误,我们建议每一个 always 块内仅进行一个变量的赋值。例如:
always @(*) begin
if (condition) begin
a = 1;
b = 2;
end
else begin
a = 2;
b = 1;
end
end
可以修改为
always @(*) begin
if (condition)
a = 1;
else
a = 2;
end
always @(*) begin
if (condition)
b = 2;
else
b = 1;
end
2.3 一个例子
为了便于理解,我们以一个例子带大家完整体验时序逻辑电路的设计流程。
例子:数字锁
某助教有一个神奇的锁。锁盘上只有两个按键,我们不妨记为 0 和 1。只有按键按照 0100 的顺序按下时才能解锁成功。例如,连续按下 01010 时并不会解锁,但再按下 0 后便会解锁(因为最近的四次输入为 0100)。我们想用一个数字电路判断给定的按键顺序能否解锁。
模块的输入包含一个时钟信号 clk
以及按下的按键编号 in
。由于只有两个按键,所以我们可以根据 in
的高低电平区分按下的按键(例如高电平代表按下 1)。在 clk
的上升沿模块接收一个按键信息,同时输出一个 unlock
信号,当 unlock
信号为高电平时表明最近四次输入的序列可以解锁。
下面是一段波形图示例:
首先来考虑如何确定状态。自然,我们可以根据当前最近的四个输入标识状态,则对应的状态共有 \(2^4=16\) 种。但包含十六个状态的有限状态机无论设计上还是实现上都较为复杂,尽管我们可以通过状态化简消去一部分,但这个过程依然是十分繁琐的。
让我们再次分析这个问题。对于一个给定的输入序列,想要判断其能否开锁,我们只需要关注其最近的输入能否组成 0100 序列。先前我们固定观察最近的四次输入,但实际上有些情况近期是一定不能解锁的,例如序列 1110 至少要再经过三次输入才有可能解锁。
基于这一事实,我们可以只关注输入序列是否包含 0100 及其子序列,即考察最近的输入内容为 0、01、010、0010 四种情况。我们称之为后缀识别。
在最开始没有任何输入时,我们可以引入一个初始状态(不妨记作 - ),用于代表不属于上述四种的情况。接下来当输入一个 0 时,我们就识别到了后缀 0,即可进入下一状态;若输入一个 1,则不属于任何一种后缀,因此依然在初始状态。以此类推,我们就得到了下图所示的状态机。
于是,我们就可以确定下来,这个问题的状态机一共有五个基本状态。我们约定如下的对应关系:
-
\(S_0\):对应 -
-
\(S_1\):对应 0
-
\(S_2\):对应 01
-
\(S_3\):对应 010
-
\(S_4\):对应 0100
初始状态为 \(S_0\),仅在 \(S_4\) 状态时输出解锁信号。由于输出仅和当前状态有关,因此我们可以选择 Moore 型状态机进行设计。五个状态可以使用 3bits 位宽的编码进行处理。接下来我们编写三段式 Moore 型状态机的代码。
首先定义状态变量以及状态名称:
reg [2:0] current_state, next_state;
localparam S0 = 3'd0;
localparam S1 = 3'd1;
localparam S2 = 3'd2;
localparam S3 = 3'd3;
localparam S4 = 3'd4;
接下来编写第一段:状态更新。假定 reset
信号的效果是清除之前所有的输入,恢复初始状态。则按下 reset
后状态机应当跳转到 \(S_0\)。
always @(posedge clk) begin
if (reset)
current_state <= S0;
else
current_state <= next_state;
end
接下来编写第二段:状态转移。根据状态转换图,我们可以编写如下的代码:
always @(*) begin
next_state = current_state;
case (current_state)
S0: begin // -
if (in)
next_state = S0; // -
else
next_state = S1; // 0
end
S1: begin // 0
if (in)
next_state = S2; // 01
else
next_state = S1; // 0
end
S2: begin // 01
if (in)
next_state = S0; // -
else
next_state = S3; // 010
end
S3: begin // 010
if (in)
next_state = S2; // 01
else
next_state = S4; // 0100
end
S4: begin // 0100
if (in)
next_state = S2; // 01
else
next_state = S1; // 0
end
endcase
end
最后,我们编写第三段:输出。
assign unlock = (current_state == S4) ? 1'B1 : 1'B0;
这样就完成了模块的编写。
参考资料
暂无