A unifying approach to edge-valued and arithmetic transform decision diagrams

Abstract

This paper shows that binary decision diagrams (BDDs) and their generalizations are not only representations of switching and integer-valued functions, but also Fourier-like series expansions of them. Furthermore, it shows that edge-valued binary decision diagrams (EVBDDs) are related to arithmetic transform decision diagrams (ACDDs), which are the integer counterparts of the functional decision diagrams (FDDs). Finally, it shows that the complexity of multi-terminal binary decision diagrams (MTBDDs), EVBDDs and ACDDs of a function f depends on the structure of the truth-vector of f, partial arithmetic transform spectra of f and the arithmetic transform spectrum of f, respectively.