Non-disjoint Decomposition Using r-admissibility and Graph Coloring and Its Application in Index Generation Functions Minimization

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

Functional decomposition is a crucial task in logic synthesis. In this paper we present a theory for finding such decomposition using the notion of r-admissibility and graph coloring. In particular, a method for generating the set of bound variables in the non-disjoint scheme is presented. We present the results of experiments, which apply proposed algorithm to minimize specific Boolean functions called index generation functions. In this way we prove that functional decomposition can efficiently reduce the size of used memory in memory-based logic synthesis.