Synthesis of Autosymmetric Functions in a New Three-Level Form

Autosymmetric functions exhibit a special type of regularity that can speed-up the minimization process. Based on this autosymmetry, we propose a three level form of logic synthesis, called ORAX (EXOR-AND-OR), to be compared with the standard minimal SOP (Sum of Products) form. First we provide a fast ORAX minimization algorithm for autosymmetric functions. The ORAX network for a function f has a first level of at most 2(n−k) EXOR gates, followed by the AND-OR levels, where n is the number of input variables and k is the “autosymmetry degree” of f. In general a minimal ORAX form has smaller size than a standard minimal SOP form for the same function. We show how the gain in area of ORAX over SOP can be measured without explicitly generating the latter. If preferred, a SOP expression can be directly derived from the corresponding ORAX. A set of experimental results confirms that the ORAX form is generally more compact than the SOP form, and its synthesis is much faster than classical three-level logic minimization. Indeed ORAX and SOP minimization times are often comparable, and in some cases ORAX synthesis is even faster.