A Heuristic Method of Two-Level Logic Synthesis

摘要

An original method of logic Junction minimization is presented. Its implementation denoted as BOOM minimizer is described an evaluated. The method is applicable to the problems of logic design, artificial intelligence, software engineering and graph theory, etc. The innovative feature of the proposed method consists above all in the top-down approach to implicant generation by inclusion of literals. The selection of these newly included literals is based on heuristics using the frequency of literal occurrence. The proposed method is efficient especially for functions with several hundreds of input variables, whose values are defined only for a relatively small part of their range. The method has been tested on several different problems including standard design benchmarks, but also on problems of a much larger dimension, generated randomly. These experiments proved that the new algorithm is very fast and that for large circuits it delivers better results than the state-of-the-art ESPRESSO.