Method and apparatus for segmented code correlation

• US 7,492,810 B2
• Filed: 04/04/2005
• Issued: 02/17/2009
• Est. Priority Date: 04/04/2005
• Status: Active Grant

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Harrison, Daniel D.
• Primary Examiner(s): Fan; Chieh M
• Assistant Examiner(s): Lee; Siu M
• Application Number:
  US11/097,294
• Publication Number:
  US 20060222113A1
• Time in Patent Office: 1,415 Days
• Field of Search: 375/208, 375/209, 375/210, 375/343, 375/150, 375/367, 375/142, 375/145, 375/149, 708/422
• US Class Current: 375/150
• CPC Class Codes: G01S 19/24 Acquisition or tracking or demodulation of signals transmitted by the system synchronisation aspects of direct sequence spread spectrum modulation H04B1/7073
• 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/708 Parallel implementation

Abstract

A method and an apparatus is disclosed for efficient cross correlation of a plurality of signal vectors. Incoming data is partitioned into several segments and processed according to an algorithm where data rotation is a function of post-correlation memory size.

Claims

1. A parallel correlator comprising:

a data memory having a sample-sequential input and a sample-parallel output, said data memory organizing the sample-sequential input into blocks of n sequential samples and providing each of said blocks cyclically to said sample-parallel output;

a segmented code register organized to receive a code sequence as an plurality of input samples, said segmented code register organizing the input samples into N segments of L length, wherein N is less than n and greater than one;

the segmented code register configured to register the input samples in their order of input and to one of forward-shift or backward-shift the registered samples on each clock cycle prior to parallel output, said forward-shift shifting the registered samples by one sample position and the backward-shift shifting the registered samples by one segment of samples;

said segmented code register having a sample parallel output; and

an inner product calculator having at least two sample-parallel inputs, said inner product calculator having one output representing the inner product of the two sample-parallel inputs;

wherein a first of said N segments is provided to the inner product calculator for processing with each of said blocks prior to providing a second of said N segments to the inner product calculator for processing with any of said blocks.

2. The parallel correlator of claim 1, wherein the sample-parallel output of the data memory defines a first input to the inner product calculator and the sample-parallel output of the segmented code register defines a second input to the inner product calculator.

3. The parallel correlator of claim 1, further comprising a Doppler memory, the Doppler memory having a sample-sequential input and a sample-parallel output, said Doppler memory organizing the sample-sequential input into blocks of n sequential samples and providing each of said Doppler memory blocks cyclically as the sample-parallel output to said inner product calculator.

4. The parallel correlator of claim 3, wherein the sample-sequential input to the Doppler memory defines an inner product of samples from a Doppler sequence, a Data sequence and a code sequence.

5. The parallel correlator of claim 3, wherein the sample-parallel output of the Doppler memory defines a third input the inner product calculator.

6. The parallel correlator of claim 1, further comprising a post-correlation memory for storing and accumulating the inner product of the two sample-parallel inputs received from the inner product calculator.

7. The parallel correlator of claim 1, further comprising a post-correlation processor for coherent and non-coherent processing of the inner product.

8. The parallel correlator of claim 1, wherein each of said samples further comprises an in-phase component and a quadrature component.

9. The parallel correlator of claim 1, wherein the parallel correlator is adapted to process an in-phase component of a received signal in parallel with a quadrature component of the received signal.

10. The parallel correlator of claim 1, wherein ,the segmented-serial input defines an accelerated input to the segmented code register as compared to the sample-serial input.

11. The parallel correlator of claim 1, wherein the segmented code register is adapted to circularly shift the sample by one sample per clock cycle.

12. The parallel correlator of claim 1, wherein the segmented code register receives a new input sample per clock cycle.

13. The parallel correlator of claim 1, wherein the data memory is adapted to receive one sample as input and outputs a block of n sequential samples per clock cycle.

14. A parallel correlator comprising:

a data memory having a sample-sequential input and a sample-parallel output, said data memory organizing the sample-sequential input into blocks of n sequential samples and providing each of said blocks cyclically to said sample-parallel output;

a Doppler memory having a sample-sequential input and a sample-parallel output, said Doppler memory organizing the sample-sequential input into blocks of n sequential samples and providing each of said Doppler memory blocks cyclically to said sample-parallel output;

a segmented code register organized to receive a code sequence as a plurality of input samples, said segmented code register organizing the input samples into N segments of L length, wherein N is less than n and greater than one;

the segmented code register configured to store the input samples in their order of input and to forward shift or backward shift the registered samples on each clock cycle prior to parallel output, said forward shift shifting the registered samples by one sample position and the backward shift shifting the registered samples by one segment of samples;

said segmented code register having a sample parallel output; and

an inner product calculator having three sample-parallel inputs, said inner product calculator having one output representing the inner product of the three sample-parallel inputs, wherein a first of said N segments is provided to the inner product calculator for processing with each of said blocks and Doppler memory blocks prior to providing a second of said N segments to the inner product calculator for processing with any of said blocks or Doppler memory blocks.

15. The parallel correlator of claim 14, wherein the sample-parallel output of the data memory and the sample-parallel output of the Doppler memory and the sample-parallel output of the segmented code register define the three sample-parallel inputs of the inner product calculator.

16. The parallel correlator of claim 14, further comprising a post-correlation memory for storing and accumulating the inner product of the three sample-parallel inputs from the inner product calculator.

17. The parallel correlator of claim 14, further comprising a post-correlation processor for coherent and non-coherent processing of the inner product.

18. The parallel correlator of claim 14, wherein each of said samples further comprises an in-phase component and a quadrature component.

19. The parallel correlator of claim 14, wherein the parallel correlator is adapted to process an in-phase component of a received signal in parallel with a quadrature component of the received signal.

20. The parallel correlator of claim 14, wherein the segmented code register receives the code segments as a segmented serial input and the segmented-serial input defines an accelerated input to the segmented code register as compared to a sample-serial input.

21. The parallel correlator of claim 14, wherein the segmented Code register is adapted to circularly shift the sample by one sample per clock cycle.

22. The parallel correlator of claim 14, wherein the segmented Code register receives a new input sample per clock cycle.

23. A method of segmented correlation comprising:

providing a data memory for receiving a sample-sequential input and providing a sample-parallel output, the data memory organizing the sample serial input into blocks of n sequential samples and providing each of said blocks cyclically to said sample-parallel output;

providing a segmented code register organized to receive a code sequence as a plurality of input samples said segmented code register organizing the input samples into N segments of L length, wherein N is less than n and greater than one, the segmented code register storing the input samples in an order of input and one of forward- or backward-shifting the registered samples on each clock cycle prior to parallel output, the forward-shifting shifting the registered samples by one sample position and the backward-shifting shifting the register samples by one segment of samples per clock cycle;

said segmented code register having a sample parallel output; and

correlating the output from the segmented code register with the sample serial output from the data memory to provide a correlation result representing the inner product of the data memory and the segmented code register;

wherein a first of said N segments is correlated with each of said blocks prior to correlating a second of said N segments with any of said blocks.

24. The method of claim 23, further comprising providing a Doppler memory having a sample-sequential input and a sample-parallel output, said Doppler memory organizing the sample-sequential input into blocks of n sequential samples and providing each of said Doppler memory blocks cyclically as the sample-parallel output for correlation.

25. The method of claim 24, wherein the Doppler memory defines an inner product of samples from each of a Doppler sequence, a data sequence and a code sequence.

26. The method of claim 23, wherein the sample-parallel output of the Doppler memory defines a third input into the inner product calculator.

27. The method of claim 23, further comprising providing a post-correlation memory for storing and accumulating the inner product of the two sample-parallel inputs from the inner product calculator.

28. The method of claim 23, further comprising providing a post-correlation processor for coherent and non-coherent processing.

29. The method of claim 23, wherein each of said samples further comprises an in-phase component and a quadrature component.

30. The method of claim 23, wherein the step of correlating the segmented sample output from the segmented code register with the sample serial output from the data memory further comprises correlating an in-phase component of a received signal in parallel with a quadrature component of the received signal.

31. The method of claim 23, further comprising the step of receiving a new input sample at the code register per each clock cycle.

32. A method for segmented correlation, comprising:

providing a data memory for receiving a sample-sequential input and providing a sample-parallel output, the data memory organizing the sample serial input into blocks of n sequential samples and providing each of said blocks cyclically to said sample-parallel output;

providing a Doppler memory for receiving a sample-sequential input and providing a sample-parallel output, the Doppler memory organizing the sample serial input into blocks of n sequential samples;

providing a segmented code register organized to receive a code sequence as a plurality of input samples, said segmented code register organizing the input samples into N segments of L length, wherein N is less than n and greater than one, the segmented code register storing the input samples in an order of input and one of forward- or backward-shifting the registered samples on each clock cycle prior to parallel output, the forward-shifting shifting the registered samples by one sample position and the backward-shifting shifting the register samples by one segment of samples per clock cycle;

said segmented code register having a sample parallel output and

correlating the segmented sample output from the segmented code register with the sample serial output from the data memory and the Doppler memory to provide a an inner product result;

wherein a first of said N segments is correlated with each of said blocks and Doppler memory blocks prior to correlating a second of said N segments with any of said blocks and Doppler memory blocks.

33. The method of claim 32, wherein the sample-parallel output of the data memory, the sample-parallel output of the Doppler memory and the sample-parallel output of the segmented code register define the three sample-parallel inputs of the inner product calculator.

34. The method of claim 32, further comprising storing the inner product result in a post-correlation memory.

35. The method of claim 32, further comprising processing the inner product result to define a coherent or a non-coherent result.

36. The method of claim 32, wherein each of said samples further comprises an in-phase component and a quadrature component.

37. The method of claim 36, further comprising processing the in-phase component of the received signal in parallel with the quadrature component of the received signal.

38. The method of claim 32, further comprising the step of receiving a new input sample at the segmented code register per each clock cycle.

39. A machine-readable medium having stored thereon a plurality of executable instructions to be executed by a processor to conduct segmented correlation method, the method comprising:

receiving a first signal and organizing sampled elements representing said first signal into a plurality of blocks each having n sequential first samples;

receiving a second signal and organizing sampled elements representing said second signal as N segments of L length, wherein N is less than n and greater than one;

cross-correlating the n sequential first samples with a first of said N segments at first clock cycle;

circularly forward-shifting the first N segment by one sample and cross-correlating the shifted first N segment with n sequential first samples at second clock cycle;

repeating the step of circularly forward-shifting the first N segment for P clock cycles; and

circularly backward-shifting the first N segment by L elements after P+1 clock cycles;

wherein the first N segment is cross-correlated with the n sequential first samples of each of the plurality of blocks prior to cross-correlating another of the N segments with any of the plurality of blocks.

40. The machine readable medium of claim 39, wherein the step of receiving a first signal further comprises retrieving the first signal from memory.

41. The machine readable medium of claim 39, wherein the step of receiving and organizing samples elements is implemented in a memory device.

42. The machine readable medium of claim 41, wherein the memory device is a Random Access Memory.

43. The machine readable medium of claim 39, wherein the step of receiving a first signal further comprises storing the received signal in a memory.

44. The machine readable medium of claim 39, wherein the step of receiving a first signal further comprises storing the sampled elements representing said first signal in a memory.

45. The machine readable medium of claim 39, the clock cycle is generated by a second processor.

46. The machine readable medium of claim 39, each sampled elements further comprise I- and Q-phase components.

47. The machine readable medium of claim 46, wherein the I- and Q-phase components are processed simultaneously.

48. The machine readable medium of claim 46, wherein the I- and Q-phase components are processed in parallel.

49. The machine readable medium of claim 39, wherein L is equal to P+1 sampled elements.

50. The machine readable medium of claim 39, wherein L is equal to P sampled elements.

51. The machine readable medium of claim 39, further comprising the step of receiving and organizing a new first signal after P+1 clock cycles.

52. The machine readable medium of claim 39, further comprising the step of storing each cross-correlation result in a post-correlation memory.

53. The machine readable medium of claim 39, wherein the step of receiving a first signal further comprises receiving one sampled element per clock cycle.

54. The machine readable medium of claim 39, wherein the step of receiving further comprises receiving a group of samples per clock cycle.