Redundancy Testing in Combinational Networks.
STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Pagination or Media Count:
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
- Electrical and Electronic Equipment