FSM State Encoding - More Switching Reduction Tips

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

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

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

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

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

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

Both have severe disadvantages.

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…