Finite State Machine (FSM)
When the sequence of actions in your design depend on
the state of sequential elements, a finite state machine
(FSM) can be implemented
FSMs are widely used in applications that require
prescribed sequential activity
Example:
• Sequence Detector
• Fancy counters
• Traffic Light Controller
• Data-path Controller
• Device Interface Controller
• etc.
Finite State Machine (FSM) (cont.)
All state machines have the general feedback structure
consisting of:
Combinational logic implements the next state logic
• Next state (ns) of the machine is formed from the current
state (cs) and the current inputs
State register holds the value of current state
Next State
Inputs Current
Next-State
Logic
Memory State
Types of State Machines
Moore State Machine
ns cs
Inputs Next-State State Output Outputs
Logic Register Logic
Next state depends on the current state and the inputs
but the output depends only on the present state
next_state(t) = h(current_state(t), input(t))
output = g(current_state(t))
Types of State Machines (cont.)
Mealy State Machine
Output Outputs
ns cs Logic
Inputs Next-State State
Logic Register
Next state and the outputs depend on the current state
and the inputs
next_state(t) = h(current_state(t), input(t))
output(t) = g(current_state(t), input(t))
Typical Structure of a FSM
module mod_name ( … );
input … ;
output … ;
parameter size = … ;
reg [size-1: 0] current_state;
wire [size-1: 0] next_state;
// State definitions
`define state_0 2'b00
`define state_1 2b01
always @ (current_state or the_inputs) begin
// Decode for next_state with case or if statement Next State
// Use blocked assignments for all register transfers to ensure Logic
// no race conditions with synchronous assignments
end
always @ (negedge reset or posedge clk) begin
if (reset == 1'b0) current_state <= state_0;
State
else current_state <= next_state;
end
Register
//Output assignments
endmodule
Sequence Detector FSM
Functionality: Detect two successive 0s or 1s in the serial input bit stream
reset
reset_state out_bit = 0
0 1
1
FSM out_bit = 0 read_1_zero read_1_one out_bit = 0
Flow-Chart 0
0 0 1 1
0 read_2_zero read_2_one 1
out_bit = 1 out_bit = 1
Sequence Detector FSM (cont.)
module seq_detect (clock, reset, in_bit, out_bit); always @ (state_reg or in_bit)
input clock, reset, in_bit; case (state_reg)
output out_bit; reset_state:
if (in_bit == 0)
reg [2:0] state_reg, next_state;
next_state = read_1_zero;
else if (in_bit == 1)
// State declaration
parameter reset_state = 3'b000; next_state = read_1_one;
parameter read_1_zero = 3'b001; else next_state = reset_state;
parameter read_1_one = 3'b010; read_1_zero:
parameter read_2_zero = 3'b011; if (in_bit == 0)
parameter read_2_one = 3'b100; next_state = read_2_zero;
else if (in_bit == 1)
// state register next_state = read_1_one;
always @ (posedge clock or posedge reset) else next_state = reset_state;
if (reset == 1) read_2_zero:
state_reg <= reset_state;
if (in_bit == 0)
else
next_state = read_2_zero;
state_reg <= next_state;
else if (in_bit == 1)
// next-state logic next_state = read_1_one;
else next_state = reset_state;
Sequence Detector FSM (cont.)
read_1_one:
if (in_bit == 0)
next_state = read_1_zero;
else if (in_bit == 1)
next_state = read_2_one;
else next_state = reset_state;
read_2_one:
if (in_bit == 0)
next_state = read_1_zero;
else if (in_bit == 1)
next_state = read_2_one;
else next_state = reset_state;
default: next_state = reset_state;
endcase
assign out_bit = ((state_reg == read_2_zero) || (state_reg == read_2_one)) ? 1 : 0;
endmodule
Clock Domain Synchronization
Larger designs generally consists of several parts that
operate at independent clocks – clock domains
Clock domain synchronization is required when ever a
signal traverses from one clock domain to another clock
domain
Problem can be treated as the case where flip-flop data
input is asynchronous
Can cause metastabilty in the receiving flip-flop
Rupture the sequential behavior
This can be avoided by using synchronization circuits
Clock Domain Synchronization (cont.)
Note:
Metastability can not be avoided
Metastability causes the flip-flop to take longer time than
tclock-output to recover
Solution: Let the signal become stable before using it (i.e.
increase the MTBF)
DA
D DB
Flip-flop1 Flip-flop2
clkA
clkB
Types of Synchronization Techniques
Case-1: When the width of asynchronous input pulse is
greater than the clock period i.e.
Tasync_in > Tclock
q1
async_in sync_out
Flip-flop1 Flip-flop2
clock
reset
Simulation Results
Presence of Metastable State
clock
reset
async_in
q1 metastable
sync_out not metastable
The flip flips The reset is Flip-flop1 enters Flip-flop1 comes
get reset de-asserted metastability back to a stable
state, latching
async_in becomes high async_in
simultaneously with Flip-flop1
the posedge of the gets a stable Flip_flop2 latches the
clock, thus violating input at this stable value of
the setup time (2nd) edge flip_flop1 (q1), thus
delaying async_in by
3 clock cycles*
* As sync_out will be available to latch only at the next clock edge
Simulation Results (cont.)
Absence of Metastable State
clock
reset
async_in
q1
sync_out
The flip flips The reset is Flip-flop1 enters
get reset de-asserted stable state
latching async_in
async_in becomes high
before the posedge of
the clock, thus Flip_flop2 latches the
meeting the setup time stable value of
flip_flop1 (q1), thus
delaying async_in by
2 clock cycles
Types of Synchronization Techniques (cont.)
Case-2: When the width of asynchronous input pulse is
less than the clock period i.e.
Tasync_in < Tclock
q1 q2
VDD sync_out
Flip-flop1 Flip-flop2 Flip-flop3
async_in
clock
reset
Simulation Results
clock
reset
async_in
q1
q2
sync_out
first_reset
Reset Sequence Flip-flop1 Sync_out becomes
for the gets a stable high after 2 clocks
synchronization posedge of and causes
circuit async_in flip-flop1 to reset
Flip-flop1
latches 1
First-in First-out Memory (FIFO)
When the source clock is higher than the destination
clock, loss of data can occur due to inability of the
destination to sample at the source speed
How to avoid this?
Use handshake signals (i.e. supply data only when the
destination is ready to receive e.g. master-slave protocol)
• Transfer rates are lower
High performance parallel interfaces between independent
clock domains are implemented with first-in first-out
memory called FIFO.
FIFO Features
A FIFO consists of block of memory and a controller that
manages the traffic of data to and from the FIFO
A FIFO provides access to only one register cell at a time (not
the entire array of registers)
A FIFO has two address pointers, one for writing to the next
available cell, and another one for reading the next unread cell
The pointers for reading and writing are relocated dynamically
as commands to read or write are received
A pointer is moved after each operation
A FIFO can receive data until it is full and can be read until it is
empty
FIFO Features (cont.)
A FIFO has:
Separate address pointers and datapaths for reading and writing data
Status lines indicating the condition of the stack (full, almost full, empty
etc.)
The input (write) and output (read) domains can be synchronized by
two separate clocks, allowing the FIFO to act as a buffer between two
clock domains
A FIFO can allow simultaneous reading and writing of data (however
synchronization is necessary if read/write parts are different clock domains)
The write signal is synchronized to the read clock using clock
synchronizers
FIFOs are usually implemented with dual-port RAMs with independent
read- and write-address pointers and registered data ports (see
www.idt.com)
FIFO Structure
stack_height -1
stack_full
data_in
stack_half
write_to_stack stack_empty
FIFO
clk_write Buffer data_out
read_from_stack
rst
clk_read
Internal Signals
0
stack_width -1 0 write_ptr
Input-output Ports
read_ptr
FIFO Model
Note: Prohibit write if the FIFO is full and Prohibit read if the FIFO is empty
module FIFO_Buffer (clk, rst, write_to_stack, data_in, read_from_stack, data_out, stack_full, stack_half_full,
stack_empty);
parameter stack_width = 32;
parameter stack_height = 8;
parameter stack_ptr_width = 3;
parameter HF_level = 4;
input clk, rst, write_to_stack, read_from_stack;
input [stack_width-1:0] data_in;
output stack_full, stack_half_full, stack_empty;
output [stack_width-1:0] data_out;
reg [stack_ptr_width-1:0] read_ptr, write_ptr;
reg [stack_ptr_width:0] ptr_gap; // Gap between the pointers
reg [stack_width-1:0] data_out;
reg [stack_width:0] stack [stack_height-1:0];
// stack status signals
assign stack_full = (ptr_gap == stack_height);
assign stack_half_full = (ptr_gap == HF_level);
assign stack_empty = (ptr_gap == 0);
FIFO Model (cont.)
always @ (posedge clock or posedge reset)
if (rst == 1) begin
data_out <= 0;
read_ptr <= 0;
write_ptr <= 0;
ptr_gap <= 0;
begin
else if (write_to_stack && (!read_from_stack) && (!stack_full)) begin
stack [write_ptr] <= data_in;
write_ptr <= write_ptr + 1;
ptr_gap <= ptr_gap + 1;
end
else if ((!write_to_stack) && read_from_stack && (!stack_empty)) begin
data_out <= stack[read_ptr];
read_ptr <= read_ptr + 1;
ptr_gap <= ptr_gap - 1;
end
else if (write_to_stack && read_from_stack && stack_empty) begin
stack [write_ptr] <= data_in;
write_ptr <= write_ptr + 1;
ptr_gap <= ptr_gap + 1;
end
FIFO Model (cont.)
else if (write_to_stack && read_from_stack && stack_full) begin
data_out <= stack[read_ptr];
read_ptr <= read_ptr + 1;
ptr_gap <= ptr_gap - 1;
end
else if (write_to_stack && read_from_stack && (!stack_empty) && (!stack_full)) begin
stack [write_ptr] <= data_in;
data_out <= stack[read_ptr];
write_ptr <= write_ptr + 1;
read_ptr <= read_ptr + 1;
end
endmodule
