A synthesis system for testable and area-efficient finite state machines
Chun-Yeh Liu · 1995
A Finite State Machine (FSM) synthesis system can generate an area-efficient testable design by performing the following steps in sequence: functional design, logic design, topological design, and testable design. The first step, functional design, maps the functional description into a logic representation. The second and third steps, namely logic minimization and topological minimization can in principle ensure area-efficient implementation of an FSM. The last step, testable design, ensures that the resulting implementation has the desired fault coverage. In this thesis, an FSM synthesis system, which globally integrates the design steps described above, is proposed. The synthesis system can generate a testable and an area-efficient implementation and makes use of the following properties: (1) It uses more than the minimum number of state variables to provide efficient and optimal logic minimization. (2) It considers the sparsity in the state assignment so that the result is well suited for minimization and folding operations. (3) It encodes the state that results into a unate realization of the circuit which makes testing easy. A heuristic-based (k,p)-code state assignment algorithm, SASSY (State Assignment for Finite State Machine $\underline{\rm SY}$nthesis), which provides a unate state assignment, is developed. Experimental results over a wide range of benchmarks show that the designs obtained by SASSY are superior to the designs provided by the existing design tools in area and wire count. Folding is a technique which reclaims unused area in the original PLA. A column bipartite folding algorithm based on a matrix representation is proposed. Heuristics are used to reduce the search space and to speed up the search process. The folding program was also applied to several benchmarks and the experimental results demonstrate the superiority of the proposed algorithm in finding optimal solutions in a reasonable CPU time. Finally, a design for testability methodology for sequential circuits is presented. The design method increases controllability and observability of the final FSM. The experimental results on the FSM benchmarks show that the designs produced are 100% testable.