Chapter 11 of 32

Combinational Circuit Design

So far we have collected tools: gates, Boolean algebra, canonical forms, Karnaugh maps, don't-cares and the Quine-McCluskey method. In this chapter we put them together and answer the practical question: given a word problem, how do you end up with a working circuit? And the reverse: given a circuit someone else drew, how do you find out what it does?

Every block in the next chapters (adders, subtractors, multiplexers, decoders, comparators, code converters) is designed with exactly the procedure you learn here, so it is worth getting it right once.

A combinational circuit is a logic circuit whose outputs at any instant depend only on the values of its inputs at that same instant. It contains no memory elements and no feedback paths.

The opposite is a sequential circuit, whose outputs also depend on the past (stored state). Sequential circuits start with the chapter Latches. Because a combinational circuit has no memory, it is completely described by a truth table: for n inputs, 2n rows tell you everything.

             +---------------------------+
  x1 ------->|                           |-------> z1
  x2 ------->|   combinational circuit   |-------> z2
  ...        |   (gates only, no loops)  |  ...
  xn ------->|                           |-------> zm
             +---------------------------+
   n inputs        zi = fi(x1, ..., xn)         m outputs

Combinational vs Sequential at a Glance

Point

Combinational

Sequential

Output depends on

Present inputs only

Present inputs and stored state

Memory elements

None

Latches / flip-flops

Feedback

No feedback paths

Has feedback

Clock

Not needed

Usually needed (synchronous circuits)

Described by

Truth table / Boolean equations

State table / state diagram

Examples

Adder, multiplexer, decoder, comparator

Register, counter, sequence detector


The Design Procedure

Designing a combinational circuit is a fixed recipe. Memorise these steps; university exams often ask for them directly.

  1. Understand the specification. Read the word problem and decide what the inputs and outputs are. Give each one a name and decide what 0 and 1 mean (for example, "1 = sensor detects a car").

  2. Write the truth table. One row for every input combination; one column for every output. Mark impossible or irrelevant input combinations as don't-cares (x).

  3. Simplify each output. Use a K-map (up to 4 or 5 variables), Quine-McCluskey (more variables) or algebra. Use the don't-cares.

  4. Choose the implementation. AND-OR, NAND-NAND, OR-AND, NOR-NOR, or a multi-level form. Share gates between outputs if possible.

  5. Draw the logic diagram and check practical limits: available gate types, fan-in, propagation delay.

  6. Verify. Check the circuit against the truth table for every row, by hand for small circuits or by simulation.

Why this order? Step 2 is where most mistakes happen: once the truth table is right, steps 3 to 5 are mechanical. So spend your time on the specification and the table.


Worked Example 1: A Majority Voting Circuit

Specification. Three judges A, B and C each press a button (1 = "pass"). A contestant passes if at least two judges press their button. Design the circuit for the output F.

Step 1. Inputs A, B, C; output F (1 = pass).

Step 2. Truth table: F is 1 when two or three inputs are 1.

Row

A

B

C

F

0

0

0

0

0

1

0

0

1

0

2

0

1

0

0

3

0

1

1

1

4

1

0

0

0

5

1

0

1

1

6

1

1

0

1

7

1

1

1

1

Step 3. F = Σm(3, 5, 6, 7). On the K-map, minterm 7 pairs with each of 3, 5 and 6:

         BC
  A     00   01   11   10
  0  |  0  |  0  |  1  |  0  |
  1  |  0  |  1  |  1  |  1  |

  pair (3,7) → BC     pair (5,7) → AC     pair (6,7) → AB

  F = AB + BC + AC

Step 4 and 5. Three 2-input AND gates feeding one 3-input OR gate: 4 gates, 9 gate inputs, 2 gate delays. Keep this function in mind: in Half & Full Adders you will meet it again as the carry output of a full adder.


Worked Example 2: Using Don't-Cares (BCD Prime Detector)

Specification. The input is one BCD digit ABCD (A is the MSB, values 0 to 9 only). Output F = 1 when the digit is a prime number.

The primes below 10 are 2, 3, 5 and 7. The codes 1010 to 1111 never appear on a BCD input, so they are don't-cares (see K-Maps with Don't-Care Conditions).

F(A, B, C, D) = Σm(2, 3, 5, 7) + d(10, 11, 12, 13, 14, 15)

           CD
  AB      00   01   11   10
  00   |  0  |  0  |  1  |  1  |      m0  m1  m3  m2
  01   |  0  |  1  |  1  |  0  |      m4  m5  m7  m6
  11   |  x  |  x  |  x  |  x  |      m12 m13 m15 m14
  10   |  0  |  0  |  x  |  x  |      m8  m9  m11 m10

  Quad (5, 7, 13, 15)  → BD
  Quad (2, 3, 10, 11)  → B′C

  F = BD + B′C

Without the don't-cares we would have needed F = A′BD + A′B′C, with an extra literal in each term. Check a few rows by hand: digit 1 (0001) gives 0 + 0 = 0 (1 is not prime, correct); digit 6 (0110) gives 0 + 0 = 0; digit 9 (1001) gives 0 + 0 = 0; digit 5 (0101) gives 1. Correct.

Choosing the Implementation: NAND-NAND

As we saw in Universal Gates: NAND & NOR, any two-level AND-OR circuit becomes a NAND-NAND circuit by replacing every gate with a NAND (double complementation):

F = BD + B′C = ((BD)′ · (B′C)′)′

  B ---[NAND as NOT]--- B′
  B, D  ---[NAND]--- (BD)′  ---+
                               +---[NAND]--- F
  B′, C ---[NAND]--- (B′C)′ ---+

Total: 4 two-input NAND gates (one used as an inverter).

If the complemented input B′ is already available (many textbook problems assume "both polarities of every input are available"), you need only 3 NAND gates.


Worked Example 3: A Multiple-Output Circuit (2-bit Multiplier)

Specification. Multiply two 2-bit unsigned numbers A = A1A0 and B = B1B0. The largest product is 3 × 3 = 9 = 1001, so we need 4 output bits P3P2P1P0.

Step 2. With the row number = A1A0B1B0 read as a 4-bit number, list where each output bit is 1:

Row  A × B   P3 P2 P1 P0        Row  A × B   P3 P2 P1 P0
 0   0 × 0   0  0  0  0          8   2 × 0   0  0  0  0
 1   0 × 1   0  0  0  0          9   2 × 1   0  0  1  0
 2   0 × 2   0  0  0  0         10   2 × 2   0  1  0  0
 3   0 × 3   0  0  0  0         11   2 × 3   0  1  1  0
 4   1 × 0   0  0  0  0         12   3 × 0   0  0  0  0
 5   1 × 1   0  0  0  1         13   3 × 1   0  0  1  1
 6   1 × 2   0  0  1  0         14   3 × 2   0  1  1  0
 7   1 × 3   0  0  1  1         15   3 × 3   1  0  0  1

P0 = Σm(5, 7, 13, 15)
P1 = Σm(6, 7, 9, 11, 13, 14)
P2 = Σm(10, 11, 14)
P3 = Σm(15)

Step 3. Minimising each output separately with K-maps gives:

P0 = A0·B0
P1 = A1·B0·A0′ + A1·B0·B1′ + A0·B1·A1′ + A0·B1·B0′
P2 = A1·B1·A0′ + A1·B1·B0′
P3 = A1·A0·B1·B0

Two-level cost (ignoring inverters): P0 needs 1 gate, P1 needs 4 AND3 + 1 OR4, P2 needs 2 AND3 + 1 OR2, P3 needs 1 AND4. That is 10 gates and 30 gate inputs, with a delay of 2 gate levels (plus inverters).

A Better Idea: Think About the Structure

Do the multiplication the way you do it on paper. The partial products are single-bit ANDs, and the columns are added with half adders (a half adder outputs sum = x ⊕ y and carry = xy; the next chapter derives it):

                  A1     A0
            ×     B1     B0
           -----------------
                A1B0   A0B0
         A1B1   A0B1
         ------------------------
   P3     P2     P1     P0

P0 = A0B0
P1 = A1B0 ⊕ A0B1          carry c1 = (A1B0)(A0B1)
P2 = A1B1 ⊕ c1
P3 = (A1B1) · c1

This uses 4 AND gates for the partial products plus 2 half adders (2 XOR + 2 AND): 8 gates and 16 gate inputs, and no inverters. The price is depth: the path A1B0 → c1 → P3 goes through 3 gates. This is the classic two-level versus multi-level trade-off: two-level forms are fastest, multi-level forms are usually smaller. Real synthesis tools explore both.

Verifying the Design by Simulation

Hardware engineers describe designs in a hardware description language (HDL) and simulate them against every input before building anything. Here is the multi-level multiplier in SystemVerilog with a testbench that tries all 16 input combinations and compares with the true product:

module mul2 (input  logic [1:0] a, b,
             output logic [3:0] p);
  logic c1;                            // carry from bit 1 to bit 2
  assign p[0] = a[0] & b[0];
  assign p[1] = (a[1] & b[0]) ^ (a[0] & b[1]);
  assign c1   = (a[1] & b[0]) & (a[0] & b[1]);
  assign p[2] = (a[1] & b[1]) ^ c1;
  assign p[3] = (a[1] & b[1]) & c1;
endmodule

module tb;
  logic [1:0] a, b;
  logic [3:0] p;
  int errors = 0;
  mul2 dut (.a(a), .b(b), .p(p));
  initial begin
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) begin
        a = i; b = j; #1;
        $display("%0d x %0d = %b (%0d)", a, b, p, p);
        if (p !== i * j) errors++;
      end
    $display("errors = %0d", errors);
  end
endmodule

Output (Icarus Verilog, iverilog -g2012 mul2.sv && vvp a.out):

0 x 0 = 0000 (0)
0 x 1 = 0000 (0)
0 x 2 = 0000 (0)
0 x 3 = 0000 (0)
1 x 0 = 0000 (0)
1 x 1 = 0001 (1)
1 x 2 = 0010 (2)
1 x 3 = 0011 (3)
2 x 0 = 0000 (0)
2 x 1 = 0010 (2)
2 x 2 = 0100 (4)
2 x 3 = 0110 (6)
3 x 0 = 0000 (0)
3 x 1 = 0011 (3)
3 x 2 = 0110 (6)
3 x 3 = 1001 (9)
errors = 0

Every assign statement is one piece of combinational logic: the output is recomputed whenever any input on the right-hand side changes. That is exactly the definition of a combinational circuit. The #1 in the testbench just lets the values settle before printing.


The Analysis Procedure

Analysis is design in reverse: you are given a logic diagram and must find what it does.

  1. Label the output of every gate with a name (T1, T2, ...).

  2. Starting from the inputs, write the Boolean expression of each gate in terms of the inputs and earlier labels.

  3. Substitute to get each output as a function of the inputs only.

  4. Build the truth table (or simplify) and describe the function in words.

Worked Example 4: Analysing a Circuit

A circuit has inputs A, B, C and the gates below. What does it compute?

A ──[NOT]── A′ ──┐
                 [AND]── T1 = A′B ─────────┐
B ───────────────┘                         │
                                           │
B ──[NOT]── B′ ──┐                         ├──[OR]── F
                 [AND]── T2 = B′C ─────────┤
C ───────────────┘                         │
                                           │
A ───────────────┐                         │
                 [AND]── T3 = AC ──────────┘
C ───────────────┘

Tabulate the intermediate signals for all 8 rows:

A

B

C

T1 = A′B

T2 = B′C

T3 = AC

F

0

0

0

0

0

0

0

0

0

1

0

1

0

1

0

1

0

1

0

0

1

0

1

1

1

0

0

1

1

0

0

0

0

0

0

1

0

1

0

1

1

1

1

1

0

0

0

0

0

1

1

1

0

0

1

1

So F = Σm(1, 2, 3, 5, 7). A K-map shows the 1s at 1, 3, 5, 7 form a quad (C), and 2, 3 form a pair (A′B):

F = A′B + B′C + AC  =  C + A′B

The circuit the designer drew uses 6 gates (2 NOT, 3 AND, 1 OR); the same function needs only an inverter, one AND and one OR. Analysis is how you catch such waste, and it is also how you check a design you have just made.


Measuring a Design: Cost and Delay

"Simplest" can mean different things. Textbooks and exam questions use these measures:

Measure

What it counts

Example: F = AB + BC + AC

Literal count

Total appearances of variables in the expression

6

Gate count

Number of gates (inverters often excluded; say which)

4

Gate-input count

Sum of the inputs of all gates; closest to transistor count

3 × 2 + 3 = 9

Levels (depth)

Gates on the longest input-to-output path

2

Propagation delay

Time for the slowest path, sum of the gate delays along it

tAND + tOR

Propagation Delay of a Path

The propagation delay of a combinational circuit is the delay of its critical path: the input-to-output path with the largest total gate delay.

For the prime detector built as NAND-NAND with an inverter for B′, the paths are:

B → NOT → NAND → NAND → F      3 gate delays   (critical path)
B → NAND → NAND → F            2 gate delays
C → NAND → NAND → F            2 gate delays
D → NAND → NAND → F            2 gate delays

If every gate has a delay of 10 ns, the circuit delay is 3 × 10 = 30 ns.
If B′ is supplied directly from the source, the delay drops to 20 ns.

When gates have different delays, add the actual delays along each path and take the maximum. For example, with tNOT = 5 ns and tNAND = 10 ns, the paths above take 25 ns and 20 ns, so the circuit delay is 25 ns. Until the critical path has settled, the output may show wrong temporary values (glitches); the chapter Hazards in Combinational Circuits deals with that.

Practical Constraints

  • Fan-in: a gate can only have so many inputs (in CMOS, gates with more than about 4 inputs get slow). A 6-input AND may need to be built from two levels of smaller gates, adding delay.

  • Fan-out: one gate output can drive only a limited number of gate inputs before it slows down or fails to give valid logic levels; Logic Families: TTL & CMOS gives the numbers.

  • Available gate types: chips and cell libraries favour NAND and NOR, so designs are converted to NAND-NAND or NOR-NOR form.

  • Shared terms: in a multiple-output circuit, a product term used by two outputs is built once.


Common Mistakes

  • Skipping the truth table. Jumping straight from words to an equation is the most common source of wrong answers. Write the table, even for 3 inputs.

  • Forgetting don't-cares. If some input combinations cannot occur (like BCD 1010 to 1111), mark them x and use them; you lose marks for a non-minimal answer.

  • Treating don't-cares as 1s in the final check. A don't-care may come out as 0 or 1 in your circuit; that is fine. But never let a real 0 become 1.

  • Minimising multiple outputs separately and stopping there. Look for product terms shared between outputs.

  • Counting delay as "number of gates in the circuit". Delay is the number (or sum of delays) of gates on the longest path, not the total gate count.

  • Forgetting the inverters in a delay or cost count. If complemented inputs are not available, inverters add a level.

  • Calling a circuit with a feedback loop combinational. Any loop from an output back to an input of the same circuit can create memory; that makes it sequential.


GATE and Interview Questions

Q1. What are the steps in designing a combinational circuit?

(1) Identify inputs and outputs from the specification and assign symbols; (2) derive the truth table; (3) obtain simplified Boolean expressions for each output (K-map / Quine-McCluskey, using don't-cares); (4) choose the gate implementation and draw the logic diagram; (5) verify the circuit against the truth table.

Q2. A circuit's output is 1 when its 4-bit unsigned input is divisible by 3 (0 counts as divisible). Write F in Σm form and minimise it.

Multiples of 3 up to 15: 0, 3, 6, 9, 12, 15. So F = Σm(0, 3, 6, 9, 12, 15). On the K-map no two of these minterms are adjacent (any two differ in at least 2 bits), so no grouping is possible and the minimal SOP keeps all 6 minterms: F = A′B′C′D′ + A′B′CD + A′BCD′ + AB′C′D + ABC′D′ + ABCD.

Q3. A BCD digit ABCD is the input. Design F = 1 when the digit is 5 or more.

F = Σm(5, 6, 7, 8, 9) + d(10 to 15). The K-map gives F = A + BD + BC. Without don't-cares the answer would be F = AB′C′ + A′BD + A′BC, which is far larger.

Q4. In a circuit every gate has a delay of 2 ns. Input X passes through a NOT, an AND and an OR to reach the output; input Y passes through an AND and an OR. What is the propagation delay of the circuit?

The critical path is X → NOT → AND → OR: 3 × 2 = 6 ns. The circuit delay is set by the slowest path, not the fastest.

Q5. Why might a designer choose a multi-level circuit over a two-level one?

Multi-level circuits can share sub-expressions and usually need fewer gates and gate inputs (smaller area and power), and they avoid very wide gates. Two-level circuits are faster (only 2 gate delays). The 2-bit multiplier in this chapter needs 10 gates in two-level form but only 8 in multi-level form, at the cost of 3 levels of delay.

Q6. How many rows does the truth table of a combinational circuit with 6 inputs and 3 outputs have?

26 = 64 rows. The number of outputs only adds columns.


Summary

  • A combinational circuit's outputs depend only on current inputs; it has no memory and no feedback, and a truth table describes it completely.

  • Design: specification → name inputs/outputs → truth table (with don't-cares) → minimise → choose gate form → draw → verify.

  • Analysis: label gate outputs → write expressions → substitute → truth table → describe the function.

  • Worked results: majority F = AB + BC + AC; BCD prime detector F = BD + B′C; 2-bit multiplier P0 = A0B0, P1 = A1B0 ⊕ A0B1, P2 = A1B1 ⊕ c1, P3 = A1B1c1.

  • Measure a design by literals, gates, gate inputs, levels and critical-path delay. Two-level = fast; multi-level = small.

  • Next, Half & Full Adders applies this procedure to the most important combinational block of all.