about Karnaugh maps?

[Amol S.]

How does one loop Karnaugh maps?

 

[TuxDave]

How does one loop Karnaugh maps?

1) Do you know how to write truth tables?
2) Do you know how to convert that into a Karnaugh map?

Then comes looping (which is actually the easiest part).
Then comes translating your loops back into a logical equation.

So to help others that want to help you, can you give some more feedback on what you know so that we don't have to start from scratch?

 

[Amol S.]

1) Do you know how to write truth tables?
2) Do you know how to convert that into a Karnaugh map?

Then comes looping (which is actually the easiest part).
Then comes translating your loops back into a logical equation.

So to help others that want to help you, can you give some more feedback on what you know so that we don't have to start from scratch?

Yes I know how to do the two things above that you said.

 

[TuxDave]

Yes I know how to do the two things above that you said.

So to circle them.... find a set of squares where
1) Each square is a power of 2 in width and a power of 2 in height
2) Each square encloses ONLY 1's
3) Each square can wrap around the edges
4) And where the union of all those squares cover all the 1's in the Karnaugh map

Done, you "looped a Karnaugh" map.

 

[Amol S.]

So to circle them.... find a set of squares where
1) Each square is a power of 2 in width and a power of 2 in height
2) Each square encloses ONLY 1's
3) Each square can wrap around the edges
4) And where the union of all those squares cover all the 1's in the Karnaugh map

Done, you "looped a Karnaugh" map.

Nice bunny you have in your posts, did u make it?

 

[atomheart]

2) Each square encloses ONLY 1's

You can also circle "x" (don't care) terms, right?

 

[TuxDave]

You can also circle "x" (don't care) terms, right?

Yeah, forgot about those. You are allowed to circle "x"s if it makes a bigger circle but you do not have to enclose all of them.

 

[videogames101]

It's also worth mentioning you can also circle the zeros and get POS (product of sums) expressions rather than SOP (sum of products). Had someone ask me about that in an interview once I think. You can sometimes get much simpler expressions this way, but as with most things ymmv. Circuits that can be more simply expressed in POS can be slower than more complex SOP expressions because the "classic" implementations used nor-nor and nand-nand logic gates respectively and nand gates are faster.

 

[atomheart]

Circuits that can be more simply expressed in POS can be slower than more complex SOP expressions because the "classic" implementations used nor-nor and nand-nand logic gates respectively and nand gates are faster.

Is that typically the case? I had to make some NAND/NOR layouts in the VLSI course I'm in and for similar sized gates the NOR was a good bit faster. (like 150ps fall times for NOR and about 200-300ps for NAND). Just curious as I'm still learning.

edit: Nevermind. When you have a NOR you have two nmos in parallel for the pull-down so it's effectively twice as wide when both nmos are are, to have symmetric rise/fall times the pull-up needs to be pretty large. But for the NAND you have two PMOS in parallel which right off the bat helps balance the rise/fall times. It seems like the NAND could stay closer to minimum gate sizes while still being symmetric. All this also accounts for why the NOR has decent fall times (vs NAND when all gate sizes are minimum).


I just woke up, but is this half-way correct?

 

[videogames101]

Is that typically the case? I had to make some NAND/NOR layouts in the VLSI course I'm in and for similar sized gates the NOR was a good bit faster. (like 150ps fall times for NOR and about 200-300ps for NAND). Just curious as I'm still learning.

edit: Nevermind. When you have a NOR you have two nmos in parallel for the pull-down so it's effectively twice as wide when both nmos are are, to have symmetric rise/fall times the pull-up needs to be pretty large. But for the NAND you have two PMOS in parallel which right off the bat helps balance the rise/fall times. It seems like the NAND could stay closer to minimum gate sizes while still being symmetric. All this also accounts for why the NOR has decent fall times (vs NAND when all gate sizes are minimum).


I just woke up, but is this half-way correct?

We're all still learning in this field I think. It's a very typical case. Also your reasoning seems fine, but as I understand it:

So, normally you don't size everything minimum as that is not the fastest gate structure. When you talk about speed, you can't just look at fall times (although ymmv, sometimes you just need one direction to be fast) you have to look at worst case which is going to be rise times for the NOR case. PMOS stacks are really slow, significantly slower than NMOS stacks. That is really the kicker from my understanding. The usual reasoning for which comes from differences in hole/electron mobility.

Another point, the classic sizing for a 2-input NAND and NOR means you double the widths of the transistors you're stacking. Doubling your NMOS widths instead of sizing up the PMOS network by 2 will net you a smaller change in total input capacitance compared to the nominal fast inverter sizing.

 

[TuxDave]

Is that typically the case? I had to make some NAND/NOR layouts in the VLSI course I'm in and for similar sized gates the NOR was a good bit faster. (like 150ps fall times for NOR and about 200-300ps for NAND). Just curious as I'm still learning.

edit: Nevermind. When you have a NOR you have two nmos in parallel for the pull-down so it's effectively twice as wide when both nmos are are, to have symmetric rise/fall times the pull-up needs to be pretty large. But for the NAND you have two PMOS in parallel which right off the bat helps balance the rise/fall times. It seems like the NAND could stay closer to minimum gate sizes while still being symmetric. All this also accounts for why the NOR has decent fall times (vs NAND when all gate sizes are minimum).

I just woke up, but is this half-way correct?

In classical theory, a NOR would require more area to have equal timing to a NAND. In terms of static timing, you would like rise/fall time to be as close as possible* but you can't really guarantee it because sometimes you'll have both parallel legs active, sometimes you'll only have one. We're talking about logic gates here. So the rule of thumb is to make the rise/fall time roughly equal for the worst case meaning only one parallel leg is active.

*Sometimes you can have an advantage in skewing the rise time vs fall time.