Adders

Arithmetic Circuits

408

Ripple Carry Adder (RCA)

Adder circuits add two N-bit operands to produce an N-bit result and a carry out signal (the carry out is a ‘1’ only when the addition result requires more than N bits). The basic adding circuit is one of the cornerstones of digital system design, and it has been used in countless applications since the earliest days of digital engineering. The simplest adding circuit performs addition in much the same way that humans do, performing the operation right to left, bit-by-bit from the LSB to the MSB. Like any circuit that deals with signals grouped as binary numbers, the simplest adding circuit can most easily be designed using the bit-slice approach. By focusing on the requirements for adding a single pair of bits from two N-bit binary numbers, an otherwise complex design challenge can be divided into a more tractable problem. Once a circuit that can add any pair of bits has been designed, that circuit can be replicated N times to create an N-bit adder.

The logic graph below shows the eight different cases that may be encountered when adding two binary numbers. The highlighted bit pairs and the associated carries show that a bit-slice adder circuit must process three inputs (the two addend bits and a carry-in from the previous stage) and produce two outputs (the sum bit and a carry out bit). In the exercises and lab project, you are asked to create a truth table and circuit for various adding circuits.

Figure 1. Truth table for a bit-slice adder (full adder)

A block diagram for the bit-slice circuit is shown in Fig. 2 on the right, and it is called a Full Adder (FA). Full adders can be used to assemble circuits that can add any number of bits. The figure below shows an 8-bit adder circuit constructed from eight individual full-adder bit- slice circuits. Note that the input and output pin locations on the bit-slice block diagram have been re-arranged in the diagram to make the drawing more convenient.

The carry-out generated in the very first stage of an 8-bit adder must “ripple” through all seven higher-order stages before a valid 9-bit sum can be produced. It is this need to ripple carry information from one bit-slice to the next that gives the adder its name: the Ripple Carry Adder (RCA). This slice-by-slice processing of carry information severely limits the speed at which an RCA can run. Consider for example an 8-bit RCA adding A = ‘11111010’ and B = ‘10001110’, and then consider that the least-significant-bit (LSB) of the B operand switches from a ‘0’ to a ‘1’. In order for all nine bits of the adder to show the correct answer, carry information from the LSB must ripple through all eight full adders. If each full adder requires, say, 1 nanosecond (ns) to create the sum and carry-out bits after an input changes, then an 8-bit RCA will require up to 8 ns to create an accurate answer (8 ns is the worst-case situation, which occurs when an operand LSB change requires the S8 output bit to change). If an 8-bit addition in a computer circuit requires 8ns, then the computer’s maximum operating frequency would be the reciprocal of 8 ns, or 125 MHz. Most computers today are 32 bits—a 32-bit addition using an RCA would require 32 ns, limiting the computers operating frequency to no more than about 33 MHz. An RCA circuit is too slow for many applications—a faster adder circuit is needed.

Figure 3. Ripple carry adder block diagram.

Note the carry-in of the RCA LSB is connected directly to ground, because (by definition) the carry-in to the LSB of any adder must be logic 0. It is possible to capitalize on this observation, and create a smaller bit-slice circuit for use in the LSB position that does not have a carry-in input. Called a half-adder (HA), this reduced-function adder circuit is often used in the LSB position. Figure 4 shows the block diagram of a half adder.

Carry Look-ahead Adder (CLA)

The carry-look-ahead adder (CLA) overcomes the speed limitations of the RCA by using a different circuit to determine carry information. The CLA uses a simpler bit-slice module, and all carry-forming logic is placed in a separate circuit called the “Carry Propagate/Generate” (CPG) circuit. The CPG circuit receives carry-forming outputs from all bit-slices in parallel (i.e., at the same time), and forms all carry- in signals to all bit-slices at the same time. Since all carry signals for all bit positions are determined at the same time, addition results are generated much faster.

Since a CLA also deals with signals grouped as binary numbers, the bit slice approach is again indicated. Our goal is to re-examine binary number addition to identify how and where carry information is generated and propagated, and then to exploit that new knowledge in an improved circuit.

The figure below shows the same eight addition cases as were presented in the first figure. Note that in just two of the cases (3 and 7), a carry out is generated. Also note that in four cases, a carry that was previously generated will propagate through the current pair of bits, asserting a carry out even though the current bits by themselves would not have created a carry.

Figure 5. Truth table for carry generation.

Based on these observations, we can define two intermediate signals related to the carry out: carry generate (or G); and carry propagate (or P). G is asserted whenever a new carry is generated by the current set of inputs (i.e., when both operand inputs are a ‘1’), and P is asserted whenever a previously generated carry will be propagated through the current pair of bits (whenever either operand is a ‘1’). Based on this discussion, a truth table for the CLA bit-slice module can be completed (and you are asked to do so in the exercises).

The CLA bit-slice module generates the P and G outputs instead of a carry out bit. Note that a carry-out from the $i^{th}$ stage in an RCA, written as $C\_{i+1} = C\_i \cdot (A\_i ⊕ B\_i) + A\_i \cdot B\_i$ , can be written as $C\_{i+1} = C\_i \cdot P\_i + G\_i$ in the CLA. Since the carry-ins to each bit-slice in a CLA arise from the carry out (in terms of P and G) from the previous stage, the carry-ins to each stage can be written as:

Table 1. Carry Look-Ahead Adder Boolean Algebra Based on Number of Bits
$0^{th} Stage$	$C\_{in} = C\_0 ($ C_0$ is the carry-in)
$1^{st} Stage$ $i = 0$	$C\_1 = C\_0 \cdot P\_0 + G\_0$
$2^{nd} Stage$ $i = 1$	$C\_2 = C\_1 \cdot P\_1 + G\_1$ $=$ $(C\_0 \cdot P\_0 + G\_0) \cdot P\_1 + G\_1$ $=$ $C\_0 \cdot P\_0 \cdot P\_1 + G\_0 \cdot P\_1 + G\_1$
$3^{rd} Stage$ $i = 2$	$C\_3 = C\_2 \cdot P\_2 + G\_2$ $=$ $((C\_0 \cdot P\_0 + G\_0) \cdot P\_1 + G\_1) \cdot P\_2 + G\_2$ $=$ $C\_0 \cdot P\_0 \cdot P\_1 \cdot P\_2 + G\_0 \cdot P\_1 \cdot P\_2 + G\_1 \cdot P\_2 + G\_2$
$4^{th} Stage$ $i = 3$	etc. the equations can be expanded to any number of $i$

Restated in written form, carry-ins to the first few CLA bit-slices are formed as follows:

Table 2. Carry Look-Ahead Adder Boolean Algebra Based on Number of Bits Explanation
$0^{th} Stage$	$C\_{in}$ is simply connected to the overall, global carry in (called $C\_0$ ).
$1^{st} Stage$ $i = 0$	$C\_{in}$ is ‘1’ if a carry is generated in stage 0, or if a carry is propagated in stage 0 and $C\_0$ is ‘1’
$2^{nd} Stage$ $i = 1$	$C\_{in}$ is ‘1’ if a carry is generated in stage 1, or if a carry is propagated in stage 1 and generated in stage 0, or if a carry is propagated in stages 1 and 0 and $C\_0$ is a ‘1’
$3^{rd} Stage$ $i = 2$	$C\_{in}$ is ‘1’ if a carry is generated in stage 2, or if a carry is propagated in stage 2 and generated in stage 1, or if a carry is propagated in stages 2 and 1 and generated in stage 0, or if a carry is propagated in stages 2, 1, and 0 and $C\_0$ was a ‘1’
$4^{th} Stage$ $i = 3$	The pattern continues for any number of stages.

The carry-in logic equations for each stage are implemented in the CPG circuit block shown below. A complete CLA adder requires the CLA bit- slice modules and the CGP circuit. This complete CLA circuit involves a bit more design work than the RCA, but because the CGP circuit drives the carry-in of each CLA bit-slice module in parallel, it avoids the excessive delays associated with the RCA.

Figure 6. Block diagram of a carry look-ahead adder (CLA)

Important Ideas

The basic adding circuit is one of the cornerstones of digital system design, and it has been used in countless applications since the earliest days of digital engineering.
Full adders can be used to assemble circuits that can add any number of bits. The figure below shows an 8-bit adder circuit constructed from eight individual full-adder bit-slice circuits.
The carry-out generated in the very first stage of an 8-bit adder must “ripple” through all seven higher-order stages before a valid 9-bit sum can be produced. It is this need to ripple carry information from one bit-slice to the next that gives the adder its name—the Ripple Carry Adder.
It is possible to capitalize on this observation, and create a smaller bit-slice circuit for use in the LSB position that does not have a carry-in input. This function is called a half-adder.
The carry look ahead adder or CLA avoids the problems of the RCA by creating a second circuit for the carry out. The CLA uses a simpler bit-slice module, and all carry-forming logic is placed in a separate circuit called the Carry Propagate/Generate (CPG) circuit. The CPG circuit receives carry-forming outputs from all bit- slices in parallel (i.e., at the same time), and forms all carry-in signals to all bit- slices at the same time.