Research Article

Run-Length Based Efficient Compression for System-on-Chip

A. Balasubramaniyan, S. Saravanan and Har Narayan Upadhyay
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Large test data volume is one of the major problems in the emerging System-on-Chip (SoC) and this can be reduced by test data compression techniques. Variable-to-variable length compression is one among the test data compression techniques. This study demonstrates a variable-to-variable length based compression technique called Run-Length based Efficient Compression. The patterns which are selected for doing compression can be partitioned into blocks having equal width. The partitioned blocks can be compared with the adjacent one and can be merged. A control code is used to denote the number of blocks merged. The proposed method can be tested by calculating the effect of compression on larger ISCAS’89 benchmark circuits.

Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

A. Balasubramaniyan, S. Saravanan and Har Narayan Upadhyay, 2013. Run-Length Based Efficient Compression for System-on-Chip. Journal of Artificial Intelligence, 6: 107-111.

DOI: 10.3923/jai.2013.107.111

Received: October 18, 2012; Accepted: November 08, 2012; Published: January 14, 2013


The varied development in the field of process technology has crammed millions of transistors into a single chip with many functions. In spite of these more ubiquitous designs, there are a major issue of defects in these designs and thereby a need to test these designs. These are affected by various test challenges. Large amount of test pattern is the major problems for the SoC vendor.

The large test pattern not only exceeds the commercial Automatic Test Equipment (ATE) memory capacity and I/O channel, but also raises the complication of testing time and test power. This has a direct impact on testing design cost and earlier to market. The reduction of test vectors is one of the widely growing fields in testing industry. The various methods that are used to reduce the test pattern that is stored in the ATE memory are test pattern compaction and compression.

Many test data compression methods proposed so far is to minimize test pattern and reduce its transmission activity between the ATE and SoC. ATE stores compressed test pattern. On-Chip decoder which is in SoC is used to bring uncompressed test pattern without any change.

Many testing engineers are doing many researches on test pattern compression and interested to reduce the test pattern volume. As a result many compression techniques are evolved. Code-based scheme is the one which evolved to reduce the patterns. According to the specific property to encode the data, the original test data is divided into number of symbols and replace it by code words (Touba, 2006). A run-length based compression technique called Multi-Dimensional Pattern Run-length Codes (MDPRC) (Tseng and Lee, 2010) encodes the original test data by partitioning it by number of blocks and runs the repeated blocks encoded by a codeword. Proper control encode is used in this technique.

In order to minimize the consecutive test blocks a block merging based technique (El-Maleh, 2008) is proposed to merge the blocks. A pattern clustering technique (Saravanan et al., 2011) is used to achieve higher test data compression by identifying proper conflict bit (‘U’). A unified approach in reduction of test pattern is discussed (Chandra and Chakrabarty, 2003). Extended frequency run length is observed (El-Maleh and Al-Abaji, 2002). This novel test data compression technique provides a substantial improvement in the compression of test pattern. Circular-scan based architecture (Azimipour and Eshghi, 2008) is used to select several scan chains in parallel approach with help of multiple hot decoders. Scan insertion and scan stitching is performed with Register Transfer Level (RTL) coding style, which is discussed (Reaz et al., 2009). In this work scan flops are considered as don’t use during synthesis process and results with cost reduction. Hybrid approach in ant colony method is presented by Shang and Zhang (2012) is used to reduce power dissipation in test pattern.


The test patterns generated by the ATE can be encoded by the runs of compatible patterns. Each test set can be partitioned into number of bit-patterns. The bit-patterns are then compared with its adjacent one. Finally the bit-patterns are merged to form Encoded pattern. The merged bit-patterns are encoded by Control Code (C), which is followed by encoded pattern collectively forms the final compressed Codeword for the test set. Figure 1 shows the entire block diagram of the proposed technique.

Initially the test set comprises of 1, 0 and X. By filling technique ‘X’ in test data is filled by either ‘0’ or ‘1’. Now the test set is divided by various numbers of bit-patterns according to the Control Code. For example, if the control code length is 2-bit (00, 01, 10 and 11) means the length of bit-pattern is varied from 2, 2, 3 and 4 (Table 1). Also if the Control Code is ‘11’, then it can encode 4 bit-patterns and each of 4-bits length. If the control code is ‘10’, then it can encode 3 bit-patterns of 3-bits each and so on.

Image for - Run-Length Based Efficient Compression for System-on-Chip
Fig. 1: Block diagram of proposed efficient compression technique

Table 1: An example for efficient compression technique
Image for - Run-Length Based Efficient Compression for System-on-Chip
C: Control code, E: Encoded pattern, C = 2-bit

Then the bit patterns are compared with its adjacent bit-pattern by bit-by-bit. Initially the maximum value of the Control Code is taken and has to merge the bit-patterns. If there is no possibility of merging occurs, then the Control Code value is decremented and has to merge the bit-patterns.

For example, in Table 1, the input test pattern length is 29 (“X1XX0111X1110X1X01X11X X10XX0X”). Here the Control Code length is 2-bit. Initially the maximum Control Code value “11” is taken. It can encode 16-bits. So the first 16-bits are taken and can be divided into 4 bit-patterns of 4-bit length each. Now the 4 bit-patterns are compared and merged into 4-bit encoded pattern (E). Then the Control Code followed by encoded pattern form a Codeword. Now the next 16-bits are taken and have to merge it. If there is no possibility for merging, then the Control Code has to be decremented and the same process is repeated till last input bit is merged. The final compressed Codeword for the above input is “11011101011010X” of 15-bit length. The ‘X’ in the test data can be either filled by ‘0’ or ‘1’ by filling technique. Then according to the Control Code by Control Code Generation block the test patterns are partitioned into bit-patterns. Then the bit-pattern comparator compares the bit-pattern and is merged. If the possibility of merging is false then the Control Code is Decremented. The final merged Codeword was generated.


The experiments are targeted over larger ISCAS’89 benchmark circuits. The benchmark circuits were generated by Mintest ATPG (Automatic Test Pattern Generator). The formula used to calculate the compression ratio (CR) is given by:

Image for - Run-Length Based Efficient Compression for System-on-Chip

For, example, s5378 benchmark circuit gives 47.15% compressed test pattern. This compression can be done by handled with help of ‘X’ in the benchmark circuits. Replacing or filling ‘X’ in the benchmark circuits by ‘0’ and then the compression is done. Also by replacing ‘X’ by ‘1’ and again the compression is done. This proposed X-Filling techniques results are tabulated in Table 2.

Figure 2, shows the simulation waveform of proposed technique. Unspecified bit (X) as a input is used in this simulation. The final compressed output in the waveform is highlighted. A 16-bit input is taken for the experiment and its output can be given in 6-bit. Figure 3 compares the compression ratios of various Benchmark circuits.

Table 2: Compression ratio (CR) of the proposed technique
Image for - Run-Length Based Efficient Compression for System-on-Chip

Image for - Run-Length Based Efficient Compression for System-on-Chip
Fig. 2: Simulation waveform of the proposed technique

Image for - Run-Length Based Efficient Compression for System-on-Chip
Fig. 3: Comparison of various benchmark circuits by their compression ratio

It shows that the Filling technique has the least compression ratio compared to other techniques. For s9234 circuits the filling techniques don’t give any compression at all.


A variable-to-variable length compression technique was presented to achieve better compression. The input test sets are partitioned into number of bit-patterns according to the Control Code. The bit-patterns are then compared and merged. Both ‘0’ and ‘1’ of test patterns are also experimented in the proposed technique. All these experiments are done on larger ISCAS’89 benchmark circuits. Compression ratio is in the range of 47 to 76%. Thus final result indicates that the circuits having ‘X’ achieves better compression.


  1. Chandra, A. and K. Chakrabarty, 2003. A unified approach to reduce SOC test data volume, scan power and testing time. IEEE. Trans. Comput. Aided Des. Integrat. Circ. Syst., 22: 352-363.
    CrossRef  |  

  2. El-Maleh, A.H. and R.H. Al-Abaji, 2002. Extended frequency-directed run length code with improved application to system-on-a-chip test data compression. Proceedings of the 9th International Conference on Electronics, Circuits and Systems, Volume: 2, September 15-18, 2002, Dubrovnik, Croatia, pp: 449-452
    CrossRef  |  

  3. El-Maleh, A.H., 2008. Efficient test compression technique based on block merging. IET Comput. Digit. Tech., 2: 327-335.
    CrossRef  |  Direct Link  |  

  4. Shang, J. and L. Zhang, 2012. Ant colony algorithm and genetic algorithm optimization for test vector reordering inform. Technol. J., 11: 1786-1789.
    Direct Link  |  

  5. Azimipour, M. and M. Eshghi, 2008. Parallel circular-scan architecture. J. Applied Sci., 8: 2083-2090.
    CrossRef  |  Direct Link  |  

  6. Reaz, M.B.I., W.F. Lee, N.H. Hamid, H.H. Lo and A.Y.M. Shakaff, 2009. High degree of testability using full scan chain and ATPG-An industrial perspective. J. Applied Sci., 9: 2613-2618.
    CrossRef  |  Direct Link  |  

  7. Saravanan, S., P. Selvakumar, A. Balasubramanian and R. Silambamuthan, 2011. Achieving higher test data compression using pattern clustering technique. Proceedings of the IEEE International Conference on Computational Intelligence and Computing Research, 16-18th December, 2011, India. -

  8. Touba, N.A., 2006. Survey of test vector compression techniques. IEEE Des. Test Comput., 23: 294-303.
    CrossRef  |  Direct Link  |  

  9. Tseng, W.D. and L.J. Lee, 2010. Test data compression using multi-dimensional pattern run-length codes. J. Electron. Test, 26: 393-400.
    CrossRef  |  Direct Link  |  

©  2023 Science Alert. All Rights Reserved