A Method of logic synthesis for Pal-Based CPLD-S, based on Two-Stage decomposition 1

The paper presents a novel method of logic synthesis dedicated for PAL based CPLD-s. The method is based on two-stage decomposition. The key point of the algorithm lies in sequential search for a decomposition providing feasibility of implementation of the Free Block in one PAL-based logic block containing a limited number of product terms. For this purpose a novel concept of graph is used - the Row Incompatibility and Complement Graph. The method is an alternative to the classical approach based on two-level minimization of separate single-output functions. The paper presents also results of experiments, and a comparison of the proposed algorithm vs. the classical method, and commercial tools.