A Fast Method for Exactly Optimum Linear Decomposition of Index Generation Functions
Shinobu Nagayama, Tsutomu Sasao and Jon T. Butler
Linear decomposition of index generation functions is a representation of index generation functions using two kinds of functions: linear functions and a function storing indices. Minimization of the number of linear functions in a linear decomposition is required for efficient implementation of index generation functions. This paper proposes a fast method to exactly minimize the number of linear functions, and shows its time and space complexities. The complexities are large because of the exact optimization method. But, experimental results show that actual computation time and memory size are quite small. This is because the proposed method searches for an optimum solution efficiently based on a dynamic programming method using zero-suppressed binary decision diagrams (ZDDs).
Keywords: Index generation functions, functional decomposition, linear decomposition, zero-suppressed binary decision diagrams, logic design, dynamic programming method