State Machines.. and their efficiency.

[[email protected]]

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

 

[Ol' Duffer]

One of the simplest structures, and one you can build youself
on a breadboard and play with, consists of a ROM and a parallel
latch. Some of the ROM data outputs go to latch inputs, and
the associated latch outputs go back to ROM address lines, so
that each time you clock the latch the machine "steps" to the
next "state". Use as many address bits as you need for the
longest sequence, plus any user "inputs". This architecture
is scalable almost to infinity...

 

[Robin]

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

Yes, I wanna know what a "state machine" is too because I'm dammed if I
understand the formal descriptions I come across.

I have seen two examples of code called "state machine" they both do
the same thing:

1) There is a pointer.
2) There are code fragments.

a) When a code fragment finishes, it sets the pointer to another code
fragment then...
b) ...the code pointed at is executed.

And that's it.

So it is a flat structure and very difficult to understand i.e. you
have to have it all "finished before you start" and hope that you never
have to maintain it


Cheers
Robin

 

[Keith Williams]

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.

When I write programs, they end up as state machines. Think CASE.

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.

Google "state machine" and "mealy" and "moore". Here is a decent web
site that explains them:
http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Seq/impl.html

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

That's what compilers are for. ;-) The FPGA tools I use will infer the
logic to create state machine I tell it to. I can tell it what sort of
state machine I want and it'll generate the logic. It's useful to
compare the output to see what the flop/logic trade off is.

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.

FPGAs tend to favor "one-hot" state machines. That is, only one
flipflop is a '1' at any given time. Thus there is one flipflop for
every bubble in the state diagram. Other common encodings include
"binary" and "gray", which would have LOG2(states) flops. The
difference being the encoding of the flops.

 

[OBones]

State machine, is just a machine that has different states, and that can
go from one to some others according to transition rules.

You go from Stopped to Started by pressing the Start button.
You go from Started to Stopped by pressing the Stop button.
You go from Started to Buzzing by depressing the Buzz button.

And so on and so on...
One usually uses a diagram (state diagram) to draw this, with circles
for states and arrows for transitions.

The most complex transition rules can even require you to do two things
at once ;-)

 

[Frithiof Andreas Jensen]

[email protected] wrote:

Yes, I wanna know what a "state machine" is too because I'm dammed if I
understand the formal descriptions I come across.

A drawing of the states and the transitions is easy to design and understand
IMO .. it's working it out in reverse from implementation is hard.

I assume the "formal description" is something else.

There are tools to generate State Machine implementations from some kind of
readable description. Rational Rose RT have graphical tools, Parsers and
such use Grammar definitions.

So it is a flat structure and very difficult to understand i.e. you
have to have it all "finished before you start" and hope that you never
have to maintain it

So, No Drawing?? No Grammar?? No Hope!

Maybe those were generated from some long-lost grammar definition or source
file and not supposed *ever* to be maintained manually (but the guy who knew
how to work the tool left, and those wierd files were taken out of the build
and then his successor put a couple of 1000 hours into improving the code
?

 

[Rene Tschaggelar]

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.

Many Thanks in advance for any attempts to illuminate me.

A state machine is a description.
Whatever you're talking about is having different states.
The states are changed by events that occur. So
for each state there are expected/anticipated events
and each of such an anticipated event can cause an action.
After the event & action, the state machine is in a
different state.

Rene

 

[Robin]

State machine, is just a machine that has different states, and that can
go from one to some others according to transition rules.

You go from Stopped to Started by pressing the Start button.
You go from Started to Stopped by pressing the Stop button.
You go from Started to Buzzing by depressing the Buzz button.

And so on and so on...
One usually uses a diagram (state diagram) to draw this, with circles
for states and arrows for transitions.

The most complex transition rules can even require you to do two things
at once ;-)

So this:

.... // mem = state_one
stab mem // mem transits to state_two
.... // mem = state_two

is a state machine?


Cheers
Robin

 

[OBones]

So this:

... // mem = state_one
stab mem // mem transits to state_two
... // mem = state_two

is a state machine?

It could be yes. Basically, "state machine" is a concept to indicate
that the machine can only have one state at any given time, depending on
its inputs and the history of it's inputs.
Nothing much in here, you could even say that a PC is a state machine.
Lots of inputs, lots of states, even some unexpected ones ;-)

 

[PeteS]

A state machine is simply one that has some number of states, and moves
from one to the other in a specific way. There are a lot of examples
around. The first one I did was to implement an error count within an
external window signal (with flip flops, gates and a 555 for the window
pulse).

A more complex one (but quite common in the FPGA world) is to implement
a system bus (for instance, interfacing to a PowerPC style device a
non-PowerPC controller). Here the bus has very specific states, and
should move from any one state to one of the others (there's more than
one way around the diagram!) based on input signals.

State machines are normally compiled in FPGAs (as noted) as one-hot
encoders (whch is really a ram array with one, and only one, output
high, denoting the 'state'), giving rise to the maxim 'Thou shalt
initialize thy state machines' to some *stated* state in the code
(otherwise all the state bits are reset - the default - and the machine
never starts).

i.e. somewhere in the code (Verilog) one should see something of the
order of:

always @ (reset)
begin
MyStateMachine <= MyMachineInitState;
end

Cheers

PeteS

 

[Terry Given]

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

David J. Comer wrote a decent book on state machines, that I learned
from in the mid-80's. digital logic and state machine design, IIRC (I
foolishly gave it to my brother)

the comments to date have been good, esp. the google mealy,moore
comment. I have built (for fun) quite a few ASMs (or FSMs or SMs) using
the eprom-latch method (back when I had an eprom programmer). I have
implemented thousands more inside programmable logic (without the aid of
fancy tools). Dont forget to decode unused states, lest some unfortunate
event send your FSM into a tailspin from which it cannot recover (eg
point all unused states back to the initial state)

Cheers
Terry

 

[Herbert Blenner]

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

Suppose you have n latches connected to a common clock. At any moment
these n outputs, a combination of ones and zeros, describe the state
of the machine. On the next clock cycle the output of each latch
changes in accordance to its present input. This characteristic
constitutes the machine.

Generally the outputs of a state machine are combinations of latch
outputs and perhaps machine inputs. Likewise the inputs of the latches
are combinations of latch outputs and machine inputs.

Herbert

 

[Roger Johansson]

So it is a flat structure and very difficult to understand..

Think about swiss music boxes, like these:
http://www.cowderoyantiques.co.uk/cylinder/cyl_list.html

We have probably all taken apart a toy containing such a music box.
Here are close-up pictures of the next to last one:
http://www.cowderoyantiques.co.uk/cylinder/cylinder_pages/11245_pg.html


The cylinder with spikes rotates, the spikes pluck at a row of reeds
and music is produced. A self-playing piano works in a similar way.

Now imagine if the spikes started motors, turned on lamps, opened
valves and doors, starting pumps.
Such a little music box could control a small industry.

Some more features we would like to see:

Possibility to jump to a certain section on the cylinder without having
to go through the program on the way. We have small "verses" in the
song we want to jump freely between, every verse is an instruktion. You
could see the instruktion list for a microprocessor as the single
verses that are programmed into the memory chip we use as the rotating
cylinder.

Possibility to let input signals influence the process. Direct hardware
interrupts and data port we can read and use the data to take decisions.


If we move over from the mechanical world to the world of electronics
we can create the same type of machine with a few components, and the
extra features we wished for are easily implemented.

A static ram memory, or an eprom, a latch/counter to hold the
address, an oscillator (clock signal circuit) to count up the counter.

The output data lines are the spikes in this electronic mucic box,
which can be connected to motors, lamps, doors, etc.

We can use these data output lines to control latches, and connect
these latches with buses. We can have instructions like "start pumping
data from the external ram memory to the hard disk" or "wait for line X
to go low before executing the next instruction".

The output signals from the memory could control the flow of 32 bit
data in 10 piece 32 bit latches, for example.
These latches we can call registers, and we have built a cpu, a
microprocessor.
It can do operations like read a byte from the hard disk and copy it to
the video memory.

http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Seq/impl.html
Look at the third image, 75% down on the page.
Right after "Here's the final diagram."

That is a simple system which consists of a memory, counters/flipflops,
and an oscillator/clock puls generator.

The X input shows that outer signals can influence the working of the
system.

The feedback lines show how the instruktions in the memory can
influence the address pointer (the memory address the counter/latch is
sending to the memory). We can jump.

The lines marked Z1 and Z0 show how we can get something done with this
machine.

These lines can control latches, control the flow of data in a whole
system.

 

[Terry Given]

Robin wrote:




Think about swiss music boxes, like these:
http://www.cowderoyantiques.co.uk/cylinder/cyl_list.html

We have probably all taken apart a toy containing such a music box.
Here are close-up pictures of the next to last one:
http://www.cowderoyantiques.co.uk/cylinder/cylinder_pages/11245_pg.html


The cylinder with spikes rotates, the spikes pluck at a row of reeds
and music is produced. A self-playing piano works in a similar way.

Now imagine if the spikes started motors, turned on lamps, opened
valves and doors, starting pumps.
Such a little music box could control a small industry.

Some more features we would like to see:

Possibility to jump to a certain section on the cylinder without having
to go through the program on the way. We have small "verses" in the
song we want to jump freely between, every verse is an instruktion. You
could see the instruktion list for a microprocessor as the single
verses that are programmed into the memory chip we use as the rotating
cylinder.

Possibility to let input signals influence the process. Direct hardware
interrupts and data port we can read and use the data to take decisions.


If we move over from the mechanical world to the world of electronics
we can create the same type of machine with a few components, and the
extra features we wished for are easily implemented.

A static ram memory, or an eprom, a latch/counter to hold the
address, an oscillator (clock signal circuit) to count up the counter.

The output data lines are the spikes in this electronic mucic box,
which can be connected to motors, lamps, doors, etc.

We can use these data output lines to control latches, and connect
these latches with buses. We can have instructions like "start pumping
data from the external ram memory to the hard disk" or "wait for line X
to go low before executing the next instruction".

The output signals from the memory could control the flow of 32 bit
data in 10 piece 32 bit latches, for example.
These latches we can call registers, and we have built a cpu, a
microprocessor.
It can do operations like read a byte from the hard disk and copy it to
the video memory.

http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Seq/impl.html
Look at the third image, 75% down on the page.
Right after "Here's the final diagram."

That is a simple system which consists of a memory, counters/flipflops,
and an oscillator/clock puls generator.

The X input shows that outer signals can influence the working of the
system.

The feedback lines show how the instruktions in the memory can
influence the address pointer (the memory address the counter/latch is
sending to the memory). We can jump.

The lines marked Z1 and Z0 show how we can get something done with this
machine.

These lines can control latches, control the flow of data in a whole
system.

pull apart one of those cute dial padlocks. They are a mechanical state
machine. Incidentally, examining the innards gives a clue as to how to
pick them

Cheers
Terry