Chapter 9. Circuits: Components

Having learned about the fundamental theory of logic circuits, we are now ready to build useful circuits. We start with two categories of circuits. The first group of circuits allow us to add values together. The second group allows us to route values, providing something analogous to a conditional statement in a general-purpose programming language.

9.1. Adding

To work toward our adding circuit, we first think about how we would do this on paper. Of course, we already understand how to do this for base-10 numbers. The computer will add binary numbers, but we can still use a similar approach. Suppose, for example, that we want to add 253₍₁₀₎ = 11111101₍₂₎ and 5₍₁₀₎ = 101₍₂₎.

The result here is 100000010₍₂₎ = 258₍₁₀₎.

The addition technique is fine on paper, but the computer doesn't have the luxury of a pencil and paper to perform computation like this. We need a circuit. We'll break the design process into two smaller pieces. The first, called a half adder, is for the rightmost column. (The box is intentionally drawn empty; we'll see what circuit it represents soon.)

It takes two inputs, representing the two bits in the rightmost column of our addition, and it has two outputs, representing the bit to place in the sum's rightmost column (sum) and the bit to carry to the next column (c_out).

For each of the other columns, we'll have three inputs: the carry from the previous column (c_in) and the two bits in the current column. We'll call the circuit to add these three bits together a full adder.

The two outputs have the same meaning as with the half adder.

9.1.1. The half adder

To build the half adder, we consider the four possible combinations of bits for the two inputs. We can draw a truth table for this.

a b c_out sum

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

`a`	`b`	`c`_out	`sum`
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Notice that the c_out output is the AND function on a and b. The sum output is called the exclusive-or function (abbreviated XOR), so named because it is like an OR, but it excludes the possibility of both inputs being 1. We draw a XOR gate as an OR gate with a shield on its inputs. [Incidentally, the Boolean expression symbol used for XOR is most often a circled plus sign (⊕); thus, x ⊕ y represents x XOR y.]

To design a XOR gate using AND, OR, and NOT gates, we observe that the sum-of-products expression is a b + a b, from which we can construct a circuit.

With a XOR gate built, we can now put together our half adder.

9.1.2. The full adder

To design our full adder, we combine two half adders. The first half adder finds the sum of the first two input bits, and the second sums the first half adder's output with the third input bit.

Technically, you might say, we should use another half adder to add the carry bits from the two half adders together. But since the carry bits can't both be 1, an OR gate works just as well. (We prefer to use an OR gate because it is only one gate, and a half adder uses several; thus, the OR gate is cheaper.)

9.1.3. Putting it together

To build our complete circuit, we'll combine a half adder and several full adders, with the carry bits strung between them. For example, here is a four-bit adder.

This diagram supposes that the first input is of the form a₃a₂a₁a₀ — that is, we call the 1's bit of the four-bit number a₀, the 2's bit a₁, the 4's bit a₂, and the 8's bit a₃. (If we were dealing with two's-complement numbers, a₃ would represent the −8's bit, and the circuit would add properly.) Similarly, the second input is of the form b₃b₂b₁b₀. Numbering the bits this way — starting with 0 for the 1's bit — may seem confusing: This numbering system comes from the fact that 2⁰ = 1 and so a₀ is for the 1's bit, while a₁ is for the 2's bit since 2¹ = 2. Each bit a_k stands for the 2^k's bit. Designers conventionally use this system for numbering bits.

9.2. Routing circuits

Computers work largely by routing electricity between components. In this section, we'll examine two particularly important circuit components whose primary purpose is to facilitate routing.

9.2.1. Multiplexers

The multiplexer is a circuit that outputs a selection of one of several inputs. A multiplexer appears in a circuit as a trapezoid.

This multiplexer takes four inputs on the left side, called data inputs, and two inputs on the bottom, called select inputs; the single output is on the right side. The way it operates is to route one of the data inputs into an output; the select inputs determine which of the inputs goes to the right side. For example, if s₁ is 1 and s₀ is 0, then the d₁₀ input is routed to the output.

If s₁ is 0 and s₀ is 1, then the circuit's output would be d₀₁ instead.

This particular multiplexer is called a 2×4 multiplexer, so called because it takes two select inputs and four data inputs. Other possible multiplexers include the 1×2 multiplexer, a 3×8 multiplexer, and the 4×16 multiplexer. Often, you want each data input to in fact include several bits; if we had a 2×4 multiplexer in which each input is 5 bits, we would call it a 5-way 2×4 multiplexer.

Conceptually a multiplexer works by rotating a wire from one input to the output based on the selection bit, similar to a railroad switch. In reality, though, circuits don't have moving parts; we can work only with logic gates. Below is an implementation of a (1-way) 2×4 multiplexer.

9.2.2. Demultiplexers

The demultiplexer reverses the process of a multiplexer: It routes a single input into one of several outputs. The unselected outputs should emit a value of 0. It is drawn in a larger circuit as follows.

Internally, its circuit is similar to that of a multiplexer's; Below is an implementation diagram.