Enumerating catastrophic fault patterns in VLSI arrays with both uni- and bidirectional links

Characterization of catastrophic fault patterns (CFPs) and their enumeratio n have been studied by several authors. Given a linear array with a set of bypass links, an important problem is how to count the number of CFPs. Enum eration of CFPs for two link redundancy G = {1, g} has been solved for both unidirectional and bidirectional link cases. In this paper, we consider th e more general case of link redundancy G = {1, 2, ..., k, g} 2 less than or equal to k < g. Using random walk as a tool, we enumerate CFPs for both un idirectional and bidirectional cases. (C) 2001 Elsevier Science B.V. All ri ghts reserved.