Optimising Logic Circuits – Digital Logic Fundamentals (Senior 4 ICT) | Ganzaa

Digital Logic Fundamentals

Lessons

Senior 4 · ICT

Digital Logic Fundamentals

5 lessons

Lesson 5 of 5

Optimising Logic Circuits

25 min

Eight gates or four?

In lesson 4 the majority voter came out as $Y = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$ : 3 NOT gates, 4 three-input AND gates and a four-input OR gate, 8 gates in all. The same truth table can be produced by $Y = A B + B C + A C$ : three 2-input AND gates and one OR gate. Half the gates means a cheaper chip, less power and heat, a faster signal (it passes through fewer gates) and fewer parts that can fail. Optimising a circuit means finding the simplest expression with the same truth table. There are two tools: the laws of Boolean algebra, and the Karnaugh map.

Definition

Equivalent expressions: expressions with identical truth tables. Simplification: replacing an expression by an equivalent one with fewer terms and fewer variables per term.

Karnaugh map (K-map): a truth table drawn as a grid in which neighbouring cells differ in exactly one input, so that 1s that can be combined sit next to each other. Its rows and columns follow Gray code order (00, 01, 11, 10), not counting order.

The laws of Boolean algebra

Law	OR form	AND form
Identity	$A + 0 = A$	$A \cdot 1 = A$
Null (annulment)	$A + 1 = 1$	$A \cdot 0 = 0$
Idempotent	$A + A = A$	$A \cdot A = A$
Complement	$A + \overline{A} = 1$	$A \cdot \overline{A} = 0$
Double negation	$\overline{\overline{A}} = A$
Commutative	$A + B = B + A$	$A \cdot B = B \cdot A$
Associative	$(A + B) + C = A + (B + C)$	$(A B) C = A (B C)$
Distributive	$A + B C = (A + B) (A + C)$	$A (B + C) = A B + A C$
Absorption	$A + A B = A$	$A (A + B) = A$
Redundancy	$A + \overline{A}B = A + B$	$A(\overline{A} + B) = AB$
De Morgan	$\overline{A + B} = \overline{A} \cdot \overline{B}$	$\overline{A \cdot B} = \overline{A} + \overline{B}$

Any law can be proved with a truth table. For De Morgan's AND form, $\overline{A \cdot B}$ and $\overline{A} + \overline{B}$ both give 1, 1, 1, 0 in the rows 00, 01, 10, 11. In words: break the bar and change the sign. De Morgan's laws also show how to build any circuit from NAND gates alone, for example $AB + CD = \overline{\overline{AB} \cdot \overline{CD}}$ , which is two NANDs feeding a third.

Worked example 1: simplify the majority voter with algebra

$Y = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$

Idempotent law: $A B C = A B C + A B C + A B C$ , so the term $A B C$ can be used three times: $Y = (\overline{A}BC + ABC) + (A\overline{B}C + ABC) + (AB\overline{C} + ABC)$
Distributive law, taking out the common factor in each bracket: $Y = BC(\overline{A} + A) + AC(\overline{B} + B) + AB(\overline{C} + C)$
Complement law, $X + \overline{X} = 1$ , then identity: $Y = B C + A C + A B$

Gates: 8 before, 4 after; gate inputs: 19 before (3 + 12 + 4), 9 after (6 + 3).

Worked example 2: a shorter one

Simplify $Y = \overline{A}\,\overline{B} + \overline{A}B + AB$ .

$Y = \overline{A}(\overline{B} + B) + AB = \overline{A} \cdot 1 + AB = \overline{A} + AB$

By the redundancy law in the form $\overline{A} + AB = \overline{A} + B$ : $Y = \overline{A} + B$

Check by truth table: $Y = 0$ only when $A = 1, B = 0$ , and $\overline{1} + 0 = 0$ . Three terms became one NOT and one OR.

Karnaugh maps

Algebra needs the right law at the right moment. A K-map makes the grouping visible.

Draw the grid: for 3 inputs, 2 rows ( $A$ ) by 4 columns ( $B C$ in the order 00, 01, 11, 10). Neighbouring cells, including the left and right edges, differ in one bit.
Copy the 1s from the truth table into their cells.
Loop the 1s in rectangles of 1, 2, 4 or 8 cells, as large as possible and as few as possible. Loops may overlap and may wrap around from the right edge to the left.
Each loop gives one AND term: keep only the variables that do not change inside the loop.
OR the terms.

The same answer as worked example 1, in three loops and no algebra.

Worked example 3: a loop that wraps around

A function is 1 in rows 000, 010, 100 and 110, and 0 elsewhere. On the K-map:

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

Columns 00 and 10 are neighbours (they differ only in $B$ ), because the map wraps from the right edge to the left. One loop of four cells covers all the 1s. Inside it, $A$ and $B$ both change, and $C = 0$ throughout, so $Y = \overline{C}$ Four minterms become a single NOT gate.

python

# Check that the simplified majority voter is equivalent to the original.
from itertools import product

def original(A, B, C):
    return (not A and B and C) or (A and not B and C) or (A and B and not C) or (A and B and C)

def simplified(A, B, C):
    return (A and B) or (B and C) or (A and C)

for A, B, C in product((0, 1), repeat=3):
    print(A, B, C, int(bool(original(A, B, C))), int(bool(simplified(A, B, C))))

same = all(bool(original(*row)) == bool(simplified(*row)) for row in product((0, 1), repeat=3))
print("Equivalent:", same)

Code Explanation

Press Run. The program prints both outputs for all 8 input rows and then Equivalent: True. A computer can test equivalence this way for small circuits; for big ones, engineers use optimisation software, but it applies the same laws.

Computer Science Lessons: Karnaugh Maps, Simplify Boolean Expressions. Watch how the cells are ordered, how the loops are drawn, and how each loop is read as a term, then redo the majority-voter map yourself.

Warning

Loops must be rectangles of 1, 2, 4 or 8 cells. A loop of 3 cells, or a diagonal pair, is not allowed: the cells in it do not share a simpler term.

Keep the Gray-code order. Columns in counting order (00, 01, 10, 11) put 01 next to 10, which differ in two bits, and the map gives wrong groups.

De Morgan changes the sign too. $\overline{A + B}$ is $\overline{A} \cdot \overline{B}$ , not $\overline{A} + \overline{B}$ .

Tip

Test the answer, not the method. After simplifying, check two or three rows of the original truth table, especially a row where the output is 0. A wrong simplification nearly always fails on one of them.

✦

Practice

Simplify: (a) $A + A B$ ; (b) $A \cdot \overline{A} + B$ ; (c) $(A + B)(A + \overline{B})$ .
Use De Morgan's law to write $\overline{A + B + C}$ without a bar over a sum.
Prove $A + \overline{A}B = A + B$ with a truth table.
Simplify $Y = AB + A\overline{B} + \overline{A}B$ with algebra, and name the single gate that does the job.
Draw a 3-variable K-map for $Y = 1$ in rows 001, 011, 101, 111, and simplify.
Use a K-map to simplify $Y = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}B\overline{C} + A\overline{B}\,\overline{C} + A\overline{B}C$ .
How many gates does $Y = \overline{A}B + AB$ need as written, and how many after simplifying?
A student loops the two cells 01 and 10 of row $A = 1$ in a K-map, saying "they are both 1, so they make $A$ ". Evaluate the claim.

Show answersHide answers

(a) $A$ (absorption). (b) $0 + B = B$ . (c) $A + B\overline{B} = A + 0 = A$ (distributive, OR form).
$\overline{A} \cdot \overline{B} \cdot \overline{C}$ .
Rows (A, B): 00: 0 and 0; 01: 1 and 1; 10: 1 and 1; 11: 1 and 1. The columns are equal, so the law holds.
$A(B + \overline{B}) + \overline{A}B = A + \overline{A}B = A + B$ : a single OR gate.
All four 1s are in columns 01 and 11 ( $C = 1$ ), both rows: one loop of four; $Y = C$ .
1s at 000, 010, 100, 101. Loop the wrap-around pair 000 and 010 in row 0 (columns 00 and 10): $\overline{A}\,\overline{C}$ . Loop 100 and 101 (row 1, columns 00 and 01): $A\overline{B}$ . Also 000 and 100 (column 00) could be looped as $\overline{B}\,\overline{C}$ , but it is not needed. $Y = \overline{A}\,\overline{C} + A\overline{B}$ .
As written: 1 NOT, 2 AND, 1 OR = 4 gates. Simplified: $B(\overline{A} + A) = B$ , so no gates at all: a plain wire from $B$ .
Wrong. Columns 01 and 10 are not neighbours (they differ in both $B$ and $C$ ), so the loop is not allowed. Each cell must be looped separately or with a real neighbour; with only those two 1s in the row the terms are $A\overline{B}C$ and $AB\overline{C}$ .

Quick check

Which expression is equal to NOT(A AND B), by De Morgan's law?

Key points

Fewer gates means a cheaper, faster, cooler and more reliable circuit.
Key laws: complement $A + \overline{A} = 1$ , absorption $A + A B = A$ , redundancy $A + \overline{A}B = A + B$ , De Morgan $\overline{A \cdot B} = \overline{A} + \overline{B}$ and $\overline{A + B} = \overline{A} \cdot \overline{B}$ .
K-map: Gray-code order; loop 1s in rectangles of 1, 2, 4 or 8, as large and as few as possible, wrapping around the edges; keep the variables that do not change.
Always check the simplified expression against the original truth table.

1Eight gates or four?

2The laws of Boolean algebra

3Karnaugh maps

Eight gates or four?

The laws of Boolean algebra

Karnaugh maps