HK1082043A

HK1082043A - Procedure for searching for position determination signals using a plurality of search modes

Info

Publication number: HK1082043A
Application number: HK06102212.2A
Authority: HK
Inventors: D‧N‧罗维奇; C‧帕特里克
Original assignee: 高通股份有限公司
Priority date: 2002-10-22
Filing date: 2003-10-22
Publication date: 2006-05-26

Description

Method for searching for a positioning signal using multiple search modes

Technical Field

The present invention relates to the field of positioning and GPS global positioning systems, and more particularly to a process for searching for a positioning signal using search modes with different sensitivities and fixed times.

Background

The GPS global positioning system is a system of earth-orbiting satellites in which the entities in view of the satellites can determine their position from the satellites. Each satellite transmits a signal marked with a repeating pseudo-random noise (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 duration of 20ms in the modulated signal.

Fig. 1 illustrates one application of the GPS global positioning system whereby a subscriber station 100 in a wireless communication system receives transmissions from satellites 102a, 102b, 102c, 102d in view of the subscriber station and derives time measurements from four or more transmissions. The station provides the measurements to a Position Determination Entity (PDE)104, which determines the position of the station from the measurements. Alternatively, subscriber station 100 may determine its own location from this information.

Subscriber station 100 searches for a transmission from a particular satellite by correlating the PN code of the satellite with the received signal. The received signal is typically a composite of transmissions from one or more satellites in view of the station's receiver in the presence of noise. The correlation is performed over a code phase hypothesis range, known as the code phase search window WCP, and over a doppler frequency hypothesis range, known as the doppler search window WDOPP. The code phase hypothesis is typically expressed as a PN code phase shift range, while the doppler frequency hypothesis is typically expressed as a doppler frequency bin (bin).

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 the number of coherent integrations that are non-coherently combined.

For a particular PN code, the correlation values are associated with the corresponding PN code phase shift and doppler bins to define a two-dimensional correlation function. Any peaks of the correlation function are located and compared to a predetermined noise threshold. The threshold is selected so that the false alarm probability (the probability of falsely detecting a satellite transmission) is at or below a predetermined value. A time measurement for the satellite is derived from the location of the earliest non-sidelobe peak along the code-phase dimension that equals or exceeds the threshold. A doppler measurement for the subscriber station may be derived from the location of the earliest non-sidelobe peak along the doppler frequency dimension that equals or exceeds the threshold.

Current subscriber station architectures place significant constraints on the process of searching for location signals. For example, in one shared radio frequency architecture, the core radio frequency circuitry in the subscriber station is shared between the GPS position location receive path and the voice/data communications transmit and receive path. Thus, the time during which the subscriber station performs the GPS location function interferes with the ability of the subscriber station to perform the voice/data communication function. To reduce this interference to an acceptable level, the GPS frequency tuning time (i.e., the time that the subscriber station listens to the GPS frequency in order to perform the GPS location function) is typically limited to a specified period, e.g., 1 or 2 seconds.

Due to constraints such as this, and the wide dynamic range typically exhibited by GPS positioning signals, it is difficult to perform a search for positioning signals in the allotted time and it is also difficult to achieve an accurate position fix. If the search is performed within a specified time period, the location of the results is often inaccurate. The allocation time is often exceeded if the search is performed accurately fixed.

Disclosure of Invention

One method describes searching for a positioning signal using a plurality of progressively more sensitive search patterns. In a first embodiment, the plurality of search modes includes, with increasing sensitivity: a first level mode, a second level mode, and at least one higher level mode. In this embodiment, the method begins by determining whether any search window parameters exceed a prescribed limit. If so, a first level search is performed and the search window parameters are refined based on the resulting search results to bring them within prescribed limits. If none of the search window parameters exceed the prescribed limit, the first level search is avoided.

A second level search is then performed as part of the position fix attempt. The measurement values are derived from subsequent search results. If the measurements satisfy one or more selected measurement sufficiency criteria, additional searches within the location fix attempt are avoided.

If the measurements do not satisfy one or more selected measurement sufficiency criteria, a higher level search is conducted beyond the second level. In one embodiment, a selection is made between the third level and fourth level searches based on defined selection criteria. In one implementation, if the criteria are met, a third level search is implemented, and if the criteria are not met, a fourth level search is implemented.

In a second embodiment, the plurality of search modes includes, with increasing sensitivity: a first stage mode, a second stage mode, and a third stage mode. In this embodiment, the method begins by performing a first level search as part of a position fix attempt.

One or more measurements are then derived from the subsequent search results. It is determined whether the measurement satisfies one or more selected measurement sufficiency criteria.

If the measurements satisfy one or more selected measurement sufficiency criteria, additional searches within the location fix attempt are avoided.

If the measurements do not satisfy one or more selected measurement sufficiency criteria, a higher level search is performed that exceeds the first level. In this embodiment, the higher level search is a second level or third level search based on one or more specified selection criteria.

A memory tangibly embodying the above method is also described.

Similarly, systems related to the above-described methods are described.

Drawings

The components in the figures are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention. In the drawings, like reference numerals designate corresponding parts throughout the different views.

FIG. 1 is a schematic diagram of a GPS global positioning system.

FIG. 2 is a method for searching for a position location signal using a plurality of progressively more sensitive search patterns in accordance with the present invention

A flow chart of an embodiment.

FIG. 3 illustrates an example of polygons formed from measurements resulting from a level 1 search.

Fig. 4 is a flow chart of an embodiment of a method for searching for a position location signal using a plurality of progressively more sensitive search modes according to the present invention, wherein the plurality of search modes includes level 0, level 1, level 2, and level 3 search modes in accordance with increasing sensitivity.

Fig. 5 is a flow diagram of a level 0 search in the implementation example of fig. 4.

Fig. 6 is a flow diagram of a level 1 search in the implementation example of fig. 4.

Fig. 7 is a flow diagram of a level 2 search in the implementation example of fig. 4.

Fig. 8 is a flow diagram of a 3-level search in the implementation example of fig. 4.

FIG. 9 is a flow chart of measurement sufficiency criteria used in the level 1 search of FIG. 6.

Fig. 10 is a flow chart of the level 2/level 3 selection criteria used in the implementation example of fig. 4.

FIG. 11 is a table identifying parameters governing the level 0, level 1, level 2, and level 3 search modes in the implementation example of FIG. 4.

Figures 12A-12B illustrate a segmentation method used in the implementation example of figure 4 whereby the two-dimensional domain of the GPS satellite search is divided into a plurality of segments, each segment characterized by a doppler frequency range and a code phase range.

Fig. 13 is a block diagram of an embodiment of a system for searching for a position location signal using a plurality of progressively more sensitive search patterns in accordance with the present invention.

Figure 14 is a block diagram of one embodiment of a subscriber station that embodies or incorporates the system of figure 13.

Detailed Description

As used herein, terms such as "about" and "substantially" mean that some allowable error is allowed in mathematical accuracy to account for commercially acceptable allowable errors. Thus, any deviation in the value of 1% to 20% upward or downward from the value modified by the terms "about" or "substantially" should be considered to be expressly within the stated range of values.

Furthermore, the term "software" as used herein includes source code, assembly language code, binary code, hardware, macro-instructions, micro-instructions, etc., or any combination of two or more of the foregoing.

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, etc., or any combination of two or more of the foregoing.

The term "processor" or "CPU" refers to any device capable of executing a series of instructions and includes, without limitation, general or special purpose microprocessors, finite state machines, controllers, computers, Digital Signal Processors (DSPs), and the like.

The terms "space vehicle" and the abbreviation "SV" both refer to GPS satellites.

Fig. 2 is a flow chart of an embodiment of a method for searching for a positioning signal using a plurality of progressively more sensitive search modes according to the present invention, the search modes including a level 0 mode, a level 1 mode, and at least one higher level mode, in accordance with increasing sensitivity. This particular embodiment and the related implementations illustrated in fig. 4-10 discard the timing constraints imposed by the shared radio frequency architecture on the time during which the subscriber station is allowed to tune to the GPS frequency, but it should be understood that: the invention is not limited in this regard and encompasses applications to dual radio frequency (unshared) architectures that do not impose such constraints.

In one example, the method IS performed by an entity seeking to determine a location, such as a subscriber station in an IS-801 compliant wireless communication system. The PDE provides Acquisition Assistance (AA) to the subscriber station: indicating which SVs may be visible to the subscriber station. These SVs form a group N_TOT. In a second example, AA is unavailable and group N_TOTConsists of all SVs in the GPS global positioning system. In a third example, the subscriber station accesses the latest calendar along with approximate time measurements and coarse information of its own location. From this information, the subscriber station predicts which SVs are in view of it. These SVs form group N in this example_TOT。

Group N_TOTIs associated with two-dimensional domain search window parameters that define the code phase and doppler frequency hypotheses for the SV search. In one implementation illustrated in FIG. 12A, the search window parameters for an SV include a code phase search window SIZE WIN _ SIZE_CPA code phase window center WIN _ CENT_CPA Doppler search window SIZE WIN _ SIZE_DOPPAnd a Doppler window center WIN _ CENT_DOPP. In the case where the entity seeking to determine position IS a subscriber station in an IS-801 compliant wireless communication system, these parameters are indicated by acquisition assistance provided to the subscriber station by the PDE.

The method begins at step 202, which includes determining whether any of the search window parameters exceed a prescribed limit. In one embodiment, step 202 includes determining group N_TOTWhether any search window for a SV in (m) exceeds a specified size limit. This may occur, for example, if a new base station is added to a network but not to the PDE base station almanac. One PDE providing an AA to a subscriber station served by the base station in this case sets the code phase search window size to a maximum of 1,023 chips for all SVs. This magnitude code phase search window may be introduced during a level 1 searchA timeout condition is initiated. The purpose of step 202 in this example is to determine which SVs, if any, are associated with those search windows that would cause a timeout condition.

If any of the search window parameters exceed the prescribed limits, step 204 is performed. Step 204 includes performing a level 0 search. In one example, only group N_TOTThose SVs with a mid-code phase search window size exceeding a predetermined threshold perform a level 0 search.

Step 206 follows step 204. In step 206, the search window parameters are refined based on the subsequent search results to bring them within the prescribed limits. In one example where only SVs having a code phase search window exceeding a predetermined threshold are searched, this step includes: locating the maximum peak of a given PN code, modifying the window center so that it is located at the peak, and reducing the window size so that the SV search can be accommodated by a single pass through the correlator. This step may also involve re-centering and reducing the size of the doppler frequency search window.

From step 206, the method performs step 208, which includes conducting a level 1 search as part of the location fix attempt. The level 1 search is a more sensitive search than the level 0 search. Thus, in one implementation, the integration time for implementing this search exceeds the integration time of the level 0 search.

[0044] From step 208, the method continues to step 210. In step 210, measurements are derived from subsequent search results. In one example, the measurements include the signal-to-noise ratio (SNR) and code phase (time) for each discernable peak. In one implementation example, the derived SNR is the peak carrier to noise ratio (C/NO).

From step 210, the method continues to query step 212. In step 212, it is determined whether the measurements resulting from the level 1 search satisfy one or more selected measurement sufficiency criteria. If the measurement satisfies one or more criteria for selected measurement sufficiency, additional searches within the position fix attempt are avoided.

If the measurements do not meet one or more selected measurement sufficiency criteria, step 214 is performed. In step 214, a higher level search for the location signal is performed. A higher level search is a more sensitive search than a level 1 search. Therefore, the integration time used in this search is longer than that used in the level 1 search.

In one implementation, the interrogation step 212 is performed by comparing the SNR measurements from the level 1 search with a first noise threshold T₁A comparison is made to begin. Determining a noise threshold T₁Such that the false alarm probability is below a predetermined level. Exceeding a noise threshold T₁Those SVs of form a group N.

The SNR measurement from the level 1 search is also compared to a second, stronger threshold T₂And (4) comparing. Exceeds a threshold value T₂Those SVs of (a) form group S. Group S' is defined as group N_TOTExcept for SV other than S.

In one example, if the number of SVs in group S | is equal to group N_TOTSV number in | N_TOTIf, then the higher level search is avoided, indicating that all SVs being searched satisfy the stronger threshold T₂。

In a second example, a polygon is formed from the measurements of SVs in set N. For each of these SVs, the carrier signal-to-noise ratio (C/N) is determined by the satellite azimuth and peak_O) Forming a vector. Those vectors are oriented in a coordinate system. The endpoints of those vectors are connected to define a polygon. In this implementation, if the area A of the polygon equals or exceeds the threshold A_TThen the second search is avoided.

Fig. 3 illustrates an example of a polygon defined by five vectors 300a, 300b, 300c, 300d, and 300 e. Each of these vectors represents or corresponds to a measurement value. More specifically, the angle between the vector and the vertical axis is the azimuth of the SV, while the magnitude of the vector is the peak carrier signal-to-noise ratio (C/N)_O). The endpoints of the vectors are identified by numerals 302a, 302b, 302c, 302d, and 302 e. The one defined by the endpointsThe polygon is identified by numeral 306. The area of this polygon determined using known techniques is used in the comparison described above.

In a third example, if the number of SVs in a group N | equals or exceeds a threshold N_EEThen higher level searching is avoided.

In a fourth example, the peak carrier signal-to-noise ratio (C/N) for each SV in set N_O) Are added. If this sum equals or exceeds a predetermined threshold, then higher level searching is avoided.

In a fifth example, a combination of any two or more of the above examples is used to determine whether a higher level search is to be avoided.

Fig. 4 illustrates an example of an implementation of a method for searching for a location signal using a plurality of progressively more sensitive search patterns. In this example of implementation, the entity requesting the determination of the location IS a subscriber station in an IS-801 compliant wireless communication system.

The search modes used in this example include a level 0 mode, a level 1 mode, a level 2 mode, and a level 3 mode in order of increasing sensitivity. In one example, the parameters governing each of these modes are shown in FIG. 11. As can be seen, in this example, the total integration time utilized in mode 0 is 20ms, consisting of one 20ms coherent integration; the total integration time utilized in mode 1 is 80ms, consisting of four 20ms coherent integrations that are incoherently combined; the total integration time utilized in mode 2 is 880ms, consisting of 44 20ms coherent integrations of the non-coherent combination; while the total integration time utilized in mode 3 is 1760ms, consisting of 22 80ms coherent integrations of the non-coherent combination. Since sensitivity is proportional to the total integration time, the sensitivity of the mode also gradually increases. In the example shown, the sensitivity of mode 0 is 31.0 dB-Hz; the sensitivity of mode 1 is 26.4 dB-Hz; the sensitivity of mode 2 is 19.2 dB-Hz; and the sensitivity of mode 3 is 15.45 dB-Hz.

The method begins at step 402. In this step, the subscriber station is in group N from one PDE_TOTAcquire acquisition assistance for each SV in the set. This acquisition assists in indicating a code phase window size, a code phase window center, a doppler frequency window size and a doppler frequency window center for each such SV. Note that: sensitivity assistance, although available, is not requested at this time since it involves a large overhead and since it is not needed for coherent integration times of 20ms or less (utilized in level 0, 1 and 2 search modes).

The method then continues to step 404. In step 404, group N is queried_TOTWhether any SV in (a) has a code phase window size that exceeds a predetermined threshold.

In one configuration, the predetermined threshold is set to identify SVs: the code phases of these SVs are such that they cannot be searched by a single pass through the correlator. Consider, for example, a correlator with eight (8) parallel channels, 32 chip capacity per channel, and several chip overlaps between channels. If the code phase search window is less than or equal to about 200 chips (a number derived from 256 chips minus the overhead due to overlap between channels, 256 chips being the assumed correlator nominal capacity), then an SV can be searched with a single pass correlator. Thus, in this configuration, those SVs with a code phase window exceeding 200 chips are searched in a level 1 search. It should be understood, however: this threshold is highly implementation dependent and therefore will vary depending on the implementation.

In step 404, if group N_TOTWhere none of the SVs have a code phase window exceeding the predetermined threshold, the method jumps to step 408. If any of the SVs have a code phase window that exceeds the threshold, step 406 is performed. In step 406, the method comprises: with respect to group N_TOTEach SV for which the mid-code phase search window exceeds the threshold performs a level 0 search.

For each SV searched in the level 0 search, the largest peak in the resulting correlation function is located. The code phase window center of an SV is then set to the code phase associated with the maximum peak of that SV. The code phase window size of the SV is also reduced so as to enable the SV to be detected again using a single segment search. Assistance data from any SVs not detected in the level 0 search is deleted so that these SVs are not searched at the subsequent search level.

From step 406, the method continues to step 408. In step 408, the method relates to group N_TOTPerforms a level 1 search for all SVs in (1). In this step, the selected measurement sufficiency criterion is also applied to the measurements derived from the search results, and a flag is set if the selected measurement sufficiency criterion is met. These measurement sufficiency criteria will be explained later with respect to fig. 9.

As part of step 408, the measurements resulting from the level 1 search are divided into three categories: strong, weak and none. In one example, such sorting is performed using a swing-hold (hold) operation. First threshold value T₁Is used to identify peaks in the weak category, and a second, more stringent, threshold T₂Is used to identify peaks in the strong category. SVs in the weak category form a group N, while SVs in the strong category form a group S. Group S' is defined as group N_TOTExcept for those SVs in group S. Note that: similar wobble-holds are also performed in level 2 and level 3 searches, and if a strong peak is identified in either of these searches (which was not previously identified in the level 1 search), the set S may be incremented.

In one configuration shown in the table of FIG. 11, a threshold T applied to identify weak peaks in Pattern 1₁Is 25.0 dB-Hz. In this configuration, the threshold T₂As a function of one of three fixed times relative to the user-selected accuracy/sensitivity option. More specifically, the threshold T of the first, second and third options₂Are set to 29.4dB-Hz, 32.4dB-Hz, and ∞, respectively. The latter refers to an arrangement: it is so large that the threshold value T is₂Will never be satisfied.

Step 410 follows step 408. In step 410, a flag indicating the application status of the measurement sufficiency criteria selected in step 408 is checked. If set, indicating that the selected measurement sufficiency criteria are met, the method continues to step 420. In step 420, the measurements resulting from the level 1 search are reported to the PDE, which determines the location of the subscriber station based thereon. Alternatively, the subscriber station determines its own position from these measurements. If not set, indicating that the selected measurement sufficiency criterion is not met, the method jumps to step 412.

In step 412, the method applies predetermined selection criteria to determine whether a level 2 search or a level 3 search should be performed. These selection criteria will be explained later with respect to fig. 10. If level 2 is selected, the method continues with step 414. If layer 3 is selected, the method jumps to step 416.

In step 414, a level 2 search is performed for those SVs in set S'. Since acceptable measurements are deemed to have been obtained for these SVs in the level 1 search, the SVs in set S are not searched. From step 414, the method continues to step 420. In step 420, measurements from the level 2 search and any level 1 measurements of SVs in the set S are reported to the PDE. In response, the PDE determines the location of the subscriber station from these measurements. Alternatively, the subscriber station determines its own position from these measurements.

In step 416, the subscriber station requests sensitivity assistance from the PDE to account for bit phase changes that occur within the 80ms coherent integration time used in the 3-level search. As discussed, this step is delayed to date to avoid incurring the overhead of sensitivity assistance in the case when a level 3 search is not needed or selected.

From step 416, the method continues to step 418. In step 418, the method performs a level 3 search for those SVs in set S'. Also, the SVs in set S are not searched since acceptable measurements have been obtained for these SVs in the level 1 search.

Step 420 follows step 418. In step 420, measurements from the level 3 search and any level 1 measurements of SVs in the set S are reported to the PDE. In response, the PDE determines the location of the subscriber station. Alternatively, the subscriber station determines its own position from these measurements.

FIG. 5 illustrates tasks or sub-steps that underlie the level 0 search (block 406) in FIG. 4. In task 502, those SVs in group NTOT having a code phase window size exceeding a predetermined threshold are identified. In one example discussed earlier, the predetermined threshold is 200 chips, but it should be understood that: this threshold is highly implementation dependent and other values depending on the implementation are possible.

In task 504, one of the SVs is selected, and in task 506, a code phase window of the selected SV is increased as necessary such that the code phase search space of the SV comprises an integer number of slices. For the purposes of this disclosure, a slice refers to a code phase space that can be searched by a single pass through the correlator. In one example where the correlator comprises 8 parallel channels (each having a capacity of 32 chips), the size of a slice is 256 chips. In this example, the code phase is incremented to account for the 4 chip overlap between adjacent segments, and then further incremented and re-centered until a total of K x 8 segments are included, where K is an integer. However, it should also be understood that: this example is implementation dependent, and other examples are possible.

Task 508 follows task 506. In task 508, the search space for the SV is partitioned into segments to accommodate a level 0 search. Fig. 12A and 12B illustrate this segmentation method in more detail.

FIG. 12A illustrates a two-dimensional search space for one SV. In this example, the code phase axis is the horizontal axis and the doppler frequency axis is the vertical axis, but this allocation is random and can be reversed. The center of the code phase search window is called WIN _ CENT_CPAnd the SIZE of the code phase search window is called WIN _ SIZE_CP. The center of the Doppler frequency search window is called WIN _ CENT_DOPPAnd the SIZE of the Doppler frequency search window is called WIN _ SIZE_DOPP。

The search space is partitioned into a plurality of segments 1202a, 1202b, 1202c, each of which is characterized by a doppler frequency range and a code phase range. In one example shown in the table of fig. 11, the frequency range associated with one segment is 250Hz for the 0-level, 1-and 2-level search patterns and 62.5Hz for the 3-level search pattern, and the code phase range associated with one segment is 32 chips. In this particular example, the frequency range characterizing a segment is divided into 20 segments, while the code phase range characterizing a segment is divided into 64 segments.

Advantageously, it is advantageous that the code phase range characterizing a segment is equal to the capacity of a channel of the correlator. In that way, the search segment may be transmitted over a single channel. In one example where the channel capacity is 32 chips, the code phase range characterizing a segment is also 32 chips, but it should be understood that: other examples are also possible.

Advantageously, the segments overlap by a defined number of chips to avoid missing peaks at segment boundaries. Fig. 12B illustrates the overlap that is commonly used. As illustrated, the tail end of segment 1202a overlaps the front end of segment 1202b by one chip, while the tail end of segment 1202b also overlaps the front end of segment 1202c by one chip. Due to the overhead caused by this overlap, the effective code phase range represented by a segment is usually smaller than the channel capacity. For example, in the case where the overlap is 4 chips, the effective code phase range represented by one segment is 28 chips.

Turning back to FIG. 5, in preparation for a level 0 search, in task 508, the search phase space of SVs are partitioned into segments, and those segments are queued. Then, task 510 is performed. In task 510, it is determined whether any additional SVs having a search window exceeding a predetermined threshold exist in group N_TOTIn (1). If so, the method returns to step 504 to perform another pass through tasks 504, 506, and 508. If not, the method continues with step 512. Through the performance of tasks 504, 506, 508, and 510, it can be seen that: code phase search windowThe search space for each SV for which the port exceeds a predetermined threshold is partitioned into segments queued in preparation for a level 0 search.

In task 512, a level 0 search is performed by adjusting the segment code phase and doppler window parameters to account for the time elapsed between the time of the assistance data and the time of performing the level 0 search, and then the segments through the correlator are processed. Also, in one example where the correlator comprises eight parallel channels, those segments are processed through the correlator eight segments at a time, but it should be understood that other examples are possible. The integration is performed by the correlator with an integration parameter of 0 th order. Advantageously, these parameters emphasize speed rather than sensitivity. In one example, the integration parameters for the level 0 search comprise a single coherent integration of 20ms, as set forth in the table of FIG. 11. Thus, a level 0 search will typically detect only the strongest signals.

Task 514 then 512. In task 514, the code phase and doppler frequency bins associated with the strongest peaks associated with each SV being searched are saved. Task 516 loops back to task 512 until all queued segments have been searched. Advantageously, all segments are searched within a single GPS frequency tuning time portion, but it should be understood that: it is also possible that multiple GPS frequency tuning times may be required to search all segments.

After all segments have been searched, task 518 is performed. In task 518, the strongest peak for each SV being searched is compared to a mode 0 detection threshold. In one example shown in the table of FIG. 11, the mode 0 detection threshold is 29.8 dB-Hz. If the strongest peak of one SV is below the threshold, the acquisition data (i.e., search window size and center) for the SV is zeroed out, ensuring that the SV will not be further searched or reported. That is desirable because these SVs represent those SVs that have a large search window that cannot be narrowed by a level 0 search. Therefore, it is important to remove SVs from the classification of the SVs being searched to avoid timeout conditions and the like.

Task 520 continues with task 518. In task 520, for each surviving SV, i.e., those SVs for which the strongest peak exceeds the level 0 threshold, the SV's code phase window is centered at the peak and the window size is reduced so that the peak is found by segmenting the single pass correlator. Also, the 0 th order doppler is modified to be that of the center frequency of the doppler bin where the maximum peak is located.

Once task 520 has completed, the level 0 search is complete.

FIG. 6 illustrates tasks or sub-steps that underlie the level 1 search (block 408) in FIG. 4. In task 602, group N_TOTAn SV (whose acquisition assistance data is still intact and which may have been modified by a level 0 search) is selected.

Task 604 is then performed. In task 604, the code phase search window for the SV is increased to account for code drift over time. In one example, one increase of 4 chips is implemented.

Task 606 follows task 604. In preparation for the level 1 search, the search space for SVs is partitioned into segments and those segments are queued, in task 606. In one example, as illustrated in fig. 11, one segment of the level 1 search is characterized by a doppler frequency range of 250Hz divided into 20 segments and a 32 chip range divided into 64 segments.

In task 608, a query is made as to whether there are other SVs that need to be searched in level 1 and that have complete acquisition data. If so, the method returns to task 602. If not, the method continues with task 610. With tasks 602 and 608, group N for which data integrity is captured after a level 0 search is performed_TOTEach SV in performs tasks 604 and 606.

In task 610, all queued level 1 segments are processed through the correlator. In one example, those segments are processed through the correlator eight segments at a time, but it should be understood that other examples are possible.

Task 612 is then performed. At task 612, a max peak algorithm is performed. According to this algorithm, the strongest peak of each SV searched in the level 1 search is maintained.

Task 614 follows task 612. In task 614, a query is made as to whether there are additional level 1 segments to process. If so, the method returns to task 610. If not, the method continues with task 616. Task 614 iterates the method through tasks 610 and 612 until all levels 1 have been processed.

The integration time on which the level 1 search is based emphasizes speed rather than sensitivity, but doing so results in a smaller range than the level 0 search. In one example, as shown in fig. 11, the order 1 integration time is 80ms, including four 20ms coherent integrations that are non-coherently combined. Advantageously, all level 1 segments are processed in a single GPS frequency tuning cycle due to the level 1 integration parameter, and the reduction in the search window obtained by the level 0 search.

Task 616 is then performed. In task 616, the SVs searched in the level 1 search are divided into three categories: strong, weak and none. In one example, sorting is performed by swing-and-hold. If the strongest peak found for SV exceeds the threshold value T₁Then the SV is in the weak category. If the strongest peak found for an SV exceeds a stronger second threshold T₂Then the SV is in the strong category. In one example, as illustrated in FIG. 11, the threshold T₁Is 25.0 dB-Hz. As indicated previously, the threshold T₂As a function of fixed time versus user selected accuracy/sensitivity options. In one configuration, one of three options is possible; threshold T of first, second and third options₂Are set to 29.4dB-Hz, 32.4dB-Hz, and ∞, respectively. The latter refers to an arrangement: it is so large that the threshold value T is₂Will never be satisfied.

SVs in the weak category define a group N, while SVs in the strong category define a group S. Group S' includes group N_TOTExcept for those SVs in group S.

Task 618 follows task 616. In task 618, the peaks in the strong and weak classes are analyzed to ensure that they are not due to cross-correlation. This analysis, which is performed to detect peaks due to cross-correlation, is conventional and need not be described in detail herein.

Task 620 is then performed. In task 620, if one peak in the strong or weak classes is determined to be due to cross-correlation, the peak is reclassified as a "none" class, i.e., as if it did not satisfy T₁The threshold is treated the same.

Task 622 is then performed. At task 622, a determination is made as to whether the measurements derived from the level 1 search results satisfy one or more selected measurement sufficiency criteria. Task 624 is then performed. In task 624, if the level 1 measurement meets one or more selected measurement sufficiency criteria, then task 626 is performed. In task 626, a flag is set: indicating that no level 2 or 3 search is required. In task 624, if the level 1 measurement does not meet one or more selected measurement sufficiency criteria, then a task 628 is performed.

The specific sub-steps below tasks 622 and 624 are illustrated in FIG. 9. In sub-step 906, the number of SVs in group S | and thus the strong class and group N_TOTSV number in | N_TOTCompare | is performed. If | S | is equal to | N_TOTL, representing group N_TOTIs in the strong category, the method continues to task 626 whereupon the flag is set, indicating that no level 2 or 3 searches are required.

If | S | is not equal to | N |_TOTSub-step 904 is performed. In sub-step 904, the polygon described earlier with respect to FIG. 3 is formed from the measurements of SV in set N, and the area A of this polygon is determined.

Query substep 906 follows substep 904. In query substep 906, the area A of the polygon is compared to a threshold area A_TA comparison is made. In addition, the number of SVs in the set N | and the threshold N_EEA comparison is made. If area A exceeds A_TOr | N | exceeds N_EEThen the method jumps to task 626 of fig. 6. Otherwise, the method continues with task 628 in FIG. 6.

In one example, the threshold area A_TAnd a threshold number N_EEOver a fixed time period relative to a user-selected accuracy/sensitivity threshold. In one configuration, the threshold areas A of the first, second and third options_TAre respectively set to 4 x 10⁷、6×10⁷And ∞. The latter refers to an arrangement: it is so large that the threshold is never met. In addition, a threshold number N of first, second and third options_EEAre set to 4, 5, and ∞, respectively. Also, the latter refers to an arrangement: it is so large that the threshold is never met.

Turning back to FIG. 6, if the level 1 measurement does not meet one or more selected measurement sufficiency criteria, then a task 628 is performed. In task 628, a list of strong peaks and weak peaks, and measurements derived therefrom, such as doppler and code phase bins including peak and peak carrier signal-to-noise ratios (C/No), is maintained. This list is used for subsequent level 2 or level 3 searches to detect peaks due to cross-correlation.

Task 630 is then performed. In task 630, the acquisition data for the SVs corresponding to the weak peaks (i.e., those in set N) are adjusted so that the peaks can be located by a single search segment. Thus, the code phase window is re-centered on the code phase at which the peak was found, and the code phase window size is reduced to 28 chips. Similarly, the doppler window size is reduced to 25Hz and the 0 th order doppler is modified to find the one of the interpolated frequencies of the peak.

Task 632 is then performed. In task 632, a flag is set: indicating that no level 2 or level 3 search is required. The level 1 search then ends.

FIG. 10 illustrates the sub-steps upon which a level 2 or level 3 search is selected at task 412. In query substep 1002, the number of SVs in set N | and a second threshold number N_EA comparison is made. If | N | exceeds N_EThen we jump to block 414 and perform a level 2 search. If not, then,the method continues with query substep 1004.

In one example, the second threshold number NE varies over a fixed time relative to the user-selected accuracy/sensitivity option. In one configuration, N of the first, second and third options_EThe values of (c) are set to 5, and ∞, respectively. The latter represents such a setting: it is so large that the threshold is never met.

In query substep 1004, an estimate t is made_estConsisting of the time required to perform a 3-level search on SVs in set S'. This time is compared to the maximum time t maintained in the current GPS position location session_maxA comparison is made. If t is_estExceeds t_maxIndicating that there is not enough time to conduct a level 3 search in the current session, the method continues to task 414 of fig. 4. Otherwise, the method continues with task 416.

In one example, time t_maxBased on quality of service considerations. In a second example, involving a PDE originated or mobile station terminated search, such as a 911 call for one subscriber station in a system generating adaptive IS-801, t_maxIs the preferred quality of response (PRQ) value specified by the PDE. In a third example, for a mobile-originated search, such as one involving an Internet geography-based search issued by a subscriber station, t_maxAssigned by the subscriber station.

FIG. 7 illustrates the tasks upon which the level 2 search (block 414) of FIG. 4 is based. In task 702, one SV in set S' (i.e., those SVs previously classified within the weak or "none" category) is selected.

Task 704 follows task 702. In task 704, the code phase window of the selected SV is increased to accommodate the segment overlap between adjacent correlator segments. In one example, the segments overlap by four chips, but it should be understood that other examples are possible.

Task 706 follows task 704. In preparation for a level 2 search, the search space for the selected SV is partitioned into segments and those segments are queued, in task 706. In one example, as shown in fig. 11, a level 2 segmentation is characterized by a doppler frequency range of ± 250 divided into 20 segments and a code phase range of 32 divided into 64 segments.

Task 708 follows task 706. At task 708, a query is made as to whether there are additional SVs in group S'. If so, the method returns to task 702 for another iteration.

If not, the method continues with task 710. Through iterations of the loop represented by tasks 702, 704, 706, and 708, the method generates and queues 2-level segments for each SV in group S'.

In task 710, the level 2 segment is processed through a correlator. In one example where the correlator comprises eight parallel channels, eight segments are processed through the correlator at a time, but it should be understood that other examples are possible.

Task 712 then task 710. In task 712, a multiple/maximum peak algorithm is used to locate the earliest valid peak for an SV for each SV in set S'. This is in contrast to the maximum peak algorithm mentioned in task 612, which locates the strongest peak for each SV involved in the respective search. According to one example of a multiple/maximum peak algorithm, a valid peak for SV is the strongest peak for that SV, unless there is an earlier peak within 4 chips and 15dB of the strongest peak, in which case the valid peak is the earlier peak. This algorithm identifies that the earliest peak is not always the strongest peak but may be a weaker peak earlier in time than the strongest peak.

In addition, the peaks identified in task 712 are analyzed to determine whether they represent cross-correlations of the peaks listed in task 628. If a peak is so identified, the identified peak is discarded at run time in preference to the weaker peak that may better represent the SV. In one example, this step occurs by comparing the C/No and Doppler values of the peak identified in task 712 with the corresponding values of the peak identified in step 628.

Task 714 continues with task 712. In task 714, a query is made as to whether there are any remaining level 2 segments to process. If so, the method returns to task 710 for another iteration. If not, the method continues with step 716. All level 2 segments are processed through one or more iterations through tasks 710, 712, and 714.

The integration parameters on which the 2-level search is based emphasize sensitivity and accuracy rather than speed. In one example as shown in fig. 11, the integration based on at level 2 search includes 44 20ms coherent integrations that are non-coherently combined. In one example, the level 2 integration parameters are such that two level 2 segments can be processed by each correlator in one GPS frequency tuning cycle. In the case of a correlator with eight parallel channels, that transition becomes a requirement: at least 16 segments are processed in a single GPS frequency tuning cycle.

Advantageously, all 2-level segmentation can be processed in a single GPS frequency tuning cycle, but it should be understood that: it is also possible that multiple GPS frequency tuning cycles would be required to process the level 2 segment.

Task 716 is then performed. In task 716, a conventional cross-correlation test is applied to all peaks that have been identified. These include peaks in group S, identified by level 1 or level 2 searches, and peaks in group S'. Since this test is conventional, it need not be described in detail here.

Task 718 then follows task 716. In task 718, for each peak identified as a cross-correlation, the RMSE saturation flag for that peak is set, or the measurement type is set to the "none" category: indicating that peak should be ignored for positioning purposes. The level 2 search then ends.

Fig. 8 illustrates tasks underlying the level 3 search (block 418) in fig. 4. In task 802, one SV in set S' (i.e., those SVs previously classified within the weak or "none" category) is selected.

Task 804 follows task 802. In task 804, a code phase search window for the selected SV is increased to account for code drift over time. In one example, the segmentation is increased by four chips.

Task 806 follows task 804. In preparation for a 3-level search, the search space for the selected SV is partitioned into segments and those segments are queued, in task 806. In one example, as shown in fig. 11, one 3-level segment is characterized by a doppler frequency range of ± 62.5 divided into 20 segments and a code phase range of 32 divided into 64 segments.

Task 808 then follows task 806. In task 808, a query is made as to whether there are additional SVs in group S'. If so, the method returns to task 802 for another iteration. If not, the method continues with task 810. Through repetition of the loop represented by tasks 803, 804, 806, and 808, the method generates and queues 3-level segments for each SV in group S'.

In task 810, the level 3 segment is processed through a correlator. In one example where the correlator comprises eight parallel channels, eight segments are processed through the correlator at a time, but it should be understood that other examples are possible.

Task 812 follows task 810. In task 812, the multiple/maximum peak algorithm is used to locate the earliest valid peak for an SV for each SV in set S'. In addition, the peaks identified in task 812 are analyzed to determine whether they represent cross-correlations of the peaks listed in task 628. If a peak is so identified, the identified peak is discarded at run time in preference to the weaker peak that may better represent the SV. In one example, this step occurs by comparing the C/No and Doppler values of the peak identified in task 812 with the corresponding values of the peak identified in step 628.

Task 814 continues with task 812. In task 814, a query is made as to whether there are any remaining level 3 segments to process. If so, the method returns to task 810 for another iteration. If not, the method continues to step 816. All level 3 segments are processed through one or more iterations through tasks 710, 713, and 714.

The integration parameters on which the 3-level search is based emphasize sensitivity and accuracy rather than speed, and doing so results in a greater degree than the 2-level search. In one example as shown in fig. 11, the integration under the 3-level search includes 22 80ms coherent integrations of non-coherent combinations. In one example, the level 3 integration parameters are such that a level 3 segment can be processed by each correlator during a GPS frequency tuning cycle. In the case of a correlator with eight parallel channels, that transition becomes a requirement: at least 8 segments are processed in a single GPS frequency tuning cycle.

Because the coherent integration time used in the 3-level search is 80ms, which exceeds the 20ms time period over which the data bits are modulated onto one SV signal, the coherent integration in the 3-level search is performed with sensitivity assistance from the PDE provided in task 416 to account for the bit phase changes that occur within the 80ms coherent integration time.

Advantageously, all 3-level segmentation can be processed in a single GPS frequency tuning cycle, but it should be understood that: it is also possible that multiple GPS frequency tuning cycles would be required to process the 3-level segment.

Task 816 is then performed. In task 816, a conventional cross-correlation test is applied to all peaks that have been identified. These include peaks in group S, identified by level 1 or level 3 searches, as well as those in group S'. Since this test is conventional, it need not be described in detail here.

Task 818 follows task 816. In task 818, for each peak identified as a cross-correlation, the RMSE saturation flag for that peak is set, or the measurement type is set to the "none" category: indicating that peak should be ignored for positioning purposes. The level 3 search then ends.

One embodiment of a system for searching for a location signal within a specified time period is shown in fig. 13. As illustrated, the system includes a processor 1302, memory 1304, and correlator 1306.

Correlator 1306 is configured to generate correlation functions from signals provided to it by a receiver (not shown), and 1304 provides them to processor 1302, either directly or through memory. Correlator 1306 may be implemented in hardware, software, or a combination of hardware and software.

The memory 1304 is tangibly embodied as a series of software instructions for carrying out any of the methods of fig. 2, 4-10 or any of the embodiments, implementations, or examples that have been described or suggested.

The processor is configured to access and execute software instructions tangibly embodied in memory 1304. Through execution of these instructions, processor 1302 directs correlator 1306 to search for a positioning signal as part of a level 0, level 1, level 2, or level 3 search, and it derives a measurement from the resulting correlation function provided to it by correlator 1306.

If the search is a level 1 search, the processor 1302 determines whether the level 1 measurements satisfy one or more selected measurement sufficiency criteria. If so, the processor 1302 terminates the search. If not, processor 1302 directs correlator 1306 to perform a level 2 or level 3 search of the positioning signal.

An embodiment of one subscriber station in a wireless communication system is illustrated in fig. 14. This particular subscriber station is configured to embody or incorporate the system of figure 13.

The radio transceiver 1406 is configured to modulate baseband information, such as voice or data, onto a radio frequency carrier and demodulate a modulated radio frequency carrier to obtain the baseband information.

The antenna 1410 is configured to transmit a modulated radio frequency carrier over a wireless communication link and to receive a modulated radio frequency carrier over the wireless communication link.

Baseband processor 1408 is configured to provide baseband information from CPU 1402 to transceiver 1406 for transmission over a wireless communication link. CPU 1402 then retrieves the baseband information from an input device within user interface 1416. Baseband processor 1408 is also configured to provide baseband information from transceiver 1406 to CPU 1402. CPU 1402 then provides the baseband information to an output device within user interface 1416.

The user interface 1416 includes a plurality of means for inputting or outputting user information such as voice or data. Those devices typically included in a user interface include a keypad, a display screen, a microphone, and a speaker.

GPS receiver 1412 is configured to receive and demodulate GPS satellite transmissions and provide demodulated information to correlator 1418.

Correlator 1418 is configured to derive GPS correlation functions from the information provided to it by GPS receiver 1412. For a given PN code, correlator 1418 produces a correlation function that is defined over a range of code phases defining a code phase search window, and over a range of doppler frequency hypotheses. Each individual correlation is performed in accordance with defined coherent and non-coherent integration parameters.

Correlator 1418 may also be configured to derive pilot-related correlation functions from information relating to the pilot signals provided to it by transceiver 1406. This information is used by the subscriber station to acquire wireless communication services.

Channel decoder 1420 is configured to decode the channel symbols provided to it by baseband processor 1408 into elementary 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 concatenated convolutional codes in series or in parallel, the channel decoder 1420 is a turbo decoder.

The memory 1404 is configured to hold software instructions embodying any of the methods of fig. 2, 4-10 or any of its embodiments, implementations or examples that have been described or suggested.

CPU 1402 is configured to access and execute these software instructions. Through execution of these software instructions, CPU 1402 directs correlator 1418 to perform a level 0, level 1, level 2, or level 3 search as appropriate, analyzes the GPS correlation function provided to it by correlator 1418, derives a measurement from its peak, and, in the case of a level 1 measurement, determines whether the level 1 measurement meets a selected measurement sufficiency criterion, or whether a level 2 or level 3 search is required to fix the location of the entity.

CPU 1402 is also configured to determine a root mean square error associated with each measurement. These measurements and RMSE values are provided to a PDE (not shown). The PDE weights each measurement based on the inverse of its corresponding RMSE value and then estimates the location of the subscriber station based on the weighted measurements. Alternatively, the subscriber station determines its own location from this information.

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 using the present invention to search for positioning signals that include base station transmissions or a combination of base station and GPS satellite transmissions. It is also possible to extend the invention to include embodiments of search processes at many levels of search patterns, including configurations using more than 3 levels. Embodiments are also possible with respect to subscriber stations using a dual radio frequency solution as compared to a shared radio frequency solution. Accordingly, the invention is not to be restricted except in light of the attached claims.

Claims

1. A method of searching for a positioning signal using a plurality of progressively more sensitive search modes, the plurality of search modes comprising, in order of increasing sensitivity, a first level mode, a second level mode, and at least one higher level mode, the method comprising:

determining whether any search window parameters exceed a prescribed limit;

performing a first level search if any of the search window parameters exceed a prescribed limit, and in response refining the search window parameters to bring them within the prescribed limit;

performing a second level search as part of the location fix attempt;

deriving one or more measurements from subsequent search results;

determining whether the measurement satisfies one or more selected measurement sufficiency criteria;

avoiding additional searches within the location fix attempt if the measurements satisfy one or more selected measurement sufficiency criteria; and

if the measurements do not satisfy one or more selected measurement sufficiency criteria, a higher level search is performed beyond the second level.

2. The method of claim 1 wherein the signal is a GPS satellite signal.

3. The method of claim 1, wherein the measurements comprise peak SNR and time measurements.

4. The method of claim 1, characterized in that the higher level search window parameter is optimized.

5. The method of claim 1, wherein a higher level search is selected between the third level and the fourth level searches based on an application of a defined selection criterion.

6. The method of claim 5, wherein the third level search does not use sensitivity assistance from the wireless communication system and the fourth level search is used.

7. A method of searching for a positioning signal using a plurality of progressively more sensitive search modes, the plurality of search modes comprising a first level mode, a second level mode, a third level mode, and a fourth level mode in order of increasing sensitivity, the method comprising:

determining whether any search window parameters exceed a prescribed limit;

performing a second level search as part of the location fix attempt;

deriving one or more measurements from subsequent search results;

if the measurements do not satisfy one or more selected measurement sufficiency criteria, a higher level search is performed that exceeds the second level, where the higher level search is a third level or a fourth level search based on the one or more specified selection criteria.

8. The method of claim 7, further comprising: the location of an entity is determined from measurements derived from one or more searches.

9. The method of claim 8, wherein said entity is a subscriber station in a wireless communication system.

10. The method of claim 7, wherein the series of search patterns progressively use a greater integration time.

11. The method of claim 7, wherein the fourth stage search uses a coherent integration time greater than 20ms and the third stage search does not.

12. The method of claim 7, wherein the fourth level search uses sensitivity assistance from the wireless communication system, and the third level search is not used.

13. A method of searching for a positioning signal using a plurality of progressively more sensitive search patterns, the plurality of search patterns comprising a first level pattern, a second level pattern, and a third level pattern in increasing order of sensitivity, the method comprising:

performing a first level search as part of a position fix attempt;

deriving one or more measurements from subsequent search results;

if the measurements do not satisfy one or more selected measurement sufficiency criteria, a higher level search is performed beyond the first level, where the higher level search is a second level or third level search based on one or more specified selection criteria.

14. A memory storing sequences of software instructions embodying the method of claim 1.

15. A memory storing sequences of software instructions embodying the method of claim 7.

16. A memory storing sequences of software instructions embodying the method of claim 13.

17. A system comprising a processor, the memory of claim 14, and a correlator, wherein the processor is configured to access and execute software instructions stored in the memory, and in combination with the correlator, perform the method embodied thereby.

18. A system comprising a processor, the memory of claim 15, and a correlator, wherein the processor is configured to access and execute software instructions stored in the memory, and in combination with the correlator, perform the method embodied thereby.

19. A system comprising a processor, the memory of claim 16, and a correlator, wherein the processor is configured to access and execute software instructions stored in the memory, and to perform the method embodied thereby in accordance with the correlator.

20. A method of searching for a positioning signal using a plurality of progressively more sensitive search modes, the plurality of search modes comprising, in order of increasing sensitivity, a first level mode, a second level mode, and at least one higher level mode, the method comprising:

a step for determining whether any of the search window parameters exceeds a prescribed limit;

a step for performing a first level search if any of the search window parameters exceed a prescribed limit, and in response thereto refining the search window parameters to bring them within the prescribed limit;

a step for performing a second level search as part of the location fix attempt;

a step for deriving one or more measurements from subsequent search results;

a step for determining whether the measurement satisfies one or more selected measurement sufficiency criteria;

a step for avoiding further searches within the location fix attempt if the measurements satisfy one or more selected measurement sufficiency criteria; and

a step for performing a higher level search beyond the first level if the measurements do not meet one or more selected measurement sufficiency criteria.

21. A method of searching for a positioning signal using a plurality of progressively more sensitive search patterns, the plurality of search patterns comprising a first level pattern, a second level pattern, and a third level pattern in increasing order of sensitivity, the method comprising:

a step for performing a first level search as part of a position fix attempt;

a step for deriving one or more measurements from subsequent search results;

a step for performing a higher level search beyond the first level if the measured values do not meet one or more selected measured value sufficiency criteria, wherein the higher level search is a second level or third level search based on one or more specified selection criteria.

22. The method of claim 1 further comprising: those measurements from the higher level search that are determined to be cross-correlated with the measurements from the second level search are discarded.

23. The method of claim 22 wherein said measurements are discarded during run time in preference to other measurements that better represent SV.

24. The method of claim 7, further comprising: those measurements from the higher level search that are determined to be cross-correlated with the measurements from the second level search are discarded.

25. The method of claim 24 wherein said measurements are discarded during run time in preference to other measurements that better represent SV.

26. The method of claim 13, further comprising: those measurements from the higher level search that are determined to be cross-correlated with the measurements from the first level search are discarded.

27. The method of claim 26 wherein said measurements are discarded during run time in preference to other measurements that better represent SV.

28. The method of claim 20, further comprising the step of discarding those measurements from the higher level search that are determined to be cross-correlated with measurements from the second level search.

29. The method of claim 28, wherein said measurements are discarded during run time in preference to other measurements that better represent SV.

30. The method of claim 21, further comprising: a step of discarding those measurements from the higher level search that are determined to be cross-correlated with the measurements from the first level search.

31. The method of claim 30 wherein said measurements are discarded during run time in preference to other measurements that better represent SV.