Deterministic Built-in Pattern Generation for Sequential Circuits.
We present a new pattern generation approach for deterministic built-in self testing (BIST) of sequential circuits. Our approach is based on precomputed test sequences, and is especially suited to sequential circuits that contain a large number of flip-flops but relatively few controllable primary inputs. Such circuits, often encountered as embedded cores and as filters for digital signal processing, are difficult to test and require long test sequences. We show that statistical encoding of precomputed test sequences can be combined with low-cost pattern decoding to provide deterministic BIST with practical levels of overhead. Optimal Huffman codes and near-optimal Comma codes are especially useful for test set encoding. This approach exploits recent advances in automatic test pattern generation for sequential circuits and, unlike other BIST schemes, does not require access to a gate-level model of the circuit under test. It can be easily automated and integrated with design automation tools. Experimental results for the ISCAS 89 benchmark circuits show that the proposed method provides higher fault coverage than pseudorandom testing with shorter test application time and low to moderate hardware overhead.
Table

1 illustrates the Huffman code for an example
test set TD with four unique patterns out of a total of
eighty. Column 1 of Table 1 lists the four patterns,
lists the corresponding number of occurrences
fi of each pattern Xi , and column 3 lists the
corresponding probability of occurrence pi , given by
fi =jTDj. Finally, column 4 gives the corresponding
Huffman code for each unique pattern. Note that the
most common pattern X1 is encoded with a single 0
bit; that is e.X1/ D 0, where e.X1/ is the codeword for
X1. Since no codeword appears as a prefix of a longer
codeword (the prefix-free property), if a sequence of
encoded test vectors is treated as a serial bit-stream, decoding
can be done as soon as the last bit of a codeword
is read. This property is essential since variable-length
codewords cannot be read from memory as words in
the usual fashion.
The Huffman code illustrated in Table 1 can be con-
structedbygeneratingabinarytree(Huffmantree)with

Table

1. Test set encoding for a simple example test sequence
of test patterns.
Unique Occur- Probability Huffman Comma
patterns rences of occurrence codeword codeword
100 Iyengar, Chakrabarty and Murray
Fig. 2. An example illustrating the construction of the Huffman
code.
edges labeled either 0 or 1 as illustrated in Fig. 2. Each
unique pattern Xi of Table 1 is associated with a (leaf)
node of the tree, which initially consists only of these
unmarked nodes. The Huffman coding procedure
iteratively selects two nodes vi and vj with the lowest
probabilities of occurrence, marks them, and generates
a parent node vij for vi and vj . If these two nodes are
not unique, then the procedure arbitrarily chooses two
nodes with the lowest probabilities. The edges (vij;vi)
and (vij;vj) are labeled 0 and 1. The 0 and 1 labels
are chosen arbitrarily, and do not affect the amount of
compression [18]. The node vij is assigned a probability
of occurrence pij D pi C pj. This process is
continued until there is only one unmarked node left in
the tree.
Each codeword e.Xi / is obtained by traversing the
path from the root of the Huffman tree to the corresponding
leaf node vi . The sequence of 0-1 values
on the edges of this path provides the e.Xi /. The
Huffman coding procedure has a worst case complexity
of O.m2 log m/, thus the encoding can be donein reasonable time. The average number of bits per
patternPlH (average length of a codeword) is given by
lH D imD1 wi pi , where wi is the length of the code-word
corresponding to test pattern Xi . The average
length of a codeword in our example is therefore given
by lH D 1  0:5625 C 2  0:1875 C 3  0:1875 C 3
0:0625 D 1:68 bits.
We next compare Huffman coding with equal-length
coding. Let lH .lE/ be the average length of a code-word
for Huffman coding (equal-length coding). Since
Huffman coding is optimal, it is clear that lH  lE.We
next show that lH D lE under certain conditions.
Theorem 1. If all unique patterns have the same
probability of occurrence and the number of unique
patterns m is a power of 2; then lH D lE .
Proof: If all the unique patterns in TD have the
same probability of occurrence p D 1=m, the entropy
H.TD/ D imD1 pi log2 pi D log2 m bits. For equal-length
encoding, lE Ddlog2 me, and if m is a power of
then lE D log2 m, which equals the entropy bound.
Therefore, l DlE for this case.
The above theorem can be restated in a more general
form in terms of the structure of the Huffman tree.
Theorem 2. If the Huffman tree is a full binary tree;
then lH D lE .
Proof: A full binary tree with k levels has 2k  1
vertices, out of which 2k1 are leaf vertices. Therefore
if the Huffman tree is a full binary tree with m leaf
vertices, then m must be a power of 2 and the number
of levels must be log m C1. It follows that every pathfrom the root to a leaf vertex is then of length log m.
If all unique patterns in TD have the same probability
of occurrence and m is a power of 2, then the Huffman
tree is indeed a full binary tree; Theorem 2 therefore
implies Theorem 1. Note that Theorem 2 is sufficient
but not necessary for lH to equal lE. Figure 3 shows a
Huffman tree for which lH D lE D 2, even though it is
not a full binary tree.
The practical implication of Theorem 1 is that
Huffman encoding will be less useful when the probabilities
of all of the unique test patterns are similar.
This tends to happen, for instance, when the ratio of the
number of flip-flops to the number of primary inputs
in the CUT, denoted  in Section 4, is low. Theorem 2
suggeststhatevenwhen ishigh, theprobabilitydistri-
bution of the unique test patterns should be analyzed to
Fig. 3. An example of a non-full binary tree with l D lE.
determine if statistical encoding is worthwhile. How-
ever, in all cases we analyzed where  was high, statistical
encoding was indeed effective.
Comma Codes
Although Huffman codes provide optimal test set com-
pression, they do not always yield the lowest-cost decoder
circuit. Therefore, we also employ a non-optimal
code, namely the Comma code, which often leads to
more efficient decoder circuits. The Comma code, also
prefix-free, derives its name from the fact that it contains
a terminating symbol, e.g. 0, at the end of each
codeword.
The Comma encoding procedure first sorts the
unique patterns in decreasing order of probability of
occurrence, and encodes the first pattern (i.e., the most
probable pattern) with a 0, the second with a 10, the
third with a 110, and so on. The procedure encodes
each pattern by addinga1tothebeginning of the previous
codeword. The codeword for the ith unique pattern
Xi is thus given by a sequence of .i 1/ 1s followed by
a 0. Comma codewords for the unique patterns in the
example test set of Section 2.1 are listed in Column 5 of

Table

1. This procedure has complexity O.m log m/and is simpler than the Huffman encoding procedure.
The Comma code also requires a substantially simpler
decoder DC than the Huffman code. Since each
Comma codeword is essentially a sequence of 1s followed
by a zero, the decoder only needs to maintain
a count of the number of 1s received before a 0 signi-
fies the end of a codeword. The 1s count can then be
mapped to the corresponding test pattern.
For a given test sequence TD with m unique patterns
having probabilities of occurrence p1  p2
pm, the aPverage length of a Comma codeword is
given by lC D imD1 ipi. Since the code is non-optimal,
lC  lH. However, the Comma code provides near-optimal
compression, i.e., limm!1.lC  lH/ D 0, if
TD satisfies certain properties. These hold for typical
test sequences that have a large number of repeated
patterns. We first present the condition under which
Comma codes are near-optimal and then the property
of TD required to satisfy the condition.
A binary tree with leaf nodes X1; X2;:::;Xm is
skewed if the distance di of Xi from the root is given
by
di D (1)
Deterministic Built-in Pattern Generation 101
For instance, the Huffman tree of Fig. 2 is a skewed
binary tree with four leaf nodes.
Theorem 3. Let p1  p2  pm be the probabilities
of occurrence of the m unique patterns in TD.
Let lH and lC be the average length of the codewords
for Huffman and Comma codes; respectively. If the
Huffman tree for TD is skewed then lC  lH D pm and
limm!1.lC  lH / D 0.
Proof:PIf the Huffman tree for TD is skePwed then
lH D imD11 ipi C .m  1/pm and lC D imD1 ipi.
Therefore, lC  lH D pm. We also know that p1
p2  pm. Therefore, 0  pm  1=m, which implies
that limm!1 pm D 0. Hence lC lH is vanishingly
small for a skewed Huffman tree and the Comma
code is near-optimal.
Next we derive a necessary and sufficient condition
that TD must satisfy in order for its Huffman tree to be
skewed.
Theorem 4. Let p1  p2    pm be the probabilities
of occurrence of the unique patterns in TD.
The Huffman tree for TD is skewed if and only if; for
the probabilities of occurrence satisfy
the condition
Xm
Proof: We prove sufficiency of the theorem. The necessity
can be proven similarly. Generate the Huffman
tree for the m patterns X1; X2;:::;Xm in TD whose
probabilities of occurrence satisfy (2). Let the leaf node
corresponding to the ith pattern be vi . The two leaf
nodes vm and vm1 corresponding to the patterns Xm
and Xm1 with the lowest probabilities pm and pm1
are first selected, and a parent node vm.m1/, with the
probability .pm C pm1/, is generatePd for them. Now,
pm3  pm2, andfrom(2), pm3  mkDm1 pk.Thus,
pm3  pm1 C pm. Therefore, the leaf node vm2
and vm.m1/ are now the two nodes with the lowest
probabilities, and a parent vm.m1/.m2/ with probability
.pm C pm1 C pm2/ is generated for them.
Similarly, a parent vm.m1/i is generated for nodes
vi and vm.m1/.iC1/;i 2f.m3/1g. The process
terminates when the root vm.m1/1 is generated for leaf
node v1 and vm.m1/2. The distance d1 of v1 to the root
is therefore 1. Similarly di D i, i 2f2;3;:::;m1g.
Leaf nodes vm and vm1 are equidistant from the root,
Iyengar, Chakrabarty and Murray
since they share a common parent vm.m1/, thus dm D
m 1. Therefore, di satisfies (1) for i 2f1;2;:::;mg,
and the Huffman tree is skewed.
We next determine the relationship between jTDj and
m, the number of unique patterns in the test set when
the Huffman tree is skewed. We show that jTDj must
be exponential in m for the Huffman tree to be skewed.
This property is often satisfied by deterministic test sets
for sequential circuits with a large number of flip-flops
but few primary inputs.
Theorem 5. Let jTDj and m be the total number of
patterns and the number of unique patterns in TD; res-
pectively. If the Huffman tree for TD is skewed then
denotes an asymptotic
lower bound in the sense that f .m/ D !.g.m// implies
limm!1 gf.m/ D1.
Proof: Let f1  f2    fm be the numbers
of Poccurrence of the unique patterns in TD. Then
jTDjD imD1 fi. We know that fm1  fm  1, and
fm2  fm  1. From (2), fm3  fm1 C fm  2. Sim-
ilarly, fm4  3 and fm5  5. The lower bounds on
thus form the FibPonacci series
3; 5;:::I therefore, jTDj1C imD1si, where si is
the ith Fibonacci termp, given by si D p1p.'iC1
'O iC1/; where ' D 1 .1 C 5/ and 'O D 1 .1  5 5/ [21].
'Om). For even m,1
from which it follows that jTDjD!.1:62m/. The proof
for odd m is similar.
Comma codes, being non-optimal, do not always
yield better compression than equal-length codes. The
following theorem establishes a sufficient condition
under which Comma codes perform worse than equal-length
codes.
Theorem 6. Let p1  p2    pm be the probabilities
of occurrence of the unique patterns in TD.
2dlog me
If pm > m.mC2 1/ ; then lC > lE ; where lC .lE / is the
average codeword length for Comma .equal-length/
coding.
Proof: We know that lE Ddlog2 me and lC D p1 C
2p2 CCmpm. Since p1  p2    pm,lC
if 12 pmm.m C 1/>dlog2 me, from which the theorem
follows.
For example, in the test set for s35932 obtained
using Gentest, m D 86 and pm D 0:012, while
2dlog me=86.87/ D 0:0019. Hence, Comma codingperforms worse than equal-length coding for this
test set.
Note that Theorem 6 not provide a necessary condition
for which lC > lE. In fact, it is easy to construct
data sets for which lC > lE even though pm
2dlog me
. The following theorem provides a tighter con-
m.mC1/
dition under which Comma codes perform worse than
equal-length codes.
Theorem 7. Let p1  p2  pm be the probabilities
of occurrence of the unique patterns in TD; and
let lC .lE / be the average codeword length for Comma
coding .equal-length coding/. Let fi D mini f ppiCi 1
me
Proof: We first note that pi  fipiC1 Pfi2 piC2
fimi pm,1i m. Since lC D imD1 ipi,it
follows that lC  fim1 pm C 2fim2 pm C 3fim3 pm C
C.m1/fipm C mpm. Let E be defined as
such that lC  E. From (4), we get
From (4) and (5), we obtain
me
fim1fi.mC21/Cm and the theorem follows.
If m  1 then (3) can be simplified to pm
fi.fim1/2mdlo.fig2m1e/ . In addition, if mini f ppiCi 1 g exceeds 2, i.e.

Table

2. Huffman and Comma code words for the patterns in
the test set of s444.
Test Occur- Probability of Huffman Comma
pattern rences occurrence codeword codeword
every data pattern occurs twice as often the next most-frequent
data pattern, then we can replace fi by2in
(3) to obtain the following simpler sufficient condition
under which Comma codes perform worse than equal-length
codes.
Corollary 1. Let p1  p2   pm be the probabilities
of occurence of the unique patterns in TD; and
let lC .lE / be the average codeword length for Comma
coding .equal-length coding/.IffiDmini f ppiCi 1 g > 2
dlog me
and pm > 2m12m2 ; then lC > lE .
However, the skewing probability distribution property
of Theorem 4 appears to be easy to satisfy in most
cases. The probabilities of occurrence of patterns for a
typical case (the s444 test set) are shown in Table 2 in
Section 3. The decrease in compression resulting from
the use of Comma codes, instead of optimal (Huffman)
codes to compress such test sets, which is given by
Deterministic Built-in Pattern Generation 103
lC  lH D pm from Theorem 3, is extremely small in
practice. For the s444 test set, pm D 0:0005;lH D
1:2121, and therefore lC D 1:2126, and the compression
loss is only one bit. Therefore, both Huffman and
Comma codes can efficiently encode sequential circuit
test sets.
3. TGC Design
In this section, we illustrate our methods for constructing
employing statistical encoding of precomputed
test sequences. We illustrate the steps involved
in encoding and decoding with the test set for the s444
benchmark circuit as an example.
Huffman Coding
The first step in the encoding process is to identify the
unique patterns in the test set. A codeword is then
developed for each unique pattern using the Huffman
code construction method outlined in Section 2. The
Huffman tree used to construct codewords for the patterns
of s444 is shown in Fig. 4. The unique test patterns
and the corresponding codewords for s444 are
listed in Table 2. The original (unencoded) test set TD,
which contains 1881 test patterns of 3 bits each, requires
bits of memory for storage. On
the other hand, the encoded test set has only 1.2121
bits per codeword, and hence requires only 2280 bits
of memory. Therefore, Huffman encoding of TD leads
to 59.59% saving in storage, while both the order as
well as the contiguity of test patterns are preserved.
Once the encoded test set TE is determined by applying
the Huffman encoding procedure to TD,itis
Fig. 4. Huffman tree for the test set of s444.
104 Iyengar, Chakrabarty and Murray
Fig. 5. Illustration of the proposed test application technique.
stored on-chip and read out one bit at a time during
test application. The sequence generator SG of Fig. 1
is therefore a ROM that stores TE. The test patterns
in TD can be obtained by decoding using a simple
finite-state machine (FSM) [20]. Table-lookup based
methods that are typically used for software implementations
of Huffman decoding are inefficient for on-chip,
hardware-implemented decoding.
The decoder DC is therefore a sequential circuit, unlike
for combinational and full-scan circuits where a
combinational decoder can be used [12, 22]. Figure 5
outlines the proposed test application scheme. We exploit
the prefix-free property of the Huffman code; thus
patterns can be decoded immediately as the bits in the
compressed data stream are encountered. We next describe
the state diagram of the FSM decoder DC using
the s444 example.

Figure

6 shows the state transition diagram of DC.
The number of states is equal to the number of non-leaf
nodes in the corresponding Huffman tree. For
example, the Huffman tree of Fig. 4 has seven non-leaf
nodes, hence the corresponding FSM of Fig. 6
has seven states-S1; S2;:::;S7. The FSM receives
a single-bit input from SG, and produces n-bit-wide
test patterns, as well as a single-bit control output
TEST VEC. The control output is enabled only when
a valid test pattern for the CUT is generated by the
decoder-this happens whenever a transition is made
to state S1. The use of the TEST VEC signal ensures
that the test sequence TD is preserved and no additional
test patterns are applied to the CUT. Hence Huffman
codes provide an efficient encoding of the test patterns
Fig. 6. State transition diagram for the FSM decoder of s444.
and a straightforward decoding procedure can then be
used during test application. The trade-off involved
is the increase in test application time t since the decoder
examines only one bit of in each clock cycle.
Fortunately, the increase in t is directly related to the
amount of test set compression achieved-the higher
the degree of compression, the lesser is the impact on t.
Theorem 8. The test application time t increases by a
lH is the average length of a Huffman
codeword.
Proof: The state transition diagram of Fig. 6 shows
that wi clock cycles are required to apply a test pattern
Xi which is mapped to a codeword of wi bits. Hence
the test application time (number of clock cycles) is
given by t D iD1 wi , where jTDj is the total number
of patterns in the test set TD. TPhejTtDejst application time
therefore increases by a factor iD1 wi =jTDjDlH, the
average length of a codeword.
Experimental results on test set compression in
Section 4 show that the average length of a Huffman
codeword for typical test sets is less than 2. This implies
that the increase in test application time rarely exceeds
100%. Since test patterns are applied in a BIST
environment, this increase in testing time is acceptable,
and it has little impact on testing cost or test quality.

Figure

7 shows the netlist of the decoder circuit for
s444. This circuit was generated for a test set obtained
using Gentest. The design is simplified considerably
by the presence of a large number of don't-cares in the
decoder specification, which a design automation tool
can exploit for optimization.
The cost of the on-chip decoder DC can be reduced
by noting that it is possible to share the same decoder
on a chip among multiple CUTs. The encoding problem
is now reformulated to encode the test sets of the
CUTs together. We do this by combining these test
sets to obtain a composite test set T 0 and applying the
encoding procedure to T 0 to obtain an encoded test set

Figure

8 illustrates a single sequence generator
SG0 and pattern decoder DC0 used to apply test sets to
multiple CUTs that have the same number of primary
inputs. Note that such sharing of the pattern decoder
is also possible if the CUTs have an unequal number
of primary inputs. The sharing is, however, more effi-
cient if the difference in the number of primary inputs
is small. The slight increase in the size of T 0 (com-
pared to TE) is offset by the hardware saving obtained
Deterministic Built-in Pattern Generation 105
Fig. 7. Gate-level netlist of the FSM decoder for s444.
by decoder sharing. We next present upper and lower
bounds on the Huffman codeword length for two test
sets that are encoded jointly.
Theorem 9. Let TD1 and TD2 be test sets for two
CUTs with the same number of primary inputs and
let TD0 be obtained by combining TD1 and TD2. Let
m1; N1;l1; and m2; N2;l2 be the number of unique pat-
terns; total number of patterns; and average Huffman
codeword length for TD1 and TD2; respectively. Let l0
be the average Huffman codeword length for T 0 and
let m0 and N0 be defined as: m0 D maxfm1; m2g and
In addition; let pi .qi /; 1  i  m0; be
the probability of occurrence of the ith unique pattern
Fig. 8. A BIST sequence generator and decoder circuit used to test multiple CUTs.
106 Iyengar, Chakrabarty and Murray
in TD1.TD2/. Then
log flmin  1
l  N0  log2 fimax C
where .i/fimax is the largest value of fi such that N1 pi C
is the smallest value of fl such that N1 pi C N2qi
N0flpi and N1 pi C N2qi
Proof:hskip10ptWe use the fact that
H.TD1/ l1  H.TD1/
and H.TD2/ are the entropies of TD1 and TD2, respec-
tively. The probability of occurrence of the ith unique
pattern in TD0 is .N1 pi C N2qi /=N0. The entropy of TD0
is therefore given by
H.T / D log
It follows from the theorem statement that
Therefore,
N0 .l1  log2 fimax/ C N0 .l2  log2 fimax/
D  log fimax
Therefore, l0  [.N1l1 C N2l2/=
Next we prove the lower bound. Once again from
the theorem statement,
flmin
Note that the lower bound is meaningful only if pi D
requiresthat TD1 and TD2 have the same set of unique patterns
and therefore m0 D m1 D m2.
Therefore,
Now, H.TD1/  l11 and H.TD2/  l21. Therefore,
l0  H.TD0 /  [.N1l1 C N2l2/=N0]  log2 flmin  1.
A tighter lower bound on l0 is given by the following
corollary to Theorem 9.
Corollary 2. Let l1 D H.TD1/ C -1 and l2 D H.TD2/
C -2; and let flmin be defined as in Theorem 9; where
As a special case, if N1 D N2 then 12 .l1 Cl2/  log2
For example, let TD1 and TD2 be test sets for two
different CUTs with five primary inputs each. Suppose
they contain the unique patterns shown in Fig. 9, with
N1 D N2. The probabilities of occurrencePof patterns
in TD1 and TD2 satisfy (2), therefore l1 D i4D1 ipi C
4p5 D 1:25. Similarly, l2 D 1:31. From Theorem 9,
fimax D 0:58, and flmin D 3:5: Since N1 D N2, the
bounds on l0 are given by 12 .l1 C l2/  log2 flmin  1
Therefore, 1:03
Fig. 9. Unique patterns and their probabilities of occurrence
for the example illustrating Theorem 9.
l0  3:55. Now, the patterns in T 0 also satisfy (2), and
therefore l0 D 4 ip0 C4p0 D 1:33, which clearly
lies between the calculated bounds, where p0 is the
probability of occurrence of pattern Xi in TD0 .
Experimental results on test set encoding and decoder
overhead in Section 4 show that it is indeed possible
to achieve high levels of compression while reducing
decoder overhead significantly if test sets for
two different CUTs with the same number of primary
inputs are jointly encoded and a single decoder DC0 is
shared among them.
Comma Coding
We next describe test set compression and test application
using Comma encoding. Once again, we illustrate
the encoding and decoding scheme using the s444
example.
The unique patterns in the test set are first identified,
and sorted in decreasing order of probability of occur-
rence. Codewords are then generated for the patterns
according to the Comma code construction procedure
described in Section 2. Comma codewords generated
for the unique patterns in the s444 test set are listed in

Table

2. The probabilities of occurrence of test patterns,
shown in Table 2 clearly satisfy (2) in Theorem 3, and
therefore the encoding is near-optimal. The Comma
encoded test set has 1.2126 bits per codeword, and requires
2281 bits for storage, an increase of only one
bit from the optimally (Huffman) encoded test set described
in Section 3. Hence the reduction in test set
compression arising from the use of Comma codes instead
of Huffman codes for this example is only 0.02%.
The slight decrease in test set compression due to
the use of the Comma code is offset by the reduced
complexity of the pattern decoder DC. Figure 10 illustrates
the pattern decoder for the s444 circuit test set.
The decoder is constructed using a binary counter and
combinational logic that maps the counter states to the
test patterns. The test application scheme is the same
as that in Fig. 5 for the Huffman decoder.
The inverted input bit is used to generate the
TEST VEC signal which ensures that the CUT is
clocked only when a 0 is received. TEST VEC is also
gated with the clock to the CUT and used to reset the
the counter on the falling edge of the clock. Bits with
value 1 received from SG therefore result in the flip-
flops of the counter being clocked to the next state,
while 0s (the terminating commas present at the end
Deterministic Built-in Pattern Generation 107
Fig. 10. The Comma pattern decoder for the s444 test set.
state after half a clock cyle. The test pattern can thus be
latched by the CUT before the counter is reset. Comma
decoders are simpler to implement than Huffman de-
coders, and binary counters already present for normal
operation can be used to reduce overhead. As in the
case of Huffman coding (Theorem 8), the increase in
testing time due to Comma coding equals the average
length of a codeword.
Run-Length Encoding
Finally, we describe run-length encoding of the statistically
encoded test sequence TE to achieve further
compression. We exploit the fact that sequences of
identical test patterns (runs) are common in test sets
for sequential circuits having a high ratio of flip-flops
to primary inputs. For example in the test set for s444,
runs of the pattern 000 occur with lengths of up to
70. Huffman and Comma encoding exploit the large
number of repetitions of patterns in the test sequence
without directly making use of the fact that there are
many contiguous, identical patterns. Run-length encoding
exploits this property of the test sequences-it
therefore complements statistical encoding. Huffman
and comma encoding transform the sequence of test
patterns to a compressed serial bit stream, and in the
test set, each occurrence of the test pattern 000 is
replaced bya0(Table 2). Therefore, long runs of 0s
are present in the statistically compressed bit stream,
108 Iyengar, Chakrabarty and Murray

Table

3. Distribution of runs in the Huffman encoded
test set for the s444 circuit.
No. of runs No. of runs
Run- Run-length
0s 1s length 0s 1s
which can be further compressed using run-length
coding.
Run-length coding is a data compression technique
that replaces a sequence of identical symbols with a
copy of the repeating symbol and the length of the se-
quence. For example, a run of 5 0s (00000) can be
encoded as (0,5) or (0,101). Run-length encoding has
been used recently to reduce the time to download test
sets to ATE across a network [23, 24]. We improve
upon the basic run-length encoding scheme by considering
only those runs that have a substantial probability
of occurrence in the statistically encoded bit stream. A
unique symbol representing a run of a particular length
(and the corresponding bit) is then stored. The value of
the repeating bit is generated from the bits representing
the length of the run during decoding. We therefore
obviate the need to store a copy of the repeating
bit.
We describe our run-length encoding process using
the s444 example. An analysis of its Huffman encoded
test set yields the distribution of runs shown in

Table

3. Encoding all runs would obviously be expensive
(4 bits would be required for each run) since
very few instances of (0,4), (0,5) and (1,3), and no
instances of (1,5), (1,6), (1,7) or (1,8) exist. We therefore
use combinations of 3 bits (000; 001;:::;111)
to encode the 8 most frequently occurring runs-(0,1),
(0,2), (0,3), (0,7), (0,8), (1,1), (1,2) and (1,4). The less-
frequently occurring runs (0,4), (0,5), (0,6) and (1,3)
are divided into smaller consecutive runs for encoding.
For example (0,5) is encoded as (0,3) followed by (0,2).

Figure

encoding applied to a
portion of the Huffman encoded s444 test set. The
encoded runs are stored in a ROM and output to a run-length
decoder. The run-length decoder provides a single
bit in every clock cycle to the Huffman (or Comma)
decoder for test application.
The run-length decoder consists of a binary down
counter, and a small amount of combinational logic.

Figure

12 illustrates the run-length decoder for the
test set. The bits used to encode a run (e.g.,
011 for (0,7)-Fig. 11(a)) are first mapped to the run-length
bits). The run-length is loaded into
the counter which outputs the first bit of the run. The
counter then counts down from the preset value 110 to
000, sending a bit (0, for this example) to the Huffman
decoderineveryclockcycle. Whenthecounterreaches
000, the NOR gate output becomes 1, enabling the
ROM to output the bits representing the next run. Since
one bit is received by the Huffman decoder in every
clock cycle, run-length decoding does not add to testing
time.
4. Experimental Results
In this section, we present experimental results on test
set encoding for several ISCAS 89 benchmark circuits
to demonstrate the saving in on-chip storage achieved
using Huffman, Comma and run-length encoding. We
Fig. 11. Run-length encoding applied to a portion of the Huffman encoded s444 test set: (a) 3-bit encoding
for 8 types of runs, (b) bit stream to be encoded, and (c) run-length encoded data.
Fig. 12. Run-length decoder for the s444
test set.
consider circuits in which the number of flip-flops f is
considerably greater than the number of primary inputs
n; we denote the ratio f=n by . Table 4 lists the values
of  for the ISCAS 89 circuits, with circuits having a
high value of  shown in bold. Such circuits are especially
hard to test because of the relatively large number
of internal states and few primary inputs. From Table 4

Table

4. The ratio of the number of flip-flops to the
number of primary inputs , and jTDj, the length of the
HITEC test sequences for the ISCAS 89 circuits.
CUT  jTDj CUT  jTDj
Deterministic Built-in Pattern Generation 109
we see that these circuits typically require longer sequences
of test patterns. On the other hand, they are
excellent candidates for our encoding approach.
Several other ISCAS 89 benchmark circuits do not
have a high value of , and are therefore more suitable
for scan-based testing, than for the proposed approach
of encoding non-scan test sets. We do not present results
for these circuits, however, statistical encoding of
full-scan test sets for these circuits, on the lines of the
proposed approach, has recently been shown to be effective
in reducing the amount of memory required for
test storage [25].
We performed experiments on test sets for single-
stuck line (SSL) faults obtained from the Gentest
ATPG program, as well as the HITEC, GATEST, and
test sets from the University of Illinois
[26]. We measured the fault coverage of these test sets
using the PROOFS fault simulator [27] and ensured
that the coverage is comparable to the best-known fault
coverage for these circuits. We next present results on
the compression achieved using Huffman and Comma
coding for all four test sets. Table 5 compares the number
of bits required to store the encoded test set
that required to store the corresponding unencoded test
set TD. The number of bits required by our scheme is
moderate, substantially less than that required to store
unencoded test sets, and reduces significantly when the
same test set can be shared among multiple CUTs of
the same type included on a chip, as in core-based DSP
circuits [14]. The saving in SG memory presented in

Table

5 is substantial, and in most cases, the difference
in compression due to the use of Comma coding instead
of Huffman coding is very small. In Table 6, we
show that further compression is achieved by applying
run-length coding to TE. We present results on run-length
encoding for the s382 and s444 circuits using
the Gentest test set.
The test application time required is considerably
less than that required for pseudorandom testing, even
though the number of clock cycles C is greater than
the number of patterns in TD (C D lHjTDj for Huffman
coding and C D lCjTDj for Comma coding). Table 7
compares the number of test patterns applied, the number
of clock cycles required, and the fault coverage
obtained for our method, with the corresponding
figures reported recently for two pseudorandom testing
schemes [5, 6]. The test application time required by
our method is much less than for the pseudorandom
testing method of [5]. We also achieve higher fault
coverage for all circuits.
Iyengar, Chakrabarty and Murray

Table

5. Experimental results on test set compression for ISCAS 89 circuits with a high value of .
Average Percentage
codeword length compression
ISCAS
circuit nmjTDjTbits lH lC Hbits Cbits HE CE
Gentest
GATEST
n: No. of primary inputs; m: No. of unique test patterns; Tbits: Total no. of bits in TD; Hbits: No. of bits in after Huffman encoding;
Cbits: No. of bits in after comma encoding;
aComma coding is not applicable for the test set of s35932, because the probabilities of occurrence of the test patterns do not satisfy (2)
given in Theorem 4.

Table

6. Percentage compression achieved by run-length coding after applying Huffman and
Comma encoding to TD.
Number of bits in Percentage compression
ISCAS
circuit Tbits Hbits Cbits HRbits CRbits HE CE HRE CRE
HRbits: No. of bits in the encoded test set after Huffman and run-length encoding; CRbits: No.
of bits in the encoded test set after Comma and run-length encoding.
Deterministic Built-in Pattern Generation 111

Table

7. Number of clock cycles C required and fault coverage obtained using pseudorandom testing
compared with the corresponding figures using precomputed deterministic test sets.
Number of patterns jTDj Number of clock cycles C Fault coverage (%)
ISCAS
circuit [5]a [6]a Deta [5] [6] Det [5] [6] Detb
a[5, 6]: Recently proposed pseudorandom BIST methods; Det: Deterministic testing using precomputed
test sets.
bThe best fault coverage achieved by precomputed deterministic testing.
cResults for these circuits were not reported in [5, 6].

Table

8. Literal counts of the Huffman and Comma decoders for the four test sets.
Decoder cost in literals
Huffman decoders Comma decoders
ISCAS
circuit Gen HIT GAT STRAT Gen HIT GAT STRAT
28
43
s400 44 33 33 37 26 27 27 27
s526 43 47 28 27
Gen: Gentest; HIT: HITEC; GAT: GATEST; STRAT: STRATEGATE.
We next present experimental results on the Huffman
and Comma decoder implementations. We designed
and synthesized the FSM decoders using the Epoch
CAD tool from Cascade Design Automation [28]. The
low to moderate decoder costs in Table 8 show that
the decoding algorithm can be easily implemented as a
BIST scheme. Note that the largest benchmark circuit
s35932 requires an extremely small overhead (synthe-
sized ROM area is 0.53% of CUT area, and decoder
area is 6.18% of CUT area) to store the encoded test
set and decoder, thus demonstrating that the proposed
approach is scalable and it is feasible to incorporate the
encoded test set on-chip for larger circuits.
Note that, while Huffman and Comma encoding reduce
the number of bits to be stored, the serialization
of the ROM may increase the hardware requirements
for ROM address generation. In a conventional
fixed-length encoding scheme, the size of the counter
required for ROM address generation is dlog2 jTDje,
while an encoded ROM requires a dlog2.jTDjl/e-bit
counter for address generation, where l is the average
codeword length. However, since l is small, this
logarithmic increase in counter size is also small, e.g.,
the size of the counter does not change for s444, while
it increases from 7 to 10 for s35932. The hardware
overhead figures in Table 8 do not include this small
increase in counter size.
It may be argued that a special-purpose, minimal-
state FSM may be used to produce a precomputed
sequence. However, we have seen that the overhead
of such FSMs is prohibitive, especially for long test
sequences. In addition, such a special-purpose FSM
wouldbespecifictoasingleCUT;ontheotherhand, the
decoder DC for the proposed scheme is shared among
multiple CUTs, thereby reducing overall TGC overhead

Table

9 compares the overhead of the proposed deterministic
BIST scheme with the overhead of a pseudorandom
BIST method [6] for several circuits. The
overhead for the pseudorandom method was obtained
112 Iyengar, Chakrabarty and Murray

Table

9. Literal counts for the proposed technique compared with
pseudorandom testing.
Deterministic
TGC cost
Pseudorandom Number of
ISCAS 89 Decoder Total TGC cost test points
circuit cost cost [6] [6]
s526
by mapping the gate count figures from [6] to the literal
counts of standard cells in the Epoch library. While the
deterministic TGC requires greater area than the pseudorandom
TGCs, the difference is quite small, and thus
may be acceptable if higher fault coverage and shorter
test times are required. Note also that the pseudorandom
method requires the addition of a large number
of observability test points. These require a gate-level
model of the CUT, as well as additional primary outputs
and routing. Moreover, they may also increase the
size of the response monitor at the CUT outputs. The
proposed TGCs require no circuit modification, thus
making them more applicable to testing core-based designs
using precomputed test sequences.
Finally, we present experimental results for test set
compression and decoder overhead, using a single
decoder to test several CUTs on a chip. Table 10
shows that the levels of compression obtained for combined
test sets are comparable to those obtained for the
individual test sets. In fact, in several cases the overall
compression is higher than that obtained for one of the
individual test sets. The percentage area overhead required
for the decoder reduces significantly, because a
single decoder can now be shared among several CUTs.
Note that in the case of the Comma decoders, a major
part of the overhead is contributed by the binary coun-
ters. For example, in the Comma decoder for the pair
head, while the combinational logic represents only
overhead. If the counter is also used for normal
operation of the system, then the BIST overhead
will reduce further. The test application technique is
therefore clearly scalable with increasing circuit com-
plexity. The decoder overhead also tends to decrease
with an increase in . This clearly demonstrates that
the proposed test technique is well suited to circuits for
which  is high.
5. Conclusion
We have presented a novel technique for deterministic
built-in pattern generation for sequential circuits. This
approach is especially suited to sequential circuits that
have a large number of flip-flops and relatively few

Table

10. Percentage compression for test sets encoded jointly.
Percentage Huffman compression Percentage Comma compression
Circuit
Gen HIT GAT STRAT Gen HIT GAT STRAT

Table

11. Decoder cost in literals and percentage decoder overhead for a single decoder shared
among several CUTs.
Decoder cost in literals Percentage decoder overhead
Circuit
Gen HIT GAT STRAT Gen HIT GAT STRAT
fs382; s444g 48 52 44 44 6.72 7.29 6.18 6.21
28
Deterministic Built-in Pattern Generation 113
primary inputs, and for circuits such as embedded 9. M.S. Hsiao, E.M. Rudnick, and J.H. Patel, Alternating Strate-
cores, for which gate-level models are not available. We gies for Sequential Circuit ATPG, Proc. European Design and
have shown that statistical encoding of precomputed Test Conf., 1996, pp. 368-374.
10. T.M.NiermannandJ.H.Patel, HITEC:ATestGenerationPack-
test sequences leads to effective compression, thereby
age for Sequential Circuits, Proc. European Design Automation
allowingon-chipstorageofencodedtestsequences.We Conf., 1991, pp. 214-218.
have also shown that the average codeword length for 11. D.G. Saab, Y.G. Saab, and J.A. Abraham, Automatic Test
the non-optimal Comma code is nearly equal to the av- Vector Cultivation for Sequential VLSI Circuits Using Genetic
erage codeword length for the optimal Huffman code if Algorithms, IEEE Trans. on Computer Aided Design, Vol. 15,
pp. 1278-1285, Oct. 1996.
the test sequence satisfies certain proeprties. These are
12. K. Chakrabarty, B.T. Murray, J. Liu, and M. Zhu, Test
generally satisfied by test sequences for typical sequen- Compression for Built-in Self Testing, Proc. Int. Test Conf.,
tial circuits, therefore Comma coding is near-optimal 1997, pp. 328-337.
in practice. 13. F. Brglez, D. Bryan, and K. Kozminski, Combinational Profiles
Our results show that Huffman and Comma encod- of Sequential Benchmark Circuits, Proc. Int. Symp. on Circuits
and Systems, 1989, pp. 1929-1934.
ing of test sequences, followed by run-length encoding,
14. M.S.B. Romdhane, V.K. Madisetti, and J.W. Hines, Quick-
can greatly reduce the memory required for test stor- Turnaround ASIC Design in VHDL: Core-Based Behavioral
age. The small increase in testing time is offset by Synthesis, Kluwer Academic Publishers, Boston, MA, 1996.
the high degree of test set compression achieved. Fur- 15. J.P. Hayes, Computer Architecture and Organization, 3rd ed.,
thermore, testing time is considerably less than that for McGraw-Hill, New York, NY, 1998.
16. G. Held, Data Compression Techniques and Applications:
pseudorandom methods. We have developed efficient
HardwareandSoftwareConsiderations, JohnWiley, Chichester,
low-overhead pattern decoding methods for applying West Sussex, 1991.
the test patterns to the CUT. We have also shown that 17. M. Jakobssen, Huffman Coding in Bit-Vector Compression,
the overhead can be reduced further by using a sin- Information Processing Letters, Vol. 7, No. 6, pp. 304-307, Oct.
gle decoder to test multiple CUTs on the same chip. 1978.
18. T.M. Cover and J.A. Thomas, Elements of Information Theory,
The proposed technique thus offers a promising BIST
John Wiley, New York, NY, 1991.
methodology for complex non-scan and partial-scan 19. M. Mansuripur, Introduction to Information Theory, Prentice-
circuits for which precomputed test sets are readily Hall, Inc., Englewood Cliffs, NJ, 1987.
available. 20. V. Iyengar and K. Chakrabarty, An Efficient Finite-State
Machine Implementation of Huffman Decoders, Information
Processing Letters, Vol. 64, No. 6, pp. 271-275, Jan. 1998.
21. D.H. Greene and D.E. Knuth, Mathematics for the Analysis of


--R



and the M.

Reliable Computing Laboratory of the Department of Electrical and
Computer Engineering.

University of Illinois at Urbana-Champaign
are in computer-aided design of VLSI circuits and systems
verification and built-in self test
Krishnendu Chakrabarty received the B.
Indian Institute of Technology
and Ph.


Engineering at Duke University.
Professor of Electrical and Computer Engineering at Boston


projects are in embedded core testing

archival journals and referred conference
of IEEE and Sigma Xi
Activities in IEEE's Test Technology Technical Council (TTTC).
Murray received the A.
from Albion College in
in Electrical Engineering from Duke University in

of Michigan in
of the technical staff at General Motors Research and Development
where he led projects in testing
systems and computer architecture.
Adjunct Lecturer at the University of Michigan since
is currently Project Manager of Dependable Embedded Systems in



tools for system safety engineering.

He currently serves on the editorial board of the Journal
of Electronic Testing: Theory and Applications.
--TR

--CTR
A. Chandra , K. Chakrabarty, Efficient test data compression and decompression for system-on-a-chip using internal scan chains and Golomb coding, Proceedings of the conference on Design, automation and test in Europe, p.145-149, March 2001, Munich, Germany
Anshuman Chandra , Krishnendu Chakrabarty, Test Data Compression and Test Resource Partitioning for System-on-a-Chip Using Frequency-Directed Run-Length (FDR) Codes, IEEE Transactions on Computers, v.52 n.8, p.1076-1088, August
Anshuman Chandra , Krishnendu Chakrabarty, Test Resource Partitioning for SOCs, IEEE Design & Test, v.18 n.5, p.80-91, September 2001
Michael J. Knieser , Francis G. Wolff , Chris A. Papachristou , Daniel J. Weyer , David R. McIntyre, A Technique for High Ratio LZW Compression, Proceedings of the conference on Design, Automation and Test in Europe, p.10116, March 03-07,
Ismet Bayraktaroglu , Alex Orailoglu, Concurrent Application of Compaction and Compression for Test Time and Data Volume Reduction in Scan Designs, IEEE Transactions on Computers, v.52 n.11, p.1480-1489, November
A. Touba, Test data compression using dictionaries with selective entries and fixed-length indices, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.4, p.470-490, October
Anshuman Chandra , Krishnendu Chakrabarty, Analysis of Test Application Time for Test Data Compression Methods Based on Compression Codes, Journal of Electronic Testing: Theory and Applications, v.20 n.2, p.199-212, April 2004
sequential circuit testing;statistical encoding;run-length encoding;embedded-core testing;BIST;pattern decoding;huffman coding;comma coding