Analysing a Clocked Sequential Circuit

Turn a schematic of flip-flops and gates into equations, a transition table, a state table and a state diagram.

You Will Be Able To

  • Read the excitation equations of each flip-flop from a schematic.
  • Turn them into next-state equations with the characteristic equations of D, T and JK flip-flops.
  • Build the transition table and the state table, and draw the state diagram.
  • Analyse a circuit with JK flip-flops without treating J as D.
Lesson
G7.2
Time
30 min
Runs on
Your browser
Check
5 questions

A supplier sent a block as a netlist with no specification. Before you can use it, you must say what it does. Analysis turns gates and flip-flops into a state diagram. Step the netlist to see it move.

A Netlist With No Specification
A Netlist With No Specificationg1 · NOTnx=0g2 · NOTna=1g3 · NOTnb=0g4 · ANDt1=0g5 · ANDt2=1g6 · ORda=1g7 · ANDdb=1g8 · ANDz=0DQfa · DFFA=0DQfb · DFFB=1x=1clk=0
x=1 clk=0
g1 · NOTx=1 → nx=0
g2 · NOTA=0 → na=1
g3 · NOTB=1 → nb=0
g4 · ANDA=0, nx=0 → t1=0
g5 · ANDB=1, x=1 → t2=1
g6 · ORt1=0, t2=1 → da=1
g7 · ANDna=1, x=1 → db=1
g8 · ANDA=0, nb=0 → z=0
fa · DFFda=1, clk=0 → A=0
fb · DFFdb=1, clk=0 → B=1
Read the connections
GateKindInputsOutput
g1NOTxnx
g2NOTAna
g3NOTBnb
g4ANDA, nxt1
g5ANDB, xt2
g6ORt1, t2da
g7ANDna, xdb
g8ANDA, nbz
faDFFda, clkA
fbDFFdb, clkB

Outputs: A, B, z. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 56. Settled after 56 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556A000000000000011111111111111111111111100000000000000000000B000001111111111111111000000000000000000000000000000001111zx00000000000000000000001111111111111110000000000000000000
Scroll horizontally ↔
Every computed frame
TimeABz
000x
1000
2000
3000
4000
5010
6010
7010
8010
9010
10010
11010
12010
13110
14110
15110
16110
17110
18110
19110
20110
21100
22100
23101
24101
25101
26101
27101
28101
29101
30101
31101
32101
33101
34101
35101
36101
37001
38000
39000
40000
41000
42000
43000
44000
45000
46000
47000
48000
49000
50000
51000
52000
53010
54010
55010
56010

  1. Step 4 · Edge 1. x = 1 from state 00. da = Ax' + Bx = 0 and db = A'x = 1, so the edge loads AB = 01.
  2. Step 12 · Edge 2. x = 1 again: da = Bx = 1 and db = A'x = 1. The edge loads 11.
  3. Step 20 · Edge 3. x = 0: da = Ax' = 1, db = 0. The state is 10, and z = AB' turns 1.
  4. Step 28 · Edge 4. x = 0 in state 10: da = 1 again. A self-loop: z stays 1.
  5. Step 36 · Edge 5. x = 1 in state 10: da = Bx = 0 and db = A'x = 0. Back to 00.

Step it one gate delay at a time. Each D input settles before the clock rises. The flops load at that edge.

Step 1: Excitation Equations

From Gates to a State DiagramArrows show the order of the analysis. Each box is one product of the analysis.
  • Neutral
  • Structure
From gates to a state diagramArrows show the order of the analysis. Each box is one product of the analysis. neutral Schematic flip-flops and gates neutral Excitationequations D, T or J and K ofeach flop neutral Next-stateequations through Q+ = D, T ⊕Q, JQ' + K'Q neutral Transition table codes: present, input,next, output neutral State table the same rows withnames neutral State diagram circles and arcs follow wires backcharacteristicequationevery row and inputname the codesdraw it
  1. neutral Schematicflip-flops and gates
    • follow wires back → Excitation equations
  2. neutral Excitation equationsD, T or J and K of each flop
    • characteristic equation → Next-state equations
  3. neutral Next-state equationsthrough Q+ = D, T ⊕ Q, JQ' + K'Q
    • every row and input → Transition table
  4. neutral Transition tablecodes: present, input, next, output
    • name the codes → State table
  5. neutral State tablethe same rows with names
    • draw it → State diagram
  6. neutral State diagramcircles and arcs
  1. Step 1

    Read each flip-flop input from the gates in front of it.

  2. Step 2

    Turn each input equation into Q+ with the flip-flop type.

  3. Step 3

    Fill the table, name the states, draw the diagram.

Read the diagram as text
  • Schematic: flip-flops and gates
  • Excitation equations: D, T or J and K of each flop
  • Next-state equations: through Q+ = D, T ⊕ Q, JQ' + K'Q
  • Transition table: codes: present, input, next, output
  • State table: the same rows with names
  • State diagram: circles and arcs
  • Schematic → Excitation equations: follow wires back
  • Excitation equations → Next-state equations: characteristic equation
  • Next-state equations → Transition table: every row and input
  • Transition table → State table: name the codes
  • State table → State diagram: draw it

The three steps below follow this order on the netlist above.

An excitation equation gives each flip-flop input as a function of the present state and the inputs. Read it by following the wires back from the input pin of each flip-flop.

Flip-flop inputGates behind itExcitation equation
D of Ag4 = A·x', g5 = B·x, g6 ORs themDA = A·x' + B·x
D of Bg7 = A'·xDB = A'·x
output zg8 = A·B'z = A·B'

From the netlist above. z reads only the state, so this is a Moore output.

Step 2: Next-State Equations

A next-state equation gives Q+ for each flip-flop. Put the excitation equations into the characteristic equation of the flip-flop type, from lesson G5.7.

Flip-flopCharacteristic equationFor this netlist
DQ+ = DA+ = A·x' + B·x and B+ = A'·x
TQ+ = T ⊕ Qsubstitute T, then XOR with Q
JKQ+ = J·Q' + K'·Qsubstitute J and K; never Q+ = J

For D flip-flops this step is free. For T and JK it is where most mistakes happen.

Step 3: Transition Table, State Table, State Diagram

The transition table lists, for each present state code and input, the next code and the output. Give the codes names and it becomes the state table. Draw it and you have the state diagram.

Present ABNext AB, x = 0Next AB, x = 1z
0000010
0100110
1110100
1010001

The transition table, one row per present state, filled from the next-state equations.

  1. Row 00

    A = B = 0. A+ = Ax' + Bx = 0 for both x. B+ = A'x = x. So 00 or 01.

  2. Row 01

    A+ = Bx = x and B+ = x: 00 or 11.

  3. Row 11

    A+ = x' + x = 1 and B+ = A'x = 0: always 10.

  4. Row 10

    A+ = x' and B+ = 0: 10 or 00. z = AB' = 1 only here.

What the Netlist Does
What the Netlist Does01010101S000AB = 00S010AB = 01S110AB = 11S101AB = 10
  1. AB = 00 · S000
    • ↓0 → S00
    • ↓1 → S01
  2. AB = 01 · S010
    • ↓0 → S00
    • ↓1 → S11
  3. AB = 11 · S110
    • ↓0 → S10
    • ↓1 → S10
  4. AB = 10 · S101
    • ↓0 → S10
    • ↓1 → S00
StateInputNextOutput in state
S000S000
S001S010
S010S000
S011S110
S110S100
S111S100
S100S101
S101S001

Current state: S01 · Output: 0

Sampled input, state and output waveformStepState0S001S012S113S104S105S006S007S01x—1100101z00011000
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step01234567
Input—1100101
StateS00S01S11S10S10S00S00S01
Output00011000

Read from the state table below. Two 1s in a row reach 11; the next edge always gives 10, where z = 1 until a 1 arrives.

Run It and Compare

The lab bench feeds a stream that takes every pair of state and input at least once. Each line is one row of the table. If a line differs from your table, your equations or your table hold the error.

Asked in interviews
  1. How do you find what an unknown sequential circuit does?

    Write the excitation equations from the gates in front of each flip-flop. Turn them into next-state equations with the characteristic equations. Fill the transition table, name the states and draw the diagram.

  2. What is the difference between a transition table and a state table?

    The transition table uses the binary state codes. The state table uses symbolic state names. They hold the same arcs.

  3. J = 0 and K = 0 on a JK flip-flop that holds 1. What is the next state?

    It stays 1. Q+ = JQ' + K'Q = 0 + 1·1 = 1. Treating J as D would give 0, a common analysis mistake.

Try It

Fill the transition table by hand first. Then run and check each line against it.

Lines 7 and 8 show z = 1. State 10 is the only state with z = 1, whatever x is.

Change g7 to and g7 (db, nb, x); and predict which rows change before you run it.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: AB=00 x=0 z=0 -> AB=00 AB=00 x=1 z=0 -> AB=01 AB=01 x=0 z=0 -> AB=00 AB=00 x=1 z=0 -> AB=01 AB=01 x=1 z=0 -> AB=11 AB=11 x=0 z=0 -> AB=10 AB=10 x=0 z=1 -> AB=10 AB=10 x=1 z=1 -> AB=00 AB=00 x=1 z=0 -> AB=01 AB=01 x=1 z=0 -> AB=11 AB=11 x=1 z=0 -> AB=10
Read included file: tb.sv
// tb.sv: the bench (read-only). From reset it feeds a stream that takes every (state, x) pair at least once.
module tb;
  logic clk = 0, rst = 1, x = 0;
  logic A, B;
  wire  z;
  mach dut (.clk(clk), .rst(rst), .x(x), .A(A), .B(B), .z(z));
  string stream = "01011001111";
  initial begin
    #1 clk = 1; #1 clk = 0; rst = 0;
    for (int i = 0; i < stream.len(); i++) begin
      x = (stream[i] == "1");
      #1 $write("AB=%b%b x=%b z=%b", A, B, x, z);
      #1 clk = 1; #1 clk = 0;
      $display("  ->  AB=%b%b", A, B);
    end
  end
endmodule

Check Yourself

ConceptA D flip-flop has D = A·B + x. What is its next-state equation?
ConceptA T flip-flop holds Q = 1 and its input T = x is 1. What is Q+?
ConceptA JK flip-flop has J = 0 and K = 0 and holds Q = 1. A student writes Q+ = 0. What went wrong?
Predict the outputThe lab netlist starts at AB = 00 and sees x = 0, 1, 1, 0, 1. The program applies A+ = Ax' + Bx and B+ = A'x at each edge and prints z = AB' after each edge. Predict the exact line.
module tb;
  logic A = 0, B = 0;
  string xs = "01101", z = "";
  initial begin
    for (int i = 0; i < xs.len(); i++) begin
      logic x;
      x = (xs[i] == "1");
      {A, B} = {(A & ~x) | (B & x), ~A & x};
      z = {z, (A & ~B) ? "1" : "0"};
    end
    $display("%s", z);
  end
endmodule
ConceptWhich row of the lab's transition table goes to the same next state for both input values?

Common Mistakes

Wrong Write the present state in the next-state column.

The table answers "where does the edge take it?" Copying the row label makes every state a self-loop.

Fix Evaluate each D (or J and K) for that row and that input, then apply the characteristic equation.

Wrong Use J as the next state of a JK flip-flop.

Q+ = JQ' + K'Q. With J = 0 and K = 0 the flop holds 1, but "J as D" clears it.

Fix Substitute J and K into JQ' + K'Q. Only a D flip-flop has Q+ = D.

Wrong Read a Moore output from the next state.

The output belongs to the present state, in the cycle before the edge. Reading it from the next state shifts every output one cycle early.

Fix Put the output in the row of the present state; for a Mealy output, in the row and the input column.

Wrong Update one flip-flop and use its new value to compute the other.

Every flop of a synchronous circuit loads at the same edge, from values that settled before it.

Fix Compute every next state from the same present state and input, then update all flops together.

Remember

  • Analysis runs: excitation equations, next-state equations, transition table, state table, state diagram.
  • Excitation equations read the present state and the inputs, from the gates in front of each flip-flop.
  • Q+ = D, Q+ = T ⊕ Q and Q+ = JQ' + K'Q turn them into next-state equations.
  • All flip-flops load together at the edge; compute every next state from the same present state.

Practice

Report a problem with this page