Variable reordering for shared binary decision diagrams using output probabilities

Author

Thornton, M.A. ; Williams, J.P. ; Drechsler, R. ; Drechsler, N.

Author_Institution

Dept. of Comput. Sci., Arkansas Univ., Fayetteville, AR, USA

fYear

1999

fDate

1999

Firstpage

758

Lastpage

759

Abstract

The shared binary decision diagram (SBDD) with negative edge attributes can represent many functions in a compact form if a proper variable ordering is used. In this work we describe a technique for reordering the variables in an SBDD to reduce the size of the data structure. We use a heuristic to formulate a technique for the reordering problem based on probability metrics

Keywords

binary decision diagrams; data structures; probability; SBDD; data structure; heuristic; negative edge attributes; output probabilities; probability metrics; shared binary decision diagrams; variable reordering; Binary decision diagrams; Boolean functions; Circuits; Computer science; Data structures; Heuristic algorithms; Histograms; Identity-based encryption;

fLanguage

English

Publisher

ieee

Conference_Titel

Design, Automation and Test in Europe Conference and Exhibition 1999. Proceedings

Conference_Location

Munich

Print_ISBN

0-7695-0078-1

Type

conf

DOI

10.1109/DATE.1999.761217

Filename

761217

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2758236