Analysing a Combinational Circuit

Find what an unknown gate circuit computes by naming every net, writing its equation and building the truth table.

You Will Be Able To

  • Label every internal net of a gate circuit.
  • Write the equation of each net from the inputs to the outputs.
  • Build the truth table one net at a time and simplify the result.
  • Check an analysis by simulation.
Lesson
G2.9
Time
20 min
Runs on
Your browser
Check
5 questions

A netlist of four NAND gates arrives with no comment. A reviewer has to say what it does before it ships. Naming each net and writing its column, one net at a time, answers the question.

Every Net of the Circuit, One Input Row per StepOne row per step, abs from 000 to 111. Each line is one net, in the order the analysis finds it.
01234567a b s000001010011100101110111n1 = (ss)'n3 = (bs)'n2 = (a·n1)'y = (n2·n3)'s = 1: y copies b
Scroll horizontally ↔
  1. Cycle 0

    s is 0, so n1 = 1. Then n2 = a' and n3 = 1, and y = a. Here y is 0.

  2. Cycle 1

    s is 1, so n1 = 0 and n2 = 1. Then n3 = b', and y = b. Here b is 0, so y is 0.

  3. Cycle 4

    a is 1 and s is 0: y is 1. With s = 0 the output follows a.

  4. Cycle 7

    Every row agrees with as' + bs: s selects b, and s' selects a.

Computed from the net equations and confirmed by the lab below on Icarus.

The Method in Four Steps

Analysis is the opposite of design. You have the gates and you want the function. The same four steps work for any circuit without feedback.

From a Netlist to a Named FunctionArrows show the order of the work. Each step uses only what the steps before it found.
  • Step
  • Structure
CallValueReturnWaiting
From a netlist to a named functionArrows show the order of the work. Each step uses only what the steps before it found. step Label name every internalnet step Equations one per net, in levelorder step Truth table one column per net step Simulate the same columns froma run namesevaluatecompare
  1. step Labelname every internal net
    • names → Equations
  2. step Equationsone per net, in level order
    • evaluate → Truth table
  3. step Truth tableone column per net
    • compare → Simulate
  4. step Simulatethe same columns from a run
  1. Label

    Give every gate output a name. Here: n1, n2, n3 and y.

    Follow the calls, values and waits
    1. data n1 n2 n3 y: Label → Equations
  2. Equations

    Write each net from its gate, using only inputs and nets already written.

    Follow the calls, values and waits
    1. data y = (n2·n3)': Equations → Truth table
  3. Table and check

    Fill one column per net. The y column, 00011011, must match a simulation of the netlist.

    Follow the calls, values and waits
    1. data 00011011: Truth table → Simulate
Read the diagram as text
  • Label: name every internal net
  • Equations: one per net, in level order
  • Truth table: one column per net
  • Simulate: the same columns from a run
  • Label → Equations: names
  • Equations → Truth table: evaluate
  • Truth table → Simulate: compare

The level of a gate is one more than the highest level among its inputs. Inputs are level 0.

Four NAND Gates to Analyse
Four NAND Gates to Analyseg1 · NANDn1=0g2 · NANDn2=1g3 · NANDn3=1g4 · NANDy=0a=1b=0s=1
a=1 b=0 s=1
g1 · NANDs=1, s=1 → n1=0
g2 · NANDa=1, n1=0 → n2=1
g3 · NANDb=0, s=1 → n3=1
g4 · NANDn2=1, n3=1 → y=0
Read the connections
GateKindInputsOutput
g1NANDs, sn1
g2NANDa, n1n2
g3NANDb, sn3
g4NANDn2, n3y

Outputs: y. 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 20. Settled after 20 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617181920yxxx111111111111111110
Scroll horizontally ↔
Every computed frame
Timey
0x
1x
2x
31
41
51
61
71
81
91
101
111
121
131
141
151
161
171
181
191
200

  1. Step 4 · a = 1, b = 0, s = 0. Here n1 = 1, n2 = 0 and n3 = 1. So y = (0·1)' = 1, which equals a.
  2. Step 10 · b rises. With s = 0, n3 stays 1 whatever b does. So y does not move: b is not selected.
  3. Step 16 · s rises. Now n1 falls, so n2 rises. The net n3 falls, because b is 1. So y = (1·0)' = 1, which equals b.
  4. Step 22 · b falls. The net n3 rises, and y falls to 0. With s = 1 the output follows b.

Every gate takes one gate delay. Click a pin to try your own rows.

Equations Net by Net

Write the nets in level order. Each equation first uses the names of the nets it reads. Then substitute until only inputs are left.

NetGateIn netsIn inputsLevel
n1NAND(s, s)(ss)'s'1
n3NAND(b, s)(bs)'(bs)'1
n2NAND(a, n1)(a·n1)'(as')'2
yNAND(n2, n3)(n2·n3)'((as')'(bs)')'3

n1 and n3 are fed only by inputs, so they come first. y comes last.

Now simplify y by De Morgan: ((as')'(bs)')' = as' + bs. When s is 0, y = a. When s is 1, y = b. The circuit is a 2:1 multiplexer.

The Truth Table, One Column per Net

Fill the table column by column, in the same order as the equations. Each column needs only the columns to its left.

a b sn1n3n2y
0001110
0010110
0101110
0110011
1001101
1010110
1101101
1110011

The y column is 00011011: Σm(3, 4, 6, 7). The lab prints the same columns.

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

    Name every gate output, write each one's equation in level order, and fill a truth table one net at a time. Then simplify, name the function and confirm it with a simulation.

  2. What makes a circuit combinational?

    Its outputs depend only on the present inputs. It has no feedback loop and no storage, so the analysis can go level by level from the inputs.

  3. Four NAND gates: s feeds an inverter, two NANDs combine the data with s and s', and a last NAND joins them. What is it?

    A 2:1 multiplexer: y = as' + bs. It is the NAND-NAND form of a sum of products, so bubble pushing turns it into AND-OR directly.

Try It

The program builds the four NAND gates as primitives and prints every net on every row.

Compare each line with your own table. n1 is s', n2 is (as')', n3 is (bs)', and y is as' + bs.

Change g2 to and and run again. Watch which rows of y change: misreading one gate spoils every net after it.

Reorder the loop to {s, a, b} = m[2:0];. The same circuit now prints its rows in a different order.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: a b s = 000: n1 1 n2 1 n3 1 y 0 a b s = 001: n1 0 n2 1 n3 1 y 0 a b s = 010: n1 1 n2 1 n3 1 y 0 a b s = 011: n1 0 n2 1 n3 0 y 1 a b s = 100: n1 1 n2 0 n3 1 y 1 a b s = 101: n1 0 n2 1 n3 1 y 0 a b s = 110: n1 1 n2 0 n3 1 y 1 a b s = 111: n1 0 n2 1 n3 0 y 1

Check Yourself

ConceptIn what order should you write the net equations of a circuit?
Conceptg1 = NAND(a, b) and y = NOR(g1, c). For which input rows abc is y = 1?
ConceptAn analysis reads a NAND gate as an AND gate. What happens to the nets after it?
ConceptWhat does y = ((as')'(bs)')' simplify to?
Predict the outputThe lab circuit gets a = 1, b = 0 and then s = 0 and s = 1. Predict the exact line.
module tb;
  logic a = 1, b = 0, s;
  wire  n1, n2, n3, y;
  nand g1 (n1, s, s);
  nand g2 (n2, a, n1);
  nand g3 (n3, b, s);
  nand g4 (y, n2, n3);
  initial begin
    s = 0; #1 $write("%b", y);
    s = 1; #1 $display("%b", y);
  end
endmodule

Common Mistakes

Wrong Work on the output equation before the nets that feed it.

An equation can only use nets that are already known. Starting at the output leaves unknowns in it.

Fix Go in level order: first the gates fed only by inputs, then the gates fed by those, and so on.

Wrong Misread one gate, for example a NAND as an AND.

One wrong net spoils every net after it. Here a misread g2 inverts n2 and changes six of the eight rows of y.

Fix Write each gate's equation beside the gate, then check its column on two rows by hand.

Wrong Number the rows in a different variable order from the one stated.

The column of y depends on the order of the inputs. With s first, the same table lists the rows differently.

Fix Fix the order before you start, and keep it in the table and in the bench.

Wrong Stop at the raw equation.

((as')'(bs)')' is correct but hides the job of the circuit. Simplified, it is as' + bs: a multiplexer.

Fix Push the bubbles and simplify. Then name the function if you can.

Remember

  • Label every net, then write the equations in level order: inputs first, outputs last.
  • Fill the truth table one column per net, left to right.
  • Simplify the output equation and name the function if you can.
  • Check the analysis with a simulation of the same netlist.

Practice

Report a problem with this page