Zero-Aliasing for Modeled Faults.
AbstractWhen using built-in self-test (BIST) for testing VLSI circuits the circuit response to an input test sequence, which may consist of thousands to millions of bits, is compacted into a signature which consists of only tens of bits. Usually a linear feedback shift register (LFSR) is used for response compaction via polynomial division. The compacting function is a many-to-one function and as a result some erroneous responses may be mapped to the same signature as the good response. This is known as aliasing.In this paper we deal with the selection of a feedback polynomial for the compacting LFSR, such that an erroneous response resulting from any modeled fault is mapped to a signature that is different from that for the good response. Such LFSRs are called zero-aliasing LFSRs. Only zero-aliasing LFSRs with primitive or irreducible feedback polynomials are considered due to their suitability for BIST test pattern generation.Upper bounds are derived for the least degree irreducible and primitive zero-aliasing LFSR polynomials. These bounds show that in all practical test applications such a polynomial will be of degree less than 53. Expected bounds are derived and show that when the number of faults is less than 106, then this degree is at most 21.Procedures to find irreducible and primitive zero-aliasing LFSR polynomials of: 1) the smallest degree and 2) a pre-specified degree; are presented. A low-complexity procedure to find a zero-aliasing LFSR polynomial is also presented. The worst case as well as expected time complexities of all these procedures are derived. Experimental results are presented for practical problem sizes to demonstrate the applicability of the proposed procedures.
Introduction
Built-In Self-Test (BIST) is the capability of a circuit to test itself. The idea behind BIST is to
create pattern generators (PGs) to generate test patterns for the circuit and response analyzers
(RAs) to compact the circuit response to the inputs that are applied. The circuit response,
which may consist of thousands to millions of bits, is compacted into a signature which consists
of only tens of bits. The compacting function is a many-to-one function and as a result some
erroneous responses might be mapped to the same signature as the good response. This is known
as aliasing.
When all erroneous responses are mapped to a different signature than the good response,
we have zero-aliasing. There are two previous schemes to achieve zero-aliasing, that take into
account all possible error sequences. The first is by Gupta et al. [7] [14]. In this scheme the RA
is a linear feedback shift register (LFSR) and the compacting function is polynomial division of
the good response by the feedback polynomial. The scheme requires the quotient of the good
response to be periodic. This is achieved by proper selection of the LFSR feedback polynomial
once the good response is known. They give a bound of n=2 on the length of the required
register, for a test sequence of length n. The second scheme, due to Chakrabarty and Hayes [5],
uses non-linear logic to detect any error in the response. The number of memory cells in their
RA is dlog ne but they have no bound on the extra logic required to implement their scheme.
The major difference between our scheme and the aforementioned zero-aliasing schemes is
that we target a specific set of possible faults and try to achieve zero-aliasing for the error
sequences resulting only from these modeled faults. We do not try to recognize all possible error
sequences, mainly because most of them will never occur. The fault model lets us focus on the
probable error sequences. As a result, we use less hardware than the aforementioned schemes.
A previous method for finding zero-aliasing feedback polynomials for modeled faults was
presented by Pomeranz et al. [13]. Different heuristics for finding a zero-aliasing polynomial are
suggested. These heuristics do not necessarily find a minimum degree zero-aliasing polynomial,
nor do they necessarily find an irreducible or primitive polynomial, which is very important if
the register is also to function as a PG. In this work we present upper bounds on the minimum
degree irreducible and primitive zero-aliasing polynomials and provide algorithms to find such
minimum degree polynomials.
The PGs and RAs are usually implemented by reconfiguring existing registers. Some registers
are configured as PGs to generate tests for some blocks of logic and reconfigured as RAs to test
other blocks of logic. When the same LFSR feedback polynomial serves both purposes, the
overhead of a reconfigurable design is saved. In such a scheme a LFSR is used as a PG and a
multiple input shift register (MISR) is used as a RA. An example of a MISR-based RA is shown
in

Figure

1. The register is configured as a shift register where the input to each cell is an XOR
function of the previous cell, an output bit of the circuit under test (CUT) and, depending on the
linear feedback function, a feedback bit. Number the cells of a k stage MISR D
with the feedback coming out of cell D k\Gamma1 . The feedback function is represented as a polynomial
and the feedback feeds cell D i iff f 1. The feedback polynomial of
the MISR in Figure 1 is 1. The difference between a LFSR and a MISR are
the extra inputs connected to the outputs of the CUT. If both the PG (LFSR) and the RA
(MISR) use the same feedback polynomial, then the overhead of reconfigurable polynomials is
saved. In a previous paper [11] we showed how to select the feedback polynomial for a PG; in
this paper we deal with selecting the feedback polynomial for a RA. Since a k-stage PG with
a primitive feedback polynomial generates all non-zero k-tuples as opposed to a PG with an
irreducible feedback polynomial, we prefer primitive zero-aliasing polynomials, even though it
takes more effort to find them.
The compacting function of a MISR is polynomial division over GF [2]. The effective output
polynomial is divided by the feedback polynomial. The signature is the remainder of the division.
If the CUT has k outputs, it has k output sequences. Denote these sequences by
. If the input sequence is of length n, then each can be viewed as a polynomial
O
is the output value of the i-th output at time j. The effective
polynomial is then
O l x l :
Our objective is to select a feedback polynomial for the compacting MISR, given a set of
modeled faults, such that an erroneous response resulting from any modeled fault is mapped to
a different signature than the signature of the good response.
For a CUT with few outputs, the available register might be too short to achieve zero-aliasing.
In this case we need to lengthen the register by adding flip-flops. To keep the hardware overhead
at a minimum, we want to add as few flip-flops as possible, hence we are interested in a feedback
polynomial of smallest degree that achieves our objective. When a register is to serve both as
a PG and a RA, it is advantageous to have the feedback polynomial of the same degree as the
available register, hence we are interested in a feedback polynomial of a pre-specified degree. At
times, we might want to find a feedback polynomial fast, even if the resulting MISR requires
extra flip-flops over the optimum.
We assume the following test scenario. The input sequence to the CUT has been designed
so that the effective output polynomial due to any target fault is different from the effective
polynomial of the good response, i.e. all the error polynomials are non-zero. Let r be the
effective polynomial of the good response, then the effective polynomial due to fault i can be
represent as r +h i . By the linearity of the remaindering operation, we get a different remainder
for this erroneous polynomial iff h i is not divisible by the feedback polynomial. We assume we
are given the error polynomials for each of the target faults.
The problem we deal with in this paper is the following: given a set of polynomials
find a polynomial that is relatively prime to all the polynomials of H. Such
a polynomial will be referred to as a non-factor of H. If a non-factor is used as the feedback
polynomial for the compacting MISR, zero-aliasing is achieved for the set of target faults. In
particular, for irreducible and primitive feedback polynomials we present (1) upper bounds on the
smallest degree zero-aliasing MISR; (2) procedures for selecting a zero-aliasing MISR with the
smallest degree; (3) procedures for determining whether a zero-aliasing LFSR of a pre-specified
degree exists, and if so, finding one; and (4) procedures for fast selection of a zero-aliasing MISR.
We analyze the worst case as well as expected time complexity of the proposed procedures.
A note on notation. When using logarithmic notation, ln x will denote the natural logarithm
of x and log x will denote the base 2 logarithm of x. The polynomials fh i g represent the error
polynomials. The degree of h i is represented by d i . The product of the polynomials in H is
denoted by h, and the degree of h is d h . For each h i , the product of the distinct, degree j,
irreducible factors of h i is denoted by g i;j , with d i;j being the degree of g i;j . The product, over
all i, of the polynomials g i;j is denoted by g j . The non-factor we seek will be referred to as a
with d a representing the degree of a.
The rest of this paper is organized as follows. In Section 2 we establish upper bounds on
the degree of a non-factor. In Section 3 we review polynomial operations over GF [2] and their
complexities. Section 4 presents procedures for finding a non-factor of smallest degree for the
set H. Section 5 presents procedures for finding a non-factor of a pre-specified degree and for
finding a non-factor fast. We also discuss the effectiveness of conducting an exhaustive search for
a least degree non-factor. Section 6 presents some experimental data. We conclude in Section
7.
2 Bounds on the least degree non-factor of a set of polynomial

Consider the following problem.
Problem 1: Let H be a set of jHj polynomials h
Give an upper
bound s(d h ) on the degree of an irreducible polynomial and an upper bound p(d h ) on the degree
of a primitive polynomial that does not divide h, i.e. there exists an irreducible (primitive)
polynomial of degree at most s(d h ) (p(d h )) that does not divide h.
Similarly, let es(H) (ep(H)) be the expected degree of an irreducible (primitive) polynomial
that is a non-factor of H.
The bounds s(d) and p(d) will be referred to as the worst case bounds while the bounds
es(H) and ep(H) will be referred to as the expected bounds. We first establish the worst case
bounds and then proceed with the expected bounds.
2.1 The worst case bounds
For the bound on s(d) we follow [10]. Let I 2 (j) denote the number of irreducible polynomials
of degree j over GF [2]. The degree of the product of all irreducible polynomials of degree j is
(j). Let s(d) denote the least integer such that
be the product of
all the irreducible polynomials of degree less than or equal to s(d). The degree of Q s(d) is greater
than d. Replacing d with d h , Q s(d h ) has at least one root that is not a root of h, hence Q s(d h )
has at least one irreducible factor that is not a factor of h. Thus, s(d h ) is an upper bound on
the degree of an irreducible polynomial that is relatively prime to all the polynomials in the set
H. The following lemma provides a bound on s(d h ).
We turn to find the bound on p(d). The number of primitive polynomials of degree m over
GF [2] ism
where OE(q) is the Euler function denoting the number of integers less than and relatively prime
to q and ([12, p. 37])
l
Y
where the p i 's are all the distinct prime factors of q.
Lemma 2: [16, p. 173]
for all q - 3 with the only exception being (the product of the first nine
primes), for which 5is replaced by 2:50637.
Lemma 3: For q ?
2:08 log log q
Proof: We first prove the case for q ? 65. By Lemma 2
2:08 log log q
For Equation (1) can be verified directly.
To help us derive the bound on p(d) we introduce the value - (t). Let - (t) denote the least
integer such that the ratio between - (t) times the number of primitive polynomials of degree
- (t) and t times the number of irreducible polynomials of degree t is greater than 1, i.e.
Lemma 4: [10, Lemma 3, p. 293] For t - 3
2:
Lemma 5: For log log 2te:
Proof: By the definition of - (t), it can be verified that the expression in the Lemma is not
valid for but is valid for 2. We now prove the case for t ? 2.
For q - 4, the function q
2:08 log log q is an increasing function. Hence
2:08 log log(q) ?
2:08 log log
Also,
2:08 log log(q
2:08 log log q
thus, since 1 ? 1
2:08 log log q ,
2:08 log log(q \Gamma 1)
2:08 log log q
be the least integer such that 2 - 0
2:08 log log 2 - 0 (t)
. By (2)
2:08 log log(2 - 0
By Equation (1), for - (t) ? 5, we get
and due to Lemma 4
Thus, by the definition of - (t), we have that - 0 (t) - (t). To bound - (t) from above, we solve
By definition, - 0 (t) must satisfy
2:08 log - 0 (t)
By setting - 0 log log 2te, we have
log log(2t)e
and for t ? 2
Thus, for t ? 2, - 0 log log 2te satisfies (3), hence
log log 2te:
Lemma p(d) denote the least integer such that
d, then for d ?
Proof: By the definition of - (t) and Lemma 5
log(2dlog(d+1)e)e
By Lemma 1 and the definition of s(d)
Example 1: In Table 1 the values of OE(2 (the degree of the product of all the primitive
polynomials of degree m) and
(the degree of the product of all the primitive
polynomials of degree 2 - i - m) are tabulated for As long as d is less than the
maximum value in the table, p(d) can be obtained from the table, instead of using Lemma 6.
For example, if the number of modeled faults in the CUT is and the length of the
test sequence is . The degree of the product of all primitive polynomials
with degree less than or equal to 33 is the first which is greater than
Thus, a zero-aliasing LFSR with a primitive feedback polynomial, of degree at most 33, exists
for the CUT. On the other hand, using the bound of Lemma 6 we get p(d h
A closer look at table 1 shows that the product of all the primitive polynomials of degree less
than or equal to 53 has degree D greater than 1:4 . Thus, as long as the product of the
number of faults and the test sequence length is less than D (which is the case for all practical
test applications) a zero-aliasing MISR of degree less than or equal to 53 exists.
2.2 The expected bounds
In deriving the expected bounds we assume that the polynomials fh i g are random polynomials.
Denote the product of the distinct irreducible factors of degree j of h i by g i;j . Denote the
number of distinct irreducible factors of h i , of degree j, by v. The value of v can range from 0
to minfbd i =jc; I 2 (j)g.
Lemma 7: For j - 2, the expected value of v (the number of irreducible, degree-j, factors of
than or equal to 1
.
Proof: Let IR 2
be the set of irreducible polynomials of degree j over GF [2]. For
a given polynomial q, of degree greater or equal to j, define the indicator function d(p i ; q) to be
one if p i divides q and zero otherwise. The probability that a polynomial of degree j divides a
random polynomial of degree greater or equal to j is 2 \Gammaj , hence the probability that
is equal to 2 \Gammaj . Thus
The same type of analysis can be used to bound V ar[v], the variance of v, and oe v , the
standard deviation of v.
Lemma 8: For j - 2, the variance of the number of irreducible factors of g i;j is less than 1
.
The standard deviation is less than
.
Proof: The variance of v is given by V
I 2 (j)
i!k
I 2 (j)
i!k
I 2 (j)
Hence
I 2 (j)
Having computed the mean and variance of the number of irreducible factors of degree j per
polynomial, we can compute a confidence measure for these results.
Lemma 9: For j - 4, the expected number of polynomials g i;j with more than 5 (50) factors
is less than jHj=100 (jHj=10; 000).
Proof: Using the Chebyshev inequality [8, p. 376]
the probability that v is greater than 5 is less than 0:01. Using this result we can
define a second random process in which the random variable x is 1 iff v is greater than 5 and
otherwise. This process is a Bernoulli experiment [6, Sec. 6.4]. The expected number of
i;j 's with more than 5 factors is upper bounded by jHj=100, as is the variance. Similarly, the
probability that v is greater than 50 is less than 0:0001 and the expected number of g i;j 's with
more than 50 factors is bounded by jHj=10; 000.
Lemma 10: The expected degree of the smallest irreducible non-factor of the set of polynomials
H is bounded from above by dlog jHje + 1.
Proof: Denote the product of the polynomials g i;j , 1 - i - jHj, by g j . By Lemma 7, the
expected number of (not necessarily distinct) factors of g j is less than jHj=j. The smallest j for
which I 2 (j) exceeds this value is an upper bound on the expected degree d a of a non-factor of
hence d a - ffi.
By applying Lemma 5 on the result of Lemma 10, we have
Corollary 11: The expected degree of the smallest primitive non-factor of the set of polynomials
H is bounded from above by 2
Example 2: Using the numbers of Example 1, let . The first j for which
exceeds jHj=j is hence we expect to find a zero-aliasing MISR
with a primitive feedback polynomial of degree less than or equal to 14, as opposed to the worst
case of 33. Corollary 11 would give us an upper bound of 19.
As the expected bound is a only a function the number of faults and not the length of the test
sequence, the expected degree of a zero-aliasing MISR will never exceed 53. In fact, as long as
the number of faults is less than 1 million, we expect to find a zero-aliasing MISR of degree less
than or equal to 21.
3 Polynomial operations in GF [2]
In search for a (least degree) non-factor of H we use procedures that sift the factors of the same
degree from a given polynomial. These procedures are based on the following lemma.
Lemma 12: [12, Lemma 2.13, p.48]
x is the product of all irreducible polynomials of
degree l, where l is a divisor of m.
Thus, a basic step in finding the distinct irreducible factors of a polynomial b(x) is the computation
of
The result of this operation is the product of all the irreducible factors of degree l, where ljm, of
b(x). For most polynomials b(x) of interest to us, 2 m ?? deg(b(x)). Therefore, we first compute
and then
In analyzing the complexity of our proposed procedures, we rely on the following results which
are stated in greater detail in the appendix.
The complexity of a polynomial gcd operation is O(M(s) log s) [1, pp. 300-308], where
s is the degree of the larger polynomial operand and M(s) is the complexity of polynomial
multiplication, where the product has degree s. The complexity of polynomial division is also
We considered two multiplication algorithms. The first algorithm is due to Sch-onhage [17].
Its complexity is O(s log s log log s). The second algorithm is suggested by Cormen et al. [6,
p. 799]. Its complexity is O(s log s). In the sequel we shall use the notation O(M(s)) for
the complexity of polynomial multiplication. Whenever possible it will mean s log s, otherwise
it should be taken as s log s log log s. Similarly the notation L(s) will denote either log s or
log s log log s, as appropriate.
The cost of finding the remainder of x 2 m
when divided by b(x) without actually carrying out
the division is [3] [15] O(mM(s)) where
Thus,
can be computed in O(mM(s) +M(s) log s).
4 Finding a non-factor of smallest degree for a given set
of polynomials
After establishing the bounds on the least degree non-factor of H in Section 2, this section
addresses the question of finding a least degree non-factor for H.
Problem 2: Given a set of polynomials
with
let
Find an irreducible (primitive) polynomial a(x), with deg(a) = d a , such that
1. For all (equivalently, h 6j 0 mod a).
2. For all irreducible (primitive) polynomials b(x), with deg(b) ! d a , h j 0 mod b (or equiv-
alently, there exists an i for which h i j 0 mod b).
One way of solving the problem is by factoring the polynomials of H. This would require
too much work, since we do not need to know all the factors in order to find a non-factor. We
only need to know the "small" factors.
In this section we present algorithms for solving Problem 2 and analyze their complexity.
The complexity is given in two forms. The first is with worst case complexity bounds, referred
to as the worst case complexity. The second is with expected complexity bounds, referred to as
the expected complexity. The expected complexity is a refinement of the worst case complexity
based on the expected size of the results from our procedures.
By Lemmas 1 and 6 (Section 2), we have an upper bound
depending on whether we are looking for an irreducible or a primitive non-factor. Using this
bound, we begin our search process, which is made up of three phases.
1. For all h i 2 H, find g i;j (x), the product of all distinct irreducible (primitive) factors of h i ,
of degree j.
2. Having found the polynomials g i;j , determine whether all irreducible (primitive) polynomials
of degree j are factors of H.
3. If not all irreducible (primitive) polynomials of degree j are factors of H, find one that is
not.
The worst case complexities of the three phases for the irreducible case are O(jHju 2 M(n)),
log n) and O(jHj 2 n 2 u 2 M(u)). The dominant term is O(jHj 2 n 2 u 2 M(u)). The
worst case complexities of the three phases for the primitive case are O(jHju 3 M(n)), O(jHj 2 \Delta
log n) and O(jHj 2 n 2 u 3 M(u) log log u). The dominant term is O(jHj 2 n 2 u 3 M(u) log log u).
The expected complexity of the first two phases are O(jHju 2 M(n)) and O(jHj log jHju 2 \Delta
log n). The expected complexity for the third phase is O(jHj log jHjd a M(d a )) to find an
irreducible non-factor and O(jHj log jHjd 2
a log log d a M(d a )) to find a primitive non-factor. The
dominant term is O(jHju 2 M(n)).
The worst case complexity is a function of jHj 2 n 2 multiplied by terms that are logarithmic
in jHj and n whereas the expected complexity is a function of jHjn multiplied by terms that
are logarithmic in jHj and n.
4.1 The product of all distinct factors of the same degree for a
given polynomial
Given the polynomial h i (x) and the upper bound u, we wish to compute g i;j , the product of all
distinct factors of h i of degree j, for u. The procedure for computing the polynomials
g i;j is given in Figure 2. The polynomials g i;j are computed in three steps. First, for u=2
compute
\Gamma x). Each g i;j is a product of all the distinct irreducible factors
of h i (x) of degree j and of degree l, where ljj.
When j is less than or equal to u=2, we have 2j - u. By Theorem 12, g i;2j contains the
product of all irreducible factors of degree l, where ljj, of h i . Since the degree of g i;2j is (much)
less than the degree of h i , it is more efficient to compute g i;j from g i;2j than from h i . Thus, in
Step 2, for
At the end of Step 2, each g i;j contains all the factors of degree ljj of h i . To sift out the
factors of degree less than j from g i;j , we need to divide g i;j by g i;l , where l ranges over the set
of divisors of j. This is carried out in Step 3.
Procedure distinct factors() is not enough when we are looking for a primitive non-factor.
At the end of the procedure, each g i;j is the product of all distinct irreducible polynomials of
degree j, that are factors of h i . From g i;j we need to sift out the non-primitive factors. Before
describing this aspect, we introduce the notion of maximal divisors.
being the distinct prime factors of q. The set
of maximal divisor of q is the set
For example,
only one prime factor,
A polynomial over GF [q] of degree m is irreducible iff it divides x does not
divide x divisors k of m. It is primitive of degree m iff it is irreducible and does
not divide x l \Gamma 1 for all l in md(q Ch. 3]. Procedure distinct primitives(), shown in

Figure

3, sifts out the non-primitive factors of g i;j .
Lemma 13:
1. The complexity of Procedure distinct factors() is O(u 2 M(n)).
2. The complexity of Procedure distinct primitive() is O(u 3 M(n)).
3. The complexity of the first phase is O(jHju 2 M(n)) for the irreducible case and O(jHju 3 \Delta
M(n)) for the primitive case.
In the above expressions for the irreducible case and for the primitive case.
Proof:
1. The worst case complexity of Procedure distinct factors() is as follows. In Step 1, the
procedure performs u=2 gcd computations involving h i . The complexity of each gcd computation
is O(jM(d i Thus the total work for the first stage is
' u
In Step 2 the procedure carries out u=2 gcd operations. The work required for this step is
In Step 3, for every element of the sets of divisors, the procedure performs a division
operation. The cost expression is
O(M(d
O(jM(d i;j
2. The complexity of Procedure distinct primitive() is as follows. Each iteration of Procedure
distinct primitives() reduces i;j and performs one gcd and one
division operation. The cost of each iteration is O(jM(d i;j There
are u, and we run the procedure u times.
Therefore, the additional work for the primitive case is bounded by O(u 3 M(d i )).
In most cases, the values d i;j will be (much) less than n, hence the actual work will
be much less then O(u 2 M(n)) and the dominant factor will be Step 1 of Procedure
distinct factors().
3. Over the set H, based on 1 and 2, the complexity of the first phase is (jHju 2 M(n)) for the
irreducible case and (jHju 3 M(n)) for the primitive case. The value of u is either s(d h ) or
corresponding to either the irreducible or primitive case.
Lemma 14: The expected complexity of the first phase is O(jHju 2 M(n))) with u equal to
either es(H) or ep(H).
Proof: The expected complexity of Procedure distinct factors() is dominated by the complexity
of Step 1, which is O(u 2 M(n)). The difference in the complexity of the other steps,
over the worst case, comes from using the expected size of the d i;j s, instead of their worst
case size, which is equal to n. The expected complexity of the procedure (including Procedure
distinct primitive()), over the set H is, thus, O(jHju 2 M(n)), with u equal to either es(H) or
ep(H).
4.2 The number of all distinct factors, of the same degree, for a
set of polynomials
After the first phase, for all degrees 1 - j - u, we have jHj polynomials g i;j , each a product of
the distinct irreducible (primitive) factors of degree j of h i . Some of the g i;j 's might equal
some pairs might have factors in common. Our goal is to find a least degree non-factor of H.
First we must determine whether all irreducible polynomials of degree j appear in
This is the second of our three phases (page 13). A simple test is to compare deg(g j )
with I 2 (j). If deg(g j )
then there is a non-factor of degree j. For the primitive case we
compare with OE(2 j \Gamma1)
.
(j), the only way to determine whether all irreducible (primitive) polynomials
of degree j are factors of g j is to find those factors that appear in more than one of the g i;j 's
and to eliminate all their appearances except for one.
We considered two methods for removing repeated factors. The first is referred to as the lcm
method and the second is referred to as the gcd method. The lcm method will be shown to be
faster, but it also requires more space, which might not be available.
In the lcm method we first sort the g i;j s according to their degrees and then place them in
the sets s k , where g i;j 2 s k iff 2 . The sets fs k g are ordered according to
their index, in increasing order. We then begin computing lcms of two polynomials taken from
the first set. If this set has only one polynomial we take the second polynomial from the next
set. The resulting lcm polynomial is placed in the set corresponding to its degree. This process
ends when we are left with one polynomial, representing the lcm of all the polynomials g i;j .
In the gcd method the polynomials g i;j are sorted by their degrees. In each iteration the
polynomial with the highest degree is taken out of the set and and all pairwise gcds between
itself and the other polynomials are taken. If the gcd is greater than 1, the other polynomial is
divided by this gcd. At the end of the iteration none of the remaining polynomials in the set
has a factor in common with the polynomial that was taken out. Thus, when the procedure
ends, no factor appears in more than one of the g i;j s.
Lemma 15:
1. The complexity of the second phase is O(jHj 2 M(n) log n).
2. The expected complexity of the second phase is O(jHj log 3 jHjL(n) log(jHjn)).
Proof:
1. We can bound the work required for the lcm method as follows. First assume jHj and d i;j
are powers of 2 (if they are not, for bounding purposes increase them to the nearest power
of 2). Also, assume the polynomials are leaves of a binary tree. All the polynomials in the
same level have the same degree (each level corresponds to a different set s k ). Assume that
in every lcm step, the degree of the lcm is the sum of the degrees of its two operands (i.e.
the operands are relatively prime). The maximum degree the final lcm can have is jHjn and
computing this lcm costs O(M(jHjn) log(jHjn)). Computing the two lcm's of the next to
last level costs at most O(2 \Delta M(jHjn=2) \Delta log(jHjn=2)). In each lower level there are at most
twice as many lcm's being computed but each costs less than half the cost of the level above
it, hence the total cost is bounded by O(log(jHjn)M(jHjn) log(jHjn)) - O(u 2 M(jHjn)).
To use the lcm method we need enough memory to store the final lcm. If we do not have
the required memory, we use the gcd method. The work required is O(jHj 2 M(n) log n).
2. When taking into account the expected size of the polynomials g i;j , factorization becomes
practical. The factoring algorithm used is that of Cantor and Zassenhaus [4]. The complexity
for factoring a product of r distinct irreducible polynomials of the degree j is given
by O(rM(rj)(j log(rj)). By Lemma 9, the expected number of polynomials g i;j that
have more than 5 factors is less than jHj=10 2k+2 . If we take the number of polynomials
with factors to be 99jH j
polynomials with at most 5 factors are assumed
to have 5, all polynomials with are assumed to have 50, etc.), then the
expected work required to factor all the polynomials is bounded by
OB
99jHj
By using the fact that 5j
bound the sum by
OB
When the factorization is completed, all the irreducible factors can be sorted in time
O(jHj \Delta log jHj) and the unique factors can be counted.
Summing over log n)). Since u -
log jHj, the expression becomes O(jHj log 3 jHjL(n) log(jHjn)).
4.3 Finding a non-factor
We are now at the third phase, where we know the smallest degree d a for which there exists
a non-factor for h. We also have, m - jHj polynomials g i;d a that are products of distinct
irreducible (primitive) factors of h, all g i;d a 's are pairwise relatively prime and every irreducible
(primitive) factor of degree d a of h is a factor of one of these polynomials. We want to find an
irreducible (primitive) polynomial of degree d a that is a non-factor of H.
One approach is to divide the product of all irreducible (primitive) polynomials of degree d a
by the product of all m polynomials and find a factor of the result. This might pose a problem
if we do not have the product at hand, i.e. only the polynomials g i;d a , or if the product is too
large to handle as one polynomial.
Another way is to randomly select irreducible (primitive) polynomials and check whether
they are factors or non-factors. The only way to check is by doing the actual division. This
division, however, will be regular long division, and not FFT division, whenever the divisor
has very small degree compared to the degree of the dividend. If an irreducible (primitive)
polynomial is relatively prime to all of the g i;da 's, it is a non-factor. If it divides at least one of
the polynomials, we can keep the result of the division and reduce our work in upcoming trials.
This reduction requires that polynomials do not repeat in the selection process.
Lemma
1. The complexity of finding a non-factor once d a is known is O(jHj
a M(d a )) for the
irreducible case and O(jHj 2 n 2 d 3
a M(d a ) log log d a ) for the primitive case.
2. The expected complexity is O(jHj log jHjd a M(d a )) for the irreducible case and O(jHj \Delta
log jHj \Delta d 2
a log log d a M(d a )) for the primitive case.
Proof:
1. The procedure generates random polynomials, checks them for irreducibility (primitivity)
and whether they are factors or not. The expected number of random polynomials that
are tested for irreducibility (primitivity) before an irreducible (primitive) polynomial of
degree d a is found is d a =2 ( dalog log d a ) [15]. The work required to test each polynomial
for irreducibility is O(d a M(d a
a M(d a ))) [15]. The sum of the d i;j 's cannot exceed
jHjn, therefore after at most jH jn
da irreducible polynomials are tried, a non-factor is found.
The work involved with each try is jHjn \Delta d a (long division). Thus, the expected work
required to find a non-factor is O(jHj
a M(d a )). For the primitive case the work is
a M(d a ) log log d a ).
2. If the polynomials g i;j were factored (see proof of Lemma 15,(2)), once d a is known, we draw
irreducible (primitive) polynomials until a non-factor is found. We expect no more than
jHj=d a factors. When an irreducible (primitive) polynomial is drawn, it takes O(log jHj)
to check whether it is a factor or not. Hence, the expected work required to find a non-
once d a is known, is bounded by O(jHj log jHjd a M(d a )) for the irreducible case and
O(jHj log jHjd 2
a M(d a ) \Delta log log d a ) for the primitive case.
5 Practical scenarios
In this section we discuss some practical scenarios for finding zero-aliasing polynomials. First,
when we want a non-factor of a pre-specified degree. Second, when we want to find a non-factor
fast. Third, we compare our algorithm for finding a least degree non-factor with an exhaustive
search over all irreducible (primitive) polynomials in ascending degrees. In some cases, this type
of search will be faster.
5.1 Finding a non-factor of a pre-specified degree
In cases where the register is required to function as both a RA and a PG, a non-factor of a
pre-specified degree is needed. Thus
Problem 3: Given a set of polynomials an
irreducible (primitive) non-factor of degree t for H.
This problem is exactly the same as finding the least degree non-factor, except that we only
need to consider the case of t, instead of iterating over all 1 - j - u. We first compute the
polynomials g i;t , then determine whether a non-factor of degree t exists, and if so find one.
Lemma 17:
1. The complexity of finding a non-factor of degree t is O(jHj for the irreducible
case and O(jHj 2 n 2 t 3 M(t) log log t) for the primitive case.
2. The expected complexity is O(jHjM(n)(t log n)).
Proof:
1. Computing the polynomials g i;t involves computing g
for each
l 2 md(t) computing f
. The cost of the first gcd
computation is O(tM(d The cost of the jmd(t)j subsequent gcd and
divisions is bounded by O(log t(tM(d i;t ) +M(d i;t ) log d i;t )). Substituting n for d i and d i;t
we get O(log t log n)).
Once we have the polynomials g i;t , we need to sift out multiple instances of the same irreducible
polynomial. When using the gcd method, this has a worst case cost of O(jHj 2 M(n) \Delta
log n).
At this stage, we know whether a non-factor of degree t exists or not. If one exists, we
carry out phase 3. This has a worst case complexity of O(jHj 2 This is the
dominant term for the whole process. The analysis is the same for the primitive case,
hence the worst case complexity of finding an irreducible (primitive) non-factor of a given
degree t for a set of polynomials H is O(jHj log log t)).
2. We turn to analyze the expected complexity. For each h i , we compute g
x). This costs O(jHjM(n)(t log n)). The cost of sifting out the factors of degree less
than t from the g i;t 's, based on the expected number of factors for each degree, will be
insignificant. Factoring and sorting the polynomials in the second phase has expected cost
of O(jHj log jHjt log n)) (Eq. (5)). The expected number of distinct irreducible
factors of degree t of H is bounded by jHj=t. Thus, the cost of finding a non-factor at this
stage which consists of drawing at most jHj
irreducible (primitive) polynomials, each at
an expected cost of O( ttM(t)) (O( tlog log t \Delta t 2 M(t))), and checking it against the list of
factors, is bounded by O( jHj
ttM(t) log(jHj=t)) for the irreducible case and O(jHj(log jHj \Gamma
log t)t 2 M(t) log log t) for the primitive case. Hence, the expected complexity of finding a
non-factor of degree t for H is bounded by O(jHjM(n)(t log n)).
5.2 Finding a non-factor fast
Problem Given a set of polynomials
find an irreducible (primitive) non-factor of H in less than 2 c tries.
The sum of the degrees of all irreducible (primitive) polynomials of degree less than or equal
to s(d h ) (p(d h )) is greater than d h . If we look at
then
'P u
and if we draw uniformly from all irreducible (prim-
itive) polynomials of degree u, after 2 c drawings we expect to find a non-factor. The expected
work cost for this case is O(2 c \Delta which is the cost of 2 c iterations
of drawing a polynomial and testing for irreducibility, and once one is found dividing all
jHj polynomials by this candidate non-factor, using long division. For the primitive case this
becomes O(2 c \Delta (u 3 M(u) log log u
Example 3: Using the numbers in Example 1 again, say we want to find a non-factor in no
more than 8 tries. We compute the bound p
and draw from all the primitive polynomials
up to the computed bound. If we use table 1, we see that instead of looking at the polynomials
of degree less than or equal to 33, we need to consider all primitive polynomials of degree up to
34. In general, 2 c
- 2, hence by Lemma 6, we only have to consider polynomials of degree
greater by at most 2 than for the case when we want the minimum degree non-factor.
We can also use the expected bounds es(d) and ep(d) to lower the degrees of the candidate
non-factors.
5.3 Exhaustive search
In this subsection, we compare our algorithms with an exhaustive search for a least degree
non-factor. We will look at the irreducible case.
Assume the least degree irreducible non-factor has degree d a . Also, assume we have a list of
all irreducible polynomials in ascending order. The number of irreducible roots of degree j is
less than 2 j . We can bound the work required to find the non-factor, by an exhaustive search,
by O(jHjn2 da+1 ). Using the expected bound on d a (d a = O(log jHj)), we can bound the work by
n). The expected work required to find the least degree non-factor, by our algorithms,
is O(jHju 2 M(n)), which becomes O(jHj log 2 jHj \Delta n log n) when we substitute in the value of u.
Not taking into account any of the constants involved with these two results, the ratio of the
work required for an exhaustive search, relative to the work required for our algorithm is
log 2 jHj log n
Assuming this ratio is less than 1 for n ? 1210. Assuming the ratio is
less than 1 for n ? 124; 500. For the ratio is less than 1 for n ? 365; 284; 284. This
suggests that when the number of faults of interest is "small" (less than 1024) an exhaustive
search might be more efficient than our algorithms. However, as the number of faults increases,
our algorithms are more efficient for test sequences of realistic length. Finally, when the number
of faults is greater than 4096, then for all practical test lengths our algorithms will be more
efficient than the simple exhaustive search.
6 Experimental results
The following experiments were conducted to verify our results. The experiments were conducted
on a HP-700 workstation.
6.1 Random selections based on the absolute bounds
An experiment was set up as follows. We generated a set of 1000 random polynomials of degree
at most 200; 000. This corresponds to a CUT with 1000 faults, i.e. 1000, and a test length
of 200; 000, i.e. The degree of the product of these polynomials (d h ) was less than
or equal to 200; 000; 000. We wanted a probability greater than 1=2 of finding a non-factor
with just one drawing of a primitive polynomial. By looking at table 1, we can achieve this
by selecting from the set of all primitive polynomials of degree less than or equal to 29. The
polynomials were drawn in a 2 step process. The first step selected the degree of the primitive
candidate, the second selected the candidate. In the first step we selected a number and
took its value modulo the number of primitive roots in the fields GF [2] through GF [2 29 ]. The
result was used to determine the degree of the primitive candidate, by looking at the first field
GF [2 d ] such that the number of primitive roots in the fields GF [2] through GF [2 d ] is greater
than the result. The selection of the actual polynomial was done by setting the coefficients
of by a LFSR with a primitive feedback polynomial of degree d \Gamma 1 that was
initialized to a random state. This guarantees that no candidate will be selected twice and all
candidates will have a chance at being considered. The candidates were tested for primitivity
and if they were primitive, they were tested for being non-factors. If at some point they were
found to be factors, the search continued from the current state of the degree
We ran 200 such experiments. In all 200 experiments the first primitive candidate turned
out to be a non-factor. Of the non-factors that were found, 1 was of degree 21, 2 were of degree
22, 3 of degree 23, 2 of degree 24, 7 of degree 25, 13 of degree 26, 32 of degree 27, 35 of degree
28 and 105 were of degree 29.
The number of polynomials that were tested for primitivity before one was found ranged
from 1 to 160. The average number was 16. The time it took to find a primitive polynomial
ranged from 0.01 seconds to 0.79 seconds. The average time was 0.104 seconds. It took between
153.25 and 166.68 seconds to find a non-factor, with the average being 160.50 seconds.
These experiments show that given the error sequences for each of the faults of interest, it
is very easy to find a zero-aliasing polynomial for a circuit.
6.2 Random selections based on the expected bounds
Based on our expected bounds, Corollary 11, we should be able to find a non-factor of degree at
most 14. We ran 100 experiment as above, only this time, we selected only primitive polynomials
of degree 11 (the expected bound based on table 1). The first primitive candidate that was
selected was a non-factor in 66 of the 100 experiments. 19 experiments found the non-factor
with the second candidate, 11 with the third, 2 with the fourth, 1 with the fifth and 1 with the
sixth. We ran 100 experiments selecting only primitive candidates of degree 9. The number of
primitive candidates that were tried before a non-factor was found ranged from 1 to 28. The
average number of candidates was 7:5.
To test the tightness of our expected bound, we ran 126 experiments. In which 1024 random
polynomials of degree at most 200,000 were generated and an exhaustive search, in increasing
order of degrees, was conducted to find the least degree non-factor. By our expected bound,
this least degree should be less than 14. In one experiment, the least degree was 7. In 35 it was
8 and in the remaining 90 experiments, the least degree was 9.
From these experiments we conclude that when the error polynomials are in fact random
polynomials, the expected bounds, based on the analysis of the expected number of factors of a
certain degree for a random polynomial, are in fact upper bounds on the least degree non-factor
for a set of polynomials. As expected, the bounds obtained from table 1 are tighter than those
from Corollary 11.
6.3 Experiments on benchmark circuits
We tried our worst case and expected bounds on error sequences of two circuits from the Berkeley
synthesis benchmarks [2]. The first circuit was in5, the second was in7. We used a fault simulator
that did not take into account any fault collapsing, hence the number of faults was twice the
number of lines in the circuit (for stuck-at-0 and stuck-at-1 faults on each line).
For circuit in5 there were 1092 faults, six of which were redundant, hence there were 1086
detectable faults. The circuit had 14 primary outputs. We used a test sequence of length 6530
that detects all the non-redundant faults and computed the effective output polynomials of all the
faults. All were non-zero, hence there were no cancellation of errors from one output by errors of
another output. Thus we had 1086 error polynomials of degree at most 6543. From table 1, the
worst case bound on the degree of a primitive non-factor is 23. To draw a primitive non-factor
with probability greater than 1we need to consider all primitive polynomials of degree 24 or
less. We conducted 20 experiments of drawing zero-aliasing primitive polynomials, based on our
worst case bounds. In all experiments, the first candidate was a non-factor. We then conducted
another 20 experiments, this time drawing primitive polynomials of degree 14, the size of the
register available at the circuit outputs. In all experiments the first candidate was a non-factor.
Based on our expected bounds (table 1), we should find a non-factor of degree 11 or less. We
tried finding non-factor of degree 11, 9 and 7. For the degree 11 experiments, in 17 of 20 cases,
the first primitive candidate was a non-factor. Two experiments found the non-factor with the
second try, one with the third. We conducted 15 degree 9 experiments before considering all 48
primitive polynomials of degree 9. Of the 48 primitive polynomials of degree 9, 33 were factors,
and 15 were non-factors. The average number of candidates tried before a non-factor was found
was 3 1. All primitive polynomials of degree 7 were factors.
For circuit in7 there were 568 faults, 567 of which were non-redundant. The circuit has 10
primary outputs and we used a test sequence of length 9280. Using the worst case bounds,
to ensure selection of a primitive non-factor with probability greater than 1, we considered all
primitive polynomials of degree 24 or less. All 20 experiments found a non-factor with the first
candidate. The expected bound (table 1) for the degree of a primitive non-factor was 10. We
tried to find non-factors of degree 11 and 10 (the size of the register available at the outputs). All
degree 11 experiments found a non-factor with the first try. Of the
13 found a non-factor with the first try, 6 with the second and one with the third.
For both circuits we tried to find the least degree non-factor using an exhaustive search.
Since the fault extractor we used did not do any fault collapsing, some of the error polynomials
were identical. By summing the values of all non-zero erroneous output words for each simulated
fault, we found at least 292 different error polynomials in in7 and at least 566 different error
polynomials in in5. This would make our expected bounds (table 1) to be 9 for in7 and 10 for
in5. For both circuits the least degree non-factor had degree 8. It took 11 CPU minutes to find
each of these polynomials.
The experiments on the two benchmark circuits show that the assumption that the error
polynomials behave as random polynomials does not invalidate our analysis and results. The
expected bounds, as was the case for the random experiments, were upper bounds on the least
degree non-factor.
Conclusions
In this paper we presented procedures for selecting zero-aliasing feedback polynomials for MISR-
based RAs. When both PGs and RAs are designed as LFSRs/MISRs, our scheme, combined
with algorithms for selecting efficient feedback polynomials for pattern generation [11], enables
the selection of one feedback polynomial that serves both tasks, thus reducing the overhead of
reconfigurable registers.
We presented upper bounds on the least degree irreducible and primitive zero-aliasing polynomial
for a set of modeled faults. We showed that in all practical test applications such a
polynomial will always be of degree less than 53. In fact, by our expected bounds, when the
number of faults is less than 10 6 , this degree will be at most 21. In the experiments that were
conducted, a zero-aliasing polynomial of degree less than the expected bound was always found.
We also presented procedures for finding a zero-aliasing polynomial, when the objective is to
minimize the degree, to have a specific degree or speed. We analyzed the computational effort
that is required both under worst case conditions and expected conditions. A (partial) summary
of the results is presented in table 2. For both the worst case analysis and expected analysis,

table

2 shows the upper bounds on the smallest non-factor, the computational complexity of
finding a smallest non-factor and the complexity of finding a factor of a given degree. When
speed is a requirement, we showed we can find a zero aliasing polynomial with, on average, two
tries, by increasing the degree of the polynomials we consider by at most two over the upper
bound on the size of the minimum degree.
Based on our analysis and on our experiments, it is our conclusion that when the error
polynomials of the modeled target faults are available, zero-aliasing is an easily achievable goal.
Thus, to ensure high quality tests, a premium should be put on fault modeling, automated test
pattern generator design and fault simulation. With these tools available, zero-aliasing is not a
problem.

Acknowledgment

We wish to thank Professors L. A. Adleman, M. A. Breuer, D. J. Ierardi
and L. R. Welch for many helpful discussions. We also wish to thank the anonymous referees
for some very helpful comments.



--R

The Design and Analysis of Computer Algo- rithms
Logic Minimization Algorithms for VLSI Synthesis
Factoring Polynomials Over Large Finite Fields
A New Algorithm for Factoring Polynomials over Finite Fields

Introduction to Algorithms

Concrete Mathematics

Complexity of multiplication in finite fields
Test Embedding with Discrete Logarithms
Introduction to finite fields and their applications
On Achieving Zero Aliasing for Modeled Faults
A. New Framework for Designing and Analyzing BIST Techniques and
Probabilistic Algorithms in Finite Fields
The Book of Prime Number Records
Schnelle Multiplikation von Polynomen - uber K-orpern der Charakteristik 2

--TR

--CTR
Krishnendu Chakrabarty , Brian T. Murray , John P. Hayes, Optimal Zero-Aliasing Space Compaction of Test Responses, IEEE Transactions on Computers, v.47 n.11, p.1171-1187, November 1998
O. Novk , Z. Plva , J. Nosek , A. Hlawiczka , T. Garbolino , K. Gucwa, Test-Per-Clock Logic BIST with Semi-Deterministic Test Patterns and Zero-Aliasing Compactor, Journal of Electronic Testing: Theory and Applications, v.20 n.1, p.109-122, February 2004
built-in self-test;linear feedback shift registers;response compaction;zero-aliasing;signature analysis