The Minimization of TANT Networks

Abstract

A TANT network is a three-level network composed solely of AND-NOT gates (i.e., NAND gates) having only true (i.e. uncomplemented) inputs. The paper presents an algorithm for finding for any given Boolean function a least-cost (i.e. fewest number of gates) TANT network. The method used is similar to the Quine-McCluskey algorithm for two-level AND/OR networks. Certain functions realizable by input gates or second-level gates are preselected as candidates for possible use in an optimal network. This is analogous to the preselecting of prime implicants in two-level minimization. A network is then obtained by choosing a least-cost subset of the candidates which is adequate for realizing the function. This selection phase is analogous to the use of a prime implicant table in two-level minimization. In TANT minimization, however, an extension to a prime implicant table known as a CC-table must be used. The algorithm permits hand solution of typical four-and five-variable problems. A computer program has been written to handle more complex cases.