Efficient input support selection for sub-functions in functional decomposition based on information relationship measures

Functional decomposition has important applications in many fields of modern engineering and science, such as combinational and sequential logic synthesis for VLSI systems, pattern analysis, knowledge discovery, machine learning, decision systems, databases, data mining etc. However, its practical usefulness for very complex systems is limited by the lack of an effective and efficient method for selection of the appropriate input support for sub-systems. A classical method based on a systematic search of the whole solution space is inefficient. In this paper, an effective and efficient heuristic method for input support selection is proposed and discussed. The method is based on the application of information relationship measures, which allows us to reduce the search space to a manageable size while keeping high-quality solutions in the reduced space. The experimental results demonstrate that the proposed heuristic method is able to construct optimal or near optimal support very efficiently even for large systems. It is much faster than the systematic method while delivering results of comparable quality.