Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 57 ยท State Machines

Designing a Sequential Circuit

Design a sequential circuit step by step: state diagram, state table, state assignment, excitation tables and gates, with a 1011 sequence detector checked in Python.

Knowing what a finite state machine is does not yet tell you how to build one out of flip-flops and gates. The good news is that the path from a written requirement to a working circuit is a fixed recipe. You follow the same steps whether the machine has four states or forty, and every step can be checked by a program.

This lesson walks through the whole recipe once, end to end, with one example: a sequence detector that watches a stream of bits and raises its output when it sees 1011. At the end we prove the finished circuit correct by testing it against thousands of input streams in Python.

The design recipe

From words to gates

  1. Specify
Write the behavior in plain words.
  1. States
Draw the state diagram.
  1. Table
Write the state table.
  1. Assign
Give each state a binary code.
1 / 2

Step 1: specify the behavior

The input x is one bit per clock cycle. The output z should be 1 in the cycle in which the last four inputs were 1, 0, 1, 1. Matches are allowed to overlap: in the stream 1 0 1 1 0 1 1 the detector fires twice, because the final 1 1 of the first match also starts the second one (1 0 1 1). The detector should also fire with no delay, so we use a Mealy machine and let the output depend on the current input.

Step 2: find the states

A state is a summary of what the machine needs to remember. For a pattern detector the answer is: how much of the pattern have I matched so far? For 1011:

State Meaning Code
A nothing useful matched (history ends in 0, or empty) 0
B the last bit was 1 (matched 1) 1
C the last bits were 10 2
D the last bits were 101 3

We have no state for "matched 1011" because in a Mealy machine the match shows up on the arrow as an output, and the state afterwards depends only on what overlap remains. Four states mean two flip-flops.

The transition rule is: append the new bit to the matched text, then keep the longest suffix that is still a prefix of the pattern. For example from D (101) with input 1 we have 1011, a full match, so output 1; the longest suffix of 1011 that is a proper prefix of 1011 is 1, so we go to B. From D with input 0 we have 1010, whose suffix 10 is a prefix, so we go to C.

stateDiagram-v2
    [*] --> A
    A --> A : 0 / 0
    A --> B : 1 / 0
    B --> C : 0 / 0
    B --> B : 1 / 0
    C --> A : 0 / 0
    C --> D : 1 / 0
    D --> C : 0 / 0
    D --> B : 1 / 1

Arrow labels are input / output. Only the arrow D to B on input 1 outputs 1.

Step 3: let the computer write the table

Instead of filling in the table by hand and hoping, we can generate it from the rule above. This also makes the lesson re-usable for any pattern.

Python Generate the state table from the rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can verify the rows against the diagram: only (D, 1) outputs 1, and the three rows that go back to B or C show the overlap.

Step 4: state assignment

State assignment gives each state a binary code. With four states and two flip-flops Q1 Q0 we have the whole code space, so every code is used and there are no unused states. We use A = 00, B = 01, C = 10, D = 11 (plain binary, which is also the matched length). Different assignments give different logic, and finding the cheapest one is a hard problem, so in practice we pick a sensible one, or try a few. One-hot coding uses one flip-flop per state and often gives simpler logic at the price of more flip-flops.

If the machine had 5 states (as a Moore version of this detector would), it would need 3 flip-flops and there would be 3 codes left over that the circuit must handle safely.

Step 5: excitation tables

A flip-flop is a memory, so to make it go from its present value Q to the wanted next value Q+ we must apply the right input. The excitation table lists these needs. For the two flip-flops you know:

Q Q+ D T J K
0 0 0 0 0 X
0 1 1 1 1 X
1 0 0 1 X 1
1 1 1 0 X 0

X means "don't care": either value works. For a D flip-flop the rule is the simplest of all: D = Q+, so the next-state equations are the flip-flop inputs. For T flip-flops, T = Q xor Q+ (toggle only when the bit has to change).

Read the next-state columns of our table:

Q1 Q0 x Q1+ Q0+ z
00 0 00 0
00 1 01 0
01 0 10 0
01 1 01 0
10 0 00 0
10 1 11 0
11 0 10 0
11 1 01 1

Step 6: simplify with K-maps

Every flip-flop input and every output is a function of three variables (Q1, Q0, x), so each fits in a 3-variable Karnaugh map.

  • Q0+ is 1 exactly when x is 1 (look down the table: every x = 1 row has Q0+ = 1, every x = 0 row has Q0+ = 0). So D0 = x. The least significant state bit is simply the last input bit.
  • Q1+ is 1 in rows 01/0, 10/1 and 11/0. Rows 01/0 and 11/0 combine to Q0 x'. Row 10/1 stays as Q1 Q0' x. So D1 = Q0 x' + Q1 Q0' x.
  • z is 1 only in row 11/1, so z = Q1 Q0 x.

The full circuit is therefore two D flip-flops, one AND gate for the output, and a few gates for D1. That is small enough to believe by inspection, but we do not stop at belief.

Step 7 and 8: build it and verify it

The best check is a brute-force one. We build the circuit exactly as the equations describe (as a Python function on bits) and compare it with a reference that does not know anything about states: "output 1 if the last four inputs were 1, 0, 1, 1". If the two agree on every input stream up to length 12, we have checked 8,190 streams, far more than this four-state machine needs to reveal a mistake.

Python Gate-level circuit versus a reference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The demo stream shows the output firing at positions 3, 6 and 10: each time the last four bits are 1 0 1 1, and the final 1 1 of one match can be the start of the next. If you change d1 slightly (try removing one of its terms), the assertion fails at once and shows the shortest stream that breaks it. That is the value of testing a design against an independent reference.

The same machine with T flip-flops

The recipe is identical for other flip-flops; only the excitation step changes. With T flip-flops the inputs are T = Q xor Q+. The program below computes the T inputs from the D equations, prints the table and runs the T-based circuit on a stream.

Python Excitation inputs for T flip-flops

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions behave the same; the choice between D, T and JK is about gate count and what your parts library offers. D flip-flops dominate in practice because their input is the next-state function itself and they are what FPGAs provide.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a state in a sequence detector represent?

    States summarize exactly what the machine must remember to decide the future: the longest part of the pattern that the recent inputs match.
  2. 2. A machine has 5 states. How many flip-flops does a binary encoding need?

    Two flip-flops give only 4 codes. Three flip-flops give 8 codes, which covers 5 states and leaves 3 unused codes.
  3. 3. For a D flip-flop, what is the excitation equation?

    A D flip-flop copies its input at the clock edge, so the input must equal the wanted next state. The next-state equation is the D input.
  4. 4. A bit goes from 1 to 1 in a transition. What does a T flip-flop need as input?

    T = Q xor Q+ = 1 xor 1 = 0. The flip-flop must not toggle, because it is already at the value it should keep.
  5. 5. Why did the Python check compare the circuit with a reference that has no states?

    If the table itself contained a mistake, testing the circuit against the same table would hide it. An independent definition of the behavior catches design errors in any step.

Summary

  • The design recipe is: specify, find states, write the table, assign codes, derive excitation inputs, simplify, draw, verify.
  • States summarize what must be remembered; for a pattern detector that is the length of the matched prefix.
  • A D flip-flop needs D = Q+; a T flip-flop needs T = Q xor Q+; JK flip-flops use their excitation table with don't-cares.
  • Four states fit two flip-flops with no unused codes; five need three flip-flops and a plan for the leftovers.
  • The 1011 detector needs D0 = x, D1 = Q0 x' + Q1 Q0' x and z = Q1 Q0 x.
  • Always verify against an independent reference, ideally by exhaustive testing.

Next: State Machine Patterns and Pitfalls.