Digital Circuits/Adders
Half Adder
[edit  edit source]Consider adding two binary numbers together:
We see that the bit in the "two's" column is generated when the addition carried over. A halfadder is a circuit which adds two bits together and outputs the sum of those two bits. The halfadder has two outputs: sum and carry. Sum represents the remainder of the integer division A+B/2, while carry is the result. This can be expressed as follows:

Full Adder
[edit  edit source]Halfadders have a major limitation in that they cannot accept a carry bit from a previous stage, meaning that they cannot be chained together to add multibit numbers. However, the two output bits of a halfadder can also represent the result A+B=3 as sum and carry both being high.
As such, the fulladder can accept three bits as an input. Commonly, one bit is referred to as the carryin bit. Full adders can be cascaded to produce adders of any number of bits by daisychaining the carry of one output to the input of the next.

The fulladder is usually shown as a single unit. The sum output is usually on the bottom on the block, and the carryout output is on the left, so the devices can be chained together, most significant bit leftmost:
RippleCarry Adder
[edit  edit source]A ripple carry adder is simply several full adders connected in a series so that the carry must propagate through every full adder before the addition is complete. Ripple carry adders require the least amount of hardware of all adders, but they are the slowest.
The following diagram shows a fourbit adder, which adds the numbers A[3:0] and B[3:0], as well as a carry input, together to produce S[3:0] and the carry output.
Propagation Delay in Full Adders
[edit  edit source]Real logic gates do not react instantaneously to the inputs, and therefore digital circuits have a maximum speed. Usually, the delay through a digital circuit is measured in gatedelays, as this allows the delay of a design to be calculated for different devices. AND and OR gates have a nominal delay of 1 gatedelay, and XOR gates have a delay of 2, because they are really made up of a combination of ANDs and ORs.
A full adder block has the following worst case propagation delays:
 From A_{i} or B_{i} to C_{i+1}: 4 gatedelays (XOR → AND → OR)
 From A_{i} or B_{i} to S_{i}: 4 gatedelays (XOR → XOR)
 From C_{i} to C_{i+1}: 2 gatedelays (AND → OR)
 From C_{i} to S_{i}: 2 gatedelays (XOR)
Because the carryout of one stage is the next's input, the worst case propagation delay is then:
 4 gatedelays from generating the first carry signal (A_{0}/B_{0} → C_{1}).
 2 gatedelays per intermediate stage (C_{i} → C_{i+1}).
 2 gatedelays at the last stage to produce both the sum and carryout outputs (C_{n1} → C_{n} and S_{n1}).
So for an nbit adder, we have a total propagation delay, t_{p} of:
This is linear in n, and for a 32bit number, would take 66 cycles to complete the calculation. This is rather slow, and restricts the word length in our device somewhat. We would like to find ways to speed it up.
CarryLookahead Adder
[edit  edit source]A fast method of adding numbers is called carrylookahead . This method doesn't require the carry signal to propagate stage by stage, causing a bottleneck. Instead it uses additional logic to expedite the propagation and generation of carry information, allowing fast addition at the expense of more hardware.
In a ripple adder, each stage compares the carryin signal, C_{i}, with the inputs A_{i} and B_{i} and generates a carryout signal C_{i+1} accordingly. In a carrylookahead adder, we define two new functions.
The generate function, G_{i}, indicates whether that stage causes a carryout signal C_{i} to be generated if no carryin signal exists. This occurs if both the addends contain a 1 in that bit:
The propagate function, P_{i}, indicates whether a carryin to the stage is passed to the carryout for the stage. This occurs if either of the addends has a 1 in that bit:
Note that both these values can be calculated from the inputs in a constant time of a single gate delay. Now, the carryout from a stage occurs if that stage generates a carry (G_{i} = 1) or there is a carryin and the stage propagates the carry (P_{i}·C_{i} = 1):
The table below summaries this:
A_{i}  B_{i}  C_{i}  G_{i}  P_{i}  C_{i+1}  

0  0  0  0  0  0  
0  0  1  0  0  0  
0  1  0  0  1  0  
0  1  1  0  1  1  
1  0  0  0  1  0  
1  0  1  0  1  1  
1  1  0  1  1  1  
1  1  1  1  1  1 
We can extend the expression for the carryout by substituting the expression for the carryout of the previous stage:
Note that this does not require the carryout signals from the previous stages, so we don't have to wait for changes to ripple through the circuit. In fact, a given stage's carry signal can be computed once the propagate and generate signals are ready with only two more gate delays (one AND and one OR). Thus the carryout for a given stage can be calculated in constant time, and therefore so can the sum.
Operation  Required Data  Gate Delays 

Produce stage generate and propagate signals  Addends (a and b)  1 
Produce stage carryout signals, C_{1} to C_{n}  P and G signals, and C_{0}  2 
Produce sum result, S  Carry signals and addends  3 
Total  6 
The S, P, and G signals are all generated by a circuit called a "partial full adder" (PFA), which is similar to a full adder.
Note that while the P signal is generated as A OR B in the circuit diagram above, another valid choice would be A XOR B, the advantage being that A XOR B already appears in the circuit diagram and would not require an extra gate. This is because in the formula it doesnt matter which way is implemented, since and are equivalent expressions as the reader may verify using a truth table.
For a slightly smaller circuit, the propagate signal can be taken as the output of the first XOR gate instead of using a dedicated OR gate, because if both A and B are asserted, the generate signal will force a carry. However, this simplification means that the propagate signal will take two gate delays to produce, rather than just one.
A carry lookahead adder then contains n PFAs and the logic to produce carries from the stage propagate and generate signals:
Two numbers can therefore be added in constant time, O(1), of just 6 gate delays, regardless of the length, n of the numbers. However, this requires AND and OR gates with up to n inputs. If logic gates are available with a limited number of inputs, trees will need to be constructed to compute these, and the overall computation time is logarithmic, O(ln(n)), which is still much better than the linear time for ripple adders.
Cascading CarryLookahead Adders
[edit  edit source]A basic carrylookahead adder is very fast but has the disadvantage that it takes a very large amount of logic hardware to implement. In fact, the amount of hardware needed is approximately quadratic with n, and begins to get very complicated for n greater than 4.
Due to this, most CLAs are constructed out of "blocks" comprising 4bit CLAs, which are in turn cascaded to produce a larger CLA.
CarrySave Adder
[edit  edit source]A carrysave adder is a kind of adder with low propagation delay (critical path), but instead of adding two input numbers to a single sum output, it adds three input numbers to an output pair of numbers. When its two outputs are then summed by a traditional carrylookahead or ripplecarry adder, we get the sum of all three inputs.
When adding three or more numbers together, a sequence of carrysave adders terminated by a single carrylookahead adder provides much better propagation delays than a sequence of carrylookahead adders. In particular, the propagation delay of a carrysave adder is not affected by the width of the vectors being added.
Carrysave adders are really completely parallel arrays of full adder circuits, with the each bit of the three input vectors loaded into each full adder's A, B, and Cin inputs. Each full adder's output S is connected to the corresponding output bit of one output, and its output Cout is connected to the next higher output bit of the second output; the lowest bit of the second output is fed directly from the carrysave's Cin input.
This section of the Digital Circuits wikibook is a stub. You can help by expanding this section. If you add something, list yourself as a Contributor.