Accession Number : AD0770541
Title : Redundancy Testing in Combinational Networks.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Personal Author(s) : Lee,Hsiao-Peng Sherman ; Davidson,Edward S.
Report Date : MAY 1973
Pagination or Media Count : 77
Abstract : A simple, necessary and sufficient test is developed for testing whether a single connection in a tree-type NAND network is redundant. A procedure is presented for testing every connection in the network. The computational complexity of the procedure is m(i squared) where m = the number of gates and i = the average number of inputs per gate in the network. The redundancy test is generalized for multi-output tree-type NAND networks and such networks realizing partially specified functions. A dual test is developed for tree-type NOR networks, but NOR networks for partially specified functions are treated by a simpler test than the dual test. The test may be applied to AND-OR networks as well by converting them, at least conceptually, to an equivalent NAND form while preserving redundancy. (Modified author abstract)
Descriptors : *Redundant components, *Logic circuits, *Electrical networks, Gates(Circuits), Computations, Algorithms, Theorems, Set theory
Subject Categories : Electrical and Electronic Equipment
Distribution Statement : APPROVED FOR PUBLIC RELEASE