In this paper we present a new search method for test set embedding using an accumulator driven with an additive constant C. We formulate the problem of finding the location of a test pattern in the generated sequence in terms of a linear Diophantine equation with two variables, which is known to be solved quickly in linear time. We show that only one Diophantine equation needs to be solved per test set irrespective of its size. Next we show how to find the starting state, for a given constant C and test set T, such that the generated sequence can reproduce T with minimum length. Finally, we show that the best constant Copt(in terms of shortest test length) for the embedding of T using an accumulator of size n can be found in O(2ldrn+Fldr|T|) steps, instead of O(nldr2nldr|T|) steps of a previous approach, where F depends on the particular test set and can be significantly smaller than its worst case value of 2n-2. The value of F can also be further reduced while providing a guaranteed approximation bound of the shortest test length. Experimental results show the computational improvements.

In this paper we show first that finding the location of a test vector in the sequence generated by an accumulator driven with an odd additive constant C is equivalent to the solution of a linear Diophantine equation with two variables. The latter equation is known to be solved fast in linear time. We then show that only one Diophantine equation needs to be solved per test set irrespective of the number of patterns in it. The finding of the locations of all patterns of a given test set T in the sequence generated under a constant C is done in O(n+ | T |) steps instead of O(n middot |T|) steps of a previous approach. Next we present a method which, given a test set T, and an odd constant C, finds the seed in the sequence generated under C that can reproduce all patterns of T in minimum length. We use this optimum technique to search for the best constant C' (in terms of short test length) in a randomly generated subset. Experimental results show the potential of the approach for test set embedding