An input-output encoding approach for serial decomposition

Functional decomposition (FD) is a process of breaking a complex and large function into smaller and simpler sub-functions. There exist two strategies in FD (1) Serial and (2) Parallel Decomposition. In this paper we deal with the problem of generating smaller sub-functions (predecessor and successor functions) of serial decomposition during the encoding process. The set of non-disjoint Maximal Compatible Classes (MCCs) are determined using a set covering approach. The algorithm proposed generates a set of Optimal Maximal Compatible Classes (OMMCs) from a non-disjoint set of MCCs. The set of disjoint or non-disjoint OMCCs generated has the following characteristics (1) maximal don´t cares in the inputs and output of the predecessor sub-function (2) minimal Face Embedded Constraints (3) maximal Hypercube Embedded Constraints. Maximal Weighted Bipartite Matching (MWBM) algorithm is used to solve the problem of determining the set of OMCCs. An input-output weighted graph approach is also presented to assign symbols or codes to the output of the predecessor sub-function. The algorithm has been implemented and tested on the MCNC and Espresso benchmarks