## Arithmetic Circuits

1968

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.

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.

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:

$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$
Table 1. Carry Look-Ahead Adder Boolean Algebra Based on Number of Bits

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

$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.
Table 2. Carry Look-Ahead Adder Boolean Algebra Based on Number of Bits Explanation

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

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


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

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

wire [3:0] Carry;

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

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

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

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

assign Cout = Carry[3];

endmodule


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.

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.