Representations of Two-Variable Elementary Functions Using EVMDDs and Their Applications to Function Generators

摘要

This paper proposes a method to represent two-variable elementary functions using edge-valued multi-valued decision diagrams (EVMDDs), and presents a design method and an architecture for function generators using EVMDDs. To show the compactness of EVMDDs, this paper introduces a new class of integer-valued functions, l-restricted Mp-monotone increasing functions, and derives an upper bound on the number of nodes in an edge-valued binary decision diagram (EVBDD) for the l-restricted Mp-monotone increasing function. EVBDDs represent l-restricted Mp-monotone increasing functions more compactly than MTBDDs and BMDs when p is small. Experimental results show that all the two-variable elementary functions considered in this paper can be converted into l-restricted Mp-monotone increasing functions with p = 1 or p = 3, and can be compactly represented by EVBDDs. Since EVMDDs have shorter paths and smaller memory size than EVBDDs, EVMDDs can produce fast and compact elementary function generators.