Unit 13 — Digital Electronics

INPUTS A B C
p = NOR(A, B)
q = NOT(C)
r = NAND(p, q)
alarm = BUFFER(r)

Lesson 1 — Gates and circuits

Division: Junior and above.

The eight gates

A logic gate is a tiny electronic part. Its inputs are signals that are either 1 (on, TRUE) or 0 (off, FALSE), and it sends out one signal, also 0 or 1. ACSL uses eight gates. Two of them take one input, and the other six take two.

The expressions use Unit 8's notation: ~ NOT, * AND, + OR, ⊕ XOR and ⊙ XNOR. The names are easy to remember: NAND is "NOT AND", NOR is "NOT OR" and XNOR is "NOT XOR". Each one is the gate without the N, followed by a NOT.

Here are all the two-input gates in one truth table:

Look along each pair of columns: AND and NAND are opposites in every row, and so are OR and NOR, and XOR and XNOR.

The pictures on a real paper. ACSL draws each gate as a small symbol, with the inputs coming in on the left and the output leaving on the right.

• BUFFER is a triangle pointing right.
• NOT is the same triangle with a small circle, a bubble, at its tip.
• AND is shaped like a letter D: a flat back and a round front.
• OR has a curved back and a pointed front, like a shield on its side.
• XOR is the OR shape with an extra curved line just behind its back.
• NAND, NOR and XNOR are AND, OR and XOR with a bubble at the output.

The bubble always means NOT. Once you know the four shapes and the bubble, you can read all eight gates.

Circuits as netlists

A circuit is gates wired together: the output of one gate becomes an input of another. This book writes every circuit as a netlist, a list of its gates, one per line:

INPUTS A B C
p = NAND(A, B)
out = OR(p, C)

• The first line starts with INPUTS and names the circuit's input signals, capital letters in alphabetical order.
• Every other line is one gate: name = GATE(x, y), or name = GATE(x) for BUFFER and NOT. The gate's inputs x and y are circuit inputs or names of gates on earlier lines.
• Gate names are written in small letters (p, q, out), so they never get mixed up with the inputs A, B, C and D.
• The gate on the last line is the circuit's output.

Circuits as sketches

On a real ACSL paper the circuit is a drawing. This book sometimes draws small circuits with text characters, like this sketch of the netlist above:

A ----\
       [NAND]--- p ---\
B ----/                [OR]--- out
C --------------------/

• Each gate is a box with its name, such as [NAND].
• The wires on its left, joined by \ and /, are its inputs, and the wire on its right is its output.
• A wire can be labelled with the name of the signal it carries (p).
• In bigger sketches, a + is a point where a wire splits in two or turns a corner, and | is a wire going up or down.

To turn a sketch into a netlist, start at the inputs on the left, give each gate's output a name, and write one line per gate, in an order where every gate comes after the gates that feed it.

Here is the greenhouse alarm as a sketch:

A ----\
       [NOR]--- p ---\
B ----/               [NAND]--- r ---[BUFFER]--- alarm
C ---[NOT]--- q -----/

Check it against the netlist on the maintenance sheet: p comes from a NOR of A and B, q from a NOT of C, r is a NAND of p and q, and the BUFFER copies r to the alarm.

From a circuit to an expression

Every circuit can be written as a Boolean expression. Work down the netlist, and replace each gate's name by its expression, putting the inputs' own expressions inside.

Example 1. The first sample on ACSL's Digital Electronics page is the netlist above:

So the circuit is ~(A * B) + C.

When a gate's input is itself a longer expression, put brackets round it, so that Unit 8's order of operations (~, then *, then ⊕ and ⊙, then +) cannot split it. For example, an XOR of A + B with C is (A + B) ⊕ C, and without the brackets A + B ⊕ C would mean A + (B ⊕ C). A NAND, NOR or XNOR puts a ~ in front of the whole thing: NAND(p, q) becomes ~(p * q), with the expressions of p and q written in.

The output for given inputs

To find the output for one set of inputs, go down the netlist and work out every gate in turn.

Example 2. The greenhouse alarm, with A = 1, B = 0 and C = 0 (hot, wet soil, door shut):

The alarm beeps. That answers the first question.

Truth tables, tuples and counts

ACSL's questions about a circuit are the same as Unit 8's questions about an expression:

• Which ordered tuples make the circuit TRUE (or FALSE)?
• How many tuples make it TRUE?
• Simplify the circuit's expression (Lesson 2).

A tuple lists a value for each input in the order of the INPUTS line: (A,B,C) for three inputs. Build a truth table with one column per gate, with the rows in counting-up order.

Example 3. This circuit has three gates:

INPUTS A B C
p = XOR(A, B)
q = AND(B, C)
out = OR(p, q)

Its expression is A ⊕ B + B * C. (No brackets are needed: * and ⊕ both come before +.)

• The triples that make it TRUE are (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,1), so the count is 5.
• The triples that make it FALSE are (0,0,0), (0,0,1), (1,1,0).
• The result column, read from top to bottom, is 00111101.

Working backwards. For "which tuples make it FALSE", you can often skip the table. In Example 1, ~(A * B) + C is an OR, and an OR is 0 only when both of its inputs are 0. So C = 0, and ~(A * B) = 0, which needs A = 1 and B = 1. The only triple that makes the circuit FALSE is (1,1,0), just as ACSL's page says.

Back to the greenhouse. The alarm is a BUFFER of r = NAND(p, q), so it is silent only when r is 0. A NAND is 0 only when both inputs are 1: p = 1 and q = 1. q = NOT(C) is 1 only when C = 0, and p = NOR(A, B) is 1 only when A = 0 and B = 0. So the only reading that keeps the alarm silent is (0,0,0). That answers the second question.

Watch out: every input on the INPUTS line is a column of the table, even if no gate uses it. A circuit with INPUTS A B C has eight rows, and a tuple always has three values. If C is unused, each row with C = 0 has a twin with C = 1 that gives the same output, so every count doubles.

How to write your answers

These are the same forms as in Unit 8:

• an output is 1 or 0, and a count is a whole number, such as 5;
• tuples are written with no spaces inside, in counting-up order, separated by a comma and a space: (0,1,0), (0,1,1), or NONE if there are none;
• a result column is its digits from top to bottom, such as 00111101;
• a simplified expression is a sum of products, as Lesson 2 describes;
• an option question is answered with the labels of every correct option, in order, such as A, C, or NONE.

Lesson 2 — Simplifying circuits

Division: Junior and above.

Simplify the expression

To simplify a circuit, write its expression and then use Unit 8's laws. The answer is a sum of products, exactly as in Unit 8: the fewest terms, then the fewest letters, letters in alphabetical order inside each term, terms ordered as Unit 8's Lesson 2 describes, and 1 or 0 if the circuit is always TRUE or always FALSE.

Example 1. The greenhouse alarm.

The alarm beeps when any sensor reports a problem: A + B + C. Four gates were doing the job of a three-input OR, which two OR gates can build (OR(OR(A, B), C)). That answers the third question.

Example 2. The third sample on ACSL's page:

INPUTS A B C
p = NOT(A)
q = OR(A, B)
r = AND(p, q)
s = NOR(B, C)
out = AND(r, s)

The circuit is always FALSE, whatever the inputs: the answer is 0.

Equivalent circuits

Two circuits with the same inputs are equivalent when they give the same output for every tuple, that is, when their truth tables have the same result column. Very different wiring can give the same circuit. For example, NOT(NOT(A)) is equivalent to BUFFER(A).

Watch out: AND, NAND, OR, NOR, XOR and XNOR do not care which input is which: AND(A, B) and AND(B, A) are the same gate. So two netlists can list the same circuit with their inputs swapped.

Four inputs

Division: Intermediate and above.

Intermediate and Senior circuits can have a fourth input D, so a truth table has 16 rows. Writing all 16 rows always works. Two shortcuts save time.

• Pieces that share no inputs. In INPUTS A B C D, p = OR(A, B), q = NAND(C, D), out = AND(p, q), the gate p is 1 for 3 of the 4 settings of A and B, and q is 1 for 3 of the 4 settings of C and D. The AND needs both, and the two pieces do not share an input, so the count is 3 × 3 = 9.
• Split on one input. Fix D = 0 and then D = 1: often one half of the circuit becomes a constant, and each half is a three-input problem of 8 rows.

XNOR chains

A chain of XOR gates feeds each gate's output into the next one:

INPUTS A B C D
p = XOR(A, B)
q = XOR(p, C)
out = XOR(q, D)

Each XOR flips its output when its new input is 1, so a chain of XORs is 1 exactly when an odd number of the inputs are 1.

An XNOR is an XOR followed by a NOT, and two NOTs cancel. So a chain of XNOR gates is the XOR chain, flipped once for every XNOR gate:

• three inputs use two XNOR gates, and two flips cancel: A ⊙ B ⊙ C is 1 when an odd number of inputs are 1;
• four inputs use three XNOR gates, one flip is left: A ⊙ B ⊙ C ⊙ D is 1 when an even number of inputs are 1 (zero counts as even).

Watch out: a chain goes left to right, like everything else on one level, so A ⊙ B ⊙ C means (A ⊙ B) ⊙ C. Check the rule on one row before you trust it: with (1,0,0), A ⊙ B is 0 and 0 ⊙ C is 0 ⊙ 0 = 1, and one input is 1, an odd number.

NAND and NOR are universal

Division: Senior and above.

Any circuit at all can be built from NAND gates only. Engineers like this, because a chip full of identical gates is cheap to make. Here is how to get each basic gate from NANDs:

So NOT, AND and OR can all be made, and any expression can be built from those.

A sum of products in two layers. De Morgan gives a short way to build any sum of products. A * B + C * D is ~(~(A * B) * ~(C * D)), which is one NAND for each product, and one more NAND to join them:

INPUTS A B C D
p = NAND(A, B)
q = NAND(C, D)
out = NAND(p, q)

NOR is universal too, with the roles of AND and OR swapped:

Checking a construction. A Senior question may show several NAND-only circuits and ask which of them are equivalent to a given function. Do not trust how a circuit looks: build each circuit's truth table (or simplify its expression) and compare the result columns. Two inputs give only 4 rows, and three give 8.

Lesson 3 — A circuit simulator in Python

Division: Junior and above.

One function for all eight gates

A Python function can play the part of every gate. It takes the gate's name and its inputs x and y, each 0 or 1. For BUFFER and NOT the second input is not used, so the program passes 0 for it.

• AND is x * y: the product of 0s and 1s is 1 only when both are 1.
• OR is max(x, y): the larger value is 1 when at least one is 1.
• XOR is int(x != y): 1 when the inputs are different.
• NAND, NOR and XNOR work out AND, OR or XOR first, and then flip the answer with 1 - answer, just as their names say.

def gate(name, x, y):
    if name == "BUFFER":
        answer = x
    elif name == "NOT":
        answer = 1 - x
    elif name == "AND" or name == "NAND":
        answer = x * y
    elif name == "OR" or name == "NOR":
        answer = max(x, y)
    else:
        answer = int(x != y)
    if name == "NAND" or name == "NOR" or name == "XNOR":
        answer = 1 - answer
    return answer


for name in ["AND", "NAND", "OR", "NOR", "XOR", "XNOR"]:
    column = ""
    for x in range(2):
        for y in range(2):
            column = column + str(gate(name, x, y))
    print(name, column)
print("NOT", str(gate("NOT", 0, 0)) + str(gate("NOT", 1, 0)))

AND 0001
NAND 1110
OR 0111
NOR 1000
XOR 0110
XNOR 1001
NOT 10

def gate(name, x, y):
    if name == "BUFFER":
        answer = x
    elif name == "NOT":
        answer = 1 - x
    elif name == "AND" or name == "NAND":
        answer = x * y
    elif name == "OR" or name == "NOR":
        answer = max(x, y)
    else:
        answer = int(x != y)
    if name == "NAND" or name == "NOR" or name == "XNOR":
        answer = 1 - answer
    return answer


name = input()
if name == "BUFFER" or name == "NOT":
    for x in range(2):
        print(str(x) + " : " + str(gate(name, x, 0)))
else:
    for x in range(2):
        for y in range(2):
            print(str(x) + " " + str(y) + " : " + str(gate(name, x, y)))

Run it from this unit's folder:

python assets/l1.py < assets/l1/1.in

The input is NAND, and the program prints four rows, ending with 1 1 : 0. assets/l1/2.in asks for NOT, a one-input gate, so its table has only two rows.

Reading a netlist line

A netlist line such as out = NAND(p, q) holds four words, out, NAND, p and q, mixed up with a space, an =, brackets and a comma. split() alone would give NAND(p, as one piece. Instead, the function words walks along the line one character at a time. Every character in " =()," ends the word being built; any other character is added to it. One extra space on the end makes sure the last word is finished too.

def words(line):
    result = []
    word = ""
    for ch in line + " ":
        if ch in " =(),":
            if word != "":
                result.append(word)
            word = ""
        else:
            word = word + ch
    return result


print(words("out = NAND(p, q)"))
print(words("q = NOT(C)"))
print(words("INPUTS A B C"))

['out', 'NAND', 'p', 'q']
['q', 'NOT', 'C']
['INPUTS', 'A', 'B', 'C']

A dictionary of signals

A circuit has signals with names: the inputs A, B, C and the gates p, q, out. A dictionary keeps the value of each one under its name. Start it with the inputs; then, going down the netlist, look up each gate's inputs and store the gate's output under its own name. Because every gate comes after the gates that feed it, its inputs are always already in the dictionary.

This program runs Example 1 of Lesson 1 for one triple.

def gate(name, x, y):
    if name == "BUFFER":
        answer = x
    elif name == "NOT":
        answer = 1 - x
    elif name == "AND" or name == "NAND":
        answer = x * y
    elif name == "OR" or name == "NOR":
        answer = max(x, y)
    else:
        answer = int(x != y)
    if name == "NAND" or name == "NOR" or name == "XNOR":
        answer = 1 - answer
    return answer


def words(line):
    result = []
    word = ""
    for ch in line + " ":
        if ch in " =(),":
            if word != "":
                result.append(word)
            word = ""
        else:
            word = word + ch
    return result


lines = ["p = NAND(A, B)", "out = OR(p, C)"]
value = {"A": 1, "B": 1, "C": 0}
for line in lines:
    w = words(line)
    x = value[w[2]]
    y = 0
    if len(w) == 4:
        y = value[w[3]]
    value[w[0]] = gate(w[1], x, y)
    print(w[0], value[w[0]])
print(value)

p 0
out 0
{'A': 1, 'B': 1, 'C': 0, 'p': 0, 'out': 0}

def gate(name, x, y):
    if name == "BUFFER":
        answer = x
    elif name == "NOT":
        answer = 1 - x
    elif name == "AND" or name == "NAND":
        answer = x * y
    elif name == "OR" or name == "NOR":
        answer = max(x, y)
    else:
        answer = int(x != y)
    if name == "NAND" or name == "NOR" or name == "XNOR":
        answer = 1 - answer
    return answer


def words(line):
    result = []
    word = ""
    for ch in line + " ":
        if ch in " =(),":
            if word != "":
                result.append(word)
            word = ""
        else:
            word = word + ch
    return result


g = int(input())
names = words(input())
lines = []
for i in range(g):
    lines.append(input())
bits = input().split()

value = {}
for i in range(1, len(names)):
    value[names[i]] = int(bits[i - 1])
last = ""
for line in lines:
    w = words(line)
    x = value[w[2]]
    y = 0
    if len(w) == 4:
        y = value[w[3]]
    value[w[0]] = gate(w[1], x, y)
    last = w[0]
print(value[last])

Run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

The input is the greenhouse alarm with the reading 1 0 0, and the program prints 1: the alarm beeps. assets/l2/2.in is the reading 0 0 0, the one that keeps it silent.

Every row at once

A truth table needs every tuple in counting-up order. With k inputs there are 2 × 2 × … × 2 (k times) rows, and row number row (counting from 0) is just row written in binary with k digits. The last input is the last binary digit, row % 2; dividing by 2 with row // 2 moves on to the next digit to the left. So the program fills the inputs from the last one back to the first, with range(k, 0, -1), which counts k, k - 1, …, 1.

Put it together: this program reads a netlist (the number of gates, then the netlist) and prints its whole truth table, one row per line, followed by the number of rows that make it TRUE. The function run is the loop of assets/l2.py above, for one row; each row gets a fresh dictionary. It is saved as assets/l3.py.

def gate(name, x, y):
    if name == "BUFFER":
        answer = x
    elif name == "NOT":
        answer = 1 - x
    elif name == "AND" or name == "NAND":
        answer = x * y
    elif name == "OR" or name == "NOR":
        answer = max(x, y)
    else:
        answer = int(x != y)
    if name == "NAND" or name == "NOR" or name == "XNOR":
        answer = 1 - answer
    return answer


def words(line):
    result = []
    word = ""
    for ch in line + " ":
        if ch in " =(),":
            if word != "":
                result.append(word)
            word = ""
        else:
            word = word + ch
    return result


def run(lines, value):
    last = ""
    for line in lines:
        w = words(line)
        x = value[w[2]]
        y = 0
        if len(w) == 4:
            y = value[w[3]]
        value[w[0]] = gate(w[1], x, y)
        last = w[0]
    return value[last]


g = int(input())
names = words(input())
lines = []
for i in range(g):
    lines.append(input())

k = len(names) - 1
total = 1
for i in range(k):
    total = total * 2

true_rows = 0
for row in range(total):
    value = {}
    rest = row
    for i in range(k, 0, -1):
        value[names[i]] = rest % 2
        rest = rest // 2
    out = run(lines, value)
    text = ""
    for i in range(1, k + 1):
        text = text + str(value[names[i]]) + " "
    print(text + ": " + str(out))
    true_rows = true_rows + out
print("TRUE rows: " + str(true_rows))

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in

The input is ACSL's first sample, and the program prints eight rows, with 1 1 0 : 0 the only 0, and then TRUE rows: 7. assets/l3/2.in is the greenhouse alarm: check that its only 0 is the row 0 0 0. assets/l3/4.in is a four-input XNOR chain: count the 1s in each row and check the rule from Lesson 2. Use this program to check any truth table you build by hand.