# Verilog 4: RT Level Finite State Machine
### 1. FSM Design Methodology
A finite state machine (FSM) is used to model a system that transits among a finite number of internal states. The transitions depend on the current state and external input. Unlike a regular sequential circuit, the state transitions of an FSM **do not exhibit a simple, repetitive pattern.**
Finite State Machines (FSM) are a **fundamental building block** in digital design because they provide **a structured, systematic, and predictable method** for designing sequential logic circuits.
### 2. Mealy and Moore Outputs
The basic block diagram of synchronous FSM is similar to the regular sequential circuit, as shown in the following figure. It consists of a state register, next-state logic, and output logic.
- An FSM is known as a **Moore** machine if the output is **only a function of state**.
- An FSM is known as a **Mealy** machine if the output is **a function of state and external input**.
### 3. FSM Representation
An FSM is usually specified by an abstract **state diagram** or **algorithmic state machine (ASM)** chart.
The following figure shows an example of a state diagram that consists of a single node and its transition arcs. The arc is taken when the corresponding expression is evaluated true. The Moore output value is placed inside the circle. The Mealy output is placed with the transition arcs.
The following figure shows an example of a ASM chart that consists of a single block. An ASM block consists of one state box and an optional network of decision boxes and conditional output boxes. A state box represents a state in an FSM, and the asserted Moore output values are listed inside the box.
A decision box tests the input condition and determines which exit path to take, true (T) or false (F). A conditional output box lists asserted Mealy output values and is usually placed after a decision box. It indicates that the listed output signal can be activated only when the corresponding condition in the decision box is met.
The following figure shows an example of a state diagram:
In this example, we consider a simple FSM example. The FSM is represented both using a state diagram and an ASM chart as in the following figure. It consists of three states and both Mealy output x, and Moore output y. The inputs to the FSM are a and b.
The following figure shows an example of an ASM diagram
### 4. Register Transfer (RT) Operation
#### 4.1 Single RT Operation
An RT operation specifies data manipulation and transfer for a single destination register. It is represented by the notation
$$r_{dest}\leftarrow f(r_{src1}, r_{src2}, ..., r_{srcn})$$
where
- $r_{dest}$ is the destination register,
- $r_{src1}$ is the source registers 1
- $r_{src2}$ is the source registers 2
- $r_{srcn}$ is the source registers n
- $f(.)$ is mathematical function realized by a combinational circuit
The notation indicates that the contents of the source registers are fed to the $f(.)$ function, which is realized by a combinational circuit, and the result is passed to the input of the destination register and stored in the destination register **at the next rising edge of the clock**.
Following are several representative RT operations and the synthesized circuit. It consist of **current state and next state**. Next state will become current state at the rising edge of the clock.
A constant 0 is stored in $r_1$ register **at the next rising edge of the clock**.
$$r_1 \leftarrow 0$$
The Verilog code for the circuit:
```verilog
reg [7:0] r1_reg, r1_next;
always @(posedge clk)
begin
if (!rst_n)
r1_reg <= 0;
else
r1_reg <= r1_next;
end
always @(*)
begin
r1_next = 0;
end
```
The summation of the $r_1$ and $r_2$ registers is written to the $r_1$ register **at the next rising edge of the clock**.
$$r_1 \leftarrow r_1 + r_2$$
The Verilog code for the circuit:
```verilog
reg [7:0] r1_reg, r1_next;
reg [7:0] r2_reg, r2_next;
always @(posedge clk)
begin
if (!rst_n)
r1_reg <= 0;
else
r1_reg <= r1_next;
end
always @(*)
begin
r1_next = r1_reg + r2_reg;
end
// r2 reg ...
```
The $r_1$ register is shifted left two positions and then written back to itself **at the next rising edge of the clock**.
$$r_1 \leftarrow r_1 << 2$$
The Verilog code for the circuit:
```verilog
reg [7:0] r1_reg, r1_next;
always @(posedge clk)
begin
if (!rst_n)
r1_reg <= 0;
else
r1_reg <= r1_next;
end
always @(*)
begin
r1_next = r1_reg << 2;
end
```
The content of the $r_1$ register is written back to itself **at the next rising edge of the clock**.
$$r_1 \leftarrow r_1$$
The Verilog code for the circuit:
```verilog
reg [7:0] r1_reg, r1_next;
always @(posedge clk)
begin
if (!rst_n)
r1_reg <= 0;
else
r1_reg <= r1_next;
end
always @(*)
begin
r1_next = r1_reg;
end
```
#### 4.2 Combining RT Operations
We can combine all of the RT operations to become a complex system. The resulting circuit from the examples before is become like this:
The Verilog code for the circuit:
```verilog
reg [1:0] state_reg, state_next;
reg [7:0] r1_reg, r1_next;
always @(posedge clk)
begin
if (!rst_n) begin
state_reg <= 0;
r1_reg <= 0;
end
else begin
state_reg <= state_next;
r1_reg <= r1_next;
end
end
always @(*)
begin
state_next = state_reg;
r1_next = r1_reg;
case (state_reg)
2'b00: begin
state_next = 2'b01;
r1_next = 0;
end
2'b01: begin
state_next = 2'b10;
r1_next = r1_reg + r2_reg;
end
2'b10: begin
state_next = 2'b11;
r1_next = r1_reg << 2;
end
2'b11: begin
state_next = 2'b00;
r1_next = r1_reg;
end
endcase
end
```
### 5. Design Examples
The procedure of developing code for an FSM is similar to that of a regular sequential circuit. We first separate the state register and then derive the code for the combinational next-state logic and output logic.
```verilog=
module fsm_eg_4seg
(
input wire clk,
input wire rst_n,
input wire a,
input wire b,
output wire [7:0] x,
output wire [7:0] y
);
// Symbolic state declaration
localparam [1:0] S0 = 2'b00,
S1 = 2'b01,
S2 = 2'b10;
// Signal declaration
reg [1:0] state_reg, state_next;
// Segment 1: State register
always @(posedge clk)
begin
if (!rst_n)
state_reg <= S0;
else
state_reg <= state_next;
end
// Segment 2: Next state logic
always @(*)
begin
state_next = state_reg;
case (state_reg)
S0: begin
if (a == 1'b1)
if (b == 1'b1)
state_next = S2;
else
state_next = S1;
else
state_next = S0;
end
S1: begin
if (a == 1'b1)
state_next = S0;
else
state_next = S1;
end
S2: begin
state_next = S0;
end
endcase
end
// Segment 3: Mealy output logic
assign x = ( ((state_reg == S0) || (state_reg == S2)) && a && b ) ?
8'd168 : 8'd0;
// Segment 4: Moore output logic
assign y = (state_reg == S1) ? 8'd168 : 8'd0;
endmodule
```
```verilog=
module fsm_eg_2seg
(
input wire clk,
input wire rst_n,
input wire a,
input wire b,
output reg [7:0] x,
output reg [7:0] y
);
// Symbolic state declaration
localparam [1:0] S0 = 2'b00,
S1 = 2'b01,
S2 = 2'b10;
// Signal declaration
reg [1:0] state_reg, state_next;
// Segment 1: State register
always @(posedge clk)
begin
if (!rst_n)
state_reg <= S0;
else
state_reg <= state_next;
end
// Segment 2: Next state logic and output logic
always @(*)
begin
state_next = state_reg;
x = 8'd0;
y = 8'd0;
case (state_reg)
S0: begin
if (a == 1'b1)
if (b == 1'b1)
begin
x = 8'd168;
state_next = S2;
end
else
state_next = S1;
else
state_next = S0;
end
S1: begin
y = 8'd168;
if (a == 1'b1)
state_next = S0;
else
state_next = S1;
end
S2: begin
if (a && b)
x = 8'd168;
state_next = S0;
end
endcase
end
endmodule
```
The following code is the testbench for the FSM example.
```verilog=
`timescale 1ns / 1ps
module fsm_eg_4seg_tb();
localparam T = 10;
reg clk, rst_n;
reg a, b;
wire [7:0] x, y;
fsm_eg_4seg dut(.clk(clk), .rst_n(rst_n), .a(a), .b(b), .x(x), .y(y));
always
begin
clk = 0;
#(T/2);
clk = 1;
#(T/2);
end
initial
begin
a = 0; b = 0;
rst_n = 0; #T;
rst_n = 1; #T;
a = 1; b = 0; // Go to state S1
#T;
a = 1; b = 0; // Go back to state S0
#T;
a = 1; b = 1; // Go to state S2
#T;
a = 0; b = 0;
end
endmodule
```
This is the simulation result of the four segments FSM example. The Moore output y changes when the FSM enters state S1. It follows the rising edge of the clock. But the Mealy output x changes when a and b are both one. It doesn't follow the rising edge of the clock. It follows external signals. This is the difference between Moore and Mealy outputs.
### 6. Coding Guidelines
#### 6.1 Common Verilog Mistake
Following are common errors found in combinational circuit codes:
- Variable assigned in multiple always blocks
- Incomplete sensitivity list
- Incomplete branch and incomplete output assignment
- Combinational feedback loop
**Variable assigned in multiple always blocks.** In Verilog, variables can be assigned (i.e., appear on the left-hand side) in multiple always blocks. For example, the y variable is shared by two always blocks is the following code segment:
```verilog
reg y, a, b, clear;
always @(*)
if (clear)
y = 1'b0;
always @(*)
y = a & b;
```
Although the code is syntactically correct and can be simulated, it cannot be synthesized. Recall that each always block can be interpreted as a circuit part. The code above indicates that y is the output of both circuit parts and can be updated by each part. No physical circuit exhibits this kind of behavior and thus the code cannot be synthesized. We must group the assignment statements in a single always block, as in
```verilog
always @(*)
if (clear)
y = 1'b0;
else
y = a & b;
```
**Incomplete sensitivity list.** For a combinational circuit, the output is a function of input and thus any change in an input signal should activate the circuit. This implies that all input signals should be included in the sensitivity list. For example, a two-input and gate can be written as
```verilog
always @(a, b) // Both a and b are in the sensitivity list
y = a & b;
```
If we forget to include b, the code becomes
```verilog
always @(a) // b missing from sensitivity list
y = a & b;
```
Although the code is still syntactically correct, its behavior is very different. When a changes, the always block is activated and y gets the value of a&b. When b changes, the always block remains suspended since it is not "sensitive to" b and y keeps its previous value. No physical circuit exhibits this kind of behavior. Most synthesis software will issue a warning message and infer the and gate instead.
In Verilog-2001, a special notation, @(*) is introduced to implicitly include all the relevant input signals and thus eliminates this problem.
**Incomplete branch and incomplete output assignment.** The output of a combinational circuit is a function of input only and the circuit should not contain any internal state (i.e., memory). One common error with an always block is the inference of unintended memory (inferred latch) in a combinational circuit.
Consider the following code segment, which intends to describe a circuit that generates greater-than gt and equal-to eq output signals.
```verilog
always @(*)
if (a > b) // eq is not assigned in this branch
gt = 1'b1;
else if (a == b) // gt is not assigned in this branch
eq = 1'b1;
// final else branch is omitted
```
Let us first examine the incomplete branch error. There is no else branch in the segment. If both the a>b and a==b expressions are false, both gt and eq are not assigned values. According to Verilog definition, they keep their previous values (i.e., the outputs depend on the internal state) and unintended latches are inferred.
The segment also has incomplete output assignment errors. For example, when the a>b expression is true, eq is not assigned a value and thus will keep its previous state. A latch will be inferred accordingly.
There are two ways to fix the errors. The first is to add the else branch and explicitly assign all output variables. The code becomes
```verilog
always @(*)
if (a > b)
begin
gt = 1'b1;
eq = 1'b0;
end
else if (a == b)
begin
gt = 1'b0;
eq = 1'b1;
end
else // i.e., a < b
begin
gt = 1'b0;
eq = 1'b0;
end
```
The alternative is to assign a default value to each variable in the beginning of the always block to cover the unspecified branch and unassigned variable. The code becomes
```verilog
always @(*)
begin
gt = 1'b0; // Default value for gt
eq = 1'b0; // Default value for eq
if (a > b)
gt = 1'b1;
else if (a == b)
eq = 1'b1;
end
```
Both gt and eq assume 0 if they are not assigned a value later.
The case statement experiences the same errors if some values of the [case_expr] expression are not covered by the item expressions. Consider the following code segment:
```verilog
reg [1:0] s;
always @(*)
begin
case (s)
2'b00: y = 1'b1;
2'b10: y = 1'b0;
2'b11: y = 1'b1;
endcase
end
```
The 2'b01 value is not covered by any branch. If s assumes this combination, y will keep its previous value and an unintended latch is inferred.
To fix this error, we have to add a default value:
```verilog
always @(*)
begin
case (s)
2'b00: y = 1'b1;
2'b10: y = 1'b0;
2'b11: y = 1'b1;
default: y = 1'b0;
endcase
end
```
Alternatively, we can assign a default value in the beginning of the always block:
```verilog
always @(*)
begin
y = 1'b0; // Default value for y
case (s)
2'b00: y = 1'b1;
2'b10: y = 1'b0;
2'b11: y = 1'b1;
endcase
end
```
**Combinational feedback loop.** Combinatorial feedback loops are usually undesirable because the output will oscillate and the output is unpredictable.
#### 6.2 Guidelines
Following are the coding guidelines for the description of combinational circuits:
- Assign a variable only in a single always block.
- Use blocking statements for combinational circuits.
- Use @(*) to include all inputs automatically in the sensitivity list.
- Make sure that all branches of the if and case statements are included.
- Make sure that the outputs are assigned in all branches.
- One way to satisfy the two previous guidelines is to assign default values for outputs in the beginning of the always block.
- Think hardware, not C code.
Sign in with Wallet
Connect another wallet