Method and apparatus for computing signal correlation

• US 6,606,346 B2
• Filed: 05/18/2001
• Issued: 08/12/2003
• Est. Priority Date: 05/18/2001
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Global Locate Incorporated (Broadcom, Inc.)
• Inventors: Abraham, Charles, Fuchs, Donald L.
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): Ha, Dac V.
• Application Number:
  US09/861,086
• Publication Number:
  US 20020172266A1
• Time in Patent Office: 816 Days
• Field of Search: 375/142, 375/150, 375/343, 375/364, 375/367, 370/335, 370/342, 370/441, 370/479, 370/515
• US Class Current: 375/142
• CPC Class Codes: G01S 19/29 carrier including Doppler, related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/30 code related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/37 Hardware or software details of the signal processing chain
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: H04B 1/70752 Partial correlation
• CPC Class Codes: H04B 1/7077 Multi-step acquisition, e.g. multi-dwell, coarse-fine or validation
• CPC Class Codes: H04B 2201/70715 with application-specific features

Abstract

A method and apparatus for computing a convolution between an input GPS signal and a C/A code reference by generating the convolution result in real time without storing unprocessed signal samples. The apparatus comprises a vector multiplier running at high speed to achieve the same result as a vector multiplier sized to process an entire epoch.

Claims

1. A method for computing correlations of a digital signal with a pseudorandom reference code, where said digital signal comprises a repeating code, the method comprising:

a) dividing a pseudorandom reference code into a plurality of code segments;

b) selecting a code segment;

c) forming an inner product between said selected code segment and a portion of said repeating code of said digital signal to produce a partial correlation;

d) repeating steps b) and c) to produce a plurality of partial correlations;

e) summing the plurality of partial correlations as each partial correlation is produced to form a plurality of correlations.

2. The method of claim 1 further comprising:

shifting said set of digital signal samples into a shift register, where, for each shift of the shift register, performing one or more said partial correlations.

3. The method of claim 1 where a size of said set of digital signal samples and a size of said set of pseudorandom reference code is an integer times a factor of 1023.

4. The method of claim 1 wherein said pseudorandom reference code is a C/A code of a global positioning system receiver.

5. The method of claim 4 wherein said set of pseudorandom reference code is generated by extending a code segment by replicating a C/A code bit to an integer number of samples.

6. The method of claim 5 further comprising:

generating said code segments from a lookup table by selecting one of a fixed number of non-overlapping segments of the C/A code.

7. The method of claim 6 where said code segments are generated from a set of circulating shift registers.

8. The method of claim 1 wherein the inner product is formed by multiplying each of the digital signal samples with a respective chip of the selected code segment and summing each multiplication result with other multiplication results to produce the partial correlation.

9. The method of claim 1 further comprising:

dividing the digital signal into in-phase and quadrature components; and

separately performing steps a) through e) on the in-phase and quadrature components.

10. The method of claim 9 further comprising:

producing an energy signal representing an amount of energy in the plurality of correlations;

integrating the energy signal over a pre-defined period.

11. A receiver of global positioning system (GPS) signals comprising:

an RF/IF converter for filtering and frequency translating received GPS signals having a repeating code to form an IF signal;

an analog to digital converter for digitizing the IF signal;

a tuner for removing Doppler shift from the digitized signal and producing an in-phase (I) signal and a quadrature (Q) signal;

a decimation circuit for subsampling the I and Q signals;

a convolution processor for producing I and Q partial correlations by multiplying selected segments of a C/A reference code with portions of said repeating code of each of said subsampled I and Q signals;

a first accumulator for accumulating said I partial correlations to form a plurality of correlations between said I signal and the C/A reference code; and

a second accumulator for accumulating said Q partial correlations to form a plurality of correlations between said Q signal and the C/A reference code.

12. The receiver of claim 11 further comprising:

a signal normalizer for generating normalizer values representative of the magnitude or power of the I and Q signals;

magnitude accumulator for summing the normalizer values.

13. The receiver of claim 11 wherein convolution processor comprises:

a code generator for producing each C/A reference code comprising a code look up circuit and a code extender.

14. The receiver of claim 11 wherein convolution processor comprises:

a first shift register for storing a segment of said subsampled I signal; and

a second shift register for storing a segment of said subsampled Q signal.

15. The receiver of claim 11 wherein convolution processor comprises:

a first vector multiplier for producing I partial correlations of said subsampled I signal; and

a second vector multiplier for producing Q partial correlations of said subsampled Q vector.

16. The receiver of claim 11 wherein said first and second accumulators each comprise:

an adder; and

a memory.

17. The receiver of claim 11 further comprising:

a plurality of processing channels, where each channel produces a convolution for a different GPS signal.

18. The receiver of claim 17 further comprising:

a computer for computing a position location using a plurality of convolutions.

19. A receiver of global positioning system (GPS) signals comprising:

an RE/IF converter for filtering and frequency translating received GPS signals having a repeating code to form an IF signal;

an analog to digital converter for digitizing the IF signal;

a tuner for removing Doppler shift from the digitized signal and producing an in-phase (I) signal and a quadrature (Q) signal;

a decimation circuit for subsampling the I and Q signals;

a convolution processor for producing I and Q partial correlations by multiplying selected segments of a C/A reference code with portions of said repeating code of each of said subsampled I and Q signals, and further comprising a code generator for producing each C/A reference code comprising a code look up circuit and a code extender, a first shift register for storing a segment of said subsampled I signal and a second shift register for storing a segment of said subsampled Q signal, a first vector multiplier for producing I partial correlations of said subsampled I signal and a second vector multiplier for producing Q partial correlations of said subsampled Q signal;

a first accumulator for accumulating said I partial correlations to form a plurality of correlations between said I signal and the C/A reference code;

a second accumulator for accumulating said Q partial correlations to form a plurality of correlations between said Q signal and the C/A reference code;

a signal normalizer for generating normalizer values representative of the magnitude or power of the I and Q signals; and

magnitude accumulator for summing the normalizer values.

20. The receiver of claim 19 wherein said first and second accumulators each comprise:

an adder; and

a memory.

21. The receiver of claim 19 further comprising:

a plurality of processing channels, where each channel produces a convolution for a different GPS signal.

22. The receiver of claim 19 further comprising:

a computer for computing a position location using a plurality of convolutions.

23. A method of computing correlations between a pseudorandom reference code and a digital signal having a repeating code, the method comprising:

a) dividing a pseudorandom reference code into a plurality of code segments;

b) selecting a portion of the repeating code of the digital signal;

c) selecting a code segment;

d) forming an inner product between said selected code segment and the selected portion of said repeating code to produce a partial correlation;

e) repeating steps c) and d) to produce a plurality of partial correlations;

f) repeating steps b) through e) for a plurality of portions of the repeating code;

g) accumulating the plurality of partial correlations as each partial correlation is produced to form a correlation; and

h) forming a plurality of correlations.