Product Transformation and Heuristic EXOR-AND-OR Logic Synthesis of Incompletely Specified Functions

Previously, the synthesis of reversible and quantum permutative circuits based on products of Exclusive-OR (EXOR) sums of inputs (POE) was explored as an approach to reduce quantum cost. Herein, the mathematical representation used in POE expressions is formally detailed and contrasted with the pseudoproduct-based theory of Luccio and Pagli. The theory and practice of product transformation, or computation of equivalent POE expressions, is presented. To demonstrate the generality of the mathematical representations outside of the reversible domain, a new method to synthesize incompletely specified functions as EXOR-AND-OR circuits is introduced. The method is heuristic. It first uses spectral information from the Walsh-Hadamard transform to compute a set of POE implicants for a function, and then uses product transformation to minimize both the total number of literals and unique EXOR sums (ignoring polarity) used in the POE implicants. The product transformation minimization extends to multioutput functions. The new method has no performance guarantees, i.e., it does not have a fallback mode of minimum or near-minimum sum of products; therefore, it is suited to a tournament synthesis approach. When synthesizing benchmark functions of up to 26 inputs, the new method is shown to typically produce lower cost circuits than heuristic pseudoproduct-based methods.

I. Introduction

Logic synthesis based on Exclusive-OR (EXOR) sums can reduce gate counts and has application in various technologies, making it an active area of research. Previously, reversible three-level logic synthesis based on products of EXOR sums of inputs (POE) was explored as a means to reduce cost [1] in no-ancilla-line reversible and quantum permutative circuits [2]. The mathematical representation of POE (EXOR-AND) expressions is based on the Galois field 2 [GF(2)] linear transform approach used by Meinel and Theobald [3], Günther and Drechsler [4], and Karpovsky et al. [5]. In a different line of research pioneered by Luccio and Pagli [6] irreversible three-level logic synthesis is based on a pseudoproduct EXOR-AND formulation. Later works applied the pseudoproduct formulation to heuristic logic synthesis methods [7]–[9] for EXOR-AND-OR circuits, and these methods consistently produce more compact expressions than AND-OR sum of products (SOP) logic synthesis methods. In CMOS technology this correlates to reduced area, capacitance, and dynamic power consumption.