Chapter 2: Computer Hardware
In 1937, a twenty-one-year-old master’s student at the Massachusetts Institute of Technology was given an unglamorous job: looking after the relay circuits of a large calculating machine, the differential analyser built under Vannevar Bush. The machine did much of its work through banks of electrical switches that clicked open and shut. Anyone designing such a circuit at the time worked by intuition and trial and error, and a wrong guess could mean days of rewiring.
The student, Claude Shannon, had also studied the algebra of true and false that George Boole had published in 1854 — an algebra written for reasoning, not for machinery. He noticed something that nobody had written down before. A switch is either open or closed, so it has two states, like a truth value. Two switches placed one after the other pass current only if both are closed. Two switches placed side by side pass current if either one is closed. Those are exactly the rules of AND and OR.
If that was so, a circuit could first be written as a Boolean expression, simplified on paper using the ordinary laws of the algebra, and only then built — with fewer switches and less wiring than the guessed version. Shannon set this out in his master’s thesis. Boole’s abstract algebra of truth values, eighty-three years old, had become the design language of electronic hardware.
Diagram
Fig. 2.0-1 – left half: a battery, a lamp and two switches labelled A and B wired one after the other in a single loop, captioned “current flows only if both are closed”; right half: the same battery and lamp with switches A and B wired side by side on two parallel branches, captioned “current flows if either is closed”; an open notebook drawn between the two halves showing the two expressions A·B and A+B
This chapter will answer each of these questions.
2.1 From Boolean Algebra to Switching Circuits
The previous chapter treated Boolean algebra as pure algebra. Variables took the values 1 and 0, three operations acted on them, and a set of laws let one expression be rewritten as a simpler one that means the same thing. Nothing in that work depended on wires or electricity.
This chapter puts the same algebra to work inside a machine. A computer stores and processes everything as patterns of 1s and 0s, so a device that physically produces a 1 or a 0 from other 1s and 0s is exactly a device that computes a Boolean function. Once that link is made, an expression on paper becomes a plan for a circuit, and simplifying the expression means building the circuit with fewer parts.
Notation used in this chapter
Boolean expressions in this chapter are written in the usual algebraic form of switching circuits. The complement of a variable takes an overbar, \(\overline{A}\); the AND operation is written by juxtaposition or with a dot, \(AB\) or \(A \cdot B\); the OR operation is written with a plus sign, \(A + B\). Two further symbols appear later — \(\oplus\) for the exclusive-OR operation and \(\odot\) for its complement. This one convention is used throughout the chapter.
2.1.1 Binary Valued Signals in Hardware
A wire inside a computer does not carry a digit. It carries a voltage, and the designer of the circuit fixes two ranges of voltage and agrees to ignore everything in between. A voltage in the higher range is read as 1, and is described as high; a voltage in the lower range is read as 0, and is described as low. The same pair of states is described in other places as ON and OFF, or as true and false. The names differ; the idea is the same, and it is the reason Boolean algebra fits hardware so exactly. A Boolean variable has two values, and so does a wire.
The simplest device with two states is an ordinary switch. It is either closed, letting current pass, or open, blocking it. A circuit built from such switches, in which the behaviour of the whole depends only on which switches are open and which are closed, is called a switching circuit.
Take a battery, a lamp and two switches labelled \(A\) and \(B\), and let a closed switch stand for 1 and an open switch for 0. Let the lamp being lit stand for an output of 1. If the two switches are wired one after the other, current has to pass through both of them to reach the lamp, so the lamp lights only when both switches are closed. If the two switches are wired side by side, on two separate branches, current has a choice of paths, so the lamp lights when either switch is closed. Table 2.1 records both arrangements.
| Switch A | Switch B | Lamp, switches one after the other | Lamp, switches side by side |
|---|---|---|---|
| open | open | off | off |
| open | closed | off | on |
| closed | open | off | on |
| closed | closed | on | on |
Read the third column with 1 for closed and 1 for a lit lamp, and it gives 0, 0, 0, 1 — the output column of \(A \cdot B\). Read the fourth column the same way and it gives 0, 1, 1, 1, which is \(A + B\). The two commonest ways of joining components are therefore not two arbitrary engineering habits; they are the AND and OR operations of the algebra, already built.
Complement needs a slightly different arrangement, shown in Fig. 2.1-1. Here the switch is not placed in the path to the lamp but across it, forming a bypass. When the switch is open, current has no alternative route and must pass through the lamp, which lights. When the switch is closed, it offers a path of far lower resistance around the lamp, so almost no current passes through the lamp and it goes out. Closed gives 0 and open gives 1: the output is the complement of the switch.
Diagram
Fig. 2.1-1 – switching circuit for complement; a battery in series with a lamp forming a loop; a single switch labelled A wired directly across the two terminals of the lamp as a bypass branch; label the lamp output as A with an overbar
2.1.2 What a Logic Gate Is
Switches worked by hand are useful for showing the idea, but a computer must set its own switches millions of times a second, from signals produced by other parts of the machine. The electronic circuit that does this is the logic gate.
A logic gate is a small electronic circuit that takes one or more binary input signals and produces exactly one binary output signal, the value of the output being fixed by a Boolean operation on the inputs. Fig. 2.1-2 shows this as a block: signals in on the left, one signal out on the right, and a rule inside that decides the output for every possible combination of inputs.
Diagram
Fig. 2.1-2 – block representation of a logic gate; a rectangle labelled LOGIC GATE with three arrows entering on the left labelled input 1, input 2, input n, and a single arrow leaving on the right labelled output; a caption line inside the rectangle reading “output fixed by a Boolean operation on the inputs”
Two parts of that definition are worth pausing on. First, one or more inputs: some books define a gate as taking two or more inputs and are then forced to call the complement gate an exception to their own definition. There is no exception. A gate that complements a single input is a gate like any other, and the definition above admits it without special pleading. Second, exactly one output: a gate never produces two answers. Circuits such as the adders in section 2.5 do produce two outputs, but they do so by using two gates, one for each output.
Gates are manufactured as integrated circuits (IC) — many components formed together on a single small chip of silicon and sealed in one package. A single inexpensive package may hold four or six gates of the same type. This is why designing with gates is practical at all: the designer works with the logical behaviour of the package and need not think about the transistors inside it.
Basic gates and derived gates
The syllabus names seven gates: NOT, AND, OR, NAND, NOR, XOR and XNOR. They fall into two groups. NOT, AND and OR are the fundamental logic gates, also called basic gates, because they carry out the three operations of Boolean algebra directly and are not built from anything simpler. The remaining four are the derived logic gates: each of them can be assembled from fundamental gates, and section 2.2 shows exactly how.
There is one further property that all seven share and that the definition quietly assumes. The output of a gate depends only on the input values present at that moment, never on what the inputs were earlier. A circuit built only from such gates is called a combinational circuit, and every circuit in this chapter is of that kind. It is an honest limitation: a combinational circuit cannot remember anything, so it cannot by itself count, store a number, or wait for the next clock pulse. Circuits that do remember are built by feeding outputs back into inputs, which is a different subject.
2.1.3 Symbol, Expression and Truth Table
The same gate, or the same circuit made of gates, can be described in three ways, and a student who can move freely between them can do almost everything this chapter asks.
The symbol is a standard shape used in a circuit diagram. It says how the parts are wired and nothing about why. The Boolean expression is the algebraic form, and it is the description that can be simplified: the laws of the previous chapter act on expressions, not on drawings. The truth table lists the output for every possible combination of inputs, and it is the description that settles arguments, because two circuits are equivalent exactly when their truth tables agree row for row.
A circuit with \(n\) inputs has \(2^n\) possible input combinations, so its truth table has \(2^n\) rows. The rows are always written in standard binary counting order — for three inputs, 000, 001, 010, 011, 100, 101, 110, 111 — so that two tables can be compared line by line without hunting for matching rows.
Building a truth table from an expression
Consider the expression \(F = \overline{A}B + AC\). It has three variables, so the table has eight rows. Rather than evaluate the whole expression at once, it is safer to give each product term a column of its own, fill those columns first, and combine them at the end. Table 2.2 does this.
| A | B | C | \(\overline{A}\) | \(\overline{A}B\) | \(AC\) | \(F\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
The last column shows that \(F\) is 1 in four of the eight cases. Reading the table back in words: the output is 1 whenever \(A\) is 0 and \(B\) is 1, and also whenever \(A\) is 1 and \(C\) is 1. Notice how the intermediate columns make checking easy. If a single entry in the \(AC\) column were wrong, it could be found by inspecting that column alone, without re-evaluating the whole expression.
The same three descriptions run in the other direction too. Sections 2.3.2 and 2.3.3 take a drawn circuit and recover its expression, and take a truth table and produce a circuit that satisfies it.
2.2 Elementary Logic Gates
Seven gates are needed for the whole of this chapter: NOT, AND, OR, NAND, NOR, XOR and XNOR. Each of them is presented here in the same four ways — what it does in plain words, its symbol, its Boolean expression and its truth table — because a gate is only properly known when all four are known together.
Three of the seven are fundamental and four are derived, as section 2.1.2 explained. The order below follows that grouping: the three fundamental gates first, then the four built from them.
2.2.1 The NOT Gate
The NOT gate reverses whatever it is given. An input of 1 produces an output of 0, and an input of 0 produces an output of 1. It is the only gate with a single input, which is why it is sometimes called the unary gate, and it is more often called the inverter, because inverting the signal is exactly what it does.
Its symbol is drawn in Fig. 2.2-1. The triangle by itself would mean “pass the signal through unchanged”; it is the small circle at the tip that carries the meaning of complement. That small circle is worth remembering, because it appears again on the NAND, NOR and XNOR symbols with exactly the same meaning.
Diagram
Fig. 2.2-1 – NOT gate symbol; a triangle pointing right with a small circle (bubble) at its tip; single input line on the left labelled A; output line on the right labelled with A carrying an overbar
| A | \(\overline{A}\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
The expression is \(F = \overline{A}\). Because complementing twice returns the original value, two inverters in a row have no effect at all on a signal — a fact used constantly when circuits are rebuilt in section 2.4.
2.2.2 The AND Gate
The AND gate gives an output of 1 only when every one of its inputs is 1. If even one input is 0, the output is 0. This matches the everyday sense of “and”: a library will issue a book if the reader has a valid card and the book is not already issued, and failing either condition is enough to refuse.
Its symbol, shown in Fig. 2.2-2, has a flat back and a rounded front.
Diagram
Fig. 2.2-2 – two-input AND gate symbol; a D-shape with a flat left edge and a semicircular right edge; two input lines on the left labelled A and B; output line on the right labelled A·B
| A | B | \(A \cdot B\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The expression is \(F = A \cdot B\), usually written simply as \(AB\). The output column is the same as the column of products \(A \times B\) in ordinary arithmetic on the digits 0 and 1, which is why the AND operation is called the logical product.
One common use follows directly from the last row. If one input of an AND gate is held at 1, the output copies the other input; if it is held at 0, the output stays 0 whatever the other input does. An AND gate can therefore be used as a switch that lets a signal through or blocks it.
2.2.3 The OR Gate
The OR gate gives an output of 1 when at least one of its inputs is 1, and 0 only when every input is 0. It corresponds to the inclusive sense of “or” in English: a warning lamp on a machine may be lit if the temperature is too high or the pressure is too high, and it is certainly lit if both are.
Diagram
Fig. 2.2-3 – two-input OR gate symbol; a shape with a curved left edge and two curved edges meeting in a point on the right; two input lines on the left labelled A and B; output line on the right labelled A+B
| A | B | \(A + B\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The expression is \(F = A + B\), called the logical sum. The name has to be handled with a little care: in the last row, \(1 + 1 = 1\), not 2. The OR gate reports whether any input is 1; it does not count them. Adding binary numbers properly is a different job, and section 2.5 builds the circuit for it.
2.2.4 The NAND Gate
NAND is short for NOT-AND, and that is precisely what it is: an AND gate with its output complemented. So its output is 0 only when all its inputs are 1, and 1 in every other case.
The symbol, Fig. 2.2-4, is the AND shape with the small circle at its output. The same figure shows the equivalent arrangement of an AND gate followed by an inverter; the two behave identically, but the manufactured NAND is a single package.
Diagram
Fig. 2.2-4 – two parts side by side. Left: two-input NAND gate symbol, the AND D-shape with a small circle at the output; inputs A and B; output labelled with an overbar over A·B. Right: the same function built from two gates — an AND gate with inputs A and B whose output A·B feeds a NOT gate, whose output is labelled with an overbar over A·B
| A | B | \(A \cdot B\) | \(\overline{A \cdot B}\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
The expression is \(F = \overline{A \cdot B}\). Comparing the last column with Table 2.4 confirms that every entry has simply been flipped.
2.2.5 The NOR Gate
NOR is short for NOT-OR: an OR gate with its output complemented. Its output is 1 only when every input is 0, and 0 as soon as any input becomes 1.
Diagram
Fig. 2.2-5 – two parts side by side. Left: two-input NOR gate symbol, the OR shape with a small circle at the output; inputs A and B; output labelled with an overbar over A+B. Right: the same function built from two gates — an OR gate with inputs A and B whose output A+B feeds a NOT gate, whose output is labelled with an overbar over A+B
| A | B | \(A + B\) | \(\overline{A + B}\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
The expression is \(F = \overline{A + B}\). A NOR gate answers the question “are all the inputs 0?”, which makes it convenient wherever a circuit must react to the absence of every signal — a lamp that lights only when no machine on a line is running, for instance.
NAND and NOR are the two gates from which every other gate can be constructed. That property is important enough to have a section of its own, section 2.4.
2.2.6 The XOR Gate
The exclusive-OR gate, written XOR or Ex-OR, gives an output of 1 when its two inputs are different, and 0 when they are the same. The word exclusive separates it from the ordinary OR gate: ordinary OR accepts the case where both inputs are 1, while exclusive-OR excludes it.
Diagram
Fig. 2.2-6 – two-input XOR gate symbol; the OR shape with an additional curved line drawn just outside its curved input edge; two input lines on the left labelled A and B; output line on the right labelled A ⊕ B
| A | B | \(\overline{A}B\) | \(A\overline{B}\) | \(A \oplus B\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
The expression \(A \oplus B = \overline{A}B + A\overline{B}\) can be read straight from the table. The output is 1 in exactly two rows: the row where \(A\) is 0 and \(B\) is 1, which the term \(\overline{A}B\) describes, and the row where \(A\) is 1 and \(B\) is 0, which the term \(A\overline{B}\) describes.
That expression also shows how to build the gate from fundamental gates alone, as in Fig. 2.2-7: complement each input, form the two products with AND gates, and combine them with an OR gate. This is why XOR is classed as a derived gate.
Diagram
Fig. 2.2-7 – XOR built from fundamental gates; inputs A and B on the left; a NOT gate on A producing A̅ and a NOT gate on B producing B̅; an AND gate taking A̅ and B, its output wire labelled A̅B; a second AND gate taking A and B̅, its output wire labelled AB̅; both AND outputs feeding one OR gate whose output on the right is labelled A ⊕ B
Since the gate reports whether two bits differ, it is the natural comparator for a single bit, and it is used wherever two bit patterns must be checked against each other. It reappears in section 2.5, in the circuit that adds binary digits.
| Feature | OR gate | XOR gate |
|---|---|---|
| Output is 1 when | at least one input is 1 | the two inputs are different |
| Output for inputs 1, 1 | 1 | 0 |
| Sense of “or” | inclusive | exclusive |
| Expression | \(A + B\) | \(\overline{A}B + A\overline{B}\) |
| Classification | fundamental gate | derived gate |
| Typical use | detecting that any one of several conditions holds | detecting that two bits disagree |
2.2.7 The XNOR Gate
The exclusive-NOR gate, written XNOR or Ex-NOR, is the complement of the XOR gate. Its output is 1 when its two inputs are the same, and 0 when they differ, so it answers the question “are these two bits equal?”. For that reason it is also called the equivalence gate. The operation is written \(A \odot B\).
Diagram
Fig. 2.2-8 – two-input XNOR gate symbol; the XOR shape, that is the OR shape with an extra curved line at the input edge, with a small circle at the output; two input lines on the left labelled A and B; output line on the right labelled A ⊙ B
| A | B | \(A \oplus B\) | \(A \odot B\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Its expression is \(A \odot B = \overline{A \oplus B} = \overline{A}\,\overline{B} + AB\), and the two product terms are again read from the rows where the output is 1: both inputs 0, or both inputs 1. Like XOR, it can be assembled from fundamental gates, either by building XOR and adding an inverter, or by forming the two products \(\overline{A}\,\overline{B}\) and \(AB\) directly and combining them with an OR gate.
The seven gates at a glance
Table 2.11 collects the seven gates. It is worth reading down the last column, because that column, and not the symbol, is what a designer actually reasons with.
| Gate | Group | Expression | Output is 1 when |
|---|---|---|---|
| NOT | fundamental | \(\overline{A}\) | the input is 0 |
| AND | fundamental | \(A \cdot B\) | all inputs are 1 |
| OR | fundamental | \(A + B\) | at least one input is 1 |
| NAND | derived | \(\overline{A \cdot B}\) | at least one input is 0 |
| NOR | derived | \(\overline{A + B}\) | all inputs are 0 |
| XOR | derived | \(\overline{A}B + A\overline{B}\) | the inputs are different |
| XNOR | derived | \(\overline{A}\,\overline{B} + AB\) | the inputs are the same |
2.2.8 Gates with More Than Two Inputs
Except for NOT, which is unary by nature, all of these gates are manufactured in versions with three, four or eight inputs, and the definitions extend in the obvious way. A three-input AND gate gives 1 only when all three inputs are 1; a three-input OR gate gives 1 when at least one of the three is 1; a three-input NAND gives \(\overline{ABC}\) and a three-input NOR gives \(\overline{A + B + C}\).
Diagram
Fig. 2.2-9 – three-input gate symbols drawn side by side; left, a three-input AND gate with inputs A, B, C and output labelled A·B·C; right, a three-input OR gate with inputs A, B, C and output labelled A+B+C
XOR needs a closer look, because “different” has no clear meaning for three inputs. The definition that extends properly is the one based on counting: a multi-input XOR gate gives an output of 1 when an odd number of its inputs are 1. For two inputs this is the same as saying the inputs differ, so nothing said earlier changes. Table 2.12 gives the three-input case.
| A | B | C | number of inputs that are 1 | \(A \oplus B \oplus C\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 2 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 2 | 0 |
| 1 | 1 | 0 | 2 | 0 |
| 1 | 1 | 1 | 3 | 1 |
The output column is 1 in exactly the four rows where the count is odd. The three-input XNOR gate is the complement of this, so it gives 1 in the four rows where the count of 1s is even, including the row with no 1s at all.
For XOR the extension is also safe in a second sense: feeding \(A\) and \(B\) into one two-input XOR gate and then feeding that result and \(C\) into another produces the same output column as a single three-input XOR gate. The operation is associative, so chaining works.
2.3 Logic Circuits
A single gate computes one operation. Useful work needs several gates wired together, with the output of one feeding the input of the next, so that the arrangement as a whole carries out a complete Boolean function. Such an arrangement is called a logic circuit.
Three tasks come up constantly, and each is the reverse of another: drawing a circuit for a given expression, recovering the expression of a given circuit, and designing a circuit when only the required behaviour is known. This section takes them in that order.
2.3.1 Drawing a Circuit for a Boolean Expression
An expression is evaluated in a fixed order, and the circuit is built in that same order. Complement is applied first, then AND, then OR; brackets override this and are worked out first. So in \(A + BC\) the AND is formed first and its result is fed to the OR gate, while in \((A + B)C\) the bracket forces the OR to come first.
The procedure is mechanical:
- Draw the input lines on the left, one for each variable, and branch each where it is needed more than once.
- Put an inverter on every variable that appears complemented, and label its output.
- Draw one AND gate for each product term, feeding it the variables or complements that the term contains, and label its output with the term.
- Feed the outputs of those AND gates into one OR gate. Its output is the whole expression.
- Work outwards from the innermost bracket wherever brackets are present, so that a gate is drawn only after everything feeding it has been drawn.
Consider \(F = A\overline{B} + \overline{A}BC\). It has two product terms, so two AND gates are needed, one with two inputs and one with three. Both \(A\) and \(B\) appear complemented, so two inverters are needed. The complete circuit is shown in Fig. 2.3-1, with every intermediate wire labelled — a habit worth keeping, because a labelled diagram can be checked, and an unlabelled one can only be admired.
Diagram
Fig. 2.3-1 – logic circuit for F = AB̅ + A̅BC; three input lines on the left labelled A, B and C, each branched with junction dots; a NOT gate on A producing a wire labelled A̅; a NOT gate on B producing a wire labelled B̅; a two-input AND gate taking A and B̅ with its output wire labelled AB̅; a three-input AND gate taking A̅, B and C with its output wire labelled A̅BC; both AND outputs feeding a two-input OR gate whose output on the right is labelled F = AB̅ + A̅BC
A bracketed expression is built the same way, but the OR gates now come first. For \(F = (A + \overline{B})(B + C)\), each bracket is an OR gate, and their two outputs are combined by an AND gate, as Fig. 2.3-2 shows.
Diagram
Fig. 2.3-2 – logic circuit for F = (A + B̅)(B + C); input lines A, B and C on the left with junction dots where B branches; a NOT gate on B producing B̅; a two-input OR gate taking A and B̅ with its output labelled A + B̅; a second two-input OR gate taking B and C with its output labelled B + C; both OR outputs feeding a two-input AND gate whose output on the right is labelled F
2.3.2 Writing the Expression of a Given Circuit
Reading a circuit is the reverse journey, and it is done from the inputs towards the output, never from the output backwards. Label the output of the first gate that has only input variables entering it, then the next gate whose inputs are now all labelled, and continue until the final gate is reached. The label on the last wire is the expression of the circuit.
Fig. 2.3-3 shows a circuit with three inputs and five gates.
Diagram
Fig. 2.3-3 – logic circuit to be read; input lines A, B and C on the left, with B and C branched using junction dots; a two-input OR gate taking A and B with its output wire marked (1); a NOT gate on C with its output wire marked (2); a two-input AND gate taking wire (1) and wire (2) with its output marked (3); a two-input AND gate taking B and C with its output marked (4); a two-input OR gate taking wires (3) and (4) whose output on the right is marked F
Working forward: wire (1) carries \(A + B\); wire (2) carries \(\overline{C}\); wire (3) is the AND of those two, so it carries \((A + B)\overline{C}\); wire (4) carries \(BC\); and the final OR gate gives
\[F = (A + B)\overline{C} + BC\]
That is a correct description of the circuit as drawn, but it is not the last word. Applying the laws of the previous chapter,
\[F = A\overline{C} + B\overline{C} + BC = A\overline{C} + B(\overline{C} + C) = A\overline{C} + B \cdot 1 = A\overline{C} + B\]
The circuit of Fig. 2.3-3 uses five gates to compute something that needs only three: an inverter, one AND gate and one OR gate. Table 2.13 confirms that the two expressions really do agree in every row, which is the only proof that matters.
| A | B | C | \(A + B\) | \(\overline{C}\) | \((A+B)\overline{C}\) | \(BC\) | \(F\) | \(A\overline{C} + B\) |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
The last two columns are identical, so the simpler circuit may be built in place of the drawn one. This is the practical point of the whole of the previous chapter: fewer gates mean a smaller chip, less power drawn and fewer connections that can fail.
2.3.3 Designing a Circuit from a Truth Table
Most real problems arrive as a description of required behaviour, not as an expression. The design route is therefore: state the condition in words, write the truth table, read a sum of products (SOP) expression off the table, simplify it, and only then draw the circuit.
Reading the expression off the table uses the idea of minterms from the previous chapter. Take each row in which the output is 1, and write a product term containing every input variable — the variable itself where that input is 1 in the row, and its complement where the input is 0. The sum of those product terms is a correct expression for the function, because it is 1 in exactly the rows the table requires and 0 everywhere else.
A worked design
A water pump in a school building is to run under this rule: the pump runs when the overhead tank is not full and either the manual switch is on or the timer is active. Three inputs describe the situation, and one output controls the pump.
- \(S\) is 1 when the manual switch is on.
- \(T\) is 1 when the timer is active.
- \(U\) is 1 when the tank is full.
- \(P\) is 1 when the pump is to run.
Table 2.14 lists all eight combinations. Notice that whenever \(U\) is 1 the pump must stop, whatever the other two inputs say.
| S | T | U | P | product term |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | — |
| 0 | 0 | 1 | 0 | — |
| 0 | 1 | 0 | 1 | \(\overline{S}T\overline{U}\) |
| 0 | 1 | 1 | 0 | — |
| 1 | 0 | 0 | 1 | \(S\overline{T}\,\overline{U}\) |
| 1 | 0 | 1 | 0 | — |
| 1 | 1 | 0 | 1 | \(ST\overline{U}\) |
| 1 | 1 | 1 | 0 | — |
Three rows give an output of 1, so the SOP expression has three terms:
\[P = \overline{S}T\overline{U} + S\overline{T}\,\overline{U} + ST\overline{U}\]
Built directly, that needs three inverters, three three-input AND gates and a three-input OR gate. Simplification comes first. Every term contains \(\overline{U}\), so it can be taken out:
\[P = \overline{U}\,(\overline{S}T + S\overline{T} + ST)\]
The bracket can be reduced by writing the term \(ST\) twice, which idempotence permits:
\[\overline{S}T + S\overline{T} + ST = (\overline{S}T + ST) + (S\overline{T} + ST) = T(\overline{S} + S) + S(\overline{T} + T) = T + S\]
so that
\[P = (S + T)\,\overline{U}\]
The final circuit, Fig. 2.3-4, needs one inverter, one OR gate and one AND gate. It is also easier to read back as English: run the pump if a request has been made and the tank is not full — which is what the original rule said all along.
Diagram
Fig. 2.3-4 – logic circuit for the pump control P = (S + T)·U̅; three input lines on the left labelled S, T and U; a two-input OR gate taking S and T with its output wire labelled S + T; a NOT gate on U with its output wire labelled U̅; a two-input AND gate taking S + T and U̅ whose output on the right is labelled P
A circuit can equally be designed from the rows where the output is 0, giving a product of sums (POS) expression built from maxterms, and for some functions that form is the shorter one. Whichever route is taken, the truth table remains the specification: the finished circuit is correct exactly when its output column matches the table row for row.
2.4 Universal Gates
Section 2.2 introduced NAND and NOR as two derived gates among four. They deserve a section to themselves, because each of them has a property the others do not: given enough gates of that one kind, any logic circuit whatever can be built.
2.4.1 Why NAND and NOR Are Called Universal
A gate is called a universal gate when every other gate, and therefore every Boolean function, can be realised using only gates of that type. NAND and NOR are the two universal gates, and they are sometimes described as universal building blocks for the same reason.
The claim looks large, but the argument behind it is short and rests on something already established. Any function at all can be written from its truth table as a sum of products, as section 2.3.3 showed, and a sum of products uses only three operations: complement, AND and OR. So if complement, AND and OR can each be built from NAND gates alone, then anything can be. The same argument works for NOR. Sections 2.4.2 and 2.4.3 do exactly this construction.
The tool that makes the construction possible is De Morgan’s theorem, because the problem in every case is that a NAND gate produces a product and a complement together, and something is needed to trade one for the other.
There is a practical reason as well as a mathematical one for caring about this. A designer who can work in one gate type can order one kind of package, keep one kind of spare, and let the manufacturer optimise a single circuit design; in the common transistor families, NAND and NOR are also the cheapest gates to fabricate, since AND and OR are internally built as a NAND or NOR followed by an inverter anyway.
2.4.2 Realising the Gates Using NAND Only
The method throughout is the same: write the required function, force it into the form “complement of a product”, and then read that form off as NAND gates. The double complement is the usual first move, since complementing twice changes nothing.
NOT from NAND
Tie both inputs of a NAND gate to the same signal. The gate then computes \(\overline{A \cdot A}\), and since \(A \cdot A = A\) by idempotence, the output is \(\overline{A}\). One gate is enough, and this arrangement — a NAND gate used as an inverter — is needed so often below that it is worth naming.
AND from NAND
A NAND gate already gives \(\overline{A \cdot B}\); all that is missing is a complement at the end. Feeding its output into a NAND used as an inverter gives \(\overline{\overline{A \cdot B}} = A \cdot B\). Two gates. Fig. 2.4-1 shows both realisations.
Diagram
Fig. 2.4-1 – two parts side by side. Left: NOT from NAND — a single two-input NAND gate with input A branching to both of its input terminals, output labelled with an overbar over A. Right: AND from NAND — a two-input NAND gate taking A and B, its output wire labelled with an overbar over A·B, feeding a second NAND gate whose two input terminals are tied together, final output labelled A·B
OR from NAND
Here De Morgan’s theorem is needed. Start from \(A + B\) and complement it twice:
\[A + B = \overline{\overline{A + B}} = \overline{\overline{A} \cdot \overline{B}}\]
The right-hand side is the complement of a product, which is exactly what a NAND gate produces — provided its inputs are \(\overline{A}\) and \(\overline{B}\). So complement each input with a NAND inverter and feed both into a third NAND gate. Three gates, as in Fig. 2.4-2.
Diagram
Fig. 2.4-2 – OR from NAND; input A entering a NAND gate with both terminals tied, output wire labelled A with an overbar; input B entering a second NAND gate with both terminals tied, output wire labelled B with an overbar; both these wires entering a third two-input NAND gate whose output on the right is labelled A + B
NOR from NAND
NOR is the complement of OR, so the circuit above needs one more NAND inverter at its output. Four gates, shown in Fig. 2.4-3.
Diagram
Fig. 2.4-3 – NOR from NAND; the three-gate OR arrangement of Fig. 2.4-2 producing A + B, with its output feeding a fourth NAND gate whose two input terminals are tied together; final output labelled with an overbar over A + B
XOR and XNOR from NAND
The XOR function is \(\overline{A}B + A\overline{B}\), a sum of two products, and the same double-complement move converts it:
\[\overline{A}B + A\overline{B} = \overline{\overline{\overline{A}B + A\overline{B}}} = \overline{\,\overline{\overline{A}B} \cdot \overline{A\overline{B}}\,}\]
Every complement bar in that final form sits over a product, so every one of them is a NAND gate. Two NAND inverters produce \(\overline{A}\) and \(\overline{B}\); one NAND gate produces \(\overline{\overline{A}B}\); another produces \(\overline{A\overline{B}}\); and a fifth combines the two. Fig. 2.4-4 gives the circuit, and Table 2.15 checks it wire by wire.
Diagram
Fig. 2.4-4 – XOR from NAND; inputs A and B on the left, each branching; NAND gate G1 with both terminals tied to A, output labelled A with an overbar; NAND gate G2 with both terminals tied to B, output labelled B with an overbar; NAND gate G3 taking A̅ and B, output wire marked G3; NAND gate G4 taking A and B̅, output wire marked G4; NAND gate G5 taking G3 and G4, output on the right labelled A ⊕ B
| A | B | \(\overline{A}\) | \(\overline{B}\) | G3 = \(\overline{\overline{A}B}\) | G4 = \(\overline{A\overline{B}}\) | output |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 |
The output column is 0, 1, 1, 0 — the XOR column of Table 2.8, so the circuit is right. XNOR needs one further NAND inverter on that output, making six gates in all.
Table 2.16 collects the counts.
| Gate required | Form used | Number of NAND gates |
|---|---|---|
| NOT | \(\overline{A \cdot A}\) | 1 |
| AND | \(\overline{\overline{A \cdot B}}\) | 2 |
| OR | \(\overline{\overline{A} \cdot \overline{B}}\) | 3 |
| NOR | complement of the OR arrangement | 4 |
| XOR | \(\overline{\overline{\overline{A}B} \cdot \overline{A\overline{B}}}\) | 5 |
| XNOR | complement of the XOR arrangement | 6 |
2.4.3 Realising the Gates Using NOR Only
Everything above repeats with the operations exchanged. A NOR gate produces the complement of a sum, so the aim now is to force each function into the form “complement of a sum”.
NOT and OR from NOR
Tying both inputs of a NOR gate to \(A\) gives \(\overline{A + A} = \overline{A}\): one gate. Adding such an inverter to the output of a NOR gate gives \(\overline{\overline{A + B}} = A + B\): two gates for OR. Fig. 2.4-5 shows both.
Diagram
Fig. 2.4-5 – two parts side by side. Left: NOT from NOR — a single two-input NOR gate with input A branching to both of its input terminals, output labelled with an overbar over A. Right: OR from NOR — a two-input NOR gate taking A and B, its output wire labelled with an overbar over A+B, feeding a second NOR gate whose two input terminals are tied together, final output labelled A + B
AND from NOR
Double complement and apply De Morgan’s theorem the other way round:
\[A \cdot B = \overline{\overline{A \cdot B}} = \overline{\overline{A} + \overline{B}}\]
So complement each input with a NOR inverter and feed both into a third NOR gate. Three gates, in Fig. 2.4-6.
Diagram
Fig. 2.4-6 – AND from NOR; input A entering a NOR gate with both terminals tied, output labelled A with an overbar; input B entering a second NOR gate with both terminals tied, output labelled B with an overbar; both these wires entering a third two-input NOR gate whose output on the right is labelled A·B
NAND from NOR
NAND is the complement of AND, so one more NOR inverter is added to the output of Fig. 2.4-6, giving four gates in all.
XNOR and XOR from NOR
Take the two NOR gates \(\overline{A + \overline{B}}\) and \(\overline{\overline{A} + B}\). By De Morgan’s theorem the first equals \(\overline{A}B\) and the second equals \(A\overline{B}\), so their sum is the XOR function. A third NOR gate fed by the two of them produces \(\overline{\overline{A}B + A\overline{B}}\), which is XNOR; a fourth NOR gate used as an inverter turns that into XOR. Counting the two NOR inverters needed to produce \(\overline{A}\) and \(\overline{B}\) in the first place, XNOR takes five NOR gates and XOR takes six. Fig. 2.4-7 shows the arrangement.
Diagram
Fig. 2.4-7 – XOR and XNOR from NOR; inputs A and B on the left, each branching; a NOR gate with both terminals tied to A giving A̅; a NOR gate with both terminals tied to B giving B̅; a two-input NOR gate taking A and B̅ with output wire labelled A̅B; a two-input NOR gate taking A̅ and B with output wire labelled AB̅; a two-input NOR gate taking those two wires, its output labelled A ⊙ B and marked “XNOR output”; that output feeding a final NOR gate with both terminals tied, whose output is labelled A ⊕ B and marked “XOR output”
| Gate required | Form used | Number of NOR gates |
|---|---|---|
| NOT | \(\overline{A + A}\) | 1 |
| OR | \(\overline{\overline{A + B}}\) | 2 |
| AND | \(\overline{\overline{A} + \overline{B}}\) | 3 |
| NAND | complement of the AND arrangement | 4 |
| XNOR | \(\overline{\overline{A + \overline{B}} + \overline{\overline{A} + B}}\) | 5 |
| XOR | complement of the XNOR arrangement | 6 |
Comparing Tables 2.16 and 2.17 shows the pattern clearly, and Table 2.18 sets the two universal gates side by side.
| Feature | NAND | NOR |
|---|---|---|
| Function | \(\overline{A \cdot B}\) | \(\overline{A + B}\) |
| Output is 0 only when | all inputs are 1 | at least one input is 1 |
| Gate obtained cheaply | AND, in 2 gates | OR, in 2 gates |
| Gate that costs most | XNOR, in 6 gates | XOR, in 6 gates |
| Natural expression form | sum of products | product of sums |
| Form to aim for while converting | complement of a product | complement of a sum |
The last two rows are the useful ones. A function already written as a sum of products converts naturally into NAND gates; a function written as a product of sums converts naturally into NOR gates. Choosing the wrong pairing is not wrong, but it wastes gates.
2.4.4 Converting a Circuit to NAND or NOR Form
A whole circuit can be converted at once, without replacing its gates one by one. The procedure for NAND is:
- Write the function as a sum of products, simplifying it first.
- Complement the whole expression twice, which leaves its value unchanged.
- Apply De Morgan’s theorem to the inner complement, turning the sum into a product of complemented terms.
- Read the result off: every complement bar now sits over a product, and each such bar is one NAND gate.
Take \(F = AB + \overline{A}C\). Step 2 gives \(F = \overline{\overline{AB + \overline{A}C}}\), and step 3 gives
\[F = \overline{\,\overline{AB} \cdot \overline{\overline{A}C}\,}\]
There are three bars over products, so three NAND gates: one for \(\overline{AB}\), one for \(\overline{\overline{A}C}\), and one combining them. If \(\overline{A}\) is not already available on a line of its own, a fourth NAND gate is used as an inverter to produce it. Fig. 2.4-8 shows the finished circuit.
Diagram
Fig. 2.4-8 – NAND-only circuit for F = AB + A̅C; inputs A, B and C on the left, with A branching; a NAND gate with both terminals tied to A producing A̅; a two-input NAND gate taking A and B with its output wire labelled with an overbar over AB; a two-input NAND gate taking A̅ and C with its output wire labelled with an overbar over A̅C; both these wires feeding a final two-input NAND gate whose output on the right is labelled F = AB + A̅C
For NOR the procedure is the mirror image. The function is written as a product of sums, complemented twice, and De Morgan’s theorem is applied to turn the product into a sum of complemented brackets; each bar then sits over a sum, and each such bar is one NOR gate. For \(F = (A + B)(\overline{B} + C)\) this gives
\[F = \overline{\,\overline{A + B} + \overline{\overline{B} + C}\,}\]
which is three NOR gates, plus one NOR inverter for \(\overline{B}\) if it is not already available. Fig. 2.4-9 shows it.
Diagram
Fig. 2.4-9 – NOR-only circuit for F = (A + B)(B̅ + C); inputs A, B and C on the left, with B branching; a NOR gate with both terminals tied to B producing B̅; a two-input NOR gate taking A and B with its output wire labelled with an overbar over A+B; a two-input NOR gate taking B̅ and C with its output wire labelled with an overbar over B̅+C; both these wires feeding a final two-input NOR gate whose output on the right is labelled F
2.5 Adders
Everything so far has been about deciding: a circuit looks at some conditions and reports whether something holds. Arithmetic is different. When a computer adds two numbers it is not testing a condition, it is producing a result, and that result may need more digits than the inputs had.
Binary addition of two single digits has four cases. \(0 + 0 = 0\), \(0 + 1 = 1\), \(1 + 0 = 1\), and \(1 + 1 = 10\). The first three fit in one digit; the fourth does not. So the answer must be reported as two separate bits: the sum bit, which is the digit written in that column, and the carry bit, which is passed to the next column on the left. That is exactly how addition is done on paper in any base — the carry out of one column becomes an input to the next.
A circuit built to do this is called an adder. Two kinds are needed, and the difference between them is simply whether the circuit accepts an incoming carry.
2.5.1 The Half Adder
A half adder adds two binary digits and produces two outputs, a sum and a carry. It has no input for a carry arriving from a previous column, which is why it is only half of what a general adder must do.
Its truth table is nothing more than the four cases of binary addition written out.
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Read the Sum column on its own: it is 1 exactly when the two inputs differ. That is the XOR function, so
\[\text{Sum} = A \oplus B = \overline{A}B + A\overline{B}\]
Now read the Carry column: it is 1 only when both inputs are 1, which is the AND function, so
\[\text{Carry} = A \cdot B\]
The circuit therefore needs one XOR gate and one AND gate, both fed by the same two input lines, as Fig. 2.5-1 shows. If only fundamental gates are available, the XOR gate is replaced by the arrangement of Fig. 2.2-7 and nothing else changes.
Diagram
Fig. 2.5-1 – logic circuit of a half adder; input lines A and B on the left, each branching with a junction dot; a two-input XOR gate taking A and B whose output on the right is labelled Sum = A ⊕ B; a two-input AND gate taking the same A and B whose output on the right is labelled Carry = A·B
Because a half adder is used as a component inside larger circuits, it is usually drawn as a block rather than as gates, with its two inputs on one side and its two outputs on the other. Fig. 2.5-2 gives that block, and section 2.5.3 uses it.
Diagram
Fig. 2.5-2 – block diagram of a half adder; a rectangle labelled HA with two input lines entering on the left labelled A and B, and two output lines leaving on the right, the upper labelled Carry and the lower labelled Sum
2.5.2 The Full Adder
A full adder adds three binary digits — the two digits of a column and the carry coming in from the column to its right — and produces a sum bit and a carry bit for the column to its left.
With three inputs the truth table has eight rows. Each row is worked out by adding the three input bits as ordinary numbers and writing the total as a two-bit binary number, in which the right digit is the sum and the left digit is the carry. Three inputs of 1, for instance, total 3, which is 11 in binary, so both outputs are 1.
| A | B | C | Sum | Carry |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Two things can be read straight off the table. The Sum column is 1 in exactly those four rows where an odd number of inputs are 1 — compare it with Table 2.12 — so
\[\text{Sum} = A \oplus B \oplus C\]
Written as a sum of products from the four rows concerned, it is \(\overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C} + ABC\). This form cannot be reduced at all: no two of those four rows differ in only one input, so no pair of terms can be combined, and a Karnaugh map of the Sum column yields no group larger than a single cell. The exclusive-OR form above is as compact as the sum gets.
The Carry column tells a different story. It is 1 in the four rows where at least two of the three inputs are 1, and its sum-of-products form is \(\overline{A}BC + A\overline{B}C + AB\overline{C} + ABC\). Here the terms do combine, and the three-variable Karnaugh map of Fig. 2.5-3 shows why: the cell for \(ABC\) is adjacent to each of the other three, so three overlapping pairs cover the map.
Diagram
Fig. 2.5-3 – three-variable Karnaugh map for the Carry output; one row for A = 0 and one row for A = 1, four columns labelled BC in Gray code order 00, 01, 11, 10; 1s entered in the cells for minterms 3, 5, 6 and 7 and 0s in the remaining cells; three pairs ringed — cells 3 and 7 labelled BC, cells 5 and 7 labelled AC, cells 6 and 7 labelled AB
The three groups give
\[\text{Carry} = AB + BC + AC\]
which reads back in words as: a carry is produced when at least two of the three inputs are 1. The full circuit, Fig. 2.5-4, uses two XOR gates in a chain for the sum, and three AND gates feeding a three-input OR gate for the carry.
Diagram
Fig. 2.5-4 – logic circuit of a full adder built from the reduced expressions; input lines A, B and C on the left, each branching several times with junction dots; a two-input XOR gate taking A and B, its output feeding a second two-input XOR gate whose other input is C, the final output labelled Sum = A ⊕ B ⊕ C; three two-input AND gates taking A and B, taking B and C, and taking A and C, with output wires labelled AB, BC and AC; all three AND outputs feeding a three-input OR gate whose output is labelled Carry = AB + BC + AC
| Feature | Half adder | Full adder |
|---|---|---|
| Number of inputs | 2 | 3 |
| Accepts a carry from the previous column | no | yes |
| Number of outputs | 2, a sum and a carry | 2, a sum and a carry |
| Sum expression | \(A \oplus B\) | \(A \oplus B \oplus C\) |
| Carry expression | \(AB\) | \(AB + BC + AC\) |
| Where it is used | the rightmost column of an addition, where no carry can arrive | every other column |
2.5.3 A Full Adder from Two Half Adders
A full adder need not be built from gates at all. Adding three bits can be done in two stages: add the first two, then add the third to that result. Each stage is an addition of two bits, and a circuit for that already exists.
The first half adder takes \(A\) and \(B\) and produces an intermediate sum \(S_1 = A \oplus B\) and an intermediate carry \(C_1 = AB\). The second half adder takes \(S_1\) and the input carry \(C\), and its sum output is the final sum, \(S_1 \oplus C = A \oplus B \oplus C\), which is what Table 2.20 requires. Its carry output is \(C_2 = S_1 \cdot C\).
That leaves the final carry. A carry must be reported if either stage produced one, so the two intermediate carries are combined with an OR gate:
\[\text{Carry} = C_1 + C_2 = AB + (A \oplus B)C\]
This looks unlike the \(AB + BC + AC\) obtained from the Karnaugh map, so it is worth checking that the two agree. Expanding the exclusive-OR,
\[AB + (A\overline{B} + \overline{A}B)C = AB + A\overline{B}C + \overline{A}BC\]
and expanding the other form,
\[AB + BC + AC = AB + (A + \overline{A})BC + A(B + \overline{B})C = AB + ABC + \overline{A}BC + ABC + A\overline{B}C\]
in which \(ABC\) is absorbed by \(AB\), leaving \(AB + \overline{A}BC + A\overline{B}C\). The two expressions are identical. Fig. 2.5-5 shows the arrangement.
Diagram
Fig. 2.5-5 – full adder built from two half adders; inputs A and B entering a half adder block labelled HA1, whose Sum output wire is labelled S1 and whose Carry output wire is labelled C1; the S1 wire and the input line C entering a second half adder block labelled HA2, whose Sum output on the right is labelled Sum and whose Carry output wire is labelled C2; the C1 and C2 wires entering a two-input OR gate whose output on the right is labelled Carry
Table 2.22 works out every wire of this arrangement and confirms that its two output columns are those of Table 2.20.
| A | B | C | \(S_1\) | \(C_1\) | Sum | \(C_2\) | Carry |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
One detail in that table is worth noticing. The columns \(C_1\) and \(C_2\) are never both 1 in the same row, and they cannot be: \(C_1\) is 1 only when \(A\) and \(B\) are both 1, and in that case \(S_1\) is 0, which forces \(C_2\) to 0. The final OR gate therefore never has to deal with two carries at once.
Full adders are the building blocks of addition on numbers of many bits. To add two four-bit numbers, four full adders are placed side by side, the carry output of each feeding the carry input of the next to its left, and the carry input of the rightmost one set to 0 — which is why a half adder would do for that position. The honest limitation of this simple arrangement is speed: each adder cannot settle until the one to its right has produced its carry, so the delays accumulate across the width of the number, and wider numbers take proportionally longer.
2.6 Encoders
Adders showed a circuit doing arithmetic. The next three sections show circuits doing something equally necessary and much less glamorous: moving information between the form a person or a device produces and the form the machine can work with.
2.6.1 The Need for an Encoder
Inside the machine every quantity is a pattern of bits. Outside it, information usually arrives as one signal out of many. A keypad has a separate contact under each key, so pressing the key marked 5 makes one particular line high and leaves the other nine low. A control panel has one switch per position. In each case the information is carried not by the value on a line but by which line is active.
That form is unusable as it stands. Ten lines, one of them high, would need ten wires all the way into the processor, and the processor works with four-bit patterns, not with ten wires. Something must convert “line 5 is active” into the pattern 0101. The circuit that does this is the encoder.
Diagram
Fig. 2.6-1 – block representation of an encoder; a rectangle labelled ENCODER with a bracketed group of input lines entering on the left labelled “one line active at a time, numbered 0 upwards”, and a smaller bracketed group of output lines leaving on the right labelled “binary code of the active line”
The number of lines on each side is fixed by counting. A binary code of \(n\) bits can name \(2^n\) different things, so \(n\) output lines can serve at most \(2^n\) input lines: three outputs for eight inputs, four for sixteen. An encoder is therefore always described by the two numbers together — an eight-to-three encoder, a ten-to-four encoder.
The design idea is simple enough to state in one line. Each output bit is 1 for certain input digits and 0 for the rest, so each output bit is an OR of exactly those input lines for which that bit is 1. No other kind of gate is needed.
2.6.2 The Octal to Binary Encoder
An octal digit runs from 0 to 7, so an octal keypad has eight lines. The largest digit, 7, is 111 in binary, which needs three bits. This is the eight-to-three encoder, also called the octal to binary encoder.
Table 2.23 lists what is wanted. The three outputs are named \(A\), \(B\) and \(C\), with \(A\) the most significant bit.
| Active input line | A | B | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |
| 5 | 1 | 0 | 1 |
| 6 | 1 | 1 | 0 |
| 7 | 1 | 1 | 1 |
Now read the table by columns instead of by rows, which is the step that produces the circuit. Column \(A\) holds a 1 in the rows for 4, 5, 6 and 7, so \(A\) must be 1 whenever any of those four lines is active:
\[A = 4 + 5 + 6 + 7\]
where each numeral names the input line of that digit. Column \(B\) holds a 1 for 2, 3, 6 and 7, and column \(C\) for 1, 3, 5 and 7, giving
\[B = 2 + 3 + 6 + 7 \qquad C = 1 + 3 + 5 + 7\]
Three OR gates of four inputs each are therefore the whole circuit, drawn in Fig. 2.6-2.
Diagram
Fig. 2.6-2 – octal to binary encoder; eight horizontal input lines drawn one below another on the left and labelled 0 to 7 from the top; three four-input OR gates on the right whose outputs are labelled A, B and C from the top; junction dots connecting lines 4, 5, 6 and 7 to the OR gate for A, lines 2, 3, 6 and 7 to the OR gate for B, and lines 1, 3, 5 and 7 to the OR gate for C; input line 0 shown running to the right with no connection to any gate
How the circuit works
Suppose the key for 5 is pressed, so line 5 goes high and every other line stays low. Line 5 is connected to the OR gate for \(A\) and to the OR gate for \(C\), so both of those outputs go to 1. It is not connected to the gate for \(B\), and since no other line is high, that gate sees only 0s and stays at 0. The output is \(A B C = 101\), which is 5 in binary.
Notice that line 0 in Fig. 2.6-2 goes nowhere. It does not need to, because the code for 0 is 000 and every output is 0 by default when no line is high. This is also the honest weakness of a plain encoder: pressing 0 and pressing nothing at all produce exactly the same output. Real designs add one more output, often called a valid line, which is the OR of all the input lines and which reports whether any key is pressed at all.
2.6.3 Decimal and Hexadecimal to Binary Encoders
The same reading-by-columns method builds an encoder of any size; only the number of lines changes.
Decimal to binary
A decimal keypad has ten lines, 0 to 9. The largest digit, 9, is 1001, so four output lines are needed. Table 2.24 gives the codes.
| Active input line | A | B | C | D |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 |
| 5 | 0 | 1 | 0 | 1 |
| 6 | 0 | 1 | 1 | 0 |
| 7 | 0 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 |
Reading the four columns downwards gives the four OR gates directly:
\[A = 8 + 9 \qquad B = 4 + 5 + 6 + 7 \qquad C = 2 + 3 + 6 + 7 \qquad D = 1 + 3 + 5 + 7 + 9\]
The gates are of different sizes — two inputs for \(A\) and five for \(D\) — which is normal, because the columns simply do not contain the same number of 1s. Fig. 2.6-3 shows the circuit.
Diagram
Fig. 2.6-3 – decimal to binary encoder; ten horizontal input lines on the left labelled 0 to 9 from the top; four OR gates on the right with outputs labelled A, B, C and D from the top; junction dots connecting lines 8 and 9 to the OR gate for A, lines 4, 5, 6 and 7 to the OR gate for B, lines 2, 3, 6 and 7 to the OR gate for C, and lines 1, 3, 5, 7 and 9 to the OR gate for D; input line 0 running to the right with no connection
Hexadecimal to binary
A hexadecimal digit runs from 0 to F, that is, sixteen values, and the largest of them, F, is 1111. Sixteen input lines are encoded onto four output lines, and this time every one of the sixteen possible codes is used. Table 2.25 gives the codes, and the four columns again give the four gates.
| Active input line | A | B | C | D |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 |
| 5 | 0 | 1 | 0 | 1 |
| 6 | 0 | 1 | 1 | 0 |
| 7 | 0 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 |
| A | 1 | 0 | 1 | 0 |
| B | 1 | 0 | 1 | 1 |
| C | 1 | 1 | 0 | 0 |
| D | 1 | 1 | 0 | 1 |
| E | 1 | 1 | 1 | 0 |
| F | 1 | 1 | 1 | 1 |
\[A = 8 + 9 + \mathrm{A} + \mathrm{B} + \mathrm{C} + \mathrm{D} + \mathrm{E} + \mathrm{F}\] \[B = 4 + 5 + 6 + 7 + \mathrm{C} + \mathrm{D} + \mathrm{E} + \mathrm{F}\] \[C = 2 + 3 + 6 + 7 + \mathrm{A} + \mathrm{B} + \mathrm{E} + \mathrm{F}\] \[D = 1 + 3 + 5 + 7 + 9 + \mathrm{B} + \mathrm{D} + \mathrm{F}\]
Each of the four OR gates now has eight inputs, and each column of the table has exactly eight 1s in it — which is no coincidence, since over the sixteen four-bit patterns every bit position is 1 in half of them. Fig. 2.6-4 shows the circuit.
Diagram
Fig. 2.6-4 – hexadecimal to binary encoder; sixteen horizontal input lines on the left labelled 0 to 9 and then A to F from the top; four eight-input OR gates on the right with outputs labelled A, B, C and D from the top; junction dots connecting lines 8, 9, A, B, C, D, E and F to the OR gate for output A; lines 4, 5, 6, 7, C, D, E and F to the OR gate for output B; lines 2, 3, 6, 7, A, B, E and F to the OR gate for output C; and lines 1, 3, 5, 7, 9, B, D and F to the OR gate for output D; input line 0 running to the right with no connection
To trace it once: pressing the key for 9 makes line 9 high, and line 9 reaches the OR gates for \(A\) and for \(D\) only. Those two outputs become 1, the other two stay 0, and the machine receives 1001.
2.7 Decoders
An encoder takes information in from the outside world. Sooner or later the machine has to send information back out — light the right segment of a display, select the right memory row, switch on the right device. Then the conversion is needed in the opposite direction, and the circuit that performs it is the decoder.
2.7.1 How a Decoder Reverses an Encoder
A decoder takes a binary code on a few input lines and makes exactly one of many output lines high — the one whose number is the value of the code. Where an encoder answers “which line is active?” with a code, a decoder answers “what does this code mean?” by activating a line.
Diagram
Fig. 2.7-1 – block representation of a decoder; a rectangle labelled DECODER with a bracketed group of input lines entering on the left labelled “binary code”, and a larger bracketed group of output lines leaving on the right labelled “one line high, numbered 0 upwards”
The counting runs the other way from an encoder: \(n\) input lines can carry \(2^n\) different codes, so a decoder with three inputs has eight outputs and one with four inputs has sixteen. Such circuits are named by the two numbers, a three-to-eight decoder or a four-to-sixteen decoder.
The design idea is again a single sentence, and it is the mirror image of the encoder’s. Each output line must be high for exactly one combination of the inputs, so each output line is an AND of all the input variables — each variable taken as it stands where that combination has a 1, and complemented where it has a 0. Every output is therefore a minterm, and the circuit needs one AND gate per output plus one inverter per input.
| Feature | Encoder | Decoder |
|---|---|---|
| Direction of conversion | one active line to a binary code | a binary code to one active line |
| Number of inputs against outputs | many inputs, few outputs | few inputs, many outputs |
| Sizes | 8 to 3, 10 to 4, 16 to 4 | 3 to 8, 4 to 16 |
| Gate used for each output | one OR gate | one AND gate, with inverters on the input lines |
| State during operation | one input line high at a time | one output line high at a time |
| Typical placement | between an input device and the processor | between the processor and the device being selected |
2.7.2 The Binary to Octal Decoder
Three input lines carry a code from 000 to 111, and each of those eight codes names one octal digit. The circuit that lights one of eight lines from this code is the three-to-eight decoder, or binary to octal decoder. Call the inputs \(A\), \(B\) and \(C\), with \(A\) the most significant bit, and name the outputs \(D_0\) to \(D_7\).
| A | B | C | Output line that is high | Product term for that output |
|---|---|---|---|---|
| 0 | 0 | 0 | \(D_0\) | \(\overline{A}\,\overline{B}\,\overline{C}\) |
| 0 | 0 | 1 | \(D_1\) | \(\overline{A}\,\overline{B}C\) |
| 0 | 1 | 0 | \(D_2\) | \(\overline{A}B\overline{C}\) |
| 0 | 1 | 1 | \(D_3\) | \(\overline{A}BC\) |
| 1 | 0 | 0 | \(D_4\) | \(A\overline{B}\,\overline{C}\) |
| 1 | 0 | 1 | \(D_5\) | \(A\overline{B}C\) |
| 1 | 1 | 0 | \(D_6\) | \(AB\overline{C}\) |
| 1 | 1 | 1 | \(D_7\) | \(ABC\) |
In every row of that table, the one output named is 1 and the other seven are 0. Each product term is built by the rule already given: take the variable itself where the bit is 1, and its complement where the bit is 0. The output \(D_5\), for example, corresponds to 101, so it is \(A\overline{B}C\).
The circuit therefore needs three inverters, to make \(\overline{A}\), \(\overline{B}\) and \(\overline{C}\) available, and eight AND gates of three inputs each. Fig. 2.7-2 shows it.
Diagram
Fig. 2.7-2 – binary to octal decoder; three vertical input lines at the left labelled A, B and C, each passing through a NOT gate so that both the line and its complement run down the diagram as separate vertical rails; eight three-input AND gates stacked on the right with outputs labelled D0 to D7 from the top; junction dots taking A̅, B̅, C̅ to the gate for D0; A̅, B̅, C to D1; A̅, B, C̅ to D2; A̅, B, C to D3; A, B̅, C̅ to D4; A, B̅, C to D5; A, B, C̅ to D6; and A, B, C to D7
How the circuit works
Suppose the input code is 110. The gate for \(D_6\) is the only one fed by \(A\), \(B\) and \(\overline{C}\), and with \(A = 1\), \(B = 1\) and \(C = 0\) all three of its inputs are 1, so it produces 1. Every other gate is fed by at least one line that is currently 0 — the gate for \(D_7\), for instance, is fed by \(C\), which is 0 — so every other output stays at 0. Exactly one line goes high, and it is line 6, which is the octal value of 110.
There is a second way of looking at Fig. 2.7-2 that turns out to be useful. Each AND gate produces one minterm of the three variables, so a decoder is a circuit that generates every minterm of its inputs at once. Any function of those three variables can then be produced simply by ORing together the decoder outputs for the rows in which the function is 1 — no further AND gates and no inverters required. Section 2.8 builds a circuit on exactly this idea.
2.7.3 The Binary to Hexadecimal Decoder
Four input lines carry sixteen codes, and each names one hexadecimal digit from 0 to F. The circuit is the four-to-sixteen decoder. Nothing about the method changes: four inverters supply the complements, and sixteen AND gates of four inputs each produce the sixteen minterms.
| A | B | C | D | Output line that is high | Product term for that output |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | \(D_0\) | \(\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}\) |
| 0 | 0 | 0 | 1 | \(D_1\) | \(\overline{A}\,\overline{B}\,\overline{C}D\) |
| 0 | 0 | 1 | 0 | \(D_2\) | \(\overline{A}\,\overline{B}C\overline{D}\) |
| 0 | 0 | 1 | 1 | \(D_3\) | \(\overline{A}\,\overline{B}CD\) |
| 0 | 1 | 0 | 0 | \(D_4\) | \(\overline{A}B\overline{C}\,\overline{D}\) |
| 0 | 1 | 0 | 1 | \(D_5\) | \(\overline{A}B\overline{C}D\) |
| 0 | 1 | 1 | 0 | \(D_6\) | \(\overline{A}BC\overline{D}\) |
| 0 | 1 | 1 | 1 | \(D_7\) | \(\overline{A}BCD\) |
| 1 | 0 | 0 | 0 | \(D_8\) | \(A\overline{B}\,\overline{C}\,\overline{D}\) |
| 1 | 0 | 0 | 1 | \(D_9\) | \(A\overline{B}\,\overline{C}D\) |
| 1 | 0 | 1 | 0 | \(D_\mathrm{A}\) | \(A\overline{B}C\overline{D}\) |
| 1 | 0 | 1 | 1 | \(D_\mathrm{B}\) | \(A\overline{B}CD\) |
| 1 | 1 | 0 | 0 | \(D_\mathrm{C}\) | \(AB\overline{C}\,\overline{D}\) |
| 1 | 1 | 0 | 1 | \(D_\mathrm{D}\) | \(AB\overline{C}D\) |
| 1 | 1 | 1 | 0 | \(D_\mathrm{E}\) | \(ABC\overline{D}\) |
| 1 | 1 | 1 | 1 | \(D_\mathrm{F}\) | \(ABCD\) |
Diagram
Fig. 2.7-3 – binary to hexadecimal decoder; four vertical input lines at the left labelled A, B, C and D, each passing through a NOT gate so that eight vertical rails run down the diagram, one for each variable and one for each complement; sixteen four-input AND gates stacked on the right with outputs labelled D0 to D9 and then DA to DF from the top; junction dots connecting each AND gate to the four rails named by the product term for that output in Table 2.28, so that the topmost gate takes A̅, B̅, C̅, D̅ and the bottom gate takes A, B, C, D
Reading one row as a check: the code 1010 makes \(A = 1\), \(B = 0\), \(C = 1\), \(D = 0\), so the only gate whose four inputs are all 1 is the one fed by \(A\), \(\overline{B}\), \(C\) and \(\overline{D}\), which is the gate for \(D_\mathrm{A}\). Hexadecimal A is decimal 10, and 1010 is indeed 10 in binary.
2.8 Multiplexers
Encoders and decoders change the form in which information is carried. A multiplexer does something different: it leaves the information alone and chooses which of several signals is allowed through.
2.8.1 Selecting One Signal from Many
Inside a computer, several sources often need to send data along the same path — a single bus, a single line to a display, a single input to an arithmetic circuit. Running a separate wire from every source is wasteful and quickly impossible. The alternative is to share one line and let a control signal decide, moment by moment, whose data travels on it.
A multiplexer, usually shortened to MUX, is the circuit that makes that choice. It has a number of data input lines, a smaller number of select lines, and exactly one output. Whatever value is present on the chosen data line appears at the output; the values on all the other data lines are ignored. Because many lines enter and one leaves, it is described as a many-to-one circuit.
Diagram
Fig. 2.8-1 – block representation of a multiplexer; a rectangle labelled MUX with a bracketed group of lines entering on the left labelled “data inputs”, a single line leaving on the right labelled “output”, and a bracketed group of lines entering from below labelled “select lines”
The counting is the same as for a decoder, because a multiplexer contains one. With \(n\) select lines there are \(2^n\) different select codes, so \(2^n\) data lines can be distinguished: two select lines for four data inputs, three for eight, four for sixteen. A multiplexer is named by the number of data inputs and its single output — a \(4 \times 1\) multiplexer, an \(8 \times 1\) multiplexer.
2.8.2 The 4 × 1 Multiplexer
Take four data lines \(D_0\), \(D_1\), \(D_2\) and \(D_3\), and two select lines \(A\) and \(B\), with \(A\) the more significant. Table 2.29 states what is required.
| A | B | Data line passed to the output |
|---|---|---|
| 0 | 0 | \(D_0\) |
| 0 | 1 | \(D_1\) |
| 1 | 0 | \(D_2\) |
| 1 | 1 | \(D_3\) |
Building this needs two ideas already available. The select lines are decoded, exactly as in section 2.7.2, so that each select code raises one internal line; and each of those internal lines is used to open a gate for its own data line. An AND gate does the opening: if one input of an AND gate is held at 1 the gate passes the other input unchanged, and if it is held at 0 the gate blocks it, as section 2.2.2 noted. The four gate outputs are then combined by an OR gate, which is safe because at most one of them can be non-zero at a time.
Written as an expression, the output is
\[Y = \overline{A}\,\overline{B}D_0 + \overline{A}BD_1 + A\overline{B}D_2 + ABD_3\]
Each product contains one minterm of the select variables and one data variable. Fig. 2.8-2 shows the circuit: two inverters, four AND gates of three inputs each, and one OR gate of four inputs.
Diagram
Fig. 2.8-2 – logic circuit of a 4 × 1 multiplexer; four horizontal data input lines on the left labelled D0, D1, D2 and D3 from the top; two vertical select lines at the left labelled A and B, each passing through a NOT gate so that four vertical rails A, A̅, B and B̅ run down the diagram; four three-input AND gates, the first taking D0 with A̅ and B̅, the second taking D1 with A̅ and B, the third taking D2 with A and B̅, the fourth taking D3 with A and B; all four AND outputs feeding one four-input OR gate whose output on the right is labelled Y
How the circuit works
Suppose the select lines carry \(A = 1\), \(B = 1\). Then only the fourth AND gate has both of its select inputs at 1, so that gate passes \(D_3\) through unchanged. The other three gates each have at least one select input at 0 and so produce 0 whatever their data lines carry. The OR gate receives \(D_3\) and three 0s, and \(D_3\) is what appears at \(Y\).
Table 2.30 traces the circuit with actual data held on the four lines, letting the select code run through all four values.
| A | B | first AND gate | second AND gate | third AND gate | fourth AND gate | Y |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
The output column reproduces the data values 1, 0, 0, 1 in order, which is the whole point: the multiplexer has delivered each stored value in turn onto a single output line.
2.8.3 The 8 × 1 Multiplexer
Eight data lines need three select lines, and the design is the same one line larger. Call the data lines \(D_0\) to \(D_7\) and the select lines \(A\), \(B\) and \(C\), with \(A\) the most significant.
| A | B | C | Data line passed to the output |
|---|---|---|---|
| 0 | 0 | 0 | \(D_0\) |
| 0 | 0 | 1 | \(D_1\) |
| 0 | 1 | 0 | \(D_2\) |
| 0 | 1 | 1 | \(D_3\) |
| 1 | 0 | 0 | \(D_4\) |
| 1 | 0 | 1 | \(D_5\) |
| 1 | 1 | 0 | \(D_6\) |
| 1 | 1 | 1 | \(D_7\) |
The output expression follows the same pattern, one product for each row of the table:
\[Y = \overline{A}\,\overline{B}\,\overline{C}D_0 + \overline{A}\,\overline{B}CD_1 + \overline{A}B\overline{C}D_2 + \overline{A}BCD_3 + A\overline{B}\,\overline{C}D_4 + A\overline{B}CD_5 + AB\overline{C}D_6 + ABCD_7\]
The circuit is a binary to octal decoder driving eight AND gates, whose outputs meet at one OR gate, as Fig. 2.8-3 shows.
Diagram
Fig. 2.8-3 – logic circuit of an 8 × 1 multiplexer; eight horizontal data input lines on the left labelled D0 to D7 from the top; three vertical select lines labelled A, B and C, each passing through a NOT gate so that six vertical rails A, A̅, B, B̅, C and C̅ run down the diagram; eight four-input AND gates, each taking one data line together with the three select rails named by its row of Table 2.31, so that the topmost gate takes D0 with A̅, B̅ and C̅ and the bottom gate takes D7 with A, B and C; all eight AND outputs feeding one eight-input OR gate whose output on the right is labelled Y
To trace one case: with \(A = 1\), \(B = 0\), \(C = 1\) the only AND gate whose three select inputs are all 1 is the one wired to \(A\), \(\overline{B}\) and \(C\), which is the gate for \(D_5\). That gate passes \(D_5\) to the OR gate; the other seven gates contribute 0; so \(Y = D_5\), and 101 is indeed 5 in binary.
| Feature | Multiplexer | Decoder |
|---|---|---|
| Purpose | selects one of many data signals | activates one of many output lines |
| Lines | \(2^n\) data inputs, \(n\) select inputs, 1 output | \(n\) inputs, \(2^n\) outputs |
| Direction | many to one | one to many |
| What the code does | names the data line to be passed | names the output line to be raised |
| Output carries | the value of the selected data line | a 1 on one line and 0 on the rest |
| Relation between them | contains a decoder, plus one AND gate per data line and one OR gate | is a component of the multiplexer |
A multiplexer saves wires, and what it pays is time. Only one source reaches the output at any moment, so if several sources must all be served, the select code has to be changed in turn and each source gets the line for part of the time. Sending data this way, one line at a time along a shared path, is exactly what is meant by sharing a bus, and it is also how a set of values held side by side can be sent out one after another on a single wire.
2.9 Summary
From algebra to hardware
A wire inside a machine carries one of two voltage ranges, read as high (1) or low (0). Because a Boolean variable also has exactly two values, Boolean algebra describes hardware exactly, and an expression on paper becomes a plan for a circuit.
In a switching circuit, two switches wired one after the other behave as AND, two switches wired side by side behave as OR, and a switch placed as a bypass across the lamp behaves as complement.
A logic gate is an electronic circuit with one or more binary inputs and a single binary output, the output being fixed by a Boolean operation on the inputs. Gates are supplied as integrated circuits (IC).
A circuit built only from gates is combinational: its output depends only on the input values present at that moment, and it can remember nothing.
Every gate and every circuit has three descriptions — the symbol, which shows the wiring; the Boolean expression, which can be simplified; and the truth table, which settles whether two circuits are equivalent. A circuit with \(n\) inputs has a truth table of \(2^n\) rows, written in standard binary counting order.
The seven gates
NOT, AND and OR are the fundamental logic gates. NOT gives \(\overline{A}\); AND gives \(A \cdot B\) and is 1 only when all inputs are 1; OR gives \(A + B\) and is 1 when at least one input is 1.
NAND, NOR, XOR and XNOR are the derived logic gates. NAND gives \(\overline{A \cdot B}\) and is 0 only when all inputs are 1. NOR gives \(\overline{A + B}\) and is 1 only when all inputs are 0.
XOR gives \(\overline{A}B + A\overline{B}\), written \(A \oplus B\): for two inputs it is 1 when they differ, and for more inputs it is 1 when an odd number of them are 1. XNOR gives \(\overline{A}\,\overline{B} + AB\), written \(A \odot B\), and is the complement of XOR.
AND, OR, XOR and XNOR may be cascaded to obtain more inputs, because those operations are associative. NAND and NOR may not: two cascaded two-input NAND gates do not give a three-input NAND.
Drawing, reading and designing circuits
A circuit is drawn from an expression by respecting precedence — complement first, then AND, then OR — so that the operation performed last becomes the gate nearest the output.
A circuit is read by labelling the output wire of each gate in turn from the inputs towards the output; the label on the last wire is the expression of the circuit.
A circuit is designed from a statement of required behaviour by writing the truth table, taking each row whose output is 1 to form one product term, summing those terms, simplifying, and only then drawing. Simplifying is what decides how much hardware is bought.
Universal gates
A universal gate is one from which every other gate, and hence every Boolean function, can be built. NAND and NOR are the two universal gates.
The construction rests on De Morgan’s theorem, \(\overline{A \cdot B} = \overline{A} + \overline{B}\) and \(\overline{A + B} = \overline{A} \cdot \overline{B}\), which exchanges a sum for a product at the cost of complementing the inputs and the output.
Using NAND gates alone: NOT takes 1 gate, AND 2, OR 3, NOR 4, XOR 5 and XNOR 6. Using NOR gates alone the picture is mirrored: NOT takes 1 gate, OR 2, AND 3, NAND 4, XNOR 5 and XOR 6.
A whole circuit is converted by complementing the expression twice and applying De Morgan’s theorem to the inner complement. A sum of products then becomes NAND gates; a product of sums becomes NOR gates. Universality costs extra gates, not lost capability.
Adders
Adding two binary digits produces two outputs, because \(1 + 1 = 10\): the sum bit written in that column and the carry bit passed to the column on the left.
A half adder adds two bits. Its outputs are \(\text{Sum} = A \oplus B\) and \(\text{Carry} = A \cdot B\), so it needs one XOR gate and one AND gate. It has no input for an incoming carry, which is why it is only half an adder.
A full adder adds three bits — two digits and an input carry. Its outputs are \(\text{Sum} = A \oplus B \oplus C\) and \(\text{Carry} = AB + BC + AC\), the carry being 1 whenever at least two of the three inputs are 1.
The sum expression of a full adder cannot be reduced, because no two of its four minterms differ in only one variable. The carry expression can be, and a Karnaugh map gives the three-term form above.
A full adder can be assembled from two half adders and one OR gate: the first adds \(A\) and \(B\), the second adds that sum to \(C\), and the OR gate combines the two intermediate carries, which can never both be 1.
Numbers of many bits are added by placing full adders side by side, each carry output feeding the next carry input. The limitation is speed: each stage must wait for the carry from the stage to its right.
Encoders, decoders and multiplexers
An encoder converts one active input line into its binary code on a smaller set of output lines. Each output is an OR of exactly those input lines whose code has a 1 in that position. Common sizes are 8 to 3 (octal to binary), 10 to 4 (decimal to binary) and 16 to 4 (hexadecimal to binary).
A plain encoder assumes that exactly one input line is active. If two are active together its output is the merged code of both, which names neither.
A decoder reverses this: \(n\) input lines carry a code and exactly one of up to \(2^n\) output lines is raised. Each output is one minterm of the input variables, so a decoder needs one AND gate per output and one inverter per input, and it generates every minterm of its inputs at once.
A multiplexer has \(2^n\) data inputs, \(n\) select lines and one output, and passes to the output the value on the data line named by the select code. It is built from a decoder on the select lines, one AND gate per data line and one OR gate. Its output is a value, not the select code.
A multiplexer saves wiring at the cost of time, since only one source uses the shared line at a time. The demultiplexer performs the opposite task, delivering one input to the output line named by the select code.
2.10 Key Terms
Adder — a circuit that adds binary digits and reports the result as a sum bit and a carry bit.
Boolean expression — the algebraic description of a circuit, and the only one of the three descriptions that can be simplified by the laws of Boolean algebra.
Carry — the bit passed on to the next column on the left when the digits of a column add up to more than one can hold.
Combinational circuit — a circuit whose output depends only on the input values present at that moment, with no memory of earlier values.
Decoder — a circuit with \(n\) input lines and up to \(2^n\) output lines which raises exactly the one output line named by the code on its inputs.
Derived logic gates — the four gates built from the fundamental ones: NAND, NOR, XOR and XNOR.
Encoder — a circuit that converts one active input line into the binary code of that line on a smaller set of output lines.
Full adder — a circuit that adds three bits, two digits and an incoming carry, giving a sum bit and a carry bit.
Fundamental logic gates — the three gates that carry out the operations of Boolean algebra directly: NOT, AND and OR; also called basic gates.
Half adder — a circuit that adds two bits, giving a sum bit and a carry bit, with no provision for an incoming carry.
High — the state of a line whose voltage lies in the upper of the two agreed ranges, read as 1.
IC — integrated circuit.
Integrated circuit (IC) — many electronic components formed together on a single small chip and sealed in one package, such as a package holding four gates.
Inverter — another name for the NOT gate, since its work is to invert the signal it is given.
Logic circuit — gates connected together so that the arrangement produces the value of a required Boolean function of its inputs.
Logic gate — an electronic circuit with one or more binary inputs and a single binary output fixed by a Boolean operation on those inputs.
Low — the state of a line whose voltage lies in the lower of the two agreed ranges, read as 0.
Multiplexer — a circuit with \(2^n\) data inputs, \(n\) select lines and one output, which passes to the output the value on the data line named by the select code.
MUX — multiplexer.
POS — product of sums.
Product of sums (POS) — an expression written as several sum terms multiplied together, obtained from the rows of a truth table in which the output is 0.
Select lines — the control inputs of a multiplexer, whose binary code names the data line to be passed to the output.
SOP — sum of products.
Sum — the bit written in a column when its digits are added, as distinct from the carry sent to the next column.
Sum of products (SOP) — an expression written as several product terms added together, obtained from the rows of a truth table in which the output is 1.
Switching circuit — a circuit of switches in which the behaviour of the whole depends only on which switches are open and which are closed.
Symbol — the standard shape used for a gate in a circuit diagram, showing how the parts are wired.
Truth table — a listing of the output of a circuit for every possible combination of its inputs, in standard binary counting order.
Universal gate — a gate from which every other gate, and hence every Boolean function, can be built; NAND and NOR are the two universal gates.
2.11 Points to Ponder
If NAND gates alone can build every circuit, why does any designer keep the other six gates in the catalogue at all? What would actually be lost by a factory that stocked nothing else?
The sum output of the full adder cannot be reduced by a single term, while its carry output reduces neatly. What is it about a function that decides whether simplification is possible — and does an unsimplifiable function mean the problem was badly stated, or simply that some jobs are irreducibly complicated?
A plain encoder produces a code that names neither key when two keys are pressed together, yet no gate in it has failed and no line is miswired. Where should the responsibility for that behaviour be placed: in the circuit, in the truth table, or in the specification that never said what should happen?
A decoder produces every minterm of its inputs at once, so any function of those inputs can be obtained by ORing the right decoder outputs together, with no simplification needed. Why, then, is a Karnaugh map still worth learning?
Simplifying an expression usually reduces the number of gates but can increase the number of kinds of gate a circuit needs. Which of the two is the better thing to minimise, and does the answer change if the circuit is to be built once for a school project rather than a million times in a factory?
A multiplexer saves wires by spending time: one source at a time uses the shared line. Where else in computing does the same trade between space and time appear, and is there any reason to believe it can be escaped rather than merely shifted?
2.12 Objective Questions
- The gate whose output is 1 only when every one of its inputs is 0 is the: [1 mark]
- NAND gate
- NOR gate
- XOR gate
- AND gate
- The number of NAND gates required to realise an OR gate is: [1 mark]
- 1
- 2
- 3
- 4
- The Boolean expression for the sum output of a full adder with inputs A, B and C is: [1 mark]
- \(A \oplus B\)
- \(AB + BC + AC\)
- \(A \oplus B \oplus C\)
- \(ABC\)
- A multiplexer that selects one of eight data inputs must have: [1 mark]
- 2 select lines
- 3 select lines
- 4 select lines
- 8 select lines
- A signal X is passed through 51 NOT gates connected one after the other. The output is: [1 mark]
- \(X\)
- \(\overline{X}\)
- 1
- 0
- In a decoder with four input lines, the number of AND gates in the circuit is: [1 mark]
- 4
- 8
- 16
- 32
- Assertion (A): The NAND gate is called a universal gate. Reason (R): Every Boolean function can be written as a sum of products, and NOT, AND and OR can each be built from NAND gates alone. Choose the correct option: [1 mark]
- Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
- Both Assertion (A) and Reason (R) are true but Reason (R) is not the correct explanation of Assertion (A).
- Assertion (A) is true but Reason (R) is false.
- Assertion (A) is false but Reason (R) is true.
- Assertion (A): A half adder can be used for the rightmost column of a binary addition. Reason (R): A half adder has no input line for a carry arriving from a previous column. Choose the correct option: [1 mark]
- Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
- Both Assertion (A) and Reason (R) are true but Reason (R) is not the correct explanation of Assertion (A).
- Assertion (A) is true but Reason (R) is false.
- Assertion (A) is false but Reason (R) is true.
- Match each circuit in column X with its description in column Y: [1 mark]
| Column X | Column Y |
|---|---|
| a. Encoder | i. passes one of several data signals to a single output |
| b. Decoder | ii. produces a sum bit and a carry bit from two bits |
| c. Multiplexer | iii. converts one active input line into a binary code |
| d. Half adder | iv. raises one output line named by a binary code |
Fill in the blank: in a decoder, each output line is produced by one AND gate and therefore corresponds to a single ______ of the input variables. [1 mark]
State whether the following is true or false: two two-input NAND gates connected one after the other behave as a three-input NAND gate. [1 mark]
Give the full forms of: (i) IC (ii) MUX (iii) SOP (iv) POS. [1 mark]
2.13 Check Your Concepts
Define a universal gate and name the two gates that are universal. [2 marks]
State the Boolean expressions for the sum output and the carry output of a half adder, and name the gate used for each. [2 marks]
Why is a plain encoder unable to give a correct output when two of its input lines are active at the same time? Illustrate with one example. [2 marks]
Differentiate between an encoder and a decoder, giving three points of difference. [3 marks]
Verify De Morgan’s theorem \(\overline{A + B} = \overline{A} \cdot \overline{B}\) using a truth table. [3 marks]
Convert \(F = A\overline{B} + BC\) into a form that uses NAND operations only, showing the steps, and state how many NAND gates the circuit needs if the complemented inputs are already available. [3 marks]
A hostel corridor lamp is to be switched on when the corridor sensor reports darkness and either the main switch is on or the night-duty switch is on. Name the three input variables, write the truth table, obtain the sum-of-products expression, simplify it and draw the logic circuit for the simplified expression. [4 marks]
With the help of the truth table of a full adder, explain why its sum output cannot be simplified while its carry output can. State the reduced expression for the carry. [4 marks]
Draw the logic circuit of a half adder using NAND gates only. State the number of NAND gates used for each of the two outputs, and verify the sum output with a truth table. [4 marks]
Given the three-input truth table of a full adder, derive the sum-of-products expressions for both outputs, reduce the carry expression using a Karnaugh map showing the groups, and draw the complete logic circuit. [6 marks]
Draw the logic circuit of a \(4 \times 1\) multiplexer, write the Boolean expression for its output, explain its working when the select lines carry the code 10, and state two differences between a multiplexer and a decoder. [6 marks]
2.14 Output & Debugging
Complete the truth table of \(F = \overline{A}B + A\overline{C}\) for all eight combinations of A, B and C, using separate columns for the two product terms. State how many rows give an output of 1. [3 marks]
Study the circuit of Fig. 2.14-1. Write the Boolean expression carried by each of the marked wires (1) and (2), write the expression for the final output F, and state the value of F when P = 1, Q = 0 and R = 1. [3 marks]
Diagram
Fig. 2.14-1 – circuit for the question; inputs P, Q and R entering from the left with P branching once; a two-input NAND gate taking P and Q, its output wire marked (1); a NOT gate on R producing R̅; a two-input AND gate taking wire (1) and R̅, its output wire marked (2); a two-input OR gate taking wire (2) and the input P, its output on the right labelled F
A student builds a half adder using an OR gate for the sum output and an AND gate for the carry output. Name the single input combination at which the circuit gives a wrong answer, state what it produces and what it should produce, and give the correction. [3 marks]
In an octal to binary encoder, input lines 2 and 4 are made active at the same time. State the code that appears on the three output lines, explain how that code arises, and say which octal digit it names. [2 marks]
A NAND gate has both of its inputs tied to the line A. Its output is taken to both inputs of a second NAND gate. State the expression at the output of each gate and name the single gate to which the whole arrangement is equivalent. [2 marks]
Fig. 2.14-2 shows a four-variable Karnaugh map for \(F(A, B, C, D)\) in which a student has ringed one quad and two pairs, giving \(F = \overline{A}\,\overline{C} + A\overline{B}C + ABC\). State whether every group ringed is valid, explain why the grouping is nevertheless not the smallest possible, and write the fully reduced expression. [4 marks]
Diagram
Fig. 2.14-2 – four-variable Karnaugh map for the question; rows labelled AB and columns labelled CD, both in Gray code order 00, 01, 11, 10; 1s entered in the cells for minterms 0, 1, 4, 5, 10, 11, 14 and 15 and 0s in the remaining eight cells; a quad ringed round cells 0, 1, 4 and 5, a pair ringed round cells 10 and 11, and a second pair ringed round cells 14 and 15