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.

## Karnaugh map.

**Moderators:** phlip, Moderators General, Prelates

### 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...

cheers for the answer

-V

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...

cheers for the answer

-V

### 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.

### 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.

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 2

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.

In the normal binary counting, each time you count you toggle the lowest n bits, where 2

^{n-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)⚠);}

- 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.

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.

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

### Who is online

Users browsing this forum: No registered users and 7 guests