Programmed logic arrays [1], [2] are common in computer design. A form of this method of design has been used since the beginnings of computers, in telephone relay networks [3]. Optimization of such realizations of functions were begun by Karnaugh [4], Quine [5], McCluskey [6], and Roth [7]. Substantial use was mnade of such programs by Preiss [8] and Perlman [9]. Despite the existence of exact procedures, "fast," "approximate" procedures have been widely used. A new approximate procedure, using the D algorithm [1], [10], [11] is introduced here. It gets around a large computation, in complementation, using prior methods. Running programs "verify" this expectation.

This paper presents an account of algorithms, and the execution of their programs, applied to large practical problems, for array logics, programmed logic arrays (PLA's), in particular for NASA's Jet Propulsion Laboratory at the California Institute of Technology for the Venus Probe and for certain nuclear propulsion studies. The problem of array logic optimization—covering switching functions—is classical. The use of array logic as a solution to an acute problem of LSI fabrication has led to a resurgence of interest in this problem. A new formulation of the multiple output problem which leads to algorithmic/computational as well as conceptual simplifications is given. Previous methods of handling multiple output problems involved encoding the outputs as inputs and solving as a many-input, single-output problem. The present method encodes these in cubes with input parts and output parts. The classical operators and the execution of algorithms are thus rendered more compact and more efficient.

The need for verification of hardware designs is particularly important for large-scale-integration technologies because of the great cost, in time and money, for engineering changes. This correspondence describes an efficient means for determining the equivalence of a behavioral, high-level, i.e., flowchart, definition of the design and a detailed regular logic design. It may be used between compatible high-level as well as low-level designs. A compiler RTRAN transforms the high-level to a low-level design and a program VERIFY determines the equivalence of two such regular logic designs. It seeks to compute a counterexample, starting at the outputs, rather than to try exhaustively input patterns. Experimentally, VERIFY is proven vastly superior to exhaustive simulation. These methods have been used routinely for very large designs.

Programmed algorithms for test generation and test evaluation are described. The D-notation is introduced and a test generator (DALG) for combinational logic is presented. The sequential case is then examined. "Real life" constraints related to LSI testing are discussed. Two heuristic test generators satisfying these constraints are introduced. The iterative test generator (ITG) generates tests by transforming the given sequential circuit into an iterative combinational circuit. The macroblock test generator (MTG) uses the same approach but makes use of complex primitives (latches, triggers, etc.) to represent the circuit to be tested. Both the ITG and the MTG are not always guaranteed to generate good tests for each examined failure, and are used in connection with a test evaluator (simulator). Basic features of this evaluator are discussed.

This paper describes an algorithm for the computation of tests to detect failures in asynchronous sequential logic circuits. It is based upon an extension of the D-algorithm [1]. Discussion of experience with a program of the procedure is given.

This paper is concerned primarily with methods of diagnosis, as opposed with detection of (single-gate) failures in combinational circuits, with but one primary output. Most previous papers in this area have been concerned with diagnosis and have neglected the detection problem. One result of interest is that it is shown that "for complete diagnosis the number of tests which must be applied to the circuit is proportional to the number of gates and is independent of the number of primary input terminals." Assumed but not given in their method is an algorithm for the purpose of computing a test to distinguish between two failures if such exists.

Two algorithms are presented: one, DALG-II, computes a test to detect a failure in acyclic logic circuits; the other, TEST-DETECT, ascertains all failures detected by a given test. Both are based upon the utilization of a ``calculus of D-cubes'' that provides the means for effectively performing the necessary computations for very large logic circuits. Strategies for combining the two algorithms into an efficient diagnostic test generation procedure are given. APL specifications of the algorithms are given in an Appendix.