ALU adder

An arithmetic and logical unit (ALU) adder provides the basic functionality of arithmetic operations within a computer, and is a significant component of the arithmetic and logical unit. Adders are composed of half adders and full adders, which add two-bit binary pairs, and ripple carry adders and carry look ahead adders which do addition operations to a series of binary numbers.

Half adder

A half adder is a logical circuit that performs an addition operation on two binary digits. The half adder produces a sum and a carry value which are both binary digits.

S = A xor B
C = A and B

Following is the logic table for a half adder:

Full adder

A full adder is a logical circuit that performs an addition operation on three binary digits. The full adder produces a sum and carry value, which are both binary digits.

S = (A xor B) xor Ci
Co = (A and B) or (Ci and (A xor B))

Ripple carry adder

It is possible to create a logical circuit using several full adders to add multiple-bit numbers. Each full adder inputs a Cin, which is the Cot of the previous adder. This kind of adder is a ripple carry adder, since each carry bit "ripples" to the next full adder.

The layout of a ripple carry adder is simple, which allows for fast design time; however, the ripple carry adder is relatively slow, since each full adder must wait for the carry bit to be calculated from the previous full adder. The delay for this circuit is nC + S, where n is the number of full adders, C is the time required to calculate (delay) an individual carry value, and S is the delay of an individual sum value. For small adders, this delay is not very important, but for 32-bit or 64-bit computations, the delay can become significant. To solve this problem, scientists devised a faster way to add two binary numbers, called the carry look ahead adder.

Carry look ahead

Let's try a little experiment. I will give a series of numbers. See how long it takes you to find the most significant digit (the number to the far left).

  3456789876543
+ 6543210123456

The most significant digit is 9. How can we tell? We can look at the far left digits being added. 3+6 = 9. If we were to add 1 to this value, the most significant digit would be 1 (9+1 = 10). So, we have to look at the digit to the right of this one, to see if there is a carry. Do the same for the following problem:

  3456789876543
+ 6544210123456

You will notice there is 6+4, which will generate a carry. Since we know all the sums to the right of this value are 9, we know immediately that the most significant digit will be 1. Try this again for this last example:

  9999919999999
+ 0000090000000

As you can see, we can quickly determine the most significant digit by looking whether the two values sum to 9 (will propagate a carry), or sum greater than 9 (will generate a carry). This is the basic principle behind the Carry Look Ahead adder.

For each bit in a binary sequence to be added, the Carry Look Ahead Logic will determine whether that bit pair will generate a carry or propagate a carry. This allows the circuit to "pre-process" the two numbers being added to determine the carry ahead of time. Then, when the actual addition is performed, there is no delay from waiting for the ripple carry effect (or time it takes for the carry from the first Full Adder to be passed down to the last Full Adder). Below is a simple 4-bit generalized Carry Look Ahead circuit that combines with the 4-bit Ripple Carry Adder we used above with some slight adjustments:

For any circuit larger than 4 bits, the Carry Look Ahead circuity becomes very complicated. For the example provided, the logic for the generate (g) and propagate (p) values are given below. Note that the numeric value determines the signal from the circuit above, starting from 0 on the far left to 3 on the far right:

C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0
C4 = G3 + P3C3 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C0

To determine whether a bit pary will generate or propagate a carry, the following logic works:

G = A and B
P = A xor B

The Carry Look Ahead 4-bit adder can also be used in a higher-level circuit by having each CLA Logic circuit produce a propagate and generate signal to a higher-level CLA Logic circuit. This becomes very complicated, but the result of having less delay time is very beneficial.