IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO.

7 , JULY 1991 867

1
x2
9

Fig. 2. A combinational network realizing the function f(.rl.x2..rg..rq) + +

= f ~ . r ~~ 2 5 3 . ~ 4rlT2.z-3 + .r,Zq.
found out, the problem is reduced to the problem of maximization [6] C. T. Ku and G. M. Masson, “The Boolean difference and multiple fault
and minimization of PB function and hence the present scheme is analysis,” IEEE Trans. Comput., vol. C-24, pp. 62-71, Jan. 1975.
[7] J. P. Roth, “Diagnosis of automata failures: A calculus and a method,”
machine computable and the standard techniques for pseudo-Boolean
I B M J . Res. Develop., vol. 10, pp. 278-291, July 1966.
programming can be applied here. 3) The present contribution is [8] S. B. Akers, “Fault diagnosis as a graph coloring problem,” IEEE Trans.
an enriched one compared to [ l ] in that it covers the cases of Comput., vol. C-23, no. 7, pp. 706-712, July 1974.
simultaneous multiple fault and bridging fault in addition to single [9] S . K . Basu, J.C. Paul, and P.R. Bhattacharjee, “Complete test set
fault. 4) Ku and Masson [6] substantially contributed to multiple fault generation for bridging faults in combinational logic circuits,” Inform.
Sci., vol. 38, no. 3, pp. 257-269, June 1986.
analysis. Theorems 2 and 3 in our contribution simplify the results
[lo] P. Goel, “An implicit enumeration algorithm to generate tests for
of Ku and Masson. This is because, following Theorem 2 of Ku and combinational logic circuits,” IEEE Trans. Comput., vol. C-30, no. 3,
Masson, if one proceeds to find the complete test set for the specified pp. 215-222, Mar. 1981.
multiple fault ATtl-s-a-a,, X , , -s-a-aZ2,. . . . -s-a-aLp on any p 1111 H. Fujiwara and T. Shimono, “On the acceleration of test generation
algorithms,” IEEE Trans. Comput., vol. C-32, no. 12, pp. 1137- 1144,
lines of a logic circuit, he must have to go through the extremely te-
Dec. 1983.
dious task of finding all the first and higher order Boolean differences [12] E. I. Muehldorf and A. D. Savakar, “LSI logic testing-An overview,”
and this can be totally dispensed with by the use of Theorem 2 of this IEEE Trans. Comput., vol. C-30, no. 1, pp. 1- 17, Jan. 1981.
contribution. Similarly Theorem 3 is a simplified form of Theorem 1 1131 P. Hammer and S. Rudeanu, Boolean Methods in Operation Research.
[6]. 5) Following the present scheme, the requirement of extensive New York: Springer-Verlag. 1968.
[I41 P. Hansen, “Un algorithme S.E.P. pour les programmes pseudo-Booleans
tables for the manipulation of Boolean expressions in the algebraic nonlineares,” Cah. du Centre d’Etude de Rech., Operationelle, vol. 11,
approach proposed in [12] can be easily dispensed with. 6) The pp. 26-44, 1969.
present approach will be equally applicable for a combinational [15] 1. Berman, “A branch-and-bound method for the maximization of a
network with or without fan-out nodes unlike the path sensitizing pseudo-Boolean function,” Tech. Rep., Faculty of Math., Univ. of
Waterloo, Ont., Canada, 1969.
technique [3] which requires a recursive search for a network with
[16] P. Hammer and U. Peled, “On the maximization of a pseudo-Boolean
fan-out nodes. 7) Following the present scheme, test input patterns function,”J. ACM, vol. 19, pp. 265-282, Apr. 1972.
are generated automatically. There is no need of recursive search and [17] R. E. Bellman and S. E. Dreyfus, Applied Dynamic Programming.
backtracks as required in D-algorithm [7]. This may amount to a Princeton, NJ: Princeton Univ., Press, 1962.
reduction of computation time.
In spite of the above advantages of the present technique, we are
not proposing right now that it is superior to the most currently used
techniques [lo], [ll]. This is because, deriving logical expressions
for all primary output lines of a large combinational network and Aliasing Probabilities for Feedback Signature
expressing them in terms of different internal nodes assumed to be
Compression of Test Data
faulty is a major effort. Finding real transforms of so many logical
expressions is the second large effort. Practical solutions for these John P. Robinson
two large efforts are the key for the success of the present technique
and deserve more research.
Abstracf- A computationally efficient procedure to find the exact
aliasing probability is presented. The model studied is applicable to test
data errors which have a constant probability of error, correlated or
REFERENCES repeated use errors, or time varying error probability. Simulation results
for various feedback polynomials and data error models are presented.
[ l ] S. G. Papaioannou, “Optimal test generation in combinational networks
by pseudo-Boolean programming,” IEEE Trans. Comput., vol. C-26, Index Terms-Aliasing probability, built-in test, compact testing, data
pp. 553-560, June 1977. compaction, linear filter, signature compression.
[2] -, “The real transform method in fault diagnosis,” Ph.D. dissertation,
Leigh Univ., Bethlehem, PA, 1975.
131 D.B. Armstrong, “On finding a nearly minimal set of fault detection I. INTRODUCTION
tests for combinational logic nets,” IEEE Trans. Electron. Comput.,
vol. EC-15, pp. 66-73, Feb. 1966. One important approach to testing a large digital circuit uses a
[4] F. F. Sellers, M. Y. Hsiao, and L. W. Bearnson, “Analyzing errors with test pattern generator and a test response compression unit. This
Boolean difference,” IEEE Trans. Comput., vol. (2-17, pp. 676-683,
July 1968. Manuscript received July 22, 1988; revised June 1, 1989.
[5] S. S. Yau and Y. S. Tang, “An efficient algorithm for generating complete The author is with the Department of Electrical and Computer Engineering,
test set for combinational logic circuits,” IEEE Trans. Comput., vol. C- University of Iowa, Iowa City, IA 52242.
20, pp. 1245-1251, Nov. 1971. IEEE Log Number 9041283.

0018-9340/91/0600-0867$01.00 0 1991 IEEE

868 IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 7, JULY 1991

methodology avoids the data transfer problem associated with all 1 +x2
the individual input and output patterns which are necessary for high
confidence. Both board level test and built-in test for VLSI often use
this method.
In operation, the test pattern generator is used to stimulate the
circuit under test while the compression unit processes the output test
results to extract some attribute. The compressed result is compared
to a reference to verify correct behavior. A faulty circuit may yield the
same reduced attribute (or signature) as a good circuit. The probability
t=o t=I t-2 t=3 t=4
of this event is called the aliasing probability. A linear feedback
shift register FBSR is the most common compaction method [l].
The procedure is called signature analysis and the final attribute is
called the signature. The required hardware is simple and the reported
performance is good [2]. 1 +x+x2
A linear FBSR has the important property that it is a linear system
and superposition holds. The response of the signature unit to a fault
sequence can be found by adding, mod 2, the correct signature to the
signature of the error pattern itself. Thus, aliasing occurs if and only
if the error pattern has an all zero signature [1]-[3].
The early analytic studies of signature analysis focused on the
entire error pattern in the data [l], [3]. Equally likely error patterns
lead to an aliasing probability of 2-L where L is the length of the t-0 t-l t-2 t:3 t:4
signature register. Recent work has considered each output bit to have
an independent error probability p [4]. For long test sequences the Fig. 1. State transition lattice for 1 + X2 and 1 + X + X 2
aliasing probability approaches 2-r, independently of p (although p
affects the rate at which the aliasing probability approaches 2-”). The
dynamic behavior of the aliasing probability was also found to depend
the probability of being in state 01 at time t +
1 is the sum of
the probability of starting in either 11 or 10 at time t and making
strongly on the particular feedback polynomial used in signature unit.
a particular transition. Given the source-destination state pair and
Primitive polynomials were found to be the best [4].
feedback polynomial we know if E should be a 1 or 0. For example,
In this paper, we will report further results on the exact probability
of aliasing errors for register lengths of practical interest. The
the state transition 11 to 10 occurs if Y = 1 for feedback 1 X 2 +
approach allows us to compute behavior for various polynomials
or I’ = 0 for feedback 1 X + +
.Y2.
We next give the basic recursion expressions for the general case.
with different data error models. The computation method utilizes
Let S denote the state of the lowest L - 1 stages of the shift register
the particular state behavior of shift registers and is closely related to
where the lowest stage is least significant, 2 denote the content of the
the fast Walsh transform. Primitive feedback polynomials with about
last stage, and g ( r ) denote the feedback function of the first L - 1
half the possible number of terms were found to be best.
stages. The serial input D to the shift register is thus given by
11. PROBABILITY
RECURSION D = g(AV)+ 1’ :I 2 (1)
A feedback shift register has a state graph with each state having
two predecessors and two successors [5]. The states can be paired so where 3 denotes Exclusive-OR. In this notation the state pair tran-
that two current states go to a pair of next states in a butterfly pattern sitions are
as in a fast discrete transform. Our approach can be introduced by
considering the case of a two stage compression register. Fig. 1 shows
s + 2.v
a state transition lattice for the two nontrivial feedback polynomials s + 2[,-l + 2-v + 1 (2)
+ + +
1 X2 and 1 X X 2 . We assume that each register is initially
when g ( S ) E’ = 0 and
cleared and that time proceeds to the right. Each edge weight is the
bit input probability for the corresponding state transition, assuming r -+ 2 s + 1
successive input bits are statistically independent. For example, the
upper path from state 00 @ t = 0 to state 11 @ t = 2 represents + 2L-1 i 2 s (3)
Y = 11 with probability p 2 for 1+ X 2 and E- = 10 with probability when g(*Y) I’ = 1 where 0 5 S < 2L-’.
p q for 1 X+ + 9’.
+-

Next let P r ( S , t ) denote the probability of the shift register being

To examine aliasing we can use linearity and just consider the in state S at time t. Time is normalized to integer values. P r ( t )
response to error bits E in the test data E‘ which is the bit-by-bit denotes the probability that the data input Y = 1 at time t. Now we
EOR of W , the correct data, and E the bit error sequence. Aliasing have enough machinery to given the key recurrence.
occurs if and only if the sequence E is not all zero and E compresses Theorem 1: A signature compressor with input probability P r ( t )
to the zero signature. Fig. 2 traces the specific aliasing events of
length 3 and 4. As is well known, these correspond to multiples of the
+
has probability P r ( S . t 1)of being in state S at time t + l given by
feedback polynomial [1]-[4]. Table I lists these events. Note that the +
~ r ( 2 - v , t 1) = p r ( t ) P r ( Y + 2L-1,t )
probabilities of aliasing are different; for example for test length 4,
+ +
case a) is 2p2q2 p4 and case b) is p 2 q 2 2p3y. + (1 - Pr(t))Pr(N,t)
The difference between a) and b) is the edge labels for the Pr(2-Y + 1.t + 1)= P r ( t ) Pr(n’. t )
upper butterfly; the effect of the difference X between the two
feedback polynomials. Our algorithm is recursive in t . For example,
+ (1 - +
~ r ( t ) ) ~ r ( M~ - ‘ , t ) (4)
IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 7, JULY 1991 869

TABLE I
1 +x2 ALIASING EVENTSIN FIG. 2

Length E seq poly form probability

1) = p a) 3 101 1 +X2 P24

Pr(Y=O) =q 4 1010 1+x2 P24*
4 0101 X(l+X2) PZq2
4 1111 +
(1 X ) ( l + x*) P4
t=O t=l t-2 t33 t=4 b) 3 111 l+X+X2 P3
4 1110 lfXfX2 P34
4 0111 x(1+x + X Z ) P34
4 1001 (l+X)[l+X+X2) p2q*

1 + x + x2 length. For this special case the dynamic behavior and resulting
aliasing probability is independent of the feedback function g ( N ) .
Combining expressions (4), ( S ) , and (7) yields Theorem 3.
Theorem 3: A signature compressor of length L with independent
Pr(Y= 1) = p
bit errors of probability one-half has aliasing probability at time
Pr(Y=O) = q
101) L+j,

t=O t=l t=2 t=3 t=4 PA(L + j ) = 0 for j _< 0

- 23 -1
Fig. 2. Aliasing events length 3 and 4 for 1 + S' and 1 + *Y+ X 2 . - 2-L for j > 0. (9)
2-1

if g ( n ; ) = 0 and Note that expression (9) approaches 2 T L , the steady-state value, from
below as j increases. At length L + 1 the aliasing probability is half
Pr(2-V. t + 1) = Pr(t) P r ( S . t ) of the asymptotic value. Next we describe an efficient procedure to
+ (1 - Pr(t))Pr(-v+ 2 L - 1 . t ) calculate the aliasing probability using Theorem 1.

~ r ( +21.t~+ 1) = pr(t) Pr(*\r +2~-'

+ (1 - P r ( t ) )P r ( 4 4
,t ) (5)
111. EXACT ALIASING PROBABILITY
In the current computer technology, relatively large amounts of
if g ( X ) = 1, where 0 5 3 < 2 L - 1 . memory are available. Recursions (4) and ( 5 ) imply a procedure
Proof: Translate the state transition pairs (2) and (3) into prob- with 2" values of the prior state probabilities, one for each register
abilistic form. state. Expression (6) gives the initial conditions and expression (7)
As we are interested in the aliasing probability, the initial condi- the aliasing probability in terms of the state and input probabilities.
tions are Fortunately for register lengths of practical interest, L = 16 and
larger, the number of time steps is only a few hundred before steady-
Pr(S,O) = 1 if S= 0 state behavior is reached. Thus, the straightforward procedure given
=0 ifS#O. (6) by (4), ( S ) , and (7) is feasible to implement. The exact aliasing
probability as a function of time results.
The feedback function of the lowest L - 1 stages can be computed
Aliasing occurs if the error pattern is not all zero and the register once in the initialization phase of the calculation. At each step along
is in state 0 when we check its contents. Thus, the probability of the time axis, pairs of state probabilities are used to compute two next
aliasing at time M , PA(M), is the probability of being in state 0 at state probabilities using (4) and (5). These 2L-' state pair calculations
time M minus the probability of having never left state 0, i.e., the can be computed in parallel and correspond to a fast Walsh transform.
probability of no bit errors. Changes in the bit error probability of I.' as time goes on simply
\I change the transition probabilities for the butterfly steps.
PA(M)= Pr(0, '2.1) - JJ [I - ~ r ( i ) ] . (7) At each time step 2 L multiplications, 2 L subtractions, and 2 L
I=' additions are performed. For a test sequence of length M, 0 ( M 2 " )
Note that if Pr(t) = 1/2 then recursions (4) and (5) are all identical calculations are needed to compute the exact aliasing probability.
and Theorem 2 results. Using (7) the aliasing probability for each test length is available.
Theorem 2: A signature compressor with equally likely one or zero Three different error models are next examined in subsequent
input probabilities has state probabilities given by the recursion sections:
I) Independent bit error with probability p .
Pr(2n',t + 1)= P r ( 2 S + 1.t + 1) 11) Correlated errors where possible bit errors are separated by
= Pr(S + ~ - ' . t ) / 2+ ~ r ( * v . t ) / 2 (8) b time units.
111) Exponential errors, burst like error patterns whose bit error
where 0 5 Y < 2L-'. probability decreases exponentially with time.
Expression (8) describes the dynamic behavior where the final Included are some of the observed behaviors found in our calcula-
equal state probabilities are approached exponentially with the test tions.
870 IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. I , JULY 1991

IV. INDEPENDENT ERRORS 0.00006 ____-

Aliasing probabilty
The shortest duration aliasing event would be the error pattern
corresponding to the feedback polynomial. For P,.i(X) = 1 + I
+ +
X7 + X9 XI2 XI6, the shortest aliasing error sequence would I I
be 10000001010010001. Suppose that the first bit error enters the i
register. Whenever a feedback connection is encountered by this
single one an input error bit of one cancels the feedback so that
Low w t prim
the register includes only a single one. Then when the end of the
register is reached the final input error returns S to zero and the error
is masked.
Independent errors correspond to a binary symmetric channel
model. Each bit has error probability p and successive bits are
statistically independent. Let t denote the weight or number of terms
in the feedback polynomial, e.g., t = U't{P,4(X)} = 5.
+
Clearly, the aliasing probability for L 1 steps is thus 0 00002 -- 7
P.A(L + 1) = p f ( l - p ) L + ' - ' . (10) I
composite

It is instructive to consider a game theory view of expression (10).

Let the first player be the signature designer, the second player is the
noiser who selects the worst value of p . Given the particular feedback
polynomial, P,4(L + 1 ) is maximized by the noiser by setting the bit
+
error probability to t / ( L 1) yielding
0 00002
I
------- I Mld wt prm
I

_ _ _ _ - ~
I
I

hIAX{PA(L + l)}= f t ( L( +L f1l )-Lt)',+'+'

+' . (11) 0 50 100 150
T e s t Length

+ +
If t is small or close to L 1 then PA(L 1) may be very much Fig 3 Aliasing probability for length 18 polynomials wlth independent
errors
larger than the steady-state value of 2TL. For example the L = 17
+ +
primitive polynomial X1' X7 1 has t = 3. If p = 3/18 with this
polynomial, expression (11) yields PA(18) KZ (39)2-17. The rotate corresponding error sequence. Each one in this sequence occurs with
polynomial, l + X ' 7 , with t = 2 is worse with PA(18) KZ ( 2 4 Z ) 2 - 1 i , probability p , each zero with probability (1 - p ) . The data sequence
when p = 2/18. Finally the worst possible polynomial for L = 17 +
length is L j and (12) follows.
is the open loop, p(X) = 1, with t = 1 and P.4(18) % (2735)2-17. Note that expression (12) is exponential in j the test length beyond
The minimum maximum occurs if player one picks f = ( L 1)/2. + L and quickly becomes impractical for computation. Theorem 4 does
For L even the minimax t is ( L = 1 ) / 2 rounded up or down to an suggest some desirable characteristics of the feedback polynomial
integer value. For L odd the minimum maximum is (1/2)2-L, while p ( X ) ; namely that the t , values should be near ( L 1)/2 as j +
for L even the minimax PA is still less than 2-'. Expression (11) increases. Medium weight primitive polynomials appear to be good
changes slowly for small changes in t from ( L 1)/2. + candidates.
+
For length L 2 there are three aliasing events corresponding to Fig. 3 compares the dynamic aliasing probability for three dif-
+
P ( X ) ,X P ( X ) , and (1 X ) P ( X )since signature analysis misses ferent degree 18 polynomials for independent errors with p =
an error if and only if the error polynomial is a multiple of the 0.9. All three cases approach 2-l' for test length greater than
feedback polynomial 111-[4]. We can combine this fact with the 150. The first case is a low-weight (3 terms out of 19 possible)
independent error model to yield Theorem 4. +
primitive polynomial -XIR X i + 1. The second case is a com-
Theorem 4: The aliasing probability for signature analysis with posite polynomial, the product of three shorter primitive polynomials
independent data errors of probability p , test length L J , and+ + +
(_X4+ X 1)(X' + X2 1)("igX4 1 ) . The third case is a + +
feedback polynomial p ( X ) of degree L is given by medium weight primitive polynomial XIH XI5 XI2 XI1 + + + +
2'-1
x 9 + XR+ x' + x6 + 1.
The low weight primitive polynomial has the poorest dynamic
PA(L+J) = p t z ( l -p)L+'-', (12)
z>o behavior, the largest probability being over 1 3 times the asymptotic
value. The peak at test length 31 for the composite polynomial seems
where t , = W t { 7 n 2 ( ~ 7 i ) p ( Xand
) } m , ( X ) is the polynomial with to arise from the X 5 X 2 + +
1 term. By far the most uniform
coefficients given by the binary expansion of 2 . performance is the mid-weight primitive polynomial.
Proof: There are exactly 2' - 1 nontrivial binary polynomials Fig. 4 compares two length 19 polynomials for independent errors
of degree j or less. Each of these polynomials defines one multiple of again with p = 0.9. The upper case is a low weight primitive
p(X) which is compressed to all zero. Conversely any error sequence polynomial X I 9 X5 5 + ' X + + +
1. For L = 19 there are no
+
of length L J , which leads to an aliasing event, is a multiple of primitive polynomials with only three terms. The lower case is the
p ( X ) where the multiplier is of degree J or less. Thus, each n r , ( X ) primitive polynomial
corresponds to an aliasing event and each aliasing event defines an
m,(X).
Expression (12) is just the summation of the probability of these
2 j - 1 mutually exclusive and exhaustive aliasing events. A particular A-19 + ~ 1 + 7X16 + X l 5 + X I 4 + XI3 + x"
multiple m , ( X ) of p(X) will have wt{nr2(-Y)p(X)}ones in the +x10 + xR+x5+ x2+ x + 1
IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 7, JULY 1991 871

4 x 16 multiplexor could have b = 16 if all 16 control combinations

are periodically used.
We represent these patterns using a two-parameter model with b
the span and p the individual bit error probability. Possible bit errors
are separated by b - 1 error-free symbols. In the calculation a speedup
is possible for the time units between errors. With no input errors the
FBSR state transitions are known. These b - 1 step state transitions
can be computed once in the initialization phase. Such a table is
computable in order log base 2 of b steps. During the probability
calculations possible error time units are butterflied, then the next
b - 1 time steps correspond to a state reindexing. Thus, each b time
0.00001
units require 2L multiplications, subtractions, and additions followed
Aliasing Probabilty by a 2 L table lookup.

.l_.U"i::l-; I
An interesting granularity arises for this error model. For those
time units where the input has no errors the aliasing probability does
not change. If the register is all zero it stays at zero while a nonzero
register remains nonzero if the last stage is a linear input to the
0 0 ~
~- feedback.
0 20 40 60 80 100
For any feedback polynomial there will be a state cycle length
for the all one input (see the Appendix). The cycle of interest to
Test L e n g t h us includes the all zero state corresponding to the aliasing event.
Fig. 4. Aliasing probability for length 19 polynomials with independent Let L Z denote the state cycle length for a signature register for the
errors. constant one input where the cycle includes the all zero state. Clearly
L Z 5 2 L (1+ X 2 is the only case we have found with equality). For
a primitive feedback polynomial L Z = 2 L - 1. From our calculations
which has 13 of the possible 20 terms. Again the behavior is similar
of this error model we conjecture:
to that of the two primitive polynomials of Fig. 3 although the
Conjecture 1 : If b is relatively prime to LZ then the aliasing
differences are not as extreme.
probability for correlated errors is identical to that for independent
When the data compressed have independent errors with a fixed
errors if time is normalized by dividing by b on the correlated time
probability p , the aliasing probability approaches 2 T L as the test
axis. The bit probability p is assumed to be the same for both cases.
length becomes long [l].Here L is the register length and 0 < p < 1.
If b divides L Z then the aliasing probability is larger than the case
For p = 0 the aliasing probability is obviously 0 since there are no
when b is relatively prime to L Z . A similar situation was found by
errors. The case of p = 1, which could only arise in practice for
Smith [3] for equally likely correlated error patterns.
unusual cases (Exclusive-OR gates) with perhaps a short test length,
yields a periodic aliasing probability. As the test length increases, the
aliasing probability is mostly 0 with periodic cases of probability 1. VI. EXPONENTIALERRORS
The Appendix examines this limiting case. We next consider a nonstationary error process where the bit error
A number of other calculations were done for various lengths, probability changes with time. The aliasing probability has a range
polynomials, and values of p . As a function of the value of p the of limiting values, strongly dependent on the particular feedback
following behaviors were noted. polynomial. The exponential error model supposes that the bit error
For 0.5 < p < 1.0, Fig. 3 represents the general character: probability decreases exponentially as time goes on. The parameter
Low weight and high weight polynomials have more peaks TAU is the time constant for the model with the probability of a bit
and excursions than mid-weight primitive polynomials. Com- error at time t , p ( t ) , given by
posite polynomials tend to have isolated peaks at test lengths p ( t ) = exp -(t/TAU).
corresponding to the period of their factors. As p increases
above 0.5 towards 1.0, variations in the aliasing probability We normalize time t so that data points occur at integer t . For t
increase in amplitude and occurrence. greater than 4 time constants the probability of error is less than 0.02.
For p = 0.5 all cases reduce to expression (9). This model gives clustered errors which might represent transient
For 0.0 < p < 0.5 the general behavior is more moderate errors or perhaps hard to test faults whose test patterns happen to be
than for case I. For very small p the dynamic shape is located closely together in the test sequence. One can get a feeling for
relatively independent of the particular polynomial and is very this error process by considering the expected number of bit errors
suggestive of an overdamped linear system. N E ( M ) for a length W sequence. Clearly,
p almost 1.0 all cases tend toward a bilevel plot. There are N E ( M ) = { 1 - ~ X ~ ( ~ ' L J / T . ~1U-) }exp(l/T-4U)}.
/{
sharp peaks of probability almost 1 with a general trend toward 2 T L .
As long as p is not 1, the peaks eventually die out and 2-r, is For M greater than 4 TAU and TA4Vgreater than 4, a close
approached. approximation is given by ?;E(M) N TAU +0.5. Thus, about TAU
and a half bit errors are expected in the first four or so time constants
with very few subsequent bit errors.
V. CORRELATEDERRORS Using the direct calculation method described earlier a simulation
study of aliasing with exponential errors was done. Three degree 16
The correlated errors we model were first described by Avizienis polynomials considered by Smith were chosen [2]:
[6] as repeated use faults. The error patterns have erroneous bits
1) A primitive polynomial used in the HP signature units [4]
separated by a span b [3]. The output of a multiplexor driven by a
counter might have periodic errors if a single data input had a fault. A P A ( X ) = Xl6 + X l 2 + x9+ x7+ 1.
872 IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 7, JULY 1991

0 . 0 Y 0 0 3 v
Aliasing
1
Probabilty

0.00002

1 1 TAU 10

prim poly

i 0 20 40 60 80 100
0.0
20 40 80 100
Number of tests

Number of tests Fig. 6 . Aliasing probability for length 16 polynomials with exponential
errors, T.4U = 20.
Fig. 5 . Aliasing probability for length 16 polynomials with exponential
errors, TAU = 10.

2) A composite polynomial, the length 31, 7 error detecting BCH

code
pB(X)= (X+1)(X5+X2+1)(x5+x4+X3+~x2$1)
. (xs+ x4+ x Z+ x + 1)
= XI6 + X I 5 +XI2+X7 +-x6+ X 5 + x 4+ 1.
3) A single stage of feedback

P c ( X ) = ( X + 1 ) ' 6 = AY16+ 1.
The aliasing probabilities for the first and third polynomials for
T.4U = 10 and T.4U = 20 are given in Figs. 5 and 6 as a
function of the test length. The asymptotic or steady-state aliasing
probabilities for long test lengths depend strongly on the feedback
polynomial. P c ( X ) has a higher aliasing probability for TAU = 10
than either P A ( X ) or P B ( X ) , yet P c ( X ) has a lower probability
for TAU = 20. A range of values for TAU was examined and it
was found that there was not much difference between the behavior
of P A ( X )and P s ( X ) . Generally P A ( X ) ,the primitive polynomial,
exhibited somewhat larger dynamic excursions for short test lengths. 1 2 5 10 20 50
This is believed to be due to the smaller number of terms in I'4(X)
as compared to P B ( X ) as suggested by expression (10). Time constant TAU
PC ( X ) exhibited a wide range of aliasing probabilities for various Fig. 7. Summary performance for two length 16 polynomials with expo-
TAU values. The same ripple effect present in Fig. 5 and 6 for nential errors.
P c ( X ) was observed for other TAU values although the scale varied
dramatically. Fig. 7 demonstrates the variation in the steady-state
aliasing probability for both P A ( X ) and P c ( X ) as a function of input is tuned to the natural cycle length of 16 for P c ( - Y ) .For
TAU the time constant of the error process. Note that both scales TAU = 4, which is the square-root of 16, P c ( X ) has its maximum
are logarithmic and that the curves cross twice. The steady-state aliasing probability. Note that this maximum aliasing probability is
value for large TAU is 2-16, the aliasing probability for independent about two orders of magnitude larger than the minimum at TAU =
errors. 16. We would expect that 2-transform analysis would support these
The region in Fig. 7 between about TAU = 12 and TAU = 40 observations.
is somewhat unexpected. In this range P c ( X ) , a single feedback
term from the last stage, has a lower aliasing probability than
PA( X ) a primitive feedback polynomial. For independent errors VII. CONCLUSIONS
Williams et al. [I] observed, "Many simulations have been run, A computationally efficient Markov state space model is developed
and all the results indicate that primitive polynomials are better for determining the aliasing probability of a linear feedback shift
than nonprimitive polynomials." Yet for exponential errors, Pc = register when used for test data reduction. Based on a number of
+
(1 X)I6 which is about as far away as one can get from being simulations of various error models and feedback polynomials it
a primitive polynomial, does perform better in some cases than a appears that a primitive polynomial, with about half its terms nonzero,
primitive polynomial Pq (X). Apparently in this range of TAU the has the best dynamic performance in most cases.
 IEEE TRANSACTIONS ON COMPUTERS, VOL. 40, NO. 7, JULY 1991 873

TABLE I1 J. E. Smith, “Measures of the effectiveness of fault signature analysis,”

ALIASING
PERIODFOR A CONSTANT
ERROR IEEE Trans. Comput., vol. C-29, no. 6, pp. 510-514, June 1980.
T. W. Williams et al., “Aliasing errors in signature analysis registers,”
Feedback Polynomial LZ IEEE Design Test Mag., pp. 39-45, Apr. 1987.
~~~ ~ ~~ S. W. Golomb, Shiff Register Sequences. California, Aegean Park Press,
1+ + x x*+ x 3+ +
. . .‘ X L L+1 1982.
+
1 X L 2L A. Avizienis, “A study of the effectiveness of fault-detection codes for
binary arithmetic,” Jet Propulsion Lab. Tech. Rep. 32-711, Sept. 1965.
p ( X ) primitive 2L -1
( 1 + X ) p ( X ) ,p ( X ) primitive 2L-2

APPENDIX
BEHAVIOR
SIGNATURE FOR CONSTANT 1 INPUT A VLSI Modulo m Multiplier
Consider the signature compression unit with the external input Y Giuseppe Alia and Enrico Martinelli
a constant 1. For aliasing considerations, this is the case of all test
data bits in error. This is the complement of the autonomous case
(input 0) and we find that many of the standard results for autonomous Abstract-In this paper, a new method to compute the exact digits of
FBSR behavior are also complemented [5].For the constant 1 input, the modulo m product of integers is proposed and a modulo m multiply
the all-zero state (aliasing) is periodically encountered as long as structure is defined. Such a structure can be implemented by means of few
fast VLSI binary multipliers and a response time of about 150-200 ns to
some feedback exists, i.e., p ( X ) # 1. The following observations
perform modular multiplications with moduli up to 32767 can be reached.
are straightforward to show. A comparison to ROM-based structures is also provided. Finally, the
Observation I: If a primitive polynomial is used for the feedback modular multiplier has been evaluated asymptotically, according to the
connections of a signature register having a constant 1 input, then the VLSI complexity theory, and it turned out to be an optimal design.
state transition graph has two cycles: This structure can be used to implement a residue multiplier in
arithmetic structures using residue number systems (RNS), whenever
The all one state cycles on itself. such structures are interesting, because of their modularity and easy
All other states, including the all-zero state, form a cycle of feasibility as VLSI components. The complexity of this residue multiplier
length 2L - 1, where L is the length of the register. has been evaluated and lower complexity figures than ROM-based mul-
tiply structures have been obtained, under several hypotheses on RNS
+
Observation 2: I f the polynomial 1 X L is used for the feedback parameters.
connections of a compression register having a constant 1 input, then
the all-zero state is in a cycle of length 2L. (In digital jargon, this Index Terms- Area-time complexity, modulo m multiplier, residue
number systems, table lookup, VLSI.
circuit is sometimes referred to as a twisted ring counter.)
Observation 3: The polynomial 1 + X + .X2 + +
. . * X I , gives
the shortest state cycle, which includes the all-zero state, among all I. INTRODUCTION
possible feedback polynomials for a compression register having a Using residue number systems (RNS) has been interesting many
constant 1 input. The minimum state cycle is of length L 1. The + authors for a long time [1]-161. Such an interest arises because RNS-
state sequence corresponds to a single one shifted along the register. based arithmetic units are fast and simple, at least for addition and
+
Observation 4: If the feedback polynomial is (1 X ) p ( X ) where multiplication which are carry-free in RNS. In practice, speed and
p ( X ) is a primitive polynomial, then the state transition graph of the simplicity are limited to applications for which the dynamic range
compression register having a constant 1 input has two cycles: of data does not overgrow and scaling is relatively simple or can
The two states of alternate ones and zeros form a cycle of length 2. be avoided by means of an acceptable redundancy, as transforms
All other states, including the all-zero state, form a cycle of and digital filtering, and special RNS-based structures have been
length 2L - 2 . The period LZ for which the aliasing probability designed [7]-[lo]. However, when a high precision requires a wide
goes to 1, for the constant error input, is thus summarized in range of representation, even only a reasonable redundancy may
Table 11. lead to a dramatic amount of the range; in these situations residue
When the feedback polynomial is the product of several terms, arithmetic units able to operate with high magnitude moduli can
the constant one input period depends on the individual terms. For be advantageous. Such units are investigated in this paper, with a
example, P B ( X ) the degree 1 6 generator polynomial for the BCH particular concern in the problem of computing the exact residue
code considered earlier factors: digits of the product of integers represented in RNS. A new method
to multiply integers modulo m is proposed, which is based on an
pB(x)= (x+ 1)(x5
+ x 2 + 1)(x5+ + x”+ x 2+ 1) approximate fractional binary multiplication and on a simple way
(x5+ x4+ x 2+ x+ 1). of correcting the related error completely. A modulo m multiplying
structure is defined and evaluated both as for its practical feasibility
For P B ( X )the period LZ is 62 or 2 times 31. The first term above by means of LSI/VLSI components, and in terms of asymptotic
has a period of 2 and each of the last three terms has a period of 31.
Manuscript received May 2, 1988; revised April 12, 1990. This work was
supported by the National Program on Solid State Electronics and Devices of
REFERENCES the Italian National Research Council.
G. Alia is with the Dipartimento di Ingegueria dell’hformazione, Faculty
R. A. Frohwerk, ‘‘Signature analysis: A new digital field service method,” of Engineering, University of Pisa, Pisa, Italy.
Hewlett-Packurd J., pp. 2-8, May 1977. E. Martinelli is with the Istituto di Elaborazione dell’hformazione, Italian
E. J. McCluskey, “Built-in self test techniques,” IEEE Design Test Mag., National Research Council, Pisa, Italy.
pp. 21-28, Apr. 1985. IEEE Log Number 9041287.

001&9340/91/06OC-0873$01.00 0 1991 IEEE