Finite State Machine - Micro-controllers-Digital Electronics

1. Used to create logic circuits with memory (i.e. they remember what happened previously)
2. Uses components called flip-flops
3. Flip-flop holds a value and only changes on a given clock signal (rising edge, falling edge)

Q is the value of the flip-flop
Q+ = Next value of Q
Typically most flip-flops have a Q and !Q output

Flip-flop examples: D, JK

More Links:

Finite State Machine-Tutorials and Examples-1
Finite State Machine-Tutorials and Examples-2
Mealy and Moore machines
Micro controller based Systems

D Flip-Flop

Q+ (Next State) = D where D is the input to the flip-flop

J-K Flip Flop
J is equivalent to the S (Set), when J=1, K=0, Q+ always = 1

K is equivalent to the R (Reset) when J=0, K=1, Q+ always = 0
When J=1, K=1, equivalent to a toggle, Q+ = !Q
When J=0, K=0, Q stays the same

Example

An FSM to o/p a 1 when the sequence of 1 0 is seen across the i/p, hover in the final state

Draw the state diagram

3 states -> 2^N states can be captured by N flip-flops
3 states therefore we need 2 flip-flops, 2^N = 4 which is greater than the 3 required states

Draw a truth table
3 inputs – 2 from the flip-flops (current state) (Q0, Q1)
1 input (1 0 sequence) (I)
Next state is a combination of the current state and input via combinatorial logic

X is a don’t care, i.e. it does not matter if it is a 0 or a 1
Why do we have X’s in this truth table?
Notice that we do not use State 11, so we don’t care
what happens in that situation
State 0 (S0) See a 0 (I=0)

State diagram tells us to stay in state 00
Q0+ = 0, Q1+ = 0, X = 0
State 0 (S0) See a 1 (I=1)

State diagram transitions to state 01
Q0+ = 0, Q1+ = 1, X = 0

3 outputs – 3 K-Maps

K-Map for Q0+

K-Map for Q1+

K-Map for X