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:

1973-05-01

Pagination or Media Count:

77.0

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 mi 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