Perturb and simplify: multilevel Boolean network optimizer

TitlePerturb and simplify: multilevel Boolean network optimizer
Publication TypeJournal Article
Year of Publication1996
AuthorsChang, S-C, Marek-Sadowska, M, Cheng, K-T
JournalComputer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Pagination1494 -1504
Date Publisheddec
Keywordsautomatic test pattern generation, Boolean functions, circuit optimisation, combinational circuits, iteration, iterative methods, logic CAD, logic optimization techniques, logic synthesis, logic testing, MCNC benchmarks, multilevel Boolean network optimizer, multilevel combinational networks, multivalued logic circuits
AbstractIn this paper, we present logic optimization techniques for multilevel combinational networks. Our techniques apply a sequence of perturbations which result in simplification of the circuit. The perturbation and simplification is achieved through wires/gates addition and removal which are guided by the Automatic Test Pattern Generation (ATPG) based reasoning. The main operations of our approaches are incremental transformations of the circuit (such as adding wires/gates and changing gate's functionality) to remove some particular wire, At each iteration, a summary information of such wires/gates addition and removal is precomputed first. Then, a transformation is chosen to remove several wires at once. We have performed experiments on MCNC benchmarks and compared the results to those of misII and RAMBO. Experimental results are very encouraging