Logic synthesis for FPGAs based on cutting of BDD

The paper presents theoretical background of a new concept of logic synthesis for LUT-based FPGAs. The idea of multi-output function description in the form of PMTBDD diagram is proposed. This form enables to carry out a simple analysis of multi-output function by appropriate algorithms which are dedicated to single-output functions. The essence of logic synthesis is searching for suitable PMTBDD cuttings. The choice of the PMTBDD cuttings enables to obtain an adequate decomposition path. As the result of BDD diagram cutting, SMTBDD diagrams are created. These diagrams are a generalized form of SBDD and MTBDD diagrams. The idea of choosing a cutting line, which matches LUTs included in FPGAs, is also proposed. The essence of the suggested method of searching for the best technology mapping is based on an analytical description of the efficiency of mapping. The experimental results, which prove efficiency of the proposed methods, are presented too.