Logic minimization algorithms for VLSI applications.

Abstract

The widespread use of Large Scale Integration (LSI) and Very Large Scale Integration (VLSI) chips in modern digital systems has intensified interest in the design of efficient circuits. As circuit complexity increases, design methodologies must evolve to handle this growth. The design process begins with system specification, followed by Boolean functional representation, logic design, chip design, and testing. A critical phase in this process is logic minimization, which is the focus of this thesis. Manual methods for logic design are often inefficient or impractical due to the large number of input-output variables. Consequently, computer-aided design (CAD) tools are extensively used in all stages of VLSI circuit development. This thesis presents two CAD-based logic minimization procedures suitable for two-level AND-OR implementations, such as those realized by Programmable Logic Arrays (PLAs). PLAs are widely used in VLSI circuits for implementing both control and data flow logic, making efficient optimization techniques essential. The first method is a minterm-based multiple-output minimization algorithm, implemented using a divide-and-conquer strategy. It operates through five procedures and is guided by two parameters: Degree of Adjacency (DA) and Candidate Product Term (CPT). These are selectively computed for minterms contributing to the optimal solution. The algorithm handles cyclic functions and generates minimal C-matrix (AND plane) and D-matrix (OR plane) representations without producing superfluous product terms or complements. Implemented in Pascal and tested on numerous examples, the algorithm is efficient for up to 12 input variables and 3000 distinct minterms, making it suitable for many industrial and research applications. The second method is a cube-based minimization procedure for multiple-output Boolean functions. It features a fast technique for identifying essential prime cubes without generating all possible prime cubes. A new class of selective cubes, called Valid Selective Prime Cubes (VSPC), is introduced to guide the algorithm toward minimal solutions, even in the presence of cyclic cube chains. This approach often avoids computationally expensive branching and is well-suited for functions with large complement sizes or high numbers of prime cubes. The algorithm has been implemented in a 3000-line Pascal program and evaluated using a wide range of PLA examples, including those from the Berkeley PLA test set. Comparative results with well-known algorithms such as ESPRESSO II and McBOOLE indicate that the proposed program produces absolute minimal solutions in most cases and near-minimal solutions in others.