Below we will discuss one of the methods to improve a chip's area. Current approaches to structural synthesis of finite state machines are nonminimal. As described above, the currently used design approach is first to minimize the number of machine's internal states and follow it with the states' assignment.
The aim of these methods is generally to decrease the semiconductor area of the realization for some selected implementing technology. However, the methods apply very abstract cost approximations to achieve this. It would be more desirable to minimize some generalized technology-dependent cost functions.
Minimization of the number of internal states results from the adopted assumption: "the more internal states, the more complicated is the realization, hence more memory elements are needed, there are more excitation functions, and therefore their realization is more complicated". Practical examples bear evidence that the flow table with the minimum number of internal states is not necessarily the appropriate starting point to achieve the circuit realization of the minimum total complexity (computed for instance as the weighted sum of the number of flip-flops and the number of combinational gates). Please note, that many contemporary technologies (among others - MOS) do not require first of all minimization of the number of memory elements, as is assumed in the classical methods.
Practical examples show evidence that we should not seek a FSM with the minimum number of internal states, nor one with the excitation functions depending on the minimum number of variables Examples of FSMs can be easily found that have minimum realizations with the greater than minimum number of flip-flops (because of much simpler excitation functions). Also, the attempt to find a realization of the set of excitation functions with the minimum number of argument variables is often useless, because such realizations can have more gates or connections than other the realizations of these functions. Moreover, these assumptions do not take into account the realization of excitation functions for flip-flops different than D flip flops.
One of the possible approaches is to replace two stages:
- minimization of the number of the machine's internal states,
- state assignment of the machine's internal states,
with one stage of joint minimization and state assignment. In this joint process, the cost function, related to the realization of the excitation functions in a selected technology, is optimized. The optimum and approximate methods of this type are presented in [121, 122].