AN XOR-BASED DECOMPOSITION DIAGRAM AND ITS APPLICATION IN SYNTHESIS OF AND XOR NETWORKS/

In this paper, we introduce a Shared Multiple Rooted XOR-based Decompo sition Diagram (XORDD) to represent functions with multiple outputs. B ased on the XORDD representation, we develop a synthesis algorithm for general Exclusive Sum-of-Product forms (ESOP). By iteratively applyin g transformations and reductions, we obtain a compact XORDD which give s a minimized ESOP. Our method can synthesize larger circuits than pre viously possible. The compact ESOP representation provides a form that is easier to synthesize for XOR heavy multi-level circuits, such as a rithmetic functions. We have applied our synthesis techniques to a lar ge set of benchmark circuits in both PLA and combinational formats. Re sults of the minimized ESOP forms obtained from our synthesis algorith m are also compared to the SOP forms generated by ESPRESSO. Among the 74 circuits we have experimented with, the minimized ESOP's have fewer product terms than those of SOP's in 39 circuits.