State Machines.. and their efficiency.

Hi all,

I'm a low-level kind of programmer (and wannabe hardware
designer). When I write a piece of code, be it assembly,
C or Verilog, I need to have a precise idea of how it
will end up.
I've began to explore the wonderful world of FPGAs and
of the Verilog hardware description language, and while
I do understand that combinational logic can be reduced
to its minimum terms, and I also understand latches and
other sequential logic, I have big problems in figuring
how a state machine ends up ("schematically speaking").

Although I've hunted for, and found, some schematics of
state machines, I still haven't found a clear explanation
and description of them that makes me sleep at night.

My aim is, other than understanding state machines at a
intuitive level, to write them in the most efficient way.

When I'm writing combinational code, I know when it will
end up in too many logic gates.. same for sequential, but
for state machines the "black box" is actually into my
mind.

Many Thanks in advance for any attempts to illuminate me.

Greets,
Mike

 

[Neo]

A state machine AFAIK is a conceptual thing. It is very descriptive way
of seeing things performed say, in an orderly manner. So my
understanding is that you need not always necessarily code for a fsm.
with that in mind when you describe sequential processes you are
essentially decscribing a fsm. But some problems can be more clearly
divided in to a set of stages in performing a certain task and this
will easily lead to the code itself to mimic the stages, leading you to
a fsm specific coding style. So FSMs are just a way of dividing the
work to be done into stages, it may either be implicit or explicit.
to know about optimizing the FSM you have have a clear picture of the
stages of the design and their actions, this you get by analysing the
problem and using state charts. hope this helps.

 

[Berty]

Maybe a simple example will help showing the benefit of state machine,
Consider something you for sure is familiar with and it is light
traffic.

It have basicly 3 color (lets forget all those "special" light like
with arrow etc),
Green - Go
Yellow - Prepare to stop/start
Red - Don't Go.

Now try to write a code that just go from Green to Yellow to Red and
back.

In general what you would like the code to do is start at some define
state like let say red light. Than after some time go to yellow from
there to green and wise versa.

One way to do it is with state machine which will have something like

casex(sm)
`red : if (red_time_done)
sm <= #1 `yellow1 ;
`yellow1 : if (yellow_time_from_red2green_done)
sm<= #1 `green ;
`green : if (green_time_done)
sm <= #1 `yellow2 ;
`yellow2 : if (yellow_time_from_greeen2red_done)
sm<= #1 `red ;
endcase

since the sm it 2 bit and all 4 combination are covered no need to
worry about undefined states and therefore a default is not needed (or
if you use overwrite technique than default in any case is not needed).

You can in such simple example use flags and than use logic on the
flags to tell what was the previous state and therefore what shall be
use next however the more complex the machine is using flags will be
quite hard not to mention hard to debug as by using state machine you
combined all flags to one place.

Notice that state machine can be "complex" in sense tat from each
state can be a path to each other state or can be "simple" such as
all state are sequential (which basically mean state machine which can
be done by shift register in certain condition)

The second point of consideration is how you code the states themselves
meaning the above for example can be done using 4 bit and the states
will be for example
0001 for red
0010 for yellow1
0100 for green
1000 for yellow2
The drawback of the last is having 4 FF versus 2 however the benefit is
that IF you need to use the state condition as part of your code and
you run in high frequency and therefore have low budget of period to
use in the second option (called one hot since there is only one FF
with value 1) you only need one FF to know you are in this state while
using the first example you need both(all) FF of the state machine.

Keep in mind that onehot have a lot of undefined state and you might
want to use default however the bigger the oneshot there will be more
penalty for all this default case so you might want to use it without
default or use other alternative to check the state machine didn't
enter undefined state and got stuck in it. There are few way to handle
it but this you can leave for later.

Have fun.

 

[balor]

A state machine is similar to a deterministic finite automata (DFA),
which you may be familiar with. There is also a software pattern "state
machine" that is similar.

When all your code is combinational, it can be difficult to determine
what the code does. A state machine organizes the code so that the
reader can analyze different states independently. They can also be
used to pipeline an operation, either to share resources or because the
delay through a long chain of combinational gates is too long.

To imagine roughly what the hardware will look like, imagine that a
state machine is a counter, where each value maps to a state in your
state machine. Suppse you had something like:

switch(stateMachine)
case STATE: output <= signal;

This would look something like
assign output = (stateMachine == STATE) & signal

Your compiler can optimize from this very well so the hardware that
will be generated will be much more efficient but this is a good way to
imagine the hardware I think.