OTHER APPROACHES TO FSM DESIGN AND OPTIMIZATION.

Because the traditional approach to FSM design either involves solving at least two difficult combinational problems: state minimization and state assignment, or produces possibly poor solutions, many attempts to implement other FSM design methodologies have been undertaken. They attempt to minimize total area/chip count and include:

• design of general-purpose FSMs based on shift-registers or other elementary machines instead of flip-flops [49],
• design with special flip-flops with multiplexed inputs,
• design with regular arrays of elementary tunable machines,
• decomposition of FSMs into structures of FSMs [116, 188],
• converting the form of machine (Mealy to Moore and Moore to Mealy) to select one of better performance,
• concurrent state minimization and state assignment [121, 122],
• special structures of FSMs, like different type of micro-programmed control units with many ROMs and multiplexers, or partitioned realizations of logic [166, 109],
• direct conversion of high level description like parallel FSMs to symbolic or geometric layout [99].

The above approaches are used selectively for various categories of machines: some of them can be used for all machines, some of them are reasonable for large machines only, some other can be applied only to small machines.

• Concurrent state minimization and state assignment to improve area.
• Methods based on decomposition and partitioning of FSMs.