A synthesis algorithm for two-level XOR based circuits

Author

Heap, Mark A. ; Rogers, William A. ; Mercer, M.R.

Author_Institution

ECE Dept., Texas Univ., Austin, TX, USA

fYear

1992

Firstpage

459

Lastpage

462

Abstract

A fast algorithm for minimizing the two-level AND/XOR representation of combinational functions, based on a graphical data structure similar to the OBDD, is described. This GMX (Graphical Minimizer for XORs) algorithm works by `reading-off´ and minimizing the solution from an augmented OBDD, called an SFG. The advantage of the SFG structure is that it is often of polynomial size. The algorithm generates solutions significantly better, or no worse, than all previously published solutions on a set of example circuits

Keywords

Boolean functions; circuit CAD; graph theory; logic CAD; minimisation of switching nets; spatial data structures; GMX; Graphical Minimizer for XORs; SFG; augmented OBDD; combinational functions; graphical data structure; polynomial size; subfunction graphs; two-level AND/XOR representation; two-level XOR based circuits; Circuit synthesis; Combinational circuits; Data structures; Equations; Error correction; Input variables; Iterative algorithms; Minimization; Neodymium; Programmable logic arrays;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Design: VLSI in Computers and Processors, 1992. ICCD '92. Proceedings, IEEE 1992 International Conference on

Conference_Location

Cambridge, MA

Print_ISBN

0-8186-3110-4

Type

conf

DOI

10.1109/ICCD.1992.276314

Filename

276314