Is there a 'normal' way to write down K-maps with more than 4 inputs? I've just written some code to verify logic which implements n-input K-maps. The user has to initialise a square or rectangular array with the function output data, so I did a quick Google search to find out how people wrote their grids. On the net, at least, it looks like the reflected binary Gray version is the normal way to do it. It's not what I was used to, but I assumed that most people would use it. Now that I've done it, though, I'm not so sure. For a 5-input function, for example, a reflected binary Gray map looks like this: // /----- A -----\ // /- B -\ /- B -\ // --------------- --------------- // | x | x | x | x | | x | x | x | x | // |---------------| |---------------| // | x | x | x | x |\ | x | x | x | x |\ // --------------- E --------------- E // / | x | x | x | x |/ / | x | x | x | x |/ // D |---------------| D |---------------| // \ | x | x | x | x | \ | x | x | x | x | // --------------- --------------- // \- C -/ \- C -/ A is the MS input, and E is the LS input. The 8 columns have left-to-right ABC codings of 000, 001, 0011, and so on. The 4 rows are coded 00, 01, 11, 10 from top-to-bottom. The coding I've used historically is different. It's still Gray-coded, of course, but it looks like this (actually, I assign A, B, C, D, E arbitrarily, but I've adjusted it to be mostly consistent with the reflected version): // /----- A -----\ // /- B -\ /- B -\ // --------------- --------------- // | x | x | x | x | | x | x | x | x | // |---------------| |---------------| // | x | x | x | x |\ | x | x | x | x |\ // --------------- E --------------- E // / | x | x | x | x |/ / | x | x | x | x |/ // D |---------------| D |---------------| // \ | x | x | x | x | \ | x | x | x | x | // --------------- --------------- // \- C -/ \- C -/ The problem with the reflected version is that it's not easy to (manually) minimise over the 2 grids, because B has moved. In the second version, you can place the two grids over each other to get your minterms. The difference is more significant for 6 variables - it's not obvious how to minimise the first version, but the second version easily turns into a 3D toroid and you can actually visualise the groups. Note that I'm not talking about machine minimisation - this is just how a human would write and visualise a 5- or 6-input map, and how they'd want to write down the function output data. If you use K-maps, which version do you prefer for 5- and 6-input functions? I clearly have to use the reflected version for more than 6 inputs; it's only 5 and 6 which are problems. Thanks - Evan
Standard forms for Karnaugh maps?
Started by ●June 27, 2008
Reply by ●June 27, 20082008-06-27
On 27 Jun, 18:09, Evan Lavelle <nos...@here.com> wrote:> Is there a 'normal' way to write down K-maps with more than 4 inputs? > > I've just written some code to verify logic which implements n-input > K-maps. The user has to initialise a square or rectangular array with > the function output data, so I did a quick Google search to find out > how people wrote their grids. On the net, at least, it looks like the > reflected binary Gray version is the normal way to do it. It's not > what I was used to, but I assumed that most people would use it. > > Now that I've done it, though, I'm not so sure. For a 5-input > function, for example, a reflected binary Gray map looks like this: > > // =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/----- =A -----\> // =A0 =A0 =A0 =A0 =A0 =A0 /- B -\ =A0 =A0 =A0 =A0 =A0 =A0/- B -\ > // =A0 =A0 --------------- =A0 =A0 =A0 =A0 =A0 =A0--------------- > // =A0 =A0| x | x | x | x | =A0 =A0 =A0 =A0 =A0| x | x | x | x | > // =A0 =A0|---------------| =A0 =A0 =A0 =A0 =A0|---------------| > // =A0 =A0| x | x | x | x |\ =A0 =A0 =A0 =A0 | x | x | x | x |\ > // =A0 =A0 --------------- =A0E =A0 =A0 =A0 =A0 --------------- =A0E > // =A0/ | x | x | x | x |/ =A0 =A0 =A0 / | x | x | x | x |/ > // D =A0|---------------| =A0 =A0 =A0 D =A0|---------------| > // =A0\ | x | x | x | x | =A0 =A0 =A0 =A0\ | x | x | x | x | > // =A0 =A0 --------------- =A0 =A0 =A0 =A0 =A0 =A0--------------- > // =A0 =A0 =A0 =A0 \- C -/ =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0\- C -/ > > A is the MS input, and E is the LS input. The 8 columns have > left-to-right ABC codings of 000, 001, 0011, and so on. The 4 rows are > coded 00, 01, 11, 10 from top-to-bottom. > > The coding I've used historically is different. It's still Gray-coded, > of course, but it looks like this (actually, I assign A, B, C, D, E > arbitrarily, but I've adjusted it to be mostly consistent with the > reflected version): > > // =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/----- =A -----\> // =A0 =A0 =A0 =A0 =A0 =A0 /- B -\ =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 ==A0/- B -\> // =A0 =A0 --------------- =A0 =A0 =A0 =A0 =A0 =A0--------------- > // =A0 =A0| x | x | x | x | =A0 =A0 =A0 =A0 =A0| x | x | x | x | > // =A0 =A0|---------------| =A0 =A0 =A0 =A0 =A0|---------------| > // =A0 =A0| x | x | x | x |\ =A0 =A0 =A0 =A0 | x | x | x | x |\ > // =A0 =A0 --------------- =A0E =A0 =A0 =A0 =A0 --------------- =A0E > // =A0/ | x | x | x | x |/ =A0 =A0 =A0 / | x | x | x | x |/ > // D =A0|---------------| =A0 =A0 =A0 D =A0|---------------| > // =A0\ | x | x | x | x | =A0 =A0 =A0 =A0\ | x | x | x | x | > // =A0 =A0 --------------- =A0 =A0 =A0 =A0 =A0 =A0--------------- > // =A0 =A0 =A0 =A0 \- C -/ =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0\- C -/ > > The problem with the reflected version is that it's not easy to > (manually) minimise over the 2 grids, because B has moved. In the > second version, you can place the two grids over each other to get > your minterms. The difference is more significant for 6 variables - > it's not obvious how to minimise the first version, but the second > version easily turns into a 3D toroid and you can actually visualise > the groups. Note that I'm not talking about machine minimisation - > this is just how a human would write and visualise a 5- or 6-input > map, and how they'd want to write down the function output data. > > If you use K-maps, which version do you prefer for 5- and 6-input > functions? I clearly have to use the reflected version for more than 6 > inputs; it's only 5 and 6 which are problems. > > Thanks - > > EvanI didn't think that anyone still used Karnaugh maps for programmable logic. Leon
Reply by ●June 27, 20082008-06-27
Evan Lavelle wrote:> Note that I'm not talking about machine minimisation - > this is just how a human would write and visualise a 5- or 6-input > map, and how they'd want to write down the function output data. > > If you use K-maps, which version do you prefer for 5- and 6-input > functions? I clearly have to use the reflected version for more than 6 > inputs; it's only 5 and 6 which are problems.Is this homework ? The design is not usually going to stay on paper, it has to end up in silicon. That makes most of this irrelevent. -jg
Reply by ●June 28, 20082008-06-28
On Sat, 28 Jun 2008 09:00:03 +1200, Jim Granville <no.spam@designtools.maps.co.nz> wrote:>Is this homework ?I did my last "homework", as you put it, 28 years ago, in Quantum Mechanics.>The design is not usually going to stay on paper, it has to >end up in silicon. That makes most of this irrelevent.There's a common misconception that K-maps are/were only used for minimisation, so they're now irrelevant. Actually, K-maps are probably the most fundamental tool for the design, specification, and analysis of combinatorial logic. They're also independent of the implementation, which makes them ideally suited for verification of the same circuits. They're about 'what', not 'how'. An HDL description, on the other hand, is exactly the opposite - 'how', not 'what'. As I said originally, this is about verification. The fact that the K-map may or may not end up in silicon is "irrelevant". Leon asked whether anyone still used K-maps for programmable logic; a good question, without being condescending. I don't imagine many people use them to fill up FPGAs. On the other hand, I'm sure there are still people in this NG who do digital logic design, and some of them may occasionally even do non-trivial combinatorial logic.
Reply by ●June 28, 20082008-06-28
Evan Lavelle wrote:> On Sat, 28 Jun 2008 09:00:03 +1200, Jim Granville > <no.spam@designtools.maps.co.nz> wrote: > > >>Is this homework ? > > > I did my last "homework", as you put it, 28 years ago, in Quantum > Mechanics. > > >>The design is not usually going to stay on paper, it has to >>end up in silicon. That makes most of this irrelevent. > > > There's a common misconception that K-maps are/were only used for > minimisation, so they're now irrelevant. Actually, K-maps are probably > the most fundamental tool for the design, specification, and analysis > of combinatorial logic. They're also independent of the > implementation, which makes them ideally suited for verification of > the same circuits. They're about 'what', not 'how'. An HDL > description, on the other hand, is exactly the opposite - 'how', not > 'what'. As I said originally, this is about verification. The fact > that the K-map may or may not end up in silicon is "irrelevant".I'm still trying to get a handle on the 'why' ?> Leon asked whether anyone still used K-maps for programmable logic; a > good question, without being condescending. I don't imagine many > people use them to fill up FPGAs. On the other hand, I'm sure there > are still people in this NG who do digital logic design, and some of > them may occasionally even do non-trivial combinatorial logic.Do you mean actual FET level logic ? Even at the lowest combinatorial logic, I still look at the tools output, and often they do eqn invert, or do D/T/XOR synthesis swapping in order to pack things more efficently. -jg
Reply by ●June 28, 20082008-06-28
On Jun 28, 6:07 am, Jim Granville <no.s...@designtools.maps.co.nz> wrote:> Evan Lavelle wrote: > > On Sat, 28 Jun 2008 09:00:03 +1200, Jim Granville > > <no.s...@designtools.maps.co.nz> wrote: > > >>Is this homework ? > > > I did my last "homework", as you put it, 28 years ago, in Quantum > > Mechanics. > > >>The design is not usually going to stay on paper, it has to > >>end up in silicon. That makes most of this irrelevent. > > > There's a common misconception that K-maps are/were only used for > > minimisation, so they're now irrelevant. Actually, K-maps are probably > > the most fundamental tool for the design, specification, and analysis > > of combinatorial logic. They're also independent of the > > implementation, which makes them ideally suited for verification of > > the same circuits. They're about 'what', not 'how'. An HDL > > description, on the other hand, is exactly the opposite - 'how', not > > 'what'. As I said originally, this is about verification. The fact > > that the K-map may or may not end up in silicon is "irrelevant". > > I'm still trying to get a handle on the 'why' ? > > > Leon asked whether anyone still used K-maps for programmable logic; a > > good question, without being condescending. I don't imagine many > > people use them to fill up FPGAs. On the other hand, I'm sure there > > are still people in this NG who do digital logic design, and some of > > them may occasionally even do non-trivial combinatorial logic. > > Do you mean actual FET level logic ? > Even at the lowest combinatorial logic, I still look at the tools > output, and often they do eqn invert, or do D/T/XOR synthesis swapping > in order to pack things more efficently. > > -jgThe last time I did Karnaugh maps was in an attempt to get 8b10b encoding into a CPLD. In this case I also had more than 4 inputs and I have to say that human interaction with such maps is not easy no matter how you slice it. This is like trying to envisage objects with more than 3 dimensions. However to answer the original question, the fact that 'B' lines up left in one map and right in the other is useful if you view them side-by-side as in your post, rather than stacked up as in a 3D viewer. Still an explanation of the end use of this would be interesting... Regards, Gabor
Reply by ●June 28, 20082008-06-28
On Sat, 28 Jun 2008 09:00:28 +0100, Evan Lavelle wrote:> On Sat, 28 Jun 2008 09:00:03 +1200, Jim Granville > <no.spam@designtools.maps.co.nz> wrote: > >>Is this homework ? > > I did my last "homework", as you put it, 28 years ago, in Quantum > Mechanics. > >>The design is not usually going to stay on paper, it has to end up in >>silicon. That makes most of this irrelevent. > > There's a common misconception that K-maps are/were only used for > minimisation, so they're now irrelevant. Actually, K-maps are probably > the most fundamental tool for the design, specification, and analysis of > combinatorial logic. They're also independent of the implementation, > which makes them ideally suited for verification of the same circuits. > They're about 'what', not 'how'. An HDL description, on the other hand, > is exactly the opposite - 'how', not 'what'. As I said originally, this > is about verification. The fact that the K-map may or may not end up in > silicon is "irrelevant". > > Leon asked whether anyone still used K-maps for programmable logic; a > good question, without being condescending. I don't imagine many people > use them to fill up FPGAs. On the other hand, I'm sure there are still > people in this NG who do digital logic design, and some of them may > occasionally even do non-trivial combinatorial logic.It's been 30 years since I've used Karnaugh maps, they were useful when the 7400 was state of the art and every gate counted. In that era logic was necessarily simple so a tool that could minimize a four input equation was helpful. However as you must have figured out by now, Karnaugh maps don't scale well. When the first widely used programmable logic was introduced, PALs, the Karnaugh maps largely disappeared. PALs had to many terms, 20, for a Karnaugh map to be usable. When FPGAs were introduced they were based on 4 input LUTs. The LUT is universal logic so there is no point in doing any minimization on the scale that Karnaugh maps are useful. What's more modern synthesis tools handle logic minimization on a scale that is simply not possible by a human being. The kinds of optimizations that are still done by hand are also in a class that is outside of the domain of Karnaugh maps, to be specific the kind of things that are done by hand are deciding what terms can be moved to a synchronous set or reset instead of the main equation, or figuring out what portion of an equation can be calculated in an earlier pipeline stage. Those are time optimizations not logic optimizations, i.e. they require knowledge of what's known when and what's nearby and what's far away.
Reply by ●June 28, 20082008-06-28
"General Schvantzkopf" <schvantzkopf@yahoo.com> wrote in message news:y-2dnZJNvsTS8vvVnZ2dnUVZ_sjinZ2d@comcast.com...> On Sat, 28 Jun 2008 09:00:28 +0100, Evan Lavelle wrote: > >> On Sat, 28 Jun 2008 09:00:03 +1200, Jim Granville >> <no.spam@designtools.maps.co.nz> wrote: >><snip>> It's been 30 years since I've used Karnaugh maps, they were useful when > the 7400 was state of the art and every gate counted. In that era logic > was necessarily simple so a tool that could minimize a four input equation > was helpful.All very true, but Evan's question was explicitly targetted toward people who USE K-maps ("If you use K-maps, which version do you prefer..." from the original post) and his reasons had to do with verification not design (later post). I don't think he was looking for responses from people who don't use K-maps while they are not doing verification. KJ
Reply by ●June 28, 20082008-06-28
KJ wrote:> "General Schvantzkopf" <schvantzkopf@yahoo.com> wrote in message > news:y-2dnZJNvsTS8vvVnZ2dnUVZ_sjinZ2d@comcast.com... > >>On Sat, 28 Jun 2008 09:00:28 +0100, Evan Lavelle wrote: >> >> >>>On Sat, 28 Jun 2008 09:00:03 +1200, Jim Granville >>><no.spam@designtools.maps.co.nz> wrote: >>> > > <snip> > >>It's been 30 years since I've used Karnaugh maps, they were useful when >>the 7400 was state of the art and every gate counted. In that era logic >>was necessarily simple so a tool that could minimize a four input equation >>was helpful. > > > All very true, but Evan's question was explicitly targetted toward people > who USE K-maps ("If you use K-maps, which version do you prefer..." from the > original post) and his reasons had to do with verification not design (later > post).To answer that question, the Logic minimisation I use, is that built into the tools, which will include the tools version of K-Maps, and others as well. ie the REPORT files are closely scrutinised. It is common to look at the tool output, and recode the source, and sometimes we have taken one tools output, and pasted into another as source code. Sometimes, the choices made within the tools surprises, and sometimes it disappoints.... Where the tools have a blind spot is in 'node creation' to reduce total mapped logic (at the expense of some speed). Understandable, as that is a LOT more variables in the air. Sometimes the designer has to help there. It's a matter of matching the degrees of freedom, to the tools IQ. In Xilinx flows, fastest and smallest switches sometimes seem to work backwards :) -jg
Reply by ●June 28, 20082008-06-28
On Jun 27, 10:09 am, Evan Lavelle <nos...@here.com> wrote:> Is there a 'normal' way to write down K-maps with more than 4 inputs? > > I've just written some code to verify logic which implements n-input > K-maps. The user has to initialise a square or rectangular array with > the function output data, so I did a quick Google search to find out > how people wrote their grids. On the net, at least, it looks like the > reflected binary Gray version is the normal way to do it. It's not > what I was used to, but I assumed that most people would use it. > > Now that I've done it, though, I'm not so sure. For a 5-input > function, for example, a reflected binary Gray map looks like this: > > // /----- A -----\ > // /- B -\ /- B -\ > // --------------- --------------- > // | x | x | x | x | | x | x | x | x | > // |---------------| |---------------| > // | x | x | x | x |\ | x | x | x | x |\ > // --------------- E --------------- E > // / | x | x | x | x |/ / | x | x | x | x |/ > // D |---------------| D |---------------| > // \ | x | x | x | x | \ | x | x | x | x | > // --------------- --------------- > // \- C -/ \- C -/ > > A is the MS input, and E is the LS input. The 8 columns have > left-to-right ABC codings of 000, 001, 0011, and so on. The 4 rows are > coded 00, 01, 11, 10 from top-to-bottom. > > The coding I've used historically is different. It's still Gray-coded, > of course, but it looks like this (actually, I assign A, B, C, D, E > arbitrarily, but I've adjusted it to be mostly consistent with the > reflected version): > > // /----- A -----\ > // /- B -\ /- B -\ > // --------------- --------------- > // | x | x | x | x | | x | x | x | x | > // |---------------| |---------------| > // | x | x | x | x |\ | x | x | x | x |\ > // --------------- E --------------- E > // / | x | x | x | x |/ / | x | x | x | x |/ > // D |---------------| D |---------------| > // \ | x | x | x | x | \ | x | x | x | x | > // --------------- --------------- > // \- C -/ \- C -/ > > The problem with the reflected version is that it's not easy to > (manually) minimise over the 2 grids, because B has moved. In the > second version, you can place the two grids over each other to get > your minterms. The difference is more significant for 6 variables - > it's not obvious how to minimise the first version, but the second > version easily turns into a 3D toroid and you can actually visualise > the groups. Note that I'm not talking about machine minimisation - > this is just how a human would write and visualise a 5- or 6-input > map, and how they'd want to write down the function output data. > > If you use K-maps, which version do you prefer for 5- and 6-input > functions? I clearly have to use the reflected version for more than 6 > inputs; it's only 5 and 6 which are problems. > > Thanks - > > EvanEvan, In John F. Wakerly's "Digital Design, Principles and Practices", 4th Edition, pgs 235-236,564 (there is also a 5th edition) uses your second version (the historical one) of 5/6-variable map for logic minimization exercises and FSM synthesis. Of course, mathematically, either one works. alan
