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