Logic minimization and testability of 2-SPP networks

2-SPP networks are three-level EXOR-AND-OR forms with EXOR gates restricted to fan-in 2. We propose a heuristic algorithm for the synthesis of these networks in a form that is fully testable in the Stuck-At Fault Model. Previous works had presented exact algorithms for the minimization of unrestricted SPP networks and of 2-SPP networks. The exact minimization procedures were formulated as covering problems as well as in the minimization of SOP forms and had worst-case exponential complexity. Extending the expand-irredundant-reduce paradigm of Espresso in heuristic mode, we propose a minimization algorithm for 2-SPP networks that iterates local minimization and reshape of a solution until no further improvement can be achieved. The algorithm could escape from local minima using a LAST_GASP-like procedure. We study the testability of 2-SPP networks under the Stuck-At Fault Model (SAFM). We introduce the notion of EXOR-irredundancy to prove that EXOR-AND-OR irredundant 2-SPP networks are fully testable under the SAFM and guarantee that our algorithm yields EXOR-AND-OR irredundant solutions. We report a large set of experiments showing high-quality results with affordable run times, handling also examples whose exact solutions could not be computed.