Posts Tagged ‘K-Maps’


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.