There were too many chores during the week, so I found an excuse to do some homework on the weekend.
As a result, after watching the game over the weekend, the Dalian team was relegated. I was very sad and found an excuse not to do the questions.
Well, it’s been a decadent week, so it’s a new week, pack up your mood and start again!
(Continued from 2.5Finite State Machine(I))
2.5.14 One-hot FSM [Fsm onehot]
Problem description
Given the following diagram a finite state machine with one input and two outputs:
Assume that the state machine uses one-hot encoding, where state[0] to state[9] correspond to the S0 to S9 states respectively. The output is 0 unless otherwise noted.
Implement the state transition logic and output logic portion of the finite state machine (but not the state flip-flops). The current state is given in state[9:0], and next_state[9:0] and two outputs must be generated. Assuming one-hot encoding, derive the logistic equation.
Code
module top_module(
input in,
input [9:0] state,
output [9:0] next_state,
output out1,
output out2);
parameter S0=0,S1=1,S2=2,S3=3,S4=4,S5=5,S6=6,S7=7,S8=8,S9=9;
\t
assign next_state[S0] = (state[S0] & amp;~in)|(state[S1] & amp;~in)|(state[S2] & amp;~in)|(state[S3] & amp; ~in)|(state[S4] & amp;~in)|(state[S7] & amp;~in)|(state[S8] & amp;~in)|(state[S9] & amp;~in );
assign next_state[S1] = (state[S0] & amp; in)|(state[S8] & amp; in)|(state[S9] & amp; in);
assign next_state[S2] = (state[S1] & amp; in);
assign next_state[S3] = (state[S2] & amp; in);
assign next_state[S4] = (state[S3] & amp; in);
assign next_state[S5] = (state[S4] & amp; in);
assign next_state[S6] = (state[S5] & amp; in);
assign next_state[S7] = (state[S6] & amp; in)|(state[S7] & amp; in);
assign next_state[S8] = (state[S5] & amp;~in);
assign next_state[S9] = (state[S6] & amp;~in);
\t
assign out1 = state[S8] | state[S9];
assign out2 = state[S7] | state[S9];
endmodule
2.5.15 PS/2 packet parser [Fsm ps2]
Problem description
The PS/2 mouse protocol sends messages that are three bytes long; however, the beginning and end of the message are not obvious in the continuous stream of bytes. The only indication is that the first byte of every three-byte message always has bit[3]=1 (but the other two bytes have bit[3] either 1 or 0 depending on the data).
We need a finite state machine that, given an input byte stream, will search for message boundaries. The algorithm we will use is to discard bytes until we see a bit[3]=1, then we assume this is byte 1 of the message, and once all three bytes have been received (completed), signal Notification message reception.
The FSM shall signal completion within the cycle immediately upon successful reception of the third byte of each message.
Some timing diagrams to explain the required behavior
Prompts and status transition diagram
- Although in[7:0] is a byte, FSM has only one input in[3].
- You need 4 states, three of which may have no effect because only one of them requires the done output, and done is only enabled for one cycle for each received message.
Code
module top_module(
input clk,
input [7:0] in,
input reset, // Synchronous reset
output done); //
\t
parameter BYTE1=1,BYTE2=2,BYTE3=3,DONE=0;
reg [1:0] state,next_state;
// State transition logic (combinational)
always@(*) begin
case(state)
BYTE1 : next_state = in[3] ? BYTE2 : BYTE1;
BYTE2 : next_state = BYTE3;
BYTE3: next_state = DONE;
DONE : next_state = in[3] ? BYTE2 : BYTE1;
endcase
end
// State flip-flops (sequential)
always@(posedge clk) begin
if(reset)
state <= BYTE1;
else
state <= next_state;
end
//Output logic
assign done = (state == DONE);
endmodule
2.5.16 PS/2 packet parser and datapath [Fsm ps2data]
Problem description
Now, there is a finite state machine that can recognize three messages in the PS/2 byte stream, and a data channel datapath is added. When the three-byte message is received, the channel will output a 24-bit message.
Whenever the done signal is high, out_bytes should be effectively output, and the output at other times is not important.
Analysis
Based on the previous question, add the output of the loaded data.
Code
module top_module(
input clk,
input [7:0] in,
input reset, // Synchronous reset
output reg [23:0] out_bytes,
output done); //
\t
parameter BYTE1=1,BYTE2=2,BYTE3=3,DONE=0;
reg [1:0] state,next_state;
// State transition logic (combinational)
always@(*) begin
case(state)
BYTE1 : next_state = in[3] ? BYTE2 : BYTE1;
BYTE2 : next_state = BYTE3;
BYTE3: next_state = DONE;
DONE : next_state = in[3] ? BYTE2 : BYTE1;
endcase
end
// State flip-flops (sequential)
always@(posedge clk) begin
if(reset)
state <= BYTE1;
else
state <= next_state;
end
// Output logic
always@(posedge clk) begin
case(state)
BYTE1 : out_bytes[23:16] <= in;
BYTE2 : out_bytes[15:8] <= in;
BYTE3 : out_bytes[7:0] <= in;
DONE : out_bytes[23:16] <= in;
endcase
end
\t
assign done = (state == DONE);
endmodule
2.5.17 Serial receiver [Fsm serial]
Problem description
In many (older) serial communication protocols, each data byte is sent with a start bit and a stop bit to help the receiver separate bytes from the bit stream. A common scheme is to use a start bit of 0, 8 data bits and a stop bit of 1. When no data is transmitted, the line is also at logic 1 (idle).
Design a finite state machine that, when given a bit stream, can recognize when bytes have been received correctly. It needs to identify the start bit, wait for all 8 bits, and then verify that the stop bit is correct. If the stop bit does not appear as expected, the FSM must wait until a stop bit is found before trying to receive the next byte.
Timing diagram example
Analysis
Note that when the state transitions to ERROR, if the bit at the input is still low, it does not mean that the next start bit has been found, but that the start bit should be found again after the next idle state.
According to the understanding of the question, five states of idle, start, read, error, and done are set up. The transferred parameters mainly involve the current input bit in and the cntBytes used to calculate the number of data bits. The specific state transfer situation can be based on the figure below.
State transition diagram
Code
module top_module(
input clk,
input in,
input reset, // Synchronous reset
output done
);
parameter IDLE=0,START=1,READ=2,ERROR=3,DONE=4;
reg [2:0] state,next_state;
reg [3:0] cntBytes;
\t
always@(posedge clk) begin
if(reset)
state <= IDLE;
else
state <= next_state;
end
\t
always@(*) begin
case(state)
IDLE : next_state = in ? IDLE : START;
START: next_state = READ;
READ :
if(cntBytes<8)
next_state = READ;
else
next_state = in ? DONE : ERROR;
ERROR : next_state = in ? IDLE : ERROR;
DONE : next_state = in ? IDLE : START;
endcase
end
\t
always@(posedge clk) begin
case(next_state)
START : cntBytes <= 0;
READ : cntBytes <= cntBytes + 1;
default : cntBytes <= cntBytes;
endcase
end
\t
assign done = (state==DONE);
endmodule
2.5.18 Serial receiver and datapath [Fsm serialdata]
Problem description
Based on the previous question, a finite state machine has been obtained that can identify when the data bytes can be received correctly in the serial bit stream, and add a data path to output the correctly received data bytes. out_byte must be valid when done=1, and its value does not matter at other times.
It is important to note that serial protocols send the least significant bits of data first.
Tip Serial bit streams need to be shifted one bit at a time and then read out in parallel.
Code
module top_module(
input clk,
input in,
input reset, // Synchronous reset
output [7:0] out_byte,
output done
);
parameter IDLE=0,START=1,READ=2,ERROR=3,DONE=4;
reg [2:0] state,next_state;
reg [3:0] cntBytes;
\t
always@(posedge clk) begin
if(reset)
state <= IDLE;
else
state <= next_state;
end
\t
always@(*) begin
case(state)
IDLE : next_state = in ? IDLE : START;
START: next_state = READ;
READ :
if(cntBytes<8)
next_state = READ;
else
next_state = in ? DONE : ERROR;
ERROR : next_state = in ? IDLE : ERROR;
DONE : next_state = in ? IDLE : START;
endcase
end
\t
always@(posedge clk) begin
case(next_state)
START : cntBytes <= 0;
READ : cntBytes <= cntBytes + 1;
default : cntBytes <= cntBytes;
endcase
end
\t
always@(posedge clk) begin
case(state)
START : out_byte[7] <= in;
READ: begin
if(cntBytes<8) begin
out_byte = out_byte >> 1;
out_byte[7] <= in;
end
end
endcase
end
\t
assign done = (state==DONE);
endmodule
2.5.19 Serial receiver with parity checking [Fsm serialdp]
Problem description
We want to add parity checking in the serial receiver. Parity adds an extra bit after each data byte. We will use odd parity where 1 out of the 9 bits received must be odd, e.g. 101001011 satisfies and 001001011 does not.
Change the FSM and datapath so that a successful reception is considered when only one byte is received correctly and its parity passes. Like the previous two questions, this FSM also needs to identify the start bit, wait for all nine (data 8 bits + parity 1 bit), and then verify that the stop bit is correct. If it is found that the stop bit does not appear as expected, the FSM needs to wait until the stop bit is found and try again to receive the next byte.
You can use the following module to calculate parity of the input stream (TFF with reset bit).
module parity(
input clk,
input reset,
input in,
output reg odd
);
always@(posedge clk) begin
if(reset) odd<=0;
else if (in) odd<= ~odd;
end
endmodule
Note that the serial protocol sends the least significant bit first and the odd parity bit after 8 data bits.
Code
module parity (
input clk,
input reset,
input in,
output reg odd);
always @(posedge clk)
if (reset) odd <= 0;
else if (in) odd <= ~odd;
endmodule
module top_module(
input clk,
input in,
input reset, // Synchronous reset
output reg [7:0] out_byte,
output done
);
parameter IDLE=0,START=1,READ=2,CHECK=3,ERROR=4,DONE=5;
reg [3:0] state,next_state,cnt;
wire start,odd;
reg checked,rst;
//
parity oddcheck(.clk(clk),.reset(rst|reset),.in(in),.odd(odd));
//
always@(posedge clk) begin
if(reset)
state <= IDLE;
else
state <= next_state;
end
\t
always@(*) begin
case(state)
IDLE : next_state = in ? IDLE : START;
START: next_state = READ;
READ : next_state = (cnt==7) ? CHECK : READ;
CHECK : next_state = in ? DONE : ERROR;
ERROR : next_state = in ? IDLE : ERROR;
DONE : next_state = in ? IDLE : START;
endcase
end
\t
always@(posedge clk) begin
case(state)
START: cnt <= 0;
READ: cnt <= cnt + 1;
default: cnt<=cnt;
endcase
end
\t
always@(*) begin
case(next_state)
START: rst <= 1;
default: rst <= 0;
endcase
end
\t
always@(posedge clk) begin
case(next_state)
DONE : checked <= odd;
default : checked<=checked;
endcase
end
\t
always@(posedge clk) begin
case(state)
START : out_byte[7] <= in;
READ: begin
if(cnt<7) begin
out_byte = out_byte >> 1;
out_byte[7] <= in;
end
end
endcase
end
assign done = (state == DONE) & amp; checked;
endmodule
I have really been pondering this question for a long time. It was mainly stuck on the rst (ie, the reset of the parity check module) signal. At first, I used non-blocking assignment. It was not until I re-ordered the timing diagram that I discovered it. It was a problem with the parity check module. I checked it again and finally determined that the problem was in the part of rst. The overall idea is actually not much changed from the previous question, except that there is an additional verification state after reading in. The 9 bits composed of 8 bits of data and 1 bit of checksum are obtained by the parity check module and the checked signal is high level. When it is in the DONE state at the same time, the done signal is set to high level.
2.5.20 Sequence recognition [Fsm hdlc]
Problem description
Synchronous HDLC framing involves decoding a continuous stream of data bits to find the beginning and end of the indicated frame (packet). When you see exactly 6 consecutive 1’s in a row (i.e., 01111110), it’s a flag indicating a frame boundary. To avoid accidentally including start or end flags in the data stream, the sender inserts a 0 after every 5 consecutive 1s, and the receiver needs to detect and discard this bit. And when 7 or more consecutive 1s appear, we also need to send an error signal.
Create a finite state machine to recognize these three sequences:
- 0111110: Interpolated 0s in the signal need to be discarded (disc)
- 01111110: Mark the beginning or end of the frame (flag)
- 01111111…: Error frame (7 or more 1’s in a row) (err)
When the FSM is reset it should be in the same state as when the previous input was 0.
Here are some examples of timing diagrams illustrating the required operations:
State transition diagram
The prompt in the question gives a ten-state finite state machine as shown below:
This state transition diagram is also very clear and can be written directly.
Code
module top_module(
input clk,
input reset, // Synchronous reset
input in,
output disc,
output flag,
output err);
\t
parameter NONE=0,ONE=1,TWO=2,THREE=3,FOUR=4,FIVE=5,SIX=6,ERROR=7,DISCARD=8,FLAG=9;
reg [3:0] state,next_state;
\t
always@(posedge clk) begin
if(reset)
state <= NONE;
else
state <= next_state;
end
\t
always@(*) begin
case(state)
NONE : next_state = in ? ONE : NONE;
ONE : next_state = in ? TWO : NONE;
TWO : next_state = in ? THREE : NONE;
THREE : next_state = in ? FOUR : NONE;
FOUR : next_state = in ? FIVE : NONE;
FIVE : next_state = in ? SIX : DISCARD;
SIX : next_state = in ? ERROR : FLAG;
ERROR : next_state = in ? ERROR : NONE;
DISCARD : next_state = in ? ONE : NONE;
FLAG : next_state = in ? ONE : NONE;
endcase
end
\t
assign disc = (state == DISCARD);
assign flag = (state == FLAG);
assign err = (state == ERROR);
\t
endmodule
2.5.21 Q8:Design a Mealy FSM [Exams/ece241 2013 q8]
Problem description
Implement a Mealy class finite state machine to recognize the sequence “101” in the input signal x. The FSM should have an output signal z. When a 101 sequence is detected, this signal should be set to 1. At the same time, the FSM should also have an active low asynchronous reset function. It is required that there can only be 3 states in the state machine, and the finite state machine should be able to recognize overlapping sequences.
Analysis
It is required to use only three states, so the three states of IDLE, ONE, and TWO are set to represent the idle state respectively. The detected input is in the 1 state, and the detected input is in the 0 state.
The idle state is the state when reset or no input of 1 is detected. The ONE state is the first or third (the first of the overlapping sequence) 1 detected. The ZERO state is the input after the first 1 is detected. 0 status. The output result z is high level and should be in the ZERO state while the input is 1.
State transition diagram
Reset is an asynchronous low-level reset and sets to IDLE state.
Code
module top_module (
input clk,
input aresetn, // Asynchronous active-low reset
input x,
output z );
parameter IDLE=0,ONE=1,ZERO=2;
reg [1:0] state,next_state;
\t
always@(posedge clk or negedge aresetn) begin
if(!aresetn)
state <= IDLE;
else
state <= next_state;
end
\t
always@(*) begin
case(state)
IDLE : next_state <= x ? ONE : IDLE;
ONE : next_state <= x ? ONE : ZERO;
ZERO : next_state <= x ? ONE : IDLE;
endcase
end
\t
assign z = (state == ZERO) & amp; (x == 1);
endmodule
2.5.22 Q5a:Serial two’s complementer(Moore FSM) [Exams/ece241 2014 q5a]
Problem description
Please design a single-input single-output serial 2’s complement Moore finite state machine. The input (x) is a number of bits starting from the least significant bit of the number (one per clock cycle), and the output (Z) is the 2’s complement form of the input x. The machine will accept input numbers of any length. The circuit requires an asynchronous reset. The conversion of the number starts when reset is released and stops when reset is set.
For example:
Analysis
For the two’s complement rule, the complement of a positive number is the original code, and the complement of a negative number is the inverse of the original code plus one.
When the input is always 0 after initialization, it is defined as the IDLE state, and the output is consistent with the input.
When the first input is 1, the output remains 1, but for subsequent inputs of 0, it outputs 1, and the input 1 outputs 0 (that is, inverted).
Then there is the following state transition diagram:
Code
module top_module (
input clk,
input areas,
input x,
output z
);
parameter IDLE = 0,s1 = 1,s2 = 2;
reg [1:0] state,next_state;
always@(posedge clk or posedge areset) begin
if(areset)
state <= IDLE;
else
state <= next_state;
end
always@(*) begin
case(state)
IDLE: next_state = x? s1: IDLE;
s1 : next_state = x ? s2 : s1;
s2 : next_state = x ? s2 : s1;
endcase
end
\t
assign z = state == s1;
\t
endmodule
2.5.23 Q5b:Serial two’s complementer(Mealy FSM) [Exams/ece241 2014 q5b]
Problem description
The figure below is the Mealy state machine implementation of 2’s complement. Please use one-hot encoding to implement it.
Analysis
As can be seen from the timing diagram, the output z and input x are different from the previous question. In the previous question, the output was one clock beat later than the input. In this question, the input and output are at the same clock beat. For one-hot encoding, the two states are therefore 01 and 10 respectively.
Code
module top_module (
input clk,
input areas,
input x,
output z
);
parameter A=2'b01,B=2'b10;
reg [1:0] state,next_state;
always@(posedge clk or posedge areset) begin
if(areset)
state <= A;
else
state <= next_state;
end
\t
always@(*) begin
case(state)
A : next_state = x ? B : A;
B : next_state = x ? B : B;
endcase
end
\t
assign z = (state==A & amp; x) | (state==B & amp; ~x);
endmodule
This series mainly records my own learning process and simple thinking process, and refers to many other people’s ideas. The questions are all on HDLBits. I organized the description of the questions with the help of a translator and my own understanding. If there are any questions, you are welcome to criticize and correct me.