Reduction of Average Path Length in Binary Decision Diagrams by Spectral Methods

This paper deals with analytic methods for the calculation and reduction of the average path lengths (APLs) in binary decision diagrams (BDDs). Usually, information-theoretic measures and information-theoretic techniques are used to construct BDDs of minimal APLs. Specifically, the mutual information between a Boolean function and its variables and the Shannon-Fano prefix coding are utilized. This paper deals with the problem of the APL reduction by using spectral techniques. Particularly, methods based on the properties of the Walsh spectrum of a Boolean function and its autocorrelation function are discussed. It is shown that the APL is a linear function of the autocorrelation values, that is, the APL depends on the Boolean function´s properties in the time domain (autocorrelation) rather on the Boolean function´s properties in the frequency domain (Walsh spectrum). In addition, it is shown that information-theoretic criteria like the mutual information or the conditional entropy are equivalent to frequency-domain criteria. Consequently, existing information-theoretic approaches for APL reduction that are based on mutual-information criterion or the Walsh transform coefficients may derive a suboptimal APL. The representation of the APL as a function of the autocorrelation values opens a way to determine the optimal ordering of the input variables analytically. Two procedures for APL reduction by ordering and by using linear combinations of the input variables are presented: (1) minimization by using the autocorrelation values and (2) minimization by using the mutual information between the Boolean function and a linear function of the input variables. The time-domain approach may derive a linearized BDD of a lower APL, whereas the information-theoretic approach has a lower computational complexity with comparable performance. Experimental results show the efficiency of the suggested techniques.