On Optimum Linear Decomposition of Symmetric Index Generation Functions

This paper shows study results on linear decomposition of symmetric index generation functions. We analyze properties of symmetric index generation functions, and derive a theorem on the number of 1’s in a compound variable for linear decomposition. The paper presents an algorithm using the theorem to exactly minimize the number of linear functions in linear decomposition. By taking advantage of the theorem and the symmetry properties, the algorithm can find an optimum linear decomposition quickly. Experimental results using symmetric index generation functions show the efficiency of the proposed algorithm.