Report Number: CSL-TR-76-108
Institution: Stanford University, Computer Systems Laboratory
Title: Cascade structure in totally self-checking networks
Author: Kolupaev, Stephen
Date: April 1976
Abstract: In the well-known totally self-checking (TSC) network, a failure must not change one output codeword into another. Called the fault-secure property, this permits a receiver of the net's output to assume that any codeword it receives is correct. Further, the self-testing property requires that each possible failure in the net must produce at least one non-code output. Thus a receiver can monitor the health of the network by watching for non-code outputs. In this paper we propose modifications of these two properties. The self-testing property is made more stringent. Each possible failure in the net is required to produce an output which is in a distinguished subset of the non-code outputs. The fault-secure requirement is modified to permit a fault to interchange certain output codewords. In particular, all outputs not in the distinguished subset are partitioned into equivalent classes, and a fault is permitted to change the output from one codeword to another codeword in the same class. However, a fault is not permitted to change the output from a codeword to any member of a different equivalence class (one not containing the correct output) . These modified properties define a generalization of the TSC network. A network which meets the modified properties is called a generalized self-checking (GSC) network. Self-checking and self-testing (Morphic) networks and TSC networks are special cases of the GSC network. Examining TSC networks, we find a further connection with the GSC network. It has been known for some time that not every subnetwork of a TSC network need by TSC. We show that every subnetwork of a TSC network is GSC, and every TSC network is a cascade of GSC networks. This establishes the GSC network as the basic building block from which every TSC network is constructed. We explore a brute-force method for constructing a desired TSC network by cascading GSC subnetworks. The method resorts to enumeration at many points of decision and thus is not a practical design tool. However, it does yield a very nice alternate realization of the Morphic OR, and suggests specializations which merit further study.
http://i.stanford.edu/pub/cstr/reports/csl/tr/76/108/CSL-TR-76-108.pdf