Boolean Algebra Simplification

[valastar]

Homework Statement

Hey PF!

I'm supposed to "Optimize the equation for minimal input-output delay with 3-input NAND gates of 1.8ns delay each." It'll become much clearer at my attempt at a solution, I hope.

Homework Equations

De Morgan's laws, K-maps, the sort...

The Attempt at a Solution

So this is part of a homework assignment I've been struggling with for a while now. We were given a word problem and had to simplify it using three input NAND gates.

I've simplified the actual word problem to :

F(ABCD)= AB + CD + BD + BC + AD + AC

As you can see this doesn't use any NAND gates, so I simplified it further to:

(A NAND B) NAND (A NAND C) NAND (A NAND D) NAND (B NAND C) NAND (B NAND D) NAND (C NAND D)

Sorry for typing out the NANDS, I thought it would be easier to see than those pesky ' marks.

How do I go about simplifying this further to 3 INPUT NANDS?

I appreciate any guidance!

 

[NascentOxygen]

I've simplified the actual word problem to :

F(ABCD)= AB + CD + BD + BC + AD + AC

So it looks like the output will be HIGH if any two (or more) inputs are HIGH?

 

[valastar]

Yes, that is correct.

 

[NascentOxygen]

Were you given the answer? I get two different implementations, each using 8 gates.

One uses three as inverters, and ends up with a maximum of 4 gates in series.
The other uses four as inverters, but has a maximum of 3 gates in series.

The latter would have least delay. I have no idea whether there is any better implementation, though.

 

[valastar]

Wow 8 gates! Is that inclusive or exclusive of the inverters that you used?

The solution has not been given out yet, so I'm still working on it.

I was able to demorgan the solution down to:

-(-a*-b*-c)*-(-a*-c*-d)*-(-a*-b*-d)*-(-b*-c*-d)

Is that the minimized equation that you used?

I mapped it using a total of 9 gates, of which 3 were inverters. The maximum gate delay was 4 though, so the idea of a solution with a lesser delay seems attractive.

 

[NascentOxygen]

I was able to demorgan the solution down to:

-(-a&&-b&&-c)&&-(-a&&-c&&-d)&&-(-a&&-b&&-d)&&-(-b&&-c&&-d)

Is this a notation that you invented? I thought there were enough notations already...

F(ABCD)= AB + CD + BD + BC + AD + AC

= A•(B+C) + D•(A+B) + C•(B+D)

Replace each red + with a NAND (and inverters), and finally implement the three black + with a NAND.

I haven't checked it, so no guarantees.

 

[NascentOxygen]

I haven't checked it, so no guarantees.

Now, I have checked it. I discovered I blundered.

I can't implement it in fewer gates than you managed. So it's 9, with up to 4 in series.