Minimization of EP-SOPs via Boolean relations

Generalized Shannon decomposition with remainder restructures a logic function into subsets of points defined by the generalized cofactors with a remainder, yielding three logic blocks. EXOR-Projected Sums of Products (EP-SOPs) are an important form of such decomposition. In this paper we propose a Boolean synthesis technique for EP-SOPs, more general than the algebraic methods investigated so far. We exploit the don't care conditions induced by the structure of the implementation, by casting synthesis for minimum area as a problem of Boolean relation minimization that captures all valid implementations of the circuit, obtaining by construction the most compact one. We report experiments confirming the effectiveness in area of the proposed approach based on Boolean relations, with better run times for some cost functions.