`(`

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.Besides data inputs and outputs, an ALU must have control inputs to specify the operations to be performed. One input is

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, *A*i, *B*i, *C*i, *M*, *S*1,
and *S*0, and two outputs, *F*i and *C*i + 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 *F*i 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 *S*1
is 0, *B*i is blocked from affecting the outputs by gate *A*1.
This happens whenever the operation deals only with *A*i. The same
is true for *C*i when *M* is 0 `(`

gate *A*2`)`

.
These are exactly the nonarithmetic operations.

Addition is indicated whenever *M* = 1. In these
cases, *B*i `(`

assuming *S*1 = 1`)`

and *C*i are passed to the inputs of the XOR gates X3 and X2. When
*S*0 is 0, the topmost XOR gate, X1, simply passes *A*i. When
*S*0 is 1, it passes *A*i's complement. Thus, the three cascaded
XOR gates form a proper sum of *A*i or its complement, *B*i
`(`

or 0 if *S*1 = 0`)`

, and *C*i 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 *S*1 = 0, we simply replace *B*i 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 *S*0 and *S*1
are both 0, *A*i is passed through to the output. If *S*0
is 1 while *S*1 is 0, the complement of *A*i is passed. When
*S*0 is 0 while *S*1 is 1, the inputs to X3 are *A*i
and *B*i, and their XOR is computed. In the last case, *S*0
= 1, *S*1 = 1, the inputs to X3 are and *B*i.
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.

The '181 has two groups of 4-bit data inputs, a carry-in `(`

*C*n`)`

,
a single 4-bit data output, and a carry-out `(`

*C*n +
4`)`

. Many of the inputs and outputs are active low.

The component also has four function select bits, *S*3,
*S*2, *S*1, *S*0, 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 `(`

*C*N, *C*N + 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.

[Top] [Next]
[Prev]

randy@cs.Berkeley.edu;