Maker Pro
Maker Pro

I have a problems with K-Map minimization

alK

May 17, 2012
16
Joined
May 17, 2012
Messages
16
Really? Seems correct to me.

X5 AND NOT (X2 OR X3)

Yellow square - area, where x5 = 1
In blue coverage x5 present both in direct and (left cells) inverse state - it is wrong
attachment.php


Timothy's idea has the same error
 

Attachments

  • y1-steve1.png
    y1-steve1.png
    20.9 KB · Views: 289

(*steve*)

¡sǝpodᴉʇuɐ ǝɥʇ ɹɐǝɥd
Moderator
Jan 21, 2010
25,510
Joined
Jan 21, 2010
Messages
25,510
Yellow square - area, where x5 = 1
In blue coverage x5 present both in direct and (left cells) inverse state - it is wrong

Timothy's idea has the same error

OK, sorry, I didn't move it over. (Told you I was a beginner!)

((X6 AND NOT X4) OR (X5 AND NOT X6) AND NOT (X2 OR X3)

But you don't need the blue one if you move the purple on down a square
 

alK

May 17, 2012
16
Joined
May 17, 2012
Messages
16
((X6 AND NOT X4) OR (X5 AND NOT X6) AND NOT (X2 OR X3)

But you don't need the blue one if you move the purple on down a square

The formula that you take is not in sum of products ( a&b&c + d&e + ...) nor product of sums ( (a+b+c) & (d+e) & ... ) form.
can you rewrite it in one of this canonical forms?

covering by 1 means that we looking for sum of products
 
Last edited:

gorgon

Jun 6, 2011
603
Joined
Jun 6, 2011
Messages
603
Hey, this Karnaugh mapping is interesting.

Say, alK, why don't you help educate me by explaining what these things are used for?

Karnaugh maps is the graphical, and practical tool between a truth table and the logic expressions resulting from it. The result is eventually the discrete logic gates you will need to process the signals to the get result in the truth table.

TOK ;)
 

(*steve*)

¡sǝpodᴉʇuɐ ǝɥʇ ɹɐǝɥd
Moderator
Jan 21, 2010
25,510
Joined
Jan 21, 2010
Messages
25,510
OK...

4396d1337322322-have-problems-k-map-minimization-y1-steve1.png


Blue: X1'.X2'.X3'.X6.X4' + X1'.X2'.X3'.X5.X6' + X1.X2'.X3'.X6.X4' + X1.X2'.X3'.X5.X6'

But it really only needs to be X5.X4'.X2'.X3'

But that is superfluous if you drop the purple one down a square:

X1.X3.X5.X4' + X2'.X3'.X5.X4'

Don't say it can't be done!
 

alK

May 17, 2012
16
Joined
May 17, 2012
Messages
16
OK...
Blue: X1'.X2'.X3'.X6.X4' + X1'.X2'.X3'.X5.X6' + X1.X2'.X3'.X6.X4' + X1.X2'.X3'.X5.X6'
It is a four different terms, four different coverages with too big complexity.
purple term is only x1&~x4&x5

But it really only needs to be X5.X4'.X2'.X3'
the same - it is two different coverages, not one.

X1.X3.X5.X4' + X2'.X3'.X5.X4'
same as above
Don't say it can't be done!
it can't be done ;)

Try to solve K-Maps in this program - http://gorgeous-karnaugh.com/
no longer a lot of questions
 
Last edited:

(*steve*)

¡sǝpodᴉʇuɐ ǝɥʇ ɹɐǝɥd
Moderator
Jan 21, 2010
25,510
Joined
Jan 21, 2010
Messages
25,510
How is this X5.X4'.X2'.X3' two different coverages? (I don't understand, maybe it is)

All my examples were sums of products.

I did pretty much what is done here on page 6.

Personally, I don't think the sum of products or the product of sums is the simplest. In terms of gates you probably want to factor stuff out and get to what I gave in an earlier answer.

For example:

X1'.X2'.X3'.X6.X4' + X1'.X2'.X3'.X5.X6' + X1.X2'.X3'.X6.X4' + X1.X2'.X3'.X5.X6'

becomes

X1'.X2'.X3'.(X6.X4' + X5.X6') + X1.X2'.X3'.(X6.X4' + X5.X6')

which further factors out to

(X1'.X2'.X3' + X1.X2'.X3').(X6.X4' + X5.X6')

and yet further to

(X2'.X3')(X1' + X1).(X6.X4' + X5.X6')

which simplifies to

(X2'.X3').(X6.X4' + X5.X6')

Look at the rules for defining these maps. None of the 2^n size rectangles we've defined break those rules. Therefore they MUST be able to be expressed.

Perhaps you have some idea of what "simple" means that differs from me.

At the very least this is the blind leading the blind,
 

alK

May 17, 2012
16
Joined
May 17, 2012
Messages
16
How is this X5.X4'.X2'.X3' two different coverages? (I don't understand, maybe it is)
Sorry, my error

All my examples were sums of products.
Not, you are wrong.

I did pretty much what is done here on page 6.
you may be something wrong there understood

Personally, I don't think the sum of products or the product of sums is the simplest. In terms of gates you probably want to factor stuff out and get to what I gave in an earlier answer.

For example:

X1'.X2'.X3'.X6.X4' + X1'.X2'.X3'.X5.X6' + X1.X2'.X3'.X6.X4' + X1.X2'.X3'.X5.X6'
This is a sum of product, yes, but it is not a minimal form. You covers on K-Map:
4397d1337332533-have-problems-k-map-minimization-y1-by1.png



becomes

X1'.X2'.X3'.(X6.X4' + X5.X6') + X1.X2'.X3'.(X6.X4' + X5.X6')

which further factors out to

(X1'.X2'.X3' + X1.X2'.X3').(X6.X4' + X5.X6')

and yet further to

(X2'.X3')(X1' + X1).(X6.X4' + X5.X6')

which simplifies to

(X2'.X3').(X6.X4' + X5.X6')

Look at the rules for defining these maps. None of the 2^n size rectangles we've defined break those rules. Therefore they MUST be able to be expressed.

Perhaps you have some idea of what "simple" means that differs from me.

At the very least this is the blind leading the blind,


You perform all minimzation job by hands, but using K-Map is more easy way

Expression:
y1 = !x2 !x5 !x6 + x1 !x4 x5 + !x2 !x4 !x6 + x2 x6;
covers all of 1 on the K-Map.
This expression is a minimal function in form of sum-of-products
Yours
X1'.X2'.X3'.X6.X4' + X1'.X2'.X3'.X5.X6' + X1.X2'.X3'.X6.X4' + X1.X2'.X3'.X5.X6'
is more longer and don't covers all ones.

y1-by1.png
 
Last edited:

(*steve*)

¡sǝpodᴉʇuɐ ǝɥʇ ɹɐǝɥd
Moderator
Jan 21, 2010
25,510
Joined
Jan 21, 2010
Messages
25,510
OK, so you're an expert.

I thought we were talking about a single rectangle (which you entered incorrectly into whatever that draws the map by the way).

you got this one wrong: X1.X2'.X3'.X6.X4' (you entered it as X1.X2'.X3'.X6'.X4')

But I guess what you and I both learned is that getting an optimal set of regions is important.

But can you explain what I've done wrong in mapping your supposed best answer?

attachment.php


I can't seem to get your y1 = !x2 !x5 !x6 + x1 !x4 x5 + !x2 !x4 !x6 + x2 x6 to cover all the 1s.

Maybe you need something like an extra x1.x2.x5

What I've learned from this is going to be my rule 0 of Karnaugh Maps

0: Draw rectangles that can be easily represented in logic.

For example, on this map x1.x2.x5 and x1.x2.x5.!x6 are both "correct", but one requires less terms than the other. Another group of 8 is apparently not able to be expressed as a simple product.

The clause x1 !x4 x5 is certainly not one which jumps out immediately, and I'm not sure how I could be lead to it.

Perhaps you could walk me through it?
 

Attachments

  • y1-by1-2.png
    y1-by1-2.png
    26 KB · Views: 839

timothy48342

Nov 28, 2011
218
Joined
Nov 28, 2011
Messages
218
Sum of products form will not always be the simplest form, that's true, but still needs to be that way, apparently. I don't know why the truth formula has to be in that form, but it probably has to do with the next step. (Whatever that is) But I know it can't contain any sub-terms. just like polynomials: s^3 + (s+3)^2 is not in sum of products form but s^3 + s^2 + 6s + 9 is.

I think I remember some type programmable chip that has a whole bunch of inputs and one output and during programming each term takes one programming step. That was a long time ago and I don't rememebr using k-maps, just formulas. Can't remember what they were called now.

alK, what is the final truth formula used for?

The term for the purple box shifted down by one row would be like steve said, X1.X3.X5.X4' + X2'.X3'.X5.X4'
The problem with that is not that it can't be done, it is just that is ends up being 2 terms.
I having trouble finding information just how to know ahead of time if a certain allignment will give a single term, but I did find this describing another way that squares can be adjacent.
Imagine a fold down the center of the map, so that green group and the orange group into one. I believe it would simply be X2X6
(Opps, I see you guys already noticed that those can combine. ok. There is other information in that link it mostly is a good explaination of dealing with 5 and 6 variable k-maps.)

I can't see any way to combine the purple and blue areas without making more terms, but I do see that shifting the blue box to the left overlapping red makes it easy to write out and 8 squares instead of 4, so it is X2'X3'x4'

So the whole formula so far as I see it:
y1=(green/orange)X2X6 + (red)X2'X5'X6' + (purple)X1X4'X5 + (blue shifted left)X2'X3'x4'
Does that work. It is very similar to what you had earlier:
k-map.jpg

--tim
 

(*steve*)

¡sǝpodᴉʇuɐ ǝɥʇ ɹɐǝɥd
Moderator
Jan 21, 2010
25,510
Joined
Jan 21, 2010
Messages
25,510
Ah yes, blue shifted left one more. Very clever.

I think the "don't care" positions mean there are a huge permutation of correct answers and there is some artistry in getting the simplest.
 
Top