Design and Implementation of Adder and Subtractor Using Logic Gates

Computers are good at math. Computers, as we've seen, are made out of simple  gates. Gates just do simple logic functions like AND and OR, not math like addition and subtraction. How do we reconcile this?

Simple... we make circuits out of logic gates that can do math. In this section we'll have a look at adders and subtractors.

This also provides a few good learning opportunities to bring out some lessons having to do with digital circuit design.

Let's start simply: adding 2 1-bit numbers. Recall from math class that adding numbers results in a sum and a carry. It's no different here. With two one bit numbers we have 4 distinct cases:

1. 0 + 0 = 0 with no carry
2. 0 + 1 = 1 with no carry
3. 1 + 0 = 1 with no carry
4. 1 + 1 = 0 with a carry

Since we are dealing with binary numbers, and each binary digit corresponds to a logic value, let's express this as a truth table:

What does that remind you of? Well, Sum is A XOR B, and Cout is A AND B!

Boolean expressions

It's common when writing boolean expressions to use operators rather than gate names:

• a vertical centered dot in place of AND
• + in place of OR
• a circled + in place of XOR
• a bar over a negated expression rather than NOT

Using this notation, the expressions describing the above truth table are:

We'll use this format from now on.

Back to the adder

So the logic circuit to add two one bit numbers would be:

Binary addition for adding more than single digit numbers is the same as you learned in school for decimal: you add the two corresponding digits and the carry from the digit adder to the immediate right to give a sum digit and a carry. So our single digit adder must support an incoming carry. What we have above is referred to as a half adder, since is really only does part/half of the job.

What we need to do is expand on this idea to include an incoming carry. Here's the truth table:

Logic simplifcation

As your logic circuits (as well as the associated truth tables and equations) get larger and more complex, it's useful to have some tools and techniques to help simplify them. Why simplify them? Mostly to require fewer gates. That means fewer chips, less silicon, fewer connections, smaller boards, faster circuits, etc. The simpler you can make a circuit and get the same job done, the better.

One useful tool was introduced by Maurice Karnaugh in 1953: Karnaugh Maps. Let's go through an example to see how it works.

To use karnaugh Maps we need to put the truth table in terms of an OR of AND terms. These AND terms correspond to the rows in the truth table contain a logical 1 for the output in question. For the half adder we had:

And for the full adder the equations are:

A Karnaugh Map is a two dimensional table that has 2^n cells if there are n inputs. Adjacent rows and columns can differ by the negation of a single input. Here's the maps for the half adder:

The way it works is that the row labelled "A" corresponds to the A input being high, the other row corresponds to A being low.  Similarly with the columns and the B input. The 1 in the Cout map corresponds to the case when both A and B are high.

There's no simplification to be done on the half adder, it's trivial. The full adder is another story. There are the maps for it.

What you are looking for to simplify using a map is groups of 1s that are some power of 2 in size. In the Sum map above, there are none. Each 1 is separate. That pattern is indicative of an XOR of all three inputs. That can be achieved by chaining XOR gates.

The Carry out is a different story, though. There are three groups of two:

The green circle is the A . B term, leaving the other two 1s to be covered. In both those cases Cin is high and A and B differ. That is the definition of XOR, and so we can rewrite the equation to replace some ANDs, ORs, and NOTs with an XOR.

Interestingly, A . B and A XOR B are both outputs of a half adder as shown above. We need another XOR and another AND. In fact we can use two half adders along with an additional OR gate to build the full adder as shown below.

This full adder only does single digit addition. Multiple copies can be used to make adders for any size binary numbers. By default the carry-in to the lowest bit adder is 0*. Carry-out of one digit's adder becomes the carry-in to the next highest digit's adder. The carry-out of the highest digit's adder is the carry-out of the entire operation.

This is pretty typical of digital circuits that work on data: if you can design a circuit to work on single bit data, multiple copies can usually be used together to operate on bigger data.

_{* A CPU/MCU will have a carry bit in its flag register that can be used as the carry-in for addition operations. The carry out from such operations will be stored in that flag for future use. This allows operations on data larger than can be added at at one time.}

Half subtractor

As before, I'll start with subtracting 1-bit numbers, generating a difference and a borrow. A will be the minuend and B will be the subtrahend. I.e.the circuit will compute A - B.

Here's the truth table:

Converting that to equations:

This gives converts easily to a circuit very similar to the half adder. The only difference is the inverter on A for the computation of the borrow.

Full subtractor

Here's the truth table and corresponding maps for the full subtractor, which takes into account an incoming borrow. I'll skip the step of writing out the equations, as the maps can easily be constructed directly from the truth table.

As before, the next step is to find the groups in the map in order to simplify the logic.

Taking the red group first, we have:

From the half subtractor, we have various pieces of this, and can do the same thing we did with the full adder: use a couple half-subtractors and an OR gate:

As with the full adder, full subtractors can be strung together (the borrow output from one digit connected to the borrow input on the next) to build a circuit to subtract arbitrarily long binary numbers.

Notice that subtractors are almost the same as adders. In fact a single circuit is generally used for both, with some "controllable invertors" being used to switch between operations. Going further than that, a CPU contains an Arithmetic-and-Logic-Unit (aka ALU) that takes two numbers, and an operation selector to configure it to perform one of a variety of arithmetic or logic operations.

Adder on a chip

This was an interesting exercise, but we'll never need to build an adder from gates. There are adder chips that can be dropped into our designs. The 7483 is one example.

Recap

There's a lot in this section:

• describing a circuit's desired behaviour with a truth table,
• extracting a AND-OR equation for each output column of the table,
• simplifying those equations using Karnough Maps,
• implementing the simplified equations using logic gates, and
• looking for similarities in existing designs to leverage work already done.

While you can always implement a truth table by ORing ANDed terms, with NOTs in the right places, it's usually not the most efficient. When using discrete gate ICs a one goal is always to minimize the chip count; fewer chips means a faster circuit, using less power, and generating less heat. These things aren't as relevant when you are using MCUs (they are when designing them, though), but it's a fun puzzle to solve.

This guide was first published on Apr 11, 2018. It was last updated on Apr 11, 2018.

This page (Adders and Subtractors) was last updated on Dec 20, 2021.

Text editor powered by tinymce.

Design and Implementation of Adder and Subtractor Using Logic Gates

Source: https://learn.adafruit.com/combinational-logic/or-and-nor

Share this post