Gray encoding for FSM

[guille]

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

 

[jim granville]

guille wrote:

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.

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

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?

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

 

[Andy Peters]

guillerodriguez@terra.es (guille) wrote in message news:<5d891e95.0401150123.31c7af38@posting.google.com>...

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.

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

-a

 

[Thomas Stanka]

guillerodriguez@terra.es (guille) wrote:

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?

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

 

[guille]

jim granville <no.spam@designtools.co.nz> wrote in message news:<ijtNb.17319$ws.2066401@news02.tsnz.net>...

guille wrote:

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.

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

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?

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?

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.

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

Thanks!

 

[guille]

That helps a lot, thanks!

guille

usenet_10@stanka-web.de (Thomas Stanka) wrote in message news:<ef424d2c.0401152348.34ad50e5@posting.google.com>...

guillerodriguez@terra.es (guille) wrote:
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?

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

 

[jim granville]

guille wrote:

jim granville <no.spam@designtools.co.nz> wrote in message news:<ijtNb.17319$ws.2066401@news02.tsnz.net>...

guille wrote:


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.

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


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?

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.

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?

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.


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

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