Totally undecomposable functions: applications to efficient multiple-valued decompositions
Tsutomu Sasao · 2003
A function f:P/sup n//spl rarr/P, P={0, 1, ..., p-1} is k-decomposable iff f can be represented as f(X/sub 1/, X/sub 2/)=g(h/sub 1/(X/sub 1/), h/sub 2/(X/sub 1/), ..., h/sub k/(X/sub 1/), X/sub 2/), where (X/sub 1/, X/sub 2/) is a bipartition of input variables. This paper introduces the notion of totally k-undecomposable functions. By using this concept, we can drastically reduce the search space to find k-decompositions. A systematic method to find the bipartitions of input variables that will not produce any k-decompositions is presented. By combining it to the conventional decomposition methods, we can build an efficient functional decomposition system. This method is promising to design LUT-based FPGAs.