An implicit algorithm for support minimization during functional decomposition
Christian Legl, Bernd Wurth, Klaus Eckl · 1996
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. 1 Introduction Functional decomposition based on the seminal work by Ashenhurst, Curtis, Roth and Karp [1, 2] has attracted considerable attention in the last years [3, 4, 5, 6, 7, 8, 9, 10, 11]. The main reason is the increasing importance of lookup table (LUT) based FPGAs. A k-LUT implements any Boolean function of k inputs. Functional decomposition is well suited for technology m...