What is the need of FSM?

[gmish27]

As far as i know and have studied a Finite State Machine helps in predicting the nest state transition but how? is what i don't know yet. Can anyone tell me the need of going for a fsm instead of solving the problem with sequential circuits, please

 

[ckshivaram]

check these links
Finite State Machines, FSM tutorial makes FSMs easy to understand
https://www.cs.hmc.edu/~keller/cs60book/12 Finite-State Machines.pdf

 

[pmat]

Hi,
i just went through both of the links but neither of them answers gmish's question.
A sequential circuit is compromised by a set of memory elements (FFs, Latches, Combinational Gates with Feedback) and combinational logic.
If during design time you know exactly the possible value combinations that the memory elements will get, you have an FSM.
When the memory elements take arbitrary values during circuit operation (the better way to think of this scenario is the memory elements being the registers of a processor's pipeline)
you make the assumption that all value combinations of the memory elements may happen.

Now, with respect to optimization of the FSM circuits, there are a lot of scenarios which simplify the logic.
If a combination that you thought it was possible to happen, never happens, then an unreachable state is found and it can be used for Logic Simplification.
If two value combinations (sequential system states) can be merged to a single one without affecting system's operation, a redundant state is found, further
optimizing the circuit.
etc. etc.

Pavlos

 

[gmish27]

Emmm...the links do illustrate a lot about what is a Finite State Machine but still i did not get the difference and the reason to shift from a sequential circuit design to designing a fsm.

I mean sequential circuit designing also involves drawing state diagrams. So in short i still don't get benefit of going for a fsm over the normal methods thru which we tackle design problems

 

[bigdogguru]

For all practical purposes a Sequential Circuit is a Finite State Machine. The difference between Combinational Circuits and Sequential Circuits is Sequential Circuits make use of a storage device, memory, flip flops, etc, to storage the current "State" of the circuit.

All sequential circuits contain combinational logic in addition to the memory elements.

**broken link removed**



Therefore when you design a Sequential Circuit, you are in fact implementing a FSM, you just might not realize it. The existence of a clock also separates Combinational and Sequential Circuits, the clock being a necessity for storage elements. It these "storage elements" that store the current state of the machine.

Hope this explaination clears up the confusion.

 

[gmish27]

Thanks! Finally i can confirm my mind's thought- they both are the same thing, nothing to worry bout.

 

[Regnum]

gmish27,

A Finite State Machine is just an abstraction to ease sequential/combinational logic design and synthesis.
Of course you are not obligated to work out sequential/combinational logic by state-machines approach, but it is usually easier and clearer.

Regards,
Regnum

 

[pmat]

I disagree with a lot of simplistic opinions which mislead the designers.
In order to get the gains of an FSM-oriented synthesis flow you must know
at design time the exact states and exact transitions between states. Otherwise
the tool will produce a sub-optimal circuit.

Lets see DC' s synthesis flow. DC will optimize your FSMs only if you specify
the exact registers which will be FSM's state holding elements. Otherwise the
tool will make the false assumption that ALL value combinations are possible
for your registers and it will not take into account any information regarding
the state diagram you had designed in paper.

If you are willing to help DC optimize your FSM-oriented designs further read
Cumming's papers at SNUG....
http://www.sunburst-design.com/papers/CummingsICU2002_FSMFundamentals.pdf

 

[gmish27]

Pmat, well when i solve a sequential circuit design i do the same thing. I plot all of my states and transitions on the paper and if any of them misleads the problem then its nothing but an Ooops!

So how come i can have 'gains' of fsm ? Cos knowing all the states and the internal transitions do help in making state diagrams and sequential circuits as well.

I wonder why the term FSM is their ? We used to solve sequential circuits problems with state diagrams and k map, then why to think bout this term in the way ?

 

[pmat]

Nowdays control systems have many FSMs and each FSM has many inputs and many outputs. The transition and output functions you used to optimize with K-maps are
far too complex to be optimized this way. Nowdays each function is a multilevel gate network and not just a two-level AND-OR circuit with FFs attached on it.

Thus, the tool should be able to co-optimize the transition and output functions according to an FSM encoding which best helps optimizes the logic. (Unfortunately there
are no tools - as far as i know - which propose an encoding, so you have to choose one ( for Synopsys DC the command is set_fsm_encoding, for RC there is NO such
command...). Therefore, as you cannot optimize the FSM on paper, help the tool do so, by exactly explaining your FSM (it would also help if you could add some dont care next
states or dont care outputs. Cumming's papers explain how to do that).

Finally, if you dont want to write HDL to insert a small FSM in DC you can even insert the
FSM as a state transition table...

Pavlos

 

[gmish27]

Hmmm...ok thanks pmat. I hope i meet a problem soon that demands extensive fsm design.