Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization

Abstract

This paper presents a logic synthesis method for look-up table (LUT) based eld programmable gate ar-rays (FPGAs). We determine functions to be mapped to LUTs by functional decomposition. We use not only disjunctive decomposition but also nondisjunctive de-composition. Furthermore, we propose a new Boolean resubstitution technique customized for an LUT net-work synthesis. Resubstitution is used to determine whether an existing function is useful to realize an-other function; thus, we can share the common func-tion among two or more functions. The Boolean re-substitution is eectively carried out by solving a sup-port minimization problem for an incompletely speci-ed function. We can also handle satisability don't cares of an LUT network using the technique. 1