Logic Gates: From a Switch to an ALU

Every computer, from a phone to a data center, calculates with circuits built from a few kinds of tiny decisions: is a signal on, or is it off? This article starts with a single switch and ends with an arithmetic logic unit, the ALU, the part of a processor that adds, subtracts and compares. Every step comes with a circuit you can click.

The arithmetic part follows David Goldberg's appendix “Computer Arithmetic”[6] in John L. Hennessy and David A. Patterson's Computer Architecture: A Quantitative Approach [5], a book that judges every design by numbers: how fast is it, and what does it cost?

Ones and zeros

A computer does not know numbers, letters or colors. Deep down it only knows signals that are either on or off. We write them as 1 and 0 and call one such value a bit. On a chip a bit is a voltage: close to the supply voltage for 1, close to zero for 0. Two states are robust: a signal that picked up a little noise on its way is still clearly high or clearly low.

Long before electronics, George Boole published a book in 1854 that treats logical reasoning as a kind of algebra [1]. The algebra with the values 0 and 1 and the operations AND, OR and NOT is named after him today: Boolean algebra. In 1938 Claude Shannon showed that this algebra can describe and simplify circuits of relays and switches [3]. That is the idea this whole article builds on: logic can be built from switches.

Two switches are already enough to see it. In series, the lamp lights up only if A and B are closed. Side by side, one of them is enough: A or B. Click the switches.

The basic gates

A gate is a tiny circuit that computes one such function. On today's chips gates are made of transistors, switches that are controlled by a voltage instead of a finger. Three gates are the basis of everything:

• NOT turns its input around: 0 becomes 1, 1 becomes 0.
• AND outputs 1 only if all inputs are 1, like the switches in series.
• OR outputs 1 if at least one input is 1, like the switches side by side.

A truth table lists the output for every combination of inputs; with two inputs there are four rows. Three more gates are just as common: NAND and NOR are AND and OR with an inverted output, and XOR, the exclusive or, outputs 1 when its inputs differ. In the symbols, the small circle at the output always means “inverted”.

A fun fact about real chips: in CMOS, the transistor technology of nearly all chips today, the inverting gates NAND and NOR are the smallest. An AND is a NAND with an extra inverter behind it. Ready for a little test? A gate hides in the box below. Try inputs until you know which one it is.

Rules of the game

Gates obey rules, much like numbers do: A AND 1 = A, A OR 1 = 1, A AND A = A. Two of the most useful ones are named after Augustus De Morgan, a contemporary of Boole, whose book Formal Logic appeared in 1847 [2]:

• NOT (A AND B) = (NOT A) OR (NOT B)
• NOT (A OR B) = (NOT A) AND (NOT B)

In words: an inverted AND is the same as an OR of the inverted inputs, and the other way round. Two completely different circuits, one result. Check it: there are only four input combinations, so you can try them all.

Something even more surprising: one kind of gate is enough for everything. Henry M. Sheffer showed in 1913 that all of Boolean algebra can be built from a single operation [4]. His operation was “neither … nor”, our NOR, and NAND works just as well. That is why NAND and NOR are called universal gates.

Counting with bits

A single bit only says yes or no. Several bits side by side make a number. As with decimal digits, every position has a value, only the values double instead of growing tenfold: 1, 2, 4, 8 and so on. Eight bits can count from 0 to 255.

And negative numbers? Goldberg lists four ways to write them in bits and calls two's complement the most widely used [6, pp. J-7–J-8]. The idea: the top bit counts negative, −128 for eight bits, all others count positive as before[6, Eq. J.2.3]. 11111111 is then −1, and eight bits cover −128 to 127. A number and its negative add up to 2ⁿ, here 256 [6, p. J-7]. Switch the reading below and see what the same bits mean.

Half adder and full adder

Binary addition works like written addition at school, one column at a time: 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 10, a 0 and a carry of 1 into the next column. Goldberg's appendix starts its integer arithmetic exactly here [6, p. J-2]. A half adder adds two bits a and b: its sum is s = a XOR b, its carry c = a AND b.

A full adder also takes the carry from the column to its right as a third input. Its sum is 1 when an odd number of its inputs is 1, its carry when at least two of them are[6, Eqs. J.2.1, J.2.2]. It can be built from two half adders and an OR gate:

The ripple-carry adder

To add two numbers of n bits, put n full adders in a row and connect the carry out of each to the carry in of the next. This is the ripple-carry adder [6, p. J-3, Fig. J.1]. The carry into the lowest bit is 0 for now; it will come in handy for subtraction.

Now the question Hennessy and Patterson's book asks of every design: how fast is it? Goldberg counts logic levels, the number of gates a signal has to pass one after another, because exact timings depend on the technology. A full adder needs two levels for its carry, so the carry out of the top bit is ready after 2n levels [6, p. J-3]: 16 for 8 bits, 128 for 64 bits. The ripple-carry adder is the slowest adder, but also the cheapest[6, p. J-3]. Press “Worst case” and follow the carry from right to left. Until it arrives, the outputs show a wrong sum.

Faster adders compute the carries in parallel. A carry-lookahead adder uses two signals per bit: generate, g = a AND b, this bit creates a carry by itself, and propagate, p = a OR b, this bit passes an incoming carry on [6, p. J-37]. With them every carry can be written down directly from the inputs. A pure carry-lookahead adder needs only five logic levels, but for many bits its gates would need impractically many inputs. So real designs arrange the same idea as a tree that needs about log₂ n levels instead of 2n [6, pp. J-38–J-39]. A few more gates for a much faster adder: quantitative design in a nutshell.

Subtraction and overflow

Subtraction needs no new circuit. In two's complement, the negative of a number is: invert every bit, then add 1. So a − b = a + (NOT b) + 1: invert b on its way into the adder and set the carry into the lowest bit to 1 [6, p. J-8]. That is what the carry input was for.

With a fixed number of bits, a result can be too large. Goldberg describes how to detect this overflow: for unsigned numbers there is a carry out of the top bit; for two's complement, the carry into the top bit differs from the carry out of it [6, p. J-8]. Processors report such events in flag bits, for example a C bit for the carry and a V bit for overflow [6, p. J-11, Fig. J.5]. When subtracting this way, a carry of 1 simply means that no borrow was needed.

The ALU

An arithmetic logic unit, ALU for short, is the part of a processor that calculates, and it combines everything above. Patterson and Hennessy build one step by step in their appendix “The Basics of Logic Design” [7], and the ALU here follows that design. Every bit gets a slice with an AND gate, an OR gate and a full adder. A multiplexer, a selector switch made of gates, decides which of the three results goes out. Two more multiplexers can invert a and b on their way in. Eight slices side by side, connected through their carries, make an 8-bit ALU.

With only four control lines it performs six operations: AND, OR and addition directly; subtraction by inverting b and setting the carry in; NOR and NAND by inverting both inputs, which is De Morgan's laws at work. Four flags describe the result: Zero, Negative, Carry and Overflow. Pick an operation, open the control lines, and solve the challenges.

Where to go from here

An ALU alone is not yet a processor. Registers hold the operands, a control unit decides which operation runs, and memory holds the program. How all of this is designed and measured, from caches to pipelines, is the subject of Hennessy and Patterson's Computer Architecture: A Quantitative Approach [5]. Goldberg's appendix in that book continues with multiplication, division and floating point [6]. And the appendix “The Basics of Logic Design” in Patterson and Hennessy's Computer Organization and Design covers the material of this article in depth, from gates to the ALU [7].

References

1. G. Boole, An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. London: Walton and Maberly, 1854. Online at Project Gutenberg
2. A. De Morgan, Formal Logic: or, The Calculus of Inference, Necessary and Probable. London: Taylor and Walton, 1847. Online at the Internet Archive
3. C. E. Shannon, “A Symbolic Analysis of Relay and Switching Circuits,” Transactions of the American Institute of Electrical Engineers, vol. 57, no. 12, pp. 713–723, 1938. doi:10.1109/T-AIEE.1938.5057767
4. H. M. Sheffer, “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants,” Transactions of the American Mathematical Society, vol. 14, no. 4, pp. 481–488, 1913. doi:10.1090/S0002-9947-1913-1500960-1
5. J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann (Elsevier), 2017. ISBN 978-0-12-811905-1. Publisher's page
6. D. Goldberg, “Appendix J: Computer Arithmetic,” online appendix in J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann (Elsevier), 2017. Used here: sections J.2 “Basic Techniques of Integer Arithmetic” (from p. J-2) and J.8 “Speeding Up Integer Addition” (from p. J-37). Publisher's companion site
7. D. A. Patterson and J. L. Hennessy, Computer Organization and Design RISC-V Edition: The Hardware/Software Interface, 2nd ed. Morgan Kaufmann (Elsevier), 2020. ISBN 978-0-12-820331-6. Appendix A: “The Basics of Logic Design.” Publisher's page