ADVANCED FREQUENCY-DIRECTED RUN-LENTH BASED CODING SCHEME ON TEST DATA COMPRESSION FOR SYSTEM-ON-CHIP

Zhang Ying,Wu Ning,Ge Fen

(Collegeof Electronic and Information Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing,210016,P.R.China)

INTRODUCTION

With the improvement of integrated circuit design and manufacturing technology,the complexity of test vector sets has increased followed by the increase of testing time and cost[1].Conventional testing methods store the test vector and test responses in automatic test equipment(ATE)with limited test equipment speed,I/O channels and storage space.The bandwidth of ATE is the bottleneck of high speed testing and will increasingly impact chip testing in complex system.One solution classified as test resource partitioning(TRP)methods is to compress test vectors for reducing storage requirements and test time.The scheme requires additional decompression module set in the original chip,so relatively simple realization circuit and the compression effect become key issues for compression coding methods.

Compression coding methods for test vectors are classified into three kinds:run-length based codes, dictionary based codes and statistical codes[2].The run-length based codes adopts different codewords based on the sequence′s length(runs of 0s or 1s)distribution without the constraint of coding length.It has better compression effectiveness and relatively simple realization circuits compared with dictionary based codes and statistical codes.The classical run-length coding methods,including Golomb codes[3]and frequency-directed run-length(FDR)codes[4],feature the prefix and the tail constituting thecodeword.The prefix shows group characteristics and the information of the source codes length.The tail is assigned to corresponding binary codes according to specific encoding methods.There are two common drawbacks for Golomb codes and FDR codes: one is that they only concentrate on the runs of 0s without consideration for runs of 1s.The other is that the coding sources are differential test vectors.The differential signal requires cyclical scan register(CSR)module for the onchip decoder,which increases the hardware overhead.

Many new coding schemes are proposed in related compression codes research,including alternate variable length codes[5], the variablelength input Huffman coding[6]and selected variable-length input coding(SVIC)[7]based on statistical characteristic analysis,the 9-Ccode[8]and modified frequency-directed run-length(MFDR)codes combining the statistical properties and characteristics of FDR codes[9], etc. Among them,coding schemes based on the statistical characteristic analysis[6-7]have higher compression ratio,while the encoding and decoding processes are relatively complex and the hardware overhead is even larger than Golomb and FDR codes.

A novel compression codes called advanced frequency-directed run-length(AFDR)codes is proposed with relatively lower hardware overhead and higher compression efficiency by improving FDR coding manner.AFDRcodes considers both the runs of 0s and 1s simultaneously,and optimizes the codes for 00 and 11 to further improve the compression efficiency.Furthermore,its decompression circuit is simpler than FDR codes without need for CSR circuit.

1 AFDR CODES

The proposed AFDR codes is the improved coding scheme based on FDR.FDRonly encodes the consecutive 0-sequence,the sequence which ends with 1 such as 00001is encoded according to the length of 0-run. And shorter 0-runs are mapped shorter codewords,while single 1 is regarded as the sequence whose run-length is zero.AFDR encodes both the 0-runs and 1-runs with almost the same codeword as FDR codes and also applies the shorter codewords to the shorter runs.

Fig.1 shows the distribution of the 0-and 1-runs for test vectors of s9234 circuit.The s9234 circuit is a typical sequence circuit and one of the largest ISCAS benchmark circuits.It is obvious that the shorter runs occur more frequently,so mapping them to short codewords will increase the compression ratio greatly.This is also the reason for the primary encoding manner of AFDR and FDR codes.

Fig.1 Distribution of run-length for circuit s9234

The AFDR codes is constructed as follows:the 0-and 1-runs are divided into groups A1,A2,A3,…,Ak,wh ere k is determined by the maximum length l max(2k-2≤ l max≤ 2k+1-3).A run with the length l is mapped to group Aj based on

Each codeword of AFDR consists of two parts with same length—a group prefix and a tail.The group prefix is used to identify the group which the run belongs to.For example,the run length is 6,then j==3,so it belongs to group A3.The tail is used to identify the members within the group.The size of codeword increases by 2 b(1 b for the prefix and 1 b for the tail)as the run′s length moves from group Aj to group Aj+1.

The AFDR encoding procedure is shown in Table 1.FDR codes has two codewords in group A1:0 b and 1 b run legnth respectively,while AFDR coding has only one codeword for the 1 b length of runs(01 or 10)for AFDRhandles 0 and 1 strings simultaneously.However,AFDR codes assumes 0-runs and 1-runs appear alternately.When they become consecutive,additional codeword,00,is chosen as the separator.

The 2 b length in Table 1 indicates the special adoption to improve the compression efficiency.According to the original coding rules,the codeword for 0-and 1-runs with 2 b length(001 or 110)is 1000,obviously wider than the original code,thus impacting on compression ratio.Furthermore,it can be proved that the quantity of 2 b long runs is quite considerable.Fig.2 shows the run-length distributions of standard circuit s9234,s13207,s38417 and s38584.The numbers of 2 b long runs is larger than that of other longer ones.Therefore,reducing the 2 b long codeword will influence the efficiency of compression.AFDR coding applies 000 for 2 b long runs instead of original 1000.

Table 1 Application of AFDR coding

Fig.2 Comparison of length frequency of runs for ISCASbenchmark circuits

An example is presented to illustrate AFDR coding realization and compared with FDR coding.Assume that there is a 32 b test sequence T D={00000111011111000000000000011111}.Apply FDRcoding and the encoded sequence T FDR={10110000010000000011011100000000},32 b long.While apply AFDRcoding,the corresponding sequence TAFDR={10110000010111101101010}is 23 b long.It is obvious that the compression effectiveness of AFDRis better than FDRcoding.Fig.3 shows the encoding procedure of AFDR coding.

Fig.3 AFDRencoding procedure of test sequence T D

2 ANALYSISON AFDR CODES

The probability of 0 is defined as p and the probability of 1 as(1-p).H(p)is the entropy indicating thevalue of information.As far as data compression is concerned,the entropy is the amount of information required for encoding which is relevant to the theory limit of compression ratio.H(p)of the test vector is proposed by the following equation[5]

H(p)=- p log2p- (1- p)log2(1- p)(2)

The upper limit of the compression gain Umaxis obtained by

For the run-length coding methods,the compression gain U is defined as

whereλis the average number of bits in any run generated by the data source and Lavgthe average codeword length.

According to the AFDRcoding table,λis defined as

The run lengths within the limit 2k-2≤ l≤2k+1- 3 belong to group Ak,so the probability P(i,k)of an arbitrarily chosen run with the length i within group Ak is given as

Codeword in group Ak consists of 2 kb,and the average codeword length Lavgis given as

Therefore,the compression gain U AFDR of AFDR coding is given as

While the compression gain U FDR is expressed as follows[5]

Fig.4 shows the comparison of U AFDR,U FDR and U max with different probability distributions.It is concluded that the compression gain of AFDR is superior to that of the FDR.The compression gain of AFDR is close to the upper bound when 0.990≤ p≤ 0.999 as well as 0.001≤ p≤ 0.009,while that of FDR stays at 0.5.

Fig.4 Comparison of compression gain between AFDR,FDR and uper limit

3 DATA PREPROCESSING AND TEST DATA DECOMPRESSION

Testing vectors often contain a large number of unspecified bits(x)to be determined as 0 or 1 before being compressed.How to fill the unspecified bits will affect the run-length distribution and the maximum compression ratio.The optimization of data preprocessing is essential to test vectors compression.The schemes for data preprocessing belong to non-deterministic polynomial complete(NPC)problems and a compatible preprocessing method for AFDRcodes is adopted to balance the process complexity and related compression effect.The realization process is as follows:

(1)For vectors as 0… 0x… x 0… 0 or 1… 1x…x 1…1,the unspecified bits are filled with their adjacent bits(0 or 1).

(2)For 0… 0x… x 1… 1 or 1… 1x… x 0… 0,name the first char of the vector as the previous char and the end char as the next char,then fill all the x with the previous char if the run length of the char string does not exceed the maximum length of its group,otherwise fill the x with the previous char until the run length is the maximum length and fill the remaining x with the next char.

The decoder of AFDRis composed of a finite state machine(FSM),a shift counter(sfcounter),a read counter(rd-counter)and a T flip-flop.Fig.5 depicts the structure of this decoder.The signal b-in is the input of FSM and en is sent to the input data to show the decoder is ready.The signal out is the output of FSM and transmitted through the T flip-flop to generatefinal decompressed signal f-out.va indicates that the output is valid.c-in is the signal sent from FSM to shift the prefix or tail into the sfcounter,the signals shift and,dec1 are respectively applied to shift the data in and to decrease the number of sf-counter.inc and dec2 are used to increase and decrease the number of rdcounter,respectively.rs1 and rs2 indicate the reset states of the corresponding counter.

Fig.5 Block diagram of decoder for AFDR

The operation process of the decoder is as follows:

Step 1 FSM uses b-in to send the group prefix with the end of 0 to sf-counter.en,shift and inc are set high in this period.

Step 2 out remains low to keep T flip-flop outputting the previous state,meawhile va is high to show the output is effective.dec1is high.sf-counter continues decreasing until rs1 is set high(the number of sf-counter is 0).

Step 3 The tail is sent to sf-counter from b-in and the length is counted by rd-counter.dec2 decreases rd-counter until rs2 is set high(the input of tail ends).

Step 4 out is high until sf-counter is 0 and then trigger T flip-flop changes state.

If the group prefix is 0(Step 1),then en,shift and inc are high.The process of the next clock cycleis as follows:

(1)If b-in is 1(the run length is 1 b),dec1,dec2 are high and the out is low simultaneously while va gains high level to make T flip-flop to output the previous state,then moves to Step 4.

(2)If b-in is 0,en,shift and inc are high and acquire the next b-in.If the new b-in is 0(the run length is 2 b),let T flip-flop to output the pervious state twice,otherwise(the separate codes)dec2 and out are high and va is low to maintain the state of T flip-flop and prepares for the next codeword.

The state diagram of FSM for decompression is shown in Fig.6.S0—S5 are the states for decompressing the strings with run-length longer than 2 b,while S6—S9are for decompressing the strings with run-length of 1 b or 2 b length and the separator.FSMis synthesized using Synopsys design compiler and the logic synthesized circuit containing only 4 flip-flops and 43 gates.It is obvious that the additional hardware overhead that the decompression circuit requires is very small.

Fig.6 State diagram of FSM for decompression circuit

4 EXPERIMENTAL RESULTS

The experimental results of the test vector compression are presented for some large-scale circuits in the ISCAS89 Benchmark.The original test vectors are generated by Mintest[10]ATPG tool from Duke University.Table 2 shows the compression ratios of AFDR coding and other schemes in Refs.[3,4,7,9].Theaverage(AVG)compression ratio is given in the last line.

Thecompression ratio is computed as follows

where STDis the size of the source test set TDand STEthe size of the encoded test set T E.

Table 2 Compression ratios of different schemes

Concluded from Table 2,the compression ratios of AFDRcoding arehigher than those of other coding schemes except MFDR and SVIC codes of s9234 and s13207.Considering both 0-and 1-runs,AFDR codes has better compression effectiveness for most of the benchmark circuits by modifying the codewords of 00 and 11 strings.Because of the statistic characteristic of test vectors,MFDR and SVIC coding have higher compression ratios for some circuits with specific statistical distribution such as s9234 and s13207 circuits.Moreover,AFDR is obviously superior to other coding schemes on the average compression ratio.

5 CONCLUSION

An effective compression scheme for test vector of system-on-chip is proposed as AFDR coding.The AFDR coding improves the FDR codes by considering the 0-runs and 1-runs simultaneously.The CSR circuit is never needed to decrease the hardware and encoding time consumption.The compression effectiveness is improved by the optimization of specific run lengths.The probabilistic analysis of AFDR codes is also presented to demonstrate the intrinsic superiority.The experimental results on ISCAS89 benchmark circuits validate the compression effectiveness of AFDR coding.The following research will focus on adoption of other preprocessing methods for higher compression ratio and the construction of practical tester with AFDR coding.

[1] Semiconductor industry association. International technology roadmap for semiconductors 2009 edn[EB/OL].http://www.itrs.net/Links/2009ITRS/Home2009.htm,2005-01-10/2011-05-23.

[2] Mehta U,Dasgupta K S,Devashrayee N M.Survey of test data compression technique emphasizing code based schemes[C]∥12th Euromicro Conference on Digital System Design,Architectures,Methods and Tools,DSD′09.Patras,Greece: IEEE,2009:617-620.

[3] Chandra A,Chakrabarty K.System-on-a-chip test data compression and decompression architectures based on Golomb codes[J].IEEE Transaction Computer-Aided Design,2001,20:355-368.

[4] Chandra A,Chakrabarty K.Frequency-directed Runlength(FDR)codes with application to System-ona-chip test data compression[C]∥19th IEEEV LST Test Symposium.Marina Del Reg,USA:IEEE,2001:42-47.

[5] Chandra A,Chakrabarty K.A unified approach to reduce SoC test datavolume,scan power and testing time[J].IEEE Transaction on Computer-aided Design of Integrated Circuits and system,2003,22(3):352-363.

[6] Gonciari P T,Al-Hashimi B M,Nicolici N.Variablelength input Huffman coding for system-on-a-chip test[J].IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems,2003,22(6):783-796.

[7] Hu B,Chen G,Xie Y.System on chip test data compression based on SVIC coding[J].Journal of Electronic Measurement and Instrument,2006,20(1):73-78.(in Chinese)

[8] Tehranipoor M,Nourani M,Chakrabarty K.Ninecoded compression technique for testing embedded cores in SoCs[J].IEEE Transaction on Verg Large Scale Integration(V LSI)Systems,2005,13(6):719-731.

[9] Feng J,Li G.A test data compression method for system-on-a-chip electronic design[C]∥4th IEEE International Symposium on Test and Applications DEL TA 2008.Hong Kong,China: IEEE,2008:270-273.

[10]Hamzaoglu I,Patel J H.Test set compaction algorithms for combinational circuits[C]∥Procssing of IEEE/ACM International Conference on CAD.San Jose,USA:IEEE,1998:283-289.