IngentaConnect Dynamic Re-Encoding During MDD Minimization

Authors: SCHMIEDLE F.¹; GU¨NTHER W.¹; DRECHSLER R.²

Source: Multiple Valued Logic: An International Journal, Volume 8, Numbers 5-6, 1 January 2002 , pp. 625-643(19)

Abstract:

Multi-valued decision diagrams (MDDs) are a generalization of binary decision diagrams (BDDs). They often allow efficient representation of functions with multi-valued input variables similar to BDDs in the binary case. Therefore they are suitable for several applications in synthesis and verification of integrated circuits. MDD sizes counted in number of nodes vary from linear to exponential dependent on the variable ordering used. In all these applications, minimization of MDDs is crucial.

In many cases, multi-valued variables are composed by a certain number of binary variables, and so the multi-valued inputs arise by grouping binary variables. The selection of these groups, that is, the decision which variables to merge, has enormous impact on MDD sizes. Techniques for finding variable groupings before starting MDD minimization have been proposed recently.

In this paper, we present a new method that uses re-encoding, i.e. dynamic variable grouping. We don't choose one fixed variable grouping before minimizing MDDs, but allow to change the binary variables to be considered together during the minimization process. This is possible since MDDs are simulated on top of BDDs. By this, the underlying binary variables remain accessible throughout the minimization process. This technique is described in detail and we also show experimental results that demonstrate the efficiency of our approach.

Keywords: Decision diagram; MDD minimization; Variable ordering; Variable grouping

Document Type: Research article

Affiliations: 1: Institute of Computer Science, Albert-Ludwigs-University Chair of Computer Architecture (Prof. Dr. Bernd Becker), Georges-Ko¨hler-Allee 51, 79110 Freiburg im’Breisgau, Germany 2: Institute of Computer Science, University of Bremen, 28359 Bremen, Germany

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$45.29 plus tax Refund Policy