目录
前言
这篇博客主要来借助HDLBits上的几道题目谈一谈有限状态机。
刷题网站: HDLBits
题目路径: HDLBits →Circutis→Finite State Machines
- 分类：
- Moore，输出只和当前状态有关，f=(state)
- Mealy，输出与当前状态以及输入有关，f=(state,input)
- 三段式状态机（状态转化、状态更新、状态输出）；
- 独热码状态机；
- 根据状态转换图、状态表，设计有限状态机。
Moore和Mealy可以互相转换，一般推荐Moore，组合逻辑输出时不用考虑输入，做法是将Mealy有不同输出的单一状态分为两个状态。
下面挑选了五个题目介绍一下，其余源码移步 Github。
1. Design a Moore FSM
solution 1 作者的解
题解：题意容易理解，三位水位传感器（S）作为输入，将水位（level）分成了4档（A，B，C，D），根据上表可以知道不同水位（level）对应的额定流量（FR）。难点在于对于额外流量控制（ΔFR）的判断，当水位降低或者处于最低水位的时候要打开ΔFR。
水位降低这一动作意味着额外流量控制不仅和当前水位有关，还和传感器（S）有关，典型的Mealy FSM，但是题目”Design a Moore FSM“，所以把中间两个水位分成上升而得（1）和下降而得（2）两种情况，总共（A2，B1，B2，C1，C2，D1）六种状态。
module top_module (
input clk,
input reset,
input [3:1] s,
output reg fr3,
output reg fr2,
output reg fr1,
output reg dfr
);
// Give state names and assignments. I'm lazy, so I like to use decimal numbers.
// It doesn't really matter what assignment is used, as long as they're unique.
// We have 6 states here.
parameter A2=0, B1=1, B2=2, C1=3, C2=4, D1=5;
reg [2:0] state, next; // Make sure these are big enough to hold the state encodings.
// Edge-triggered always block (DFFs) for state flip-flops. Synchronous reset.
always @(posedge clk) begin
if (reset) state <= A2;
else state <= next;
end
// Combinational always block for state transition logic. Given the current state and inputs,
// what should be next state be?
// Combinational always block: Use blocking assignments.
always@(*) begin
case (state)
A2: next = s[1] ? B1 : A2;
B1: next = s[2] ? C1 : (s[1] ? B1 : A2);
B2: next = s[2] ? C1 : (s[1] ? B2 : A2);
C1: next = s[3] ? D1 : (s[2] ? C1 : B2);
C2: next = s[3] ? D1 : (s[2] ? C2 : B2);
D1: next = s[3] ? D1 : C2;
default: next = 'x;
endcase
end
// Combinational output logic. In this problem, a procedural block (combinational always block)
// is more convenient. Be careful not to create a latch.
always@(*) begin
case (state)
A2: {fr3, fr2, fr1, dfr} = 4'b1111;
B1: {fr3, fr2, fr1, dfr} = 4'b0110;
B2: {fr3, fr2, fr1, dfr} = 4'b0111;
C1: {fr3, fr2, fr1, dfr} = 4'b0010;
C2: {fr3, fr2, fr1, dfr} = 4'b0011;
D1: {fr3, fr2, fr1, dfr} = 4'b0000;
default: {fr3, fr2, fr1, dfr} = 'x;
endcase
end
endmodule
2. Lemmings4
See also: Lemmings1, Lemmings2, and Lemmings3.
Although Lemmings can walk, fall, and dig, Lemmings aren’t invulnerable. If a Lemming falls for too long then hits the ground, it can splatter. In particular, if a Lemming falls for more than 20 clock cycles then hits the ground, it will splatter and cease walking, falling, or digging (all 4 outputs become 0), forever (Or until the FSM gets reset). There is no upper limit on how far a Lemming can fall before hitting the ground. Lemmings only splatter when hitting the ground; they do not splatter in mid-air.
Extend your finite state machine to model this behaviour.
Falling for 20 cycles is survivable:
Falling for 21 cycles causes splatter:
solution 2
题解：这一题是Lemmings系列的第四题，前面三题就略过，直接看第四题。作者依旧给出了状态转换图，挖、跌落都区分了左右。
未指定位宽的常量，默认32bit，所以定义[31:0] count
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 );
// delcaration
parameter wl=3'b000,wr=3'b001,fl=3'b010,fr=3'b011,dl=3'b100,dr=3'b101,splat=3'b110;
reg [2:0] state, next;
reg [31:0] count;
// state transition logic
always @(*) begin
case(state)
wl:begin
if(~ground) next = fl;
else if(dig) next = dl;
else if(bump_left) next = wr;
else next = wl;
end
wr:begin
if(~ground) next = fr;
else if(dig) next = dr;
else if(bump_right) next = wl;
else next = wr;
end
fl:begin
if(ground) begin
if(count>19) next = splat;
else next = wl;
end
else next = fl;
end
fr:begin
if(ground) begin
if(count>19) next = splat;
else next = wr;
end
else next = fr;
end
dl:begin
if(~ground) next = fl;
else next = dl;
end
dr:begin
if(~ground) next = fr;
else next = dr;
end
splat:begin
next = splat;
end
endcase
end
// state flip-flop DFF
always @(posedge clk, posedge areset) begin
if (areset)
state <= wl;
else if(state == fl || state == fr) begin
state <= next;
count <= count + 1;
end
else begin
state <= next;
count <= 0;
end
end
// output logical
assign walk_left = (state == wl);
assign walk_right = (state == wr);
assign aaah = (state == fl)||(state == fr);
assign digging = (state == dl)||(state == dr);
endmodule
3. Serial receiver with parity checking
See also: Serial receiver and datapath
We want to add parity checking to the serial receiver. Parity checking adds one extra bit after each data byte. We will use odd parity, where the number of 1s in the 9 bits received must be odd. For example, 101001011 satisfies odd parity (there are 5 1s), but 001001011 does not.
Change your FSM and datapath to perform odd parity checking. Assert the done signal only if a byte is correctly received and its parity check passes. Like the serial receiver FSM, this FSM needs to identify the start bit, wait for all 9 (data and parity) bits, then verify that the stop bit was correct. If the stop bit does not appear when expected, the FSM must wait until it finds a stop bit before attempting to receive the next byte.
You are provided with the following module that can be used to calculate the parity of the input stream (It’s a TFF with reset). The intended use is that it should be given the input bit stream, and reset at appropriate times so it counts the number of 1 bits in each byte.
module parity (
input clk,
input reset,
input in,
output reg odd);
always @(posedge clk)
if (reset) odd = 0;
else if (in) odd = ~odd;
endmodule
Note that the serial protocol sends the least significant bit first, and the parity bit after the 8 data bits.
Some timing diagrams
No framing errors. Odd parity passes for first byte, fails for second byte.
solution 3
题解：这题依旧是循序渐进，由前两题铺垫而来：
- 串行接收（低电平开始，传输一字节，高电平结束）；
- 成功接收后，并行输出该字节；
- 接收一字节后，进行奇校验，校验成功并正常结束后，并行输出该字节。
把传输过程用8个状态表示。作者提供了奇校验模块。
由于clocked always中使用了非阻塞复制，状态转换和串行输入同时进行，所以case中判断的是next状态。
module top_module(
input clk,
input in,
input reset, // Synchronous reset
output [7:0] out_byte,
output done
); //
// Modify FSM and datapath from Fsm_serialdata
parameter [3:0] idle = 4'ha,start = 4'hb,stop = 4'hc,err=4'hd,odd_check=4'he;
parameter [3:0] d0=4'h0,d1=4'h1,d2=4'h2,d3=4'h3,d4=4'h4,d5=4'h5,d6=4'h6,d7=4'h7;
reg [3:0] state,next;
reg [7:0] rcv;
always @(posedge clk)begin
if(reset)
state <= idle;
else
state <= next;
case(next)
d0: rcv <= {in,rcv[7:1]};
d1: rcv <= {in,rcv[7:1]};
d2: rcv <= {in,rcv[7:1]};
d3: rcv <= {in,rcv[7:1]};
d4: rcv <= {in,rcv[7:1]};
d5: rcv <= {in,rcv[7:1]};
d6: rcv <= {in,rcv[7:1]};
d7: rcv <= {in,rcv[7:1]};
default: rcv <= rcv;
endcase
end
always @(*)begin
case(state)
idle: next = (~in)? start : idle;
start: next = d0;
d0: next = d1;
d1: next = d2;
d2: next = d3;
d3: next = d4;
d4: next = d5;
d5: next = d6;
d6: next = d7;
d7: next = (odd^in) ? odd_check : err ; // XOR the odd of input byte and parity bit, confirm odd parity
odd_check: next = in ? stop : err ; // high end bit
stop: next = (~in) ? start : idle;
err: next = (~in) ? err : idle;
default: next = idle;
endcase
end
// New: Datapath to latch input bits.
assign done = (state == stop);
assign out_byte = done ? rcv : 8'bx;
// New: Add parity checking.
// record odd of the input 8 bytes [7:0]
wire odd;
parity parity1(
.clk(clk),
.reset(state == idle), // reset when idle
.in(in),
.odd(odd));
endmodule
4.1 Serial two’s complementer (Moore FSM)
You are to design a one-input one-output serial 2’s complementer Moore state machine. The input (x) is a series of bits (one per clock cycle) beginning with the least-significant bit of the number, and the output (Z) is the 2’s complement of the input. The machine will accept input numbers of arbitrary length. The circuit requires an asynchronous reset. The conversion begins when Reset is released and stops when Reset is asserted.
solution 4.1
题意：串行输出二进制补码，低位先输入。补码可以通过取反加1，即低位遇到第一个1后，后续各位取反。
Moore FSM设计4个状态，遇到第一个1前，状态为A，后续状态为B，下标分别表示输入0或1。
module top_module (
input clk,
input areset,
input x,
output z
);
parameter A0 = 2'b00,A1 = 2'b01, B0 = 2'b10, B1 = 2'b11;
reg [1:0] state,next;
always@(*) begin
case(state)
A0: next = x ? A1 : A0;
A1: next = x ? B1 : B0;
B0: next = x ? B1 : B0;
B1: next = x ? B1 : B0;
endcase
end
always@(posedge clk, posedge areset) begin
if(areset)
state <= A0;
else
state <= next;
end
always@(*) begin
case(state)
A0: z = 1'b0;
A1: z = 1'b1;
B0: z = 1'b1;
B1: z = 1'b0;
endcase
end
endmodule
4.2 Serial two’s complementer (Mealy FSM)
The following diagram is a Mealy machine implementation of the 2’s complementer. Implement using one-hot encoding.
solution 4.2
题解：实现的功能与上一题相同，作者给出了状态图，本题使用两个状态，根据当前状态和输入决定输出。
module top_module (
input clk,
input areset,
input x,
output z
);
parameter A = 1'b0,B = 1'b1;
reg state,next;
always@(*) begin
case(state)
A: next = x ? B : A;
B: next = B;
endcase
end
always@(posedge clk, posedge areset) begin
if(areset)
state <= A;
else
state <= next;
end
always@(*) begin
if(areset)
z <= x;
else
case(state)
A: z = x;
B: z = ~x;
endcase
end
endmodule
5 FSM one-hot next-state logic
Consider the state machine shown below, which has one input w and one output z.
For this part, assume that a one-hot code is used with the state assignment ‘y[6:1] = 000001, 000010, 000100, 001000, 010000, 100000 for states A, B,…, F, respectively.
Write a logic expression for the next-state signals Y2 and Y4. (Derive the logic equations by inspection assuming a one-hot encoding. The testbench will test with non-one hot inputs to make sure you’re not trying to do something more complicated).
solution 5
题解：作者给了状态图，很容易根据状态转换的边写出独热码状态机。
module top_module (
input [6:1] y,
input w,
output Y2,
output Y4);
parameter A=1,B=2,C=3,D=4,E=5,F=6;
reg [6:1] state;
// State transition logic: Derive an equation for each state flip-flop.
assign state[A] = w&(y[A]|y[D]);
assign state[B] = (~w)&y[A];
assign state[C] = (~w)&(y[B]|y[F]);
assign state[D] = w&(y[B]|y[C]|y[E]|y[F]);
assign state[E] = (~w)&(y[C]|y[E]);
assign state[F] = (~w)&(y[D]);
// Output logic:
assign Y2 = state[B];
assign Y4 = state[D];
endmodule
Pingback引用通告： HDLBits 刷题总结 | My ignorance