Efficient Design of a Full Adder with Karnaugh Maps

3 replies · 4K views · last reply
Bluskyz
Messages
20
Reaction score
0
Just a quick apology for the long post. Recently I have been looking into digital circuit design and how karnaugh maps can help you simplify a logic table to simple gates. I extended this idea to trying to derive the most efficient full adder design and came up with the following logic table for two 1-bit inputs (a and b) for the current bits being added and a carry in(c):

x-y-c-a1-a0
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

Then I made the karnaugh maps corresponding to the outputs, one for the most significant bit and another for the other bit.

Two Karnaugh maps for a full adder: the most significant bit map with ab on columns and c on rows, and the next most significant bit map with the same layout, each showing filled cells in black.


At this point I began looking at the map for the most significant bit and noted the groupings and turning them into a logical equation.

ab+ac+bc

With this, I don't really think that you can simplify this problem very much. I just simplified out the carry bit resulting in:

ab+c(a+b)

The story is similar with the next significant bit but due to the fact that there aren't any groupings in the karnaugh map, it really can't be simplified. I ended up with the following:
_
c(a[itex]\odot[/itex]b)+c(a[itex]\oplus[/itex]b)

After taking these final equations for the two outputs bits, I combined them into the final circuit. This should be a simplified form of a full adder.

Logic circuit diagram of a full adder with inputs Input a, Input b and Cin, and outputs Output Bit and Cout, built from XOR1, XNOR1, NOT1, AND2, AND3, AND4 and AND5 gates.


Comparing this to a fully simplified version of a full adder here:

Logic circuit diagram of a full adder with inputs A, B and Cin, outputs S and Cout, built from two XOR gates, two AND gates and one OR gate.


Both circuits are very similar its just mine seems to have a few more unessesary gates. Firstly, it seems that my xnor gate can simply be an xor wired to the output of the first xor gate and the carry in. Secondly, the additional and gates after the xor and xnor gates on my circuit can be completely omitted. My ultimate question is this: Is there a methodical way in which I can find the most simplified circuit for a corresponding truth table without resorting to brute force and examination of which parts can be omitted, changed, etc? Thank you for your help.
 
Attachments
  • Two Karnaugh maps side by side: the top labelled Most Significant Bit with ab columns 00, 01, 11, 10 and c rows 0, 1, shaded cells forming a grouping; the bottom labelled Next Most Significant Bit with a checkerboard pattern of shaded cells.
    Karnaugh.PNG
    3.4 KB · Views: 696
A K-map doesn't give you XOR or XNOR so no, there isn't a methodical way to do what your'e asking.

You did the k-map correctly but you didn't simplify the Sum bit well. Look again and you'll see that when C=0 its just an XOR and obviously once you see than when C=1 you've got an XNOR (you can do this algebraically if you want).

Typically if you see a "checkerboard" pattern you should be looking for ways to use XORs and XNORs. There is a logic style focused on XORs called "Reed Muller" logic that you may find interesting.

http://www.eetimes.com/document.asp?doc_id=1274545

Keep in mind we never use this in industry (at least I've never seen it done).
 
analogdesign said:
A K-map doesn't give you XOR or XNOR so no, there isn't a methodical way to do what your'e asking.

You did the k-map correctly but you didn't simplify the Sum bit well. Look again and you'll see that when C=0 its just an XOR and obviously once you see than when C=1 you've got an XNOR (you can do this algebraically if you want).

Typically if you see a "checkerboard" pattern you should be looking for ways to use XORs and XNORs. There is a logic style focused on XORs called "Reed Muller" logic that you may find interesting.

http://www.eetimes.com/document.asp?doc_id=1274545

Keep in mind we never use this in industry (at least I've never seen it done).

I should be a bit more explicit. A Karnaugh map gives you a sums-of-products expression or a products-of-sums expression depending on whether you minimize the ones or zeros. That maps onto AND and OR gates in boolean logic, not XORs.