Phase shifter with reduced linear dependency

• US 7,263,641 B2
• Filed: 08/03/2004
• Issued: 08/28/2007
• Est. Priority Date: 11/23/1999
• Status: Expired due to Term

• Current Assignee: Siemens Industry Software Limited (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Tyszer, Jerzy, Rajski, Janusz, Tamarapalli, Nagesh
• Primary Examiner(s): Ton; David
• Application Number:
  US10/911,033
• Publication Number:
  US 20050015688A1
• Time in Patent Office: 1,120 Days
• Field of Search: 365/244, 380/28, 711/100, 382/276, 326/46, 714/726, 714/739, 714/729, 714/727
• US Class Current: 714/729
• CPC Class Codes: G01R 31/31813 Test pattern generators
• CPC Class Codes: G01R 31/318385 Random or pseudo-random test pattern
• CPC Class Codes: G01R 31/318541 Scan latches or cell details
• CPC Class Codes: G01R 31/318547 Data generators or compressors
• CPC Class Codes: G01R 31/318594 Timing aspects clock circuits G01R31/318552

Abstract

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.

Claims

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.