Title :
Generalized cofactoring for logic function evaluation
Author :
Jiang, Yunjian ; Matic, Slobodan ; Brayton, Robert K.
Author_Institution :
Univ. of California, Berkeley, CA, USA
Abstract :
Logic evaluation of a Boolean function or relation is traditionally done by simulating its gate-level implementation, or creating a branching program using its binary decision diagram (BDD) representation, or using a set of look-up tables. We propose a new approach called generalized cofactoring diagrams, which are a generalization of the above methods. Algorithms are given for finding the optimal cofactoring structure for free-ordered BDD´s and generalized cube cofactoring under an average path level (APL) cost criterion. Experiments on multi-valued functions show superior results to previously known methods by an average of 30%. The framework has direct applications in logic simulation, software synthesis for embedded control applications, and functional decomposition in logic synthesis.
Keywords :
Boolean functions; binary decision diagrams; embedded systems; function evaluation; logic design; logic gates; logic simulation; logic testing; Boolean function; binary decision diagram; cofactoring structure; cube cofactoring; embedded control application; free-ordered BDD; functional decomposition; generalized cofactoring; logic function evaluation; logic simulation; logic synthesis; software synthesis; Algorithm design and analysis; Application software; Binary decision diagrams; Boolean functions; Computational modeling; Computer simulation; Data structures; Discrete event simulation; Logic design; Logic functions;
Conference_Titel :
Design Automation Conference, 2003. Proceedings
Print_ISBN :
1-58113-688-9
DOI :
10.1109/DAC.2003.1218924