Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > VHDL > learning vhdl - state machines

Reply
Thread Tools

learning vhdl - state machines

 
 
Al Muliman
Guest
Posts: n/a
 
      02-12-2009
Trying to find an accepted way to construct state machines in vhdl, I
came upon this:

http://web.engr.oregonstate.edu/~tra...es_in_vhdl.pdf

This is just explanation that I found - I picked this one because it
seems rather nice.

One key point seems to be to avoid latches.

The accepted way to construct state machines would be to have a
synchronous part that turns the next state into the current and a
combinatorial part that determines the next state.

My worry is that the combinatorial part selects a new state with an
encoding that is "more than one bit away" from that of the current state
(or any other state that the combinatorial part might otherwise have
selected) just as the synchronous part flipsflops. In my mind the
current state might become a mix of the two different states that the
combinatorial part had to choose from. Is this worry unfounded?

I am a total fpga noob with a software background mind you.


 
Reply With Quote
 
 
 
 
eliascm eliascm is offline
Member
Join Date: Jan 2009
Posts: 42
 
      02-12-2009
What should happen in your state machine, as in any synchronous design, is the the combinational changes that start on a clock edge will be stable by the time the next clock edge occurs. The only way this wouldn't happen is that the clock period is so short that the combinational logic changes don't become stable between clock edges. If you set your timing contraints correctly, the FPGA synthesis software will indicate whether or not you will have a timing problem.
 
Reply With Quote
 
 
 
 
Al Muliman
Guest
Posts: n/a
 
      02-12-2009
Jonathan Bromley skrev:
> On Thu, 12 Feb 2009 10:54:52 +0100, Al Muliman wrote:
>
>> Trying to find an accepted way to construct state machines in vhdl, I
>> came upon this:
>>
>> http://web.engr.oregonstate.edu/~tra...es_in_vhdl.pdf

>
> I don't have time to get involved in this, but I'm sure you will
> find people telling you that the style recommended in that
> document is not in wide use - rolling a combinational and
> a clocked process into one VHDL (lexical) process is not
> generally accepted style, although the majority of synthesis
> tools now accept it.


So... you would separate the clocked and combinational parts of the
process into a process each and have the two processes share the state
variables like I see in some of the other examples? I thought it seemed
handy to just put the two parts in the same process, but I am definately
trying to learn what is the most accepted practice.

>
>> My worry is that the combinatorial part selects a new state with an
>> encoding that is "more than one bit away" from that of the current state
>> (or any other state that the combinatorial part might otherwise have
>> selected) just as the synchronous part flipsflops. In my mind the
>> current state might become a mix of the two different states that the
>> combinatorial part had to choose from. Is this worry unfounded?

>
> Yes. In VHDL, FFs clocked by the same clock are guaranteed to
> update in a coherent manner. Furthermore, timing analysis
> within the synthesis and implementation tools will ensure
> that this guarantee holds good in the real hardware too.
> If, on reading the post-implementation timing report, you
> see warnings about "hold time violations" then you know
> that these synchronous assumptions are in jeopardy and
> you should start worrying all over again


But... as I understand, the combinational process which selects the next
state is not clocked at all? So any asynchronous input to the
combinational process might potentially result in an undesired state
being clocked past the state FFs due to different delays through the
various part of the combinational process?

Forgive me, but I don't have much (you might say "any") understanding of
what circuitry is generated by the vhdl constructs. I am working on an
example so I can see for myself but it will be a little while till I get
there.

>
> If you write your design in Verilog, then your worry
> most certainly DOES have foundation and you need to
> take great care to code in a way that keeps things OK.


Ok, thanks for the heads up. I will stick with VHDL for now to avoid
more confusion than what already clouds my mind, but I'm sure I'll do
good to keep your comment in mind.

Thank you for your input.
 
Reply With Quote
 
Al Muliman
Guest
Posts: n/a
 
      02-12-2009
On 12-02-2009 17:12, Jonathan Bromley wrote:
> There are single-process styles that do not have any
> combinational outputs, and that's the technique I prefer
> myself.


Okay that was also the solution I had reached on my own before I started
looking for the True Path. But that means states and outputs are
registered, right? Inferred... learning new words here. And more logic,
right? So I might try the combinational approach to see what that could
do for me.

> There is widespread disagreement on this matter,
> and the "correct" answer is strongly affected by what
> you're trying to do with the state machine. I am trying
> very hard here to avoid fomenting religious warfare


I sensed as much, but I am agnostic (and still a bit confused).

> It is
> *essential* that all inputs to such a thing be synchronous, so that
> they exhibit sufficient setup time relative to the clock. Of course,
> it is always possible to meet this requirement by individually
> registering (resynchronizing) each potentially asynchronous input
> into its own register.


Ah good, I am still on track. Thank you.

>
> As you correctly said, a transition whose Hamming distance is
> one (only one bit changes) is immune to problems of this kind,
> apart from the old spectre of metastability. If you can
> code your state machine so that *all* its transitions are
> one-bit only, then you have what's known as a "Gray code".


Yes, I know of gray code and learned today that the enumeration types
typically used for state machines can be "custom encoded":

attribute enum_encoding: string;
attribute enum_encoding of state_type:type is "001 010 011 100 101 110 111";

I suppose the default encoding is 0,1,2,3 etc...

> In the old days when flip-flops were a precious resource,
> writing state machines so that their asynchronous inputs
> affected only Gray transitions was a standard trick.
> Nowadays it's rarely worth the (considerable) bother;
> simply register all the asynchronous inputs.


I recognise the reasoning from software development. It is inevitable
and possibly necessary. But I should learn.

>
>> Forgive me, but I don't have much (you might say "any") understanding of
>> what circuitry is generated by the vhdl constructs.

>
> I think you are amply aware of what is going on.


It's more like a sense of what's going on than actual awareness. A
mixture of what little I recall from the lectures I have attended about
digital design (reduction of karnaugh maps, race conditions and that
sort), the parallels I can draw from software development and the
realization that vhdl is nothing like software at all. What happens when
i write "if rising_edge(clk)" - the inferring that is going an - all
that I have to learn. I have yet to wrap my mind around functions and
procedures in vhdl - that I am definately saving for later. Right now I
just need a lean, mean state machine...

The topic seems a nice angle to get started on vhdl - I recognise state
machines from software development, and they are used all the time... in
vhdl as well as in software I expect.

I do belive you have answered the questions that bothered me the most.
Thank you.
 
Reply With Quote
 
Andy
Guest
Posts: n/a
 
      02-12-2009
On Feb 12, 11:38*am, Al Muliman <(E-Mail Removed)> wrote:
> On 12-02-2009 17:12, Jonathan Bromley wrote:
>
> > There are single-process styles that do not have any
> > combinational outputs, and that's the technique I prefer
> > myself. *

>
> Okay that was also the solution I had reached on my own before I started
> looking for the True Path. But that means states and outputs are
> registered, right? Inferred... learning new words here. And more logic,
> right? So I might try the combinational approach to see what that could
> do for me.


Registered outputs do not always need more logic than combinatorial
ones (except the register itself, which is almost free in most FPGA
architectures). In the simplest case, with one-hot state encoding, the
output is optimized to be just the corresponding bit in the state
register (whether you are using combinatorial or registered outputs)

How you code things depends on how you think. If you think of outputs
being (combinatorially) decoded from states, then to register the
outputs with the same clock-cycle-based timing (on and off at the same
time as the states are), you need to assert the output with every
transition into the state(s) that you would have decoded. That may
mean more coding, but not usually more resulting logic. I've gotten so
used to it, it is second nature to me, and I prefer registered outputs
from state machines (avoids output glitches).

I use a single, clocked process for the state machine and its outputs.
It is immune from latches, requires less coding that two processes,
and simulates more quickly due to modern simulator optimizations
(mostly noticeable in large designs).

I also happen to use VHDL variables inside clocked processes, but
depending on how you think about design, they may help or hinder you.
Variables behave more like SW (updates are not postponed), and thus
the clock-cyclic behavior is easier to understand, but mentally
synthesizing a variable-based description into gates and flops is not
as easy. It suffices to say that a good synthesis tool will reliably
synthesize a clocked process into a circuit that behaves, on a clock-
cyclic basis, like the description simulates, so long as the inputs
are synchronous to the clock. If you prefer to design with gates and
flops, then use signals, and maybe even separate combinatorial and
clocked processes. If you prefer to design with a behavioral
description and let the synthesis tool do the lifting, use variables
in clocked processes.

>
> > There is widespread disagreement on this matter,
> > and the "correct" answer is strongly affected by what
> > you're trying to do with the state machine. *I am trying
> > very hard here to avoid fomenting religious warfare

>
> I sensed as much, but I am agnostic (and still a bit confused).
>
> > It is
> > *essential* that all inputs to such a thing be synchronous, so that
> > they exhibit sufficient setup time relative to the clock. *Of course,
> > it is always possible to meet this requirement by individually
> > registering (resynchronizing) each potentially asynchronous input
> > into its own register.

>
> Ah good, I am still on track. Thank you.
>
>
>
> > As you correctly said, a transition whose Hamming distance is
> > one (only one bit changes) is immune to problems of this kind,
> > apart from the old spectre of metastability. *If you can
> > code your state machine so that *all* its transitions are
> > one-bit only, then you have what's known as a "Gray code".

>


Not necessarily true. First off, it depends on whether you want grey
coding to avoid decoding glitches, or you want grey coding to avoid
erroneous transitions based on asynchronous inputs.

In a gray coded state machine for asynchronous inputs, the most
adjacent destinations, including the current state if applicable,
reachable from the current state is two. If a state machine needs to
transition from one state to one of two different desitination states
(without the possibility of waiting in the current state), those two
destinations must be "adjacent" (hamming distance=1) to each other,
not to the original state. Thus the transitions are not always
adjacent, but the destinations are. This is (was, before registers
became cheap) the typical approach to gray coding state machines:
State driven transitions are always synchronous, and do not require
adjacent transitions. Input-driven transitions may not be synchronous,
and thus need adjacent transitions.

These were reliable techniques, and still are, from a hardware point
of view. But from a design review/audit point of view, separately
synchronizing all state machine inputs is much easier to verify that
it is done correctly. It also renders worrying about adjacent
transitions moot, which then makes other, potentially more efficient
state encodings (e.g. one-hot) usable.

Andy
 
Reply With Quote
 
Mike Treseler
Guest
Posts: n/a
 
      02-12-2009
Al Muliman wrote:

> One key point seems to be to avoid latches.


I avoid latches and fussing with Gray codes
by following a single process template
like the one below.

main : process (clock, reset) is
begin -- for details see http://mysite.verizon.net/miketreseler/

if reset = '1' then -- Assumes synched trailing edge reset pulse
init_regs; -- reg_v := init_c;
elsif rising_edge(clock) then
update_regs; -- reg_v := f(reg_v);
end if;
update_ports;
end process main;

In my code, counters, state machines, shifters, arbiters etc
are all described the same way:
[] a register declaration
[] a procedure to update the register on every rising clock edge.

Each process can cover one or more registers.

-- Mike Treseler
 
Reply With Quote
 
Al Muliman
Guest
Posts: n/a
 
      02-12-2009
On 12-02-2009 19:42, Andy wrote:
> Registered outputs do not always need more logic than combinatorial
> ones (except the register itself, which is almost free in most FPGA
> architectures). In the simplest case, with one-hot state encoding, the
> output is optimized to be just the corresponding bit in the state
> register (whether you are using combinatorial or registered outputs)
>
> How you code things depends on how you think. If you think of outputs
> being (combinatorially) decoded from states, then to register the
> outputs with the same clock-cycle-based timing (on and off at the same
> time as the states are), you need to assert the output with every
> transition into the state(s) that you would have decoded. That may
> mean more coding, but not usually more resulting logic. I've gotten so
> used to it, it is second nature to me, and I prefer registered outputs
> from state machines (avoids output glitches).
>
> I use a single, clocked process for the state machine and its outputs.
> It is immune from latches, requires less coding that two processes,
> and simulates more quickly due to modern simulator optimizations
> (mostly noticeable in large designs).


Ok I think I need an example now...

Is this the newfangled pattern for a fsm:

entity fsm is
port ( clock : in std_logic;
reset : in std_logic;
input : in std_logic);
end fsm;
architecture behavioral of fsm is
type state_type is (THIS, THAT);
begin
process (clock, reset)
variable state : state_type;
begin
if (reset = '1') then
state := THIS;
elsif rising_edge(clock) then
-- register inferred on any variables or signals
-- assigned to inside this elsif section, right?
-- due to the rising_edge...
case state is
-- Can you assign directly to a state variable when it is
-- registered? Or does it mess the case up?
-- Those are things I worry about...
when THIS => if (input = '1') then state := THAT; end if;
when THAT => if (input = '0') then state := THIS; end if;
when others => state := THIS;
end case;
end if;
end process;
end behavioral;

I like it - one process, a private variable; no polluting the namespace.
Sorry, software speak. But is this it then?

>
> I also happen to use VHDL variables inside clocked processes, but
> depending on how you think about design, they may help or hinder you.


That I shall worry about when I start thinking consciously about design.
Currently I am fumbling in the dark.

> Not necessarily true. First off, it depends on whether you want grey
> coding to avoid decoding glitches, or you want grey coding to avoid
> erroneous transitions based on asynchronous inputs.
>
> In a gray coded state machine for asynchronous inputs, the most
> adjacent destinations, including the current state if applicable,
> reachable from the current state is two. If a state machine needs to
> transition from one state to one of two different desitination states
> (without the possibility of waiting in the current state), those two
> destinations must be "adjacent" (hamming distance=1) to each other,
> not to the original state. Thus the transitions are not always
> adjacent, but the destinations are. This is (was, before registers
> became cheap) the typical approach to gray coding state machines:
> State driven transitions are always synchronous, and do not require
> adjacent transitions. Input-driven transitions may not be synchronous,
> and thus need adjacent transitions.
>
> These were reliable techniques, and still are, from a hardware point
> of view. But from a design review/audit point of view, separately
> synchronizing all state machine inputs is much easier to verify that
> it is done correctly. It also renders worrying about adjacent
> transitions moot, which then makes other, potentially more efficient
> state encodings (e.g. one-hot) usable.


Thank you for clarifying further.
 
Reply With Quote
 
Andy
Guest
Posts: n/a
 
      02-12-2009
On Feb 12, 2:18*pm, Al Muliman <(E-Mail Removed)> wrote:
>
> Ok I think I need an example now...
>
> Is this the newfangled pattern for a fsm:
>
> entity fsm is
> * *port ( clock : in *std_logic;
> * * * * * reset : in *std_logic;
> * * * * * input : in *std_logic);
> end fsm;
> architecture behavioral of fsm is
> * *type state_type is (THIS, THAT);
> begin
> * *process (clock, reset)
> * *variable state : state_type;
> * *begin
> * * *if (reset = '1') then
> * * * *state := THIS;
> * * *elsif rising_edge(clock) then
> * * * *-- register inferred on any variables or signals
> * * * *-- assigned to inside this elsif section, right?
> * * * *-- due to the rising_edge...
> * * * *case state is
> * * * * -- Can you assign directly to a state variable when it is
> * * * * *-- registered? Or does it mess the case up?
> * * * * *-- Those are things I worry about...
> * * * * *when THIS => if (input = '1') then state := THAT; end if;
> * * * * *when THAT => if (input = '0') then state := THIS; end if;
> * * * * when others => state := THIS;
> * * * *end case;
> * * *end if;
> * *end process;
> end behavioral;
>
> I like it - one process, a private variable; no polluting the namespace.
> Sorry, software speak. But is this it then?
>


With signals in a clocked process, any signals assigned represent
registers.

With variables, it is different. A reference to a variable can be a
registered or combinatorial reference, depending on the relative order
of reading and writing the variable within a given clock cycle. If a
variable was previously written in the current clock cycle, before it
is accessed, then THAT REFERENCE to that variable is combinatorial. If
the variable was not written prior to being accessed, within that
clock cycle, then that implies that a previous clock cycle's value
has to be remembered, from which synthesis will infer a register FOR
THAT REFERENCE. The key is that the reference to the variable
determines register/combinatorial, not the variable itself. Multiple
references to the same variable can be combinatorial, registered, or
even both, in the case of a conditional prior write. In this case the
same condition that determines the prior write will drive a
multiplexer to select the registered or combinatorial value to be used
for that reference.

Just remember this: the description will behave like the SW reads:
variable values are updated as soon as the assignment is executed. If
the description recalls a value stored in a previous clock cycle, then
a register will be inferred. If the description recalls a value stored
previously in the current clock cycle, then a combinatorial value is
inferred.

In terms of your template, the reference to state occurs right up
front in the case statement, before state has been written within the
current clock cycle. So that reference to state is to the output of
the register that stores state.

Hope this helps.

Andy
 
Reply With Quote
 
Al Muliman
Guest
Posts: n/a
 
      02-13-2009
On 12-02-2009 23:50, Andy wrote:

> With signals in a clocked process, any signals assigned represent
> registers.
>
> With variables, it is different. A reference to a variable can be a
> registered or combinatorial reference, depending on the relative order
> of reading and writing the variable within a given clock cycle. If a
> variable was previously written in the current clock cycle, before it
> is accessed, then THAT REFERENCE to that variable is combinatorial. If
> the variable was not written prior to being accessed, within that
> clock cycle, then that implies that a previous clock cycle's value
> has to be remembered, from which synthesis will infer a register FOR
> THAT REFERENCE. The key is that the reference to the variable
> determines register/combinatorial, not the variable itself. Multiple
> references to the same variable can be combinatorial, registered, or
> even both, in the case of a conditional prior write. In this case the
> same condition that determines the prior write will drive a
> multiplexer to select the registered or combinatorial value to be used
> for that reference.
>
> Just remember this: the description will behave like the SW reads:
> variable values are updated as soon as the assignment is executed. If
> the description recalls a value stored in a previous clock cycle, then
> a register will be inferred. If the description recalls a value stored
> previously in the current clock cycle, then a combinatorial value is
> inferred.
>
> In terms of your template, the reference to state occurs right up
> front in the case statement, before state has been written within the
> current clock cycle. So that reference to state is to the output of
> the register that stores state.
>
> Hope this helps.


It does. Thank you. It also raises new questions, but I have to keep my
focus.
 
Reply With Quote
 
Al Muliman
Guest
Posts: n/a
 
      02-13-2009
On 13-02-2009 00:39, Jonathan Bromley wrote:

> For software folk, it may be useful to gloss this in
> a slightly different way:
>
> The linear, procedural idiom beloved of beginner programmers:
>
> do something
> wait for input
> do something else
> wait for more input
> do yet other things
> ...
>
> does not work in a typical modern operating-system
> environment; instead, your program must look like
> an event loop:
>
> while (1) {
> wait for anything interesting to happen
> deal with the consequences of that event
> update variables (state) to reflect the change
> }
>


Ah the message pump

> So the main code body looks like a state machine;
> each time it is woken up by an external event, it
> must look at the external event AND at its own internal
> state ("where have I got to so far?") and use that to
> decide what to do, and how to update the internal state.
>
> In a software event loop, each trip round the loop must
> execute very quickly so that the system remains responsive
> to other events (oh, how I wish certain well-known programs
> would keep that in mind... why does my entire PC freeze
> just because a certain well-known word-processor is
> trying to find a file on the network?). Indeed, if
> you have lots of work to do, you must break it up into
> small pieces, and after doing each little bit you must
> set a wakeup timeout and go back to waiting; you can
> do the next bit of work when next awoken by the timer.
>
> A hardware "event loop", in typical modern synchronous
> designs, has only one input event to wait for: the clock.
> On each and every clock edge, it examines all the inputs
> that it cares about given its current state. Just as
> with a software event loop, the loop body MUST execute
> very quickly. In fact, the body of your VHDL clocked
> process conceptually executes in zero time at the
> moment of the clcok edge. It is an algorithm for
> computing, in zero simulated time, the next state
> from the current state and inputs; EVERY synchronous
> design is nothing more than a big state machine.
>
> However, the current-state/next-state algorithm
> is in reality "executed" by a piece of combinational
> logic. Only in simulation is the next-state algorithm
> executed on a computer. The job of a synthesis tool
> is to infer from your algorithm what the logic function
> needs to be. Your algorithm can be arbitrarily
> complicated, with arbitrary numbers of internal variables,
> some of which hold state information from one clock to
> the next, and it all still works.
>
> Aaaargh.... this was all going to be so beautifully
> elegant and clear, and it's come out all rambly and
> long-winded as usual. Anyway, it may be useful to
> someone, I suppose


Yes I think I get what you are saying. But... I still have questions. I
am going to think about what has already been explained to me here, read
a little xilinx documentation and work on my own example (state machine
for writing to the LCD on a Spartan-3E kit). After that I shall return
with more questions . You have all been most helpfull. Usenet is
still alive. If you have any pointers on what the internal building
blocks of an FPGA looks like, I stand a better chance of learning what
is meant by a register and when the value that a register holds is
clocked through, and why they come almost free in an FPGA but not so in
an Asic.
 
Reply With Quote
 
 
 
Reply

Thread Tools

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 Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Virtual Server - Microsoft Learning Machines Nachete Windows 64bit 2 05-20-2008 09:36 PM
VHDL-2002 vs VHDL-93 vs VHDL-87? afd VHDL 1 03-23-2007 09:33 AM
One-hot Coding of State machines Clyde R. Shappee VHDL 10 06-03-2004 05:53 PM
Generics and state machines Steve VHDL 7 05-05-2004 06:28 PM
How to implement linked Finite State Machines Sidney Cadot VHDL 0 04-18-2004 10:45 AM



Advertisments