Arithmetic Circuits

Two 4-bit numbers are added with a 4-bit parallel (ripple-carry) adder: four full adders, one for each bit position, with the carry of each stage feeding the next. The first stage's carry-in is 0 (a half adder could be used there).

Let $A = A_3A_2A_1A_0 = 1011$ and $B = B_3B_2B_1B_0 = 1100$.

Block diagram

   A3 B3     A2 B2     A1 B1     A0 B0
   1  1      0  1      1  0      1  0
   |  |      |  |      |  |      |  |
  +-----+   +-----+   +-----+   +-----+
C4<| FA3 |<C3| FA2 |<C2| FA1 |<C1| FA0 |<-C0=0
  +-----+   +-----+   +-----+   +-----+
     |         |         |         |
     S3        S2        S1        S0

Each full adder computes

$$S_i = A_i \oplus B_i \oplus C_i, \qquad C_{i+1} = A_iB_i + C_i(A_i \oplus B_i)$$

Working, stage by stage

1. FA0 adds the LSBs 1 + 0 with $C_0 = 0$: sum 1, carry 0.
2. FA1 adds 1 + 0 + 0: sum 1, carry 0.
3. FA2 adds 0 + 1 + 0: sum 1, carry 0.
4. FA3 adds 1 + 1 + 0: sum 0, carry 1, which appears as $C_4$ (the fifth bit of the result).

Answer: $1011 + 1100 = 10111_2$ ($C_4 = 1$, $S_3S_2S_1S_0 = 0111$). Check: $11 + 12 = 23 = 10111_2$.

All bits are applied at the same time (parallel), but the final result is valid only after the carry has rippled through all four stages. IC 7483/74283 is a ready-made 4-bit parallel adder.

In signed 1's complement form a negative number is the 1's complement (all bits inverted) of its positive value; the MSB is the sign bit. An end-around carry, if produced, is added back to the LSB.

Step 1: Represent the numbers in 8 bits

$$\begin{aligned} +65 &= 0100\,0001 \\ -65 &= 1011\,1110 \quad (\text{1's complement}) \\ +15 &= 0000\,1111 \end{aligned}$$

Step 2: Add

   1011 1110   (-65)
 + 0000 1111   (+15)
 -----------
   1100 1101

There is no end-around carry out of the MSB, so the result is already in final form. The sign bit is 1, so the result is negative and is in 1's complement form.

Step 3: Find the magnitude

$$\overline{1100\,1101} = 0011\,0010 = 32 + 16 + 2 = 50$$

Answer: $(-65) + (+15) = 1100\,1101$ in 8-bit signed 1's complement, which is $-50$. Check: $-65 + 15 = -50$. No overflow, because the operands have opposite signs.

A 4-bit parallel adder adds two 4-bit binary numbers $A = A_3A_2A_1A_0$ and $B = B_3B_2B_1B_0$ at the same time. It uses four full adders connected in cascade: the carry-out of each full adder is the carry-in of the next higher stage. It is also called a ripple-carry adder (IC 7483 / 74283).

Diagram

  A3 B3      A2 B2      A1 B1      A0 B0
   | |        | |        | |        | |
 +-----+    +-----+    +-----+    +-----+
 | FA3 |<C3-| FA2 |<C2-| FA1 |<C1-| FA0 |<- C0
 +-----+    +-----+    +-----+    +-----+
  |   |        |          |          |
 C4   S3       S2         S1         S0

Each full adder gives

$$S_i = A_i \oplus B_i \oplus C_i, \qquad C_{i+1} = A_iB_i + B_iC_i + A_iC_i$$

Operation

1. All bits of A and B are applied to the full adders at the same time; $C_0$ is normally 0.
2. FA0 adds $A_0$, $B_0$, $C_0$ and gives $S_0$ and $C_1$.
3. $C_1$ goes to FA1, which then gives $S_1$ and $C_2$, and so on.
4. FA3 gives $S_3$ and the final carry $C_4$, which is the fifth bit of the sum.
5. The output $C_4S_3S_2S_1S_0$ is valid only after the carry has passed through all stages.

Example: $A = 0110\ (6)$, $B = 0111\ (7)$:

Result $C_4S_3S_2S_1S_0 = 01101 = 13$.

Cascading two 4-bit adders

Two such 4-bit adders give an 8-bit adder: $C_4$ of the lower adder (bits 0–3) is connected to $C_0$ of the upper adder (bits 4–7).

Limitation: carry propagation delay. In the worst case the carry passes through every stage, so delay $\approx n \times t_{carry}$. A carry look-ahead adder removes this.

To find $A - B$ by 2's complement: add the 2's complement of $B$ to $A$. If an end carry occurs, drop it and the result is positive. If no end carry occurs, the result is negative: take the 2's complement of the sum and put a minus sign.

Make both numbers the same length: $A = 10.001$, $B = 11.101$.

Step 1: 2's complement of B

$$\begin{aligned} \text{1's complement of } 11.101 &= 00.010 \\ \text{add 1 at LSB} &= 00.010 + 00.001 = 00.011 \end{aligned}$$

Step 2: Add to A

   10.001
 + 00.011
 --------
   10.100    (no end carry)

Step 3: No end carry, so the answer is negative. Take the 2's complement of 10.100:

$$\begin{aligned} \text{1's complement} &= 01.011 \\ +\,0.001 &= 01.100 \end{aligned}$$

Answer: $(10.001)_2 - (11.101)_2 = -(1.1)_2$

Check in decimal: $2.125 - 3.625 = -1.5 = -(1.1)_2$.

FFH AND C0H

AND each bit pair:

 FFH = 1111 1111
 C0H = 1100 0000
 AND = 1100 0000

Answer: $FF_H \cdot C0_H = C0_H$. (ANDing with $FF_H$ leaves the other number unchanged.)

(16)₁₀ − (26)₁₀ by 2's complement (8-bit)

$$\begin{aligned} 16 &= 0001\,0000 \\ 26 &= 0001\,1010 \\ \text{2's complement of } 26 &= 1110\,0101 + 1 = 1110\,0110 \end{aligned}$$

   0001 0000   (+16)
 + 1110 0110   (-26)
 -----------
   1111 0110   (no end carry)

No end carry, so the result is negative. Its magnitude is the 2's complement of the sum:

$$\overline{1111\,0110} + 1 = 0000\,1001 + 1 = 0000\,1010 = 10$$

Answer: $16 - 26 = 1111\,0110$ (2's complement form) $= -10$.

A binary multiplier multiplies two numbers by forming partial products with AND gates and adding them with binary parallel adders (BPA), in the same way as long multiplication by hand.

Let $A = A_3A_2A_1A_0$ (multiplicand) and $B = B_3B_2B_1B_0$ (multiplier). The product has $4 + 4 = 8$ bits, $P_7 \dots P_0$.

Partial products

                    A3   A2   A1   A0
                  x B3   B2   B1   B0
 ------------------------------------
                  A3B0 A2B0 A1B0 A0B0
             A3B1 A2B1 A1B1 A0B1
        A3B2 A2B2 A1B2 A0B2
   A3B3 A2B3 A1B3 A0B3
 ------------------------------------
 P7  P6   P5   P4   P3   P2   P1   P0

Each partial-product bit $A_jB_i$ is one 2-input AND gate, so 16 AND gates are needed. Adding the four rows needs three 4-bit parallel adders.

Design

1. Row 0: $A_3B_0\,A_2B_0\,A_1B_0\,A_0B_0$. Its LSB $A_0B_0$ is directly $P_0$.
2. Adder 1: adds row 1 ($A_3B_1 \dots A_0B_1$) to the upper three bits of row 0 ($0, A_3B_0, A_2B_0, A_1B_0$). Its sum LSB is $P_1$; its carry and upper three sum bits go on.
3. Adder 2: adds row 2 ($A_3B_2 \dots A_0B_2$) to (carry of adder 1, upper three sum bits of adder 1). Its sum LSB is $P_2$.
4. Adder 3: adds row 3 ($A_3B_3 \dots A_0B_3$) to (carry of adder 2, upper three sum bits of adder 2). Its four sum bits give $P_6P_5P_4P_3$ and its carry gives $P_7$.

 A x B0 (4 AND) -> [b3 b2 b1 | b0=P0]
                     |
 A x B1 (4 AND) -> [ 4-bit BPA #1 ] -> s0 = P1
                     | carry + s3 s2 s1
 A x B2 (4 AND) -> [ 4-bit BPA #2 ] -> s0 = P2
                     | carry + s3 s2 s1
 A x B3 (4 AND) -> [ 4-bit BPA #3 ] -> s0 = P3
                     |
               Cout=P7, s3 s2 s1 = P6 P5 P4

Each adder's carry-in $C_0 = 0$.

Example: $1101 \times 1011$ (13 × 11)

Product $= 1000\,1111_2 = 143$, and $13 \times 11 = 143$.

Hardware: 16 AND gates and three 4-bit parallel adders (e.g. three IC 7483). In general an $n \times m$-bit multiplier needs $n \cdot m$ AND gates and $(m-1)$ $n$-bit adders.

An n-bit full adder (n-bit parallel adder) adds two n-bit binary numbers $A = A_{n-1}\dots A_1A_0$ and $B = B_{n-1}\dots B_1B_0$ plus an input carry $C_0$. It is made by cascading $n$ one-bit full adders: the carry output of each stage is connected to the carry input of the next higher stage.

Block diagram

 A(n-1)B(n-1)     A2 B2      A1 B1      A0 B0
    |  |          |  |       |  |       |  |
 +--------+    +------+   +------+   +------+
 | FA n-1 |<...| FA2  |<--| FA1  |<--| FA0  |<-C0
 +--------+ C3 +------+ C2+------+ C1+------+
   |    |         |          |          |
  Cn   S(n-1)     S2         S1         S0

One stage (full adder)

$$S_i = A_i \oplus B_i \oplus C_i$$ $$C_{i+1} = A_iB_i + C_i(A_i \oplus B_i)$$

Operation

1. All $2n$ input bits are applied at the same time (parallel inputs). $C_0$ is 0 for plain addition (it is set to 1 for 2's complement subtraction).
2. FA0 adds $A_0$, $B_0$, $C_0$ and gives $S_0$ and $C_1$.
3. $C_1$ enters FA1, which produces $S_1$ and $C_2$; the carry ripples stage by stage to the left.
4. The last stage gives $S_{n-1}$ and the final carry $C_n$. The result is the $(n+1)$-bit number $C_nS_{n-1}\dots S_0$.

Example (n = 4): $A = 1001\ (9)$, $B = 0111\ (7)$, $C_0 = 0$:

Result $= 1\,0000 = 16$.

Timing and expansion

• Each stage must wait for the carry from the previous stage, so the worst-case delay is about $n \cdot t_c$ (where $t_c$ is the carry delay of one full adder). This carry propagation delay grows with $n$.
• Larger adders are built by cascading 4-bit adder ICs (7483/74283): $C_4$ of one IC goes to $C_0$ of the next.
• For high speed, the carry chain is replaced by a carry look-ahead generator, which forms all carries directly from $G_i = A_iB_i$ and $P_i = A_i \oplus B_i$.
• With XOR gates on the B inputs and $C_0 = 1$, the same circuit works as an n-bit subtractor (adder/subtractor).

A ripple carry adder (RCA) is a parallel adder made of full adders in cascade, where the carry out of each stage is the carry in of the next, so the carry "ripples" from LSB to MSB.

4-bit RCA (block diagram)

  A3 B3      A2 B2      A1 B1      A0 B0
   | |        | |        | |        | |
 +-----+    +-----+    +-----+    +-----+
 | FA3 |<C3-| FA2 |<C2-| FA1 |<C1-| FA0 |<- C0
 +-----+    +-----+    +-----+    +-----+
  |   |        |          |          |
 C4   S3       S2         S1         S0

$$S_i = A_i \oplus B_i \oplus C_i, \qquad C_{i+1} = A_iB_i + C_i(A_i \oplus B_i)$$

Problems with RCA

1. Carry propagation delay: stage $i$ cannot give a correct sum until $C_i$ arrives. In the worst case (e.g. $1111 + 0001$) the carry passes through all stages, so the total delay is about $n \times t_{carry}$. For a 32-bit adder this is very slow.
2. Delay grows linearly with word length, so the RCA limits the speed of the ALU and processor clock.
3. Glitches: outputs change several times while the carry ripples, giving temporary wrong values and extra power use.

Eliminating the problems: carry look-ahead adder (CLA)

The CLA generates every carry directly from the inputs, without waiting for the previous stage. Define for each bit

$$G_i = A_iB_i \ (\text{generate}), \qquad P_i = A_i \oplus B_i \ (\text{propagate})$$

Then $C_{i+1} = G_i + P_iC_i$. Expanding:

$$\begin{aligned} C_1 &= G_0 + P_0C_0 \\ C_2 &= G_1 + P_1G_0 + P_1P_0C_0 \\ C_3 &= G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0 \\ C_4 &= G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0 \end{aligned}$$ $$S_i = P_i \oplus C_i$$

 A,B -> [P,G gen] -> [Carry look-ahead] -> C1..C4
             |                               |
             +---------> [XOR: S = P xor C] <+

All carries are two-level AND-OR functions of $G$, $P$ and $C_0$, so every carry appears after a fixed delay (about 2 gate delays after $P$, $G$), independent of $n$. IC 74182 is a carry look-ahead generator. Other methods: carry-select and carry-skip adders, and grouping 4-bit CLA blocks with a second level of look-ahead for wide adders.

The circuit takes a 4-bit number $A_3A_2A_1A_0$ and gives $Y_3Y_2Y_1Y_0$ = its 2's complement ($\overline{A} + 1$, keeping 4 bits).

Truth table

Simplified expressions

From K-maps (or from the rule "copy bits up to and including the first 1 from the right, then invert the rest"):

• $Y_0 = 1$ for odd numbers only: $Y_0 = A_0$
• $Y_1 = 1$ for 01, 10 in $A_1A_0$: $Y_1 = A_1 \oplus A_0$
• $Y_2$ equals $A_2$ when $A_1A_0 = 00$, else $A_2'$: $Y_2 = A_2 \oplus (A_1 + A_0)$
• $Y_3$ equals $A_3$ when $A_2A_1A_0 = 000$, else $A_3'$: $Y_3 = A_3 \oplus (A_2 + A_1 + A_0)$

$$\begin{aligned} Y_0 &= A_0 \\ Y_1 &= A_1 \oplus A_0 \\ Y_2 &= A_2 \oplus (A_1 + A_0) \\ Y_3 &= A_3 \oplus (A_2 + A_1 + A_0) \end{aligned}$$

Circuit

A0 ------------------------------> Y0
A1, A0 ----------[XOR]-----------> Y1
A1, A0 --[OR]--> X1 = A1+A0
A2, X1 ----------[XOR]-----------> Y2
A2, X1 --[OR]--> X2 = A2+A1+A0
A3, X2 ----------[XOR]-----------> Y3

Gates: 3 XOR and 2 OR gates (the second OR adds $A_2$ to the first OR output).

Check: $A = 0110$: $Y_0 = 0$, $Y_1 = 1\oplus0 = 1$, $Y_2 = 1\oplus1 = 0$, $Y_3 = 0\oplus1 = 1$, so $Y = 1010$, and $16 - 6 = 10 = 1010$. Correct.

(Alternative: invert each bit with NOT gates and add 1 using a 4-bit parallel adder with $C_0 = 1$.)

Half adder and half subtractor in one circuit

Inputs $A$, $B$. Outputs: sum $S$, carry $C$, difference $D$, borrow $B_o$ ($A - B$).

$$S = D = A \oplus B, \qquad C = AB, \qquad B_o = A'B$$

The sum and difference are the same function, so one XOR gate serves both. Add one AND gate for $C$ and one NOT plus one AND gate for $B_o$.

A --+--------------[XOR]---+--> S (= D)
B --|--+-----------[   ]   |
    |  |
    +--|-----------[AND]------> C
    |  +-----------[   ]
    |  |
    +-[NOT]--A'----[AND]------> Bo
       +-----------[   ]

Total: 1 XOR, 2 AND, 1 NOT.

(If one output pair with a mode input $M$ is preferred: $S/D = A \oplus B$, $C/B_o = (A \oplus M)B$, giving carry when $M=0$ and borrow when $M=1$.)

a) (47)₁₀ − (26)₁₀ by 2's complement (8-bit)

$$\begin{aligned} 47 &= 0010\,1111 \\ 26 &= 0001\,1010 \\ \text{2's complement of } 26 &= 1110\,0101 + 1 = 1110\,0110 \end{aligned}$$

    0010 1111   (+47)
  + 1110 0110   (-26)
  -----------
  1 0001 0101

An end carry occurs: discard it. The result is positive.

Answer: $0001\,0101_2 = 16 + 4 + 1 = 21$. Check: $47 - 26 = 21$.

b) (10010)₂ − (10011)₂ by 1's complement

$$\text{1's complement of } 10011 = 01100$$

   10010
 + 01100
 -------
   11110   (no end-around carry)

No end carry, so the result is negative; take its 1's complement:

$$\overline{11110} = 00001$$

Answer: $(10010)_2 - (10011)_2 = -(00001)_2 = -1$. Check: $18 - 19 = -1$.

A full subtractor subtracts $B$ and a borrow-in $B_{in}$ from $A$, giving difference $D$ and borrow-out $B_o$. A half subtractor subtracts $Y$ from $X$: $D = X \oplus Y$, $B = X'Y$.

Truth table and expressions

$$D = A \oplus B \oplus B_{in}$$ $$\begin{aligned} B_o &= A'B'B_{in} + A'BB_{in}' + A'BB_{in} + ABB_{in} \\ &= A'B(B_{in}' + B_{in}) + B_{in}(A'B' + AB) \\ &= A'B + (A \oplus B)'\,B_{in} \end{aligned}$$

Using two half subtractors and one OR gate

• HS1 with inputs $A$, $B$: $D_1 = A \oplus B$, $B_1 = A'B$.
• HS2 with inputs $D_1$, $B_{in}$: $D = D_1 \oplus B_{in} = A \oplus B \oplus B_{in}$, $B_2 = D_1'B_{in} = (A \oplus B)'B_{in}$.
• OR gate: $B_o = B_1 + B_2 = A'B + (A \oplus B)'B_{in}$, which matches the expression above.

        +-----+  D1   +-----+
A ----->| HS1 |------>| HS2 |----------> D
B ----->|     |  Bin->|     |
        +-----+       +-----+
           | B1          | B2
           +---->[OR]<---+
                   |
                   +-----------------> Bo

Check: $A=0, B=1, B_{in}=1$: HS1 gives $D_1 = 1$, $B_1 = 1$; HS2 gives $D = 0$, $B_2 = 0$; $B_o = 1$. So $0 - 1 - 1 = -2$, i.e. $D = 0$ with borrow 1. Correct.

A 3-bit binary multiplier multiplies $A = A_2A_1A_0$ by $B = B_2B_1B_0$ to give a 6-bit product $P_5\dots P_0$. Partial products are made with AND gates and added with binary parallel adders (BPA).

Partial products

               A2    A1    A0
             x B2    B1    B0
 -----------------------------
               A2B0  A1B0  A0B0
         A2B1  A1B1  A0B1
   A2B2  A1B2  A0B2
 -----------------------------
 P5 P4   P3    P2    P1    P0

• $3 \times 3 = 9$ AND gates make the partial-product bits.
• Two 3-bit parallel adders add the three rows.

Design steps

1. $P_0 = A_0B_0$ directly.
2. Adder 1 (3-bit): adds row 1 ($A_2B_1, A_1B_1, A_0B_1$) to ($0, A_2B_0, A_1B_0$). LSB of its sum gives $P_1$.
3. Adder 2 (3-bit): adds row 2 ($A_2B_2, A_1B_2, A_0B_2$) to (carry of adder 1, upper two sum bits of adder 1). LSB gives $P_2$, the next two sum bits give $P_3P_4$, and its carry is $P_5$.

 A2B0 A1B0  A0B0 -----------------------> P0
  |    |
  0  A2B0 A1B0 + A2B1 A1B1 A0B1
       [ 3-bit BPA #1 ] --- S0 --------> P1
        C, S2, S1
           +   A2B2 A1B2 A0B2
       [ 3-bit BPA #2 ] --- S0 --------> P2
        C   S2   S1
        |    |    +--------------------> P3
        |    +-------------------------> P4
        +------------------------------> P5

Both adders have carry-in $= 0$.

Example: $101 \times 011$ (5 × 3)

Product $= 001111_2 = 15$, and $5 \times 3 = 15$.

Hardware needed: 9 AND gates and two 3-bit parallel adders (or two 4-bit adders such as IC 7483 with the top bit tied to 0).

2-bit binary fast adder

A fast adder (carry look-ahead adder) is a parallel adder in which all carries are produced directly from the input bits and the input carry, instead of waiting for the carry to ripple through each stage. This makes the addition time almost independent of the number of bits.

For each bit:

$$G_i = A_iB_i \ (\text{carry generate}), \qquad P_i = A_i \oplus B_i \ (\text{carry propagate})$$

Carries for 2 bits ($A_1A_0 + B_1B_0 + C_0$):

$$\begin{aligned} C_1 &= G_0 + P_0C_0 \\ C_2 &= G_1 + P_1C_1 = G_1 + P_1G_0 + P_1P_0C_0 \end{aligned}$$

Sums:

$$S_0 = P_0 \oplus C_0, \qquad S_1 = P_1 \oplus C_1$$

A0,B0 -[XOR]-P0   -[AND]-G0
A1,B1 -[XOR]-P1   -[AND]-G1

C1 = G0 + P0.C0           (1 AND, 1 OR)
C2 = G1 + P1.G0 + P1.P0.C0 (2 AND, 1 OR)

S0 = P0 xor C0 ; S1 = P1 xor C1  (2 XOR)
C2 is the output carry.

Since $C_2$ comes from a two-level AND–OR circuit, it is ready after the same delay as $C_1$.

Full subtractor using half subtractors

$$D = A \oplus B \oplus B_{in}, \qquad B_o = A'B + (A \oplus B)'B_{in}$$

• HS1 ($A$, $B$): $D_1 = A \oplus B$, $B_1 = A'B$
• HS2 ($D_1$, $B_{in}$): $D = D_1 \oplus B_{in}$, $B_2 = D_1'B_{in}$
• $B_o = B_1 + B_2$ (one OR gate)

A --->[ HS1 ]--D1-->[ HS2 ]----------> D
B --->[     ]  Bin->[     ]
         |B1           |B2
         +----->[OR]<--+
                  +------------------> Bo

A fast adder (carry look-ahead adder, CLA) is a parallel adder that produces the carries for all bit positions at the same time, directly from the inputs, instead of letting the carry ripple from stage to stage.

Principle

For bit $i$:

• Carry generate $G_i = A_iB_i$: a carry is produced regardless of $C_i$.
• Carry propagate $P_i = A_i \oplus B_i$: an incoming carry is passed on.

$$C_{i+1} = G_i + P_iC_i, \qquad S_i = P_i \oplus C_i$$

2-bit fast adder

$$\begin{aligned} C_1 &= G_0 + P_0C_0 \\ C_2 &= G_1 + P_1G_0 + P_1P_0C_0 \\ S_0 &= P_0 \oplus C_0 \\ S_1 &= P_1 \oplus C_1 \end{aligned}$$

Logic diagram

A0 B0 --+--[XOR]--> P0
        +--[AND]--> G0
A1 B1 --+--[XOR]--> P1
        +--[AND]--> G1

P0,C0 ----[AND]--+
G0 --------------+--[OR]--> C1

P1,G0 ----[AND]--+
P1,P0,C0 -[AND]--+--[OR]--> C2 (carry out)
G1 --------------+

P0,C0 --[XOR]--> S0
P1,C1 --[XOR]--> S1

Working: the P and G signals appear after one gate delay; $C_1$ and $C_2$ appear after two more gate delays (AND then OR); the sums after one more XOR delay. $C_2$ does not wait for $C_1$.

Example: $A = 11$, $B = 01$, $C_0 = 0$: $G_0 = 1, P_0 = 0, G_1 = 0, P_1 = 1$; $C_1 = 1$, $C_2 = 0 + 1\cdot1 + 0 = 1$; $S_0 = 0$, $S_1 = 1 \oplus 1 = 0$. Result $C_2S_1S_0 = 100 = 4$ (3 + 1). Correct.

Advantages of a fast adder

1. Much higher speed: carry delay is constant (about 3–4 gate delays), not $n$ times one stage delay as in a ripple adder.
2. Delay does not grow with word length within a block, so it suits fast ALUs.
3. Blocks can be cascaded with a second level of look-ahead (IC 74182) for wide adders.
4. Output settles quickly, with fewer glitches.

(Cost: more gates and gates with many inputs, so very wide single-level CLAs are impractical.)

A binary parallel adder is a combinational circuit that adds two n-bit binary numbers with all bits applied at the same time. It is made of $n$ full adders in cascade; the carry output of each full adder goes to the carry input of the next higher stage.

  A3 B3      A2 B2      A1 B1      A0 B0
 +-----+    +-----+    +-----+    +-----+
 | FA3 |<C3-| FA2 |<C2-| FA1 |<C1-| FA0 |<- C0
 +-----+    +-----+    +-----+    +-----+
  |   |        |          |          |
 C4   S3       S2         S1         S0

Each stage: $S_i = A_i \oplus B_i \oplus C_i$, $C_{i+1} = A_iB_i + C_i(A_i \oplus B_i)$.

Operation: FA0 adds the LSBs with $C_0$ (0 for plain addition); its carry goes to FA1, and so on. The result is $C_4S_3S_2S_1S_0$. Example: $0101 + 0011 = 01000$ (5 + 3 = 8).

Features and uses:

• IC 7483/74283 is a 4-bit binary parallel adder; ICs are cascaded ($C_4$ to next $C_0$) for 8, 12, 16 bits.
• With XOR gates on B and $C_0 = 1$ it becomes an adder/subtractor (2's complement).
• Used in multipliers, BCD adders and the ALU.

Limitation: carry propagation (ripple) delay; worst-case delay is $n \times$ one-stage carry delay. A carry look-ahead adder overcomes this.

A full adder adds three bits $A$, $B$, $C_{in}$ and gives sum $S$ and carry $C_{out}$. A half adder adds two bits: $S = X \oplus Y$, $C = XY$.

Full adder expressions

$$S = A \oplus B \oplus C_{in}$$ $$\begin{aligned} C_{out} &= A'BC_{in} + AB'C_{in} + ABC_{in}' + ABC_{in} \\ &= AB + C_{in}(A'B + AB') = AB + C_{in}(A \oplus B) \end{aligned}$$

Construction with two half adders and an OR gate

• HA1 ($A$, $B$): $S_1 = A \oplus B$, $C_1 = AB$
• HA2 ($S_1$, $C_{in}$): $S = S_1 \oplus C_{in} = A \oplus B \oplus C_{in}$, $C_2 = C_{in}(A \oplus B)$
• OR: $C_{out} = C_1 + C_2 = AB + C_{in}(A \oplus B)$

       +-----+  S1   +-----+
A ---->| HA1 |------>| HA2 |-----------> S
B ---->|     | Cin ->|     |
       +-----+       +-----+
          | C1          | C2
          +---->[OR]<---+
                  +--------------------> Cout

Check: $A=1, B=0, C_{in}=1$: $S_1 = 1, C_1 = 0$; $S = 0, C_2 = 1$; $C_{out} = 1$. So $1+0+1 = 10_2$. Correct.