Topics Topics Edit Profile Profile Help/Instructions Help Member List Member List  
Search Last 1|3|7 Days Search Search Tree View Tree View  

State Machines

:: EPE Chat Zone ­:: ­Radio Bygones Message Board :: » EPE Forum Archives 2007-2009 » Archive through 16 March, 2008 » State Machines « Previous Next »

  Thread Last Poster Posts Pages Last Post
  ClosedClosed: New threads not accepted on this page        

Author Message
Top of pagePrevious messageNext messageBottom of page Link to this message

bob9999
Regular Contributor
Username: bob9999

Post Number: 26
Registered: 08-2007

Rating: N/A
Votes: 0 (Vote!)

Posted on Sunday, 24 February, 2008 - 05:21 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

I read the article in Pic N' Mix, EPE Dec 2007. I was puzzled by the concept of "State Machines", as it is an item I have not come across before. I have searched for a method whereby I could learn to programme this in QBasic, no luck.
I can see the concept, but just how I would programme Fig 5 for example is beyond me.
Is a "state machine" a form of linked lists?
Any help would be appreciated.
Sorry, but I just love QBasic!
Sorry too if this is not quite Electronics.
Top of pagePrevious messageNext messageBottom of page Link to this message

philwarn
Frequent Contributor
Username: philwarn

Post Number: 178
Registered: 04-2005

Rating: N/A
Votes: 0 (Vote!)

Posted on Sunday, 24 February, 2008 - 05:26 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Bob,

Finite State Machines can be found by googling for them.

The following link will take you to the C code for one. Just re0-write in your favourite flavour of Basic.

http://en.wikipedia.org/wiki/Event_driven_finite_state_machine

Phil
Top of pagePrevious messageNext messageBottom of page Link to this message

kevinbrunt
Regular Contributor
Username: kevinbrunt

Post Number: 32
Registered: 02-2007

Rating: N/A
Votes: 0 (Vote!)

Posted on Sunday, 24 February, 2008 - 08:32 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Even that Wikipedia reference is probably a bit like hard work.

Consider the sort of digital watch that has two buttons to set the time, etc. If it's like mine, you use one button to cycle around between the different displays (current time, alternative current time, date, alarm, stopwatch...) and then press the second button to go into "set mode", after which you manipulate the buttons to change the settings.

You might well say that the effect of pressing one of the buttons differs depending on the "state that the watch is currently in." This precisely the meaning of "state" in the term "state machine."

When someone is talking about a state machine, they are really viewing a program in terms of a black box, and what happens when an event that affects the block box occurs. (I'm think of computer programs here and am being a little lax in my terminology, as a light switch can be regarded as a state machine.)

In the watch example, you could list all the possible "states" of the display, and then, for each state, list what happens for each possible button push, and importantly, what state the display is left in afterwards.

(Incidentally, there is a design question here. Are every possible displayed time (all 24 hours by 60 minutes by 60 seconds) a separate state, so the the change of a digit represents a change of state? Or is "changing units of minutes digit" a state, so that pressing the button changes the "data" but does not change the state?

Having built the table, you could translate it into a program, where each state represents a place where the program waits for input, acts on it and then transfers control to the place in the program which represents the new state.

However, you could translate the table directly into a machine-compatible form, and then write a program which holds the current state in a variable. The program would have a loop which gets the next input, find the entry in the table for the state/input pair, performs the associated action, sets the state variable to the new state, and goes round for the next input.

Translating into "direct" code is likely to be faster, which might be an issue if your hardware is barely keep up. However, while the table-driven version will be a potch to implement correctly in the first place, it is a good deal easier when the spec changes (or you find a major bug in your initial understanding of the state machine!)
Top of pagePrevious messageNext messageBottom of page Link to this message

bob9999
Regular Contributor
Username: bob9999

Post Number: 27
Registered: 08-2007

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 25 February, 2008 - 12:09 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Phil, Thanks for the Info. I will try to de-scramble the C code, I have however never studied C at all!

Kevin, Thanks for the detail, you obviously know your subject. I did, though, ask for information in implementing this info in a programme, Basic if possible. It is the programme structure that interests me.

Regards, Bob
Top of pagePrevious messageNext messageBottom of page Link to this message

hackinblack
Frequent Contributor
Username: hackinblack

Post Number: 198
Registered: 09-2006

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 25 February, 2008 - 12:10 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

the term 'state machine' was a new one to me when i read it in the files for the microchip PICkit1 LED blink sequence demo;but i soon realised it simply meant an 'options' table,i.e output A=1001 output B=1110 etc.or in Basic IF A= x then output 1001.it saves code space for frequently repeated code chunks,and saves typing them repeatedly too! look-up tables area a similar idea;something akin to a books index.

(Message edited by hackinblack on 25 February, 2008)
Top of pagePrevious messageNext messageBottom of page Link to this message

alexr
Just joined
Username: alexr

Post Number: 1
Registered: 02-2008

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 25 February, 2008 - 03:03 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Unless the program that you are writing is fairly trivial you would not implement it as a state machine. The concept of a state machine is very useful in analyzing, rationalizing and then describing complex event driven programs but coding you software as a state machine adds an unnecessary layer of complexity to your code which would make it both messy to write and slow to execute.
Top of pagePrevious messageNext messageBottom of page Link to this message

atferrari
Frequent Contributor
Username: atferrari

Post Number: 534
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 25 February, 2008 - 08:27 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Trying not to hijack this thread:

Recently, when programming a function generator with no external input other than the change of frequency / phase by the user via keyboard, I started to see the different menus like small "state machines" part of a bigger (virtual) one, comprising every posible combination.

Is this vision correct?

I recall a book from Don Lancaster about TTL where he explained the use of PROMs with a "state machine" even if he did not use that name.
Agustín Tomás - Buenos Aires - Argentina
Top of pagePrevious messageNext messageBottom of page Link to this message

zeitghost
Frequent Contributor
Username: zeitghost

Post Number: 1045
Registered: 01-2006

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 25 February, 2008 - 08:32 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Damn.

I've been adding a layer of unnecessary complexity to my programs without being aware of it.

Me and a shedload of other embedded programmers.


Fie.
Top of pagePrevious messageNext messageBottom of page Link to this message

kevinbrunt
Regular Contributor
Username: kevinbrunt

Post Number: 34
Registered: 02-2007

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 25 February, 2008 - 10:36 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Being a programmer myself, I tend to think that fleshing out the concepts into explicit code is getting into egg-sucking grandparent territory :-)

How you actually program up a state machine implementation is heavily dependent on the hardware and software constraints of the application. At one end of the spectrum you have the pure table-driven approach, where you represent the state/event/action/new-state quadruples that describe the state machine as an array. You then implement an "interpreter" for the state table, which a single loop, which reads the next input event, searches the table for the entry that matches the state/event pair, performs the indicated action and sets the state variable to the new state.

Despite alexr's objections, this can be a useful way of working, particularly since the state machine interpreter is largely independent of the application, and can be used for the next project.

Obviously, for a large state table it would be necessary to use a better method of searching the table than a simple linear search. One way would be to have a separate event table for each state, and a "higher-level" table of states, to find the right event table.

The next "evolution" would be to eliminate the "interpreter loop" by having a fragment of code for each state, each with its own "wait for input" and "search table" code, and the change-of-state operation becomes a jump to the code implementing the new state.

The final "twist" is to replace the event tables with an if-else structure.

This pure sequential-flow version is not necessarily better, since any change to the state table means rewriting the program. What is more, a radical change to the state table will cause a change in the *structure* of the program.
Top of pagePrevious messageNext messageBottom of page Link to this message

eagre
Frequent Contributor
Username: eagre

Post Number: 207
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Tuesday, 26 February, 2008 - 02:30 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

The Finite State Machine is a generalization of the Turing Machine (Alan Turing, British mathematician, 1912-1954) conceived to investigate calculability by "mechanical" means. In principle, it consisted of a "tape" specifying a "state", which in combination with an input, dictated the next state on the tape. It can be simulated by computer programs in whatever language that you choose, but has no relationship to any particular language.

Ed
Top of pagePrevious messageNext messageBottom of page Link to this message

kevinbrunt
Regular Contributor
Username: kevinbrunt

Post Number: 36
Registered: 02-2007

Rating: N/A
Votes: 0 (Vote!)

Posted on Tuesday, 26 February, 2008 - 10:08 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Ed,

Isn't it more the other way round? Turing started from the state machine concept and contributed the idea of the infinite tape which is both the input and the output of the state machine.

From this Turing created the "Universal Turing Machine," which operates on a tape which contains both the description of another arbitrary Turing machine and the data for a particular run of the machine. Effectively, the program and the data of the interpreted machine are together the data for the UTM. The "program is data" concept is fundamental to the digital computer as we know it today.

Further, Turing demonstrated that the infinite set of possible tapes for his UTM was the "same size" as the set of integers, and thus "countably infinite".

Turing then envisaged a UTM whose tape itself held the description of a UTM and (as the 2nd UTM's tape) the description of an arbitrary Turing machine and its data. Turing then showed that there were questions that could be asked about the setup that could not be answered by replacing the "real UTM" with a special-purpose Turing machine designed to answer the question.

This proves that there are problems that a Turing machine cannot solve. A Turing machine deals with problems that are "effectively computable", a concept which is fundamental to theoretical Computer Science, which is why Turing's place in posterity was secure long before his wartime cryptographic work became known.
Top of pagePrevious messageNext messageBottom of page Link to this message

grab
Frequent Contributor
Username: grab

Post Number: 669
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Tuesday, 26 February, 2008 - 10:38 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

I'd say that Alexr has it 100% the wrong way round. For any significantly complicated logic, a state machine is almost always the *best* way to do it.

Of course it depends on the situation. But if you're trying to represent a real physical system - for example, a valve moving between fully-open and fully-closed, driven by a motor and checked by switches at each end - then your best bet is usually to use a state machine. For the valve, it might have states VALVE_OPEN, VALVE_CLOSED and VALVE_PART_OPEN. It might also include VALVE_FAULTY as a state if you're detecting failure by cross-checking switch states, motor current and the time the motor has been driving for.

The problem that state machines solve is the proliferation of conditions and what they mean. Is it easier to understand "(X<y>D) OR (P>Q AND G==H)", or is it easier to understand "VALVE_FAULTY"? This greatly simplifies your code and makes it much easier for you and other people to see what it's doing.

And it often makes it more efficient too. Suppose you had three places throughout your code checking for this valve being faulty. Would you check "(X<y>D) OR (P>Q AND G==H)" in all three places? Or would you check it once, set the state to "VALVE_FAULTY", and in all three places just say "if valve_state == VALVE_FAULTY"?

Yes, you could use multiple Boolean flags instead - maybe one for "faulty", one setting "open/closed", and one for "partially open". That works. Except that this is using more memory than the state variable, so it's less efficient.

State machines also work well for following a methodical path through actions. Suppose you have something which needs to read an ADC input, do five layers of processing on it (two of which are optional), and then write the result to an output. Again you could use multiple flags, but a state machine makes it clearer and easier.

Implementing a state machine is easy. It generally follows the BASIC-like pseudocode:-

Procedure Startup()
Set all outputs to initial values
Set state to initial value

Procedure CalledOnceEachLoop()
If state == STATE1
Do actions for STATE1
Check conditions for leaving state
If conditions met, move to new state

Elsif state == STATE2
...

Replace the "if-elsif" with your language's improve construct - "switch/case" in C, for example.

Hope this helps flesh out the concepts a bit.

Graham.

(Message edited by grab on 26 February, 2008)
Top of pagePrevious messageNext messageBottom of page Link to this message

bob9999
Regular Contributor
Username: bob9999

Post Number: 28
Registered: 08-2007

Rating: N/A
Votes: 0 (Vote!)

Posted on Tuesday, 26 February, 2008 - 12:04 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Guys, Many thanks for the informative articles. My understanding of FSM has greatly improved.

My initial puzzle was in programming a menu item into a continuous data logging devic, (PIC).
My usual effort would be to programme the normal logging process, then use an interrupt for the menu. That way the main programme runs without interruption, pausing briefly with a keypress.

Then I read about FSM and wondered if I had been missing somthing on the programming front.

About page 29 on a google search, I foung a good tutorial. This explained the principle with a simple programming example. It seems to me that the main problem is in drawing out the state diagram. It is then necessary to work through all the posabilities, then coding.

I still can't see the use of "States", why not just use Flags as normal?
Perhaps when a more complicated system is envisaged the FSM comes into it's own, I'll stick with interupts for menus meanwhile! I don't think the overhead is too severe using this method.
Again, very many thanks,
Regards, Bob
Top of pagePrevious messageNext messageBottom of page Link to this message

epithumia
Frequent Contributor
Username: epithumia

Post Number: 515
Registered: 06-2006

Rating: N/A
Votes: 0 (Vote!)

Posted on Tuesday, 26 February, 2008 - 03:46 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)


quote:

I still can't see the use of "States", why not just use Flags as normal?




Hi,

I'm not sure if this addresses the question, but if I remember correctly you can have 'maximally encoded' state machines and 'minimally encoded' state machines (or somewhere in between, of course).

Say a state machine has 8 possible states. A maximally encoded state machine would use 3 bits to carry the state: 3 bits = 8 combinations, State 0 to State 7.

A minimally encoded state machine would use 8 bits to show the state.
State 0 = 00000001
State 1 = 00000010
..
State 7 = 10000000

In the minimally encoded state machine you could think of each bit being a flag.

Which way you do it depends on the technology you're using. A CPLD is logic-rich but has a limited number of D-types available, so the maximally encoded machine may be preferable. An FPGA is register-rich, so the minimally encoded machine may be more efficient.

If writing it in PIC assembler, the minimally encoded machine has the advantage that you can check for a particular state using a bit-test, which is very efficient.

Epi
If you need me, Neil and me will be hanging out with the Dream King. - Tori Amos
Top of pagePrevious messageNext messageBottom of page Link to this message

eagre
Frequent Contributor
Username: eagre

Post Number: 208
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Wednesday, 27 February, 2008 - 03:40 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Kevin -

You are certainly correct that the concept of a state machine preceeded Turing's contributions, but I think he really brought attention to the ideas. I was introduced to a "Turing machine" before ever encountering a FSM. And, as you say, his place in history was well established before his cryptographic work in WW2.

I guess questions of computability digress a bit from the focus of this forum.

Ed
Top of pagePrevious messageNext messageBottom of page Link to this message

grab
Frequent Contributor
Username: grab

Post Number: 671
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Wednesday, 27 February, 2008 - 11:45 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Bob, if you've only got two states then a flag is fine. :-) But suppose you've got more states. You're then probably going to have a bunch of flags to capture the various situations.

For starters, a state variable is almost always the most efficient way of representing this - a state variable needs at most only enough bits to store all the states, but to make flags clear you usually need more than that.

And for another thing, a common error is to assume that flag X is irrelevant in a particular situation because flags Y and Z are both set. Trying to remember this across the whole system can be tricky - and even more so if there's a slight change to the logic in setting flag Z which invalidates that assumption! A state machine stops that source of errors.

And finally there's the simple clarity of it. You go from state "OPEN" to state "PART_OPEN" to state "CLOSED", for example - it's totally clear and unambiguous. You just can't get that with flags.

The most common mistake amongst non-expert coders is to think that most bugs are down to how you use the language - ambiguities in the language, using the wrong operator, or simple typos. This is untrue - if these bugs make it past compilation, they're usually easy to find because you can see what it's doing. The bugs which make you tear your hair out and promise your first-born to Satan in exchange for a fix, they're the ones you *can't* find easily because the circumstances they happen under are difficult to reproduce. And the reason you can't find them easily is because they're inherent in your design. If your design is unclear (and trust me, your own designs will be unclear to you yourself after three months) then you're basically pinning a sign on your back saying "kick me".

Graham.

Administration Administration Log Out Log Out   Previous Page Previous Page Next Page Next Page