SME
Digital Logic Design · Problem type
Flip-flops for a state machine
Use this for “A controller has 5 states. How many flip-flops does binary encoding need, and how many codes go unused?”
This is an example. Type your own values to start a new problem.
n
=
⌈log₂
S
⌉
U
=
2
−
S
C
Binary codes
worked out (not typed)
h
One-hot flip-flops
worked out (not typed)
Formulas
n
=
⌈log₂
S
⌉
3 = ⌈log₂ 5⌉
C
=
2
n
8
=
2
3
U
=
C
−
S
3 = 8 − 5
h
=
S
5 = 5
Assumptions
•
Binary encoding gives each state its own code, one bit per flip-flop, so n flip-flops name up to 2ⁿ states.
•
One-hot encoding uses one flip-flop per state, and exactly one of them holds 1 at a time.
•
Binary codes no state uses are unused states: the design must lead each one back to a real state.
Step-by-step
WE KNOW
S = 5
FIND
binary flip-flops (n), binary codes (C), unused codes (U), one-hot flip-flops (h)
Step 1 · Find binary flip-flops (n)
Use n = ⌈log₂ S⌉
n
flip-flops
make
2ⁿ
codes,
so
take
the
smallest
n
with
2ⁿ
at
least
the
number
of
states.
⌈log₂
5⌉
=
3,
since
2
2
=
4
<
5
≤
8
=
2
3
n
=
3
Step 2 · Find binary codes (C)
Use C = 2ⁿ
Each flip-flop doubles the codes it can hold.
C
=
2
3
C
=
8
Step 3 · Find unused codes (U)
Use U = C − S
Every code that no state takes is left unused.
U
=
8
−
5
U
=
3
Step 4 · Find one-hot flip-flops (h)
Use h = S
One-hot gives every state a flip-flop of its own.
h
=
5
Check
Put the numbers back in. Both sides should match.
3 = ⌈log₂ 5⌉ ✓
8
=
2
3
✓
3 = 8 − 5 ✓
5 = 5 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.