CS61C

Adder/Subtractor

Learning Outcomes

Implement an n-bit adder as a cascade of 1-bit adders.
Recall that XOR is a conditional inverter and can be used with SUB to augment the adder block into an adder/subtractor block.

#fig-add-sub-block shows the add/subtract block used in our basic ALU:

Adder-subtractor block with 32-bit inputs A and B, control signal SUB, 32-bit output Y, and overflow flag.

This single circuit is capable of addition and subtraction:

two 32-bit wide data inputs A and B
a 1-bit wide control input SUB.
a 32-bit wide data output Y
a 1-bit wide output overflow.

When SUB=1, the circuit performs the subtraction A - B. When SUB=0 the circuit performs the addition A + B.

The “special” output, labeled overflow signals for integer overflow. Upon performing an addition or subtraction, this output will be a 1 if the result is too large to fit in 32 bits. We return to this fact later.

To design our adder/subtractor circuit, we will start out by studying the design of an adder circuit, then later augment it to also perform subtraction.

Cascading Intuition

One strawman¹ method for arriving at the detailed gate-level circuit for the adder would be to follow the procedure we learned in the previous chapter². Unfortunately, that technique is only effective for very narrow adders (e.g., 1-bit or 2-bit wide), because the size of the truth table is too large for wider adders.

Therefore, we turn to modular design: Find a way to break the design up into smaller more manageable pieces. We will design the smaller pieces individually, then wire them together to create the entire wide adder.

Consider adding two 4-bit numbers A= a{sub}3a{sub}2a{sub}1a{sub}0 and B= b{sub}3b{sub}2b{sub}1b{sub}0:

\begin{array}{c c c c c} & \texttt{c}_{\texttt{3}} & \texttt{c}_{\texttt{2}} & \texttt{c}_{\texttt{1}} & \\ & \texttt{a}_{\texttt{3}} & \texttt{a}_{\texttt{2}} & \texttt{a}_{\texttt{1}} & \texttt{a}_{\texttt{0}} \\ + & \texttt{b}_{\texttt{3}} & \texttt{b}_{\texttt{2}} & \texttt{b}_{\texttt{1}} & \texttt{b}_{\texttt{0}} \\ \hline & \texttt{y}_{\texttt{3}} & \texttt{y}_{\texttt{2}} & \texttt{y}_{\texttt{1}} & \texttt{y}_{\texttt{0}} \end{array}

Example, where A is 1011 and B is 0001:

\begin{array}{c c c c c} & \texttt{0} & \texttt{1} & \texttt{1} & \\ & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} \\ + & \texttt{0} & \texttt{0} & \texttt{0} & \texttt{1} \\ \hline & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} \end{array}

1-bit Adder

Addition in the i{sup}th spot produces two outputs:

Result bit, i.e., y{sub}i
Carry bit (e.g., c{sub}i+1 which feeds into the addition in the (i+1){sup}th spot addition. We name a carry bit according to the stage to which it is an input.

Zero-th spot

We build our intuition for implementing a 1-bit adder by considering the adder in the zero-th spot (least significant stage). This computes the least significant result bit, $\texttt{y}_{\texttt{0}}$ , and the carry-out bit of the least significant stage, $\texttt{c}_{\texttt{1}}$ .

1-bit adder block demonstrating a single bit-wise addition between a0 and b0, producing output y0 and carry bit c1 to be included in the next single bit addition. The left depicts the fully written 4-bit addition between 4-bit a and 4-bit b, resulting in 4-bit y. There is no carry-in bit in this first single-bit addition between a0 and b0.

By inspection of the truth table in #tab-adder-1-zero, we can directly write the logic equations for this stage³.

\begin{aligned} \\ \\ \\ \texttt{s}_{\texttt{0}} &= \texttt{a}_{\texttt{0}} \texttt{ \^ \ } \texttt{b}_{\texttt{0}} \\ \texttt{c}_{\texttt{1}} &= \texttt{a}_{\texttt{0}} \texttt{ \& } \texttt{b}_{\texttt{0}} \end{aligned}

First spot

Next, consider the logic for the next significant stage (and all subsequent stages):

Single bit addition between bit a1 and b1 with carry bit c1 from previous addition, and producing sum bit y1 and a second carry-out bit c2.

Even though the truth table is larger, the logic equations are still straightforward to write—at least, if we remember what we learned from previous sections.

$\texttt{a}_{\texttt{1}}$	$\texttt{b}_{\texttt{1}}$	$\texttt{c}_{\texttt{1}}$	$\texttt{y}_{\texttt{1}}$	$\texttt{c}_{\texttt{2}}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

\begin{aligned} \\ \\ \\ \\ \\ \begin{aligned} \texttt{y}_{\texttt{1}} &= \texttt{XOR}(\texttt{a}_{\texttt{1}}, \texttt{b}_{\texttt{1}}, \texttt{c}_{\texttt{1}}) \\ \texttt{c}_{\texttt{2}} &= \texttt{MAJ}(\texttt{a}_{\texttt{1}}, \texttt{b}_{\texttt{1}}, \texttt{c}_{\texttt{1}}) \\ &= \texttt{a}_{\texttt{1}}\texttt{b}_{\texttt{1}} + \texttt{a}_{\texttt{1}}\texttt{c}_{\texttt{1}} + \texttt{b}_{\texttt{1}}\texttt{c}_{\texttt{1}} \end{aligned} \end{aligned}

General case

Let us finally consider the logic for the i{sup}th spot, where $i = 0, ..., n-1$ for an $n$ -bit wide addition. We will encapsulate the operations of one stage, or column, of the add operation into a small block, shown in #fig-adder-1-i:

Generic depiction of the i-th full-adder block with inputs ai, bi, and carry bit ci, as well as outputs yi and c_i+1. This shows an intermediate single-bit adder step in a n-bit by n-bit summation.

You can think of this block as a 1-bit adder. It’s official name is a full-adder cell, but most people confuse this with an n-bit adder, which it certainly is not.

The 1-bit adder’s gate-level circuit diagrams for its internals are in #fig-adder-1-i-circuit. The logic equation can be pattern-matched from our earlier discussion and is Equation #eq-adder-1-i.

Gate-level full-adder implementation using XOR for the sum bit and combinational logic with 3 AND gates and an OR gate to calculate the carry-out bit.

\begin{aligned} \\ \\ \\ \begin{aligned} \texttt{y}_{\texttt{i}} &= \texttt{XOR}(\texttt{a}_{\texttt{i}}, \texttt{b}_{\texttt{i}}, \texttt{c}_{\texttt{i}}) \\ \texttt{c}_{\texttt{i+1}} &= \texttt{MAJ}(\texttt{a}_{\texttt{i}}, \texttt{b}_{\texttt{i}}, \texttt{c}_{\texttt{i}}) \\ &= \texttt{a}_{\texttt{i}}\texttt{b}_{\texttt{i}} + \texttt{a}_{\texttt{i}}\texttt{c}_{\texttt{i}} + \texttt{b}_{\texttt{i}}\texttt{c}_{\texttt{i}} \end{aligned} \\ \\ \\ \end{aligned}

N-bit Adder

The next step in the design of our adder circuit is to wire together a collection of our 1-bit adders to create an n-bit adder. All we need to do is to wire the carry-out output of one stage into the carry-in input of the next, from least significant to most, as shown in #fig-cascade-add:

Inputs are applied at the top and after some delay, associated with the delay through the logic gates for the blocks, and the delay of the carry from stage to stage, the final result appears at the bottom.

What to do with carry-in bit c{sub}0? For the adder to produce the correct result, convince yourself that c{sub}0 must be connected to a source of logic 0 (GND in the circuit). But we will find something more interesting to do for c{sub}0 when we discuss the subtractor below.

What to do with carry-out bit c{sub}n? The carry-out from the most significant stage, c{sub}n, can be used as the (n+1){sup}th bit of the result (remember, adding two n-bit numbers could result in a (n+1)-bit result). However, in most uses for an adder, we must generate an n bit result. For instance, RV32I registers can only store 32 bits, so the result of the add instruction must be a 32-bit number. In this case, we must signal overflow, which we discuss next.

Overflow

As discussed in our initial adder/subtractor design, an overflow output must be generated to indicate when the result cannot fit into n bits. Recall from an earlier section that overflow can occur when adding a pair of negative numbers or when adding a pair of positive numbers.

We can make the following observations about adds in this circuit. Remember, the most significant stage is the stage associated with the sign bit, i.e., stage n-1.

If there was a carry in to the most significant stage, but no carry out of that stage, then A and B were both positive and the result of the addition overflowed, erroneously generating a 1 in the sign bit position.
If there was a carry out of the most significant stage and no carry out that stage, then A and B were both negative and the result of addition overflowed.
In all other cases the value of the carry in to the most significant stage matches the carry out, then there was no overflow.

We demonstrate this intuition in #fig-2bit-add-overflow-table for a 2-bit adder.

Table diagram showing different outputs from 2-bit addition with varying carry-bits and signed interpretations, highlighting cases used to reason about overflow.

Based on these observations, we can design a simple circuit that generates the overflow output signal by comparing the carry-in and carry-out of stage n-1. A simple circuit that indicates when two signals are different in value is the XOR gate.

$\texttt{overflow} = \texttt{c}_{\texttt{n}} XOR \texttt{c}_{\texttt{n-1}}$

#fig-cascade-add-overflow shows our full n-bit adder:

Complete ripple-carry adder represented with sequential single-bit adder blocks for bits a0 and b0 through a_n-1 and b_n-1. Overflow detection is computed after the adder logic for bit a_n-1 and b_n-1 using an XOR gate with inputs c_n and c_n-1 from before the final adder block.

Subtractor

We mentioned earlier that addition and subtraction are closely related, and therefore we would expect that their respective circuits are similar and could serve dual both purposes.

As discussed in our initial adder/subtractor design, a control bit SUB signals if the add/subtract block should perform subtraction. We note the following holds, due to two’s complement:

When SUB=0 the circuit performs the addition A + B.
When SUB=1, the circuit performs the subtraction A - B. The following statements are erquivalent:
- Compute A + (-B), where B is the two’s complement.
- Compute A + ~B + 1. This is the definition of two’s complement: invert bits and add 1.

This last observation gives us a very clean way to augment our adder circuit to be a combined adder and subtractor:

Add 1 to the result.
Invert the bits of B.

The augmented adder design is shown below. When the input SUB is 1 the block performs subtraction, when SUB=0 the block performs addition.

The same n-bit adder circuit with overflow detection, but now with subtractor design using XOR gates to conditionally invert B based on a control input SUB that is determining the initial carry-in bit c0.

Wikipedia: Straw Man ↩
As discussed in the previous chapter: Start with a truth table, write the canonical Boolean equation, then simplify. ↩
^: XOR, &: AND ↩

Adder/Subtractor

Learning Outcomes

Cascading Intuition

1-bit Adder

Zero-th spot

First spot

General case

N-bit Adder

Overflow

Subtractor

Footnotes