Designs based on Finite State Machines - Digital Design of Signal Processing Systems: A Practical Approach - page 389

output

input

Combinational Logic

Next state

Current state

Figure 9.8 Combinational and sequential components of an FSM design

sequence is finite. The FSM can be described using a bubble (state) diagram or an algorithmic state
machine (ASM) chart.
FSM implementation in hardware has two components, a combinational cloud and a sequential
logic. The combination cloud computes the output and the next state based on the current state and
input, whereas the sequential part has the resetable state register. A FSM with combinational and
sequential components is shown in Figure 9.8.
Example: This example designs an FSM that counts four 1s on a serial interface and generates a 1
at the output. One bit is received on the serial interface at every clock cycle. Figure 9.9 shows a
bubble diagram in which each circle represents a state, and lines and curves with arrowheads
represent state transitions. There are a total of four states, S0 ... S3.
S0 represents the initial state where number of 1s received on the interface is zero. A 0/0 on the
transition curve indicates that, in state S0, if the input on the serial interface is 0 then the state
machine maintains its state and generates a 0 at the output. In the same state S0, if 1 is received at
the input, the FSM changes its state to S1 and generates a 0 at the output. This transition and
input-output relationship is represented by 1/0 on the line or curve with an arrowhead showing state

0/0

S0

0/0 1/0 1/1 0/0

S1 S3

0/0

1/0 1/0

S2

Figure 9.9 State diagram implementing counting of four 1s on a serial interface