Arithmetic Logic Unit Design

An arithmetic logic unit, or ALU (sometimes pronounced "Al Loo"), is a combinational network that implements a function of its inputs based on either logic or arithmetic operations. ALUs are at the heart of all computers as well as most digital hardware systems. In this section, we learn how to design these very important digital subsystems.

5.3.1 A Sample ALU

An n-bit ALU typically has two input words, denoted by A = An - 1, , A0 and B = Bn - 1, , B0. The output word is denoted by F = Fn, Fn - 1, , F0, where the high-order output bit, Fn, is actually the carry-out. In addition, there is a carry-in input C0.

Besides data inputs and outputs, an ALU must have control inputs to specify the operations to be performed. One input is M, a mode selector. When M = 0, the operation is a logic function; when M = 1, an arithmetic operation is indicated. In addition, there are operation selection inputs, Si, which determine the particular logic or arithmetic function to be performed.
To make the discussion more concrete, Figure 5.18 contains the specification of a simple ALU bit slice, that is, the behavior of a single bit of the ALU. The list of operations is partitioned into three sections: logic operations, arithmetic operations where the carry-in is 0, and arithmetic operations where the carry-in is 1. Some of the operations do not appear to be useful, such as the sum of B and the ones complement of A. However, if we set carry-in to 1, we obtain a very useful operation indeed: B minus A (B plus the twos complement of A).

Implementation of an ALU ALUs are relatively simple to implement: design a 1-bit slice and cascade as many of these as you need to build a multibit structure. Of course, the limiting performance factor will be the propagation of carries among the ALU stages.

Using the specification of Figure 5.18, a single bit slice has six inputs, Ai, Bi, Ci, M, S1, and S0, and two outputs, Fi and Ci + 1. This may appear daunting, but the truth table shows a relatively simple structure with many don't cares (see Figure 5.19).

We can use espresso to find an optimized two-level implementation. Figure 5.20 shows the reduced truth table it produces. This result is still complicated. The Fi output requires 18 product terms. A PLA-based design is feasible, but a design based on discrete gates is probably too complex even to consider.

MisII does a bit better. MisII's output on the espresso truth table is shown in Figure 5.21.

The circuit it derives appears in Figure 5.22. It requires 12 gates plus 5 inverters, which are not shown in the -schematic.

The schematic in Figure 5.23 offers an alternative multilevel implementation for the ALU. We obtained it by hand after a careful evaluation of how operations are encoded by the M and selection inputs. This implementation is based on the observation that when S1 is 0, Bi is blocked from affecting the outputs by gate A1. This happens whenever the operation deals only with Ai. The same is true for Ci when M is 0 (gate A2). These are exactly the nonarithmetic operations.

Addition is indicated whenever M = 1. In these cases, Bi (assuming S1 = 1) and Ci are passed to the inputs of the XOR gates X3 and X2. When S0 is 0, the topmost XOR gate, X1, simply passes Ai. When S0 is 1, it passes Ai's complement. Thus, the three cascaded XOR gates form a proper sum of Ai or its complement, Bi (or 0 if S1 = 0), and Ci whenever the ALU is in its arithmetic mode.

How about the carry output? When the ALU is in the arithmetic mode, the output of gate O1 is the function . The first product term is formed from gate A3, the second from A4. This is a valid form of the carry. If S1 = 0, we simply replace Bi by 0 in this expression to obtain the correct carry function.

When the ALU is in the logic mode, M = 0, we can concentrate on the cascaded XOR gates. When S0 and S1 are both 0, Ai is passed through to the output. If S0 is 1 while S1 is 0, the complement of Ai is passed. When S0 is 0 while S1 is 1, the inputs to X3 are Ai and Bi, and their XOR is computed. In the last case, S0 = 1, S1 = 1, the inputs to X3 are and Bi. This function is equivalent to the XNOR function. The circuit does the right thing!

A careful hand design can sometimes do better than a sophisticated CAD tool. MisII did not come up with this schematic, in part because of its inability to exploit don't-care conditions or to use XOR functions effectively.

5.3.2 TTL ALU Components

The most widely used ALU in TTL designs is the 74181. Its schematic shape is shown in Figure 5.24.
The '181 has two groups of 4-bit data inputs, a carry-in (Cn), a single 4-bit data output, and a carry-out (Cn + 4). Many of the inputs and outputs are active low.

The component also has four function select bits, S3, S2, S1, S0, and a mode bit M. This allows the ALU to compute 32 different functions of its inputs. The component can also be used as a comparator, and it has an open-collector A = B output for easy cascading across multiple stages.
Figure 5.25 shows the function table for the device, assuming negative logic data inputs and outputs. The ALU implements the logic functions NAND, NOR, AND, OR, XOR, and XNOR, as well as arithmetic plus and minus. The chip contains internal logic that implements a 4-bit carry look-ahead. It outputs group generate and propagate signals, making it possible to cascade ALU stages and carry look-ahead units to construct arithmetic units of larger bit widths.

Quite a few of the functions implemented by the 74181 are unlikely to be used in practice. After all, what does AB plus A implement? These are in the function table because they fall out of the internal implementation of the more interesting functions of the ALU.

The 74181 can also be used with positive logic inputs and outputs. The function table is the same, but the carry-in and out are complemented to maintain the proper sense of the function. In other words, to select the first column of arithmetic functions in positive logic, the carry-in, , must be set to 1. Similarly, the second column of arithmetic functions is selected when is set to 0.

Figure 5.26 shows how to use a carry look-ahead unit in conjunction with the 74181 to construct a 16-bit ALU. The figure assumes that the ALUs and the carry look-ahead unit are being used in negative logic mode (CN, CN + 1 are active high, G and P are active low). As long as the sense of the carries is maintained, this interconnection scheme works whether the ALU is being used in negative or positive logic modes.