Decision diagram method for calculation of pruned Walsh transform

Discrete Walsh transform is an orthogonal transform often used in spectral methods for different applications in signal processing and logic design. P ET-like algorithms make it possible to efficiently calculate the discrete W alsh spectrum. However. for their exponential complexity, these algorithms are practically unsuitable for large functions. For this reason. a Binary D ecision Diagram (BDD) based recursive method for Walsh spectrum calculation has been introduced in [4]. A disadvantage of this algorithm is that the r esulting Multi-Terminal Binary Decision Diagram (MTBDD) representing the Wa lsh spectrum for f can be large for some functions. Another disadvantage tu rns out if particular Walsh coefficients are to be computed separately. The algorithm always calculates the entire spectrum and, therefore, it is rath er inefficient for applications where a subset of Walsh spectral coefficien ts. i.e., the pruned Walsh spectrum. is required. In this paper. we propose another BDD-based method for Walsh spectrum calculation adapted for applic ation where the pruned Walsh spectrum is needed. The method takes advantage of the property that. for most switching functions, the size of a BDD for f is usually quite a bit smaller than the size of the MTBDD for the Walsh s pectrum. In our method, a MTBDD representing the Walsh spectrum is not cons tructed. Instead. two additional fields are assigned to each node in the BD D for the processed function f. These fields are used to store the results of intermediate calculations. Pairs of spectral coefficients are calculated and stored in the fields assigned to the root node. Therefore, the calcula tion complexity of the proposed algorithm is proportional to the size of th e BDD for f whose spectrum is calculated. Experimental results demonstrate the efficiency of the approach.