13-06-2012, 05:09 PM
FINITE STATE MACHINES
FINITE STATE MACHINES.pdf (Size: 368.18 KB / Downloads: 40)
Finite-statemachine(FSM)isamathematicalmodelusedtodesigncomputerprogramsanddigitallogiccircuits.
Any Circuit with Memory Is a Finite State Machine
Even computers can be viewed as huge FSMs
Design of FSMs Involves
Defining states
Defining transitions between states
Optimization / minimization
Above Approach Is Practical for Small FSMs Only
State diagram & State assignment
Astatediagramisatypeofdiagramtodescribethebehaviorofsystems.
Statediagramsrequirethatthesystemdescribediscomposedofafinitenumberofstates
Stateassignmentisaspecificationhavebeengiventoacombinationofflip-flopsandcombinationallogic
Stateassignmentistothenumberofpresentstatesinaparticularcircuit
N-numberofflipflop2^Nstateassignment
Sequential circuit design
Now let’s reverse the process: In sequential circuit design, we turn some description into a working circuit.
We first make a state table or diagram to express the computation.
Then we can turn that table or diagram into a sequential circuit.
Making a state table
The first thing you have to figure out is precisely how the use of state will help you solve the given problem.
Make a state table based on the problem statement. The table should show the present states, inputs, next states and outputs.
Sometimes it is easier to first find a state diagram and then convert that to a table.
This is usually the most difficult step. Once you have the state table, the rest of the design procedure is the same for all sequential circuits.
Sequence recognizers are especially hard! They’re the hardest example we’ll see in this class, so if you understand this you’re in good shape.