System and method for synchronizing digital bits in a data stream

• US 8,121,238 B2
• Filed: 10/27/2006
• Issued: 02/21/2012
• Est. Priority Date: 06/30/2006
• Status: Expired due to Fees

• Current Assignee: CSR Technology Incorporated (Qualcomm, Inc.)
• Original Assignee: CSR Technology Incorporated (Qualcomm, Inc.)
• Inventors: Raman, Sundar, Brown, James M.
• Primary Examiner(s): Payne, David C.
• Assistant Examiner(s): PANWALKAR, VINEETA S
• Application Number:
  US11/553,983
• Publication Number:
  US 20080002797A1
• Time in Patent Office: 1,943 Days
• Field of Search: 375/130, 375/140, 375/142, 375/145, 375/147, 375/149, 375/150, 375/316, 375/340, 375/343, 375322-326, 375/354, 375/359, 375/360, 375/362, 375/365, 375/367, 370/498, 370/503, 713/400, 713/401, 713/500, 708/1, 708/3, 708/5, 708/100, 708/200, 708/207, 708/422, 708/800, 708/801, 708/813, 704/200, 704/201, 704/211, 704/216, 704/218, 704/231, 704/326, 704/237, 704/258, 704/263
• US Class Current: 375/355
• 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/30 code related G01S19/246 takes precedence
• CPC Class Codes: H04B 1/7075 with code phase acquisition
• CPC Class Codes: H04B 2201/70715 with application-specific features

Abstract

A system and method for synchronizing a receiver of a bit stream to the bit stream include a correlator to remove the PN code modulation and to generate a stream of time sequence values (samples) from the received bits. A plurality of accumulators are included, each accumulator corresponding to an offset in a series of time intervals starting with a first time period. The accumulators add a number of values equal to a number of samples in a bit period. The values added by each accumulator is a set of values starting with the value at the offset corresponding to the accumulator. A plurality of magnitude calculators receives a sum from the corresponding accumulator and calculates a magnitude. A plurality of non-coherent summers are then used to add the magnitudes for each offset in each bit period for all of the received bits. The total sum in each non-coherent summer is then analyzed to find the highest value, such that the offset corresponding to the non-coherent summer with the highest value represents the location of the bit transition in the bit period.

Claims

1. A method for synchronizing a receiver of a bit stream to the bit stream comprising:

selecting a finite sample of N received bits, the bits having a bit period of T units of time;

generating a time sequence stream of values representing the N received bits sampled with a sample period of S units of time, where S is an integer sub-multiple of T;

generating a correlated sequence of values by correlating the time sequence stream of values with a known time sequence stream of values;

selecting a first sample period in the correlated sequence and defining a cycle of X offsets from the first sample period, where X=T/S−

1, each offset representing a sample period that is a number of sample periods away from the first sample period, each offset corresponding to one of the values from the correlated sequence of values;

initializing Y accumulators, where Y is less than or equal to T/S, a first accumulator corresponding to a zero offset representing the first sample period, the remaining accumulators each corresponding to one of the X offsets;

starting with a first value at the offset corresponding to each accumulator, summing in each accumulator corresponding to the offset, each value at each sample period at each offset until values at X subsequent offsets have been summed to the first value;

calculating a magnitude for each sum of values in each of the Y accumulators;

adding the magnitude to a sum of magnitudes in each of Y non-coherent summers corresponding to each offset;

repeating the steps of summing in each accumulator, calculating the magnitude, and adding the magnitudes until samples for all N bits have been summed; and

defining a main peak location as the offset corresponding to the non-coherent summer having the highest sum of magnitudes.

2. The method of claim 1 further comprising:

calculating a probability of transition; and

applying a bit synchronization analysis method to determine if the bit transition location passes or fails.

3. The method of claim 2 where the bit synchronization analysis method comprises:

generating an array of peak values from at least a set of the Y sums of magnitudes where a plot of the peak values against the offsets corresponding to each peak shows the largest magnitude forming a main peak between peaks on either side of the main peak and substantially linear patterns formed by the peaks right and left of the main peak;

generating a right line by a first order curve fit using at least one peak to the right of the main peak and the main peak, the right line having a right slope and a right intercept;

generating a left line by a first order curve fit using at least one peak to the left of the main peak and the main peak, the left line having a left slope and a left intercept;

identifying a predicted peak by identifying an intersection point on a timeline formed by the offsets at which the right line intersects the left line; and

providing indication that the main peak location passes if the intersection point is within a predefined interval around the main peak location.

4. The method of claim 3 where the array of peak values is generated as an ordered set of peak values, the first element in the array containing the main peak, the second element in the array containing the second highest peak value, the third element in the array containing the third highest peak value, and so on for all of the elements in the array, the method further comprising:

testing the sums of magnitudes by;

determining if the second and third highest peak values are valid peaks by checking if the second and third highest peak values correspond to the sums of magnitudes one offset to the right and left of the offset corresponding to the main peak;

determining if the fourth and fifth highest peak values are valid peaks by checking if the fourth and fifth highest peak values correspond to the sums of magnitudes two offsets to the right and left of the offset corresponding to the main peak;

determining if the sixth and seventh highest peak values are valid peaks by checking if the sixth and seventh highest peak values correspond to the sums of magnitudes three offsets to the right and left of the offset corresponding to the main peak;

if only the second and third peaks are valid peaks, selecting a two-point bit synchronization analyzer method that uses one peak to the right of the main peak and the main peak to define a right slope of the right line and one peak to the left of the main peak and the main peak to define a left slope of a left line;

if only the second, third, fourth and fifth peaks are valid peaks, selecting a four-point bit synchronization analyzer method that uses two peaks to the right of the main peak to generate the right line and two peaks to the left of the main peak to generate the left line; and

if the second, third, fourth, fifth, sixth and seventh peaks are valid peaks, selecting a six-point bit synchronization analyzer method that uses three peaks to the right of the main peak to generate the right line and three peaks to the left of the main peak to generate the left line.

5. The method of claim 4 wherein, if the two point bit synchronization analyzer method is used, performing the steps of:

calculating a slope of the right line;

calculating a slope of the left line;

calculating the probability of transition using;

probability of transition=5*(slope of left line+slope of light line)/main peak; and

comparing the probability of transition with a minimum probability.

6. The method of claim 3 wherein before performing the bit synchronization analysis, performing the steps of:

calculating a probability of bit transition; and

performing the bit synchronization analysis if the probability of bit transition is greater than a minimum probability.

7. The method of claim 3 wherein before performing the bit synchronization analysis, performing the steps of:

calculating a number of bit transitions using;

No. bit transitions=p_trans*T(elapsed)secs.*50 bps;

measuring a carrier to noise level (C/N_o) and calculating a minimum number of transitions based on the C/N₀.

8. The method of claim 2 where the bit synchronization analysis method comprises:

generating an array of peak values from at least a set of the Y sums of magnitudes where a plot of the peak values against the offsets corresponding to each peak shows the largest magnitude forming a main peak between peaks on either side of the main peals and substantially linear patterns formed by the peaks right and left of the main peak;

generating a second array of peak values by;

calculating an average difference, DIFF_AVE, between the main peak and each peak value in the array of peak values;

generating a set of ideal right peaks using;

peak_right_n=main peak−

n*DIFF_AVE, where n=an integer number of offsets from the main peak offset;

generating a set of ideal left peaks using;

peak_left_n=main peak−

n*DIFF_AVE, where n=an integer number of offsets from the main peak offset greater than 1;

calculating a sum of the differences, DIFF·

_SUM, using;

Diff_Sum=(right_—

1−

peak_right_—

1)+(right_—

2−

peak_right_—

2)+ . . . +(right_n−

peak_right_n)+(left_—

1−

peak_left_—

1)+(left_—

2−

peak_left_—

2)+ . . . +(left_n−

peak_n), where right_n is the peak value n offsets to the right of the main peak and left_n is the peak value n offsets to the left of the main peak;

calculating a sum of squares, SUM_SQ, using;

9. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 1.

10. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 2.

11. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 3.

12. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 1 where the bit period T=20 ms, the sample period S=1 ms, X=20, and Y=20.

13. A system for synchronizing a receiver of a bit stream to the bit stream comprising:

a correlator to generate a correlated sequence of values by correlating a time sequence stream of values from a finite sample of received bits with a known sequence stream of values,

a plurality of offset accumulators, each corresponding to an offset in a series of time intervals within the correlated sequence, starting with a first time period, the accumulators operable to add a number of values equal to a number of samples in a bit period, the number of values added by each accumulator being a set of values in the correlated sequence starting with the value at the offset corresponding to the accumulator;

a plurality of magnitude calculators, each corresponding to one of the offsets, operable to receive a sum from the corresponding accumulator, and to calculate a magnitude; and

a plurality of non-coherent summers each corresponding with one of the offsets, the non-coherent summers operable to add the magnitudes received for each offset in each bit period for all of the N bits, the total sum of magnitudes in each non-coherent summer being analyzed for the highest sum of magnitudes, such that the offset corresponding to the non-coherent summer with the highest sum of magnitudes represents the location of the bit transition in the bit period.

14. The system of claim 13 further comprising a bit synchronization analyzer to analyze the sums of magnitudes in the non-coherent summers to determine whether the location of the bit transition was correctly determined.

15. The system of claim 14 where the bit synchronization analyzer includes hardware and/or software components programmed to perform steps of:

generating an array of peak values from at least a set of the Y sums of magnitudes where a plot of the peak values against the offsets corresponding to each peak shows the largest magnitude forming a main peak between peaks on either side of the main peak and substantially linear patterns formed by the peaks right and left of the main peak;

generating a right line by a first order curve fit using at least two peaks to the right of the main peak, the right line having a right slope and a right intercept;

generating a left line by a first order curve fit using at least two peaks to the left of the main peak, the left line having a left slope and a left intercept;

identifying a predicted peak by identifying an intersection point on a timeline formed by the offsets at which the right line intersects the left line, and

indicating that the main peak location passes if the intersection point is within a peak offset time limit of the main peak location.

16. The system of claim 14 where the bit synchronization analyzer includes hardware and/or software components programmed to perform steps of:

generating an array of peak values from at least a set of the Y sums of magnitudes where a plot of the peak values against the offsets corresponding to each peak shows the largest magnitude forming a main peak between peaks on either side of the main peak and substantially linear patterns formed by the peaks right and left of the main peak;

generating a second array of peak values by;

calculating an average difference, DIFF_AVE, between the main peak and each peak value in the array of peak values;

generating a set of ideal right peaks using;

peak_right.sub_n=main peak−

n*DIFF_AVE, where n=an integer number of offsets from the main peak offset;

generating a set of ideal left peaks using;

peak_left_n=main peak−

n*DIFF_AVE, where n=an integer number of offsets from the main peak offset greater than 1;

calculating a sum of the differences, DIFF_SUM, using;

Diff_Sum=(right_—

1−

peak_right_—

1)+(right_—

2−

peak_right_—

2)+ . . . +(right_n−

peak_right_n)+(left_—

1−

peak_left_—

1)+(left_—

2−

peak_left_—

2)+ . . . +(left_n−

peak_left_n), where right_n is the peak value n offsets to the right of the main peak and left_n is the peak value n offsets to the left of the main peak;

calculating a sum of squares, SUM_SQ, using;

17. A method for synchronizing a receiver of a bit stream to the bit stream comprising:

selecting a finite sample of N received bits, the bits having a bit period of T units of time;

generating a correlated sequence of values by correlating a time sequence stream of values representing the N received bits, with a known time sequence stream of values, wherein the time sequence stream of values is sampled with a sample period of S units of time, where S is an integer sub-multiple of T;

selecting a first sample period in the correlated sequence and defining a cycle of X offsets from the first sample period, where X=T/S−

1, each offset representing a sample period that is a number of sample periods away from the first sample period, each offset corresponding to one of the values from the correlated sequence;

initializing Y accumulators, where Y less than or equal to T/S, a first accumulator corresponding to a zero offset representing the first sample period, the remaining accumulators each corresponding to one of the X offsets;

starting with a first value at the offset corresponding to each accumulator, summing in each accumulator corresponding to the offset, each value at each sample period at each offset until values at X subsequent offsets have been summed to the first value;

calculating a power magnitude for each sum of values in each of the Y accumulators;

adding the power magnitude to a sum of power magnitudes in each of Y non-coherent summers corresponding to each offset;

repeating the steps of summing in each accumulator, calculating the power magnitude, and adding the power magnitudes until samples for all N bits have been summed; and

defining a main peak location as the offset corresponding to the non-coherent summer having the highest sum of power magnitudes.

18. The method of claim 17 further comprising:

calculating a probability of transition; and

applying a bit synchronization analysis method to determine if the main peak location passes or fails.

19. The method of claim 18 where the bit synchronization analysis method comprises:

generating an array of peak values from at least a set of the Y sums of magnitudes where a plot of the peak values against the offsets corresponding to each peak shows the largest magnitude forming a main peak between peaks on either side of the main peak and substantially curvilinear patterns formed by the peaks right and left of the main peak;

generating a right curve by curve-fitting using at least two peaks to the right of the main peak, the right curve having a light second order curve fit;

generating a left curve by curve-fitting using at least two peaks to the left of the main peak, the left curve having a left second order curve fit;

identifying a predicted peak by identifying an intersection point on a timeline formed by the offsets at which the right curve intersects the left curve; and

indicating that the main peak location passes if the intersection point is within a peak offset time limit of the main peak location.

20. The method of claim 19 wherein before performing the bit synchronization analysis, performing the steps of:

calculating a probability of bit transition; and

performing the bit synchronization analysis if the probability of bit transition is greater than a minimum probability.

21. The method of claim 19 wherein before performing the bit synchronization analysis, performing the steps of:

calculating a number of bit transitions using;

No. bit transitions=p_trans*T(elapsed)secs.*50 bps;

measuring a carrier to noise level (C/N₀) and calculating a minimum number of transitions based on the C/N₀.

22. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 17.

23. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 18.

24. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 19.

25. A Global Navigation Satellite System (GNSS) Receiver comprising hardware and software components programmed to perform the method of claim 17 where the bit periodT=20 ms, the sample period S=1 ms, X=20, and Y=20.

26. A system for synchronizing a receiver of a bit stream to the bit stream comprising:

a correlator to generate a correlated sequence of values by correlating a of time sequence stream of values from a finite sample of received bits with a known sequence stream of values;

a plurality of offset accumulators, each corresponding to an offset in a series of time intervals within the correlated sequence, starting with a first time period, the accumulators operable to add a number of values equal to a number of samples in a bit period, the number of values added by each accumulator being a set of values in the correlated sequence starting with the value at the offset corresponding to the accumulator;

a plurality of power magnitude calculators, each corresponding to one of the offsets, operable to receive a sum from the corresponding accumulator, and to calculate a power magnitude; and

a plurality of non-coherent summers each corresponding with one of the offsets, the non-coherent summers operable to add the magnitudes received for each offset in each bit period for all of the N bits, the total sum of magnitudes in each non-coherent summer being analyzed for the highest sum of magnitudes, such that the offset corresponding to the non-coherent summer with the highest sum of magnitudes represents the location of the bit transition in the bit period.

27. The system of claim 26 further comprising a bit synchronization analyzer to analyze the sums of magnitudes in the non-coherent summers to determine whether the location of the bit transition was correctly determined.

28. The system of claim 27 where the bit synchronization analyzer includes hardware and/or software components programmed to perform steps of:

generating a list of peak values from at least a set of the Y sums of magnitudes where a plot of the peak values against the offsets corresponding to each peak shows the largest magnitude forming a main peak between peaks on either side of the main peak and substantially linear patterns formed by the peaks right and left of the main peak;

generating a right curve by curve-fitting at least two peaks to the right of the main peak;

generating a left curve by curve-fitting at least two peaks to the left of the main peak;

identifying a predicted peak by identifying an intersection point on a timeline formed by the offsets at which the right line intersects the left line; and

indicating that the bit transition location passes if the intersection point is within a peak offset time limit of the bit transition location.