Problem A1: Test Pattern Generation by Using Reseedable LFSRs
Abstract
Built-In-Selft-Test (BIST) is one of most popular test solutions to test the embedded cores in a chip. The BIST circuit can generate pseudo random test patterns to test these embedded cores without using expensive Automatic Test Equipments (A TEs). On the other way, if you have test vectors which are generated by the test generator, you can design a pseudo random pattern generator suitable for hitting these test vectors in short time. In this subject, try to write a program to create the pseudo random pattern generator, performed by Linear Feedback Shift Registers (LFSRs), for hitting the generated test vectors. The output of LFSRs can be rearranged before feeding to the input of Core Under Test (CUT). The lengths of LFSRs and the numbers of LFSRs are no limit. In the vectors generation procedure, the seeds of LFSRs can be changed for the purpose of saving BIST time.
1.Introduction:
Linear Feedback Shift Registers (LFSRs) are widely adopted as the pseudo-random test pattern generators for built-in self test (BIST) of logic circuits shown in Figure1, due to its low hardware overhead. However, there are many faults in the circuits under test (CUTs) that are hardly detected b
y the test patterns generated by using the traditional LFSRs, certain deterministic patterns are needed for achieved higher fault coverage. These extra patterns can be stored in the memory of an external tester or the on-chip memory.
In order to reduce the time of LFSR to generate patterns for testing such hard to detect fault, storage requirements, one of the solutions is to change seeds of the LFSRs during test pattern generation. A seed refers to the initial state of an LFSR. The procedure for changing the seed of the LFSR is called reseeding. Since the seeds still need to be stored in the memory, it needs a good reseeding strategy to reduce a large test data volume into a smaller set of seeds.
Test Result
Figure 1: BIST Architecture
The structure of an LFSR is composed of D-FFs and exclusive-OR gates. It can be expressed by a polynomial of X. Figure 2 shows the division type LFSR with polynomial X 4 + X 3 + 1:核桃剥壳机
1
1 0 0 1 Coefficient Exponent 0 (Seed)
推杆炉
O 4 O 3 O 2 O 1
Figure 2: The division type LFSR with polynomial X 4 + X 3 + 1
It is easy to figure out that the radix-N polynomial requires N D-FFs. The coefficient of each expone
nt denotes the insertion points of exclusive-OR gates in the shifting path. When the LFSR starts or restarts for a new seed, the LFSR is reset to zero first. Then the seed value is applied sequentially from I 0, see Figure 2. As the LFSR is operating in test pattern generation mode, the I 0 is set to 0. Therefore, there are two penalties for reseeding, one is the memory occupied by the seeds, and another is the clock cycles to reset and shift the seeds into the LFSR. 2. LFSR Design Issue and Partition
It is not practical to implement a big LFSR to test a circuit with large number of inputs. It is because such implementation often results in lower F.C. and longer BIST time. A good partition of LFSR will improve F.C. and BIST time. Figure 3 shows a CUT with k-bit inputs (I k , I k-1, …, I 1). The LFSR is partitioned into m smaller LFSRs (LFSR m , LFSR m-1, …, LFSR 1). Each LFSR is with a size of L m , L m-1, …, L 1, respectively , and hence the total size of the LFSRs is L m +L m-1+…+ L 1 = k. Since the LFSRs nees s seeds to generate the test vectors for the CUT, it needs an (s *k)-bit
memory to store the seeds.
Figure 3: LFSR partition
Assume that there are n test vectors (V1, V2, …, V n) in the test set. If you cannot find any correlation (equivalent or inversion, i.e., I i= I j or I i=I j’) between inputs of test patterns, the optimal size of LFSR is k. However, the correlations between inputs are possible in the test set. Hence, there are two cost considerations in test application:
2.1The hardware cost:
Figure 4: Example of a test set
Y ou can use both of the bit broadcast and bit inversion techniques to reduce the required length of LFSRs if the correlations, I i=I j or I i=I j’, exist between inputs of test pattern. The total length of LFSRs, L1+L2+…+ L m = L total, will smaller than k. In the Figure 4, the input length k is 10. The
对照物
test set is composed of 13 test vectors (V1, V2, …, V13) . The minus sign denotes “don’t care”. The
patterns are listed in descending order from I10 to I1. In the test set, the I8 and I5 in every test vector are equivalent or compatible. The I7and I3in every test vector are inversion or compatible. The two bits are called equivalent, inversion or compatible are list in Table 1. Y ou can combine I8 and I5 into a single bit and combine I7 and I3with adding an inverter to save 2 D-FFs of LFSRs.
无数字签名
2.2The test time cost
In some cases, if we use all bits of LFSRs to be test inputs, it will expense more test time for the purpose of high Pattern Coverage Rate (= Hit Patterns / Total Test Patterns). One of the solutions is to appropriately increase the size of LFSRs and use some of them to be test inputs. In such condition, L total will larger than k.
3.Subject of this problem:
Please write a program which can generate appropriate structures of LFSRs and a set of seeds for the applied test set. The program must consider four factors: (1) the hardware test cost, (2) pattern coverage rate, (3) the total data volume of seeds, and (4) BIST time. The seeds of every LFSRs can be changed values during the test. The input file to the program is the description of the test set. Its format will be described in detail in the Input Format section. Y ou must generate a output file to describe the structures of LFSRs, the cycles for applying seeds, the ending cycle, and pattern coverage. The required formats are listed in the Output Format section.
The command line format for this program is
猎
结构<exe_filename> <vector_file>.vec
Where the <exe_filename> is the execution file of this program after compiling, and the <vector_file>.vec is the input filename with (.vec) file extension. The program must write an output file after execution. The output filename format is
Where (.out) is the file extension of the output file.
4.Input Format
The input file contains three keywords: INPUT_NO, VECTOR_NO, and VECTORS, which represent the number of input, the number of test vector, and the test vectors, respectively. In figure
4, the number of input is 10 and the number of test vector is 13. The input file is written as follows:
INPUT_NO10
VECTOR_NO13
VECTORS // I10 I9 I8 I7 I6 I5 I4 I3 I2 I1
1-01101000 // V1
000-101111 // V2
….
1001100011 // V13
5.Output Format
The output structure file contains 8 keywords: TOTAL_SIZE, LFSR_NO, POLY, INPUT_SEQ, SEED, CYCLE, END, and COVERAGE which represent: total size of LFSR, the number of LFSR, polynomials of LFSRs, seeds of LFSRs, input order, the number of clock cycles for reseeding, end of the pattern generation procedure, and the pattern coverage in percentage, respectively. Note that POLY and SEED represent all LFSRs’ polynomial and seed from LFSR m to LFSR n, respectively. The polynomial is expressed in a list of exponents whose coefficient is 1. For example, three LFSRs (LFSR3, LFSR2 and LFSR1) are used in the design. The polynomials of LFSR3, LFSR2and LFSR1are X4+ X3+ 1, X3+ X2+ 1 and X3+ X + 1, respectively. The corresponding arguments of POLY are 4 3 0, 3 2 0, and 3 1 0. All numbers in POLY are separated by blank or tab. The numbers are listed in a descending order for each LFSR’s polynomial.
The seed is represented in the binary format. For example, if the initial (or reseeding) state of X4 + X3+ 1 is {0 0 1 0} in your design, its corresponding representation is 0010. Y ou can insert space, tab, or underlines between binary digits for readability.
The LFSRs’ output IDs, which are not listed in the output file but used for INPUT_SEQ, are set from TOTAL_SIZE to 1 by default. The INPUT_SEQ specifies the connection from LFSRs’outputs to CUT’s inputs. For example, a 3-LFSR structure with X4 + X3+ 1, X3 + X2+ 1 and X3 + X+ 1 forms a
10-bit test pattern generator. Eight of them are used as inputs of CUT. The output structure file is shown as follows, and the connection between LFSRs and CUT is shown in figure 5.
At the 0th clock cycle, the LFSR is reset. At the 1st clock cycles, the 1st seed will be shifted into the LFSR from I0 to all DFFs in the LFSRs, which initializes the pattern generation sequence. This initialization step takes k clock cycles for shifting a seed into the LFSRs, if the LFSR size is equal to k. When the LFSRs need a new seed, it needs to take one extra clock cycle to reset the LFSRs before it takes another k clock cycles for shifting the new seed. So the total time penalty for s seeds is:
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议