目录
写在前面
Finite State Manchines
Lemmings1
Lemmings2
Lemmings3
Lemmings4
Fsm onehot
Fsm ps2
Fsm ps2data
Fsm serial
写在前面
HDLBits 刷题来到了最为重要的一部分---有限状态机,都说 Verilog 设计的精髓就是状态机的设计,可见状态机设计的重要性,通过三十多道的状态机的练习,可以更加熟悉状态机设计的要点,通常都设计为三段式,这样设计的状态机层次清晰且易于设计,时序上更为易懂。以下的解题方法不一定为最佳解决方案,有更好的方法欢迎提出,共同学习,共同进步!
Finite State Manchines
Lemmings1
游戏 Lemmings1 涉及大脑相当简单的小动物。如此简单,以至于我们将使用有限状态机对其进行建模。
在Lemmings 的2D世界中,Lemmings 可以处于两种状态之一:向左走或向右走。如果它撞到障碍物,它会改变方向。特别是,如果旅鼠在左侧被撞倒,它将向右走。如果它被撞到右边,它会向左走。如果它同时在两侧颠簸,它仍然会切换方向。
实现具有两个状态、两个输入和一个输出的 Moore 状态机,以对此行为进行建模。
以下四道题还挺有趣的,以游戏为引入,对其状态进行建模。
module top_module(
input clk,
input areset,
input bump_left,
input bump_right,
output walk_left,
output walk_right
);
//状态机状态定义
parameter LEFT = 0;
parameter RIGHT = 1;
reg state;
reg next_state;
//状态机第一段,状态初始化,时序逻辑非阻塞赋值
always @(posedge clk or posedge areset) begin
if (areset) begin
state <= LEFT;
end
else begin
state <= next_state;
end
end
//状态机第二段,状态跳转,阻塞复制
always @(*) begin
next_state = state;
case(state)
LEFT: begin
if (bump_left) begin
next_state = RIGHT;
end
else begin
next_state = LEFT;
end
end
RIGHT: begin
if (bump_right) begin
next_state = LEFT;
end
else begin
next_state = RIGHT;
end
end
endcase
end
//状态机第三段,结果输出,组合逻辑
assign walk_left = (state==LEFT);
assign walk_right = (state==RIGHT);
endmodule
Lemmings2
除了左右走之外,如果地面消失在他们下面,Lemmings也会摔倒(并且大概会“啊!”)。
除了左右走和颠簸时改变方向外,当地面=0时,旅鼠会摔倒并说“啊啊!当地面重新出现(地面=1)时,旅鼠将恢复沿与坠落前相同的方向行走。在跌倒时被撞到不会影响行走方向,并且与地面消失(但尚未下降)在同一周期中被撞击,或者当地面在仍然下降时重新出现时,也不影响行走方向。
构建一个有限状态机来模拟这种行为。
//`timescale 100ps / 1ps
//
// Stage: Finite_State_Manchines
// Engineer: LQC
// Create Date: 2022/08/06
// Design Name:
// Module Name: top_module
// Description:
// 除了左右走之外,如果地面消失,Lemmings也会摔倒(并且大概会“啊!”)。
//
// 除了左右走和颠簸时改变方向外,当地面=0时,旅鼠会摔倒并说“啊啊!
// 当地面重新出现(地面=1)时,旅鼠将恢复沿与坠落前相同的方向行走。
// 在跌倒时被撞到不会影响行走方向,并且与地面消失(但尚未下降)
// 在同一周期中被撞击,或者当地面在仍然下降时重新出现时,也不影响行走方向。
//
// 构建一个有限状态机来模拟这种行为。
//
module top_module(
input clk,
input areset, // Freshly brainwashed Lemmings walk left.
input bump_left,
input bump_right,
input ground,
output walk_left,
output walk_right,
output aaah
);
//状态机状态定义
parameter LEFT = 0;
parameter RIGHT = 1;
parameter LEFT_AAAH = 2;
parameter RIGHT_AAAH = 3;
reg [1:0] state;
reg [1:0] next_state;
//状态机第一段,初始化状态,时序逻辑非阻塞赋值
always @(posedge clk or posedge areset) begin
if (areset) begin
state <= LEFT;
end
else begin
state <= next_state;
end
end
//状态机第二段,状态跳转,阻塞赋值
always @(*) begin
case(state)
LEFT: begin
if (~ground) begin
next_state <= LEFT_AAAH;
end
else if (bump_left) begin
next_state <= RIGHT;
end
else begin
next_state <= LEFT;
end
end
RIGHT: begin
if (~ground) begin
next_state <= RIGHT_AAAH;
end
else if (bump_right) begin
next_state <= LEFT;
end
else begin
next_state <= RIGHT;
end
end
LEFT_AAAH: begin
if (ground) begin
next_state <= LEFT;
end
else begin
next_state <= LEFT_AAAH;
end
end
RIGHT_AAAH: begin
if (ground) begin
next_state <= RIGHT;
end
else begin
next_state <= RIGHT_AAAH;
end
end
endcase
end
//状态机第三段,结果输出,组合逻辑
assign walk_left = (state==LEFT);
assign walk_right = (state==RIGHT);
assign aaah = ((state==LEFT_AAAH) | (state==RIGHT_AAAH));
endmodule
Lemmings3
除了走路和摔倒之外,Lemmings有时还可以被告知做一些有用的事情,比如挖(当dig=1时开始挖)。如果旅鼠当前在地面上行走(地面=1且未掉落),则可以挖掘,并将继续挖掘,直到到达另一侧(地面=0)。在这一点上,由于没有地面,它会掉下来(啊啊!),然后一旦它再次撞击地面,就继续朝着原来的方向走。与坠落一样,在挖掘时被撞击没有效果,并且在跌倒或没有地面时被告知要挖掘会被忽略。
(换句话说,行走的旅鼠可能会摔倒,挖掘或改变方向。如果满足这些条件中的多个条件,则下降的优先级高于 dig,后者的优先级高于切换方向。
扩展有限状态机以对此行为进行建模。
module top_module(
input clk,
input areset, // Freshly brainwashed Lemmings walk left.
input bump_left,
input bump_right,
input ground,
input dig,
output walk_left,
output walk_right,
output aaah,
output digging
);
//状态申明
parameter LEFT = 8'b00000001; //向左走状态
parameter RIGHT = 8'b00000010; //向右走状态
parameter LEFT_AH = 8'b00000100; //向左走出现没地喊叫
parameter RIGHT_AH = 8'b00001000; //向右走出现没地喊叫
parameter LEFT_DIG = 8'b00010000; //向左走挖掘指令
parameter RIGHT_DIG = 8'b00100000; //向右走挖掘指令
parameter LEFT_DIG_AH = 8'b01000000; //向左走挖掘出现地空
parameter RIGHT_DIG_AH = 8'b10000000; //向右走挖掘出现地空
reg [7:0] state;
reg [7:0] next_state;
//状态机第一段,状态初始化,时序逻辑非阻塞赋值
always @(posedge clk or posedge areset) begin
if (areset) begin
state <= LEFT;
end
else begin
state <= next_state;
end
end
//状态机第二段,状态跳转,阻塞赋值
always @(*) begin
next_state = state;
case(state)
LEFT: begin
if (~ground) begin
next_state = LEFT_AH;
end
else if (dig) begin
next_state = LEFT_DIG;
end
else if (bump_left) begin
next_state = RIGHT;
end
else begin
next_state = LEFT;
end
end
RIGHT: begin
if (~ground) begin
next_state = RIGHT_AH;
end
else if (dig) begin
next_state = RIGHT_DIG;
end
else if (bump_right) begin
next_state = LEFT;
end
else begin
next_state = RIGHT;
end
end
LEFT_AH: begin
if (ground) begin
next_state = LEFT;
end
else begin
next_state = LEFT_AH;
end
end
RIGHT_AH: begin
if (ground) begin
next_state = RIGHT;
end
else begin
next_state = RIGHT_AH;
end
end
LEFT_DIG: begin
if (~ground) begin
next_state = LEFT_DIG_AH;
end
else begin
next_state = LEFT_DIG;
end
end
RIGHT_DIG: begin
if (~ground) begin
next_state = RIGHT_DIG_AH;
end
else begin
next_state = RIGHT_DIG;
end
end
LEFT_DIG_AH: begin
if (ground) begin
next_state = LEFT;
end
else begin
next_state = LEFT_DIG_AH;
end
end
RIGHT_DIG_AH: begin
if (ground) begin
next_state = RIGHT;
end
else begin
next_state = RIGHT_DIG_AH;
end
end
default: begin
next_state = LEFT;
end
endcase
end
//状态机第三段,结果输出,组合逻辑
assign walk_left = (state == LEFT);
assign walk_right = (state == RIGHT);
assign aaah = ((state == LEFT_AH) | (state == RIGHT_AH) | (state == LEFT_DIG_AH) | (state == RIGHT_DIG_AH));
assign digging = ((state == LEFT_DIG) | (state == RIGHT_DIG));
endmodule
Lemmings4
虽然旅鼠可以走路,摔倒和挖掘,但旅鼠并不是无懈可击的。如果旅鼠坠落太久然后撞到地面,它可能会飞溅。特别是,如果一只旅鼠坠落超过20个时钟周期,然后撞击地面,它将飞溅并停止行走,坠落或挖掘(所有4个输出变为0),永远(或直到FSM被重置)。旅鼠在落地之前可以落多远没有上限。旅鼠只在撞击地面时飞溅;它们不会在半空中飞溅。
扩展有限状态机以对此行为进行建模。
module top_module(
input clk,
input areset, // Freshly brainwashed Lemmings walk left.
input bump_left,
input bump_right,
input ground,
input dig,
output walk_left,
output walk_right,
output aaah,
output digging
);
//状态申明
parameter LEFT = 9'b000000001; //向左走状态
parameter RIGHT = 9'b000000010; //向右走状态
parameter LEFT_AH = 9'b000000100; //向左走出现没地喊叫
parameter RIGHT_AH = 9'b000001000; //向右走出现没地喊叫
parameter LEFT_DIG = 9'b000010000; //向左走挖掘指令
parameter RIGHT_DIG = 9'b000100000; //向右走挖掘指令
parameter LEFT_DIG_AH = 9'b001000000; //向左走挖掘出现地空
parameter RIGHT_DIG_AH = 9'b010000000; //向右走挖掘出现地空
parameter SPLATTER = 9'b100000000; //掉落时间过久碰地飞溅
reg [8:0] state;
reg [8:0] next_state;
reg [100:0] fall_cnt;
//状态机第一段,状态初始化,时序逻辑非阻塞赋值
always @(posedge clk or posedge areset) begin
if (areset) begin
state <= LEFT;
end
else begin
state <= next_state;
end
end
//状态机第二段,状态跳转,阻塞赋值
always @(*) begin
next_state = state;
case(state)
LEFT: begin
if (~ground) begin
next_state = LEFT_AH;
end
else if (dig) begin
next_state = LEFT_DIG;
end
else if (bump_left) begin
next_state = RIGHT;
end
else begin
next_state = LEFT;
end
end
RIGHT: begin
if (~ground) begin
next_state = RIGHT_AH;
end
else if (dig) begin
next_state = RIGHT_DIG;
end
else if (bump_right) begin
next_state = LEFT;
end
else begin
next_state = RIGHT;
end
end
LEFT_AH: begin
if (ground && fall_cnt>='d20) begin
next_state = SPLATTER;
end
else if (ground && fall_cnt<='d19) begin
next_state = LEFT;
end
else begin
next_state = LEFT_AH;
end
end
RIGHT_AH: begin
if (ground && fall_cnt>='d20) begin
next_state = SPLATTER;
end
else if (ground && fall_cnt<='d19) begin
next_state = RIGHT;
end
else begin
next_state = RIGHT_AH;
end
end
LEFT_DIG: begin
if (~ground) begin
next_state = LEFT_DIG_AH;
end
else begin
next_state = LEFT_DIG;
end
end
RIGHT_DIG: begin
if (~ground) begin
next_state = RIGHT_DIG_AH;
end
else begin
next_state = RIGHT_DIG;
end
end
LEFT_DIG_AH: begin
if (ground && fall_cnt>='d20) begin
next_state = SPLATTER;
end
else if (ground && fall_cnt<='d19) begin
next_state = LEFT;
end
else begin
next_state = LEFT_DIG_AH;
end
end
RIGHT_DIG_AH: begin
if (ground && fall_cnt>='d20) begin
next_state = SPLATTER;
end
else if (ground && fall_cnt<='d19) begin
next_state = RIGHT;
end
else begin
next_state = RIGHT_DIG_AH;
end
end
SPLATTER: begin
next_state = next_state;
end
default: begin
next_state = LEFT;
end
endcase
end
//对掉落时间计数
always @(posedge clk or posedge areset) begin
if (areset) begin
fall_cnt <= 'd0;
end
else if (state==LEFT_AH || state==RIGHT_AH || state==LEFT_DIG_AH || state==RIGHT_DIG_AH) begin
fall_cnt <= fall_cnt + 'd1;
end
else begin
fall_cnt <= 'd0;
end
end
//状态机第三段,结果输出,组合逻辑
assign walk_left = (state == LEFT);
assign walk_right = (state == RIGHT);
assign aaah = ((state == LEFT_AH) | (state == RIGHT_AH) | (state == LEFT_DIG_AH) | (state == RIGHT_DIG_AH));
assign digging = ((state == LEFT_DIG) | (state == RIGHT_DIG));
endmodule
Fsm onehot
给定具有以下具有 1 个输入和 2 个输出的状态机:
假设此状态机使用单热编码,其中状态[0]到状态[9]分别对应于状态S0到S9。除非另有说明,否则输出为零。
实现状态机的状态转换逻辑和输出逻辑部分(但不是状态触发器)。您将获得状态为当前状态[9:0],并且必须产生next_state[9:0]和两个输出。通过假设一个热编码的检查来推导逻辑方程。(测试平台将使用非一个热输入进行测试,以确保您不会尝试执行更复杂的操作)。
module top_module(
input in,
input [9:0] state,
output [9:0] next_state,
output out1,
output out2
);
assign next_state[0] = (state[0] & ~in) | (state[1] & ~in) | (state[2] & ~in) | (state[3] & ~in) | (state[4] & ~in) | (state[7] & ~in) | (state[8] & ~in) | (state[9] & ~in);
assign next_state[1] = (state[0] & in) | (state[8] & in) | (state[9] & in);
assign next_state[2] = (state[1] & in);
assign next_state[3] = (state[2] & in);
assign next_state[4] = (state[3] & in);
assign next_state[5] = (state[4] & in);
assign next_state[6] = (state[5] & in);
assign next_state[7] = (state[6] & in) | (state[7] & in);
assign next_state[8] = (state[5] & ~in);
assign next_state[9] = (state[6] & ~in);
assign out1 = (state[8] | state[9]);
assign out2 = (state[7] | state[9]);
endmodule
Fsm ps2
PS/2 鼠标协议发送长度为 3 个字节的消息。但是,在连续的字节流中,消息的开始和结束位置并不明显。唯一的迹象是,每个三字节消息的第一个字节总是有位[3]=1(但其他两个字节的位[3]可能是1或0,具体取决于数据)。
我们想要一个有限状态机,当给定一个输入字节流时,它将搜索消息边界。我们将使用的算法是丢弃字节,直到我们看到一个bit[3]=1的字节。然后,我们假设这是消息的字节1,并在收到所有3个字节(完成)后发出消息接收信号。
FSM 应在成功接收每条消息的第三个字节后立即在周期内完成信号。
module top_module(
input clk,
input [7:0] in,
input reset, // Synchronous reset
output done
);
parameter IDLE = 'd0;
parameter BYTE1 = 'd1;
parameter BYTE2 = 'd2;
parameter BYTE3 = 'd3;
reg [1:0] state;
reg [1:0] next_state;
//状态机第一段,初始状态,时序逻辑非阻塞赋值
always @(posedge clk or posedge reset) begin
if (reset) begin
state <= IDLE;
end
else begin
state <= next_state;
end
end
//状态机第二段,状态跳转,阻塞赋值
always @(*) begin
next_state = state;
case(state)
IDLE: begin
if (in[3]) begin
next_state = BYTE1;
end
else begin
next_state = IDLE;
end
end
BYTE1: begin
next_state = BYTE2;
end
BYTE2: begin
next_state = BYTE3;
end
BYTE3: begin
if (in[3]) begin
next_state <= BYTE1;
end
else begin
next_state <= IDLE;
end
end
endcase
end
//状态机第三段,结果输出,组合逻辑
assign done = (state == BYTE3);
endmodule
Fsm ps2data
现在,您已经有了一个状态机,该状态机将识别 PS/2 字节流中的三字节消息,请添加一个数据路径,该数据路径在收到数据包时也会输出 24 位(3 字节)消息(out_bytes[23:16] 是第一个字节,out_bytes[15:8] 是第二个字节,依此类推)。
每当置位完成的信号时,out_bytes都必须有效。您可以在其他时间输出任何内容(即,不在乎)。
例如:
module top_module(
input clk,
input [7:0] in,
input reset,
output [23:0] out_bytes,
output done
);
parameter IDLE = 'd0;
parameter BYTE1 = 'd1;
parameter BYTE2 = 'd2;
parameter BYTE3 = 'd3;
reg [1:0] state;
reg [1:0] next_state;
reg [23:0] byte_rx;
//状态机第一段,初始状态,时序逻辑非阻塞赋值
always @(posedge clk) begin
if (reset) begin
state <= IDLE;
end
else begin
state <= next_state;
end
end
//状态机第二段,状态跳转,阻塞赋值
always @(*) begin
next_state = state;
case(state)
IDLE: begin
if (in[3]) begin
next_state = BYTE1;
end
else begin
next_state = IDLE;
end
end
BYTE1: begin
next_state = BYTE2;
end
BYTE2: begin
next_state = BYTE3;
end
BYTE3: begin
if (in[3]) begin
next_state = BYTE1;
end
else begin
next_state = IDLE;
end
end
endcase
end
//
always @(posedge clk) begin
if (next_state == BYTE1) begin
byte_rx <= {byte_rx[15:0],in};
end
else if (next_state == BYTE2) begin
byte_rx <= {byte_rx[15:0],in};
end
else if (next_state == BYTE3) begin
byte_rx <= {byte_rx[15:0],in};;
end
else begin
byte_rx <= 'd0;
end
end
//状态机第三段,结果输出,组合逻辑
assign done = (state == BYTE3);
assign out_bytes = byte_rx;
endmodule
Fsm serial
在许多(较旧的)串行通信协议中,每个数据字节都与起始位和停止位一起发送,以帮助接收方从位流中分隔字节。一种常见的方案是使用一个起始位 (0)、8 个数据位和 1 个停止位 (1)。当没有传输任何内容(空闲)时,该线也处于逻辑1。
设计一个有限状态机,当给定比特流时,它将识别何时正确接收字节。它需要识别起始位,等待所有8个数据位,然后验证停止位是否正确。如果停止位未按预期出现,则 FSM 必须等到找到停止位后再尝试接收下一个字节。
module top_module(
input clk,
input in,
input reset,
output done
);
//状态机状态申明
parameter IDLE = 12'b000000000001;
parameter START = 12'b000000000010;
parameter DATA_ONE = 12'b000000000100;
parameter DATA_TWO = 12'b000000001000;
parameter DATA_THREE = 12'b000000010000;
parameter DATA_FOUR = 12'b000000100000;
parameter DATA_FIVE = 12'b000001000000;
parameter DATA_SIX = 12'b000010000000;
parameter DATA_SEVEN = 12'b000100000000;
parameter DATA_EIGHT = 12'b001000000000;
parameter STOP = 12'b010000000000;
parameter WAIT = 12'b100000000000;
reg [11:0] state;
reg [11:0] next_state;
//状态机第一段,状态初始化,时序逻辑,非阻塞赋值
always @(posedge clk) begin
if (reset) begin
state <= IDLE;
end
else begin
state <= next_state;
end
end
//状态机第二段,状态跳转,阻塞赋值
always @(*) begin
next_state = state;
case(state)
IDLE: begin
if (~in) begin
next_state = START;
end
else begin
next_state = IDLE;
end
end
START: begin
next_state = DATA_ONE;
end
DATA_ONE: begin
next_state = DATA_TWO;
end
DATA_TWO: begin
next_state = DATA_THREE;
end
DATA_THREE:begin
next_state = DATA_FOUR;
end
DATA_FOUR: begin
next_state = DATA_FIVE;
end
DATA_FIVE: begin
next_state = DATA_SIX;
end
DATA_SIX: begin
next_state = DATA_SEVEN;
end
DATA_SEVEN: begin
next_state = DATA_EIGHT;
end
DATA_EIGHT: begin
if (in) begin
next_state = STOP;
end
else begin
next_state = WAIT;
end
end
WAIT: begin
if (in) begin
next_state = IDLE;
end
else begin
next_state = WAIT;
end
end
STOP: begin
if (in) begin
next_state = IDLE;
end
else begin
next_state = START;
end
end
default: begin
next_state = IDLE;
end
endcase
end
//状态机第三段,结果输出,组合逻辑
assign done = (state==STOP);
endmodule