1. Digital Logic
2. Topic: Adders

Adders

Arithmetic Circuits

11360

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.

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 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.

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.

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: KaTeX parse error: Expected 'EOF', got '¢' at position 27: …_i \cdot (A_i â̲Š• B_i) + A_…, 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:

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

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.

Example: Designing a 4-bit Binary Adder Structurally and Behaviorally

Implement the Adder Structurally

Full Adder (FA)

Create a Verilog module for a full adder.

module FA(
    input A,
    input B,
    input Cin,
    output S,
    output Cout
    );

assign S = A ^ B ^ Cin;
assign Cout = (A & B) | ((A ^ B) & Cin);

endmodule

Half Adder (HA)

Create another Verilog module for a half adder.

module HA(
    input A,
    input B,
    output S,
    output Cout
    );

assign S = A ^ B;
assign Cout = A & B;

endmodule

Implement 4-bit Adder using FA and HA

Create a Verilog module called adder to wrap three FAs with one HA to form a 4-bit adder based on figure 7 (PS! This example only uses 4 bits wherease the figure represents 8 bits). Check your wrapper code below after you’re done by clicking “Show Code”.

Show/Hide Code

module adder(
    input [3:0] A,
    input [3:0] B,
    output [3:0] S,
    output Cout
    );

wire [3:0] Carry;

HA add_0 (
    .A(A[0]),
    .B(B[0]),
    .S(S[0]),
    .Cout(Carry[0])
    );

FA add_1 (
    .A(A[1]),
    .B(B[1]),
    .Cin(Carry[0]),
    .S(S[1]),
    .Cout(Carry[1])
    );

FA add_2 (
    .A(A[2]),
    .B(B[2]),
    .Cin(Carry[1]),
    .S(S[2]),
    .Cout(Carry[2])
    );

FA add_3 (
    .A(A[3]),
    .B(B[3]),
    .Cin(Carry[2]),
    .S(S[3]),
    .Cout(Carry[3])
    );

assign Cout = Carry[3];

endmodule

Implement Adder Behaviorally

Verlilog allows you to use operator + in your code to instantiate an adder implicitly. However, the Verilog synthesizer will decide the circuit implementation of the adder. In some situation, you may allow the synthesizer to select the logic implementation of the adder, while in some other cases, you may want to implement the adder yourself and pick the right structure of the adder to be implemented.

Create your code and double check it below to make sure you got it right.

Show/Hide Code

module adder(
    input [3:0] A,
    input [3:0] B,
    output [3:0] S,
    output Cout
    );

wire [4:0] Result;
assign Result = A + B;

assign S = Result[3:0];
assign Cout = Result[4];

endmodule

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.