Some Algorithmic Improvements in Multi-Level Logic Minimisation

Abstract

In this paper an improved method for extraction of common subfunction in Multilevel Logic Minimization is implemented. The method for extraction of subfunction of Mathony and Baitinger is modified here by using some heuristics. Firstly the literals are sorted in decreasing order of their weight instead of increasing order of their frequencies. Secondly, for finding factor of a hyperfunction, common output literal is not needed to be present. Thus a method is implemented which is more general in the sense that it can give solution for different kinds of circuits and more efficient in the sense that it uses less number of iteration passes to give the solutions. The method for extraction of common factors is also implemented. The time complexity for these two methods are compared. Then the two multi-level circuits obtained from the above two methods are compared with the circuit obtained from two-level minimization using VLSI package VINYAS-GX. For smaller two-level circuit, each method realises multilevel circuits of nearly the same propagation delay and gate complexity, but for larger two-level circuit with larger fan-in, the subfunction method generally realises a multi-level circuit with lower propagation delay and smaller gate complexity. It also uses a simpler approach with lesser time complexity than that for the factor method.

Indexing terms:

• Algebraic hyperfunction
• Multiple output cube
• Boolean circuits
• Circuit minimization