# A Review of Test Stimulus Compression Methods for Ultra-Large-Scale Integrated Circuits
## 4 Scan Chain Optimization-Based Compression Methods  
### Linear Decompression Structure  
The first type of optimized scan chain structure is the linear decompressor, which is a combinational logic circuit consisting of XOR gates and flip-flops. Its output response space is a linear space formed by the expansion of a Boolean matrix [25]. Typical linear decompression structures include Linear Feedback Shift Registers (LFSR), Cellular Automata, and Ring Generators, as shown in Figure 4. Compared to LFSRs, RGs demonstrate enhanced encodability, albeit with an associated hardware overhead that translates to a chip area increase of up to 14% [26].  
The test stimulus compression method based on a linear decompression structure achieves the transformation of compressed test vectors X stored in the ATE into the test vectors Y inputted into the circuit under test by solving a system of linear equations, MX = Y. In this equation, M represents the characteristic matrix of the linear decompression structure, which symbolizes the structure. X is a free variable that can be reassigned and is treated as a seed, with the process of inputting the variable X into the decompression structure being referred to as reseeding. The linear decompression structure can only output the target vector if and only if the system of linear equations has a solution [27].  
Figure 4: Schematic diagram of linear decompression structure [26].  
Based on the differences in reseeding methods, the reseeding compression technique is categorized into static reseeding and dynamic reseeding. Static reseeding involves re-inputting a new seed after testing a scan chain is completed. Taking LFSR as an example, the seed is transmitted from the ATE to the LFSR, where it decompresses the test vectors and inputs them into the scan chain. Once the scan chain outputs the response, the LFSR retrieves a new seed from the ATE for the next round of decompression. In static reseeding, the structure of the LFSR is constrained by the test data, meaning that the length of the LFSR must be no shorter than the maximum number of fixed bits in the test cube.  
To reduce the length of the LFSR [63; 64], [PERSON] and [PERSON] encoded the relationship between the seed and the scan slice, allowing each test vector to be determined by multiple seeds. During static reseeding, the ATE is idle during the linear decompression process, with the seed reading process being carried out serially with the generation of test vectors. This serial operation mode results in long test time and low test efficiency.  
To address this issue, [PERSON] [65] and others proposed dynamic reseeding, which allows the ATE to read the seed and generate the test vectors in parallel, thereby increasing the utilization of the ATE and reducing test time. [PERSON] [66] utilized a ring generator as the decompression structure and optimized the dynamic reseeding technique based on the Embedded Deterministic Test (EDT). This method can generate test cubes of a fixed length, improving encoding flexibility and subsequently reducing test time. [PERSON] [67] utilized the redundant test channels of the ATE to control the seed timing and employed variable-length seed coding for test cubes. [PERSON] [68] used multiple polynomials for reseeding, reducing the dependency probability while also reducing the length of the seed. [PERSON] [69] further reduced the seed length for test sets with fewer determinants to improve test efficiency. Additionally, [PERSON] proposed partial reseeding [70], [PERSON] reseeded the overlapping parts of the scan slices [71], and [PERSON] proposed parallel LFSR reseeding [72]. Recently, [PERSON] optimized LFSR for delay faults [73] and [PERSON] proposed a mixed-mode LFSR reseeding [74], both of which can effectively increase test efficiency. [PERSON] [75] also proposed an algorithm for the shortest order of the LFSR, further reducing the order being limited by the test cube.