The Arithmetic Logic Unit and Code Converters

1 From the Adder to an Arithmetic Unit

Chapter 16 left us with a four-bit parallel adder that computes \(S = A + Y + C_{in}\) for two four-bit words \(A\) and \(Y\) and a carry into the least significant stage. It looks like a circuit that does one thing, but the useful observation is that \(Y\) and \(C_{in}\) are inputs like any others. If a small network sits in front of the adder and replaces \(B\) by something else before it arrives, the adder performs a different arithmetic operation without a single gate inside it being altered.

Four choices of \(Y\) are enough to be interesting, and all four are cheap: \(Y = 0000\), \(Y = B\), \(Y = B'\) (the bitwise complement) and \(Y = 1111\). Combined with the two values of \(C_{in}\) they give eight arithmetic functions:

The third and fourth rows deserve justification rather than assertion. Chapter 3 defined the two's complement of an \(n\)-bit word as \(2^n - B\), obtained by complementing every bit and adding one, so

The \(2^n\) is the carry out of the most significant stage and is discarded, leaving \(A - B\) in the four sum bits. With \(C_{in} = 0\) the same expression gives \(A - B - 1\), which is subtraction with a borrow already taken. For the last row, \(1111\) is the four-bit two's complement representation of \(-1\), so adding it decrements.

Reading the carry out takes a moment's care in the subtraction rows, because it is now a borrow indicator with inverted sense: \(C_{out} = 1\) means the \(2^n\) term appeared, which means no borrow was needed and \(A \ge B\). A student who reports a borrow whenever the carry output is high has the condition exactly backwards on half the class of problems.

Producing \(Y\) is a job for the multiplexer of Chapter 19. Four data inputs — the constant 0, the bit \(B_i\), the bit \(B_i'\) from an inverter, and the constant 1 — feed a 4-to-1 multiplexer per bit, all four multiplexers sharing the same two select lines \(S_1S_0\). The select word therefore names the arithmetic operation, and the whole arithmetic section is one adder, four multiplexers and four inverters.

2 The Logic Unit and the Function-Select Multiplexers

Arithmetic is only half of what an instruction set needs. The other half is bitwise logic — AND for masking, OR for setting bits, exclusive-OR for toggling and comparison, and complement — and these cannot be squeezed out of the adder, because the adder's whole purpose is to let information move between bit positions along the carry chain, whereas a logic operation must keep every bit position independent.

So the logic section is built separately and in the obvious way: for each bit, one AND gate, one OR gate, one XOR gate and one inverter, with their four outputs going to a 4-to-1 multiplexer driven by the same \(S_1S_0\) that steers the arithmetic section. A second, 2-to-1 multiplexer then chooses between the arithmetic result and the logic result under a mode input \(M\), and its output is the slice output \(F_i\).

The reason for a separate mode bit rather than simply widening \(S\) to three bits is worth stating, because it is the one place where the two halves interact. In logic mode the carry chain must be broken. If \(M = 1\) selected a logic function at the output multiplexer but left the adder running, the carry rippling along the slices would be meaningless — yet it would still be presented at \(C_{out}\), and any circuit downstream that tested it would be misled. Real ALUs use \(M\) to disable the internal carries as well as to steer the output multiplexer, which is exactly what the mode pin of the 74181 does.

Counting the hardware for a four-bit unit: one adder, twelve multiplexers and sixteen gates in the logic section — a great deal of logic to control with three pins, which is why the ALU was among the first functions offered as a single MSI package.

3 A Complete 4-Bit ALU and Its Function Table

Four of the slices of Figure 20.1 side by side, with the carry output of each driving the carry input of the next, make a four-bit ALU with twelve inputs — \(A_3\ldots A_0\), \(B_3\ldots B_0\), \(M\), \(S_1\), \(S_0\), \(C_{in}\) — and five outputs, \(F_3\ldots F_0\) and \(C_{out}\). Its complete behaviour is the twelve-row function table below.

Two notes follow from the table. Several operations appear twice — transfer \(A\) at both \(S_1S_0C_{in} = 000\) and \(111\) — which is the normal price of a simple operand-select network. And the ALU produces no flags of its own: zero is a four-input NOR across \(F\), negative is \(F_3\) read as a sign bit, and overflow is the exclusive-OR of the carries into and out of the most significant stage, exactly as Chapter 3 defined it.

4 Carry Propagation Between ALU Slices

The four slices of the last section are joined by a ripple carry, and Chapter 16 showed what that costs: the most significant sum bit cannot settle until a carry has walked the whole length of the adder. Inside a single package this is tolerable and is usually solved by carry-look-ahead within the four bits. Between packages it becomes the dominant delay, because a sixteen- or thirty-two-bit word needs four or eight ALU packages in a row.

Put numbers on it. Take a package that needs \(t_g = 15\) ns to produce a carry from its operands, \(t_c = 10\) ns to pass a carry from its input to its output, and \(t_F = 15\) ns from its carry input to a settled output word. Chained end to end, \(N\) packages settle after

which is 50 ns for a sixteen-bit machine (\(N = 4\)) but 170 ns for a sixty-four-bit one (\(N = 16\)), because the middle term grows with the word length while nothing else does. A single look-ahead generator serving four packages replaces that middle term by one fixed delay, giving \(15 + 10 + 15 = 40\) ns for sixteen bits, and two levels of generator give \(15 + 10 + 10 + 15 = 50\) ns for sixty-four bits, 3.4 times faster than the ripple.

That is why every serious ALU package brings out two extra pins. Instead of only a carry output, it produces a group propagate \(P\) and a group generate \(G\) for the four bits it contains:

\(P\) says that a carry entering the group will reappear at its output, and \(G\) says that the group makes a carry of its own regardless of what enters it. These are the same definitions Chapter 16 used for a single bit, applied to a block of four — the look-ahead idea being applied a second time, one level up.

The 74182 look-ahead carry generator takes four such \(P, G\) pairs and a carry-in and produces the three intermediate group carries in two gate delays, along with its own \(P\) and \(G\) so that a third level can be added for a sixty-four-bit machine. The principle scales logarithmically: each level of look-ahead multiplies the word length by four and adds only a constant delay.

One warning about the boundary between the halves of the ALU. When \(M\) selects logic mode, the carry chain is disabled, so \(P\), \(G\) and \(C_{out}\) carry no useful information. A cascade of ALU packages must therefore have every package in the same mode, and control logic that ignores the carry outputs whenever \(M = 1\).

5 The 74181 as a Case Study

The 74181, introduced in 1970, was the first ALU on a single chip and remained the standard teaching example long after it stopped being used in new designs. It is worth studying because it is exactly the structure of Figure 20.1, generalised until the function-select network can produce every useful transformation of \(B\) rather than just four.

The package is a 24-pin part with four-bit operands \(A\) and \(B\), a four-bit select \(S_3S_2S_1S_0\), a mode input \(M\), a carry input \(\overline{C_n}\), and outputs \(F_3\ldots F_0\), \(\overline{C_{n+4}}\), \(\overline{P}\), \(\overline{G}\) and an open-collector \(A = B\). Sixteen select codes and the mode bit give sixteen logic functions and sixteen arithmetic ones, each of the latter appearing twice over the carry input.

A few rows, in the active-HIGH operand convention, show the pattern:

Three features of the data sheet regularly confuse students. The first is the active-low convention: the carry pins and the \(P\) and \(G\) outputs are active-low, so \(\overline{C_n} = 0\) means a carry is being applied. The second is that the part has two function tables, one for active-HIGH operands and one for active-LOW, and they list different operations against the same select codes; if the arithmetic in a laboratory exercise comes out consistently wrong, the wrong table is the usual reason. The third is that \(A = B\) is open-collector, so it needs a pull-up resistor and can be wire-ANDed across several packages to compare words wider than four bits — the wired-AND connection of Chapter 13. That output is only meaningful when the part is set to subtract, because equality is detected as an all-ones result of \(A\) minus \(B\) minus 1.

Modern devices no longer look like this: a processor synthesised from the kind of hardware description Chapter 30 introduces has its adder architecture chosen by a tool, and its operation set decided by an instruction decoder rather than by four select pins. The organisation, though, is unchanged — transform an operand, add, select a result.

6 Binary-to-Gray and Gray-to-Binary Converters

Chapter 4 introduced the reflected binary or Gray code, in which successive values differ in exactly one bit, so that a shaft encoder read during a transition can never give a wildly wrong value. Any system using such an encoder needs a converter, and the design follows the procedure of Chapters 7 and 8 exactly — truth table, map, minimal expression — but produces an answer so much simpler than the truth table looks that it is worth doing carefully.

Treat the table as four separate four-variable functions of \(B_3B_2B_1B_0\). The first, \(G_3\), is 1 for exactly the eight rows with \(B_3 = 1\), so its map is two full columns and \(G_3 = B_3\) with no gate at all. For \(G_2\), read down the column: it is 1 for decimals 4 to 11, that is for \(B_3B_2 = 01\) and \(B_3B_2 = 10\), and 0 for \(B_3B_2 = 00\) and \(11\). The map has two groups of four cells and gives

The two product terms are the definition of the exclusive-OR, so the minimal sum of products is a single XOR gate rather than two ANDs and an OR. \(G_1\) and \(G_0\) come out the same way with the variables shifted along, giving \(G_1 = B_2 \oplus B_1\) and \(G_0 = B_1 \oplus B_0\).

The general rule is therefore \(G_{n-1} = B_{n-1}\) and \(G_i = B_{i+1} \oplus B_i\): the most significant bit is copied and every other Gray bit is the exclusive-OR of two neighbouring binary bits. An \(n\)-bit converter is \(n-1\) XOR gates, all working simultaneously, so the conversion takes one gate delay however wide the word.

Reversing the conversion is not symmetrical, and the reason is instructive. Rearranging \(G_i = B_{i+1} \oplus B_i\) with the XOR property \(X \oplus X = 0\) gives \(B_i = B_{i+1} \oplus G_i\), which expresses each binary bit in terms of the Gray bit at the same position and the binary bit above it — a bit that has itself still to be computed. The conversion is therefore recursive: \(B_3 = G_3\), then \(B_2 = B_3 \oplus G_2\), then \(B_1 = B_2 \oplus G_1\), then \(B_0 = B_1 \oplus G_0\).

Substituting each equation into the next removes the recursion: \(B_i = G_{n-1} \oplus \cdots \oplus G_i\), the parity of all the Gray bits from the most significant down to that position. Built as parity trees the converter is fast but larger; built as the cascade of Figure 20.2 it is only \(n-1\) XOR gates but \(n-1\) gate delays deep. This is the same chain-versus-tree trade that carry-look-ahead resolves in the adder.

7 BCD-to-Binary and Binary-to-BCD Conversion

Between binary and BCD there is no bitwise relationship to exploit, because ten is not a power of two. The two directions have to be treated as arithmetic rather than as coding, and they turn out to have quite different costs.

BCD to binary is the easy direction. A BCD number is a weighted sum, so a two-digit value \(D_1D_0\) is worth \(10D_1 + D_0\), and multiplying by ten in binary is free because \(10 = 8 + 2\):

A shift is a wiring pattern, not a circuit, so the whole converter is two binary adders. For three digits the hundreds contribute \(100D_2 = (D_2 \ll 6) + (D_2 \ll 5) + (D_2 \ll 2)\), since \(100 = 64 + 32 + 4\), and one more adder handles it.

Binary to BCD has no such shortcut, because dividing by ten is not a shift. The standard method is the shift-and-add-3 algorithm, also called double dabble. Set up a register holding the binary number at the right-hand end and one four-bit field per decimal digit to its left, all initially zero. Then repeat, once for every bit of the binary number: inspect each BCD field, and if it holds 5 or more add 3 to it; then shift the whole register left by one place, so that the top bit of the binary number moves into the units field.

The add-3 rule looks arbitrary until you see what the shift is doing. A left shift doubles the value held in the BCD fields. A decimal digit \(d\) that is 5 or more will double to 10 or more, which no longer fits in one digit and must produce a carry into the next. Adding 3 first gives \(2(d+3) = 2d + 6\), and since \(2d + 6 \ge 16\) whenever \(d \ge 5\), the sixteen is a 1 shifted into the next digit while \(2d + 6 - 16 = 2d - 10\) is left behind — which is precisely the correct units result after the decimal carry. Adding 3 before doubling is the same correction as adding 6 after it, and Chapter 3 met that +6 as the BCD addition correction.

The algorithm becomes a circuit in either of two ways. As a sequential machine it is a shift register, an add-3 corrector per digit and a controller that counts the shifts — a natural use for the registers of Chapter 25. As a combinational circuit the loop is unrolled: each add-3 test becomes a small four-in, four-out block, the shifts become wiring, and an eight-bit converter is a triangular array of such blocks. The combinational version is fast and needs no clock; the sequential version is far smaller. Unrolling an algorithm in space or iterating it in time is a recurring decision in digital design, and it returns in the multiplier of Chapter 17 and the successive-approximation converter of Chapter 29.

8 Summary and Key Results

9 Common Mistakes

10 Chapter Review