VECTOR-SPACE THEORETIC ANALYSIS OF ADDITIVE CELLULAR AUTOMATA AND ITSAPPLICATION FOR PSEUDOEXHAUSTIVE TEST PATTERN GENERATION

This paper introduces a novel scheme for utilizing the regular structu re of three neighborhood additive cellular automata (CA) for pseudoexh austive test pattern generation. The vector space generated by a CA ca n be decomposed into several cyclic subspaces. A cycle corresponding t o an m-dimensional cyclic subspace has been shown to pseudoexhaustivel y test an n-input circuit (n greater-than-or-equal-to m). Further, suc h a cycle is shown to supply (m - 1) bit exhaustive pattern including the all-zeros (m - 1)-tuple. Schemes have been reported specifying how one or more subsets of (m - 1) cell positions of an n-cell CA can be identified to generate exhaustive patterns in an m-dimensional cyclic subspace.