Parallel frequency searching in an acquisition correlator

• US 6,466,958 B1
• Filed: 09/12/2000
• Issued: 10/15/2002
• Est. Priority Date: 09/12/2000
• Status: Active Grant

• Current Assignee: L-3 Communications Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Interstate Electronics Corp. (L3Harris Technologies, Inc.)
• Inventors: McKenney, Michael F., Van Wechel, Robert J.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/659,517
• Time in Patent Office: 763 Days
• Field of Search: 708/422, 375/142, 375/143, 375/150, 375/152
• US Class Current: 708/422
• 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/29 carrier including Doppler, related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/37 Hardware or software details of the signal processing chain
• CPC Class Codes: G06F 7/4812 Complex multiplication
• CPC Class Codes: G06F 7/4818 using coordinate rotation digital computer [CORDIC]

Abstract

An apparatus and method allow receivers to quickly acquire a pseudorandom noise signal. A receiver advantageously detects frequency shifts using a compact parallel process hardware implementation of a Discrete Fourier Transform (DFT). The simultaneous detection of multiple frequencies allows the receiver to search the frequency range of the transmitted signal in larger increments of frequency, thereby increasing the speed of acquisition. One receiver does not use coherent integration before computation of the transform and advantageously maintains a flat frequency response. The flat frequency response of the DFT circuit enables searching of multiple frequency offsets without CPU intensive processing to compensate for frequency response variations. A receiver can include a Doppler correction circuit, which permits correlation data with frequency shift in the code to be non-coherently integrated among relatively fewer addresses or tap positions in memory.

Claims

1. A correlation circuit for acquiring a pseudorandom noise (PN) code signal, the correlation circuit comprising:

a digital matched filter adapted to receive a reference code, a first detected code, and a second detected code, the digital matched filter shifting the first and second detected codes along a first and a second shift register, the first and second shift registers containing taps such that a comparison circuit compares the reference code to the first and second code as accessed through the taps, the comparison circuit generating a first output and a second output where the first output peaks when the first detected code substantially matches the reference code and where the second output peaks when the second detected code substantially matches the reference code;

a Coordinate Rotation Digital Computer (CORDIC) phase rotator circuit adapted to receive the first and second outputs of the digital matched filter, where the first and second outputs of the digital matched filter are represented as x and y components of a sequence of vectors in a complex plane, the CORDIC phase rotator circuit performing a rotation to the sequence of vectors such that the rotation results in a complex multiplication to the sequence of vectors in a Discrete Fourier Transform (DFT);

a first coherent memory adapted to receive a real part of the complex multiplication result from the CORDIC phase rotator circuit, the first coherent memory further adapted to relate the complex multiplication result to an address in the first coherent memory where the address corresponds to a position of a tap in the digital matched filter where the tap position indicates a relative position of the first detected code within the digital matched filter; and

a second coherent memory adapted to receive an imaginary part of the complex multiplication result from the CORDIC phase rotator circuit, the second coherent memory relating the complex multiplication result to an address in the second coherent memory where the address corresponds to a position of a tap in the digital matched filter where the tap position indicates a relative position of the second detected code within the digital matched filter.

2. The correlation circuit as defined in claim 1, further including an integration circuit, the integration circuit adapted to accumulate the real part of the complex multiplication result with a content of the first coherent memory related to the tap position and accumulate the imaginary part of the complex multiplication result with a content of the second coherent memory related to the tap position.

3. The correlation circuit as defined in claim 2, wherein the CORDIC phase rotator circuit further includes a quadrant rotating circuit which rotates the vector in the CORDIC by an integer multiple of 90 degrees.

4. The correlation circuit as defined in claim 2, wherein the CORDIC phase rotator comprises a plurality of CORDIC phase rotators, the first coherent memory comprises a first plurality of coherent memories, the second coherent memory comprises a second plurality of coherent memories, where the plurality of CORDIC phase rotators rotate the outputs of the digital matched filter in a DFT manner, and where at least one CORDIC phase rotator from the plurality of CORDIC phase rotators changes angles at a rate that is different from a rate at which the other CORDIC phase rotators change angles such that the at least one CORDIC phase rotator performs a DFT computation at a different frequency than the other CORDIC phase rotators.

5. The correlation circuit as defined in claim 1, wherein a number of taps of the first shift register and a number of memory addresses for the first coherent memory are equal.

6. The correlation circuit as defined in claim 1, where the first coherent memory and the second coherent memory are combined into one memory.

7. The correlation circuit as defined in claim 1, where the CORDIC phase rotator computes a plurality of rotations with a plurality of outputs, the correlation circuit further comprising an angle selector adapted to receive the plurality of outputs and to select the output with a phase characteristic that corresponds to an integer multiple of 90 degrees of the DFT multiplication, the angle selector further adapted to rotate the selected output by the integer multiple of 90 degrees so that the rotated selected output corresponds to the DFT multiplication.

8. The correlation circuit as defined in claim 1, further comprising:

a magnitude detection circuit adapted to retrieve a first content from the first coherent memory and a second content from the second coherent memory, the first content and the second content related to the same tap, the magnitude detection circuit computing a magnitude output predictably related to the magnitude of a vector defined by the first content and the second content where the magnitude is a square root of the sum of the squares of the first content and the second content; and

a non-coherent integration memory adapted to receive and accumulate the magnitude output of the magnitude detection circuit where the non-coherent integration accumulates the magnitude output with a content of the non-coherent memory at an address of the non-coherent memory related to the tap position and a frequency of the DFT computation corresponding to the magnitude output.

9. The correlation circuit as defined in claim 8, wherein the non-coherent integration memory comprises a plurality of non-coherent integration memories, where the plurality of non-coherent integration memories are coupled to at least one magnitude detection circuit such that contents of the plurality of non-coherent integration memories relate to magnitudes of the contents of the first and second pluralities of coherent memories, the correlation circuit further comprising a peak detector coupled to the plurality of non-coherent integration memories, the peak detector adapted to retrieve the contents of the non-coherent integration memories, compare the contents of the non-coherent integration memories to a predetermined threshold, and provide an indication when at least one content from the contents of the non-coherent integration memories exceeds the predetermined threshold.

10. The correlation circuit as defined in claim 8, wherein the non-coherent integration memory further comprises:

a counter adapted to provide a count related to an accumulated number of tap positions by which a code signal with a frequency offset has shifted relative to a time index signal; and

an adder circuit adapted to apply the time index signal to the counter output and use the result to address the non-coherent integration memory.

11. The correlation circuit as defined in claim 8, further comprising:

an offset occurrence circuit adapted to receive a clock signal and to provide an indication with a period related to an inverse of a product of a frequency computation associated with the at least portion of the non-coherent integration memory;

a counter circuit adapted to accumulate indications provided by the offset occurrence circuit, where an output of the counter circuit is termed a time offset signal; and

an adder circuit adapted to sum a time index signal with the time offset signal, where the time index signal relates to a memory address with no code drift, where an output of the adder circuit is applied to the address of the non-coherent integration memory such that a memory location indicated by the output of the adder circuit is synchronized with the code.

12. The correlation circuit as defined in claim 1, wherein the CORDIC phase rotator further comprises:

a first rotation circuit, where the first rotation circuit rotates a vector from the sequence of vectors by a first angle, where an absolute value of the first angle is defined by an arctangent of a first power of 2; and

a second rotation circuit coupled to an output of the first rotation circuit, where the second rotation circuit rotates the output of the first rotation circuit in two separate rotations, where the two separate rotations rotate in opposite directions, where the two separate rotations are further characterized by having an angle of rotation with an absolute value defined by an arctangent of a second power of 2, where the second power of 2 is one less than the first power of 2.

13. The correlation circuit as defined in claim 1, further comprising:

an integrate and dump control circuit adapted to sequence the start of the first coherent integration memory and the second coherent integration memory and to sequence the outputs of the first coherent integration memory and the second coherent integration memory in a sequential manner, where the integrate and dump control circuit is configured to reset a memory location after the memory location has been accessed; and

a multiplexer circuit coupled to the first coherent integration memory and to the second coherent integration memory, where the multiplexer circuit is configured to select between an output of the first coherent integration memory and an output of the second coherent integration memory based on which output is outputting data.

14. A method for detecting correlation in a spread spectrum pseudorandom noise receiver, the method comprising:

comparing a first detected code and a second detected code to a reference code and generating a first output and a second output in a digital matched filter, where the first and second outputs are respective summations of comparisons between the first detected code and the reference code and comparisons between the second detected code and the reference code;

generating a product by multiplying a first number by a second number, where the first number is defined by the first output and the second output where the first output corresponds to a real part of the first number and the second output corresponds to an imaginary part of the first number, and where the second number corresponds to an e<sup>jω

T</sup> term from a DFT computation; and

maintaining the product of the multiplication such that products of multiplies pertaining to a tap in the digital matched filter are identifiably maintained separately from products of multiplies of other taps.

15. The method as defined in claim 14, wherein the multiplying is performed in accordance with a Coordinate Rotation Digital Computer (CORDIC) algorithm.

16. The method as defined in claim 14, further comprising accumulating the product of the multiplication with a further product of multiplies where the product and the further product are related to the tap in the digital matched filter.

17. The method as defined in claim 16, further comprising:

converting the accumulated product of the multiplication into a scalar value representing a magnitude of the accumulated product;

generating an accumulation by accumulating the scalar value with other scalar values where the scalar value and the other scalar values are related by the tap position in the digital matched filter and frequency of the DFT computation; and

storing the accumulation in a collection of elements.

18. The method as defined in claim 17, further comprising:

searching the collection;

comparing the elements of the collection to a predetermined threshold; and

providing an indication when an element of the collection is at least as high as the predetermined threshold.

19. The method as defined in claim 18, further comprising:

receiving a time index signal, where the time index signal relates to addresses of elements of the collection;

receiving an offset signal, where the offset signal is approximately related to an inverse of a product of a frequency computation associated with the collection and a number of elements per code chip;

applying the time index signal to the time offset signal to generate a compensated signal;

applying the compensated signal to the collection to retrieve a first accumulation;

summing the first accumulation with a sample to generate a second accumulation; and

storing the second accumulation in the collection to correct for code drift in the collection.

20. The method as defined in claim 17 wherein the collection of elements is an addressable memory device.

21. The method as defined in claim 14, further comprising:

simultaneously generating multiple products of the first number and the second number;

maintaining the multiple products in Cartesian coordinate form as the multiple products are generated and rotate in a complex plane;

generating the multiple products by rotating the first number in a series of stages, where a second stage rotates a result of a first stage by an angle where an absolute value of the angle is an arctangent of a power of 2, wherein the power of 2 for the second stage is one less than the power of 2 for the first stage; and

calculating, in the second stage, both positive and negative rotations of a multiplicand such that more than one multiplication product is computed.

22. The method as defined in claim 14, wherein the DFT computation further comprises:

maintaining multiple periods of the first output and the second output of the digital matched filter in a collection;

reading data from the collection in an order such that the data is extracted from a common point within a period;

multiplying the data in accordance with a DFT algorithm; and

accumulating the multiplied data.

23. A correlation circuit for acquiring a pseudorandom noise (PN) code signal, the correlation circuit comprising:

a comparison circuit;

a digital matched filter adapted to receive a reference code, a first detected code, and a second detected code, the digital matched filter shifting the first and second detected codes through a first and a second shift register, the first and second shift registers containing taps such that the comparison circuit compares the reference code to the first and second code as accessed through the taps, the comparison circuit generating a first output and a second output where the first output peaks when the first detected code substantially matches the reference code and the second output peaks when the second detected code substantially matches the reference code;

a multiplier circuit adapted to receive the first and second outputs of the digital matched filter, where the multiplier circuit computes a plurality of complex multiplication products of a complex number defined by the first and second output, the plurality of products spanning a first angular range relative to the complex number defined by the first and second output;

an angle selector coupled to the multiplier circuit, where the angle selector receives the plurality of products and is adapted to select the product from the plurality of products with the rotation that corresponds to an angle indicated by a DFT computation;

a first coherent integration memory adapted to receive and accumulate real parts of the complex multiplication result from the multiplier circuit, the first coherent integration memory relating the complex multiplication result to an address in the first coherent integration memory, where the address in memory corresponds to a position of a tap in the digital matched filter, where the tap position indicates a relative position of the first detected code within the digital matched filter, the first coherent integration memory further accumulating real parts of the complex multiplication products with a content of the first coherent integration memory at the memory address indicated by the tap position; and

a second coherent integration memory adapted to receive and accumulate imaginary parts of the complex multiplication products from the multiplier circuit, the second coherent integration memory relating the complex multiplication products to an address in the second coherent integration memory, where the address corresponds to a position of a tap in the digital matched filter, where the tap position indicates a relative position of the first detected code within the digital matched filter, the second coherent integration memory further accumulating the imaginary parts of the complex multiplication products with a content of the second coherent integration memory at the memory address indicated by the tap position.

24. The correlation circuit as defined in claim 23, wherein the first range is approximately 90 degrees.

25. The correlation circuit as defined in claim 23, wherein the angle selector selects a product from the plurality of products corresponding to an integer multiple of 90 degrees of the angle indicated by a DFT computation, and is further adapted to rotate the selected product by the integer multiple of 90 degrees so that the rotated selected output corresponds to the DFT computation.

26. The correlation circuit as defined in claim 23, wherein the multiplier circuit is implemented with a Coordinate Rotation Digital Computer (CORDIC).

27. The correlation circuit as defined in claim 23, further comprising an input memory circuit between the digital matched filter and the multiplier circuit, wherein the input memory circuit stores sequences of data from the first and second outputs of the digital matched filter such that after the data has been stored in the input memory circuit, the multiplier circuit can access the data by tap.

28. The correlation circuit as defined in claim 27, wherein the first coherent integration memory and the second coherent integration memory comprise one register per tap.

29. The correlation circuit as defined in claim 23, further comprising:

a magnitude detection circuit adapted to retrieve a first content from the first coherent memory and to retrieve a second content from the second coherent memory, the first content and the second content related to the same tap, the magnitude detection circuit computing a magnitude output predictably related to the magnitude of a vector defined by the first content and the second content; and

a non-coherent integration memory adapted to receive and accumulate the magnitude output of the magnitude detection circuit, where the non-coherent integration accumulates the magnitude output with a content of the non-coherent memory at an address of the non-coherent memory related to the tap position and to a frequency of the DFT computation corresponding to the magnitude output.

30. The correlation circuit as defined in claim 23, further comprising a peak detector coupled to the plurality of non-coherent integration memories, the peak detector adapted to retrieve the contents of the non-coherent integration memories, to compare the contents of the non-coherent integration memories to a predetermined threshold, and to provide an indication when at least one content from the contents of the non-coherent integration memories exceeds the predetermined threshold.

31. A method for detecting correlation in a spread spectrum pseudorandom noise receiver, the method comprising:

comparing first and second detected codes to a reference code;

generating a first output and a second output in a digital matched filter, where the first and second outputs are respective summations of comparisons between the first detected code and the reference code and comparisons between the second detected code and the reference code, and where the first output corresponds to a real part of a number and the second output corresponds to an imaginary part of a number;

storing the first and second outputs;

retrieving the first and second outputs in an order such that a series of first and second outputs corresponding to data from a common tap is retrieved;

generating a plurality of products by multiplying the first and second outputs in the complex domain by a plurality of multipliers, where the plurality of multipliers rotate the first and second outputs in a first range in the complex plane;

selecting a product from the plurality of products that corresponds to a phase of a DFT product; and

accumulating the plurality of products of the multiplication such that an accumulation of products of multiplies pertaining to a first tap in the digital matched filter is identifiably maintained separately from an accumulation of products of a second tap.

32. The method as defined in claim 31, wherein the multiplying is performed in accordance with a Coordinate Rotation Digital Computer (CORDIC) algorithm.

33. The method as defined in claim 31, where the first range is 90 degrees.

34. The method as defined in claim 31, further comprising:

converting the accumulation of products of the multiplication into a scalar value representing a magnitude of the accumulated product;

accumulating the scalar value with other scalar values, where the scalar value and the other scalar values are related to a time indicated by the first tap in the digital matched filter and to a frequency of a DFT corresponding to the selected product; and

storing a result of accumulating the scalar values and the other scalar values in a first collection.

35. The method as defined in claim 34, further comprising:

searching the first collection;

comparing entries in the first collection to a predetermined threshold; and

providing an indication when an entry of the first collection is at least as high as the predetermined threshold.

36. A circuit useful for acquiring a pseudorandom noise (PN) code signal, the correlation circuit comprising:

means for comparing a first detected code and second detected code to a reference code and for generating first and second outputs, where the first and second outputs are respective summations of a comparison between the first detected code and the reference code and a comparison between the second detected code and reference code;

means for multiplying a first number defined by the first and second outputs in the complex domain by a second number, where the first output corresponds to a real part of the first number and the second output corresponds to an imaginary part of the first number, where the second number is a term from a DFT computation;

means for converting the product of the multiplication of the first number and the second number into a scalar value representing a magnitude of the product; and

means for searching a collection of products, comparing elements of the collection to a predetermined threshold, and providing an indication when an element of the collection is at least as high as the predetermined threshold.

37. The circuit as defined in claim 36, wherein the means for multiplying is a Coordinate Rotation Digital Computer (CORDIC) rotator.