Fast Optimal Synthesis of Symmetric Index Generation Functions

Index generation functions are needed in many applications to reduce the number of variables used to select the related result. Examples of such applications are switches that route the packages of the internet, the detection of viruses of computers, or the analysis of DNA sequences. Several approaches have been suggested to find the decomposition into the linear part L and the general part G of circuits for the special case of symmetric index generation functions \(S^n_1(\mathbf {x})\). Recently an approach for this task has been published by Nagayama et al. that found exact solutions much faster than known approaches, but is also limited in the number n of variables of the symmetric function due to the needed computation time. In this chapter, we suggest an approach that solves the same task in such a short time (less than 1 μs for n = 1, 000, 000, 000) so that no restriction in the number n of variables x of the decomposed symmetric functions \(S^n_1(\mathbf {x})\) must be taken in to account anymore. We created extremely fast algorithms using our already published method of a very deep analysis of the given problem.