A New Approach to Three-Level Logic Synthesis
Three-level logic SPP forms are OR of AND of EXORs expressions.
In the framework of SPP minimization we give a new
algebraic definition of SPP expressions using affine spaces.
The main problems of SPP model are: the
``hard to digest'' SPP theory; the time required for
minimization, which is still high; and the unbounded fan-in EXOR gates in
the form. Consequently, our main results in this paper are: 1)
we rephrase the SPP theory using well known algebraic structures
(vector and affine spaces) to obtain an easier description of pseudocubes,
which play the same role as cubes in
standard minimization; 2) we describe a new canonical representation of
pseudocubes leading to a more efficient data structure for SPP
minimization; 3) we introduce a novel form, called k-SPP
form}, where the number of literal in the EXOR factors is upper
bounded by a chosen constant $k$, and show how to modify the
SPP algorithms for computing the minimal
k-SPP form efficiently. Finally, we perform an extensive set of experiments
on classical benchmarks aimed at validating the new approach.