## Karnaugh Map Minimizations

Started by 2 years ago8 replieslatest reply 2 years ago103 views

It's funny how easy it is to forget things that you used to do all the time. I'm going to be writing a series of columns teaching digital logic fundamentals to newbies. I've been jotting down some notes and -- as part of all this -- I just created the truth table and performed the K-map minimizations for a BCD to 7-segment decoder -- now I'm looking at them wondering if (a) I did everything right and (b) if I missed anything obvious. If you have a few minutes to take a look, that would be awesome: https://www.clivemaxfield.com/kan-klives-karnaugh-...

[ - ]
Klive, I did not analyze your truth table,. I just looked at the map. On a Karnaugh map, terms on opposite ends of rows are adjacent, since only one variable changes. Similarly terms on opposite ends of columns are adjacent. Visualize the columns being written on a cylinder with a vertical axis. This makes the top and bottom rows adjacent. Consequently you can draw a loop around 0000 and 0010. Otherwise the map looks OK.
[ - ]

Hi Kral -- as you say, that's the beauty of K-maps -- the fact that their rows and columns are ordered using as Gray codes -- I'm really impressed that Karnaugh came up with this -- I bet he was really excited when he realized what he'd got :-)

[ - ]

Hi, MaxMaxfield !

When I saw the subject of the thread, I thought, can only be MaxMaxfield!   :-)

Many years have passed since I have used Karnaugh Maps for the last time, hence, I cannot be of any help to you, but I appreciate too much your initiative to bring knowledge to others.

FYI, when I studied this subject in the eighties, I used the fantastic book of William I. Fletcher, An Engineering Approach to Digital Design.

Perhaps it's worthwhile to give a look at this book ( https://books.google.com.br/books/about/An_Enginee... ).

Cheers!

Dilberto.

[ - ]

Hi Dilberto -- it's funny (well, not so funny) how much we forget if we don't keep on practicing with this stuff -- but it's also interesting how quickly it all comes back when you start doing it again -- I'm actually finding it to be a lot of fun.

[ - ]

Hi Max, I think your map decodings look good, if you missed anything then so did I. In your discussion it might be worth noting that you can also decode 0's and invert. For example, in segment c you can circle just the two bottom corners, and in segments d and f there are decodings with three terms instead of four.

c = !(!d2 & d1 & !d0)
d = !((d2 & !d1 & !d0) | (!d2 & !d1 & d0) | (d2 & d1 & d0))
f = !((d1 & d0) | (!d2 & d1) | (!d3 & !d2 & d1))

These aren't great simplifications, but are perhaps useful for instructional purposes.

Fond memories! I don't think I've whipped out a Kmap in the course of a logic design problem since the 80s, Synopsys really changed the game. I also recall using Espresso in situations where the number of inputs made the Kmap approach unwieldy. These minimization tools and techniques don't find much use nowadays, but are certainly still more relevant than drafting templates with logic gates!

[ - ]
Hi Matthew -- I was on the fence about telling them about optimizing using 0s -- but based on your feedback I now think I should add that in as a sidebar, so thanks so much for your input. Re your stencil ... YOU HAD A STENCIL? (We used to dream about owning a stencil LOL)
[ - ]

Hi Max,

I hadn't heard of K-maps before - I guess it didn't come up in mechatronics class. It looks like a really useful tool as I had a use case just the other day. I'm looking forward to your series!

I did notice from your examples that two numbers do not appear how I'm used to seeing them. I often see "9" with LED (d) and "6" with LED (a) illuminated. How much would these changes affect the resulting mapping?

One more question: if I wanted sink LED current through the logic gate by changing illuminated LEDs to 0 and off LEDs to 1, is it fine to just apply a logical NOT to each mapping and then reduce or should the K-map be rewritten?

Thanks,

Daniel

[ - ]