1. Home
  2. Field-Programmable Gate Arrays
  3. Gray encoding for FSM

Gray encoding for FSM

Hello all,

I have a FSM with 6 states: IDLE, and S0-S5. Transitions are synchronized with the system clock, but next state might be determined by signals which are asynchronous to that clock.

The FSM is normally at state IDLE. If certain signals are active, it will go from IDLE to S0, then go through some intermediate states, and finally back to IDLE. Here's a list of possible transitions:

Current state Possible next states

------------- -------------------- IDLE IDLE, S0 S0 S1 S1 S2, IDLE S2 S3, IDLE S3 S4, IDLE S4 S4, S5, IDLE S5 IDLE

I would like to use Gray encoding for this FSM but I'm not sure how it should be done. Using Gray encoding is straightforward for things like counters and such where there's only one possible next state for each current state. However, is it possible in a case like this?

Thanks, Guillermo Rodriguez

Reply to
guille
Loading thread data ...

Sounds like thin ice. Can you not sync these to the opposite clock edge ?

A formal Gray code may be impossible, but you may be able to find a 'single bit change' pattern using pencil and paper. It can also help, if you allow IDLEa, IDLEb,(etc) for example - these are extra states added purely to ensure single-bit state jumps can be met.

-jg

Reply to
jim granville

Those asynchronous signals should be synchronized to the clock, lest you get into troubles!

-a

Reply to
Andy Peters

Draw a picture of your FSM. Now try to color each state with two rules:

  1. no adjacent state shall have the same color (A and B shall be adjacent iff theres a edge from state A to state B)
  2. use no unused color when possible

If you come along with two colors, your statemachine fits perfect into gray code. Else you could start inserting states unless you need only two colors. There are two possibilities for inserting states:

  1. null states without funktion (these will anyway delay your fsm)
  2. Split a state in two states, that will do the work.

Another possibility is to use gray as good as possible, but to break the rules for some seldom used transitions.

bye Thomas

Reply to
Thomas Stanka

Actually the signals are being double clocked (to the same clock edge) to synchronize them and avoid metastables. So the actual implementation would look more or less like this:

clk

-----------+-----------+ | | +-----+ +-----+ sig | | | | sig1

--------|D Q|-----|D Q|-------- +-----+ +-----+

And sig1 is the signal that the FSM looks at to determine which state to go next. Is it a problem if the signal is sycnrhonized to the same clock edge?

I assume that this is still needed even after adding the double clocking described above, right?

Thanks!

Reply to
guille

That helps a lot, thanks!

guille

Reply to
guille

No - the resaon I suggested the 'other edge', is sometimes the latency matters, and other edge is one way to make that 'half-clock'. What you have here is fully sync signals.

No - once you have sync'd any signals that may have violated Tsu, you can generate any state pattern you like, including one where multiple bits change. Provided all downstream decisions are made by FF's ( not async decoded) you do not need actually Gray code.

The real danger of async signals -> Two bit changes is aperture skew, where the precise capture time of two FFs is not exactly the same. Then only one bit may toggle, taking you into unwanted state territory.

-jg

Reply to
jim granville

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.