A framework for satisfying input and output encoding constraints
A. Saldanha, Tiziano Villa, Robert K. Brayton, Alberto Luigi Sangiovanni-Vincentelli · 1991
Three relevant encoding problems are input, output and state encoding.Several algorithms have been proposed for their solutions that decompose the problem into symbolic minimization (yielding a set of constraints) and constraint satisfaction.At least two exact formulations of the input encoding constraint satisfaction problem exist.However, a more important use of encoding is in state assignment of finite state machines where both input and output encoding constraints must be satisfied to obtain the most effective implementations.We develop a framework for the simultaneous satisfaction of input and output encoding constraints.We describe an algorithm, polynomial in the number of symbols to be encoded, to check for the existence of a solution for a set of input and output constraints.We provide an efficient atgorithm that determines the minimum number of encoding bits required to satisfy all the given constraints.We demonstrate how heuristic algorithms can be developed within the framework.Firtatly, we discuss the use of this framework in solving a variety of encoding problems with different cost functions.Some preliminary results on medium sized machines are given for both exact and heuristic algorithms.