An Efficient Interpolation-Based Projected Sum of Product Decomposition via Genetic Algorithm
Tai-Lin Chen, Chun-Yao Wang, Ching-Yi Huang and Yung-Chih Chen
Projected Sum of Products (P-SOP) is a bounded multi-level representation. The synthesis of P-SOP representation is based on decomposing the input space with respect to the orthogonal basis x’i ⊕p(X(i)) and xi ⊕p(X(i)) where xi is an input variable and p(X(i)) is a function of all variables except xi. Different p(X(i)) may result in different areas after synthesis. Therefore, to obtain a minimal P-SOP circuit, it is important to select an appropriate variable xi and function p(X(i)). In this paper, we propose a Genetic Algorithm to efficiently determine xi and p(X(i)). Experimental results show that the proposed approach saves 81% CPU time in searching such a pair as compared to an exhaustive method without sacrificing the optimality.
Keywords: Logic synthesis, interpolation, optimization, EX-OR network, generic algorithm, functional decomposition