Finite
state machines (FSM) have been a topic of great importance in the last five
decades and have been used to specify and implement control units. Due to the
increasing complexity of control units and since the FSM model does not
explicitly support hierarchy and concurrency, new state-based models with
hierarchical and concurrent constructions were proposed in order to overcome the
limitations of the conventional FSM model and allowing the specification of
complex control units in a top-down manner. Still, there are not many
hierarchical FSM architectures (HFSM) that have been proposed to implement those
hierarchical specifications and most of them cannot be seen as a whole FSM
implementing internally in an efficient way the switching between the different
hierarchical levels of the machine, except for the HFSM with stack memory.
This
thesis tackles the synthesis of FSMs from hierarchical specifications and
proposes two HFSMs and a parallel hierarchical FSM (PHFSM) with stack memory
that can provide such facilities as flexibility, extensibility and reusability.
It also presents the synthesis methodology from hierarchical specifications to
the generation of state transition tables that can be used to carry out the
logic synthesis of the proposed HFSM models.
Considering
that the use of formal state-based models that provide hierarchical and
concurrent constructions is highly recommended for specifying complex control
units, hierarchical graph-schemes (HGS) and parallel hierarchical graph-schemes
(PHGS) are used and some considerations about their execution and correctness
are presented. It is also explained how HGSs can be used to specify a control
algorithm and how it is possible to verify automatically its correctness and to
validate the intended functionality through simulation.
Using the
first model of a HFSM with stack memory as a starting model, two new models that
can provide flexibility, extensibility and reusability and a PHFSM model that
combines hierarchy and pseudo-parallel execution of operations are proposed.
Their functionality, flexibility, extensibility, synchronisation and internal
realisation are fully explained.
To
implement a control unit specified with a set of HGSs/PHGSs it is necessary to
perform the first step of the sequential logic synthesis, taking in
consideration the pretended target model. The manual synthesis methodology
required to build the state transition table of a HFSM/PHFSM starting from a
hierarchical specification based on HGSs/PHGSs is explained for a Moore, a Mealy
and a mixed Moore/Mealy FSM. A tool that automatically performs this first step
for the two HFSM models proposed is also presented.
In order to validate the proposed HFSM/PHFSM models and their synthesis,
the models were described in VHDL for a LUT-based implementation and simulated
using the Synopsys simulation tools.