Hierarchical cellular automata as an on-chip test pattern generator

Abstract—This paper introduces the concept of hierarchical cellular automata (HCA). The theory of HCA is developed over the Galois extension field (2), where each cell of the CA can store and process a symbol in the extension field (2). The hierarchical field structure of (2) is employed for design of an HCA-based test pattern generator (HCATPG). The HCATPG is ideally suited for testing very large scale integration circuits specified in hierarchical structural description. Experimental results establish the fact that the HCATPG achieves higher fault coverage than that which could be achieved with any other test structures. The concept of percentile improvement in fault coverage is introduced to have a realistic assessment of fault coverage achieved with the proposed HCATPG. I