Determining the spatio-temporal and kinematic parameters of a signal receiver and its clock by information fusion

FIELD OF THE INVENTION

0001The present invention relates to signal processing and, more particularly, to techniques for estimating certain parameters by means of processing a received signal containing possible contributions from known signals originating from multiple sources.

BACKGROUND OF THE INVENTION

0002In general, before a known signal is received by a receiver, the known signal is modified by effects due to various receiver parameters such as the receiver's spatio-temporal location, the receiver's velocity and the offset and drift rate of the receiver's clock. The receiver's location affects the signal delay, that is the unknown amount of time by which the signal is delayed in the course of traveling from the source to the receiver. In addition, the carrier frequency of the known signal is shifted by an unknown amount due to the receiver's clock drift and the Doppler shift caused by the relative motion of the receiver with respect to the source. Clock drift is herein referred to as "clock Doppler". The overall frequency shift, herein referred to as "Doppler shift", is the sum of clock Doppler and motion Doppler. The motion Doppler is further decomposed into source motion Doppler and receiver motion Doppler. In many applications, the source motion Doppler is known and the unknown Doppler shift depends only on unknown receiver parameters, such as clock Doppler and receiver motion Doppler.

0003The signal that is received at the receiver, which typically includes noise, is generally referred to as the "received signal", or also "data". For many applications, when a receiver samples the received signal for a long duration of time, it is important to know the carrier frequency of the received signal to a high degree of accuracy in order to process the received signal using coherent correlation methods. In particular, for signals sampled over a long duration, an inaccurate estimation of the carrier frequency will often result in out-of-phase correlations. Estimation of the carrier frequency is equivalent to estimation of the Doppler shift. The carrier frequency and delay of a known signal are herein referred to also as "signal parameters".

0004Typically, in the case of multiple known signals being transmitted to a receiver by multiple sources, as in the case of Global Positioning System, the Doppler shifts and delay values of the received signals are independently calculated for each satellite vehicle that is potentially overhead the receiver.

0005A significant disadvantage to the above approach is that the approach does not leverage the calculations for the signal and receiver parameters performed with respect to one source against the calculations with respect to another source, thus resulting in a high computational expense. Further, the approach does not take advantage of the fact that it may be possible to obtain a coarse estimate of certain signal and receiver parameters with small computational expense by processing a small segment of the received signal. A coarse estimate obtained from a small data segment can be used to significantly reduce the computational expense in processing a larger data segment and/or the entire segment of received data.

0006Based on the foregoing, there is a clear need for a technique to determine the receiver parameters and the carrier frequencies and delays of the known signals that leverages the information gathered from a subset of the sources and from shorter segments of the received signal to reduce the calculations needed to process the entire duration of the received signal and the entire set of sources.

SUMMARY OF THE INVENTION

0007Techniques are provided for determining the spatio-temporal and kinematic receiver parameters and, in addition, the Doppler shifts and the signal delays (the signal parameters) of multiple known signals transmitted by multiple sources. One aspect of the invention is to divide the sampled data received by the receiver into possibly overlapping segments of data, herein referred to as "data segments". In some embodiments, these segments form a nested sequence of segments of increasing length. Receiver and signal parameters are estimated by searching for the known signals in the various data segments. Each pair consisting of a source and a data segment, herein referred to as "source-segment" pair, yields a piece of information obtained by means of searching for the known signal corresponding to that source in that data segment. In some embodiments, the search is carried out by correlating data segments with the known signals for a suitable set of signal parameter values. The information recovered from the source-segment pairs that have already been processed is used to reduce and refine the calculations for the other source-segment pairs.

0008A "fusion engine" is used to store and integrate the information on receiver parameters and signal parameters gathered at any intermediate stage from the source-segment pairs that have been processed. Such information is represented inside the fusion engine by means of an "uncertainty region representation", which in some embodiments consists of a set of inequalities. At any stage, the engine uses the current uncertainty region representation to generate estimates and bounds of signal parameters (such as Doppler shifts and delay values) used to guide the search in the subsequent stages. Estimates and bounds of signal parameters and receiver parameters get refined as more stages are completed.

BRIEF DESCRIPTION OF THE DRAWINGS

0009The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> is a block diagram that illustrates a system overview of a multi-stage technique for estimating receiver parameters and signal parameters;</li><li><figref idref="f0002">FIG. 2A</figref> and <figref idref="f0003">FIG. 2B</figref> are flowcharts that illustrate the functional overview of a technique for estimating receiver parameters; <figref idref="f0004">FIG. 2C</figref> is a block diagram that illustrates increasing data segments;</li><li><figref idref="f0005">FIG. 3</figref> illustrates the geometric and kinematic parameters of the receiver relative to one particular source;</li><li><figref idref="f0006">FIG. 4</figref> illustrates one embodiment of a fusion engine which integrates receiver parameters, signal delay values and carrier frequency information obtained from a subset of sources and from segments of the received signal;</li><li><figref idref="f0007">FIG. 5</figref> is a flowchart that illustrates the calculations to determine the coefficients used in one embodiment of the fusion engine based on Linear Programming;</li><li>FIG. 6 is a block diagram illustrating a computer system on which embodiments of the invention may be implemented.</li></ul>

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

0010Techniques are provided for estimating the spatio-temporal and kinematic parameters of a signal receiver that receives multiple known signals transmitted by multiple sources. These spatio-temporal and kinematic parameters of a receiver can include such parameters as position, velocity, clock offset, clock drift rate, etc. In addition, the provided techniques estimate signal parameters such as the signal delay and carrier frequencies associated with the set of sources. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

SYSTEM OVERVIEW

0011<figref idref="f0001">FIG. 1</figref> is a block diagram that illustrates a system overview for estimating receiver parameters. In one embodiment, these parameters are estimated by means of determining the carrier frequency (equivalently, the Doppler shift) and the signal delay of the different known signals that contribute to a received signal that is received at the receiver as explained below. System 100 comprises a plurality of signal sources of which only signal sources <i>S</i>₁ and <i>S_n</i> are shown in <figref idref="f0001">FIG. 1</figref>. In addition, system 100 comprises a receiver H, a base station B, and a server D. By way of example, only one base station and one server are shown in system 100. For example, in a practical system, there may be multiple base stations and multiple servers. In other embodiments of the invention, the server may be co-located with the base station or with the receiver.

0012Signal sources <i>S</i>₁ and <i>S_n</i> may represent a variety of different signal sources. For example, signal sources <i>S</i>₁ and <i>S_n</i> may be satellites. Receiver H may represent a variety of receiver devices such as Global Positioning System receivers, cell phones with embedded signal receivers, Personal Digital Assistants (PDAs) with embedded signal receivers, etc. For the purpose of explanation, the embodiments of the invention are explained with respect to a set of Global Positioning System (GPS) satellite vehicles that are overhead the location of receiver H at a given time. Thus, in the example, <i>S</i>₁ through <i>S_n</i> is the plurality of signal sources that make up the set of GPS satellite vehicles that are overhead the location of receiver H at any given time.

0013By way of example, the GPS satellite vehicles produce analog signals. Each analog signal is transmitted to receiver H. The signal that is received at H is herein referred to as "received signal". Thus, the received signal contains, in addition to noise, contributions from multiple GPS satellite vehicles that are overhead the receiver H. In certain embodiments of the invention, H converts the analog signal into a discrete sequence of values as a function of time by digitizing the received signal. The digitized received signal is herein referred to as a "sampled signal" or "sampled data". In one embodiment of the invention, H transmits the sampled data to server D for processing.

0014Assuming there is an unknown delay in time from the time the analog signal leaves a particular GPS satellite vehicle and the time the signal is received at receiver H, such a delay is herein referred to as a "delay value". The distance between the GPS vehicle and the receiver H can be estimated from an estimate of the delay in the known signal corresponding to the particular GPS vehicle. However, this distance estimate is biased by the receiver's clock offset. By combining estimates from different satellites it is possible to estimate the clock offset and correct the distance estimates for the clock offset bias.

0015Further, by the time the signal that is being transmitted by each of the satellite vehicles overhead reaches the receiver, the signal's original carrier frequency is shifted by an unknown amount due to a Doppler shift, which may, for example, include a satellite clock Doppler, a receiver clock Doppler, source motion Doppler and/or receiver motion Doppler. If it is assumed that the position of the receiver is known; that the motion of each signal source (satellite vehicles, for example) is known; and that the satellite clock Dopplers are also known, then the sum of receiver clock Doppler and receiver motion Doppler can be estimated by determining the carrier frequency of the different signals that comprise the received signal. By combining information from different satellites it is possible to separate clock Doppler from receiver motion Doppler and to determine the clock Doppler and the velocity of the receiver.

FUNCTIONAL AND OPERATIONAL OVERVIEW

0016<figref idref="f0002">FIG. 2A</figref> and <figref idref="f0003">FIG. 2B</figref> are flowcharts that illustrate the functional overview of a technique for estimating the spatio-temporal and kinematic parameters of the receiver and, in addition, the Doppler shifts and the signal delays of multiple known signals transmitted by multiple sources. In the preferred embodiment, it is assumed that the positions and velocities of all the sources and their clock's offsets and drift rates are known at any point in time. Further, it is assumed that an initial coarse estimate of the receiver location, the receiver velocity, and the receiver's clock time offset and clock Doppler can be obtained, in addition to uncertainty bounds on these values.

0017In the particular embodiment shown in <figref idref="f0002 f0003 f0004">FIG. 2</figref> the segments of data form a nested sequence of increasing length, as explained below. Further, the source-segment pairs are processed in an order determined by an outer loop over the increasing sequence of nested segments and an inner loop over the set of sources. One skilled in the art can see that other orderings of the source-segment pairs can also be used.

0018At block 202 of <figref idref="f0002">FIG. 2A</figref>, the sampled data associated with the received signal is received for analysis by server D. At block 204, the sampled data is divided into a set of increasing data segments, wherein each successive data segment in the set is formed by extending a previous data segment to include additional data from the sampled data. Thus, the data segments are extended in an incremental manner. By way of example, <figref idref="f0004">FIG. 2C</figref> is a block diagram that illustrates increasing data segments. There are (J+1) number of segments. Segment 250 is the first data segment, segment 252 is the second data segment, etc. Segment 258 is the J-th data segment. For segment 250, j is zero, for segment 252, j is 1, etc. As can be seen from <figref idref="f0004">FIG. 2C</figref>, each successive segment includes the previous segment and additional data from the sampled data. In certain embodiments of the invention, the length of each segment is proportional to 2<i>^j</i>.

0019At block 206 of <figref idref="f0002">FIG. 2A</figref>, a shortest data segment j that has not been previously selected is selected from the set of data segments to be a selected segment. In the first stage, the shortest segment that is selected is the data segment for which j is zero. At block 208, one source <i>S_i</i> that has not been previously selected with the selected segment j is selected to be the selected source. Let <i>l</i> be the total number of sources that have been selected so far for the selected segment j. At block 210, control is passed to block 218 of <figref idref="f0003">FIG. 2B</figref>. This begins the stage (<i>j</i>, <i>l</i>) of the method.

0020At block 218 of <figref idref="f0003">FIG. 2B</figref>, queries 425 and 426 (<figref idref="f0006">FIG. 4</figref>) are submitted to the fusion engine 430 to obtain current bounds for the Doppler shift <maths id="math0001"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>f</mi><mi>i</mi><mi>max</mi></msubsup></mfenced></math><img file="EP2020607A2_D0001.tif" /></maths> and the code-phase <maths id="math0002"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>σ</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup></mfenced></math><img file="EP2020607A2_D0002.tif" /></maths> of the known signal corresponding to the selected source <i>S_i</i>. The code-phase is an equivalent representation of the signal delay, as one skilled in the art will see after reading section "Linear expression for code-phase and Doppler shift". Examples of how these uncertainty intervals are calculated are described in section "Calculation of uncertainty intervals".

0021At block 220 of <figref idref="f0003">FIG. 2B</figref>, the calculations (e.g. correlations) for data segment j and the known signal of souree <i>S_i</i> are performed as explained in section "Calculation of uncertainty intervals" and new bounds <maths id="math0003"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>f</mi><mi>i</mi><mi>max</mi></msubsup></mfenced><mo>,</mo></math><img file="EP2020607A2_D0003.tif" /></maths><maths id="math0004"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>σ</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup></mfenced></math><img file="EP2020607A2_D0004.tif" /></maths> are calculated. At block 222, the updated uncertainty intervals <maths id="math0005"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>f</mi><mi>i</mi><mi>max</mi></msubsup></mfenced></math><img file="EP2020607A2_D0005.tif" /></maths> and <maths id="math0006"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>σ</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup></mfenced></math><img file="EP2020607A2_D0006.tif" /></maths> are encoded as constraints 455, 456 in the fusion engine 430 of <figref idref="f0006">FIG. 4</figref>. In some embodiments, the fusion engine will use the updated uncertainty intervals coming from this source-segment pair to replace any previous uncertainty constraints that had been explicitly associated with this source in previous stages. This terminates the stage (<i>j,l</i>) of the method.

0022At block 224, control is passed to block 208 of <figref idref="f0002">FIG. 2A</figref> until all the sources have been selected as the selected source. If all the sources from the set of sources have been selected to be the selected source, then control passes to block 226 and the set of selected sources is cleared by setting <i>l</i> = 0. At block 226, control is passed to block 206 of <figref idref="f0002">FIG. 2A</figref> until all the data segments from the set of data segments have been selected to be the selected segment. The operation as described with reference to <figref idref="f0002">FIG. 2A</figref> and <figref idref="f0003">FIG. 2B</figref> is complete once all the data segments from the set of data segments have been selected as the selected segment.

SPATIO-TEMPORAL COORDINATES OF THE RECEIVER

0023In some embodiments of the invention, a query is made at a particular point in time to request information about the location of the receiver and possibly other receiver parameters such as receiver velocity, clock offset and clock drift rate. This will be called the "query event" and denoted Q. The query event <i>Q</i> can be parameterized by a total of four coordinates, one temporal and three spatial. These coordinates are unknown and one objective of this invention is to estimate them. The specific values of these coordinates depend on the particular coordinate system, also called "observation frame" and denoted F, which was chosen beforehand. Let (<i>t,<o ostyle="single">x</o></i>) be the spatio-temporal coordinate of the query event <i>Q</i> in the frame F. The velocity of the receiver in the frame F at the query time is denoted <o ostyle="single">v</o>.

0024The relative position of the receiver with respect to one particular signal source is illustrated in <figref idref="f0005">FIG. 3</figref>. Block 310 is the origin of the coordinate system F. Block 320 is the query event <i>Q</i> that coincides spatially with the receiver and temporally with the time instant at which the receiver parameter must be estimated. Block 330 is a known approximation to the query event, denoted <i>Q*</i>, which is used in the preferred embodiment as the linearization point. Block 340, the <i>i</i>-th "transmission event", is located at the position of source <i>S_i</i> at the time when <i>S_i</i> transmits the known signal arriving to the approximate receiver location <o ostyle="rightarrow">x</o>* at the approximate query time <i>t</i>*. The spatio-temporal coordinate of the <i>i</i>-th transmission event 340 is denoted <maths id="math0007"><math display="inline"><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup><mo>⁢</mo><msub><mover><mi>x</mi><mo>→</mo></mover><mi>i</mi></msub></mfenced><mn>.</mn></math><img file="EP2020607A2_D0007.tif" /></maths> The velocity of source <i>S_i</i> at time <maths id="math0008"><math display="inline"><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></math><img file="EP2020607A2_D0008.tif" /></maths> is denoted <o ostyle="single">v</o><i>_i</i>.

0025Block 350 is the unit vector <o ostyle="single">e</o><i>_i</i> that points from <o ostyle="single">x</o>* to the source location <i>_{<o ostyle="single">x</o>i}</i>. This unit vector is used in several calculations described ahead.

EXAMPLES OF VALID OBSERVATION FRAMES

0026An example of a valid observation frame is an Earth-centered inertial frame <i>F</i>^eci, where the spatial origin coincides with the center of the Earth and where the Earth rotates around the <i>z</i>-axis with a period of 24 hours (many such frames exist according to how the time origin and the <i>x</i>, <i>y</i>-axis are chosen). In this frame, the receiver's velocity <o ostyle="single">v</o> at the query time is given by the velocity of the Earth's surface near the receiver due to the Earth's rotation plus the relative velocity of the receiver with respect to the Earth's surface.

0027Another example of a valid observation frame is the "locally-Earth-fixed" inertial frame <i>F</i>^lefi(<i>Q</i>) whose origin is the event <i>Q</i> and whose motion "cancels out" the rotational velocity of the Earth's surface near the receiver at the query time. In this frame, the receiver's velocity at the query time is the same as the receiver's velocity with respect to the Earth's surface. More specifically, <i>F</i>^lefi(<i>Q</i>) is defined by the following properties: the spatio-temporal origin of <i>F</i>^lefi(<i>Q</i>) is the event Q; the Earth's surface near the receiver is stationary at the query time in the frame <i>F</i>^lefi(<i>Q</i>); in the Earth-centered inertial frame <i>F</i>^eci, the frame <i>F</i>^lefi(<i>Q</i>) moves with constant velocity at all times; (equivalently, the Earth's center and Earth's axis move with constant velocity in the frame <i>F</i>^lefi(<i>Q</i>)); at the query time, the three spatial axes of <i>F</i>^lefi(<i>Q</i>) are aligned along the longitude, latitude and altitude directions, respectively. It should be noted that <i>F</i>^lefl(<i>Q</i>) and <i>F</i>^eci are inertial with respect to each other, that is, their relative acceleration is zero.

0028One skilled in the art will see that many other reference frames are possible and can be used in connection with this invention.

THE LINEAR PROGRAMMING ENGINE AND THE MULTI-STAGE METHOD

0029<figref idref="f0006">FIG. 4</figref> illustrates one embodiment of a fusion engine based on Linear Programming (LP) that, at any stage, stores and integrates available information and use it to deduce new information to speed-up the future calculations and to refine the estimates of the parameters of interest. One skilled in the art will see how such techniques as the Simplex Method and Interior Point Methods, among others, can be used in LP to maximize and minimize the functions of interest over the uncertainty region. In one embodiment, a stage is defined by which segment of received signal is currently being selected for processing (denoted j in the embodiment of <figref idref="f0002 f0003 f0004">FIG. 2</figref>) and by the number <i>l</i> of sources whose known signals have been processed with the current segment. In one embodiment, this processing consists of correlation calculations and searches.

0030Certain termination conditions can be tested between selected stages to determine whether sufficient information has been gathered. For instance, in some embodiments of this invention, the test is whether the location uncertainty region of the receiver is contained in a box smaller than a certain size. The sides of the box can be determined by minimizing and maximizing the basic location variables over the current uncertainty region. In other embodiments, the test is whether the receiver is inside (or outside) a given region, e.g. a certain city block. One skilled in the art will be able to appropriately formulate many other termination conditions based on the specific application requirements at hand.

0031Block 405 represents the linear coefficients and offsets used by the fusion engine. These coefficients and offsets are calculated once at the outset as described in <figref idref="f0007">FIG. 5</figref> and section "Calculation of the linear coefficients and offsets". They may also be re-calculated one or more times at a new linearization point if the estimate of the receiver parameters becomes significantly different from the current linearization point and if a more accurate linear approximation is needed. One skilled in the art will see how Taylor series residuals and other known techniques for quantifying and bounding linear approximation error can be used with application specific knowledge to determine what constitutes a significant difference.

0032Block 410 represents the information available at the beginning of the method. In some embodiments, 410 contains four pieces of information: an uncertainty region that contains (with a suitably high degree of confidence) the three-dimensional location <o ostyle="single">x</o> of the receiver (block 411); an uncertainty region that contains (with a suitably high degree of confidence) the three-dimensional velocity <o ostyle="single">v</o> of the receiver (block 412); the maximum value of the receiver's clock offset (block 413); and the maximum value of the receiver's clock drift rate (block 414).

0033At block 415, the selected source-segment pair is processed to calculate updated uncertainty intervals for the Doppler shift and code-phase <i>f_i</i> and σ<i>_i</i>. The details of this are in section "Calculation of uncertainty intervals". Block 415 is repeated at every stage of the method.

0034Block 450 is the fusion engine's internal representation of the available information which, in LP embodiments of the fusion engine, consists of a set of linear inequalities, as explained in more details in section "Encoding given information". In some embodiments, linear inequality constraints exist for the three-dimensional location <o ostyle="rightarrow">x</o> of the receiver (block 451); the three-dimensional velocity <o ostyle="single">v</o> of the receiver (block 452); the one-dimensional receiver's clock offset (block 453); and the one-dimensional drift rate of receiver's clock (block 454).

0035Blocks 425 and 426 are the queries submitted by the multi-stage method that searches the selected known signal in the selected segment of received signal. These queries are processed by blocks 465 and 466 that, in the LP embodiment, consist of linear programming optimizations.

0036Block 420 is a set of possible queries about receiver parameters. Typically, these queries are submitted at the end of the multi-stage method when the information about receiver parameters is the most accurate. Or, they can be submitted at certain stages to help decide whether the method should terminate. In some embodiments, block 421 can request the minimum and maximum coordinates of the receiver's location along three orthogonal axes (e.g. longitude, latitude and altitude). Similarly, block 422 can request information about minimum and maximum velocity of the receiver and block 433 can request information about the clock offset of the receiver.

DETERMINING THE LINEARIZATION POINT

0037Block 530 of <figref idref="f0007">FIG. 5</figref> determines an initial coarse estimate of (<i>t,</i><o ostyle="single">x</o>), which will be denoted (<i>t</i>*, <o ostyle="single">x</o>*). For example, if the receiver is connected to a cellular network, <o ostyle="single">x</o>* can be set to be the location of the cell tower that picks up the signal from the receiver and <i>t</i>* can be set to be the query time as measured by the receiver's clock. In general, <i>t</i>* is not exactly the same as the true query time <i>t</i> because of the inaccuracy of the receiver's clock. The event corresponding to the known spatio-temporal coordinate (<i>t</i>*, <o ostyle="single">x</o>*) in the frame F will be denoted <i>Q</i>*.

0038The initial coarse estimate to the receiver's velocity <o ostyle="single">v</o> is denoted <o ostyle="single">v</o>*. For example, if F is chosen to be <i>F</i>^eci, then an approximate value for <o ostyle="single">v</o> is the rotational velocity of the Earth's surface near the receiver. If instead F is a frame in which the Earth is stationary at the query event (for instance, if <i>F</i> = <i>F</i>^lefi(<i>Q</i>*)), one should set <o ostyle="rightarrow">v</o> = 0, unless the receiver is known to be moving in a certain direction with respect to the Earth's surface.

0039Let also <maths id="math0009"><math display="inline"><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup><mo>/</mo><mi>c</mi></math><img file="EP2020607A2_D0009.tif" /></maths> denote a known approximation to the clock's rate υ₀/<i>c</i>. If no information is available on whether the receiver's clock is fast or slow, then one should set <maths id="math0010"><math display="inline"><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup><mo>/</mo><mi>c</mi><mo>=</mo><mn>1.</mn></math><img file="EP2020607A2_D0010.tif" /></maths>

0040The known quantities (<i>t</i>*, <i>x</i>*), and <maths id="math0011"><math display="inline"><mfenced><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup><mo>,</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mfenced></math><img file="EP2020607A2_D0011.tif" /></maths> in the frame F represent a linear space-time trajectory that passes through the approximate query event <i>Q</i>*. This linear trajectory, denoted (<i>Q</i>*, <i>Q*</i>)<i>,</i> is the linearization point used for the equations described in the next section. Within a particular frame F, one can view (<i>Q*, Q*</i>) as a shorthand for its <i>F</i>-coordinates: <maths id="math0012"><math display="block"><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mo>≡</mo><mi>F</mi><mfenced><mi>t</mi><mo>*</mo><mo>,</mo><mi>x</mi><mo>*</mo><mo>,</mo><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup><mo>,</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mfenced><mn>.</mn></math><img file="EP2020607A2_D0012.tif" /></maths> These coordinates are computed at block 530.

LINEAR EXPRESSION FOR CODE-PHASE AND DOPPLER SHIFT

0041The piece of known signal transmitted by source <i>S_i</i> and collected by the receiver begins at a particular point in time which is called the "code-phase" of source <i>S_i</i> is and denoted σ<i>_i</i>(<i>Q</i>). The code-phase σ<i>_i</i>(<i>Q</i>) is the time, as recorded by the source clock, at which the first sample of the collected signal was transmitted by source <i>S_i.</i>

0042Let σ_i(<i>Q</i>*) be the initial estimate of the code-phase, that is, the code-phase that the receiver would see if the query were truly submitted at location <i>x</i>* and time <i>t</i>*. Similarly, <i>J_i</i>(<i>Q,</i><img file="EP2020607A2_D0013.tif" /> ) denotes the Doppler shift seen by the receiver, and <i>f_i</i>(<i>Q*,</i><img file="EP2020607A2_D0014.tif" /> *) denotes the Doppler shift that the receiver would see if its space-time trajectory were truly (<i>Q</i>*,<img file="EP2020607A2_D0015.tif" /> *). By assuming that (<i>Q</i>*,<img file="EP2020607A2_D0016.tif" /> *) is sufficiently close to (<i>Q</i>, <img file="EP2020607A2_D0017.tif" /> ), it is possible to express the differences <i>σ_i</i>(<i>Q*</i>) <i>- σ_i</i>(<i>Q</i>) and <i>f_i</i>(<i>Q*, Q*</i>) <i>- f_i</i>(<i>Q,</i><img file="EP2020607A2_D0018.tif" /> ) in terms of (t - <i>t*, <o ostyle="single">x</o>- <o ostyle="single">x</o></i>*) and <maths id="math0013"><math display="inline"><mfenced><msub><mi>υ</mi><mn>0</mn></msub><mo>-</mo><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup><mo>,</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>-</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mfenced><mn>.</mn></math><img file="EP2020607A2_D0019.tif" /></maths> These linear equations are given by: <maths id="math0014" num="(1)"><math display="block"><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi></mfenced><mo>=</mo><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mo>+</mo><mfenced><mi>t</mi><mo>-</mo><mi>t</mi><mo>*</mo></mfenced><mo>+</mo><mfrac><mn>1</mn><mi>c</mi></mfrac><mo>⁢</mo><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub><mo>⋅</mo><mfenced><mover><mi>x</mi><mo>→</mo></mover><mo>-</mo><mover><mi>x</mi><mo>→</mo></mover><mo>*</mo></mfenced><mo>,</mo></math><img file="EP2020607A2_D0020.tif" /></maths><maths id="math0015" num="(2)"><math display="block"><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>⁢</mo><mover><mi>Q</mi><mo>˙</mo></mover></mfenced><mo>=</mo><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mo>-</mo><mfrac><msub><mi>f</mi><mi>c</mi></msub><mi>c</mi></mfrac><mo>⁢</mo><mfenced><msub><mi>υ</mi><mn>0</mn></msub><mo>-</mo><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup></mfenced><mo>+</mo><mfrac><msub><mi>f</mi><mi>c</mi></msub><mi>c</mi></mfrac><mo>⁢</mo><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub><mo>⋅</mo><mfenced><mover><mi>υ</mi><mo>→</mo></mover><mo>-</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mfenced><mo>+</mo><mfrac><msub><mi>f</mi><mi>c</mi></msub><mi>c</mi></mfrac><mo>⁢</mo><mfrac><mrow><msub><mover><mi>υ</mi><mo>→</mo></mover><mi>i</mi></msub><mo>-</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mrow><msub><mi>r</mi><mi>i</mi></msub></mfrac><mo>⋅</mo><msubsup><mi>P</mi><mi>i</mi><mo>⊥</mo></msubsup><mo>⁢</mo><mfenced><mover><mi>x</mi><mo>→</mo></mover><mo>-</mo><mover><mi>x</mi><mo>→</mo></mover><mo>*</mo></mfenced><mo>,</mo></math><img file="EP2020607A2_D0021.tif" /></maths> where <o ostyle="rightarrow">e</o><i>_i</i> is the unit vector from <o ostyle="rightarrow">x</o>* to the spatial coordinate of source <i>S_i</i> in the frame F (denoted <o ostyle="single">x</o><i>_i</i>), at transmission time: <maths id="math0016" num="(3)"><math display="block"><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub><mo>=</mo><mfrac><mrow><msub><mover><mi>x</mi><mo>→</mo></mover><mi>i</mi></msub><mo>-</mo><mover><mi>x</mi><mo>→</mo></mover><mo>*</mo></mrow><mrow><mo>‖</mo><msub><mover><mi>x</mi><mo>→</mo></mover><mi>i</mi></msub><mo>-</mo><mover><mi>x</mi><mo>→</mo></mover><mo>*</mo><mo>‖</mo></mrow></mfrac><mo>;</mo></math><img file="EP2020607A2_D0022.tif" /></maths><i>r_i</i> denotes the distance <maths id="math0017" num="(4)"><math display="block"><msub><mi>r</mi><mi>i</mi></msub><mo>=</mo><mo>‖</mo><msub><mover><mi>x</mi><mo>→</mo></mover><mi>i</mi></msub><mo>-</mo><mover><mi>x</mi><mo>→</mo></mover><mo>*</mo><mo>‖</mo><mo>;</mo></math><img file="EP2020607A2_D0023.tif" /></maths><i><o ostyle="single">v</o>_i</i> is the velocity of source <i>S_i</i> in the frame F at transmission time; <maths id="math0018"><math display="inline"><msubsup><mi>P</mi><mi>i</mi><mo>⊥</mo></msubsup></math><img file="EP2020607A2_D0024.tif" /></maths> is the projection matrix that projects on the space orthogonal to the vector <o ostyle="single">e</o><i>_i</i> and is defined by <maths id="math0019" num="(5)"><math display="block"><msubsup><mi>P</mi><mi>i</mi><mo>⊥</mo></msubsup><mo>⁢</mo><mover><mi>b</mi><mo>→</mo></mover><mo>=</mo><mover><mi>b</mi><mo>→</mo></mover><mo>-</mo><mfenced><mover><mi>b</mi><mo>→</mo></mover><mo>⋅</mo><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub></mfenced><mo>⁢</mo><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub><mo>,</mo></math><img file="EP2020607A2_D0025.tif" /></maths> where <i><o ostyle="single">b</o></i> is an arbitrary three-dimensional vector; <i>c</i> is the speed of light in vacuum; <i>f_c</i> is the carrier frequency of the known signal; and · denotes the Euclidean inner product of two vectors. Block 555 of <figref idref="f0007">FIG. 5</figref> calculates <o ostyle="single">x</o><i>_i</i>, <i>_{<o ostyle="single">v</o>i}</i> and <maths id="math0020"><math display="inline"><msubsup><mi>P</mi><mi>i</mi><mo>⊥</mo></msubsup><mo>,</mo></math><img file="EP2020607A2_D0026.tif" /></maths> as described in section "Calculation of the linear coefficients and offsets".

0043Equations (1) and (2) can be rewritten as <maths id="math0021" num="(6)"><math display="block"><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi></mfenced><mo>=</mo><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mo>+</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi></math><img file="EP2020607A2_D0027.tif" /></maths><maths id="math0022" num="(7)"><math display="block"><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>⁢</mo><mover><mi>Q</mi><mo>˙</mo></mover></mfenced><mo>=</mo><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mo>+</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>⋅</mo><mi>υ</mi><mo>+</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi><mo>,</mo></math><img file="EP2020607A2_D0028.tif" /></maths> where the new four-dimensional variables <i>x</i> and <i>v</i> are given by: <maths id="math0023" num="(8)"><math display="block"><mi>x</mi><mo>=</mo><mfenced><mi mathvariant="italic">ct</mi><mo mathvariant="italic">-</mo><mi mathvariant="italic">ct</mi><mo>*</mo><mo>,</mo><mover><mi>x</mi><mo>→</mo></mover><mo>-</mo><mover><mi>x</mi><mo>→</mo></mover><mo>*</mo></mfenced></math><img file="EP2020607A2_D0029.tif" /></maths><maths id="math0024" num="(9)"><math display="block"><mi>υ</mi><mo>=</mo><mfenced><msub><mi>υ</mi><mn>0</mn></msub><mo>-</mo><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup><mo>,</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>-</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mfenced></math><img file="EP2020607A2_D0030.tif" /></maths> and the coefficients <maths id="math0025"><math display="inline"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>,</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>,</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup></math><img file="EP2020607A2_D0031.tif" /></maths> are given by: <maths id="math0026" num="(10)"><math display="block"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>=</mo><mfrac><mn>1</mn><mi>c</mi></mfrac><mfenced><mn>1</mn><mo>⁢</mo><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub></mfenced><mo>,</mo></math><img file="EP2020607A2_D0032.tif" /></maths><maths id="math0027" num="(11)"><math display="block"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>=</mo><mfrac><msub><mi>f</mi><mi>c</mi></msub><mi>c</mi></mfrac><mo>⁢</mo><mfenced><mo>-</mo><mn>1</mn><mo>,</mo><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub></mfenced><mo>,</mo></math><img file="EP2020607A2_D0033.tif" /></maths><maths id="math0028" num="(12)"><math display="block"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>=</mo><mfrac><msub><mi>f</mi><mi>c</mi></msub><mi>c</mi></mfrac><mo>⁢</mo><mfrac><mn>1</mn><msub><mi>r</mi><mi>i</mi></msub></mfrac><mo>⁢</mo><mfenced><mn>0</mn><mo>,</mo><mfenced><msub><mover><mi>υ</mi><mo>→</mo></mover><mi>i</mi></msub><mo>-</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mfenced><mo>⁢</mo><msubsup><mi>P</mi><mi>i</mi><mo>⊥</mo></msubsup></mfenced><mn>.</mn></math><img file="EP2020607A2_D0034.tif" /></maths>

0044The linear equations (6) and (7) are valid in any observation frame F' that moves with constant velocity with respect to F, provided that this velocity is sub-relativistic, that is, much smaller than c. One skilled in the art will see that many equivalent embodiments of this invention are obtained by choosing one of these many possible frames.

CALCULATION OF THE LINEAR COEFFICIENTS AND OFFSETS

0045The linear equations used by the fusion engine are obtained by linearizing the kinematic equations of the source's motion with respect to the receiver. This linearization is based on an initial estimate of the receiver location and receiver velocity.

0046In this section a method is provided to calculate the linear coefficients <maths id="math0029"><math display="inline"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>,</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>,</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup></math><img file="EP2020607A2_D0035.tif" /></maths> and the offset parameters σ_i(<i>Q</i>*), and <i>f_i</i>(<i>Q</i>*, <i><o ostyle="dots">Q</o></i>*), which are used for encoding the given information and for deducing the new requested information. Although the description here is for how to calculate these parameters in the frame <i>F</i> = <i>F</i>^eci, one skilled in the art can transform these parameters and perform analogous calculations in any another valid frame. These calculations are illustrated in <figref idref="f0007">FIG. 5</figref>.

0047The first step, block 510, consists in choosing an appropriate observation frame F. Block 520 is the query event, parameterized by four spatio-temporal coordinates (<i>t,<o ostyle="rightarrow">x</o></i>) and four additional kinematic coordinates (<i>v</i>₀, <o ostyle="rightarrow">v</o>) (block 525). Block 530 determines an initial coarse estimate of the receiver parameters.

0048Block 550 calculates the <i>F</i>-time <maths id="math0030"><math display="inline"><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></math><img file="EP2020607A2_D0036.tif" /></maths> at which the signal was emitted by the source. The parameter satisfies the following equation: <maths id="math0031" num="(13)"><math display="block"><mi>t</mi><mo>*</mo><mo>-</mo><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup><mo>=</mo><mfrac><mn>1</mn><mi>c</mi></mfrac><mo>‖</mo><msub><mover><mi>s</mi><mo>→</mo></mover><mi>i</mi></msub><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></mfenced><mo>-</mo><mover><mi>x</mi><mo>→</mo></mover><mo>*</mo><mo>‖</mo><mo>+</mo><msubsup><mi>τ</mi><mi>i</mi><mi mathvariant="normal">a</mi></msubsup><mo>+</mo><msup><mi>τ</mi><mi mathvariant="normal">r</mi></msup><mo>,</mo></math><img file="EP2020607A2_D0037.tif" /></maths> where <maths id="math0032"><math display="inline"><msubsup><mi>τ</mi><mi>i</mi><mi mathvariant="normal">a</mi></msubsup></math><img file="EP2020607A2_D0038.tif" /></maths> are atmospheric delays calculated by using the differential corrections computed by block 545; <img file="EP2020607A2_D0039.tif" /> is the additional delay caused by analog processing at the receiver. The parameter <maths id="math0033"><math display="inline"><msup><mi>τ</mi><mi mathvariant="normal">r</mi></msup></math><img file="EP2020607A2_D0040.tif" /></maths> is obtained from block 548. The function <i><o ostyle="rightarrow">s</o>_i</i>(<i>t_i</i>), stored in the database at block 549, represents the position of source <i>S_i</i> at any F-time <i>t_i</i>. One skilled in the art knows how to implement blocks 545, 548 and 549. Further, one skilled in the art can develop an iterative procedure to calculate the solution <maths id="math0034"><math display="inline"><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></math><img file="EP2020607A2_D0041.tif" /></maths> of equation (13).

0049Once the transmission time <maths id="math0035"><math display="inline"><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></math><img file="EP2020607A2_D0042.tif" /></maths> has been calculated, block 550 calculates source location <o ostyle="rightarrow">x</o><i>_i</i> by letting <maths id="math0036"><math display="block"><msub><mover><mi>x</mi><mo>→</mo></mover><mi>i</mi></msub><mo>=</mo><msub><mover><mi>s</mi><mo>→</mo></mover><mi>i</mi></msub><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></mfenced></math><img file="EP2020607A2_D0043.tif" /></maths> and the source's velocity <o ostyle="rightarrow">v</o>_i, obtained by differentiating the function <o ostyle="rightarrow">s</o>_i(<i>t_i</i>) and evaluating it at <i>t_i</i> = <maths id="math0037"><math display="inline"><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup><mo>:</mo></math><img file="EP2020607A2_D0044.tif" /></maths><maths id="math0038"><math display="block"><msub><mover><mi mathvariant="italic">v</mi><mo>→</mo></mover><mi mathvariant="italic">i</mi></msub><mo>=</mo><msub><mrow><mfrac><mrow><mi mathvariant="italic">d</mi><mo>⁢</mo><msub><mover><mi mathvariant="italic">s</mi><mo>→</mo></mover><mi mathvariant="italic">i</mi></msub><mfenced><msub><mi mathvariant="italic">t</mi><mi mathvariant="italic">i</mi></msub></mfenced></mrow><mrow><mi mathvariant="italic">d</mi><mo>⁢</mo><msub><mi mathvariant="italic">t</mi><mi mathvariant="italic">i</mi></msub></mrow></mfrac><mo>|</mo></mrow><mrow><msub><mi mathvariant="italic">t</mi><mi mathvariant="italic">i</mi></msub><mo>=</mo><msubsup><mi mathvariant="italic">t</mi><mi mathvariant="italic">i</mi><mo>*</mo></msubsup><mn>.</mn></mrow></msub></math><img file="EP2020607A2_D0045.tif" /></maths> Block 555 calculates the parameters <o ostyle="rightarrow">e</o><i>_i</i>, <i>r_i</i> and <maths id="math0039"><math display="inline"><msubsup><mi>P</mi><mi>i</mi><mo>⊥</mo></msubsup></math><img file="EP2020607A2_D0046.tif" /></maths> by using formulas (3), (4) and (5). Block 560 calculates the linear coefficients <maths id="math0040"><math display="inline"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>,</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>,</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup></math><img file="EP2020607A2_D0047.tif" /></maths> by means of the formulas (10-12). Block 580 computes the offset parameter σ<i>_i</i>(<i>Q</i>*), given by: <maths id="math0041" num="(14)"><math display="block"><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mo>=</mo><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup><mo>+</mo><mi>δ</mi><mo>⁢</mo><msubsup><mi>t</mi><mi>i</mi><mi>err</mi></msubsup><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></mfenced></mfenced></math><img file="EP2020607A2_D0048.tif" /></maths> where <maths id="math0042"><math display="inline"><mi>δ</mi><mo>⁢</mo><msubsup><mi>t</mi><mi>i</mi><mi>err</mi></msubsup><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></mfenced></math><img file="EP2020607A2_D0049.tif" /></maths> is a correction to the source's clock. More specifically, <maths id="math0043"><math display="inline"><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></math><img file="EP2020607A2_D0050.tif" /></maths> + <maths id="math0044"><math display="inline"><mi>δ</mi><mo>⁢</mo><msubsup><mi>t</mi><mi>i</mi><mi>err</mi></msubsup><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></mfenced></math><img file="EP2020607A2_D0051.tif" /></maths> is what the source believes the time is at time <maths id="math0045"><math display="inline"><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup><mn>.</mn></math><img file="EP2020607A2_D0052.tif" /></maths> The function <maths id="math0046"><math display="inline"><mi>δ</mi><mo>⁢</mo><msubsup><mi>t</mi><mi>i</mi><mi>err</mi></msubsup><mfenced><msub><mi mathvariant="italic">t</mi><mi mathvariant="italic">i</mi></msub></mfenced></math><img file="EP2020607A2_D0053.tif" /></maths> is stored in the database 579.

0050In the GPS embodiment, since each known signal repeats itself with a period of <i>T_σ</i> = 1<i>ms</i>, the code-phase can also be calculated by the formula <maths id="math0047" num="(15)"><math display="block"><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mo>=</mo><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup><mo>+</mo><mi>δ</mi><mo>⁢</mo><msubsup><mi>t</mi><mi>i</mi><mi>err</mi></msubsup><mfenced><msubsup><mi>t</mi><mi>i</mi><mo>*</mo></msubsup></mfenced></mfenced><mo>⁢</mo><mfenced><mi>mod</mi><mspace width="1em" /><msub><mi>T</mi><mi>σ</mi></msub></mfenced></math><img file="EP2020607A2_D0054.tif" /></maths> where z(mod <i>T_σ</i>) denotes the remainder of the division of z by <i>T_σ.</i> If this formula is used, all additions of code-phase quantities have to be carried out "modulo <i>T_σ",</i> as one skilled in the art can see. This applies to all the formulas that involve code-phase quantities.

0051Block 570 calculates the Doppler shift <i>f_i(Q*,</i><img file="EP2020607A2_D0055.tif" /><i>*)</i> by using the formula: <maths id="math0048" num="(16)"><math display="block"><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mo>=</mo><mo>-</mo><mfrac><msub><mi>f</mi><mi>c</mi></msub><mi>c</mi></mfrac><mo>⁢</mo><msub><mover><mi>e</mi><mo>→</mo></mover><mi>i</mi></msub><mo>⋅</mo><mfenced><msub><mover><mi>υ</mi><mo>→</mo></mover><mi>i</mi></msub><mo>-</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>*</mo></mfenced><mo>-</mo><msub><mi>f</mi><mi>c</mi></msub><mo>⁢</mo><mfenced><mfrac><msubsup><mi>υ</mi><mn>0</mn><mo>*</mo></msubsup><mi>c</mi></mfrac><mo>-</mo><mn>1</mn></mfenced><mn>.</mn></math><img file="EP2020607A2_D0056.tif" /></maths>

0052If at any stage the center of the uncertainty region of the receiver parameters moves significantly from the initial coarse estimate (<i>Q*</i>, <img file="EP2020607A2_D0057.tif" /><i>*</i>), then the center of the uncertainty region can be set to be the new linearization point. This is done by carrying out again the calculations described in this section at the new linearization point. This step can be repeated more than once, as needed.

ENCODING GIVEN INFORMATION

0053At any stage during the application of the method, certain information is available about various unknown parameters and variables. The method is initialized with certain information. Subsequently, and on the basis of the processing of the data samples, additional information can be made available. As the method proceeds, the available information is used to deduce new information (see section "Deducing new information"), and the new information is incorporated in the already available information. This section illustrates, by way of example, some of the types of information that may be available and the manner in which the available information is represented and encoded.

0054In general, a set of information is represented by an uncertainty region representation. In some embodiments, the uncertainty region representation consists of a set of linear inequality constraints <maths id="math0049" num="(17)"><math display="block"><msub><mi>h</mi><mi>k</mi></msub><mo>⋅</mo><mi>x</mi><mo>+</mo><msub><mi>g</mi><mi>k</mi></msub><mo>⋅</mo><mi>υ</mi><mo>≤</mo><msub><mi>b</mi><mi>k</mi></msub><mo>,</mo><mspace width="13em" /><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>K</mi><mo>,</mo></math><img file="EP2020607A2_D0058.tif" /></maths> where K is the number of constraints needed to encode the set of information. These constraints are stored inside the fusion engine, block 430 of <figref idref="f0006">FIG. 4</figref>. In some embodiments, quadratic or other convex constraints are also used. In other embodiments, non-convex constraints are also used including those represented by mixed-integer programs and other combinatorial structures. It should be pointed out that the formulas <maths id="math0050"><math display="block"><msub><mi>h</mi><mi>k</mi></msub><mo>⋅</mo><mi>x</mi><mo>+</mo><msub><mi>g</mi><mi>k</mi></msub><mo>⋅</mo><mi>υ</mi><mo>≤</mo><msub><mi>b</mi><mi>k</mi></msub></math><img file="EP2020607A2_D0059.tif" /></maths> and <maths id="math0051"><math display="block"><mo>-</mo><msub><mi>h</mi><mi>k</mi></msub><mo>⋅</mo><mi>x</mi><mo>-</mo><msub><mi>g</mi><mi>k</mi></msub><mo>⋅</mo><mi>υ</mi><mo>≥</mo><mo>-</mo><msub><mi>b</mi><mi>k</mi></msub></math><img file="EP2020607A2_D0060.tif" /></maths> are equivalent representations of the same constraint. In the following, the most convenient of these two representations will be used for exposition purposes. Code-phase: In one embodiment, code-phase information is represented by an uncertainty interval <maths id="math0052"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>σ</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup></mfenced></math><img file="EP2020607A2_D0061.tif" /></maths> known to contain, with sufficient degree of confidence, the code-phase for a given source observed by the receiver at the query event, σ<i>_i</i>(<i>Q</i>). Whenever the code-phase variables take values in a circular domain, one skilled in the art knows how to make the necessary adjustments to ensure that code-phase uncertainty intervals and code-phase constraints are implemented and interpreted appropriately.

0055Block 456 inside the fusion engine 430 contains the constraints corresponding to the code-phase uncertainty interval <maths id="math0053"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>σ</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup></mfenced><mo>,</mo></math><img file="EP2020607A2_D0062.tif" /></maths> given by: <maths id="math0054" num="(18)"><math display="block"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi><mo>≤</mo><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup><mo>-</mo><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mo>,</mo></math><img file="EP2020607A2_D0063.tif" /></maths><maths id="math0055" num="(19)"><math display="block"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi><mo>≥</mo><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup><mo>-</mo><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mn>.</mn></math><img file="EP2020607A2_D0064.tif" /></maths> The method to calculate <maths id="math0056"><math display="inline"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup></math><img file="EP2020607A2_D0065.tif" /></maths> was described in section "Calculation of the linear coefficients and offsets" (block 560 of <figref idref="f0007">FIG. 5</figref>). Doppler-shift: Doppler-shift information can be represented by an uncertainty interval <maths id="math0057"><math display="inline"><mfenced open="[" close="]"><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>⁢</mo><msubsup><mi>f</mi><mi>i</mi><mi>max</mi></msubsup></mfenced></math><img file="EP2020607A2_D0066.tif" /></maths> and can be encoded by the LP inequality constraints: <maths id="math0058" num="(20)"><math display="block"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi><mo>+</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>⋅</mo><mi>υ</mi><mo>≤</mo><msubsup><mi>f</mi><mi>i</mi><mi>max</mi></msubsup><mo>-</mo><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mo>,</mo></math><img file="EP2020607A2_D0067.tif" /></maths><maths id="math0059" num="(21)"><math display="block"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi><mo>+</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>⋅</mo><mi>υ</mi><mo>≥</mo><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>-</mo><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mn>.</mn></math><img file="EP2020607A2_D0068.tif" /></maths> These are stored in block 455 of the fusion engine 430. The method to calculate <maths id="math0060"><math display="inline"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup></math><img file="EP2020607A2_D0069.tif" /></maths> and <maths id="math0061"><math display="inline"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup></math><img file="EP2020607A2_D0070.tif" /></maths> was described in section "Calculation of the linear coefficients and offsets" (block 560 of <figref idref="f0007">FIG. 5</figref>). Spatial location: Information about the spatial location of the receiver at the query time is represented by a set of inequality constraints of the form <maths id="math0062" num="(22)"><math display="block"><msub><mover><mi>h</mi><mo>→</mo></mover><mi>k</mi></msub><mo>⋅</mo><mover><mi>x</mi><mo>→</mo></mover><mo>≤</mo><msub><mi>b</mi><mi>k</mi></msub><mo>,</mo><mspace width="11em" /><mi>k</mi><mo>=</mo><mn mathvariant="italic">1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>K</mi></math><img file="EP2020607A2_D0071.tif" /></maths> where <o ostyle="rightarrow">x</o> is the three-dimensional spatial component of the four-dimensional variable <i>x</i> = (<i>ct</i>, <o ostyle="single">x</o>). These constraints are stored in block 451 of the fusion engine. In some embodiments, these constraints represent a convex polyhedron or an unbounded region between parallel planes that contains the true receiver's location with suitably high degree of confidence. The values of the parameters <o ostyle="single">h</o><i>_k</i> and <i>b_k</i> are calculated according to what frame of observation F has been chosen. For example, if F is the frame <i>F</i>^lefi(<i>Q</i>*) centered at the approximate location of the receiver and with the axes oriented along the longitude, latitude and altitude directions, then the following six inequalities are used to constrain the receiver in an uncertainty box of size 2<i>X</i>_hor (horizontally) and 2<i>X</i>_ver (vertically): <maths id="math0063" num="(23)"><math display="block"><msub><mi>x</mi><mn>1</mn></msub><mo>≤</mo><msub><mi>X</mi><mi>hor</mi></msub><mo>,</mo><mspace width="8em" /><msub><mi>x</mi><mn>1</mn></msub><mo>≥</mo><mo>-</mo><msub><mi>X</mi><mi>hor</mi></msub><mo>,</mo></math><img file="EP2020607A2_D0072.tif" /></maths><maths id="math0064" num="(24)"><math display="block"><msub><mi>x</mi><mn>2</mn></msub><mo>≤</mo><msub><mi>X</mi><mi>hor</mi></msub><mo>,</mo><mspace width="8em" /><msub><mi>x</mi><mn>2</mn></msub><mo>≥</mo><mo>-</mo><msub><mi>X</mi><mi>hor</mi></msub><mo>,</mo></math><img file="EP2020607A2_D0073.tif" /></maths><maths id="math0065" num="(25)"><math display="block"><msub><mi>x</mi><mn>3</mn></msub><mo>≤</mo><msub><mi>X</mi><mi>ver</mi></msub><mo>,</mo><mspace width="8em" /><msub><mi>x</mi><mn>3</mn></msub><mo>≥</mo><mo>-</mo><msub><mi>X</mi><mi>ver</mi></msub><mo>,</mo></math><img file="EP2020607A2_D0074.tif" /></maths> where <o ostyle="single">x</o> = (x₁, x₂, x₃). In some embodiments, such an uncertainty box can be the uncertainty region associated with the initial coarse estimate of the receiver's location. In other embodiments, the uncertainty region can be represented by an appropriate convex polytope and one skilled in the art will see how such a polytope can be expressed as linear inequality constraints. Velocity: Similarly, information about the velocity of the receiver is encoded by constrains of the form: <maths id="math0066" num="(26)"><math display="block"><msub><mover><mi>g</mi><mo>→</mo></mover><mi>k</mi></msub><mo>⋅</mo><mover><mi>υ</mi><mo>→</mo></mover><mo>≤</mo><msub><mi>b</mi><mi>k</mi></msub><mo>,</mo><mspace width="8em" /><mi>k</mi><mo>=</mo><mn>1</mn><mo>…</mo><mo>,</mo><mi>K</mi><mn>.</mn></math><img file="EP2020607A2_D0075.tif" /></maths> Velocity constraints are stored in block 452 of the fusion engine. For example, if <i>F</i> = <i>F</i>^lefi(<i>Q</i>*), the following inequality constraints are used if the horizontal and vertical velocities of the receiver are known to be less than <i>V</i>_hor and <i>V</i>_ver respectively: <maths id="math0067" num="(27)"><math display="block"><msub><mi>υ</mi><mn>1</mn></msub><mo>≤</mo><msub><mi>V</mi><mi>hor</mi></msub><mo>,</mo><mspace width="8em" /><msub><mi>υ</mi><mn>1</mn></msub><mo>≥</mo><mo>-</mo><msub><mi>V</mi><mi>hor</mi></msub><mo>,</mo></math><img file="EP2020607A2_D0076.tif" /></maths><maths id="math0068" num="(28)"><math display="block"><msub><mi>υ</mi><mn>2</mn></msub><mo>≤</mo><msub><mi>V</mi><mi>hor</mi></msub><mo>,</mo><mspace width="8em" /><msub><mi>υ</mi><mn>2</mn></msub><mo>≥</mo><mo>-</mo><msub><mi>V</mi><mi>hor</mi></msub><mo>,</mo></math><img file="EP2020607A2_D0077.tif" /></maths><maths id="math0069" num="(29)"><math display="block"><msub><mi>υ</mi><mn>3</mn></msub><mo>≤</mo><msub><mi>V</mi><mi>ver</mi></msub><mo>,</mo><mspace width="8em" /><msub><mi>υ</mi><mn>3</mn></msub><mo>≥</mo><mo>-</mo><msub><mi>V</mi><mi>ver</mi></msub><mn>.</mn></math><img file="EP2020607A2_D0078.tif" /></maths> Clock Information about the receiver's clock offset and drift rate are represented by the constrains <maths id="math0070" num="(30)"><math display="block"><msub><mi>x</mi><mn>0</mn></msub><mo>≤</mo><mi mathvariant="italic">cT</mi><mo>,</mo><mspace width="8em" /><msub><mi>x</mi><mn>0</mn></msub><mo>≥</mo><mo>-</mo><mi mathvariant="italic">cT</mi><mo>,</mo></math><img file="EP2020607A2_D0079.tif" /></maths><maths id="math0071" num="(31)"><math display="block"><msub><mi>υ</mi><mn>0</mn></msub><mo>≤</mo><mi mathvariant="italic">cγ</mi><mo>,</mo><mspace width="8em" /><msub><mi>υ</mi><mn>0</mn></msub><mo>≥</mo><mo>-</mo><mi mathvariant="italic">cγ</mi><mo>,</mo></math><img file="EP2020607A2_D0080.tif" /></maths> where T is the maximum clock offset and γ is the maximum drift rate (and x₀ = <i>ct-ct*</i>). These constraints are stored in blocks 453 and 454 respectively.

DEDUCING NEW INFORMATION

0056This section illustrates, by way of example, what kinds of information can be obtained by means of this invention and how to process a query for such information. In some embodiments, information is obtained by solving a set of constrained linear optimization problems, each of which determines a bound on some scalar variable of interest z. Consider a variable z of the form <maths id="math0072" num="(32)"><math display="block"><mi>z</mi><mo>=</mo><msub><mi>z</mi><mn>0</mn></msub><mo>+</mo><mi>h</mi><mo>⋅</mo><mi>x</mi><mo>+</mo><mi>g</mi><mo>⋅</mo><mi>υ</mi><mn>.</mn></math><img file="EP2020607A2_D0081.tif" /></maths> The lower and upper bounds of z are determined by: <maths id="math0073" num="(33)"><math display="block"><msubsup><mi>z</mi><mi>i</mi><mi>min</mi></msubsup><mo>=</mo><msub><mi>z</mi><mn>0</mn></msub><mo>+</mo><munder><mi>min</mi><mrow><mi mathvariant="italic">Hx</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Gυ</mi><mo>≤</mo><mi>b</mi></mrow></munder><mo>⁢</mo><mfenced><mi>h</mi><mo>⋅</mo><mi>x</mi><mo>+</mo><mi>g</mi><mo>⋅</mo><mi>υ</mi></mfenced><mo>,</mo></math><img file="EP2020607A2_D0082.tif" /></maths><maths id="math0074" num="(34)"><math display="block"><msubsup><mi>z</mi><mi>i</mi><mi>max</mi></msubsup><mo>=</mo><msub><mi>z</mi><mn>0</mn></msub><mo>+</mo><munder><mi>max</mi><mrow><mi mathvariant="italic">Hx</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Gυ</mi><mo>≤</mo><mi>b</mi></mrow></munder><mo>⁢</mo><mfenced><mi>h</mi><mo>⋅</mo><mi>x</mi><mo>+</mo><mi>g</mi><mo>⋅</mo><mi>υ</mi></mfenced></math><img file="EP2020607A2_D0083.tif" /></maths> where Hx + <i>Gv ≤ b</i> is a matrix representation of the set of all inequality constraints {<i>h_k</i> · <i>x + gk · v</i>, <i>k</i> = 1, ..., <i>K</i>} that encode the current set of information. In this particular embodiment, the uncertainty region representation is the vector inequality <i>Hx</i> + <i>Gv</i> ≤ <i>b.</i>

0057Block 466 computes code-phase bounds on demand by means of the formulae: <maths id="math0075" num="(35)"><math display="block"><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup><mo>=</mo><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mo>+</mo><munder><mi>max</mi><mrow><mi mathvariant="italic">Hx</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Gυ</mi><mo>≤</mo><mi>b</mi></mrow></munder><mfenced><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi></mfenced></math><img file="EP2020607A2_D0084.tif" /></maths><maths id="math0076" num="(36)"><math display="block"><msubsup><mi>σ</mi><mi>i</mi><mi>min</mi></msubsup><mo>=</mo><msub><mi>σ</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo></mfenced><mo>+</mo><munder><mi>min</mi><mrow><mi mathvariant="italic">Hx</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Gυ</mi><mo>≤</mo><mi>b</mi></mrow></munder><mfenced><msubsup><mi>a</mi><mi>i</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi></mfenced></math><img file="EP2020607A2_D0085.tif" /></maths>

0058Block 465 computes Doppler-shifts bounds by means of the formulae: <maths id="math0077" num="(37)"><math display="block"><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>=</mo><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mo>+</mo><munder><mi>max</mi><mrow><mi mathvariant="italic">Hx</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Gυ</mi><mo>≤</mo><mi>b</mi></mrow></munder><mo>⁢</mo><mfenced><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi><mo>+</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>⋅</mo><mi>υ</mi></mfenced></math><img file="EP2020607A2_D0086.tif" /></maths><maths id="math0078" num="(38)"><math display="block"><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>=</mo><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>Q</mi><mo>*</mo><mo>,</mo><mover><mi>Q</mi><mo>˙</mo></mover><mo>*</mo></mfenced><mo>+</mo><munder><mi>max</mi><mrow><mi mathvariant="italic">Hx</mi><mo mathvariant="italic">+</mo><mi mathvariant="italic">Gυ</mi><mo>≤</mo><mi>b</mi></mrow></munder><mo>⁢</mo><mfenced><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mo>⋅</mo><mi>x</mi><mo>+</mo><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msubsup><mo>⋅</mo><mi>υ</mi></mfenced></math><img file="EP2020607A2_D0087.tif" /></maths>

0059Bounds for other variable of interest such as receiver location, velocity, clock offset and clock drift rate can be obtained in a similar way (blocks 461,462 and 463).

0060In one embodiment, the calculations for solving the min and max optimization problems in the above LP equations can be simplified by neglecting the "cross-term" <maths id="math0079"><math display="inline"><msubsup><mi>a</mi><mi>i</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msubsup><mn>.</mn></math><img file="EP2020607A2_D0088.tif" /></maths> By means of this approximation, the LP equations over the 8-dimensional linear space in (<i>x, v</i>) decompose into two independent spaces in <i>x</i> and <i>v</i> respectively, as one skilled in the art can see, and the optimization problems can be solved separately in these smaller spaces, thus reducing the total amount of calculations.

0061In certain situations, such as in the presence of multipath interference, invalid information associated with one or more sources can result in the above optimization problems not having any solution. These exceptional events can be detected and one skilled in the art can devise a method to be used to determine which sources are providing invalid' information. In some embodiments, one possible method is to test all possible subsets of sources to determine the subset of sources that provides the most consistent subset of associated constraints. Alternatively, one could determine the largest subset of sources whose resulting constraints exceeds a pre-determined level of consistency. One way to measure the consistency of a set of sources is to use a statistical test based on the standard deviation of the receiver parameters, as one skilled in the art will see.

CALCULATION OF UNCERTAINTY INTERVALS

0062Block 415 calculates uncertainty intervals for the code-phase and Doppler shifts by using a function <i>A</i>(<i>f,σ</i>) that expresses the probability that the code-phase σ<i>_i</i>(<i>Q</i>) and Doppler shift <i>f_i</i>(<i>Q,<o ostyle="dots">Q</o>)</i> at the query time have particular values. In some embodiments used for GPS applications, such a function is often called an "ambiguity function". In some embodiments, the ambiguity function <i>A</i>(<i>f,σ</i>) is given by the square magnitude <i>I</i>²(<i>f,σ</i>) + <i>Q</i>²(<i>f,σ</i>) of the complex IQ correlation between the known signal associated with the given source and the selected segment of received signal, modulated at the appropriate frequency <i>f</i> and with the hypothesized delay corresponding to code-phase σ. One skilled in the art knows how to calculate these correlations. Improved techniques to calculate these correlations are described further in U.S. Patent Application No. _,filed on the same day herewith, entitled "Signal Acquisition Using Data Bit Information", by inventors Anant Sahai, Wallace Mann, Andrew Chou and Benjamin Van Roy (Attorney Docket No. 60021-0011), U.S. Patent Application No. _, filed on the same day herewith, entitled "Synthesizing Coherent Correlation Sums at One or Multiple Carrier Frequencies Using Correlation Sums Calculated at a Coarse Set of Frequencies", by inventors Anant Sahai and John Tsitsiklis, (Attorney Docket No. 60021-0012), and U.S. Patent Application No. _, entitled "Extracting Fine-Tuned Estimates from Correlation Functions Evaluated at a Limited Number of Values" by Anant Sahai, John Tsitsiklis, Stefano Casadei, Andrew Chou, Benjamin Van Roy and Jesse Robert Stone, filed on the same day herewith, Attorney Docket No. 60021-0013. The aforementioned U.S. patent applications describe ways of refining these calculations in small neighborhoods.

0063One method to implement block 415 is to determine "nominal" values of code-phase and Doppler shift, <maths id="math0080"><math display="inline"><msubsup><mi>σ</mi><mi>i</mi><mi>nom</mi></msubsup></math><img file="EP2020607A2_D0089.tif" /></maths> and <maths id="math0081"><math display="inline"><msubsup><mi>f</mi><mi>i</mi><mi>nom</mi></msubsup><mo>,</mo></math><img file="EP2020607A2_D0090.tif" /></maths> by locating the maximum of the function <i>A</i>(<i>f,σ</i>). Then uncertainty intervals can be defined by using given risk/safety margins around these nominal values: <maths id="math0082" num="(39)"><math display="block"><msubsup><mi>σ</mi><mi>i</mi><mi>min</mi></msubsup><mo>=</mo><msubsup><mi>σ</mi><mi>i</mi><mi>nom</mi></msubsup><mo>-</mo><msubsup><mi>σ</mi><mi>i</mi><mi>dev</mi></msubsup><mo>,</mo><mspace width="4em" /><msubsup><mi>σ</mi><mi>i</mi><mi>max</mi></msubsup><mo>=</mo><msubsup><mi>σ</mi><mi>i</mi><mi>nom</mi></msubsup><mo>+</mo><msubsup><mi>σ</mi><mi>i</mi><mi>dev</mi></msubsup><mo>,</mo></math><img file="EP2020607A2_D0091.tif" /></maths><maths id="math0083" num="(40)"><math display="block"><msubsup><mi>f</mi><mi>i</mi><mi>min</mi></msubsup><mo>=</mo><msubsup><mi>f</mi><mi>i</mi><mi>nom</mi></msubsup><mo>-</mo><msubsup><mi>f</mi><mi>i</mi><mi>dev</mi></msubsup><mo>,</mo><mspace width="4em" /><msubsup><mi>f</mi><mi>i</mi><mi>max</mi></msubsup><mo>=</mo><msubsup><mi>f</mi><mi>i</mi><mi>nom</mi></msubsup><mo>+</mo><msubsup><mi>f</mi><mi>i</mi><mi>dev</mi></msubsup><mo>,</mo></math><img file="EP2020607A2_D0092.tif" /></maths> where <maths id="math0084"><math display="inline"><msubsup><mi>σ</mi><mi>i</mi><mi>dev</mi></msubsup></math><img file="EP2020607A2_D0093.tif" /></maths> and <maths id="math0085"><math display="inline"><msubsup><mi>f</mi><mi>i</mi><mi>dev</mi></msubsup></math><img file="EP2020607A2_D0094.tif" /></maths> denote here given values of the risk/safety margins. For example, in some embodiments, a code-phase margin of 1<i>µsec</i> can be used, and a Doppler-shift margin of one cycle (2π) divided by the duration of the collected signal can be used. Alternatively, one skilled in the art can adjust these margins according to the height of the peak in the function <i>A</i>(<i>f,</i>σ), with smaller margins chosen for larger heights of the peak.

0064If the given function <i>A</i>(<i>f</i>,σ) represents or is proportional to a modeled probability density, then one skilled in the art will see that another method to determine uncertainty intervals is to use statistical techniques to define the margins <maths id="math0086"><math display="inline"><msubsup><mi>σ</mi><mi>i</mi><mi>dev</mi></msubsup></math><img file="EP2020607A2_D0095.tif" /></maths> and <maths id="math0087"><math display="inline"><msubsup><mi>f</mi><mi>i</mi><mi>dev</mi></msubsup></math><img file="EP2020607A2_D0096.tif" /></maths> around the nominal values in such a way that the confidence that these intervals contain the true value of code-phase and Doppler-shifts is above a suitable threshold.

0065Another method is to choose the convex hull of all the code-phase values and Doppler shift values for which <i>A</i>(<i>f</i>,σ) is above a certain threshold. This threshold can be given a-priori, or it can be determined according to the peak value of <i>A</i>(<i>f,σ</i>) (for example, a certain fraction of the peak value, or the peak value minus a certain constant) or it can be specified by using a confidence threshold. One skilled in the art will see that there are many ways of determining an interval from the observations.

0066In some situations it is appropriate to provide only an upper bound to the code-phase. For example, if the function <i>A</i>(<i>f,σ</i>) contains multiple large peaks or other indications of significant multipath interference, then the largest peak might be due to a reflected path. In this case, the code-phase of this peak provides an upper bound to the value of the true code-phase which always corresponds to the direct path.

0067In some embodiments, if the signal search in the segment is judged to be inconclusive then the uncertainty intervals corresponding to this signal source and segment is set to large intervals or the constraints associated with the signal source are simply removed from the representation. One skilled in the art will see that a search can be judged to be inconclusive for many reasons depending on the application requirements, but one such way is for the magnitude of the correlations to all be below a given threshold in the region being searched. This threshold can be determined by many means. In some embodiments, the threshold is determined by considering the probability of false acquisition and adjusting the size of the threshold based on the size of the range of signal parameters being searched over so as to keep the probability of false acquisition suitably small.

0068Regardless of what method is used to calculate uncertainty intervals for σ<i>_i</i> and <i>f_i</i>, these intervals can be improved in some embodiments by taking into account the error due to the linear approximation made. This extra width, that needs to be added the uncertainty intervals, can be determined by calculating an upper bound to the magnitude of the non-linear terms neglected in the linear approximation. One skilled in the art can see that this upper bound can be calculated in many possible ways. In some embodiments, the code-phase uncertainty interval can be corrected for non-linear terms by increasing it on each side by the following amount: <maths id="math0088" num="(41)"><math display="block"><mfrac><mn>1</mn><mi>c</mi></mfrac><mo>⁢</mo><mfenced><mfrac><msup><mi>R</mi><mn>2</mn></msup><mrow><mi>R</mi><mo>+</mo><msub><mi>r</mi><mi>i</mi></msub></mrow></mfrac><mo>+</mo><mi>T</mi><mo>⁢</mo><msub><mi>υ</mi><mi>i</mi></msub></mfenced><mo>,</mo></math><img file="EP2020607A2_D0097.tif" /></maths> where R is the maximum distance from the linearization point to the receiver; <i>r_i</i> is the distance from the linearization point to source <i>S_i</i>; <i>v_i</i> is the magnitude of the source velocity; and T is maximum clock offset of the receiver.

HARDWARE OVERVIEW

0069An embodiment of the invention may be implemented using a computer system that includes a processor for processing information. The Computer system also includes a main memory, such as a random access memory (RAM) or other dynamic storage device, coupled to a bus for storing information and instructions to be executed by the processor. The main memory also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by the processor. The computer system further includes a read only memory (ROM) or other static storage device coupled to the bus for storing static information and instructions for the processor. A storage device, such as a magnetic disk or optical disk, is provided and coupled to the bus for storing information and instructions.

0070The invention is related to the use of the computer system for implementing the techniques described herein. According to one embodiment of the invention, those techniques are implemented by the computer system in response to the processor executing one or more sequences of one or more instructions contained in main memory. Such instructions may be read into the main memory from another computer-readable medium, such as the storage device. Execution of the sequences of instructions contained in the main memory causes the processor to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in the main memory. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

0071The term "computer-readable medium" as used herein refers to any medium that participates in providing instructions to the processor for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as the storage device. Volatile media includes dynamic memory, such as the main memory. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise the bus. Transmission media can also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications.

0072Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave as described hereinafter, or any other medium from which a computer can read.

0073Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions to the processor for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system can receive the data on the telephone line and use an infrared transmitter to convert the data to an infrared signal. An infrared detector coupled to the bus can receive the data carried in the infrared signal and place the data on the bus. The bus carries the data to the main memory, from which the processor retrieves and executes the instructions. The instructions received by the main memory may optionally be stored on the storage device either before or after execution by the processor.

0074The computer system also includes a communication interface coupled to the bus. The communication interface provides a two-way data communication coupling to a network link that is connected to a local network. For example, the communication interface may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, the communication interface may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, the communication interface sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

0075The network link typically provides data communication through one or more networks to other data devices. For example, the network link may provide a connection through the local network to a host computer or to data equipment operated by an Internet Service Provider (ISP). The ISP in turn provides data communication services through the worldwide packet data communication network now commonly referred to as the "Internet". The local network and the Internet both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on the network link and through the communication interface, which carry the digital data to and from the computer system, are exemplary forms of carrier waves transporting the information.

0076The computer system can send messages and receive data, including program code, through the network(s), the network link and the communication interface. In the Internet example, a server might transmit a requested code for an application program through the Internet, the ISP, the local network and the communication interface. In accordance with the invention, one such downloaded application implements the techniques described herein.

0077The received code may be executed by the processor as it is received, and/or stored in the storage device, or other non-volatile storage for later execution. In this manner, the computer system may obtain application code in the form of a carrier wave.

0078In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. A first aspect of the present invention is a method for determining one or more target receiver parameter values wherein the one or more target receiver parameter values is a member of a set of receiver parameter values that are associated with a receiver, the method comprising the computer-implemented steps of: step A: receiving from the receiver, sampled data associated with a received signal that is received at the receiver; step B: dividing the sampled data into a set of overlapping data segments; step C: receiving a set of information that is associated with the set of receiver parameter values and a set of signal parameter values; step D: determining a current region of uncertainty for the set of receiver parameter values using the set of information; step E: selecting a data segment that has not been previously selected to be a selected data segment and performing the steps of: step F selecting a signal source that has not been previously selected to be a selected signal source, wherein the signal source is from a set of signal sources associated with the received signal; step G: forming a selected data segment-source pair comprising the selected data segment and the selected signal source; step H: for the selected segment-source pair, determining in the current region of uncertainty one or more ranges of interest that correspond to the one or more target receiver parameter values; step I: using the selected segment-source pair and using the one or more ranges of interest that correspond to the one or more target receiver parameter values, determining one or more optimized functions that correspond to the receiver parameter values and the signal parameter values; step J: updating the current region of uncertainty using the one or more optimized functions; and step K: repeating steps E through K until the current region of uncertainty satisfies a pre-determined termination condition.

0079A second aspect of the present invention is the method of the first aspect, wherein using the one or more optimized functions involves expressing the one or more optimized functions as inequalities.

0080A third aspect of the present invention is the method of the first or second aspect, wherein the set of information that is associated with the set of receiver parameter values and the set of signal parameters comprises linear inequalities, wherein the linear inequalities restrict the receiver parameter values and the signal parameter values.

0081A fourth aspect of the present invention is the method of one of the first to third aspects, wherein the set of information that are associated with the set of receiver parameter values and the set of signal parameters comprises non-linear inequalities, wherein the non-linear inequalities restrict the receiver parameter values and the signal parameter values.

0082A fifth aspect of the present invention is the method of one of the first to fourth aspects, wherein the set of information that is associated with the set of receiver parameter values and the set of signal parameters are received from one or more systems that uses techniques to solve for a location of the receiver.

0083A sixth aspect of the present invention is the method of one of the first to fifth aspects, wherein the set of receiver parameter values comprises: a location of the receiver; a velocity of the receiver; a clock Doppler of the receiver; and a starting time when the received signal is received at the receiver.

0084A seventh aspect of the present invention is the method of one of the first to sixth aspects, wherein the set of signal parameter values comprises: a delay value associated with the received signal; and a carrier frequency value associated with the received signal.

0085An eighth aspect of the present invention is the method of one of the first to seventh aspects, further comprising the steps of: determining a selected set of signal parameter values contained in this uncertainty region for selected source; searching in the selected segment-source pair for the known signal corresponding to the selected source, by means of hypothesizing all the signal parameter values in the selected set of signal parameter values.

0086A ninth aspect of the present invention is the method of one of the first to eighth aspects, wherein the set of overlapping data segments comprises a nested sequence of data segments of increasing length; and the selected data segment is greater in length than a previously selected segment.