Circuit design from Kronecker Galois field decision diagrams for multiple-valued functions

Abstract

In this paper we define the Kronecker Galois Field Decision Diagrams (KGFDDs), a generalization of Kronecker Decision Diagrams (KDDs) to the representation of Multiple-Valued (MV) functions. Starting from the Multi-place Decision Diagrams (MDDs) and Galois Field Decision Diagrams (GFDDs) we give a generalization that allows more compact representation with respect to the nodes needed. Based on KGFDDs we present a new method for circuit design for MV circuits. In contrast to previously presented approaches the resulting circuits have only logarithmic (instead of linear) depth.