Non-Abelian groups in optimization of decision diagrams representations of discrete functions

Abstract

This paper is devoted to the reduction of decision diagram (dd) representations of discrete functions by using the non-abelian groups and Fourier DDs on these groups. The number of levels in a DD can be reduced through decomposition of the domain group of the represented function into large subgroups. That approach however increases the number of nodes per levels which may decrease the global reduction possibilities in the DD. At the same time, the nodes with a considerable number of outgoing edges are required. In applications, the complexity, thus the price, of a node is proportional to the number of outgoing edges. From an inspection of optimization methods for DDs representations, it follows that a solution of this problem can hardly be found with DDs on Abelian groups. Therefore, we are proposing the use of Fourier DDs on finite non-abelian groups. In that way, the matrix-valued decision diagrams are introduced, since in Fourier DDs on non-abelian groups some of constant nodes are matrices. These Dds permit two-steps optimization. First we determine the optimal structure of the corresponding decision tree by the reduction of which a DD is derived. The optimization is done with respect to the combination of the number of nodes and levels we may require depending on the application intended. Then, we do the optimization of the representations of matrix-valued constant nodes by ordinary DDs of smaller size. In that way, the complex-valued and integer-valued Fourier DDs are derived depending on the chosen group representations for these applications where the matrix-valued Fourier DDs may not be allowed. With thus derived Fourier DDs, the reduction of both number of levels and non-terminal nodes may be achieved. Efficiency of representations with the Fourier DDs on non-abelian groups is illustrated by the example of DDs representations of n-bit multipliers.