Totally undecomposable functions: applications to efficient multiple-valued decompositions

A function f:Pⁿ→P, P={0, 1, ..., p-1} is k-decomposable iff f can be represented as f(X₁, X₂)=g(h₁(X₁), h₂(X₁ ), ..., h_k(X₁), X₂), where (X₁, X₂) 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