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 :)
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:
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:
formatting link
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.
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.
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 ;-)
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 :-)?
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.
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.
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 ;-)
We have probably all taken apart a toy containing such a music box. Here are close-up pictures of the next to last one:
formatting link
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.
formatting link
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 :)
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)
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.