NSP kernel finder - A methodology to find and to build non-series-parallel transistor arrangements

The transistor arrangement optimization is an effective possibility to improve logic gates and, consequently, VLSI design. This paper presents a graph-based methodology to determine if an ISOP may be implemented in non-series-parallel (NSP) switch arrangement. The proposed method aims to combine the cubes of such ISOP to build a graph where the vertices represent the cubes and the edges exist whether the vertices have common literals. Hence, if the obtained graph has the same topology of a `bridge´ arrangement and each cube has all literals shared through the edges, this ISOP may be efficiently implemented through a NSP transistor network. The experiments were performed over the set of 4-input P-class Boolean functions, and the results were compared to the Moore´s catalog. These experiments demonstrate that the proposed method tends to deliver optimal solutions for unate functions. Moreover, the method was able to determine equivalent SP or NSP transistor arrangements in 82.69% of the cases when considering a set of non-unate functions.