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