Title of Invention

METHOD OF ESTIMATING A PARAMETER OF A LOCAL MAXIMA OR LOCAL MINIMA OF A CORRELATION FUNCTION DERIVED FROM A RECEIVED SIGNAL

Abstract A method of and system for estimating a parameter of a local maxima or minima of a function. An interpolated local maxima or minima is determined. An interpolation offset is then derived, comprising a deviation between locations of the interpolated and sampled local maxima or minima of the function. An estimate of the parameter is derived from the interpolation offset.
Full Text

PROCEDURE FOR ESTIMATING A PARAMETER OF A LOCAL
MAXIMA OR MINIMA OF A FUNCTION
Related Applications
[0000J This application claims priority to U.S. Provisional Application No.
'60/419,626, filed on October 17, 2002.
Field of the Invention.
[0001] This invention relates to the fields of position determination, quadratic
interpolation, arid GPS geo-location systems, and, more specifically, to procedures for estimating a parameter, such as location or scale factor, of a local maxima or minima of a function, such as a GPS correlation function.
Related Art
/ [0002] ") The GPS geo-location system is a system of earth orbiting satellites from Vj&im5h entities visible to the satellites are able to determine their position. Each of the satellites transmits a signal marked with a repeating PN code of 1,023 chips uniquely identifying the satellite. The 1,023 chips repeat every millisecond. The signal is also modulated with data bits, where each data bit has a 20 ms duration in the modulated signal.
[0003] Referring to Figure 1, subscriber station 100 in a wireless communications
system receives transmissions from GPS satellites 102a, 102b, 102c, 102d visible to the
station, and derives various measurements and related values from each of four or more
of the transmissions. The station 100 then communicates the measurements and values
to position determination entity (PDE) 104, which estimates the location and velocity of
the station 100 from these measurements and values. Alternatively, the station 100
determines its own position and velocity from these measurements and values.
[0004] The station 100 searches for a transmission from a particular satellite by
correlating the PN code for the satellite with the received signal, which typically is a composite of transmissions from one or more of the satellites which are visible to the station's receiver in the presence of noise. The correlation is typically performed in two dimensions. In the first dimension, the code phase dimension, the correlation is

performed over a range of possible shifts of the PN code known as the search window W. Each correlation is performed over an integration time I which may be expressed as the product of Nc and M, where Nc is the coherent integration time, and M is number of coherent integrations which are non-coherently combined. In the second dimension, the Doppler frequency dimension, the correlation is performed over a range of Doppler frequency hypotheses.
[0005] The resulting correlation values define a two-dimensional correlation
function. The correlation function is sampled, and the peaks of the correlation function located along each of the two dimensions. Typically, the peaks are also compared to a predetermined threshold selected so that the false alarm probability is at or below a predetermined value. The location of the largest peak in the code phase dimension forms a time measurement for the satellite. Similarly, the location of the largest peak in the Doppler frequency dimension forms a Doppler frequency measurement for the satellite. Peak energy measurements are also derived from the height of the largest peak in both the code phase or Doppler frequency dimensions.
[0006] Due to lack of synchronization with the sampling clock, there is often a
divergence between the sampled and actual peak locations, in both the code phase and Doppler frequency dimensions, and between the sampled and actual peak heights in both dimensions.
[0007] Interpolation is often applied to the samples of the correlation function in
an effort to more accurately estimate the locations and heights of the actual peaks. In quadratic interpolation, for example, a quadratic function is fitted to three samples of the correlation function. The peak of the quadratic function is often a more accurate estimate of the actual peak than is the sampled peak.
[0008] However, the shape of a GPS correlation function, in either the code phase
or Doppler frequency dimensions, rarely resembles a quadratic function. The actual . correlation pulse shape will depend on the exact filtering used in the receive chain of the receiver and the search parameters Nc and M Consequently, the interpolated and actual peak locations will often diverge from one another as will the interpolated and actual peak heights.
[0009] Figure 2 illustrates a pulse 202 of a GPS correlation function in the code
phase dimension. The shape of this particular pulse corresponds to a particular set of filters and a setting of the parameter Nc equal to 20 ms. The peak of this pulse is located

at 0 chips, and the height (in normalized terms) is 1. A first quadratic function 206 is fitted to samples 204b, 204d, and 204f of the pulse 202. A second quadratic function 208 is fitted to samples 204a, 204c, and 204e of the pulse 202. The location 210 of the peak of the first quadratic function 206 and the location 212 of the peak of the second quadratic function 208 both deviate from the location of the true peak (0 chips). Similarly, the height 214 of the peak of the first quadratic function 206 and the height 216 of the second quadratic function 208 both deviate from the height of the true peak (1 in normalized terms).
[0010] Consequently, position and velocity estimates derived from interpolated
peak locations and heights will often be erroneous. The error in locating the peak of the
correlation function in the code phase dimension can give rise to a significant error in
the position estimate. In the particular example illustrated in Figure 2, the error in
locating the peak gives rise to an error of ± 15 m in the position estimate.
[0011] Moreover, currently available interpolation procedures which provide more
precision than quadratic interpolation are expensive and time-consuming, and therefore less suitable for mass market consumer electronic devices such as wireless handsets.
SUMMARY OF THE INVENTION
[0012] A method is described of estimating a parameter of a local maxima or
minima of a function. In one embodiment, the method begins by performing interpolation on samples of the function at or near a local maxima or minima, resulting in an interpolated local maxima or minima.
[0013] Then, an interpolation offset is derived. The interpolation offset is a
deviation between locations of the interpolated local maxima or minim,; and a sampled local maxima or minima. A parameter estimate is then derived from i:^ interpolation offset.
[0014] In one embodiment, the function is a two-dimensional com. ition function,
having a code phase dimension and a Doppler frequency dimension, /'he parameter which is sought to be determined is the location or scale factor of ; peak of the correlation function along one of the two dimensions. A quadratic fun ion is fit to a plurality of samples of the correlation function at or near the peak, and i ie peak of the quadratic function then determined.

[0015] An interpolation offset is then derived, equal to the difference between the
location of the peak of the quadratic function and the location of the sampled peak. A parameter of the peak, such as its location or height, is then determined from the interpolation offset. * "
[0016] In one implementation, a parameter bias has a pre-existing relationship
with the interpolation offset. In this implementation, the parameter estimate is derived using a two-step process. First, the parameter bias corresponding to the interpolation offset is derived using the pre-existing relationship. Second, an estimate of the parameter is derived from the parameter bias.
[0017] In one example, the parameter which is sought to be estimated is the location of a peak of the correlation function along the code phase dimension. An interpolation offset is derived, equal to the difference between the locations of the interpolated and sampled peaks along the code phase dimension. A code phase bias corresponding to this interpolation offset is then determined through an access to a lookup table embodying a pre-existing relationship which is present between these two variables. This code phase bias is added to the interpolation offset to yield an estimate of the location of the peak along the code phase dimension.
[0018] In a second example, the parameter which is sought to be estimated is the
height of a peak of the correlation function along the code phase dimension. An
interpolation offset is derived, again equal to the difference between the locations of the
interpolated and sampled peaks along the code phase dimension. A peak energy bias
corresponding to this interpolation offset is then determined through an access to a
lookup table embodying a pre-existing relationship which is present between these two
variables. This peak energy bias is added to the interpolated peak energy to yield an
estimate of the height of the peak along the code phase dimension.
[0019] In a third example, the parameter which is sought to be estimated is the
location of a peak of the correlation function along the Doppler frequency dimension. An interpolation offset is derived, equal to the difference between the interpolated and sampled peaks along the Doppler frequency dimension. A Doppler frequency bias corresponding to this interpolation offset is determined through an access to a lookup table embodying a pre-existing relationship which is present between these two variables. This Doppler frequency bias is added to the interpolation offset to yield an estimate of the location of the peak along the Doppler frequency dimension.

[0020] In a fourth example, the parameter which is sought to be estimated is the
height of a peak of the correlation function along the Doppler frequency dimension. An interpolation offset is derived, again equal to the difference between the interpolated and sampled peaks along the Doppler frequency dimension. A peak energy bias corresponding to this interpolation offset is determined through a pre-existing relationship which is present between these two variables. This peak energy bias is added to the interpolated peak energy to yield an estimate of the height of the peak along the Doppler frequency dimension.
[0021] Memories tangibly embodying these methods, and related systems, are also
described.
BRIEF DESCRIPTION OF THE DRAWINGS
[0022] The components in the figures are not necessarily to scale, emphasis
instead being placed upon illustrating the principles of the invention. In the figures, like
reference numerals designate corresponding parts throughout the different views,
[0023] Figure 1 is a diagram of a GPS geo-location system,
[0024] Figure 2 is a diagram illustrating interpolation error in a correlation
function derived from a received signal in a GPS geo-location system.
[0025] Figure 3 illustrates an example of a two-dimensional GPS correlation
function, wherein the first dimension is the code phase dimension and the second
dimension is the Doppler frequency dimension.
[0026] Figure 4 illustrates an example of a pulse of a GPS correlation function
along the code phase dimension,
[0027] Figure 5 illustrates an example of a pulse of a GPS correlation function
along the Doppler frequency dimension.
[0028] Figure 6 is a diagram illustrating interpolation offset and parameter bias in
the context of a pulse of a GPS correlation function along the code phase dimension.
[0029] Figure 7 illustrates a flowchart of an embodiment of :: method of
estimating a parameter of a local maxima or minima of a function aa-rding to the
invention.
[0030] Figure 8 illustrates an example of a pre-existing relation, hip between
interpolation offset and code phase bias.

[0031] Figure 9 is an example of a lookup table implementing the relationship of
Figure 8.
[0032] Figure 10 illustrates an example of a pre-existing relationship between
interpolation offset and Doppler frequency bias.
[0033] Figure 11 illustrates an example of a lookup table implementing the
relationship of Figure 10.
[0034] Figure 12 illustrates an example of a pre-existing relationship between
interpolation offset in the code phase dimension and peak energy bias.
[0035] Figure 13 illustrates an example of a lookup table implementing the
relationship of Figure 12.
[0036] Figure 14 illustrates an example of a pre-existing relationship between
interpolation offset in the Doppler frequency dimension and peak energy bias.
[0037] Figure 15 illustrates an example of a lookup table implementing the
relationship of Figure 14.
[0038] Figure 16 is a block diagram of an embodiment of a system for estimating
a parameter of a local maxima or minima of a function according to the invention. '
[0039] Figure 17 is a block diagram of an embodiment of a subscriber station
incorporating the system of Figure 16.
DETAILED DESCRIPTION
[0040} As utilized herein, terms such as "about" and "substantially" are intended
to allow some leeway in mathematical exactness to account for tolerances that are
acceptable in the trade. Accordingly, any deviations upward or downward from the
value modified by the terms "about" or "substantially" in the range of 1% to 20% should
be considered to be explicitly within the scope of the stated value.
[0041] Moreover, as used herein, the term "software" includes source code,
assembly language code, binary code, firmware, macro-instructions, micro-instructions, or the like, or any combination of two or more of the foregoing.
[0042] Furthermore, the term "memory" refers to any processor-readable medium,
including but not limited to RAM, ROM, EPROM, PROM, EEPROM, disk, floppy disk, hard disk, CD-ROM, DVD, or the like, or any combination of two or more of the foregoing, on which may be stored a series of software instructions executable by a processor.

[0043] The terms "processor" or "CPU" refer to any device capable of executing a
series of instructions and includes, without limitation, a general- or special-purpose
microprocessor, finite state machine, controller, computer, digital signal processor
(DSP), or the like.
Introduction to Correlation Functions and Interpolation Error
[0044] Figure 3 illustrates an example of a two-dimensional correlation function
derived from a received signal in a GPS geo-location system. The received signal is a
composite signal comprising one or more component signals each transmitted by a GPS
satellite.
[0045] The correlation function is derived by correlating the received signal with a
PN code for one of the satellites. The correlations are performed over a plurality of code
phase and Doppler frequency hypotheses. The correlation function represents the
correlated energy, in dB or in linear terms, plotted along two dimension, a code phase
dimension and a Doppler frequency dimension. In the example illustr. ed in Figure 3,
the code phase dimension is identified with numeral 302, and the D dimension is identified with numeral 304.
[0046] In the example illustrated in Figure 3, along, the D^ >ler frequency
dimension 304, the correlation function consists of a main lobe 306b a .: two sidelobes
306a, 306c. Along the code phase dimension 302, the correlation fur on consists of
the main lobe 306b and two sidelobes 308a, 308b. Other examples e possible, so
nothing in the foregoing should be taken as limiting.
[0047] Figure 4 illustrates a side view of the correlation function igure 3 along
the axis 4-4 in Figure 3. As shown, the main lobe 306b give rises to a n pulse 402a,
and the sidelobes 308a, 308b give rise to two side pulses 402b, 402b >e main pulse
402a is the relevant pulse for position determination purposes.
[0048] Figure 5 illustrates a side view of the correlation function igure 3 along
the axis 5-5 in Figure 3. As shown, the main lobe 306b gives rise i e main pulse
502a, and the sidelobes 306a, 306c give rise to two side pulses 502b. J. The main
pulse 502a is the relevant pulse for position determination purposes.
[0049] A peak of the correlation function is characterized by c r more peak
parameters. Examples include the location of the peak in the code pha: nension, the
location of the peak in the Doppler frequency dimension, and the heig' *ergy) of the
peak in either dimension. In Figure 6, which illustrates the pulses of Fi: 4 at a higher

level of detail, the location of the peak 602 in the code phase dimension is identified
with numeral 604, and the normalized energy of the peak (in terms of dB) is identified
with numeral 606. These parameters are referred to as "actual" peak parameters.
[0050] The sampled peak, which is the sample closest in height to the actual peak,
is identified with numeral 608a. The sampled peak is characterized by one or more sampled peak parameters, including the location 610 of the sampled peak in the code phase dimension, the location (not shown in Figure 6) of the sampled peak in the Doppler frequency dimension, and the normalized energy of the sampled peak, identified with numeral 612.
[0051] There is usually a deviation between the sampled and actual peaks due to
the asynchronous nature of the sampling clock in relation to the actual peak location. This translates into a deviation between the actual and sampled peak parameters. In Figure 6, for example, the deviation between the actual and sampled peak locations in the code phase dimension is Aj, and the deviation between the actual and sampled peak heights is A2.
[0052] An interpolated peak is identified with numeral 614. This interpolated
peak, which is assumed to have been derived through quadratic interpolation applied to the samples 608a, 608b, and 608c, is characterized by one or more parameters, including the location 616 of the interpolated peak in the code phase dimension, the location (not shown) of the interpolated peak in the Doppler frequency dimension, and the height 618 of the interpolated peak.
[0053] The deviation between a parameter, such as location or scale factor, of the
interpolated peak and of the actual peak is the interpolation error. In Figure 6, the
interpolation error between the actual and interpolated peak heights is A3, and the
interpolation error between the actual and interpolated peak locations along the code
phase dimension is A4 ■ ♦
Embodiments Of The Invention
[0054] Figure 7 illustrates a flowchart of an embodiment of a method of
estimating a parameter of a local maxima or minima of a function. The method begins with step 702. In step 702, the method comprises performing interpolation on samples of the function at or near a local maxima or minima, resulting in an interpolated local maxima or minima. In one implementation, the function is a two-dimensional

correlation function, having a code phase dimension and a Doppler frequency
dimension. In this implementation, step 702 comprises fitting a quadratic function to
three samples at or near a peak of the correlation function along one of the two
- dimensions, and then determining the peak of the quadratic function.
[0055] Step 704 follows step 702. Step 704 comprises deriving an interpolation
offset. The interpolation offset is the difference between the location of the interpolated
local maxima or minima determined in step 702 and the location of a sampled local
maxima or minima. In one example, the sampled local maxima or minima is the largest
or smallest sample (corresponding respectively to whether a local maxima or minima is
involved) within the plurality of samples used in the interpolation process.
[0056] In one embodiment, the interpolation offset is the difference between the
locations of the interpolated and sampled local maxima or minima of the correlation function along either the code phase or Doppler frequency dimensions. In Figure 6, for example, the interpolation offset is the difference A5 between the locations of the sampled and interpolated peaks along the code phase dimension. [0057] Turning back to Figure 7, from step 704, the method proceeds to step 706. In step 706, the method comprises deriving an estimate of the parameter from the interpolation offset.
[0058] In one embodiment, step 706 comprises deriving a parameter bias from the
interpolation offset using a pre-existing relationship which is present between these two variables, and then deriving an estimate of the parameter from the parameter bias. In another embodiment, this step comprises deriving the parameter estimate directly from the interpolation offset.
[0059] In one example, the interpolation offset is the deviation between the
locations of interpolated and sampled peaks of the correlation function along the code phase dimension. A code phase bias bears a relationship with this interpolation offset which is illustrated in Figure 8. Numeral 802 identifies the interpolation offset in terms of chips, numeral 804 identifies the code phase bias, and numeral 806 identifies a curve which embodies the relationship between these two variables. As can be seen, in this particular example, for an interpolation offset ranging between -0.5 and +0.5, the code phase bias ranges between -0.00405 to +0.0575 chips, which translates to -11.87 to + 16.85 meters.

[0060] In one implementation of this example, the relationship between the
interpolation offset and the code phase bias is embodied as a lookup table. Using this lookup table, a code phase bias is determined responsive to the interpolation offset. The code phase Bias is added to the interpolation offset to form an estimate of the location of the peak along the code phase dimension. In this particular example, the estimate is in terms of a code phase offset between the sampled and actual peaks, but it should be appreciated that other forms of expressing the estimate are possible, such as the code phase offset between the interpolated and actual peaks. Moreover, in this particular example, an access to the lookup table yields a code phase bias which is then added to the interpolation offset to form the peak location estimate. However, it should be appreciated that embodiments are possible in which an access to the lookup table directly yields the peak location estimate.
[0061] An example of this lookup table is illustrated in Figure 9. in this particular
example, the lookup table has 129 entries, associated with table indices ranging from 0 to 128. The entry corresponding to index value 0 is identified with numeral 902a; the entry corresponding to index value 1 is identified with numeral 1; the entry corresponding to index value 2 is identified with numeral 2; and the entry corresponding to index value 128 is identified with numeral 902e.
[0062] The following equation maps the interpolation offset, interp_offset, to a
table index, lutjndex:
lut_index = (int)((interp_offset + 0.5) * (lut_size-l)) (1)
where int is the integer function, and lut_size is the size of the lookup table. In this
particular example, lut_size is 129. For values of the interpolation offset which range
between -0.5 and +0.5, this expression yields index values between 0 and 128.
[0063] In a second example, the interpolation offset is the deviation between the
locations of interpolated and sampled peaks of a correlation function along the Doppler frequency dimension. A Doppler frequency bias bears a relationship with this interpolation offset which is illustrated in Figure 10. The interpolation offset i* identified with numeral 1002, the Doppler frequency bias is identifier with numeral 1004, and a curve embodying the relationship between these two variables is identified with numeral 1006. As can be seen, for an interpolation offset ranging between -0.5 and +0.5, the Doppler frequency bias ranges between -2 to +2 Hz.

[0064] In one implementation of this example, the relationship is embodied as a
lookup table. Using this lookup table, a Doppler frequency bias is determined which corresponds to the interpolation offset. This Doppler frequency bias is added to the interpolation offset to form an estimate of the location of the peak along the Doppler frequency dimension. In this particular example, the peak location estimate is in the form of a Doppler frequency offset between the sampled and actual peaks, but it should be appreciated that other forms of expressing the estimate are possible, such as in the form of an offset between the interpolated and actual peaks. Moreover, in this particular example, an access to the lookup table yields a Doppler frequency bias, but it should be appreciated that examples are possible where an access to the lookup table directly yields the peak location estimate.
[0065J An example of this lookup table is illustrated in Figure 11. In this
particular example, the lookup table has 33 entries, associated with table indices ranging
from 0 to 32. The table entry corresponding to the index 0 is identified with numeral
1102a; the table entry corresponding to index value 1 is identified with numeral 1102b;
the table entry corresponding to index value 2 is identified-with numeral 1102c; and the
table entry corresponding to index value 32 is identified with numeral 1102d.
[0066] The entries of the table illustrated in Figure 11 are in terms of Doppler bins
rather than Hz. The relationship between the size of Doppler bins and Hz in this example depends on the setting of Nc- In the case where Nc is set to 20 ms, the size of a Doppler bin is 25 Hz. Equation (1) above, with lut_size set equal to 33, maps the interpolation offset into a table index.
[0067] In a third example, the interpolation offset is again the deviation between
the locations of interpolated and sampled peaks along the code phase dimension. A peak energy bias bears a relationship with this interpolation offset which is illustrated in Figure 12. The interpolation offset is identified with numeral 1202, the peak energy bias is identified with numeral 1204, and a curve embodying the pre-existing relationship between these two variables is identified with numeral 1206. The peak energy bias is in terms of C/No, expressed in units of dB-Hz. As can be seen, for values of the interpolation offset ranging from -0.5 to +0.5, the peak energy bias ranges from -0.69 to +0.14.
[0068] In one implementation of this example, this relationship is embodied as a
lookup table. Using this lookup table, a peak energy bias is determined which

corresponds to the interpolation offset. This peak energy bias is then added to the
interpolated peak energy to form an estimate of the actual peak energy.
[0069] An example of this lookup table is illustrated in Figure 13. In this
particular example, the lookup table has 33 entries, associated with table index values ranging from 0 to 32. The entry corresponding to an index of 0 is identified with numeral 1302a; the entry corresponding to an index of 1 is identified with numeral 1302b; the entry corresponding to an index of 2 is identified with numeral 1302c; and the entry corresponding to an index of 32 is identified with numeral J302d. Equation (1) maps an interpolation offset to a table index.
[0070] In this particular example, an access to the lookup table yields a peak
energy bias which is subsequently added to the interpolated peak energy to form an
estimate of the actual peak energy, but it should be appreciated thiii examples are
possible where an access to the lookup table directly yields the estimate of the actual
peak energy. Moreover, examples are possible where the estimate of the actual peak
energy is formed by adding the peak energy bias to the sampled peak ent gy.
[0071] In a fourth example, the interpolation offset is the deviar -n between the
locations of the interpolated and sampled peaks along the Doppler frequ^ icy dimension. A peak energy bias bears a relationship with this interpolation offset wh h is illustrated in Figure 14. The interpolation offset is identified with numeral 1402. :-;e peak energy bias is identified with numeral 1404, and the curve embodying the relar nship between these two variables is identified with numeral 1406. As can be seen, ( values of the interpolation offset ranging from -0.5 to +0.5, the peak energy bias which in thi: particular example is in terms of C/No and is expressed in units of dB-R ranges from -0.45 to 0.
[0072] In one implementation of this example, the relationship be cen these tw; variables is embodied as a lookup table. Using this lookup table, a pc. nergy bias is
determined which corresponds to the interpolation offset. This peak em v bias is then
added to the interpolated peak energy to form an estimate of the actual j« energy.
[0073] An example of this lookup table is illustrated in Rgu 15. In thi
particular example, the lookup table has 33 entries associated with v;r of the table-index ranging from 0 to 32. The entry corresponding to an index of 0 r ientified with numeral 1502a; the entry corresponding to an index of 1 is identifier vith numeral 1502b; the entry corresponding to an index of 2 is identified with nunn ; 1502c; am

the entry corresponding to an index of 32 is identified with numeral 1502d. Equation
(1) above maps between an interpolation offset to a table index.
[0074] In this particular example, an access to the lookup table yields a peak
energy bias which is subsequently added to the interpolated peak energy to form an
estimate of the actual peak energy, but it should be appreciated that examples are
possible where an access to the lookup table directly yields an estimate of the actual
peak energy. Moreover, examples are possible where the estimate of the actual peak
energy is formed from the sum of the peak energy bias and the sampled peak energy.
[0075] An embodiment of a system for estimating a paramater of a local maxima
or minima of a function is illustrated in Figure 16. As illustrated, the system comprises
processor 1602 and memory 1604. The memory 1604 tangibly embodies a series of
instructions for performing the method of Figure 7, or any of the embodiments,
implementations, or examples thereof which have been described or suggested. The
processor is configured to access and execute the software instructions tangibly
embodied by memory 1604.
[0076] In one implementation, in which a parameter estimate or bias bears a
relationship with the interpolation offset which is embodied as a lookup table, the
lookup table is stored in the memory 1604, and accessible by the processor 1602 for
determining the parameter estimate or bias corresponding to a particular value of the
interpolation offset.
[0077] An embodiment of a subscriber station in a wireless communication system
is illustrated in Figure 17. This particular subscriber station is configured to embody or
incorporate the system of Figure 16.
[0078] Radio transceiver 1706 is configured to modulate baseband information,
such as voice or data, onto an RF carrier, and demodulate a modulated RF carrier to
obtain baseband information.
[0079] An antenna 1710 is configured to transmit a modulated RF carrier over a
wireless communications link and receive a modulated RF carrier over a wireless
communications link.
[0080] Baseband processor 1708 is configured to provide baseband information
from an input device within user interface 1716 to transceiver 1706 for transmission
over a wireless communications link. Baseband processor 1708 is also configured to

provide baseband information from transceiver 1706 to an output device within user interface 1716.
[0081] User interface 1716 comprises a plurality of devices for inputting or
outputting user information such as voice or data. The devices typically included within
the user interface include a keyboard, a display screen, a microphone, and a speaker.
[0082] GPS receiver 1712 is configured to receive and down-convert GPS satellite
transmissions, and providing the down-con verted information to correlator 1718.
[0083] Correlator 1718 is configured to derive GPS correlation functions from the
information provided to it by GPS receiver 1712. For a given PN code, correlator 1720 produces a correlation function which is defined over a code phase dimension and a Doppler frequency dimension. In the code phase dimension, the correlation function is defined over a range of code phases which define a search window W. In the Doppler frequency dimension, the correlation function is defined over a plurality of Doppler frequency bins. Each individual correlation is performed in accordance with defined coherent and non-coherent integration parameters (Nc, M).
[0084] ..Correlator 1718 may also be configured to derived pilot-related correlation functions from information relating to pilot signals provided to it by transceiver 1706. This information is used by the subscriber station to acquire wireless communications services.
[0085] Channel decoder 1720 is configured to decode channel symbols provided
to it by baseband processor 1708 into underlying source bits. In one example, where the
channel symbols are convolutionally encoded symbols, the channel decoder is a Viterbi
decoder. In a second example, where the channel symbols are serial or parallel
concatenations of convolutional codes, the channel decoder 1720 is a turbo decoder.
[0086] Memory 1704 in configured to hold software instructions embodying the
method of Figure 7, or any of the embodiments, implementations, or examples thereof which have been described or suggested. CPU 1702 is configured to access and execute these software instructions to estimate parameters of local maxima or minima in the GPS correlation functions provided to it by correlator 1718,
[0087] Memory 1704 is also configured to hold lookup tables embodying the pre-
existing relationships between an interpolation error and a parameter estimate or bias. In one example, CPU 1702 is configured to access and utilize these lookup tables to

determine a parameter estimate or bias which corresponds to a particular interpolation offset.
[0088] CPU 1702 is configured to analyze the GPS correlation functions provided
to it by correlator 1718, to isolate the local maxima or minima thereof, and to estimate
parameters of or relating to these local maxima or minima using the method of Figure 7,
or any of the variants thereof which have been discussed or suggested.
[0089] CPU 1702 is also configured derive time and Doppler frequency
measurements from these parameters. In addition, in one embodiment, CPU 1702 is
configured to determine the root mean square error (RMSE) associated with each of the
measurements. In this embodiment, these measurements and RMSE values are provided
to a PDE (not shown). The PDE weights each of the measurements based on the inverse
of its corresponding RMSE value, and then estimates the location and velocity of the
subscriber station based on the weighted measurements. Alternatively, the subscriber
station determines its own location and velocity from this information.
[0090] While various embodiments, implementations and examples have been
described, it will be apparent to those of ordinary skill in the art that many more embodiments, implementations and examples are possible that are within the scope of this invention. In particular, embodiments are possible where the invention is employed to estimate parameters of local maxima or minima of functions other than correlation functions, or of correlation functions derived from signals transmitted by base stations in wireless communications systems, including omni base stations and individual sectors in a multi-sector cell, or of correlation functions derived from signals transmitted by in hybrid systems employing combinations of base stations and GPS satellites. Moreover, embodiments are possible where more than one parameter of a local maxima or minima of a function is estimated at a time. Consequently, the invention is not to be limited except in relation to the appended claims.

CLAIMS
1. A method of estimating a parameter of a local maxima or minima of a
function comprising:
performing interpolation on samples of the function at or near a local maxima or minima, resulting in an interpolated local maxima or minima;
deriving an interpolation offset comprising a deviation between locations of the interpolated local maxima or minima and a sampled local maxima or minima; and
deriving an estimate of the parameter from the interpolation offset.
2. The method of claim 1 wherein the function is a correlation function.
3. The method of claim 2 wherein the correlation function is derived from a
received signal.
4. The method of claim 2 wherein the second deriving step comprises
deriving a parameter bias from the interpolation offset using a pre-existing relationship
that is present between these two variables and then deriving an estimate of the
parameter from the parameter bias.
5. The method of clafm 4 wherein the interpolation offset comprises a
deviation between locations of interpolated and sampled peaks along a code phase
dimension.
6. The method of claim 5 wherein the parameter bias is a code phase bias.
7. The method of claim 6 wherein the parameter which is estimated is
location of a peak along the code phase dimension, and an estimate of this parameter is
derived from the code phase bias.
8. The method of claim 4 wherein the interpolation offset comprises a
deviation between locations of interpolated and sampled peaks along a Doppler
frequency dimension.

9. The method of claim 8 wherein the parameter bias is a Doppler frequency
bias.
10. The method of claim 9 wherein the parameter which is estimated is
location of a peak of the function along the Doppler frequency dimension, and an
estimate of this parameter is derived from the Doppler frequency bias.
11. The method of claim 5 wherein the parameter bias is a peak energy bias.
12. The method of claim 11 wherein the parameter which is estimated is peak
energy, and an estimate of this parameter is derived from the peak energy bias.
13. The method of claim 9 wherein the parameter bias is a peak energy bias.
14. The method of claim 13 wherein the parameter which is estimated is peak
energy, and an estimate of this parameter is derived from the peak energy bias.
15. The method of claim 4 wherein the pre-existing relationship between the
interpolation offset and the parameter bias is embodied as a lookup table.
16. The method of claim 15 wherein the second deriving step comprises
directly deriving an estimate of the parameter from the interpolation offset through an
access to the lookup table.
,\ n>^ 17. A memory tangibly embodying a lookup table, the lookup table x\y ^K
implementing a pre-existing relationship between an interpolation offset and a , *A parameter bias or parameter estimate, and the interpolation offset comprising a deviation A
between locations of interpolated and sampled local maxima or minima of a function. ^ > y,
18. The memory of claim 17 wherein the function is a correlation function. \ ^
V
A* (

19. The memory of claim 18 wherein the correlation function is derived from a
received signal.
20. The memory of claim 18 wherein an access to the lookup table yields a
parameter bias.
21. The memory of claim 18 wherein an access to the lookup table yields a
parameter estimate.
22. The memory of claim 20 wherein the interpolation offset comprises a
deviation between locations of interpolated and sampled peaks along a code phase
dimension.
23. The memory of claim 22 wherein the parameter bias is a code phase bias
24. The memory of claim 23 wherein the parameter estimate is an estimate o
the location of a peak along a code phase dimension.
25. The memory of claim 24 wherein the parameter estimate comprises a sun
of the interpolation offset and the code phase bias.
26. The memory of claim 22 wherein the parameter bias is a peak energy bias
27. The memory of claim 26 wherein the parameter estimate is an estimate ol
peak energy.
28. The memory of claim 27 wherein the parameter estimate comprises a surr
of interpolated peak energy and a peak energy bias.
29. The memory of claim 27 wherein the parameter estimate comprises a sum
of sampled peak energy and a peak energy bias.

30. The memory of claim 20 wherein the interpolation offset comprises a
deviation between locations of interpolated and sampled peaks along a Doppler
frequency dimension.
31. The memory of claim 30 wherein the parameter bias is a Doppler
frequency bias.
32. The memory of claim 31 wherein the parameter estimate is an estimate of
the location of a peak along a Doppler frequency dimension.
33. The memory of claim 32 wherein the parameter estimate comprises a sum
of the interpolation offset and a Doppler frequency bias.
34. The memory of claim 30 wherein the parameter bias is a peak energy bias.
35. The memory of claim 34 wherein the parameter estimate is an estimate of
peak energy.
36. The memory of claim 35 wherein the estimate comprises a * urn of
interpolated peak energy and a peak energy bias.
37. The memory of claim 35 wherein the estimate comprises a ;m of sampled
peak energy and a peak energy bias.
38. A system comprising a processor and the memory of clain 7, wherein the
processor is configured to access the lookup table tangibly embodied b; •.: memory.
39. A memory tangibly embodying a sequence of software in: lions for
performing a method of estimating a parameter of a local maxima or m: a of a
function comprising:
performing interpolation on samples of the function at or near a 1 maxima or minima, resulting in an interpolated local maxima or minima;

deriving an interpolation offset comprising a deviation between locations of the interpolated local maxima or minima and a sampled local maxima or minima; and deriving an estimate of the parameter from the interpolation offset.
40. The memory of claim 39 wherein the function is a correlation function.
41. The memory of claim 40 wherein the correlation function is derived from a
received signal.
42. The memory of claim 40 wherein the second deriving step comprises
deriving a parameter bias from the interpolation offset using a pre-existing relationship
which is present between these two variables and deriving an estimate of the parameter
from the parameter bias.
43. The memory of claim 42 wherein the interpolation offset comprises a
deviation between locations of interpolated and sampled peaks along a code phase
dimension.
44. The memory of claim 43 wherein the parameter bias is a code phase bias.
45. The memory of claim 44 wherein the parameter is location of a peak along
the code phase dimension, and an estimate of this parameter is derived from the code
phase bias.
46. The memory of claim 42 wherein the interpolation offset comprises a
deviation between locations of interpolated and sampled peaks along a Doppler
frequency dimension.
47. The memory of claim 46 wherein the parameter bias is a Doppler
frequency bias.

48. The memory of claim 47 wherein the parameter which is estimated is
location of a peak of the function along the Doppler frequency dimension, and an
estimate of this parameter is derived from the Doppler frequency bias.
49. The memory of claim 46 wherein the parameter bias is a peak energy bias.
50. The memory of claim 49 wherein the parameter which is estimated is peak
energy, and an estimate of this parameter is derived from the peak energy bias.
51. The memory of claim 46 wherein the parameter bias is a peak energy bias.
52. The memory of claim 51 wherein the parameter which is estimated is peak
energy, and an estimate of this parameter is derived from the peak energy bias.
53. The memory of claim 42 wherein the pre-existing relationship between the
interpolation offset and the parameter bias is embodied as a lookup table.
54. A system comprising a processor and the memory of claim 39, wherein the
processor in configured to access and execute the sequence of software instructions
tangibly embodied by the memory.
55. A method of estimating a parameter of a local maxima or minima of a A
function comprising: I a step for performing interpolation on samples of the function at or near a local J k 7y
maxima or minima, resulting in an interpolated local maxima or minina; \, x / /
y IX \t/
a step for deriving an interpolation offset comprising a deviation between . IX \ locations of the interpolated local maxima or minima and a sampled local maxima or
minima; and
a step for deriving an estimate of the parameter from the interpolation offset.





Documents:

628-CHENP-2005 AMENDED CLAIMS 18-05-2011.pdf

628-CHENP-2005 AMENDED PAGES OF SPECIFICATION 18-05-2011.pdf

628-CHENP-2005 OTHER PATENT DOCUMENT 18-05-2011.pdf

628-chenp-2005 amended pages of specification 16-06-2011.pdf

628-chenp-2005 amended claims 16-06-2011.pdf

628-chenp-2005 correspondence others 18-05-2011.pdf

628-CHENP-2005 EXAMINATION REPORT REPLY RECEIVED 16-06-2011.pdf

628-chenp-2005 form-1 18-05-2011.pdf

628-chenp-2005 form-3 18-05-2011.pdf

628-chenp-2005 other patent document 16-06-2011.pdf

628-CHENP-2005 POWER OF ATTORNEY 18-05-2011.pdf

628-CHENP-2005 CORRESPONDENCE OTHERS 01-10-2010.pdf

628-CHENP-2005 CORRESPONDENCE 01-10-2010.pdf

628-CHENP-2005 no document.pdf

628-chenp-2005-abstract.pdf

628-chenp-2005-assignement.pdf

628-chenp-2005-claims.pdf

628-chenp-2005-correspondnece-others.pdf

628-chenp-2005-description(complete).pdf

628-chenp-2005-drawings.pdf

628-chenp-2005-form 1.pdf

628-chenp-2005-form 18.pdf

628-chenp-2005-form 26.pdf

628-chenp-2005-form 3.pdf

628-chenp-2005-form 5.pdf

628-chenp-2005-pct.pdf


Patent Number 248147
Indian Patent Application Number 628/CHENP/2005
PG Journal Number 25/2011
Publication Date 24-Jun-2011
Grant Date 22-Jun-2011
Date of Filing 13-Apr-2005
Name of Patentee QUALCOMM INCORPORATED
Applicant Address 5775 MOREHOUSE DRIVE, SAN DIEGO, CALIFORNIA 92121, USA
Inventors:
# Inventor's Name Inventor's Address
1 PATRICK, CHRISTOPHER 14358 DALHOUSIE ROAD, SAN DIEGO, CALIFORNIA 92129, USA
2 ROWITCH, DOUGLAS, NEAL 2009 DE MAYO ROAD, DEL MAR, CALIFORNIA 92014, USA
PCT International Classification Number G01S 5/14
PCT International Application Number PCT/US03/33122
PCT International Filing date 2003-10-17
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 10/687,478 2003-10-16 U.S.A.
2 60/419,626 2002-10-17 U.S.A.