Microprocessor Design

Back To Introduction

Back To Introduction

The diagrams below show a half adder and a full adder.

These adders add bit A to bit B, forming a

Carry In B A Sum Carry Out -------------------------------------- 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

Using subscripts, as in

The diagram above shows three full adders used to add two 3-bit words. Each adder receives a bit from the binary word A

Additional logic called

The carry input on the bottom right of the diagram will come from the carry-look-ahead logic. The sum, S, and two new outputs, P and G, are shown. The G signal is known as the

Here is a diagram of a 3-bit adder that is ready for connection to a care-look-ahead logic unit:

The figure above diagrams the carry-look-ahead logic. It consists of three parts. They produce C

Designing this carry-look-ahead logic and more complicated logic units by reference to truth tables alone (however well memorized) is a somewhat trail-and-error process that is tedious and prone to errors. Nothing should discourage you from becoming a virtuoso of this approach, but you should also be aware of an algebra of logic gates based on the work of George Boole. His creation is called

Boolean algebra operates on two values. They can stand for

Knowing the purpose and constraints associated with a desired logic-gate function, a workable arraignment can often be found by solving Boolean equations.

Early on, the symbols for AND and OR were defined this way: A AND B = A ∧ B, and A OR B = A ∨ B. Using these symbols, equations looked like this:

C

Motivated by greater clarity, other symbols have become popular. A AND B is often written A · B, or simply AB, indicating the multiplication of the inputs. So long as the input numbers are limited to 1 and 0, this ordinary multiplication gives the same result as an AND gate, even if that gate has more than two inputs. The result of using AB to mean A AND B seems clearer:

C

The

C

Using + in place of ∨ presents a problem. 1 + 1 is not 1. Using + requires taking care to recognize two meanings for the plus symbol because its meaning depends on the context. If you are sure that the equation is Boolean, you can get away with using the plus sign; but I prefer to avoid having two context-dependent meanings for + by consistently using ∨ for OR.

The preferred symbol for XOR is ⊕, so A XOR B = A ⊕ B. With the A ⊕ B, A ∨ B, and AB logical operations we have enough to describe the partial adder and the carry-look-ahead logic.

In the partial adder, we have three equations:

P = A ⊕ B

G = AB

S = P ⊕ C

In the full adder we also have an equation for the carry output:

C

In fact, this is the model for the first of three sections in the carry-look-ahead logic that produces C

C

The sections for C

C

= G

= G

C

= G

= G

= G

= G

We now have an equation for each of the three sections of the carry-look-ahead logic:

C

C

C

These equations can readily be translated into logic designs. Consider C

The propagation delay is much longer in the serial arrangement than in the four-input OR gate, but their truth tables are the same.

The C

The serial versions have the same truth tables as versions that use many inputs, and they have the same Boolean expressions. The serial versions have much longer propagation delays; but if the underlying technology is electronic, and they have more than just a few inputs, they have noticeably longer propagation delays. For this reason, a multilevel approach is used for 16-bit and 64-bit addition. It keeps the number of logic-gate inputs limited to four, and avoids the extra delays that would be caused by 17-input and 65-input electronic gates.

The 4-Bit adder diagramed above has a fourth partial adder and does not directly produce C

The Boolean expression for PG is P

The 4-bit adder diagramed above could be substituted for any of the four 4-bit adders used in the 16-bit adder shown below. In the 16-bit adder, C

PG

GG

C

= GG

= G

= G

= G

= G

= G

= G

= G

The pattern has been maintained while limiting the number gate inputs to four. The 16-bit adder has two levels, each with a carry-look-ahead unit.

The 64-bit adder below is a three-level unit.

The carry input C