Linear and Non-linear Decomposition of Index Generation Functions

T. Mazurkiewicz (Military Univ. of Techn., Poland), T. Łuba (Warsaw School of Computer Science, Poland)

Minimization of index generation functions attracts increasing interest lately. Methods proposed in the literature focus mainly on linear decomposition using XOR gates. In this paper we propose an algorithm using discernibility sets. We prove that it minimize standard benchmark functions as efficiently as the best-known algorithms. However, linear transformations seem to be insufficient for some functions. Therefore, we propose a novel approach to the minimization of index generation functions that uses non-linear transformations, i.e. AND gates. We provide examples showing that this technique can further reduce the number of input variables.