Cellular Automata with Large Channel Separations

In built-in 2D test pattern generation, parallel scan chains are driven by successive stages of a TPG mechanism. The bit sequences received by the scan chains are shifted versions of one another by different numbers of bit positions known as phaseshifts. Small phaseshifts impact negatively the fault coverage, and in order to alleviate this problem, the use of additional hardware overhead in terms of multi-input XOR gates (phaseshifters) has been proposed in the literature to impose large phaseshifts. In this paper we show that by simply permuting locally the stages of a cellular automaton and adding absolutely no other logic, large phaseshifts can be attained. In particular we show that scan chain i can be driven by an appropriate CA stage j, such that |j - i| les B and the minimum phaseshift between successive chains (channel separation) is maximized. The user-defined bound B controls the routing overhead. We have obtained large channel separations even for B = 2.