# Finite State Machines (from HDLBits)

## 前言

1. 分类：
1. Moore，输出只和当前状态有关，f=(state)
2. Mealy，输出与当前状态以及输入有关，f=(state,input)
2. 三段式状态机（状态转化、状态更新、状态输出）；
3. 独热码状态机；
4. 根据状态转换图、状态表，设计有限状态机。

Moore和Mealy可以互相转换，一般推荐Moore，组合逻辑输出时不用考虑输入，做法是将Mealy有不同输出的单一状态分为两个状态。

## 1. Design a Moore FSM

### solution 1 作者的解

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

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

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

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

1. 串行接收（低电平开始，传输一字节，高电平结束）；
2. 成功接收后，并行输出该字节；
3. 接收一字节后，进行奇校验，校验成功并正常结束后，并行输出该字节。

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;

// 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

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

## 《Finite State Machines (from HDLBits)》有1个想法

1. Pingback引用通告： HDLBits 刷题总结 | My ignorance