Digital Logic Fundamentals

Lessons

Senior 4 · ICT

Digital Logic Fundamentals

5 lessons

Lesson 3 of 5

Logic Circuit Design

25 min

How does a computer add?

In lesson 1 you added binary numbers column by column: in each column, 1 + 1 gives a sum bit of 0 and a carry of 1. A processor does exactly this, billions of times a second, with a small circuit of gates for each column. In this lesson you learn to read and draw such circuits, and you design the first piece of a computer's adder yourself.

Definition

Logic circuit: gates joined by wires so that the outputs of some gates are the inputs of others. In a combinational circuit the outputs depend only on the present inputs (no memory).

Intermediate output: the output of a gate inside the circuit, labelled with a letter (P, Q) so that the circuit can be analysed step by step.

Junction: a dot where wires are joined. Wires that cross without a dot are not connected.

From expression to circuit

Read the expression the way it is evaluated: brackets, then NOT, then AND, then OR. Each operation is one gate, and the operation done last is the gate that gives the output.

Write the inputs on the left.
Draw a gate for each NOT, then each AND, then the final OR (or whatever is done last).
Join each gate's inputs to the right wires, and label each intermediate output with what it computes.

For $Y = A \cdot B + \overline{C}$ , the last operation is the OR, so an OR gate gives $Y$ . Its two inputs are $A \cdot B$ (an AND gate) and $\overline{C}$ (a NOT gate): three gates in all.

From circuit to expression and truth table

To analyse a circuit, work from the inputs to the output. Label every intermediate output, write its expression, then substitute.

$P = \overline{A \cdot B}, \qquad Q = B + C, \qquad Y = P \cdot Q = \overline{A \cdot B} \cdot (B + C)$

Worked example 1: the truth table of the circuit above

Three inputs give $2^{3} = 8$ rows. List them in binary counting order (000 to 111) so none is missed, then fill the intermediate columns before $Y$ .

A	B	C	$P = \overline{A \cdot B}$	$Q = B + C$	$Y = P \cdot Q$
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	1	0	0
1	0	1	1	1	1
1	1	0	0	1	0
1	1	1	0	1	0

$Y = 1$ in four rows: whenever $B$ or $C$ is 1, except when $A$ and $B$ are both 1.

python

# Truth table of Y = NOT(A AND B) AND (B OR C)
print("A B C | P Q | Y")
for A in (0, 1):
    for B in (0, 1):
        for C in (0, 1):
            P = int(not (A and B))   # NAND gate
            Q = int(B or C)          # OR gate
            Y = P and Q              # AND gate
            print(A, B, C, "|", P, Q, "|", Y)

Code Explanation

Press Run to let Python work through all 8 rows and compare its output with worked example 1. Each line inside the loops is one gate. You will write programs like this yourself in Unit 4.

Designing a circuit: the half adder

Design follows five steps: (1) name the inputs and outputs; (2) write the truth table; (3) find an expression for each output; (4) draw the circuit; (5) test every row.

To add two bits $A$ and $B$ , the circuit needs two outputs: the sum bit $S$ and the carry bit $C$ .

A	B	A + B in binary	Carry C	Sum S
0	0	00	0	0
0	1	01	0	1
1	0	01	0	1
1	1	10	1	0

The $S$ column (0, 1, 1, 0) is XOR and the $C$ column (0, 0, 0, 1) is AND, so $S = A \oplus B$ and $C = A \cdot B$ . Both gates share the same two inputs.

A half adder cannot accept a carry from the column to its right. A full adder has a third input, the carry-in $C_{in}$ , and computes $S = A \oplus B \oplus C_{in}$ and $C_{out} = A \cdot B + C_{in} \cdot (A \oplus B)$ ; it can be built from two half adders and an OR gate. Chaining 8 full adders adds two bytes.

VAM! Physics & Engineering: Convert Boolean Algebra to Gated Circuit, Vice Versa and Truth Tables. Watch how an expression is turned into gates and how a drawn circuit is read back into an expression, then compare with the two methods above.

Worked example 2: draw from an expression, and count the gates

Draw a circuit for $Y = (A + B) \cdot \overline{A \cdot C}$ .

Inside the brackets: an OR gate for $A + B$ and an AND gate for $A \cdot C$ .
The bar is over the whole product $A \cdot C$ , so a NOT after the AND; together they form one NAND gate.
The last operation is the AND between the two parts: an AND gate whose inputs are the OR output and the NAND output.
Input $A$ is used twice, so its wire splits at a junction dot.

Gates: OR, NAND, AND, which is 3 gates (or 4 if the NAND is drawn as AND + NOT). Check one row: $A = 1, B = 0, C = 1$ : $A + B = 1$ , $A \cdot C = 1$ , $\overline{1} = 0$ , $Y = 1 \cdot 0 = 0$ .

Warning

A crossing is not a joint. Two wires that cross are connected only if a dot marks the junction. Leaving out a needed dot, or adding a dot where wires only cross, changes the circuit.

Check the operation done last. In $A + B \cdot C$ the output gate is OR, not AND, because AND is done first.

Tip

Label as you go. Write the expression of every wire on the diagram beside it. Then the expression of the output can be read straight off the last gate, and a truth table needs one column per label.

✦

Hands-on: build it in a simulator

Open the free online simulator CircuitVerse (no installation needed). Place two Input elements, an XOR gate, an AND gate and two Output elements, and wire up the half adder. Click the inputs to set every combination of 0 and 1 and check the outputs against the truth table. Then build the circuit of worked example 1 and test its eight rows.

Practice

How many gates of each type are needed for $Y = \overline{A} + B \cdot C$ ? Which gate gives the output?
Describe, gate by gate, the circuit for $Y = \overline{A + B} \cdot C$ .
A circuit has an AND gate with inputs $A$ and $B$ , a NOT gate on $C$ , and an OR gate joining the two results. Write its expression.
Complete the truth table of $Y = A \cdot B + \overline{C}$ (8 rows).
For the circuit in worked example 1, list the input rows for which $P = 0$ .
Add the bits 1 and 1 with a half adder: give $S$ and $C$ , and explain how they make the binary number 10.
Find $S$ and $C_{out}$ of a full adder when $A = 1, B = 1, C_{in} = 1$ , and check that $1 + 1 + 1 = 11_{2}$ .
A student draws the half adder with an OR gate in place of the XOR gate. For which input row does it give a wrong answer, and why?

Show answersHide answers

One NOT, one AND, one OR; the OR gives the output.
An OR gate on $A$ and $B$ , followed by a NOT (together a NOR gate); then an AND gate whose inputs are the NOR output and $C$ .
$Y = A \cdot B + \overline{C}$ .
Rows ABC: 000 → 1, 001 → 0, 010 → 1, 011 → 0, 100 → 1, 101 → 0, 110 → 1, 111 → 1.
$P = 0$ only when $A = B = 1$ : rows 110 and 111.
$S = 1 \oplus 1 = 0$ , $C = 1 \cdot 1 = 1$ . Written carry then sum, $C\,S = 10_2 = 2$ .
$S = 1 \oplus 1 \oplus 1 = 0 \oplus 1 = 1$ ; $C_{out} = 1 \cdot 1 + 1 \cdot (1 \oplus 1) = 1 + 0 = 1$ . Output $11_{2} = 3 = 1 + 1 + 1$ .
Row $A = B = 1$ : OR gives $S = 1$ , but the sum bit must be 0 (since $1 + 1 = 10_{2}$ ). OR is 1 when both inputs are 1; XOR is not.

Quick check

In a circuit for Y = A + B·C, which gate gives the output Y?

Key points

Expression to circuit: one gate per operation; the operation done last gives the output gate.
Circuit to expression: label every intermediate output, write each expression, then substitute; build the truth table column by column in binary counting order.
Design: inputs and outputs, truth table, expressions, circuit, test.
Half adder: $S = A \oplus B$ , $C = A \cdot B$ ; a full adder also takes a carry-in.

Sources and credits

Adder (electronics) and Combinational logic, Wikipedia contributors, Wikipedia, licensed under CC BY-SA 4.0. Adapted by Ganzaa.
Simulator: CircuitVerse, a free online digital-logic simulator (linked, not copied).
Video: Convert Boolean Algebra to Gated Circuit, Vice Versa & Truth Tables, VAM! Physics & Engineering, embedded from YouTube.
The circuit diagrams, truth tables, code, worked examples and practice items were written by Ganzaa.

This lesson adapts CC BY-SA material and is shared under CC BY-SA 4.0.

1How does a computer add?

2From expression to circuit

3From circuit to expression and truth table

4Designing a circuit: the half adder

5Hands-on: build it in a simulator

How does a computer add?

From expression to circuit

From circuit to expression and truth table

Designing a circuit: the half adder

Hands-on: build it in a simulator