## Karnaugh map.

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

tipo test
Posts: 66
Joined: Sun May 23, 2010 12:15 pm UTC

### Karnaugh map.

http://en.wikipedia.org/wiki/Karnaugh_map

00, 01, 11, 10. What kind of progression is that?

I need it for an exam. Thanks in advance.

Axidos
Posts: 167
Joined: Tue Jan 20, 2009 12:02 pm UTC
Location: trapped in a profile factory please send help

### Re: Karnaugh map.

tipo test
Posts: 66
Joined: Sun May 23, 2010 12:15 pm UTC

### Re: Karnaugh map.

yeah that's it

after a quick google search I've found that people say that it suffices to just memorize the sequence rather than understanding it. gray conversions seem to be quite a pain in the ass...

-V

tipo test
Posts: 66
Joined: Sun May 23, 2010 12:15 pm UTC

### Re: Karnaugh map.

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

### Re: Karnaugh map.

What's so hard about gray codes? So long as you realize that each step is only flipping one bit, the progression seams pretty natural to me. Most aren't going to require you to come up with your own gray code, rather they will present the progression and have you identify what it is.

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

### Re: Karnaugh map.

As long as it's a gray code it will work (and symmetric). The map wraps around.

You just have to keep changing only one bit at a time.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Karnaugh map.

What helped me memorise the Gray code:
In the normal binary counting, each time you count you toggle the lowest n bits, where 2n-1 is the highest power of 2 that's a factor of the number you're counting to. The pattern for n goes 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,etc. Pretty easy pattern to remember (every second value is 1, every second value of the ones left is 2, etc).
For Gray code, the pattern is the same, but you toggle only the nth-last bit each time, instead of all of the last n bits.

To convert an arbitrary index from normal binary counting to Gray code and back:
* The MSB of both numbers is the same
* All of the other bits can be converted back and forth by XORing with the Gray code bit for the next-most-significant bit. So that means for converting binary->Gray you xor each bit with the result you got for the previous bit... for Gray->binary you xor two neighbouring input bits to get an output bit.

It's also easy to write down the complete Gray code sequence in a column... the LSB repeats "0110", the next bit repeats "00111100", the next repeats "0000111111110000", etc.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Karnaugh map.

The gray code for 0 bits is nothing.

The gray code for n bits is the 0 followed by the gray code for n-1 bits in sequence, then by 1 followed by the gray code for n-1 bits backwards in sequence.

{}

{0,1}

0 followed by {0,1}, then 1 followed by {0,1} backwards: {00,01,11,10}

{000,001,011,010,110,111,101,100}

0 followed by {000,001,011,010,110,111,101,100} then 1 followed by backwards {000,001,011,010,110,111,101,100}

0 followed by ( 0 followed by {000,001,011,010,110,111,101,100} then 1 followed by backwards {000,001,011,010,110,111,101,100}
) then 1 followed by backwards ( 0 followed by {000,001,011,010,110,111,101,100} then 1 followed by backwards {000,001,011,010,110,111,101,100} )

You can see how this results in a 1 bit change per cycle. When the MSB doesn't change, the bottom bits are all the lower-sized gray code in order (or backwards). When the MSB changes (at the start/end), you have joined up either the two start or the two end copies of the previous gray code.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.