Improving Compression Ratios for Code-Based Test Pattern Compressions through Column-Wise Reordering Algorithms

摘要

Chip testing is an effective way to reduce the number of defective or faulty chips that reach the market. However, as large-scale test patterns need to be transmitted into a circuit under test during testing, the transmission time dominates the test application time of the chip testing. Therefore, code-based compression methods are widely used in compressing test patterns because of their capability to reduce the transmission time and save storage space significantly. Current code-based compression methods cannot fully apply the inherent characteristics of test patterns yet. To address this problem, this study proposes two-stage test pattern preprocessing algorithms, thereby improving the efficiency of the code-based compression method. First, we propose a column-wise reordering for Hadamard matrix (CRHM) algorithm, which decomposes a test set consisting of test patterns into a primary component set (PCS) and a residual component set (RCS). The PCS inherits some is from the original test set (OTS), and other is belong to the RCS. As the number of is contained in the RCS is less than that in the OTS, the RCS can obtain a higher code-based compression ratio. The PCS can be generated by an on-chip generator, which does not consume transmission time. Second, we propose a novel column-wise reordering for the RCS (CRRCS) algorithm. The CRRCS solves the new location of each column of the RCS one by one in the list to decrease the entropy of the RCS. The entropy denotes the shortest length of the codeword required for the symbol to be encoded. The smaller entropy value refers to a higher compression ratio. For the sorted RCS, more high-frequency symbols can be replaced by shorter codewords. Experimental results based on seven code-based compression methods show that the proposed algorithms can increase the average compression ratio by a total of 19.91%, and the highest average compression ratio reaches 85.04% for ISCAS'89 benchmark circuits.