A MINIMIZATION APPROACH FOR TWO LEVEL LOGIC SYNTHESIS USING CONSTRAINED DEPTH-FIRST SEARCH

Two-level optimization of Boolean logic circuits, e xpressed as Sum-of-Products (SOP), is an important task in VLSI design. It is well known that an optimal SOP representation for minimizing gate input count is a cover of prime implicants. De termination of an optimal SOP involves two steps: first step is generating all prime implicants of the Boolean function, and the second step is finding an optimal cover from the set of all prime implicants. A cube absorption method for generating all prime implicants is significantly more efficient than the tabular Quine-McCluskey method, when implemented using the position cube notation (PCN) to represent product cubes, and efficient bit manipulations to implement the cube operations.