Test data compression

Test data compression consists of test vector compression on the input side
and response compaction on the output side. Test data compression involves
adding some additional on-chip hardware before and
after the scan chains. This additional hardware decompresses
the test stimulus coming from the tester; it also
compacts the response after the scan chains and before
it goes to the tester. This permits storing the test data in a
compressed form on the tester. With test data compression,
the tester still applies a precise deterministic
(ATPG-generated) test set to the circuit under test (CUT).
The advantage
of test data compression is that it generates the
complete set of patterns applied to the CUT with ATPG,
and this set of test patterns is optimizable with respect
to the desired fault coverage. Test data compression is
also easier to adopt in industry because it is compatible
with the conventional design rules and test generation
flows for scan testing.
Test data compression provides two benefits. First, it
reduces the amount of data stored on the tester, which
can extend the life of older testers that have limited
memory. Second—and this is the more important benefit,
which applies even for testers with plenty of memory—
it can reduce the test time for a given test data
bandwidth. Doing so typically involves having the
decompressor expand the data from n tester channels
to fill greater than n scan chains. Increasing the number
of scan chains shortens each scan chain, in turn reducing
the number of clock cycles needed to shift in each
test vector.
Test data compression must compress the test vectors
losslessly (that is, it must reproduce all the care bits
after decompression) to preserve fault coverage. The
output response, on the other hand, can use lossy compaction
(which does not reproduce all data, losing
information) with negligible impact on fault coverage.
Ideally, the output response could be compacted using
just a multiple-input signature register (MISR
The subject here is test vector compression techniques.
Test vectors are highly compressible because
typically only 1% to 5% of their bits are specified (care)
bits. The rest are don’t-cares, which can take on any
value with no impact on the fault coverage. A test cube
is a deterministic test vector in which the bits that ATPG
does not assign are left as don’t-cares (that is, the ATPG
does not randomly fill the don’t-cares).
In addition to containing a very high percentage of
don’t-cares, test cubes also tend to be highly correlated
because faults are structurally related in the circuit.
Both of these factors are exploitable to achieve high
amounts of compression.
The focus is on hardware-based test vector compression
techniques for scan architectures;
Test vector compression schemes fall broadly into
three categories:
■ Code-based schemes use data compression codes to
encode test cubes.
■ Linear-decompression-based schemes decompress
the data using only linear operations (that is LFSRs
and XOR networks).
■ Broadcast-scan-based schemes rely on broadcasting
the same values to multiple scan chains.

Linear-decompressor-based schemes:

A second category of compression techniques is

based on using a linear decompressor. Any decompressor
that consists of only wires, XOR gates, and flipflops
is a linear decompressor and has the property that
its output space (the space of all possible vectors that it
can generate) is a linear subspace spanned by a
Boolean matrix. A linear decompressor can generate
test vector Y if and only if there exists a solution to the
system of linear equations AX = Y, where A is the characteristic
matrix for the linear decompressor and X is a
set of free variables shifted in from the tester (you can
think of every bit on the tester as a free variable assigned
as either 0 or 1). The characteristic matrix for a linear
decompressor is obtainable from symbolic simulation
of the linear decompressor; in this simulation a symbol
represents each free variable from the tester. Encoding a test cube using a
linear decompressor
requires solving a system of linear equations consisting
of one equation for each specified bit, to find the freevariable
assignments needed to generate the test cube.
If no solution exists, then the test cube is unencodable
(that is, it does not exist in the output space of the linear
decompressor). In this method, it is difficult to
encode a test cube that has more specified bits than the
number of free variables available to encode it.
However, for linear decompressors that have diverse linear
equations (such as an LFSR with a primitive polynomial),
if the number of free-variables is sufficiently
larger then the number of specified bits, the probability
of not being able to encode the test cube becomes negligibly
small. For an LFSR with a primitive polynomial,
research showed that if the number of free variables is
20 more than the number of specified bits, then the
probability of not finding a solution is less than 10−6.

Combinational linear decompressors:

Researchers described the use of a combinational

linear decompressor in which an XOR of some of the
tester channels drives each scan chain. This
approach uses simpler hardware and control logic than
approaches based on sequential linear decompressors.
The drawback is that combinational linear decompressors
must encode each scan slice using only the free
variables shifted in from the tester in a single clock
cycle, which is equal to the number of tester channels.
The worst-case, most highly specified scan slices tend
to limit the amount of achievable compression because
the number of tester channels must be sufficiently large
to encode the most highly specified scan slices.
Static reseeding:

The earliest work in this area was

based on static LFSR reseeding, a technique that computes
a seed (an initial state) for each test cube. This
seed, when loaded into an LFSR and run in
autonomous mode, will produce the test cube in the
scan chains. This technique achieves compression by
storing only the seeds instead of the full test cubes.
One drawback of using static reseeding for compressing
test vectors on a tester is that the tester is idle
while the LFSR is running in autonomous mode. One
way around this is to use a shadow register for the LFSR
to hold the data coming from the tester while the LFSR
is running in autonomous mode.
Another drawback of static reseeding is that the
LFSR must be at least as large as the number of specified
bits in the test cube. One way around this is to only
decompress a scan window (a limited number of scanslices)
per seed.

SEED CALCULATION:

LFSR Seed Calculation

Figure 1(a) shows an example of an LFSR configured to
deliver patterns to test a circuit. The seed line is used to
transmit the seed which will be expanded to produce the test
pattern. The purpose of the seed register is to allow a new
seed (for the next pattern for instance) to be loaded while the
LFSR operates, expanding the current seed. The loading of
the seed from the seed register into the LFSR is controlled by
the reseed indicator. The central part of the figure shows a
typical LFSR implementation with the feedback provided by
an XOR gate. The phase shifter shown is used to introduce
offests between adjacent channels of the output. Finally the
scan chains (the output of the decompressor) are the channels
through which the data is delivered to the internal part of the
circuit.
In order to map a test pattern onto a seed to produce a sequence
which will satisfy the test pattern, the LFSR must be modeled. Figure 2
shows the process of mapping a partially
specified test pattern to an LFSR by modeling through matrices
and vectors in Galois Field (using modulo-2 arithmetic).
Each next state of the LFSR can be represented as
a matrix multiplication of the current state of the LFSR (as a
vector) and the LFSR matrix. It follows that the LFSR state after
t clock pulses will be the LFSR matrix raised to the power
t, multiplied by the seed vector. The phase shifter also has a
matrix representation, and combining with the LFSR matrix
gives a description of any frame (time slice) of the pattern (P
in the figure) in terms of the seed vector (s in the figure). Setting
P vector positions to specified bits of the test pattern (in
the way shown in the figure) a system of equations in terms of
the seed vector variables. Simple Gaussian elimination can be
used to obtain the seed vector and thus accomplish the compression.

LFSR FEEDBACK:

Fig 1(a) Linear Decompressor

 Fig 1(b) Linear Decompressor with programmable channel separation

SEED REGISTER
A linear feedback shift register (LFSR) is a shift register whose input bit is a
linear function of its previous state.
The only linear functions of single bits are xor and inverse-xor; thus it is a shift
register whose input bit is driven by the exclusive-or (xor) of some bits of the
overall shift register value.
The initial value of the LFSR is called the seed, and because the operation of
the register is deterministic, the sequence of values produced by the register
is completely determined by its current (or previous) state. Likewise, because
the register has a finite number of possible states, it must eventually enter a
repeating cycle. However, an LFSR with a well-chosen feedback function can
produce a sequence of bits which appears random and which has a very long
cycle.
Applications of LFSRs include generating pseudo-random numbers, pseudo-
noise sequences, fast digital counters, and whitening sequences. Both
hardware and software implementations of LFSRs are common
An LFSR is a shift register that, when clocked, advances the signal through the register from one bit to the
next most-significant
bit (see Figure 1). Some of the outputs are combined in exclusive-OR configuration to form a feedback
mechanism. A linear
feedback shift register can be formed by performing exclusive-OR on the outputs of two or more of the
flip-flops together and
feeding those outputs back into the input of one of the flip-flops as shown in Figure 2.

Figure 1. A 3-Bit Shift Register

Figure 2. Linear Feedback Shift Register
Pseudorandom Pattern Generation
Linear feedback shift registers make extremely good pseudorandom pattern generators. When the outputs
of the flip-flops are
loaded with a seed value (anything except all 0s, which would cause the LFSR to produce all 0 patterns)
and when the LFSR
is clocked, it will generate a pseudorandom pattern of 1s and 0s. Note that the only signal necessary to
generate the test patterns
is the clock.

A LFSR (linear feedback shift register) is a shift register where the input is a linear
function of two or more bits (taps). There are many possible configurations, the one
presented here is very simple and has the property that it will start from an input of all 0's
and is very easy to implement in software and hardware.

A LFSR of this type will never contain only 1's and would stall if loaded with that value.
Only some taps will generate a maximal sequence with a period of 2^n-1 cycles.

If you need a counter and it does not have to count in a linear way then a LFSR is faster
and requires less hardware resources.

Some possible uses:

Pseudo random number generator
Head and tail pointers in a FIFO
Program counter in a simple CPU
Galois Field Mathematics and M-Sequences
Finite (Galois) field mathematics are used to derive m-sequence feedback taps. Any LFSR can be
represented as a polynomial of variable X, referred to as the generator polynomial:

Equation 1. Generalized generator polynomial.

The coefficients gi represent the tap weights, as defined in Figures 1 and 2, and are 1 for taps
that are connected (fed back), and 0 otherwise. The order of the polynomial, m, represents the
number of LFSR stages. Rules of linear algebra apply to the polynomial, but all mathematical
operations are performed in modulo-2:

Modulo-2 addition:

0+0=0
0+1=1
1+1=0

Modulo-2 multiplication:

0*0=0
0*1=0
1*1=1

As an example of polynomial representation, the generator polynomial

G(X) = X3 + X1 + 1

represents an LFSR with feedback taps 3 and 1, denoted as [3, 1]g:

The constant 1 in the generator polynomial represents the input connection of the shift register,
g0.
Now, here is the key to determining m-sequence feedback taps: The generator polynomial of
Equation 1 is said to be primitive if it cannot be factored (i.e. it is prime), and if it is a factor of (i.e.
can evenly divide) XN+1, where N = 2m-1 (the length of the m-sequence). It can be shown that an
LFSR represented by a primitive polynomial will produce a maximal length sequence.

Consider again the example of the [3, 1]g LFSR just given. We wish to know if this generator will
produce an m-sequence. First we note that m = 3 and N=23-1=7. It can be shown that its
polynomial, X3+X1+1 , cannot be factored, and it can be shown that its polynomial is a factor of
X7+1. Thus, we conclude that this LFSR will indeed produce a maximal length sequence.

In this example, we went through the process of determining whether or not the given set of
feedback taps would result in a maximal length sequence. Normally, however, we are required to
do just the opposite. That is, we are normally asked to find all sets of feedback taps that will
produce m-sequences for a given register size.

For example, we may be asked to find all sets of maximal-length feedback taps for an LFSR with
m=3 registers. We do this as follows: The length of the m-sequences will be N=23-1=7. We know
that the solution lies in all the primitive factors of polynomial X7+1. We use modulo-2 linear
algebra (perhaps with the aid of a computer algorithm) to find the prime factors to be

The primitive polynomials are those factors whose order is the same as the register size, m = 3.
Of the three prime factors, the last two meet this criterion. Thus we see that there are exactly two
sets of m-sequence feedback taps, [3, 1]g and [3, 2]g.

It is interesting to note that, given any shift register size, there will always be an even number of
m-sequence feedback sets. More specifically, given any one of its m-sequence feedback sets,

[f1, f2, f3, ..., fJ] g

there will be a companion set described as

[f1, m-f2, m-f3, ..., m-fJ] g

whose sequence will be the mirror image of the original set's sequence. Note that subtracting
feedback tap numbers from m for the companion set is equivalent to reversing the order of those
taps. Thus we conclude that, for any given feedback set that produces an m-sequence, the mirror
image of the feedback set will produce the mirror image of the m-sequence. And, of course, the
resulting sequence will also be an m-sequence since all possible states are exhausted. An astute
reader may have noticed in the last example that the two derived sets of m-sequence feedback
taps, [3, 1]g and [3, 2]g, are in fact mirror images of each other.

Tables of m-sequence feedback taps are presented below for the reader's convenience.
SHIFT REGISTER

One of the two main parts of an LFSR is the shift register (the other being the feedback
function). A shift register is a device whose identifying function is to shift its contents
into adjacent positions within the register or, in the case of the position on the end, out of
the register. The position on the other end is left empty unless some new content is shifted
into the register.

The contents of a shift register are usually thought of as being binary, that is, ones and
zeroes. If a shift register contains the bit pattern 1101, a shift (to the right in this case)
would result in the contents being 0110; another shift yields 0011. After two more shifts,
things tend to get boring since the shift register will never contain anything other than
zeroes.

Two uses for a shift register are 1) convert between parallel and serial data and 2) delay a
serial bit stream. The conversion function can go either way -- fill the shift register
positions all at once (parallel) and then shift them out (serial) or shift the contents into the
register bit by bit (serial) and then read the contents after the register is full (parallel). The
delay function simply shifts the bits from one end of the shift register to the other,
providing a delay equal to the length of the shift register.

Figure 2) Shift Register

Some nomenclature:

Clocking) One of the inputs to a shift register is the clock; a shift occurs in the register
when this clock input changes state from one to zero (or from zero to one, depending on
the implementation). From this, the term "clocking" has arisen to mean activating a shift
of the register. Sometimes the register is said to be "strobed" to cause the shift.

Shift direction) A shift register can shift its contents in either direction depending on how
the device is designed. (Some registers have extra inputs that dictate the direction of the
shift.) For the purposes of this discussion, the shift direction will always be from left to
right.

Output) During a shift, the bit on the far right end of the shift register is moved out of the
register. This end bit position is often referred to as the output bit. To confuse matters a
bit, the bits that are shifted out of the register are also often referred to as output bits. To
really muddy the waters, every bit in the shift register is considered to be output during a
serial to parallel conversion. Happily, the context in which the term "output" is used
generally clears things up.

Input) After a shift, the bit on the left end of the shift register is left empty unless a new
bit (one not contained in the original contents) is put into it. This bit is sometimes
referred to as the input bit. As with the output bit, there are several different references to
input that are clarified by context.

FEEDBACK FUNCTION

In an LFSR, the bits contained in selected positions in the shift register are combined in
some sort of function and the result is fed back into the register's input bit. By definition,
the selected bit values are collected before the register is clocked and the result of the
feedback function is inserted into the shift register during the shift, filling the position
that is emptied as a result of the shift.

The feedback function in an LFSR has several names: XOR, odd parity, sum modulo 2.
Whatever the name, the function is simple: 1) Add the selected bit values, 2) If the sum is
odd, the output of the function is one; otherwise the output is zero. Table 1 shows the
output for a 3 input XOR function.

Table 1) XOR Function

Input A Input B Input C XOR Output
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
 1 1 0 0
1 1 1 1

The bit positions selected for use in the feedback function are called "taps". The list of the
taps is known as the "tap sequence". By convention, the output bit of an LFSR that is n
bits long is the nth bit; the input bit of an LFSR is bit 1.

TAP SEQUENCES

An LFSR is one of a class of devices known as state machines. The contents of the
register, the bits tapped for the feedback function, and the output of the feedback function
together describe the state of the LFSR. With each shift, the LFSR moves to a new state.
(There is one exception to this -- when the contents of the register are all zeroes, the
LFSR will never change state.) For any given state, there can be only one succeeding
state. The reverse is also true: any given state can have only one preceding state. For the
rest of this discussion, only the contents of the register will be used to describe the state
of the LFSR.

A state space of an LFSR is the list of all the states the LFSR can be in for a particular tap
sequence and a particular starting value. Any tap sequence will yield at least two state
spaces for an LFSR. (One of these spaces will be the one that contains only one state --
the all zero one.) Tap sequences that yield only two state spaces are referred to as
maximal length tap sequences.

The state of an LFSR that is n bits long can be any one of 2^n different values. The
largest state space possible for such an LFSR will be 2^n - 1 (all possible values minus
the zero state). Because each state can have only once succeeding state, an LFSR with a
maximal length tap sequence will pass through every non-zero state once and only once
before repeating a state.

One corollary to this behavior is the output bit stream. The period of an LFSR is defined
as the length of the stream before it repeats. The period, like the state space, is tied to the
tap sequence and the starting value. As a matter of fact, the period is equal to the size of
the state space. The longest period possible corresponds to the largest possible state
space, which is produced by a maximal length tap sequence. (Hence "maximal length")

Table 2 is a listing of the internal states and the output bit stream of a 4-bit LFSR with tap
sequence [4, 1]. (This is the LFSR shown in Figure 1.)

Table 2) 4-Bit LFSR [4, 1] States and Output

Register States
Output
Bit 1 (Tap) Bit 2 Bit 3 Bit 4 (Tap)
Stream
1 1 0 1
0 1 1 0 1
0 0 1 1 0
1 0 0 1 1
0 1 0 0 1
0 0 1 0 0
0 0 0 1 0
1 0 0 0 1
1 1 0 0 0
1 1 1 0 0
1 1 1 1 0
0 1 1 1 1
1 0 1 1 1
0 1 0 1 1
1 0 1 0 1
1 1 0 1 0

Figure 1) 4-Bit LFSR, Tap Sequence; [4,1]