Adder

From CPUDev Wiki
Jump to: navigation, search

This page or section is a stub. You can help the wiki by accurately contributing to it.

At the heart of every ALU there is a circuit for adding integers, the adder. An N-bit adder contains (at least) N full adders.

TODO add schematics

Logic

Half Adder circuit
Half adder truth table
A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Full Adder circuit
Full adder truth table
A B C in Sum C 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
Full Adder icon

Subtraction

Subtracting B from A is essentially the same as adding A and -B, this way we can really easily re-use the adder hardware to subtract. Negative values are almost always represented in Two's Complement, as these can be normally added together. (In the addition of 5 and -9, -9 requires 5 bits to be expressed. If you leave out the 4th bit, it will be 7 instead of -9)

 0101   (5)            0101   (5)
 0111 - (7)            1001 + (-7)
——————                ——————
 1110   (-2)           1100   (-2)

As such, adding logic for subtracting is pretty easy. If we take the full adder (with inputs A, B, and Carry In) we just need to convert B to its two's complement form. This is done by negating B and adding one, the adding one can be accomplished by making Carry In high. All that's left is to negate B, but since we want to use the same adder hardware for addition, NOT gates aren't the best choice.

B B XOR 0 B XOR 1
0 0 1
1 1 0
4-bit Adder/Subtractor

If we take the table on the left, it is clearly visible that the XOR gate acts like a sort of toggled NOT gate, when one of its inputs is high the other is negated, if not the other passes through untouched.

Ripple Carry Adder

4-bit ripple carry adder

By placing N full adders next to each other with the carry out of the previous full adder connected to the carry in, we have created a ripple carry adder. This is the simplest N-bit adder, and also the slowest. In the worst case, when adding 1 to 0b111...111, the operation can only be finished when the carry has propagated from right to left. This propagation will take longer when N is increased.

Carry Select Adder

The Carry Select Adder can provide a smaller computation time by duplicating some of the hardware. By splitting the ripple carry adder into smaller ripple carry adders (for example, 4 8-bit adders), and duplicating all but the least significant byte we can let one half of every pair perform the addition with a low carry in, and the other half with a high carry in. Afterwards we can use the carry out of the non-duplicated adder to select the correct result for the second byte, the carry out of the second adder to select the third byte, etc. That way, we have a 32-bit adder with the computation time of an 8-bit adder.

Carry Look-ahead Adder

TODO

Hardware

Full adder CMOS circuit