Spectral Logic and Its Applications for the Design of Digital Devices

CHAPTER 4

SPECTRAL METHODS IN OPTIMIZATION OF DECISION DIAGRAMS

This chapter is devoted to the minimization of basic characteristic of decision diagrams for representation of discrete functions. We will also provide a spectral interpretation of decision diagrams and based on it define decision diagrams derived from the Haar transform.

The main interest will be focused on decision diagrams for switching functions and their integer equivalent functions. In particular, we will discuss minimization of Binary Decision Diagrams (BDDs) by autocorrelation functions, minimization of planar BDDs by using Walsh coefficients, and minimization of Haar diagrams by using again the autocorrelation coefficient.

The complexity of a decision diagram is usually estimated as the number of nodes, called the size of the BDD. In the case of switching functions, it is enough to consider the nonterminal nodes, since the constant nodes always represent two logic values 0 and 1.

The size of a BDD is very sensitive to the order of variables, ranging from the polynomial to the exponential complexity for the same function for different orders of variables. Therefore, majority of the approaches to the reduction of sizes of BDDs is related to developing efficient algorithms for reordering of variables, see References 185 and 478. Linearly transformed BDDs (LT-BDDs) are defined by allowing linear combinations of variables (220). In this way, the number of possible transformations of variables is increased from ...