h1

K-Maps Walks and Gray Codes

September 26, 2008

It is this time of year maybe, but I just feel I have to write another post on Gray codes.
We all remember our good friend the K-map (give yourself a point if you knew how to spell the full name, I’m getting it all wrong each time).

By nature of its construction – a “walk” through the map will generate a Gray code, since each cell is different from its adjacent one by a single bit only. Moreover, If we return to the point of origin, we just created a cyclic Gray code.

Draw yourself some 4×4 K-Maps and start playing around with the idea. Remember the K-map is like a toroid, moving off the map to the left pops us back in on the right side and in an analogous way for up/down, right/left and down/up.

Here for instance is the good old “reflected Gray code” which is usually used in many applications which require “a Gray code”. Notice the different toggling cycles of the columns in the outcome sequence – 2-2-2-2-2-2-2-2-2…,4-4-4-4…,8-8… and 8-8….

What if we take a slightly different tour through the map? Notice how now the 3 LSB columns have been rotated.

Let’s try another way to walk the K-map, but maybe this time a little less symmetric (only one axis of symmetry). Look how now the toggling cycles of the columns became rather strange – no more something like 4-4-4-4… but rather 4-2-4-6… and other weird cycles.

What if we need (for whatever strange reason) a non cyclic one? there is nothing easier than that. The start and the end point are not adjacent! which makes the sequence not a cyclic one.

As you see there are many, many different Gray codes around. Sometimes it is just nice playing around with some combinations. For practical implementations, the only time I personally needed the non standard Gray code was when using a non power of 2 Gray code counter – a topic which was already discussed here.

Advertisements

2 comments

  1. detailed explanation sir, thankyou…i was exactly looking 4 this


  2. hi, is there any algorithm to produce these codes for n bits? I want to produce these codes in vhdl program but I do not know the algorithm. what is the category of these codes are there balanced gray codes?



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: