FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > FPGA

FPGA comp.arch.fpga newsgroup (usenet)

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 01-15-2004, 10:23 AM
guille
Guest
 
Posts: n/a
Default 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 With Quote
  #2 (permalink)  
Old 01-15-2004, 10:51 AM
jim granville
Guest
 
Posts: n/a
Default Re: Gray encoding for FSM



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

Reply With Quote
  #3 (permalink)  
Old 01-15-2004, 10:43 PM
Andy Peters
Guest
 
Posts: n/a
Default Re: Gray encoding for FSM

[email protected] (guille) wrote in message news:<[email protected] 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
Reply With Quote
  #4 (permalink)  
Old 01-16-2004, 08:48 AM
Thomas Stanka
Guest
 
Posts: n/a
Default Re: Gray encoding for FSM

[email protected] (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
Reply With Quote
  #5 (permalink)  
Old 01-16-2004, 11:30 AM
guille
Guest
 
Posts: n/a
Default Re: Gray encoding for FSM

jim granville <[email protected]> wrote in message news:<[email protected]>...
> 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!
Reply With Quote
  #6 (permalink)  
Old 01-16-2004, 11:30 AM
guille
Guest
 
Posts: n/a
Default Re: Gray encoding for FSM

That helps a lot, thanks!

guille

[email protected] (Thomas Stanka) wrote in message news:<[email protected] com>...
> [email protected] (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

Reply With Quote
  #7 (permalink)  
Old 01-16-2004, 10:11 PM
jim granville
Guest
 
Posts: n/a
Default Re: Gray encoding for FSM

guille wrote:
> jim granville <[email protected]> wrote in message news:<[email protected]>...
>
>>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

Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT +1. The time now is 10:22 PM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved