Finite State Machines are a fundamental tool for Hardware design. They are sequential circuits with inputs ($i$) and outputs ($o$) containing an internal state ($S$).
$FSM = \{i, o, S, n, f\}$
The next state can be updated by a combinational function ($n$) between the inputs and the previous state.
$S_{i} = n(i, S_{i-1})$
The outputs can also be updated by a different combinational function ($f$) between the inputs and the previous state.
$o = f(i, S_i)$
This type of FSMs are called Mealy Machines.
If the $f$ function only depends on the state (i.e. $o = f(S_i)$), they are called Moore Machines.
We will introduce a typical FSM example. A circuit with a single input that receives an stream of bits. The circuit has an output that outputs a 1 when the sequence 111 is found.
So for the input sequence $I$ the output should be $O$
$I=101110110101111011011101$
$O=000001000000001100000010$
import py4hw
class FSM(py4hw.Logic):
def __init__(self, parent, name, a, r):
super().__init__(parent, name)
self.a = self.addIn('a', a)
self.r = self.addOut('r', r)
self.state = 0
def clock(self):
if (self.state == 0):
if (self.a.get() == 1):
self.state = 1
self.r.prepare(0)
else:
self.state = 0
self.r.prepare(0)
elif (self.state == 1):
if (self.a.get() == 1):
self.state = 2
self.r.prepare(0)
else:
self.state = 0
self.r.prepare(0)
elif (self.state == 2):
if (self.a.get() == 1):
self.state = 2
self.r.prepare(1)
else:
self.state = 0
self.r.prepare(0)
else:
self.state = 0
self.r.prepare(0)
sys = py4hw.HWSystem()
a = sys.wire('a')
exp = sys.wire('exp')
r = sys.wire('r')
a_seq = [int(x) for x in '101110110101111011011101']
exp_seq = [int(x) for x in '000001000000001100000010']
py4hw.Sequence(sys, 'a', a_seq, a)
py4hw.Sequence(sys, 'exp', exp_seq, exp)
fsm = FSM(sys, 'fsm', a, r)
wvf = py4hw.Waveform(sys, 'wvf', [a,r, exp])
sys.getSimulator().clk(len(a_seq))
wvf.draw_wavedrom()
We can get a Verilog translation of the FSM
rtl = py4hw.VerilogGenerator(fsm)
print(rtl.getVerilog())
transpiling sequential /HWSystem[HWSystem]/FSM[fsm]
// This file was automatically created by py4hw Verilog generator
module FSM_216cbb61d10 (
input clk,
input a,
output reg r);
// Code generated from clock method
// wire/variable declaration
integer state;
// initial
initial
begin
state=0;
end
// process
always @(posedge clk)
begin
if (state==0)
begin
if (a==1)
begin
state=1;
r<=0;
end
else
begin
state=0;
r<=0;
end
end
else
begin
if (state==1)
begin
if (a==1)
begin
state=2;
r<=0;
end
else
begin
state=0;
r<=0;
end
end
else
begin
if (state==2)
begin
if (a==1)
begin
state=2;
r<=1;
end
else
begin
state=0;
r<=0;
end
end
else
begin
state=0;
r<=0;
end
end
end
end
endmodule