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

## Non-Power-of-2 Gray Counter Design

June 9, 2008

So… you want to design a counter with a cycle which is different than a power of 2. You would like to use a Gray counter because of its advantages and just because it is simply beautiful, but alas, your cycle length is not a power of two – what to do?
This post will try to give you a sort of recipe of how to design such a non-power-of-2 Gray counter and the reasoning behind.

First, if your cycle length is an odd number, you are in trouble since this is just not possible to construct a counter with the Gray properties and with an odd cycle length. A simple way to see why it is so, is to notice that a Gray counter changes its parity with each count because only one bit changes at a time.
This naturally means that the parity toggles, but since we have an odd number of states and if we started with even parity – the last state will also have odd parity, and when we wrap around the parity won’t change! Assuming that the first and last states are different, this means that 2 bits must change at a time, thus contradicting the Gray hypothesis.

OK, so we limited ourselves to an even amount of states, is it possible now? It is! We could ask our friend Google and come up with some info and even some patents, but the best discussion on the subject that I found was written by Clive Maxfield here.

When approaching this problem, what (hopefully) should immediately struck us, is that we have to somehow use the reflection property of the Gray code (This method among others is discussed by Clive as well). Let’s take a deeper look at the 4-bit Gray code below.

The pairs of states which have identical distance from the axis of reflection are only different by their MSB. This in turn, means that we could eliminate pairs-at-a-time around the axis of reflection, and arrive to our desired number of states for the counter. Moreover, we notice that the (n-1) LSBs count up to a certain value then change direction and count down again. This property remains true even if we remove any amount of pairs around the axis of reflection.

What we have to do now, is to find this “switching value”, when we reach it on the up-count, toggle the direction bit – which is also our MSB, and block the (n-1) LSBs Gray counter for this direction switch cycle (otherwise 2 bits would change). We now count down to the initial state (all zeros). When we reach it, we again have to switch direction and block the counter and so on ad infinitum.

We can use the modular up/down Gray counter I described here, here and here. for our (n-1) LSBs. We have to find a priori the “switching value”, which is the (n-1) bit Gray value of our number of counter states divided by 2. For Example, if you want a 10 state Gray counter then: 10/2 = 5, therefore we need the 5th Gray value of a normal 3 bit Gray code, which turns out to be 110
The rest of the circuit is depicted in the figure below:

It is important to see that we use the minimal possible memory elements required for the Gray counter (i.e. no extra states to remember or pipeline) and that during “direction switching” we gate the clock for the (n-1) LSBs up/down Gray counter using an ordinary clock gate construct.
If we look carefully we see that the “direction switching” logic is basically a mux structure with the select being the direction bit.

A timing diagram of the above circuit for a 10 state Gray counter is also depicted below for clarity.

## FSM State Encoding – More Switching Reduction Tips

September 4, 2007

I promised before to write some words on reducing switching activity by cleverly assigning the states of an FSM, so here goes…

Look at the example below. The FSM has five states “A”-”E”. Most naturally, one would just sequentially enumerate them (or use some enumeration scheme given by VHDL or Veriog – which is easier for debugging purposes).
In the diagram the sequential enumeration is marked in red. Now, consider only the topology of the FSM – i.e. without any reference to the probability of state transitions. You will notice that the diagram states (pun intended) in red near each arc the amount of bits switching for this specific transition. For example, to go from state “E” (100) to state “B” (001), two bits will toggle.

But could we choose a better enumeration scheme that will reduce the amount of switching? Turns out that yes (don’t tell anybody but I forced this example to have a better enumeration ). If you look at the green state enumeration you will clearly see that at most only one bit toggles for every transition.

If you sum up all transitions (assuming equal probability) you would see that the green implementation toggles exactly half the time as the red. An interesting point is that we need only to consider states “B” – “E”, because once state “A” is exited it can never be returned to (this is sometimes being referred to as “black hole” or “a pit”).

The fact that we chose the states enumeration more cleverly doesn’t only mean that we reduced switching in the actual flip-flops that hold the state itself, but we also reduce glitches/hazards in all the combinational logic that is dependent on the FSM! The latter point is extremely important since those combinational clouds can be huge in comparison to the n flops that hold the state of the FSM.

The procedure on choosing the right enumeration deserve more words but this will become a too lengthy post. In the usually small FSMs that the average designer handles on a daily basis, the most efficient enumeration can be easily reached by trial and error. I am sure there is somewhere some sort of clever algorithm that given an FSM topology can spit out the best enumeration. If you are aware of something like that, please send me an email.

## Puzzle #5 – Binary-Gray

June 12, 2007

Assuming you have an n-bit binary counter, made of n identical cascaded cells, which hold the corresponding bit value. Each of the binary cells dissipates a power of P units only when it toggles.
You also have an n-bit Gray counter made of n cascaded cells, which dissipates 3P units of power per cell when it toggles.

You now let the counters run through an entire cycle (2^n different values) until they return to their starting position. Which counter burns more power?

## Synchronization of Buses

June 1, 2007

I know, I know, it is common knowledge that we never synchronize a bus. The reason being the uncertainty of when and how the meta-stability is resolved. You can read more about it in one of my previous posts.

A cool exception of when bus synchronization would be safe, is when you guarantee that:

1. On the sender side, one bit only changes at a time – Gray code like behavior
2. On the receiver (synchronized bus) side, the sampling clock is fast enough to allow only a single bus change

Just remember that both conditions must be fulfilled.

It is important to note that this can still be dangerous when the sender and receiver have the same frequency but phase is drifting! why???

Are there any other esoteric cases where one could synchronize a bus? comments are welcome!

## Counting in Gray – Part III – Putting Everything Together

May 14, 2007

In the last post we built the basis for our Gray counter implementation. In this post we will combine all observations and create a “Gray bit cell” which could be instantiated as many times as one wishes to create Gray counters which count up or down and are of any desired length.

As mentioned before, the basic idea is to build a “Gray bit cell”. Naturally it has a single bit output, but the cell also has to get the information from all previous cells whether or not a pattern was identified and whether it has to toggle or not.

The latter point reminds us that we will have to use T-Flops for the implementation, since the patterns we observed in the previous post only concern when a certain Gray bit toggles and not its absolute value. The most basic implementation of a T-Flop is presented on the figure on the right.

The abstract view of the Gray cell is presented to the left. Both the clock and reset inputs have been omitted. The cell inputs and outputs are:

• Q_o – Gray value of the specific bit (n)

• Q_i – The previous – n-1 – Gray bit value
• Z_i – All Gray bits n-2 down to 0 are “0″
• Z_o – All Gray bits n-1 down to 0 are “0″
• parity – Parity bit – or more correctly inverted parity
• up_n_dn – If “1″ count up, if “0″ count down
• enable – enable counting
• Two implementations of the Gray cell are depicted below, the left one being more intuitive than the right, but the right one is more compact. Both implementations are logically identical.

All that is left now is to see how to connect the Gray cells in series to produce a Gray up/down counter.
In the final picture the Gray cells were connected to form a Gray counter. Notice that some cells are connected in a special way:

• Cell 0 – Q_i and Z_i are both connected to “1″, The parity input is inverted and Z_o left unconnected
• Cell 1 – Z_i connected to “1″
• Cell n (MSB) – Q_i is connected to “1″, Z_o left unconnected
• A few more words on the parity bit. In the given implementation it is generated by a normal D-Flop with its Qbar output connected to its D input. The same functionality can be achieved without this extra D-Flop, by using an Xor tree on the outputs of the Gray counter – remember our first observation from the previous post? the parity changes with each count.

That concludes this series of posts on Gray counters, but don’t worry I promise there will be more interesting stuff coming on Gray codes.

## Counting in Gray – Part II – Observations

May 13, 2007

In the last post we discussed the different approaches, their advantages and disadvantages in terms of implementation, design requirements etc. We finished with the promise to have a solution for counting in Gray code, with registered outputs and which is could easily be described in HDL.

In this post we will observe some interesting facts concerning mirrored Gray codes, which in turn will lead us to our implementation.

Let’s start.

One of the most important and basic things we can see when observing Gray codes, is that with each increment or decrement the parity of the entire number changes. This is pretty obvious since each time only a single bit changes.

The Next observation is the “toggling period” of each of the bits in Gray representation. Bit 0, or the LSB has a “toggle period” of 2 – i.e. it flips each 2 counts. Bit 1 (one to the left of the LSB) has a “toggle period” of 4. In General with each move towards the MSB side, the toggle period doubles. An Exception is the MSB which has the same toggle period has the bit to its immediate right.
The top figure on the right demonstrates this property for a 5 bit Gray code.

The reason why this is true can be easily understood if we consider the way mirrored Gray codes are being constructed (which I assume is well known). Notice that this fact just tells us only the toggle period of each bit, not when it should toggle! To find this out, we will need our third observation.

Let us now look at when each bit flips with respect to its position. In order to help us, we will have to recall our first observation – parity changes with each count. The bottom figure on the right reveals the hidden patterns.

In General: Gray bit n will toggle in the next cycle, when the bit to its immediate right is “1″ and all the other bits to its right are 0 – or in other words a 100…00 pattern
The only exception is the MSB which toggles when all the bits to its right except the one to its immediate right are “0″ – or a X00…00 pattern

sounds complicated? look in the picture again, the pattern will just pop out to you.

You can take my word for it or check for yourself, anyways the rules for counting backwards (or down), in Gray, are:

The LSB toggles when the parity bit is “0″
For all the other bits: Gray bit n will toggle in the next cycle, when the bit to its immediate right is “1″, all the other bits to its right are 0 and the parity bit is “1″ – or in other words a 100…01 pattern

On the next post we will see how to use those observations to create a simple “gray bit cell”, which will be used as our building block for the final goal – the up/down Gray counter.

## Counting in Gray – Part I – The Problem

May 10, 2007

I love Gray codes, there I said it. I love to try to find different and weird applications for them.
But Gray codes are one of those things where most designers heard of and know the principle they use – but when coming to implement a circuit based on Gray codes, especially when simple arithmetic is involved, things get complicated for them.

I don’t really blame them since that stuff can get relatively tricky. Maybe it is best to show with an example…
This paper is a must read for any digital designer trying to design an asynchronous FIFO. All the major issues, corner cases and pitfalls are mentioned there, and I just can’t recommend it enough.

But… what caught my attention was the implementation of the Gray counters in the design (page 2, section 2.0). Before we get into what was written, maybe a presentation of the problem is in place. Counting (i.e. only +1 or -1 operations on a vector is considered) in binary is relatively straight forward. We all learned to do this, and use it. The problem is how do you count in “Gray code” – i.e. given the 3-bit gray code number 111, what is the next number in line? (answer: 101)

The figure below shows the Gray code counting scheme for 3-bit “mirrored” Gray code (the most commonly used)

Look at any line, can you figure out what will be the next line based only on the line you look at??? If you think you know try figuring out what comes after 11011000010 ???

There are 2 very common approaches to solve this problem:

1. Convert to binary –> do a “+1″ –> convert back to Gray
2. Use a Look-up-Table to decode the next state

Let’s look through them one at a time.
Option 1, can be implemented in principle in two different ways (the plot thickens…)

The implementation on the left has the big advantage that the Gray output is registered, i.e. the values stored in the Flip-Flop are truly Gray. This is necessary when the output is used in an asynchronous interface (e.g. as a FIFO pointer).
The implementation on the right is faster though, with the disadvantage of the output being combinational.
The advantage of both implementations is that they are relatively compact to describe in HDL, even for wide counters and very flexible – e.g. one can add a “-1″ functionality quite easily.

Option 2, is basically a big LUT that describes the next Gray state of the counter.
The outputs will be truly registered, the implementation relatively fast, but very tedious to describe in HDL and prone to errors. just imagine a 7-bit Gray counter implemented as a big case statement with 128 lines. Now imagine that you would want to add a backward counting (or “-1″) operation.

The natural question asked is, isn’t there a better implementation that gives us the best of both worlds? Registered outputs, fast and easily described in HDL. The answer is a big “YES”, and I will show how to do it on my next post. That implementation will be even easy enough for entering it in schematic tools and using it in a full-custom environment!

hold on…