Method of input variable partitioning in functional decomposition based on evolutionary algorithm and binary decision diagrams

The functional decomposition is recognized as very efficient synthesis method of digital circuits and systems. However its practical usefulness for very complex systems is limited by lack of an efficient method of input variable partitioning. In this paper, a heuristic method for input variable partitioning is proposed for decomposition of Boolean function represented by BDD. The method is based on an application of evolutionary algorithms, what allows exploring the possible solution space of a problem while keeping the high-quality solutions in this reduced space. The boolean function is represented by the reduced ordered binary decision diagram (ROBDD). The experimental results show that the proposed heuristic method is able to generate optimal or near optimal solution very efficiently even for large systems. It is much faster than the systematic method while delivering results of the comparable quality.