Analyzing a sequential circuit
Reverse engineering: from an unknown netlist back to behavior
Analyzing a sequential circuit is the reverse of designing one: starting from an unknown clocked netlist of flip-flops and gates, you read each flip-flop's input equations off the gates, substitute them into the flip-flop's characteristic equation to get every next-state bit, tabulate the result as a state table, draw the state diagram, and read off in words what the machine does.
In designing a sequence detector you went forwards: a plain-English spec became a state diagram, a state table, and finally gates plus flip-flops. This lesson runs that pipeline backwards. Someone hands you a clocked circuit with no documentation, a bank of flip-flops and a tangle of gates, and asks the only question that matters: *what does it do?* Recovering the answer is called sequential analysis, and it is exactly the finite state machine idea in reverse.
The setting is real. A decapped military chip, a competitor's controller, an undocumented board you inherited: the schematic is all you have, and you need its behavior. Because a synthesized machine is fully determined by its wiring, that behavior is always recoverable by one mechanical recipe. No guessing, just algebra and a table.
The five-step recipe
Analysis is synthesis with every arrow reversed. You start at the gates and end at a sentence:
- Read the flip-flop input equations off the gates. For each flip-flop, trace back from its input pin(s) through the combinational logic to get a boolean equation in the present-state bits and the external inputs. (A
Dflip-flop has one input equation; aJKhas two, one forJand one forK.) - Substitute into the characteristic equation. Plug those input equations into the flip-flop's characteristic equation to get the next-state bit, written
Q+, as a function of the present state and the inputs. This is the step that turns 'what feeds the flip-flop' into 'what the flip-flop becomes'. - Build the state table. List every combination of present-state bits and inputs, and fill in each next-state bit and each output from the equations. One row per (present state, input).
- Draw the state diagram. One bubble per state, one labelled arrow per (input to next-state) move, tagged with the output. This is the picture of the behavior.
- Describe what it does in words. Read the diagram like a story: which runs of input drive it where, and when the output fires. That sentence is the deliverable.
Recall the three characteristic equations from flip-flop types, because step 2 needs whichever matches the chip: D is
Q+ = D, JK is Q+ = J*Q' + K'*Q, and T is Q+ = T XOR Q (Q' means NOT Q). For a D flip-flop step 2 is trivial, the input equation *is* the next-state equation, which is exactly why D is the easy case. For JK and T the substitution does real work.The circuit we were handed
Here is a small unknown circuit to reverse engineer: **two
D flip-flops** named A and B (so the state is the two bits A B), one external input x, and one output y. Following the wires back from each flip-flop's D pin and from the output gate gives three equations. Note the feedback: the present outputs A and B loop back through the gates into the flip-flop inputs, which is what makes the circuit remember.D_A = A*x + B*x, D_B = A'*x, y = (A + B)*x'
In words:
A's D input is fed by an OR of two ANDs (A AND x, B AND x); B's D input is NOT A ANDed with x; and the output y is (A OR B) ANDed with NOT x. That is step 1 finished. Everything else follows from these three lines.Step 2: substitute into the characteristic equation
Both storage cells are
D flip-flops, so the characteristic equation is Q+ = D: whatever sits on the D input at the clock edge becomes the new output. Substituting is therefore just a rename, A+ = D_A and B+ = D_B:A+ = A*x + B*x, B+ = A'*x, y = (A + B)*x'
This is where the flip-flop *type* matters. Had these been
JK flip-flops with, say, gates giving J_A = B and K_A = x, step 2 would substitute into Q+ = J*Q' + K'*Q to get A+ = B*A' + x'*A, a genuinely different next-state equation than the raw inputs. For a T flip-flop with T_A = x you would write A+ = x XOR A. Always route the input equations through the right characteristic equation before you build the table, never straight into the next-state column (unless the cell is a D).Step 3: build the state table
Two flip-flops means
2^2 = 4 states, and one input means 2 input values, so the table has 8 rows. For each row, evaluate A+, B+, and y from the equations above. (Remember A' is NOT A, and x' is NOT x.)| A | B | x | A+ | B+ | y |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
A B and input x on the left; next state A+ B+ and output y on the right. Sample check, row A B x = 0 1 1: A+ = 0*1 + 1*1 = 1, B+ = A'*x = 1*1 = 1, y = (0+1)*x' = 1*0 = 0, giving next state 1 1, output 0. Notice y depends on x as well as the state, so this is a Mealy machine.You do not need to know the starting state to build this table: it lists every state, so it captures the machine no matter where it powers up. A reset input just picks which row you begin on. That is why analysis can ignore initial values that a running trace would care about.
Step 4: draw the state diagram
Four states means four bubbles:
00, 01, 11, 10. Copy each table row into an arrow: the arrow leaves the present-state bubble, its label is x / y (input that triggers it, over the output produced), and it points at the next-state bubble. Grouping the eight rows gives a strikingly simple shape:00 -(1/0)
→ 01 -(1/0)
→ 11 -(1/0)
→ 10 -(1/0)
→ 10 (a run of 1s walks the states)
and from every state: -(0/y)
→ 00, with y = 1 unless already at 00
So a
1 on the input marches the machine along the chain 00 -> 01 -> 11 -> 10 (and 10 loops on itself for further 1s), always with output 0. A 0 on the input snaps it straight back to the reset state 00, and on that return arrow the output y is 1 unless the machine was already sitting in 00. (The state codes happen to advance in Gray-code order, 00, 01, 11, 10, one bit changing per step, but that is incidental here.)Step 5: describe what it does
Read the diagram as behavior. The output
y is 1 exactly when the current input is 0 and the machine is not in state 00, and it lands in a non-00 state precisely after seeing one or more 1s. Put plainly: **y pulses 1 on the first 0 that follows a run of one or more 1s.** It marks the end of every burst of 1s. A second 0 in a row does nothing, because the first 0 already reset the machine to 00. Trace the stream x = 1 0 1 1 1 0 0 1 0 from reset (A B = 00):| Cycle | x | State A B (before edge) | y |
|---|---|---|---|
| 1 | 1 | 00 | 0 |
| 2 | 0 | 01 | 1 |
| 3 | 1 | 00 | 0 |
| 4 | 1 | 01 | 0 |
| 5 | 1 | 11 | 0 |
| 6 | 0 | 10 | 1 |
| 7 | 0 | 00 | 0 |
| 8 | 1 | 00 | 0 |
| 9 | 0 | 01 | 1 |
That sentence,
y marks the first 0 after each run of 1s, is the reverse-engineering result. From a pile of anonymous gates you now know precisely what the chip computes, and you could rebuild, verify, or defeat it. This is the same detective work that historically cracked machines like the Enigma: recover the state graph, then reason about the behavior it encodes.Common mistakes. Feeding the raw input equations into the state table without routing them through the characteristic equation first (only a
D cell lets you skip that; a JK or T does not). Swapping the present-state and next-state columns, or forgetting that the *present* outputs feed back into the *inputs*. Treating a Mealy output as Moore: here y depends on x, so it can change within a cycle as the input changes, not only at the clock edge. Computing the next state but forgetting the separate output equation. And do not invent an initial state, analysis describes all states at once; reset only chooses where a run begins.Analysis and synthesis are the two directions of the same map: synthesis goes spec -> state diagram -> table -> circuit, analysis goes circuit -> table -> state diagram -> spec. Being fluent both ways is what lets you verify that a built circuit matches its intended state machine (synthesize, then analyze the result and compare), reverse-engineer undocumented or hostile hardware, and debug a sequential design that misbehaves. The CPU's control unit is a finite state machine you can now read back from its gates, not just build.
Try it
You are handed a one-flip-flop circuit: a single
JK flip-flop Q with input x, whose gates give J = x and K = x'. Do steps 2 and 3, find the next-state equation Q+ and fill the 2-row-per-Q table, then say in one line what it does.Answer
Substitute into the
JK characteristic equation Q+ = J*Q' + K'*Q. With J = x and K = x', note K' = (x')' = x, so Q+ = x*Q' + x*Q = x*(Q' + Q) = x. The table: Q x = 00 -> 0, 01 -> 1, 10 -> 0, 11 -> 1. So Q+ = x: it simply loads x on every clock edge. In other words, this JK wiring (J = x, K = NOT x) is secretly a plain D flip-flop that copies the input. That is the payoff of always substituting into the characteristic equation: the true behavior hides in the algebra, not in the raw J/K wires.Frequently asked
How do you analyze a sequential circuit?
Follow five steps: (1) read each flip-flop's input equation(s) off the gates; (2) substitute them into the flip-flop's characteristic equation to get each next-state bit
Q+; (3) build a state table with one row per present-state-and-input combination, filling in next state and output; (4) draw the state diagram (a bubble per state, arrows labelled input over output); (5) describe in words what the machine does. It is finite-state-machine design run backwards.What is the difference between an input equation and a next-state equation?
An input equation describes what combinational logic feeds a flip-flop's input pin (for example
D_A = A*x + B*x, or a J and a K for a JK cell). A next-state equation describes what the flip-flop *becomes* after the clock edge, written Q+. You get the next-state equation by substituting the input equation into the flip-flop's characteristic equation. For a D flip-flop they coincide (Q+ = D); for JK (Q+ = J*Q' + K'*Q) and T (Q+ = T XOR Q) they differ.How do you analyze a circuit that uses JK flip-flops?
The same five-step recipe, but step 2 does real work. Read the
J and K input equations off the gates, then substitute both into the JK characteristic equation Q+ = J*Q' + K'*Q to get the next-state bit. For example J = B, K = x gives Q+ = B*Q' + x'*Q. Only after that substitution do you build the state table; feeding the raw J/K equations straight into the table is the classic analysis error.What is a state table?
A state table lists, for every combination of present-state bits and external inputs, the resulting next-state bits and outputs, one row each. It is the exhaustive record of a finite state machine's behavior: build it from the next-state and output equations during analysis, or fill it from a spec during design. The state diagram is just the same information drawn as bubbles and arrows.
Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →