Karnaugh Map Minimizations

Started by 1 year ago8 replieslatest reply 1 year ago91 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-...

[ - ]
Reply by November 24, 2020
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.
[ - ]
Reply by November 24, 2020

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 :-)

[ - ]
Reply by November 24, 2020

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.

[ - ]
Reply by November 24, 2020

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.

[ - ]
Reply by November 24, 2020

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!

[ - ]
Reply by November 24, 2020
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)
[ - ]
Reply by November 24, 2020

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

[ - ]
Reply by November 25, 2020

Hi Daniel -- K-Maps really are a useful tool -- re having "9" with LED (d) and "6" with LED (a), it would certainly be possible to do this -- I just used the same values as shown for the Texas Instruments 7400-series BCD to 7-Segment decoders (and didn't implement the last 6 codes).

With regard to sinking current rather than driving it -- you could go two ways -- if I were doing this from the ground up, then I would have drawn my truth table with active low outputs (basically swap the output 0s for 1s and 1s for 0s in my existing table) and performed the K-map optimization on the result.

Note that I typically populate my K-maps with the 1s from the truth table and then extract my equations in sum-of-product form (where & (AND) is the product operator and | (OR) is the sum operator; that is, (a & b) | (c & d) | (e & f) etc. However, you can also populate a K-map with the 0s from the truth table and extract the equations in a product-of-sums form.

However, if I'd already done all the work for active-high outputs (as I have done) and then I decided I wanted to use active low, I would just invert the outputs, which means swapping the OR gates for NOR gates.