Problem with Grey Code

Thread Starter

bitflogger

Joined Apr 6, 2010
2
Under "Logic simplification with Karnaugh maps", it is suggested that you can draw bigger K-maps by using Grey Code. The example given is 000, 001, 011, 010, 110, 111, 101, 100. It looks good because each bit pattern has adjacent patterns that differ by only one bit, including wrap-around.

I had a professor in college who used 3-bit Grey Code.

Here is why it is wrong: Take 000, it clearly should be adjacent to 001, 100, AND 010.

i.e. using the Grey Code, above, you cannot draw union 000,010 = 0x0.

On a 2-D axis, using 3 bits, you will only have 2 of 3 possible adjacent relations to each bit pattern. What this means, and I proved it to myself back in 1979 or so, is that some problems will be solved nicely, some will not. With 4-bit Grey Code, you will be losing 2 out of 4, or 1/2 of the possible adjacent relations. It was not until the 1990s that I realized what my professor had done wrong.

You can only go above 4 bits (2-bit axis x 2-bit axis) using a representation, like x01x00x0101, or bCefhIjK.
 
Last edited:

Thread Starter

bitflogger

Joined Apr 6, 2010
2
After some more thought, I see I have changed the definition of a K-map.
Instead of "adjacent squares must differ from each other by one bit", I have "All squares different by one bit must be adjacent".
 
Top