This paper deals with the number of paths in multiterminal binary decision diagrams (MTBDDs) and shared binary decision diagrams (SBDDs) representing a set of Boolean functions. It is shown that the number of paths in an MTBDD (SBDD) can be uniquely determined by values of specific weighted-autocorrelation coefficients. An analytical expression for the number of paths as a linear function of the values of the weighted-autocorrelation coefficients is presented. Based on this expression, a method of minimization of the number of paths is proposed. The method is based on replacing the initial set of input variables with their linear combinations. By using this method, a deterministic paths-reduction procedure, which provides MTBDDs and SBDDs with a reduced number of paths, is presented. The efficiency of the suggested approach is demonstrated on benchmark functions.

Decision diagrams (DDs) are a data structure that allows compact representation of discrete functions. The efficient construction of DDs in terms of space and time is often considered problem. A particular problem is that during the construction of a DD, a large number of temporary nodes are created. We address this problem in the case when the functions are specified in the PLA format. A common practice is to construct a DD by recursively processing all the cubes in PLA specification. The DD representing a subfunction defined by a single cube is merged with the DD for the subfunction defined by all the previously processed cubes. We proposed a method of reordering and partitioning the set of cubes in PLA specification that results in the reduction of both space and time complexities of the construction of DDs. First, we arrange cubes by their suffices. Then we partition the set of cubes, construct DDs for the subfunctions representing each partition separately, and merge them into a final DD. The reordering and partitioning ensures that these intermediary decision diagrams never exceed a certain size which is controlled by the size of the partitions. In this way, the number of operations on the nodes during the merging decision diagrams is reduced. This reduction results in a decrease both in the number of temporary nodes and construction time. The proposed method is used for the construction of DDs for the set of standard benchmark functions. The experiments show that the total number of created nodes is reduced on average by 34.65 percent, while the construction time is decreased by 48.6 percent.

Reed-Muller expressions and their various extensions and generalizations for binary and multiple-valued logic functions are an important class of discrete function representations that are often used in practical applications. These expressions can be uniformly viewed as discrete polynomial expressions over finite fields GF(2) and GF(q) or the field of rational numbers in the case of expressions with integer-valued coefficients. The optimization of them in the number of product terms count is performed by selecting either positive or negative literals (polarities) for variables in the functions to be represented. Since there are no ways to select in advance the polarity for variables that will result in most compact expression for a given function, all possible expressions have to be generated and the simplest of them selected. This is a task computationally very demanding, the complexity of which is O(q^n \times C), where C is the time to calculate a particular polarity. Since the reduction of the first factor may lead to missing the most compact expression, the reduction of C is the single option to speed up the procedure. In this paper, we propose an approach to the solution of this problem by exploiting the notion of extended dual polarity, which provides a simple way of ordering polarities to obtain an effective way of finding the optimal one by reducing the time to move between them. The method still implies exhaustive search, but it is an optimized search, which may be expressed in very simple rules resulting in efficient implementation. Experimental results illustrate the effectiveness of the proposed method.

This paper discusses reduction of the number of product terms in representation of totally symmetric Boolean functions by Sum of Products (SOP) and Fixed Polarity Reed- Muller (FPRM) expansions. The suggested method reduces the number of product terms, correspondingly, the implementation cost of symmetric functions based on these expressions by exploiting Gray decoding of input variables. Although this decoding is a particular example of all possible linear transformation of Boolean variables, it is efficient in the case of symmetric functions since it provides a significant simplification of SOPs and FPRMs. Mathematical analysis as well as experimental results demonstrate the efficiency of the proposed method.

This paper discusses optimization of decisions diagrams (DDs) by total autocorrelation functions. We present an efficient algorithm for construction of linearly transformed binary decision diagrams (LT-BDDs) and Linearly transformed multiterminal BDDs (LT-MTBDDs) for systems of Boolean functions, based on linearization of these functions by the corresponding autocorrelation functions. Then, we present a method for reduction of sizes of DDs by a level-by-level reduction of the width of DDs using the total autocorrelation functions. The approach provides for a simple procedure for minimization of LT-BDDs and LT-MTBDDs and upper bounds on their sizes. Experimental results for benchmarks illustrate that the proposed method on average is very efficient.

In this paper, we propose an approach to the reduction of sizes of multi-terminal binary decision diagrams (MTBDDs) by using the copy properties of discrete functions. The underlying principles come from copy theory of discrete signals considered previously. We propose two modifications of MTBDDs, called copy DDs (CDDs) and half copy DDs (HCDDs), using the corresponding copy operations from copy theory. Functions having different types of copy properties can be efficiently represented by the proposed Copy DDs. Examples are Walsh and Reed-Muller functions as well as different binary codes.

Discrete Walsh transform is an orthogonal transform often used in spectral methods for different applications in signal processing and logic design. FFT-like algorithms make it possible to efficiently calculate the discrete Walsh spectrum. However, for their exponential complexity, these algorithms are practically unsuitable for large functions. For this reason, a Binary Decision Diagram (BDD) based recursive method for Walsh spectrum calculation has been introduced in Clarke et al. (1993). A disadvantage of this algorithm is that the resulting Multi-Terminal Binary Decision Diagram (MTBDD) representing the Walsh spectrum for f can be large for some functions. Another disadvantage turns out if particular Walsh coefficients are to be computed separately. The algorithm always calculates the entire spectrum and, therefore, it is rather inefficient for applications where a subset of Walsh spectral coefficients, i.e., the pruned Walsh spectrum, is required. In this paper, we propose another BDD-based method for Walsh spectrum calculation adapted for application 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 spectrum. In our method, a MTBDD representing the Walsh spectrum is not: constructed. Instead, two additional fields are assigned to each node in the BDD 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 calculation complexity of the proposed algorithm is proportional to the size of the BDD for f whose spectrum is calculated. Experimental results demonstrate the efficiency of the approach.

This paper discusses early work by Komamiya in Reed-Muller and arithmetic expressions for switching functions.

This paper classifies different decision diagrams (DDs) for discrete functions with respect to the domain and range of represented functions. Relationships among different DDs and their relations to spectral transforms are also shown. That provides a unified interpretation of DDs, and their further classification with respect to the spectral transforms.

This paper describes the relationship between the Walsh transform and Hadamard matrices. It is an attempt to establish the correct terminology in spectral techniques for logic design.

In this paper we give a spectral transform interpretation of AND-EXOR representations of switching functions and related decision diagrams in the vector space over GF(2). The consideration is uniformly extended to the Fourier series-like expressions of functions in the complex vector space and the decision diagrams for integer-valued functions. It is shown that the multi-terminal decision diagrams, MTBDDs, and edge-valued decision diagrams, EVBDDs, for integer-valued functions are derived by using the same sets of basic functions already applied for the decision diagrams attached to some AND-EXOR expressions, but considered over the complex field. The algebraic transform decision diagrams, ATDDs, are considered as the integer counterparts of the functional decision diagrams, FDDs, attached to the algebraic transform in the same way as the FDDs are attached to the Reed-Muller expressions. It is shown that the EVBDDs are the ATDDs in different notation.