A Novel Compression Techniques for Test Responses
Cao Lei, Microelectronics Department of Xi’anJiaoTongUniversity, Xi’an, Shaanxi, 710049
E-mail:
Abstract—Built-In Self-Test (BIST) requires a significant amount of memory for saving the correct responses. This will increase the hardware overhead as well as the test time. This paperintroduces a novel lossy compression method, named half-compression or "4-2" compression techniqueto solve this problem. This paperfirst studies the grouping information of 4-bit binary, then finds the effective signatures for compression. Further, compression ratio and aliasing probability is analyzed. Based on above, the compression technique and circuit design method are developed. Finally, experiments on ISCAS 85 Benchmark are carried out to analyze the compression ratio and the performance of the designed compression circuit. Experimental data show that the proposed method shows the feature of high compression ratio, short compression time and low overhead.
Index Terms— Half-compression Fault coverage Hardware overhead
1 Introduction
With the increasing complexity and intensity of VLSI, test data volume and test time are increasing [1], and resulting in test cost increasing steadily. In addition, there are limits to the numbers of I/O, the operating speed and the throughput of the ATE[2]. Hence, it is becomingincreasingly difficult to do high coverage testing only using external test equipment. With built-in pattern sources and response analyzers, BISToffers a number of advantages compared withexternal testing[3]. However, BIST requires a significant amount of memory for saving the correct responses, for example, memory BIST will occupy 30% -40% of the memory size. So test data reducingtechniques becomes a research hot. Compression technique may be an attractive solution, such approaches like statistical coding, run-length coding, and Golomb coding [4], [5], [6], [7], [8], [9] are comprehensively studied. These compression methods can achieve high compression ratio, but require more complicated compression circuit.
The goal of this paper is to propose a new and high efficient test compression technique for test responses, called half-compression or "4-2" compression technique. To demonstrate the good feature of the proposed method, theory analysis and experiments are carried out, and related results are explained in detail. Final analytical results show that the proposed circuit has a simple structure, high compression ratio, small hardware overhead and low aliasing probability. All these can meet the requirements of major circuits.
2 Principle of "4-2" Compression
The 4-bit binary haspossibility of =16 compositions, which can be divided into twogroups. The first group is{0001,0100, 0111, 0010, 1110, 1011, 1000, 1101}, and the second is {0011, 0110, 1111, 1010, 1100, 1001, 0000, 0101}.The parity of first group is odd , we mark them with “1”, and the parity of second group iseven, we mark them with“0”. Take “0001” for example, the result is 0⊕0⊕0⊕1=1. As a result, we can use one binary "0" or "1" to mark the first group or the second group.
We can also divide {0001, 0100, 0111, 0010, 1110,1011, 1000, 1101} into {0001, 0111, 1011, 1101} and {0100, 0010, 1110, 1000}. The last bit of the data in the first group is “1”, and the last bit of the data in the second group is “0”. So we can also use one binary “0” or “1” to mark the first group or the second group. We can divide {0011, 0110, 1111, 1010, 1100, 1001, 0000,0101} with the same method. We can use 2 binary to mark 4 binary, so it is called "4-2" compression.
So anyone of the 16 figures in this group can be marked with two binary, as shown in Fig.1. Take “0101” for example, the parity of it is even, so we mark the first bit with “0”. Because the last bit of “0101”is “1”, we mark the secondbit with “1”, the final result is “01”. The same for “0100”, its compression result is “10”. Its logical graphics of structure is shown in Fig.2, a, b, c, d are the initial four binary, e and f are the second bit and the first bit after compression.
Fig.1. marking the 16 different figures
Fig.2. Logical graphics of structure of “4-2” compression circuit
3 Half-compression and Related Theoretical Analysis
Half-compression is the expansion on the basis of “4-2” compression.We make four bits a group.For example, the C1355has 32 responses which require eight basic “4-2” compression circuit units.The results of compression are16 responses. From 32-bit to 16-bit, it is compressed by a half, so-called Half-compression.
This method is for the circuit whose response is a multiple of 4, but how about the circuit withthe response which is not a multiple of 4. The approach taken here is observing the response of the circuit firstly, if there is one more bit we will and“000”, two more we will and“01”, three more we will and either “1” or “0”. Because of this circuit can reduce the compression rate of aliasing, higher precision, the whole compression circuit structure reunification can be achieved with simple. Because we can make the circuit have lower aliasing probability, higher precision, and make all the compression circuit the same and simple.
3.1 Compression Ratio
The effect of compression coding can be measured by compression multiple or compression ratio.
Compression MultipleCM= the initial test data / test data after compression
Compression ratio CR = (the initial test data - the test data after compression) /the initial test data
The relationship of compression multiple and compression ratio is CR＝1-1/CM. Compression multiple is positive to compression ratio, the better the effect of compression the higher compression multiple, the greater compression ratio. Conversely, the smaller the compression multiple will be, the smaller compression ratio will be.
The structure of Half-compression circuit is simple. So if the test data is a multiple of 4, the entire compression ratio is 1 / 2, but if not, the corresponding compression ratio will decrease.Take the c432 for example, the compressed responses has 4-bit while the theoretical output has the 7-bit, so compression ratio is 4 / 7 that is bigger than 1 / 2. But when the output is considerable, even if the output is not a multiple of 4, the compression ratio will near the theoretical value, such as the circuit c5315, theoretical output has 123-bit, but there is 62-bit after compressed, the compression ratio is62/123 = 0.504.The compression ratios of ISCAS 85 Benchmark are shown in Table 1.
Table.1. Compression Ratios of ISCAS 85 Benchmark
CUT / Bits before compression / Bits after compression / compression ratioC432 / 7 / 4 / 0.429
C499 / 32 / 16 / 0.500
C880 / 26 / 14 / 0.459
C1355 / 32 / 16 / 0.500
C1908 / 25 / 14 / 0.435
C2670 / 140 / 70 / 0.500
C3450 / 22 / 12 / 0.455
C5315 / 123 / 62 / 0.495
C6288 / 32 / 16 / 0.500
C7552 / 108 / 54 / 0.500
3.2 Analysis of Aliasing Probability
Aliasing is that compressed results of compressed response with wrong data and the compressed response with correct data are entirely the same.As a result, the wrong response will be misconstrued as the correct one. Because of aliasing, testers willmistakenly the chip with faults as a correct one. In testing aliasingof the circuit should be as fewer as better. The aliasing probabilityin traditional compression methods is as follow.
In Ones-Count Compression, consider a circuit tested with L random input vectors and m that is the number of 1s appearing in the input. The number of L-bit sequences having m 1s is. Thus such sequences are aliases. The aliasing probability sequences to all possible erroneous sequences is P (m )= .
In transition-count testing, the signature is the number of 0-to-1and 1-to-0 transitions in the output stream. Let test length of sequence is L that has(L-1 )boundaries between bits where a transition can occur. The transition count associated with sequence is r. There are ways a transition can occur. Since the sequence obtained by complementing every bit of L has the same transition count as L, there are 2 possible sequences that have transition count r, only one of which is the response of the fault-free circuit. Thus there are 2-1possible error sequences that lead to aliasing. If all faulty sequences are equally likely to occur as the response of a faulty circuit, then the probability of aliasing is .
In “4-2” compression, the possibleof marking is4-1 = 3, and thealiasing probabilityis.The responses of Half-compression are composed by n “4-2” compressioncircuits. The aliasing probability of each module is the same.So the aliasing probabilityis.The aliasing probability is shown in figure 3;we can see the aliasing probability will decrease as the number of units increase.
Fig.3. Aliasing probability
4. Experiment
Now here we will use the results of ISCAS85 benchmark to research this compression circuit. In the experiment we use TMSC 0.18 andISCAS85 Benchmark Verilog of North Carolina State University, and use analysis tools Design Analyzer, ATPG tools Tetramax of V-Synopsys 2003.12. The result shows in Table 2 is under the Sun Blade workstations for tests.And SF is stuck-atFault, TF is transition fault.
ISCAS 85 benchmark circuit contains c432, c499, c880, c1355, c1908, c2670, c3540, c5315, c6288, c7552 which need 2, 8, 7, 8, 7, 35, 6, 31, 8, 27 “4-2” compression circuit units respectively. Here take c1355forexample, the ideal response is 32 bits which needs eight “4-2” compression units.And the compressed response is 16 output bits. This is the original benchmark test circuit on the basis directly to the "4-2" compression circuit increases in the base circuit compression.
It can be seen from Table 2 that the length of response compressed is half of the response before compression. But the fault coverage of the circuit after the compression is just a slight decline compared to the circuit before compression. The will not affect the overall performance of the circuit. In theory, if we increase the length of the compression test twice as before when the testing response capacity is in the same size, the fault coverage of compressed circuit will be greater than the circuit before compression. So the performance of the compression circuit can meet expected objectives. From the table, we can see the effect of compression using the Half-compression. At the same time “4-1” compression can be used fully efficiency compared to the size of the relatively large circuit. This will further reduce hardware overhead and become useful to reduce test responses.
Table.2 Fault Coverage Before and After Compress
Before Compress / After CompressBits OfSeeds / Test Length / SF (% ) / TF (% ) / SF (% ) / TF (% )
C432 / 36 / 2593 / 99.05 / 89.01 / 97.46 / 86.81
C499 / 41 / 2100 / 99.93 / 93.71 / 97.28 / 87.22
C880 / 60 / 7200 / 96.37 / 81.45 / 95.56 / 78.98
C1355 / 41 / 2252 / 98.00 / 86.16 / 94.76 / 79.72
C1908 / 33 / 6600 / 99.67 / 95.18 / 99.00 / 92.18
C2670 / 233 / 108578 / 92.15 / 86.31 / 89.99 / 88.45
C3450 / 50 / 100000 / 97.12 / 87.61 / 97.10 / 87.58
C5315 / 178 / 108578 / 99.47 / 93.84 / 97.76 / 91.32
C6288 / 32 / 2048 / 99.93 / 98.54 / 99.90 / 98.15
C7552 / 207 / 85698 / 97.34 / 91.34 / 96.81 / 88.90
5 Performance of Half-compression
As the pseudorandom test vectors, linear feedback shift register (LFSR) test vector generator is the most common method. These test vectors hasthe nature all the random numbers needed, and they are generated through testing ha1rdware vector generator, so it can be repeated, this is necessary for BIST. It need not cover all the inputs, but in order to get adequate fault coverage, long sequence of test vector generation is necessary. The pseudorandom test vectors more needed for test is more than ATPG test vector, but less than exhaustive testing code. Because LFSR has so many advantages, we willcompare Half-compression with LFSR to findthe performance of Half-compression circuit.
5.1 Fault Coverage
Lossy compression will lost part of the information, as a result the wrong response would be mistaken to bethe correctone. For example, the ideal response of the circuit before compression is "0010", and the final output is “10” when the response through the compression unit.But if there are faults in the circuit andthe actual response is “1110”. Then the output results after compression is still “10”. The circuit with faultscan not be tested. But if the response of the circuit with faults is “1010”, then the compression results for the output is “00”, this fault can be detected. The fault coverageof lossy compression will decrease, but this will not affect the overall performance of the circuit.
Table 3 shows the fault coverage of Half-compression and LFSR. Half-compression and LFSR achieve the same fault coverage but LFSR required test vectors less than Half-compression.
Table 3 Fault Coverage of Different Methods
CUT / Before Compression / After Compression / LFSR**Bits Of
Seeds / Test Length / SF (% ) / TF (% ) / SF (% ) / TF (% ) / Test Length / SF (% )
C432 / 36 / 2593 / 99.05 / 89.01 / 97.46 / 86.81 / 267 / 98.84
C499 / 41 / 2100 / 99.93 / 93.71 / 97.28 / 87.22 / 533 / 99.20
C880 / 60 / 7200 / 96.37 / 81.45 / 95.56 / 78.98 / 8445 / 100
C1355 / 41 / 2252 / 98.00 / 86.16 / 94.76 / 79.72 / 1408 / 99.71
C1908 / 33 / 6600 / 99.67 / 95.18 / 99.00 / 92.18 / 6250 / 99.69
C2670 / 233 / 108578 / 92.15 / 86.31 / 89.99 / 88.45 / 950930 / 95.92
C3450 / 50 / 100000 / 97.12 / 87.61 / 97.10 / 87.58 / 17019 / 96.41
C5315 / 178 / 108578 / 99.47 / 93.84 / 97.76 / 91.32 / 1795 / 99.50
C6288 / 32 / 2048 / 99.93 / 98.54 / 99.90 / 98.15 / 80 / 99.50
C7552 / 207 / 85698 / 97.34 / 91.34 / 96.81 / 88.90 / 935462 / 97.72
5.2 Overhead
“4-2” compression circuit mainly composed by the two not gates, four nand gates, two nor gates, five notgates and three or gates.But a standard D flip-flop needs ten two-input gates. Such as the simplest C433, Half-compression needfour not gates, eight nand gates, four nor gates, ten not gates and six or gates, totally 32 two-input gates. AndLFSRneed 36 standard D flip-flop, two two-input gates, about 362 two-input logic gates. It is obvious LSFR use more hardware overhead than half-compression.
Table 4 Hardware Overhead Compression
CUT / Half-compression / LFSRNumber of two-input gates / Number of two-input gates
C432 / 32 / 362
C499 / 128 / 412
C880 / 112 / 602
C1355 / 128 / 412
C1908 / 112 / 332
C2670 / 560 / 2332
C3450 / 96 / 502
C5315 / 496 / 1282
C6288 / 128 / 312
C7552 / 435 / 2072
Table 4 shows the hardware overhead of the benchmark using different method.Half-compression use less hardware overhead than LFSR cost less, so the corresponding power consumption spending will be less than LSFR. Half-compression has the advantages of hardware overhead.
5.3 Compression Time
LFSR achieve the fault coverage test through a gradual shift. If the compression circuit contains n D flip-flop, then the whole compression need n clock to achieve the compression with long time and more power. Half-compression mentioned in this paper is based on parallel compression, all the task can be finished in a clock. So the Half-compression will speed less time and less power to compress the responses.
6 Conclusions
This paper mainly deals with responses compression in built-in self-test. There are many problems about the existing compression methods. The purpose of this paper is trying to find a compression circuit which has simple structure and is easy to achieve. We find a simple structure compression circuit, and researchthe compression efficiency of circuits using ISCAS 85 benchmark. The results showed that the Half-compression circuit has high fault coverage. It has simple structure size, higher compression speed, lower power compared with LFSR circuit. And after a further improvement it is expected as a relatively good compression method.
REFERENCES
[1]E.J. McCluskey, D. Burek, B. Koenemann, S. Mitra, J.H. Patel, J. ajski, and J.A. Waicukauski, “Test Compression—Roundtable, ” IEEE Design and Test of Computers, Vol. 20, No. 2, pp. 76-87, Mar./Apr. 2003.
[2] Subhasish Mitra and Kee Sup Kim, “XPAND: An Efficient Test Stimulus Compression Technique, ”IEEE Trans. On Compt.,Vol. 55, No. 2, pp. 163-173, Feb. 2006
[3]B.T. Murray and J.P. Hayes, “Testing ICs: Getting to the Core of the Problem, ”IEEE Trans. On Compt., Vol.29, No. 11, pp. 32-38, Nov. 1996
[4] A. Jas, J. Ghosh-Dastidar, and N.A. Touba, “Scan Vector Compression/Decompression Using Statistical Coding, ” Proc.IEEE VLSI Test Symp., pp. 114-120, 1999.
[5] A. Jas and N.A. Touba, “Test Vector Decompression via Cyclical Scan Chains and Its Application to Testing Core-Based Design, ” Proc. Int’l Test Conf., pp. 458-464, 1998.
[6] A. Chandra and K. Chakrabarty, “Test Data Compression for System-on-a-Chip Using Golomb Codes, ” Proc. IEEE VLSI Test Symp., pp. 113-120, 2000.
[7] A. Chandra and K. Chakrabarty, “System-On-a-Chip Test Data Compression and Decompression Architectures Based on Golomb Codes, ” IEEE Trans. On Computer-Aided Design, Vol. 20, No. 3, pp. 355-368, Mar. 2001.
[8] V. Iyengar, K. Chakrabarty, and B.T. Murray, “Deterministic Built-In Self Testing of Sequential Circuits Using Precomputed Test Sets, ” J. Electronic Testing: Theory and Applications(JETTA ), Vol. 15, pp. 97-114, Aug./Oct. 1999.
[9] Anshuman Chandra, and Krishnendu Chakrabarty, “Test Data Compression and Test ResourcePartitioning for System-on-a-Chip Using Frequency-Directed Run-Length(FDR ) Codes” IEEE Trans. On Compt, Vol. 52, No. 8, Aug. 2003
1