Cj. Shi et Ja. Brzozowski, AN EFFICIENT ALGORITHM FOR CONSTRAINED ENCODING AND ITS APPLICATIONS, IEEE transactions on computer-aided design of integrated circuits and systems, 12(12), 1993, pp. 1813-1826
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.