Layout-friendly test pattern decompressor

1. A circuit, comprising:

a register configured to be a linear finite state machine and comprising storage elements, injection devices, one or more input channels for injecting variables using the injection devices, and one or more feedback devices;

a plurality of phase shifters, each of the plurality of phase shifters configured to receive signals from a unique segment of the register;

scan chains, serial inputs of the scan chains configured to receive signals from outputs of the plurality of phase shifters,

wherein the one or more input channels are coupled to the injection devices at injection points in the register, each of the injection points being assigned to one of the one or more input channels based on lifespan values for the injection points, the injection points being determined based on one or more predetermined requirements, a life span value for an injection point in a specific segment of the register being a number of clock cycles for which a variable injected at the injection point can provide encoding capacity to scan chains associated with the specific segment of the register before being shifted out of the specific segment of the register.

2. The circuit recited in claim 1 , wherein the register is a ring generator.

3. The circuit recited in claim 1 , wherein at least one segment of the register providing signals to a phase shifter in the plurality of phase shifters contains two groups of bits, bits in each of the two groups of storage elements forming a shift register, the shift register having one or more of the injection points, one or more points for inserting the feedback devices, or both.

4. The circuit recited in claim 1 , wherein the one or more predetermined requirements comprise: a requirement that a feedback device and an injection device should not be located at the same location between two neighboring storage elements of the register, a requirement that any two of the injection devices should be separated by at least two neighboring storage elements of the register, or both.

5. The circuit recited in claim 1 , wherein the injection points in each segment of the register are assigned to different input channels if a number of the injection points in the each segment of the register is less than or equal to a number of the one or more input channels, or each of the one or more input channels is assigned to at least one of the injection points in each segment of the register if the number of the injection points in the each segment of the register is greater than the number of the one or more input channels.

6. The circuit recited in claim 1 , wherein the assignment of the injection points to the one or more input channels employs a diagonal search method on a two-dimensional map which groups the injection points in each of the segments of the register in one of columns or rows of the two-dimensional map, the injection points in each of the columns or rows being ordered according to the life span values of the injection points.

7. The circuit recited in claim 1 , wherein each of the one or more input channels is assigned to at least one of the injection points in each segment of the register, and sums of the life span values for the injection points are equal for the one or more input channels.

8. The circuit recited in claim 1 , wherein the injection devices and the feedback devices are XOR gates.

9. The circuit recited in claim 1 , wherein each of the plurality of phase shifters comprises XOR gates.

10. One or more non-transitory computer-readable media storing computer-executable instructions for causing a computer to perform a method, the method comprising:

creating a circuit in a circuit design for testing a chip fabricated according to the circuit design, the circuit comprising:

a register configured to be a linear finite state machine and comprising storage elements, injection devices, one or more input channels for injecting variables using the injection devices, and one or more feedback devices;

a plurality of phase shifters, each of the plurality of phase shifters configured to receive signals from a unique segment of the register;

scan chains, serial inputs of the scan chains configured to receive signals from outputs of the plurality of phase shifters,

wherein the one or more input channels are coupled to the injection devices at injection points in the register, each of the injection points being assigned to one of the one or more input channels based on lifespan values for the injection points, the injection points being determined based on one or more predetermined requirements, a life span value for an injection point in a specific segment of the register being a number of clock cycles for which a variable injected at the injection point can provide encoding capacity to scan chains associated with the specific segment of the register before being shifted out of the specific segment of the register.

11. The one or more non-transitory computer-readable media recited in claim 10 , wherein the register is a ring generator.

12. The one or more non-transitory computer-readable media recited in claim 10 , wherein at least one segment of the register providing signals to a phase shifter in the plurality of phase shifters contains two groups of bits, bits in each of the two groups of storage elements forming a shift register, the shift register having one or more of the injection points, one or more points for inserting the feedback devices, or both.

13. The one or more non-transitory computer-readable media recited in claim 10 , wherein the one or more predetermined requirements comprise: a requirement that a feedback device and an injection device should not be located at the same location between two neighboring storage elements of the register, a requirement that any two of the injection devices should be separated by at least two neighboring storage elements of the register, or both.

14. The one or more non-transitory computer-readable media recited in claim 10 , wherein the injection points in each segment of the register are assigned to different input channels if a number of the injection points in the each segment of the register is less than or equal to a number of the one or more input channels, or each of the one or more input channels is assigned to at least one of the injection points in each segment of the register if the number of the injection points in the each segment of the register is greater than the number of the one or more input channels.

15. The one or more non-transitory computer-readable media recited in claim 10 , wherein the assignment of the injection points to the one or more input channels employs a diagonal search method on a two-dimensional map which groups the injection points in each of the segments of the register in one of columns or rows of the two-dimensional map, the injection points in each of the columns or rows being ordered according to the life span values of the injection points.

16. The one or more non-transitory computer-readable media recited in claim 10 , wherein each of the one or more input channels is assigned to at least one of the injection points in each segment of the register, and sums of the life span values for the injection points are equal for the one or more input channels.

17. The one or more non-transitory computer-readable media recited in claim 16 , wherein the injection devices and the feedback devices are XOR gates.

18. The one or more non-transitory computer-readable media recited in claim 10 , wherein each of the plurality of phase shifters comprises XOR gates.