Phase shifter with reduced linear dependency
View Patent ↗A method is disclosed for the automated synthesis of phase shifters. Phase shifters comprise circuits used to remove effects of structural dependencies featured by pseudo-random test pattern generators driving parallel scan chains. Using a concept of duality, the method relates the logical states of linear feedback shift registers (LFSRs) and circuits spacing their inputs to each of the output channels. The method generates a phase shifter network balancing the loads of successive stages of LFSRs and satisfying criteria of reduced linear dependency, channel separation and circuit complexity.
1. A method for generating a phase shifter network, comprising:
providing a linear finite state machine, the linear finite state machine comprising a plurality of cells;
providing a first combination of cells from the plurality of cells, the first combination of cells providing a first plurality of sequences to be sent to a circuit under test;
generating at least one second combination of cells from the plurality of cells to provide at least one second plurality of sequences to be sent to the circuit under test;
determining whether the at least one second plurality of sequences overlaps with the first plurality of sequences; and
generating a linear phase shifter based on whether the at least one second plurality of sequences overlaps with the first plurality of sequences.
2. The method of claim 1 , wherein determining comprises evaluating at least one inter-channel separation criterion.
3. The method of claim 1 , wherein determining comprises evaluating fanout of the plurality of cells.
4. One or more computer-readable media having computer-executable instructions for performing the method of claim 1 .
5. A method, comprising:
providing an integrated circuit to be tested, the integrated circuit capable of receiving scan chains;
providing a linear finite state machine (LFSM) having a balanced load; and
generating a linear phase shifter, the linear phase shifter working in combination with the LFSM to send a plurality of scan chains to the integrated circuit to be tested.
6. The method of claim 5 , wherein generating the linear phase shifter comprises selecting cells of the LFSM by using a pseudo-random number generator yielding uniformly distributed integers between 0 and n-1, wherein n represents the size of the LFSM.
7. The method of claim 6 , wherein selecting cells comprises consulting a histogram of the cells to determine how often the cells have been used.
8. The method of claim 7 , wherein selecting cells further comprises given a first cell, temporarily excluding the first cell if the number of times the first cell has been used exceeds a given threshold.
9. One or more computer-readable media having computer-executable instructions for performing the method of claim 5 .
10. The method of claim 5 , wherein the LFSM comprises a t-LFSR.
11. The method of claim 5 , wherein generating the linear phase shifter comprises:
generating a linear combination of taps; and
verifying that test patterns produced by the linear combination of taps do not overlap with sequences generated by at least one previously generated combination of taps.
12. One or more computer-readable media having computer-executable instructions for performing a method of processing memory elements, the method comprising:
preprocessing a plurality of memory elements; and
generating a plurality of XOR taps from the plurality of memory elements, wherein generating the plurality of XOR taps comprises:
generating pseudo-random integers uniformly distributed in a given range; and
filling in a vector to produce a plurality of sequences chosen from an element set using the pseudo-random integers.
13. The one or more computer-readable media of claim 12 , wherein preprocessing the plurality of memory elements comprises implementing the following pseudo-code:
Preprocessing true
while Preprocessing do
for i 0 up to t-LFSR size − 1 do Position[i] = i
k 0
for i 0 up to t-LFSR size − 1 do
if
Histogram[i] = limit then
Position[i] Position[k]
k k + 1
if t-LFSR size − k < desired number of XOR taps
then limit limit + 1
else Preprocessing false.
14. The one or more computer-readable media of claim 13 , wherein generating the plurality of XOR taps further comprises implementing the following pseudo-code:
for i 0 up to desired number of XOR taps − 1 do
r random (k, t-LFSR size − 1)
Taps[i] Position[r]
Position[r] Position[k]
k k + 1.
15. One or more computer-readable media having computer-executable instructions for performing a method of synthesizing phase shifters, the method comprising:
generating a plurality of XOR taps combinations; and
adding at least one of the plurality of XOR taps combinations and a corresponding guard combination to a list.
16. The one or more computer-readable media of claim 15 , further comprising repeating the step of adding until a counter reaches a value corresponding to a desired interchannel separation.
17. The one or more computer-readable media of claim 16 , further comprising implementing the following pseudo-code:
channels 0
while channels < requested outputs do
generate XOR taps
rejected false
initialize a dual t-LFSR using a XOR taps combination
i 0
while i ≦ separation and not rejected do
rejected already generated (state of the dual
t-LFSR)
simulate the dual t-LFSR for one clock cycle
i i + 1
if not rejected then
insert the XOR taps combination into a list of guard
combinations
insert the state of the dual t-LFSR into the list of guard combinations
record the XOR taps combination
channels channels + 1.
18. An apparatus, comprising:
means for providing a linear finite state machine having multiple memory elements coupled together, the memory elements having outputs for driving the linear phase shifter;
means for analyzing loading of outputs of memory elements to determine loading information indicating the loading of memory elements;
means for generating the linear phase shifter using the loading information, the linear phase shifter having linear logic gates coupled to the outputs of the multiple memory elements; and
means for coupling the linear phase shifter to multiple scan chains used for testing the integrated circuit.
19. One or more computer-readable media having computer-executable instructions for performing a method comprising:
providing a linear finite state machine having multiple memory elements coupled together, the memory elements having outputs for driving the linear phase shifter;
analyzing loading of outputs of memory elements to determine loading information indicating the loading of memory elements;
generating the linear phase shifter using the loading information, the linear phase shifter having linear logic gates coupled to the outputs of the multiple memory elements; and
coupling the linear phase shifter to multiple scan chains used for testing the integrated circuit.