A Finite State Machine (FSM) is an abstraction used to describe the input/output behaviour of a sequential circuit independently of its actual implementation. It has a finite number of states, with exactly one state active at any time.
States
A state is a representation of the current ‘status’ of the system at any given time, with the information needed to determine future behaviour.
The next state depends on the present state, usually in addition to its current inputs. This behaviour is captured graphically as a state diagram, or equivalently as a state transition table.
Quote bq
Typically, the state of a circuit depends on the values held in its registers.
Types of FSMs
We categorise FSMs depending on whether their outputs depend only on the present state, or on the present state and the current inputs. These are known as Moore and Mealy machines respectively.
Equivalent States
Two states of an FSM are equivalent if for each input, they produce the same outputs and their transition states are identical.
Concept bq
To find equivalent states systematically, use an implication chart.
Transitive States
A transitive relationship means that if state and are equivalent, and and are equivalent, then and are also equivalent.
Equivalence of states is transitive when machine is fully specified, but is not transitive when ‘don’t cares’ are present.
A state with an
Xcan satisfy equivalency for multiple states even if those states clash with each other.
await dv.view("Scripts/topic-backlinks");