High-quality sub-function construction in functional decomposition based on information relationship measures

Functional decomposition seems to be the most effective circuit synthesis approach for look-up table (LUT) FPGAs, (C)PLDs and complex gates. In the functional decomposition that targets LUT FPGAs, the circuit is constructed by recursively decomposing a given function and its sub-functions until each of the resulting sub-functions can be directly implemented with a LUT. The choice of sub-functions constructed in this process decides the quality of the resulting multi-level circuit expressed in terms of the logic block count and speed. In this paper, we propose a new effective and efficient method for the sub-function construction, and we consider its application in our circuit synthesis tool that targets LUT-based FPGAs. The method is based on the information relationship measures. The experimental results demonstrate that the proposed approach leads to extremely fast and very small circuits.