Adders

Adders#

Adder circuits are circuits that perform binary addition, and in many cases subtraction as well using the 2’s complement system. The entire addition operation is typically carried out by a large assembly called the Arithmetic Logic Unit (ALU), but at its core are circuits that simply perform the bit-by-bit addition in each column as a logic operation.

Adder logic circuits for one bit come in two types:

  • Half Adder: Has two inputs (\(A\) & \(B\)) and two outputs: the Sum (\(S\)) and Carry (\(C_{out}\)).

  • Full Adder: Can also take an additional input \(C_{IN}\), the carry bit from another adder. A Full Adder can be constructed from two half adders.

Full Adder Logic#

What does the inner circuitry of a Full Adder look like? Let’s use a K Map to design one. First we will make a truth table, recalling how addition works.

\(A\)

\(B\)

\(C_{in}\)

\(C_{out}\)

\(S\)

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

For \(S\) The K-map looks like so:

Kmap for S

There are not really any simplifying loops we can do, but remember that the checkerboard pattern means the circuit diagram can be be made more compact with XOR gates.

\[\begin{split}\begin{aligned} S &= \bar{A}\bar{B}C + \bar{A}B\bar{C} + ABC + A\bar{B}\bar{C} \\ &= \bar{A}(\bar{B}C + B\bar{C}) + A(BC + \bar{B}\bar{C}) \\ &= \bar{A}(B \oplus C) + A(\overline{B \oplus C}) \\ &= A \oplus B \oplus C \end{aligned}\end{split}\]

For \(C_{out}\):

Kmap for Cout

Here, we do have some loops and the sum-of-products expression is simply

\[C_{out} = AB + BC + AC\]

The final full adder circuit is shown below. This circuit will add, at most, three one-bit numbers.

[Figure: Logic circuit implementation. Inputs A, B, and C run down the left side. Two cascaded XOR gates produce \(S\) (A XOR B, then XOR C). Three AND gates (for AB, BC, and AC) feed into an OR gate producing \(C_{out}\).]

Parallel Adder#

Since we usually want to sum binary numbers with more than one bit, several adders are chained together to create a Parallel Adder. Here is an example of a 4-bit Parallel Adder.

Figure: Four Full Adder blocks in a row. Each Full Adder takes input from above and from below, and outputs a sum downward. Carries chain from right to left: enters the rightmost Full Adder, which passes to the next, then , then , with the leftmost producing .

The right-most adder is the Least Significant Bit, and could be implemented with a half-adder since there would be no carry input. However, we shall soon see that it is still useful to have a Full Adder in the LSB place.

An important consideration is carry-bit propagation. Each full adder cannot give the correct answer until it receives the correct carry-in from the previous adder. That means that in this set up, the time it takes to add N-bit numbers scales linearly with the number of bits. If each full adder has a propagation delay of \(t_P\), then it takes \(Nt_P\) seconds to arrive at the correct answer. If speed is an important consideration, calculation time can be improved by having a separate circuit dedicated to calculating each carry-bit individually directly from the numbers being added. This is known as a Carry Look Ahead adder, and it is significantly faster than the parallel adder above, but comes at the cost of significantly increasing circuit size, complexity, and power consumption.

ALU#

To control timing considerations and determine which numbers are being added processors have an Arithmetic Logic Unit (ALU). The ALU will have a parallel adder at its center (possibly with Carry Look Ahead functionality) as well as two registers called the A register (also known as the Accumulator) and the B register, and a control unit. The control unit coordinates loading values from memory addresses, clearing the registers, and sending signals to perform the summation operation.

Figure: Block diagram of an ALU. A large Memory block on the left. In the center, an Accumulator block sits above an Adder block, with arrows between them in both directions. A B Register block sits below the Adder, feeding up into it. A Control Unit block on the right sends arrows to the Adder and down toward the B Register. Memory feeds the Accumulator and the B Register, and a line runs from the bottom back to Memory.

Let’s walk through the steps to add two numbers 1001 and 0101 together. ALLCAPS terms are signals sent from the control unit.

  1. CLEAR to make [A] 0000.

  2. LOAD first number (say 1001) into the [B]. The sum from the adders is now 1001 as well, but note that it hasn’t been moved to Accumulator yet.

  3. TRANSFER to move the sum output of the parallel adder to [A], now 1001.

  4. LOAD to put next number (0101) into [B]. Sum becomes 1110.

  5. TRANSFER to set [A] to the desired sum. This overwrites what was in [A] and replaces it with the entire sum of 1110.

  6. If finished, [A] can be output to memory. If you want to add another number, go back to step 4 and transfer a new value into [B]. Repeating steps 4 and 5 will continue to add to the accumulator (hence the name).

Below is a more complete look at how the registers and parallel adder are connected together.

Figure: A full 4-bit register/adder diagram spanning the page. Top: a bus labeled "From Memory" (marked with a brace) feeds the D inputs of four D flip-flops labeled , , , — the B Register (labeled in red). A LOAD line runs across and connects to the clock input of each B flip-flop. Middle: each B flip-flop output feeds the B input of a corresponding Full Adder — the Adder row (labeled in red). The adders are chained by carries from right to left: in at the far right, then , , between stages, and out at the far left. Bottom: each Full Adder's sum output feeds the D input of a flip-flop labeled , , , — the Accumulator (A Register) (labeled in red). Each A flip-flop has a clock input and an active-low input. A CLEAR line connects to all inputs, and a TRANSFER line connects to all clock inputs. The A flip-flop outputs feed back up into the A inputs of the Full Adders, and also run down to a bus labeled "To Memory" (marked with a brace). Red note with arrow from the LOAD/CLEAR/TRANSFER lines: The LOAD, CLEAR and TRANSFER commands would come from the control unit.

So why keep \(C_0\) as an input? It is so that we can use this same parallel adder to subtract as well as add.

Let’s put in another flag from the control unit. An ADD command that is level triggered, so that ADD = 1 will add A+B, and ADD = 0 will lead to subtraction of A−B. When ADD is 0, we want to turn B into its 2’s complement. Recall that a number’s 2’s complement was found by flipping the bits and adding 1. This is why \(C_0\) is useful, it can be used to perform the “add 1”.

Place the following logic component in between the B register and the adder, and your adder can now subtract as well:

Figure: An ADD control line runs horizontally. Inputs , , , each feed one input of a two-input XNOR gate (drawn as an XOR gate with an inverting bubble on the output), with the ADD line feeding the other input of each gate. The four gate outputs feed into an Adder block below. The ADD line also passes through an inverter (a triangle with a bubble) into the input of the Adder — so when ADD = 0, the B bits are inverted and , forming the 2's complement.

I guess when performing subtraction through addition more is less?