An implicit algorithm for support minimization during functional decomposition

Abstract

Functional decomposition is an important synthesis technique for lookup table based FPGAs. Given a partitioning of a function's input variables into bound set and free set, the extracted subfunctions usually depend on all bound set variables. We show that this, however, is often not necessary. We present an implicit algorithm that finds subfunctions with a minimal support among the huge number of possible subfunctions. Our approach includes non-disjoint decompositions as a special case. The algorithm is very fast due to the use of implicit techniques. Experimental results show substantial area reductions.