Full adder

[joobcode]

Rather than using halfadders I wanted to see what a simplified canonical representation of the full adders truth table would yield.

As there are 2 outputs, I assumed that I would need to build 2 seperate C.R's. One for Sum output and one for the Carry?

I get this:

a   b   c    car     sum    carCR    sumCR
0   0   0     0        0      
0   0   1     0        1                  A'B'C
0   1   0     0        1                  A'BC'
0   1   1     1        0       A'BC
1   0   0     0        1                  AB'C'
1   0   1     1        0       AB'C
1   1   0     1        0       ABC'
1   1   1     1        1       ABC      ABC

CR sum =  A'B'C+A'BC'+AB'C'+ABC
CR car  =  A'BC+AB'C+ABC'+ABC

Why does this simplification not work?

Carry:
A'BC+AB'C + ABC'+ABC good
C(A'B+AB') + A(BC'+BC) good
C               + AB           bad

What am I missing?

[cadet1620]

joobcode wrote

Why does this simplification not work?

Carry:
A'BC+AB'C + ABC'+ABC good
C(A'B+AB') + A(BC'+BC) good
C               + AB           bad

What am I missing?

Bad algebra in the last step. The teacher in me says, "Show your work." How'd you get from step 2 to 3? What you're aiming for is:
    Cout = AB + AC + BC

--Mark

[joobcode]

Well bad algebra I knew already ;-)

Where I write good I mean I have tested the circuit and it is correct for cout.

Cout:
 
A'BC+AB'C + ABC'+ABC good
Apply the distributive law.
C(A'B+AB') + A(BC'+BC) good
Given that x.x' = 1 I can reduce the 1st term:
C  + A(BC'+BC) bad, am I miss applying here?

So applying x.x'=1 to the term C(A'B+AB') causing the circuit design it yields to break. Really not sure why? Is it because I am negating A an B variables from that term altogether?

Strangely if I do this it works:

cout = A'BC+AB'C + ABC'+ABC
Expand ABC
A'BC+AB'C +ABC'+ABC+ABC+ABC
Using x+x'=1 for 1st and 4th, 2nd and 5th, 3rd and 6th term.
BC+AC+AB

So far I am at a loss to understand why I must expand before I can reduce with x+x'=1 in this example. Till now just applying the rules like x+x'=1, x'x = 0 etc have worked well.

[cadet1620]

joobcode wrote

C(A'B+AB') + A(BC'+BC) good
Given that x.x' = 1 I can reduce the 1st term:
C  + A(BC'+BC) bad, am I miss applying here?

The problem is that (~A)B does not equal ~(A(~B)) so X + ~X = 1 does not apply.

The easiest way to simplify Boolean expressions is using Karnaugh maps. http://www.facstaff.bucknell.edu/mastascu/elessonshtml/Logic/Logic3.html is a good introduction.

--Mark

[joobcode]

K-Maps our very interesting, thank you.

Could you please show your work with regard to your statement,

(~A)B does not equal ~(A(~B)) so X + ~X = 1

when considering my reduction of:

C(~AB  + A(~B) )

=======

You mention ~(A(~B)) which I read as:

Not( And(A, Not(B) ))

I ask for your working because I can't see this directly in the term I want to reduce or how to derive this from the term I am trying to reduce.

It has occurred to me that I might not be using the correct conventions for expressing this term with plain text. So here is the term I trying to reduce in postfix notation.

And(C, Or( And(Not(A),B), And(A, Not(B) ) ) )

[cadet1620]

joobcode wrote

You mention ~(A(~B)) which I read as:

Not( And(A, Not(B) ))

I ask for your working because I can't see this directly in the term I want to reduce or how to derive this from the term I am trying to reduce.

It has occurred to me that I might not be using the correct conventions for expressing this term with plain text. So here is the term I trying to reduce in postfix notation.

And(C, Or( And(Not(A),B), And(A, Not(B) ) ) )

Your notation is OK.

To use x + ~x = 1 to reduce the above, And(Not(A),B) and And(A,Not(B)) must be logical inverses. In other words,
    And(Not(A),B) = Not(And(A,Not(B)))
must be true. It is not. Use truth tables to compare them.

--Mark

[joobcode]

Thank you, that makes more sense now and K-Maps are an easier again option.

If I build it from 2x Halfadders and 1 Or that is total of 15 Nand
If I use K-maps / simplified canonical form I get an different 15 Nand total layout.

Some googling shows me a Full adder implementation in 9 Nand! What is the next tool to derive this? Super K-maps? ;-)

http://ca.wikipedia.org/wiki/Fitxer:NandFullAdder.png

[cadet1620]

Getting to the 9 Nand solution comes with experience. The 4 Nands in a diamond pattern are the known best Nand implementation of Xor, which is the adding part of a half-adder. Conveniently, the first Nand in each Xor generates ~carry. The two ~carrys can be Ored together with a Nand because of DeMorgan's law.

If you take a look at Why We Like Abstraction there's an ALU done entirely with Nands. You'll see a lot of these 9-Nand adders.

--Mark

[Radoslav]

Hi.
Maybe it helps some people with Full-adder implementation problem.
Canonical( full ) :
   SUM=(~a)*(~b)*c+(~a)*b*(~c)+a*(~b)*(~c)+a*b*c
 
  abbreviation form of SUM = ~a*Xor(b,c)+a*(~Xor(b,c))

Canonical( full ) :
   Carry=(~a)*b*c+a*(~b)*c+a*b*(~c)+a*b*c
 
  abbreviation form of CARRY=c*Xor(a,b)+a*b

It's just my implementation so i think it isn't the most simplify form.