Connect with us

State Machines.. and their efficiency.

Discussion in 'Electronic Design' started by [email protected], May 26, 2005.

Scroll to continue with content
  1. Guest

    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
     
  2. Ol' Duffer

    Ol' Duffer Guest

    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...
     
  3. Robin

    Robin Guest

    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
     
  4. When I write programs, they end up as state machines. Think CASE.
    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
    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.
    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.
     
  5. OBones

    OBones Guest

    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 ;-)
     
  6. 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, 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
    :)?
     
  7. 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
     
  8. Robin

    Robin Guest

    So this:

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

    is a state machine?


    Cheers
    Robin
     
  9. OBones

    OBones Guest

    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 ;-)
     
  10. PeteS

    PeteS Guest

    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
     
  11. Terry Given

    Terry Given Guest

    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
     
  12. 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
     
  13. 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.
     
  14. Terry Given

    Terry Given Guest

    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
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-