Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

What is the need of FSM?

Status
Not open for further replies.

gmish27

Member level 1
Joined
May 12, 2011
Messages
34
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Activity points
1,553
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
 

pmat

Member level 5
Joined
Mar 26, 2007
Messages
91
Helped
15
Reputation
28
Reaction score
9
Trophy points
1,288
Location
Grenoble, France, EU
Activity points
1,790
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
 
  • Like
Reactions: MRAMA

    MRAMA

    points: 2
    Helpful Answer Positive Rating

gmish27

Member level 1
Joined
May 12, 2011
Messages
34
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Activity points
1,553
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

Administrator
Joined
Mar 12, 2010
Messages
9,831
Helped
2,348
Reputation
4,690
Reaction score
2,274
Trophy points
1,413
Location
Southwest, USA
Activity points
62,508
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.
Combinational vs. Sequential Circuits

Difference between Combinational and Sequential Logic

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

Member level 1
Joined
May 12, 2011
Messages
34
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Activity points
1,553
Thanks! Finally i can confirm my mind's thought- they both are the same thing, nothing to worry bout.
 

Regnum

Full Member level 5
Joined
Jun 17, 2004
Messages
262
Helped
18
Reputation
36
Reaction score
7
Trophy points
1,298
Location
Hurlingham
Activity points
2,168
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
 
Last edited:

pmat

Member level 5
Joined
Mar 26, 2007
Messages
91
Helped
15
Reputation
28
Reaction score
9
Trophy points
1,288
Location
Grenoble, France, EU
Activity points
1,790
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

Member level 1
Joined
May 12, 2011
Messages
34
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Activity points
1,553
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

Member level 5
Joined
Mar 26, 2007
Messages
91
Helped
15
Reputation
28
Reaction score
9
Trophy points
1,288
Location
Grenoble, France, EU
Activity points
1,790
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

Member level 1
Joined
May 12, 2011
Messages
34
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Activity points
1,553
Hmmm...ok thanks pmat. I hope i meet a problem soon that demands extensive fsm design.
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top