Great Lakes Symposium on VLSI '98 An Exact Input Encoding Algorithm for BDDs Representing FSMs Lafayette, Louisiana February 19-February 24 ISBN: 0-8186-8409-7
We address the problem of encoding the state variables of a finite state machine such that the BDD representing its characteristic function has the minimum number of nodes. We present an exact formulation of the problem. Our formulation characterizes the two BDD reduction rules by deriving conditions under which these reduction rules can be applied. We then provide an algorithm that finds these conditions and solves the problem by formulating it as a 2-CNF formula and extracting all its prime implicants. In addition to this, we implemented a simulated annealing algorithm for this problem and provide a thorough experiment of the impact of encoding on a BDD representing an FSM with different orderings.
Index Terms:
multi-valued decision diagrams, binary decision diagrams, input encoding, finite state machines.
Citation:
Wilsin Gosti, Alberto L. Sangiovanni-Vincentelli, Tiziano Villa, Alexander Saldanha, "An Exact Input Encoding Algorithm for BDDs Representing FSMs," glsvlsi, pp.294, Great Lakes Symposium on VLSI '98, 1998 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb