AN EFFICIENT ALGORITHM FOR CONSTRAINED ENCODING AND ITS APPLICATIONS

In this paper, an efficient algorithm and its implementation ENCORE ar e presented for finding approximate solutions to dichotomy-based const rained encoding, a problem fundamental to the synthesis of combination al logic circuits, and synchronous and asynchronous sequential circuit s. ENCORE adopts a greedy strategy to find an encoding bit by bit, and then uses an iterative method to improve the solution quality. The no velty of our algorithm lies mainly in a linear-time heuristic to selec t each individual bit; this problem was previously solved in quadratic time. ENCORE has been applied to a variety of practical problem insta nces. For a number of examples found in the literature on the synthesi s of asynchronous sequential machines, ENCORE consistently obtains opt imal or near-optimal results. For the optimum state assignment of the MCNC FSM benchmarks, ENCORE generates the same or even shorter encodin g lengths than the programs KISS, NOVA and DIET, but takes much less C PU time. It is demonstrated for the first time that PLA implementation s of synchronous FSMs using dichotomy constraints compare very favorab ly with respect to area with those based on traditional group constrai nts.