Generating synthetic MVL benchmarks from random MDDs under restrictions

Abstract

Since standard benchmark functions for analysis of multiple-valued logic (MVL) designs are not widely available, benchmark functions for binary logic design are often used in this area after an appropriate encoding of function values and possibly padding with zeros. Such generated MVL benchmarks might not express inherent properties of MVL functions. Synthetic benchmark MVL functions are an alternative and their construction is an interesting problem. Various restrictions imposed on the structure of decision diagrams, i.e., distribution of nodes and their interconnections; lead to functions expressing various properties. Based on this observation, we propose a method for generating synthetic MVL benchmark functions derived from randomly generated multiple-valued decision diagrams (MDD) under certain structural restrictions. We consider four different structural parameters: The number of levels, the maximal size, i.e., the total number of nodes, the maximal width, and the average edge length. Experimental results are provided to illustrate the efficiency of the proposed method.