Microsoft Word - Digital Logic Design v_4_6a

4.4. Finite State machine

 State Diagram
A state diagram is a graphical method of showing each state and the movement to other steps based
on the new values of external inputs. Here are the steps (example for SR flip-flop):

 Finite State Machine or Simple State Machine is used to describe a sequential logic circuit

 A completely specified state machine is one for which all input conditions are used to specify

each next state condition. For a completely specified machine, the “sum = 1 rule” applies which

says that all outgoing conditions from a state must sum up to 1.

For example for state 0 of the SR flip-flop, a completely specified state machine, the outgoing

conditions sums up to 0

Sum of Outgoing Conditions =(S+R)+S.R= 1

 An incompletely specified state machine is one which is missing some input condition. You may

interpret them as “don’t care” conditions.

Note: For the incompletely specified state machine, the sum of outgoing conditions of all states

are not equal to 1.

 Algorithmic State Machine (ASM) Chart
An ASM chart is similar to the programming flow chart and is an equivalent of the state diagram used
to describe a sequential logic circuit (or Finite State Machine).

The chart uses three symbols:

 Rectangle is the state box (equivalent to circles in state diagram)

 Diamond is the decision box (equivalent to inputs next to the lines in state diagram)

one of two paths provide the exit from decision box:

S R Q+

0 0 Q

0 1 0

1 0 1

1 1 0

(reset dominant)

Step 1. Write the

Compressed

Characteristic Table

Step 2. Present State

/Next State (PS/NS)

Table

S R Q Q+

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 0

Step 3. Draw a circle for each state

(one output, Q, so 2 –state)

Step 4. Draw arrow showing change

for each possible input in each state.

Q=0 Q=1

Hold 0

S R

0 0

0 1

1 1

=S+R

Reset

S R

1 1

0 1

=R

Hold 1

S R

0 0

1 0

=R

Set

S R

1 0

=S.R