J. A. Brzozowski and H. Jurgenson
An Algebra of Multiple Faults in RAMs
Department of Computer Science
University of Waterloo
Research Report CS-95-18
May 1995


Cell array faults in random-access memories (RAMs) are usually represented by Mealy automata. In such a model, multiple faults should also be representable by automata; in fact, it should be possible to compute the automaton representing a multiple fault from the automata representing the single faults that make up the multiple fault. In this paper we study properties of binary composition operations on automata that are appropriate for the representation of multiple faults in RAMs. First, we derive a set of generic conditions that every composition operation must satisfy. Second, we develop a set of physical conditions that the composition must satisfy in order to apply to stuck-at, transition and coupling faults in RAMs. Third, we represent the transition table rules used by van de Goor and Smit by a composition operation and prove that this operation satisfies both the generic and physical conditions. Fourth, we point out that in some circumstances, it is appropriate to use a different composition operation (defined by us in a previous paper) to permit a different handling of coupling faults in the presence of stuck-at or transition faults. We compare and relate the properties of the two algebras.

Index Terms

automaton, composition, coupling fault, multiple fault, pattern-sensitive fault, RAM, semilattice, stuck-at fault, testing, transition fault.

Download this document (compressed postscript).

Go back to Maveric Publications
Go back to Maveric home page.