Functional decomposition with an efficient input support selection for sub-functions based on information relationship measures

The functional decomposition of binary and multi-valued discrete functions and relations has been gaining more and more recognition. It has important applications in many fields of modern digital system engineering, such as c ombinational and sequential logic synthesis for VLSI systems, pattern analy sis, knowledge discovery, machine learning, decision systems, data bases, d ata mining etc. However, its practical usefulness for very complex systems has been limited by the lack of an effective and efficient method for selec ting the appropriate input supports for sub-systems. In this paper, a new e ffective and efficient functional decomposition method is proposed and disc ussed. This method is based on applying information relationship measures t o input support selection. Using information relationship measures allows u s to reduce the search space to a manageable size while retaining high-qual ity solutions in the reduced space. Experimental results demonstrate that t he proposed method is able to construct optimal or near-optimal supports ve ry efficiently, even for large systems. It is many times faster than the sy stematic support selection method, but delivers results of comparable quali ty. (C) 2001 Elsevier Science B.V. All rights reserved.