Logic minimization algorithms for VLSI applications

Abstract

The extensive use of large scale integration (LSI) and very large scale integration (VLSI) chips in the present day digital systems has evinced keen interest in the design of LSI and VLSI circuits. The design methodology must be able to handle the increased complexity of these circuits. The design process starts with system specification of the digital system which is to be realized. This is then transformed into Boolean functional representation which leads to logic design. An important integral part of logic design is logic minimization which is the subject matter of this thesis. Subsequently, chip design is undertaken according to the desired implementation technology. Finally, testing is carried out to ascertain proper functioning of all the modules. The large number of input-output variables and the complexity of these circuits make the manual methods of design inefficient and sometimes impractical. Therefore, computers are being extensively used in all stages of design and development of VLSI circuits and systems. This thesis presents two computer-aided logic minimization procedures suitable for minimizing two-level AND-OR implementations such as those realized by a programmable logic array (PLA). PLAs are being extensively used in VLSI circuits to implement both control logic and data flow logic. As such, efficient optimization techniques need to be applied for the implementation of the PLA so that it occupies minimum silicon area. As the area occupied by the PLA is proportional to the number of product terms, it is imperative to minimize the multiple output function realized by the PLA to such an extent that it is implemented by the minimum number of product terms. The first algorithm presented is a minterm-based multiple output minimization algorithm. This is a divide and conquer algorithm and is carried out by five procedures. The algorithm is mainly guided by two parameters, the degree of adjacency (DA) and the candidate product term (CPT), which are selectively computed for those minterms that participate in the generation of product terms constituting the optimal solution. The algorithm also handles a multiple output function whose individual functions are cyclic functions. For the implementation of the multiple output function using a PLA, the algorithm produces the C-matrix (AND plane) and the D-matrix (OR plane), where the number of product terms as well as the crosspoints are minimal. The algorithm does not generate any superfluous product term or the complement (OFF set) of any function. Consequently, the number of computations turn out to be quite minimal. The algorithm has been implemented in Pascal and tested using a large number of examples. As the algorithm is minterm-based, the storage and time requirements grow exponentially with the number of variables and the number of distinct minterms. However, if the number of input variables is less than or equal to 12, and if the number of distinct minterms remains within 3000, then the algorithm can be applied with reasonable computer resources. There are many applications in industry and research where the size of the function and the number of distinct minterms will remain well within these limits. For such applications, the minterm-based algorithm is very likely to be suitable. A cube-based computer-aided design procedure for the minimization of multiple-output Boolean functions as encountered in the synthesis of VLSI logic circuits is also presented in this thesis. A fast technique for the determination of essential prime cubes without generating all the prime cubes is among the salient features of the algorithm. A new class of selective prime cubes called valid selective prime cubes (VSPC) has also been introduced. This new class of prime cubes has proved to be a very powerful tool inasmuch as it guides the algorithm to the minimal set of selective prime cubes while encountering either an independent chain or an interconnected chain of cyclic prime cubes. In many cases, this avoids branching which is computationally an expensive operation. The other significant features of the algorithm are that it does not generate either the complement or all the prime cubes of the functions. Therefore, it is well suited to minimize functions with large complement size and/or very high number of prime cubes. The algorithm has been implemented in a 3000-line Pascal program and evaluated using a large number of PLAs including those of Berkeley PLA test set. Results of comparison with well-known algorithms ESPRESSO II and McBOOLE indicate that the program produces absolute minimal solution in most cases and near minimal in a few others.