Karnaugh map.

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

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

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

Karnaugh map.

Postby tipo test » Sun Aug 29, 2010 12:42 am UTC

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.

Postby Axidos » Sun Aug 29, 2010 12:51 am UTC


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

Re: Karnaugh map.

Postby tipo test » Sun Aug 29, 2010 1:44 am UTC

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

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

Re: Karnaugh map.

Postby tipo test » Sun Aug 29, 2010 2:01 am UTC


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

Re: Karnaugh map.

Postby cogman » Sun Aug 29, 2010 5:35 am UTC

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.

Postby mr-mitch » Sun Aug 29, 2010 8:13 am UTC

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.

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

Re: Karnaugh map.

Postby phlip » Tue Aug 31, 2010 8:24 am UTC

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]

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

Postby Yakk » Tue Aug 31, 2010 6:40 pm UTC

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.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 7 guests