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

 

[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...

In article <RSjle.945836$b5.41282603@news3.tin.it>, nospam@nospam.com
says...

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.

 

[Keith Williams]

In article <RSjle.945836$b5.41282603@news3.tin.it>, nospam@nospam.com
says...

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.

--
Keith

 

[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]

"Robin" <robin.pain@tesco.net> wrote in message
news:1117116312.005215.285330@z14g2000cwz.googlegroups.com...

nospam@nospam.com 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]

nospam@nospam.com wrote:

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
--
Ing.Buero R.Tschaggelar - http://www.ibrtses.com
& commercial newsgroups - http://www.talkto.net

 

[OBones]

Robin wrote:

OBones wrote:

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?

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 ;-)

 

[Terry Given]

nospam@nospam.com wrote:

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

 

[Roger Johansson]

Robin wrote:

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.



--
Roger J.

 

[Terry Given]

Roger Johansson wrote:

Robin wrote:


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.

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