Multi-level logic optimization based on pseudo maximum sets of permissible functions

Abstract

The transduction method is one of the strongest multilevel logic optimization algorithms. It uses permissible functions which represent Don't-Care conditions of a circuit. An original transduction algorithm has two sorts of sets of permissible functions: MSPF (maximum set of permissible functions) and CSPF (compatible set of permissible functions). A CSPF has the characteristics that computation time is short but optimization capability is weak. An MSPF has the opposite characteristics. The authors propose a new set of permissible functions, which is called pseudo-MSPF. It has the good characteristics of both a CSPF and an MSPF. The authors also shown that they can shorten the time for gate transformations by using pseudo-MSPFs instead of CSPFs. Experimental results show that the optimization based on pseudo-MSPFs can make logic equations with fewer literals, and shorten the total processing time than that based on CSPFs.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>