Computer Architecture And

Organization

Lec_4
Building an ALU (Part 2):
Dr. Abdallah Ramadan Fawzy
Overview

• Arithmetic Unit Design

• Primitive gates base implementation
• MUX-based implementation
• Logic Unit Design
• Arithmetic-logic Unit Design

Chapter-8
M. Morris Mano, Charles R. Kime and Tom Martin, Logic and Computer Design Fundamentals, Global (5th) Edition,
Pearson Education Limited, 2016. ISBN: 9781292096124
Remember:

3
 Arithmetic-logic units

• An arithmetic-logic unit, or ALU, performs many different

arithmetic and logic operations. The ALU is the “heart” of a
processor—you could say that everything else in the CPU is
there to support the ALU.
• Here’s the plan:
– We’ll show an arithmetic unit first, by building off ideas from the adder-
subtractor circuit.
– Then we’ll talk about logic operations a bit, and build a logic unit.
– Finally, we put these pieces together using multiplexers.
• We show the same examples as from the book.
 The four-bit adder

• The basic four-bit adder always computes S = A + B + CI.

• But by changing what goes into the adder inputs A, B and CI, we can
change the adder output S.
• This is also what we did to build the combined adder-subtractor
circuit.
 It’s the adder-subtractor again!

• Here the signal Sub and some XOR gates alter the adder inputs.
– When Sub = 0, the adder inputs A, B, CI are Y, X, 0, so the adder
produces G = X + Y + 0, or just X + Y.
– When Sub = 1, the adder inputs are Y’, X and 1, so the adder
output is G = X + Y’ + 1, or the two’s complement operation X - Y.
 The multi-talented adder

• So we have one adder performing two separate functions.

• “Sub” acts like a function select input which determines whether the
circuit performs addition or subtraction.
• Circuit-wise, all “Sub” does is modify the adder’s inputs A and CI.
 Modifying the adder inputs

• By following the same approach, we can use an adder to compute other

functions as well.
• We just have to figure out which functions we want, and then put the
right circuitry into the “Input Logic” box .
 Some more possible functions

• We already saw how to set adder inputs A, B and CI to compute either

X + Y or X - Y.
• How can we produce the increment function G = X + 1?

One way: Set A = 0000, B = X, and CI = 1

• How about decrement: G = X - 1?

A = 1111 (-1), B = X, CI = 0

• How about transfer: G = X?

(This can be useful.)

A = 0000, B = X, CI = 0

This is almost the same as the

increment function!
 The role of CI

• The transfer and increment operations have the same A and B inputs,
and differ only in the CI input.
• In general we can get additional functions (not all of them useful) by
using both CI = 0 and CI = 1.
• Another example:
– Two’s-complement subtraction is obtained by setting A = Y’, B =
X, and CI = 1, so G = X + Y’ + 1.
– If we keep A = Y’ and B = X, but set CI to 0, we get G = X + Y’.
This turns out to be a ones’ complement subtraction operation.
Table of arithmetic functions

• Here are some of the different possible arithmetic operations.

• We’ll need some way to specify which function we’re interested in, so
we’ve randomly assigned a selection code to each operation.
Mapping the table to an adder

• This second table shows what the adder’s inputs should be for each of
our eight desired arithmetic operations.

Selection code Desired arithmetic operation Required adder inputs

S2 S1 S0 G (A + B + CI) A B CI
0 0 0 X (transfer) 0000 X 0
0 0 1 X +1 (increment) 0000 X 1
0 1 0 X +Y (add) Y X 0
0 1 1 X+ Y+ 1 Y X 1

1 0 0 X + Y' (1C subtraction) Y' X 0

1 0 1 X + Y'+ 1 (2C subtraction) Y' X 1

1 1 0 X-1 (decrement) 1111 X 0

1 1 1 X (transfer) 1111 X 1

– Adder input CI is always the same as selection code bit S0.

– B is always set to X.
– A depends only on S2 and S1.
• These equations depend on both the desired operations and the
assignment of selection codes.
 Building the input logic
• All we need to do is compute the adder input A, given the arithmetic
unit input Y and the function select code S (actually just S2 and S1).
• Here is an abbreviated truth table:

inputs output
S2 S1 Yi Ai
0 0 0 0
0 0 1 0
S2 S1 A 0 1 0 0
0 0 0000 0 1 1 1
0 1 Y 1 0 0 1
1 0 Y' 1 0 1 0
1 1 0 1
1 1 1111
1 1 1 1

• We want to pick one of these four possible values for A, depending on

S2 and S1.
 Primitive gate-based input logic

• We could build this circuit using primitive gates.

• If we want to use K-maps for simplification, then we should first
expand out the abbreviated truth table.
– The Y that appears in the output column (A) is actually an input.
– We make that explicit in the table on the right.
• Remember A and Y are each 4 bits long!
inputs output
S2 S1 A S2 S1 Yi Ai
0 0 0000 0 0 0 0
0 1 Y 0 0 1 0
1 0 Y' 0 1 0 0
1 1 1111 0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
Primitive gate implementation

• From the truth table, we can

find an MSP:

S1
0 0 1 0
S2 1 0 1 1
Yi

Ai = S2Yi' + S1Yi

• Again, we have to repeat this

once for each bit Y3-Y0,
connecting to the adder inputs
A3-A0.

• This completes our arithmetic

unit.
 Multiplexer-based implementation
Alternative Implementation using 4 bit adder circuit and multiplexers

Selection code Desired arithmetic operation Required adder inputs

S2 S1 S0 G (A + B + CI) Y X CI

0 0 0 A (transfer) 0000 A 0

0 0 1 A+ 1 (increment) 0000 A 1

0 1 0 A+ B (add) B A 0

0 1 1 A+ B+ 1 B A 1

1 0 0 A + B' (1C subtraction) B' A 0

1 0 1 A + B' + 1 (2C subtraction) B' A 1

1 1 0 A- 1 (decrement) 1111 A 0

1 1 1 A (transfer) 1111 A 1
 Bitwise operations

• Most computers also support logical operations like AND, OR and

NOT, but extended to multi-bit words instead of just single bits.
• To apply a logical operation to two words X and Y, apply the operation
on each pair of bits Xi and Yi:
1 01 1 1 01 1 1 01 1
AND 1 1 1 0 OR 1 1 1 0 XOR 1 1 1 0
1 01 0 1 1 1 1 01 01

• Single operand logical operation: “complementing” all the bits in a

number.
NOT 1 0 1 1
01 00
Bitwise operations in programming

• Languages like C, C++ and Java provide bitwise logical operations:

& (AND) | (OR) ^ (XOR) ~ (NOT)

• These operations treat each integer as a bunch of individual bits:

13 & 25 = 9 because 01101 & 11001 = 01001

• They are not the same as the operators &&, || and !, which treat each
integer as a single logical value (0 is false, everything else is true):

13 && 25 = 1 because true && true = true

• Bitwise operators are often used in programs to set a bunch of Boolean

options, or flags, with one argument.
• Easy to represent sets of fixed universe size with bits:
– 1: is member, 0 not a member. Unions: OR, Intersections:AND
 Defining a logic unit

• A logic unit supports different logical functions on two

multi-bit inputs X and Y, producing an output G.
• This abbreviated table shows four possible functions and
assigns a selection code S to each.

S1 Output
S
0
0 0 Gi = XiYi
0 1 Gi = Xi + Yi
1 0 Gi = Xi  Yi
1 1 Gi = Xi'

• We’ll just use multiplexers and some

primitive gates to implement this.
• Again, we need one multiplexer for each
bit of X and Y.
 Our simple logic unit

• Inputs:
– X (4 bits)
– Y (4 bits)
– S (2 bits)
• Outputs:
– G (4 bits)
 Combining the arithmetic and logic units

• Now we have two pieces of the puzzle:

– An arithmetic unit that can compute eight functions on 4-bit inputs.
– A logic unit that can perform four functions on 4-bit inputs.

• We can combine these together into a single circuit, an arithmetic-logic unit (ALU).
 Our ALU function table

S3 S2 S1 S0 Operation

0 0 0 0 G =X
• This table shows a sample 0 0 0 1 G = X +1
function table for anALU.
0 0 1 0 G=X+Y
• All of the arithmetic operations
have S3=0, and all of the logical 0 0 1 1 G=X+Y+1
operations have S3=1.
0 1 0 0 G = X + Y'
• These are the same functions we
saw when we built our arithmetic 0 1 0 1 G = X + Y' + 1
and logic units a few minutes ago. 0 1 1 0 G=X-1
• Since our ALU only has 4 logical
0 1 1 1 G =X
operations, we don’t need S2.
The operation done by the logic 1 x 0 0 G = X andY
unit depends only on S1 and S0.
1 x 0 1 G = X or Y

1 x 1 0 G=XY

1 x 1 1 G = X'
 A complete ALU circuit
The / and 4 on a line indicate that it's actually four lines.

4 Cout should be ignored

when logic operations are
4 performed (when S3=1).

4 4

G is the final ALU output.

• When S3 = 0, the final
The arithmetic and logic units share the select inputs S1 output comes from the
and S0, but only the arithmetic unit uses S2. arithmetic unit.
• When S3 = 1, the
output comes from the
logic unit.
 Comments on the multiplexer

• Both the arithmetic unit and the logic unit are “active” and produce
outputs.
– The mux determines whether the final result comes from the
arithmetic or logic unit.
– The output of the other one is effectively ignored.
• Our hardware scheme may seem like wasted effort, but it’s not
really.
– “Deactivating” one or the other wouldn’t save that much time.
– We have to build hardware for both units anyway, so we might as
well run them together.
• This is a very common use of multiplexers in logic design.
 The completed ALU

• This ALU is a good example of hierarchical

design.
– With the 12 inputs, the truth table would
have had 212 = 4096 lines. That’s an awful 4

lot of paper. 4
– Instead, we were able to use components 4
that we’ve seen before to construct the 4
entire circuit from a couple of easy-to-
understand components.
• As always, we encapsulate the complete
circuit in a “black box” so we can reuse it in
fancier circuits.