Automated synthesis of finite state machines using a dynamic partial-valued logic technique

Computer-aided design software, known as CAD tools, is indispensable in very large scale integrated (VLSI) circuit design. With the rapid evolution of VLSI technology, design of large, complex electronic systems becomes increasingly complex and difficult. Success of design work depends heavily on CAD tools at the various design phases of VLSI. CAD tools also reduce design efforts and turnaround time, eliminate human errors, and as a result, reduce design cost and risk.;Dynamic partial-valued logic (DPVL) technique was proposed two decades ago. However, this technique has been applied only to a limited range of dynamic asynchronous finite state machines (FSMs). This dissertation presents a systematic approach to design general synchronous DPVL-based FSMs. We also present the development of a new computer synthesis program, Tao, for implementing synchronous FSMs using the DPVL technique. A new transistor array structure is proposed to layout DPVL-based FSM circuits. The layout structure produced by Tao is area efficient. Design examples have shown that implementations of DPVL-based FSMs using this array structure results in approximately 25% smaller layout area of the informing logic circuit than that of its PLA counterpart.;The dynamic performance of DPVL gates has been analyzed. Two new heuristic state assignment algorithms targeting DPVL implementation have been proposed. The algorithms aim at minimizing the layout area of FSMs. It has been shown that the results of using these algorithms to encode FSM examples, randomly chosen from the literature, are comparable to those achieved using another state assignment program, Mustang.;The automatic synthesis program, Tao, accepts a state transition table or a language description of a FSM and provides the layout masks to be fabricated. Design examples generated by Tao have shown an approximately 30% layout area reduction as compared with PLA implementation. Simulation results of two design examples have also demonstrated that power dissipation for DPVL-based FSMs can be more than ten times lower than that for PLA-based FSMs. Small area and low power dissipation make DPVL technique an attractive alternative to design FSMs for high-speed and low-power applications.