Title :
Exact minimization of determinant decision diagrams
Author :
Manthe, Alicia ; Shi, C. J Richard
Author_Institution :
Dept. of Electr. Eng., Univ. of Washington, Seattle, WA, USA
fDate :
29 June-1 July 2002
Abstract :
Determinant decision diagram (DDD) is a canonical and compact representation of symbolic expressions in the form of circuit matrix determinants and cofactors for symbolic circuit analysis. DDD-based symbolic analysis algorithms have time and space complexities proportional to the number of DDD vertices. In this paper, we first present a theoretical characterization of the worst-case complexity of the minimal DDDs. We then present an exact algorithm to minimize the number of DDD vertices incorporating both a lower bound and upper bound for pruning the search space. Experimental results are presented to demonstrate the effectiveness of the proposed algorithm and the validity of theoretical analysis.
Keywords :
analogue circuits; circuit analysis computing; circuit complexity; decision diagrams; determinants; matrix algebra; minimisation; symbol manipulation; DDD; DDD vertices; DDD-based symbolic analysis algorithms; canonical compact representation; circuit matrix cofactors; circuit matrix determinants; determinant decision diagrams; exact minimization; search space bounds; space complexities; symbolic circuit analysis; symbolic expressions; time complexities; worst-case complexity; Algorithm design and analysis; Analog circuits; Boolean functions; Circuit analysis; Data structures; Engineering profession; Heuristic algorithms; Minimization methods; Transfer functions; Upper bound;
Conference_Titel :
Communications, Circuits and Systems and West Sino Expositions, IEEE 2002 International Conference on
Print_ISBN :
0-7803-7547-5
DOI :
10.1109/ICCCAS.2002.1179035