Multifunction minimization for Programmable Logic Arrays

Abstract

The problem of minimizing two-level AND/OR Boolean algebraic functions of n inputs and m outputs for implementation on Programmable Logic Arrays (PLA) is examined. The theory of multiple-output functions as well as the historically alternative approaches to reckoning the cost of an equation implementation are reviewed. The PLA is shown to be a realization of the least product gate equation cost criterion. The multi-function minimization is dealt with in the context of a directed tree search algorithm developed in previous research. The PLA oriented minimization is shown to alter the nature of each of the basic tenets of multiple-output minimization used in earlier work. The concept of a non-prime but selectable implicant is introduced. A new cost criterion, the quantum cost, is discussed, and an approximation algorithm utilizing this criterion is developed. A timing analysis of a cyclic resolution algorithm for PLA based functions is presented. Lastly, the question of efficiency in automated minimization algorithms is examined. The application of the PLA cost criterion is shown to exhibit intrinsic increases in computational efficiency. The technique of judiciously selecting the next minterm for expansion on a search tree is discussed. The theory of the requirements for essentiality in single and multiple-output functions is enlarged. The reuse of previously obtained information in the minimization process is examined. A minterm classification algorithm is suggested and a PLA minimization algorithm is implemented in the FORTRAN language.