Redundancy Testing in Combinational Networks.

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)

Document Details

Document Type
Technical Report
Publication Date
May 01, 1973
Accession Number
AD0770541

Entities

People

  • Edward S. Davidson
  • Hsiao-peng Sherman Lee

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Computational Complexity
  • Computations
  • Redundancy

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Networking