HK1038398A - Position location in memory limited environment - Google Patents

Description

Positioning in memory-limited environments

Background

The present invention relates to positioning. More particularly, the present invention relates to a novel and improved method and apparatus for position location in a wireless communication system.

Description of the Related Art

Government regulations and customer requirements have driven the need for location functions in cellular telephones. Currently, the Global Positioning System (GPS) can be used for positioning by a GPS receiver in combination with a set of earth orbiting satellites. Therefore, it is desirable to use GPS functionality for cellular telephones.

However, cellular telephones are very sensitive to issues of cost, weight and power consumption. Simply adding additional circuitry for performing GPS positioning is not a satisfactory solution for providing positioning functionality in a cellular telephone. It is therefore an object of the present invention to provide GPS functionality in a cellular telephone system with minimal additional hardware, cost and power consumption.

Summary of The Invention

The present invention is a novel and improved method and apparatus for performing position location in a wireless communication system. One embodiment of the present invention includes a method for performing position location in a wireless communication system using a set of signals transmitted from a set of satellites, the method comprising the steps of: receiving signal samples, rotating an acquisition code by a first rotation amount, thereby generating a rotated acquisition code; despreading the signal samples using a rotating acquisition code to produce despread data; accumulating the despread data over a first duration of time to produce partially accumulated data; the partially accumulated data is rotated by a second amount of rotation, thereby generating rotated data and accumulating the rotated data.

Brief description of the drawings

The features, objects, and advantages of the present invention will be apparent from the detailed description set forth below when taken in conjunction with the drawings. In the drawings, like reference numerals designate like elements, and

FIG. 1 is a block diagram of a Global Positioning System (GPS) waveform generator;

FIG. 2 is a highly simplified block diagram of a cellular telephone system constructed in accordance with the use of the present invention;

fig. 3 is a block diagram of a receiver constructed in accordance with an embodiment of the invention;

fig. 4 is another block diagram of the receiver shown in fig. 3;

fig. 5 is a receiver constructed in accordance with another embodiment of the invention;

FIG. 6 is a flow chart of steps performed during a positioning operation;

FIG. 7 is a block diagram of a DSP constructed according to an embodiment of the invention;

FIG. 8 is a flowchart of steps performed during a search performed in accordance with one embodiment of the present invention;

FIG. 9 is a timeline illustrating stages of performing fine and coarse searches according to one embodiment of the present invention;

FIG. 10 is a timeline of a search process when performed according to one embodiment of the present invention;

FIG. 11 is a diagram of a search space;

fig. 12 is a block diagram of a receiver according to another embodiment of the present invention.

Detailed description of the preferred embodiments

Novel and improved methods and apparatus for performing position location in a wireless communication system are described. The exemplary embodiments are described in the context of a digital cellular telephone system. Although useful in this context, different embodiments of the invention may be used in different environments or configurations. Generally, the various systems described herein may be formed using software controlled processors, integrated circuits, or discrete logic blocks, however, implementation in an integrated circuit is preferred. Data, instructions, commands, information, signals, symbols, and chips that may be referenced throughout the application are advantageously represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or a combination thereof. Furthermore, the blocks shown in each block diagram may represent hardware or method steps.

Fig. 1 is a block diagram of a Global Positioning System (GPS) waveform generator. One plus symbol inside the circle represents modulo 2 plus. In general, the GPS constellation includes 24 satellites: 21 Space Vehicles (SV) for navigation and 3 backups (square). Each SV includes a clock synchronized to GPS time by monitoring a ground station. To determine position and time, the GPS receiver processes signals received from several satellites. At least 4 satellites must be used to solve for 4 unknowns (x, y, z, time).

Each SV transmits 2 microwave carriers: an 1557.42MHz L1 carrier carrying signals for Standard Positioning Services (SPS) and a 1227.60MHz L2 carrier carrying signals required for Precision Positioning Services (PPS). The government agency structure uses PPS and allows for higher accuracy positioning.

The L1 carrier is modulated with a coarse acquisition (C/a) code, which is a 1023-chip pseudorandom code transmitted at 1.023Mcps for civil location services. (coarse acquisition codes should not be confused with the coarse and fine acquisition described herein, which involves the use of C/a codes.) each satellite has its own C/a code, which repeats every 1 ms. The P-code for PPS is a 10.23MHz code, which is 2676 days in length. The P-code appears on both carriers but is 90 degrees out of phase with the C/a code on the L1 carrier. The 50Hz navigation message exclusive ored with the C/a and P codes prior to carrier modulation provides system information such as satellite orbit and clock corrections.

The L1 carrier is modulated with a coarse acquisition (C/a) code, which is a 1023-chip pseudo-random code transmitted at 1.023Mcps for civilian positioning traffic. Each satellite has its own C/a code, which repeats every 1 ms. The P-code for PPS is a 10.23MHz code, which is 267 days long. The P-code appears on both carriers and is 90 degrees out of phase with the C/a-code on the L1 carrier. The 50Hz navigation message exclusive ored with the C/a and P codes prior to carrier modulation provides system information such as satellite orbit and clock corrections.

The L1 carrier is modulated with a coarse acquisition (C/a) code, which is a 1023-chip pseudo-random code transmitted at 1.023Mcps for national location services. Each satellite has its own C/a code, which repeats every 1 ms. The P-code for PPS is a 10.23MHz code, which is 267 days long. The P-code appears on both carriers and is 90 degrees out of phase with the C/a-code on the L1 carrier. The 50Hz navigation message exclusive ored with the C/a and P codes prior to carrier modulation provides system information such as satellite orbit and clock corrections.

Each satellite has a different C/a code belonging to a series of codes called Gold codes. Gold codes are used because the cross-correlation between them is small. Two 10-stage shift registers (as shown in fig. 1.4-2) are used to generate the C/a code. Polynomial 1+ X for G1 generator³+X¹⁰While the generator G2 uses polynomial 1+ X²+X³+X⁶+X⁸+X⁹+X¹⁰. The C/A code is generated by EXCLUSIVE-OR' ing the output of the G1 shift register with the 2 bits of the G2 shift register.

Fig. 2 is a highly simplified block diagram of a cellular telephone system configured for use in accordance with the present invention. The mobile telephone 10 is located between base stations 12, with the base stations 12 being coupled to a Base Station Controller (BSC) 14. The mobile switching center MSC16 connects the BSC14 to a Public Switched Telephone Network (PSTN). During operation, some mobile phones make phone calls by connecting to the base station 12 while other mobile phones are in standby mode.

As described in co-pending U.S. patent application No. 09/040,051 (entitled "system and method for determining the location of a wireless CDMA transceiver," assigned to the assignee of the present invention and incorporated herein by reference), a location request message is sent to facilitate location determination, wherein the location request message includes "aiding information" that allows the mobile phone to quickly acquire GPS signals. The information includes an ID number of the SV (SV ID), an estimated code phase, a search window size around the estimated code phase, and an estimated frequency doppler. With this information, the mobile unit can more quickly acquire the GPS signal and determine its location.

In response to the aiding information, the mobile unit tunes to the GPS frequency and begins correlating the received signal with its locally generated C/a sequence for the SV specified by the base station. It uses aiding information to narrow the search space and compensate for the doppler response and uses time correlation to obtain the pseudorange for each satellite. Note that these pseudoranges are based on mobile unit time (referred to as the combiner system timer of the CDMA receiver), which is a delayed representation of GPS time.

Once this information is calculated, the mobile unit sends to the base station the pseudoranges for each satellite (preferably with a resolution of 1/8 chips) and the time required for the measurement. The mobile unit then returns to CDMA and continues the call.

Typically, upon receiving the information, the BSC uses one-way delay estimation to convert the pseudorange from the mobile unit time to the base station time and calculates the estimated location of the mobile unit by solving for the intersection of several regions.

Another parameter provided by the help message is frequency doppler or doppler shift. The doppler effect represents a significant change in the frequency of the received signal due to the relative velocity between the transmitter and the receiver. The effect of doppler on the carrier is known as frequency doppler and the effect on the baseband signal is known as code doppler.

In the case of GPS, frequency doppler changes the received carrier frequency so that the effect is the same as demodulation with carrier offset. Since the GPS receiver of the base station actively tracks the desired satellite, it knows the frequency doppler due to satellite movement. Furthermore, the satellite is so far away from the base station and the mobile station that the doppler shift seen by the mobile unit is virtually the same as the doppler shift seen by the base station. In one embodiment of the invention, the mobile unit employs a rotator in the receiver in order to correct the frequency doppler value. The frequency Doppler ranges from-4500 Hz to +4500Hz, and the rate of change is approximately 1 Hz/s.

The effect of code doppler is to change the 1.023Mhz chip rate, which actually compresses or expands the width of the received C/a code chips. In an embodiment of the present invention, the mobile unit corrects for code doppler by multiplying frequency doppler by the ratio 1.023/1575.42. The mobile unit can then correct code doppler over time by rotating (introducing delay to) the phase of the received IQ samples in 1/16 chip increments as needed.

Fig. 3 is a block diagram of a receiver portion of a cellular telephone (wireless subscriber unit) constructed in accordance with an embodiment of the invention. Modeling the received waveform 100 for use at a frequency w_c+w_dA carrier modulated C/A signal C (n) where w_cIs the nominal carrier frequency 1575/42MHz, and w_dIs the doppler frequency produced by the satellite movement. The doppler frequency ranges from 0 (when the satellite is directly overhead) to about 4.5kHz (in the worst case). The receiver analog part can be modeled as demodulation with a carrier at frequency wr and random phase _ followed by low pass filtering.

The resulting baseband signal is passed through an a/D converter (not shown) to produce digital I and Q samples, which are stored so that they can be searched repeatedly. The samples are generated at twice the C/a code chip rate (chip x 2), which is lower than the resolution required to perform the fine search algorithm, but allows 18ms of sampled data to be stored in a reasonable amount of memory. In general, it is desirable to search at a rate greater than 10ms, allowing acquisition under most environmental conditions, with 18ms being the preferred integration period. These environmental conditions include being inside or not directly in view of the satellites.

During operation, the samples are first rotated by rotator 102 to correct for doppler frequency offset. The rotated I and Q samples are correlated with various offsets of the C/a sequence of the satellite and the resulting products are coherently integrated over Nc chips with an integrator 104. The coherent integration sum is squared and summed to remove the effect of the unknown phase offset. To increase hypothesis testing for a particular offset, several coherence intervals are non-coherently combined. The despreading is performed repeatedly at a plurality of time offsets to find the time offset of the satellite signal. It uses the doppler frequency specified by the base station (preferably quantized to 10Hz intervals) and rotates the I and Q samples to remove the frequency offset.

In one embodiment of the invention, the rotation is continuous only within the coherent integration window. I.e. the rotator is stopped between coherent integration periods of 1ms, for example. Summing the squared values eliminates any resulting phase difference.

Fig. 4 is another block diagram of a receiver constructed in accordance with an embodiment of the invention, showing the rotator portion of the receiver in greater detail.

Fig. 5 is a receiver constructed in accordance with another embodiment of the invention. This internal embodiment of the present invention takes advantage of the ability to stop the rotator between coherent integration periods by rotating the locally generated C/a sequence instead of the input samples.

As shown, the C/A sequence C (n) is generated by applying to the sine and cosine signals sin (W)_dnT_c) And cos (W)_dnT_c) Rotated above, and then stored. Each satellite need only rotate the C/a sequence once. Thus, rotating the C/a code sequence reduces the amount of computation required. In one embodiment of the invention, this also saves on the amount of memory in the DSP used to perform such calculations.

Another significant detriment that degrades the performance of the positioning algorithm is the frequency error in the mobile unit internal clock. It is this frequency error that encourages the use of short coherent integration times, on the order of 1 ms. Preferably, coherent integration is performed over a longer period of time.

In the exemplary architecture, the free-running (internal) local oscillator clock of the mobile station is a 19.68MHz crystal, which has a frequency tolerance of +/-5 ppm. This can result in a large error of about +/-7500 Hz. The clock is used to generate a carrier wave for demodulating the GPS signal, thereby adding a clock error to the signal acquisition time. Such large errors due to frequency tolerance are not tolerable and must be greatly reduced because of the short time available for searching.

To allow for longer coherent integration times, in one embodiment of the invention, the CDMA receiver corrects the local oscillator by applying timing obtained from the CDMA amble or any other timing information available. This generates a control signal that tunes the local oscillator clock as close to 19.68MHz as possible. The control signal applied to the local oscillator clock is frozen when the radio unit switches from CDMA to GPS.

However, even after performing the correction using timing information from the base station (or other resource), some additional clock error remains. In one embodiment of the invention, the resulting frequency uncertainty after correction is +/-100 Hz. This residual error still degrades the performance of the receiver and generally prevents longer coherent integration times. In one embodiment of the invention, residual errors can be simply avoided by performing non-coherent integration for a duration greater than 1ms, which degrades performance.

As shown in fig. 1, the 50Hz NAV/system data is also modulated on an L1 carrier. If a data transition (0 to 1 or 1 to 0) occurs between two half coherent integration windows, the resulting coherent integration sum will be zero, since the two halves will cancel each other. This effectively decrements the incoherent integration number by 1 in the worst case. While synchronizing the data boundaries of all satellites, they cannot arrive at the mobile unit at the same time due to differences in channel delay. The channel delay effectively randomizes the phase of the received data.

In one embodiment of the invention, the problem with different data phases for different signals is to include the data phases in the aiding information sent from the base station to the mobile unit. Since the base station demodulates the 50Hz data, it knows when each satellite has data transitions. By applying the well-known one-way delay, the base station can encode the data phase with 5 bits (per satellite) by indicating which of the 20 1 millisecond intervals the data transition occurred.

If the coherent integration window spans both sides of the 50Hz data boundary, the coherent integration is split into 2 (2) parts. One portion precedes the data boundary and the other portion follows the data boundary. For example, if En1 is the coherent integration sum in the window before the data boundary (the first half of the window) and En2 is the coherent integration sum in the window after the data boundary, the mobile unit selects the maximum values (amplitude) of (En1+ En2) (in case of the same data) and (En1-En2) (in case of data variation) to account for the phase variation. The mobile unit may also choose between non-coherently combining the two halves across the data window or eliminating the data window altogether.

In another embodiment of the invention, the mobile unit attempts to find a data transition by comparing the difference between the magnitude squared of the sum and the 1ms coherent integration without the aid of information from the base station.

In one embodiment of the invention, a firmware-based DSP (digital Signal processor) method is used to perform GPS processing. The DPS receives I and Q samples at a rate of chip x 2(2.046MHz) or chip x 8(8.184MHz) and stores snapshots of the 4-bit I and Q samples in its internal RAM.

In the exemplary embodiment, the DSP generates the C/A sequences, rotates to eliminate frequency Doppler, and correlates within a search window provided by the base station for each satellite. The DSP performs coherent integration and non-coherent combining and rotates the IQ sample decimator as needed to compensate for code doppler.

To save computation and memory space, an initial search is performed with a _ chip resolution and a fine search is performed around the best flag or flags to obtain 1/8 chip (higher) resolution. The system time is maintained by counting 1ms interrupts (generated by a local oscillator) generated by the hardware.

Furthermore, in one embodiment of the present invention, the fine search is performed by accumulating chip x 8 samples (higher resolution) over the duration of one chip at different chip x 8 offsets.

Fig. 6 is a flow chart showing steps performed to correct a local oscillator during positioning when performed in accordance with one embodiment of the present invention. In step 500, it is determined whether the local oscillator has recently been correctly corrected. If not, then the amble is acquired from the base station and an error of the local oscillator is determined by comparison with the amble timing in step 502 and a correction signal based on the error is generated.

Flow then proceeds to step 504 where the correction signal is frozen at the current value. In step 506, GPS mode is entered and a fix is performed using the corrected clock. Once the position fix is performed, the mobile station leaves GPS mode in step 508.

Figure 7 illustrates a DSP receiver system constructed in accordance with one embodiment of the invention. The DSP performs the entire search operation with minimal additional hardware. The DSP core 308, modem 306, interface unit 300, ROM302, and memory (RAM)304 are coupled by bus 306. The interface unit 300 receives RF samples from an RF unit (not shown) and provides the samples to the RAM 304. The RF samples may be stored at a coarse resolution or a fine resolution. The DSP core 308 processes the samples stored in memory using instructions stored in the ROM302 and the memory 304. The memory 304 has a plurality of "banks," some of which store samples and some of which store instructions. Modem 700 performs CDMA processing in the normal mode.

Fig. 8 is a flow chart of steps performed during a positioning operation. The positioning operation is started when the help message is received and the RF system is switched to the GPS frequency (in step 600). When the RF is switched to receive GPS, the frequency tracking loop is fixed. The DSP receives the step information from the telephone microprocessor and classifies the satellites by doppler amplitude.

In step 602, the coarse search data is stored in DSP RAM. The DSP receives input data for several hundred microseconds to set the Rx AGC. The DSP records the system time and starts storing the chip x 2IQ data for the 18ms window (DSP memory limit) in its internal RAM. The effect of code doppler is mitigated with contiguous data windows.

Once the data is stored, a coarse search is performed in step 604. The DSP starts a coarse (chip x 2 resolution) search. For each satellite, the DSP generates a C/A code, rotates the code according to frequency Doppler and correlates within a search window specified by the base station by reusing the C/A code for the stored coarse search data. The satellites are processed within the same 18ms data window and the best chip x 2 hypothesis is obtained for each satellite that exceeds the threshold. While in one embodiment of the invention a 2ms correlation integration time is used (with 9 non-correlation integrations), a longer correlation integration time (e.g., 18ms) may be used, although additional adjustments as described below are preferred.

Once the coarse search is performed, a fine search is performed in step 606. Before starting the fine search, the DSP calculates the rotated C/a code for each satellite. This allows the DSP to process fine searches in real time. During the execution of a fine (chip x 8 resolution) search, one satellite at a time is processed on different data.

The DSP first rotates the decimator to compensate for the code doppler for a given satellite. The Rx AGC value is also reset before storing the 1ms correlation integration window of chip x 8 samples while waiting for the next 1ms boundary.

The DSP processes the 5 contiguous chip x 8 resolution hypotheses for the 1ms coherent integration window, with the center hypothesis being the best hypothesis found in the coarse search. After processing the next 1ms window, coherently combining the results for all Nn repetitions does not coherently combine the 2ms sums.

This step is repeated (starting with the rotational decimator) for the same data for the next satellite until all satellites have been processed. If the code doppler for 2 satellites is the same in magnitude, then both satellites can be processed at the same data to reduce the number of data sets required. In the worst case, 8 sets of 1ms 2 xn data windows are used for the fine search.

Finally, in step 608, the results are reported to the microprocessor and vocoder processing is restarted in the DSP so that the call can continue. The DSP reports the pseudoranges to the microprocessor, which forwards them to the base station. After the microprocessor re-downloads the vocoder program code to the DSP memory, the DSP clears its data memory and re-enables the vocoder.

Fig. 9 shows a fine search performed after the coarse search. After the best chip x 2 stage is separated in the coarse search, the DSP performs a fine search around this stage to obtain a chip x 8 resolution.

The 5 stages for comparison in the fine search are boxed with rectangles as shown. The best chip x 2 phase is evaluated again so that the same data set can be compared. This also allows the coarse and fine searches to employ different integration times. Since each satellite may have a different value for code doppler, the fine search may be performed separately for each satellite.

FIG. 10 provides a timeline for fine processing when implemented according to one embodiment of the present invention. The entire processing time (coarse + fine search) is completed in about 1.324 seconds in one embodiment of the invention, which interrupts the call but still allows the call to continue once the search is completed. The entire search of 1.324 seconds is an upper limit because it assumes that the DSP needs to search all 8 satellites and that each satellite has a search window of 68 chips. However, the probability of requiring 1.324 seconds for the entire process is small due to the geometry of the satellite orbit.

During the first 18ms80, IQ sample data is collected at the GPS frequency. Within period 82, a coarse search is performed internally, which may last as long as 1.13 seconds, but may terminate early when a satellite signal is identified. Once the coarse search is performed, the C/a code is calculated within time period 84, which takes 24 ms. During time period 86, the rotation value is adjusted for code doppler and Rx AGC is further adjusted. During time period 88, a fine search is performed on the IQ data samples, which performs continuous adjustment during time period 86. Using an 18ms integration time allows code doppler to be ignored because the received C/a code phase offset is less than 1/16 chips. The adjustment and fine search to adjust up to 8 sequences is performed for up to 8 satellites, at which point the positioning process is completed.

Further, in some embodiments of the present invention, the phone continues to transmit frames of the reverse link to the base station while performing the positioning process. These frames may simply remain empty information to allow the base station to remain synchronized with the subscriber unit, or the frames may contain additional information such as power control commands or information requests. The frames are preferably transmitted when the RF circuitry is available and no GPS samples are collected, or if sufficient RF circuitry is available, when GPS samples are collected.

Although the 18ms integration time is used to avoid the code doppler effect, sending data to the GPS signal at the 50Hz rate causes problems if the data changes within the 18ms processing interval (as described above). The data variations cause a shift in the phase of the signal. For each satellite, a 50Hz data boundary occurs at a different place. By varying the path length from each satellite to the phone, the 50Hz switching phase for each satellite is effectively randomized.

In the worst case, coherent integration can be completely erased if the midpoint data bit during coherent integration is inverted. Thus, in one embodiment of the invention, the base station must propagate the data transition boundaries for each satellite to the phone (as described above). Preferably, the transmission boundaries are also included in the aiding messages sent from the base station (such as in a set of 5-bit messages that indicate the millisecond interval at which each satellite makes a transition). The phone uses the boundary to divide the coherent integration interval for each satellite into 2 slices and determines whether to add or subtract the coherent integration sum over these 2 intervals. Thus, by including a data boundary for each GPS signal, the reliability of the positioning process is increased.

In an exemplary embodiment of the present invention, any frequency uncertainty produces a loss of Ec/Nt, where the loss increases with increasing coherent integration time. For example, uncertainty +/-100Hz, the loss of Ec/Nt increases rapidly with increasing coherent integration time, as shown in Table I.

Nc	Ec/Nt loss
		1023(1ms)	0.14dB
2046(1ms)	0.58dB
		4092(1ms)	2.42dB
6138(1ms)	5.94dB
		8184(1ms)	12.6dB

TABLE 1

As mentioned above, there is always some unknown frequency offset of the local oscillator in the mobile unit. It is these unknown frequency offsets that prevent longer coherence from despreading and integrating. Longer coherence can improve processing if these unknown frequency offset effects can be reduced.

In one embodiment of the invention, these unknown frequency offsets are taken into account by extending the search space into 2 dimensions to contain the frequency search. For each hypothesis, several frequency searches are performed, where each frequency search assumes that the frequency offset is a known value. By spacing the frequency offsets one can reduce the frequency uncertainty to an arbitrary value, but at the expense of additional computation and memory. For example, if 5 frequency hypotheses are used, the resulting search space is shown in FIG. 10.

For a +/-100Hz frequency uncertainty, which is a typical mobile unit operating specification, the architecture reduces the maximum frequency offset to 20Hz (one assumption must be within 20Hz of the actual frequency offset). The EC/Nt loss with 20Hz frequency offset is 2.42dB for a 20ms coherent integration time. By doubling the frequency hypothesis number to 10, the frequency uncertainty can be reduced to 10Hz, which results in a.58 dB Ec/Nt loss. However, adding additional assumptions widens the search space, which increases computational and storage requirements.

One embodiment of the present invention calculates the frequency hypotheses by aggregating the frequency doppler and frequency offset and calculating a new rotated PN code for each frequency hypothesis. However, this doubles the number of frequency hypotheses throughout the calculation: the 5 frequency hypotheses mean 5 more calculations.

On the other hand, in another embodiment of the invention, the rotational phase may be considered constant over a 1ms interval (assuming 8% of one period for 80 Hz) due to the small frequency uncertainty compared to frequency doppler. Thus, by dividing the coherent integration interval into sub-intervals as long as 1ms, the sum of the integrals of the sub-intervals is rotated to reduce the amount of additional computation required to search for the computation frequency by 3 orders of magnitude. The result is that longer coherent despreading can be performed and performance improved.

Fig. 12 is a block diagram of a receiver constructed in accordance with a despreading method that employs longer coherence. The first set of multipliers 50 compensates for frequency doppler by correlating IQ samples with the rotated C/a code. This is equivalent to inThe unchanged C/A code takes the rotated IQ samples prior to correlation. Since frequency doppler can be as long as 4500Hz, each chip can be rotated. After coherent integration with accumulator 52 over a 1ms interval (1023 chips), second set of multipliers 54 rotates the 1ms sum of integrals (\ u)_IAnd_Q) To implement the frequency hypothesis. The rotating sum is accumulated over the entire coherent integration interval.

Recall that the frequency doppler rotation is computed only on 1023 chips to save memory and computation. For coherent integration times longer than 1ms, each coherent integration sum is multiplied by a phase offset to continue the rotational phase in time. To show this mathematically, the 1ms coherent integration sum with frequency doppler rotation can be expressed as follows:wherein_-I=Re{S₁And_-Q=Im{S₁}

where I (n) and Q (n) are input samples received on the I and Q channels, respectively, C (n) is an unrotated C/A code, W_dIs the frequency Doppler sum, T_cIs the chip interval (.9775 us). The 2ms coherent integration sum can be expressed as follows:

here, S₁Is the first 1ms integral sum, and S₂Is used for calculating S₁The second 1ms integrated sum of the same rotational C/a value calculation.The term is to compensate for phase offsets that apply the same rotation value. Similarly, the 3ms coherent integration sum can be expressed as

To extend the integration time, the same 1023-unit rotated C/A sequence is applied simultaneously, (n +1)1ms integration and should be matched with e before adding to the sum^-jwdn(1ms)Multiplication. Since this is a rotation of the 1ms integral sum, we combine this operation with a frequency search to avoid performing 2 rotations. That is, due to

We sum the (n +1) th 1ms integral with e^{-j(wd+wh)n(1ms)}The multiplication searches for the frequency hypothesis and takes into account the frequency doppler phase shift.

Note that since the frequency uncertainty is not satellite dependent, the frequency search can be reduced after one satellite is acquired. If longer coherent integration is required, a finer frequency search can be performed.

In the exemplary embodiment of the present invention, the fine search is performed in a similar method to the coarse search. But with a 2 point difference. First, the integration interval is always a coherent addition, rather than a squaring and non-coherent addition. Second, the rotation that removes the frequency uncertainty (which should be known after the coarse search) is combined with the frequency doppler phase offset and added together after rotating the 1ms coherent integration interval.

In another embodiment of the invention, the integration time is longer than 18msA coherent integration window of data is integrated. This embodiment is useful if additional memory is available. For coherent integration longer than 18ms, the 50Hz data boundaries are processed the same as those performed during the shorter integration period. The base station indicates for each satellite where the boundary is and the DSP decides whether to add or subtract 20 1ms coherent integration intervals to its operation sum.

However, since the product of the frequency uncertainty and the integration time constant affects the Ec/Nt loss, the frequency uncertainty must be reduced to a small value over a long coherent integration interval. Since integration at 20ms with 20Hz frequency uncertainty results in a 2.42dB Ec/Nt loss, keeping the same loss requirement at integration time 400ms reduces the frequency uncertainty to 1 Hz. To correct this problem, the frequency uncertainty needs to be reduced to 1Hz by a hierarchical approach. For example, a first frequency search reduces uncertainty from 100Hz to 20Hz, a second search reduces uncertainty to 4Hz and a third search reduces uncertainty to 1 Hz. The frequency search will compensate for the error in the frequency doppler acquired from the base station.

Furthermore, to perform longer integration, only satellites with similar doppler are searched for the same data over a long integration time because the code doppler is different for each satellite. When the DSP collects the coherent integration data window, it calculates the time required for the slip 1/16 chips and rotates the decimator. Further, a plurality of data windows are employed in this embodiment.

Thus, methods and apparatus for performing positioning in a wireless communication system are described. The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (6)

1. A method for performing position location in a wireless communication system using a set of signals transmitted from a set of satellites, comprising the steps of:

(a) receiving a signal sample;

(b) rotating the acquisition code by a first rotation amount, thereby generating a rotated acquisition code;

(c) despreading the signal samples using a rotating acquisition code to produce despread data;

(d) accumulating the despread data over a first duration of time to produce partially accumulated data;

(e) rotating the partially accumulated data by a second rotation amount, thereby generating rotated data;

(f) accumulating the rotation data.

2. The method of claim 1, wherein the first rotation amount corresponds to a larger offset and the second rotation amount corresponds to a smaller offset.

3. The method of claim 1, wherein steps (b) - (f) are performed for each satellite.

4. The method of claim 1, wherein the first duration is less than 2 ms.

5. The method of claim 1, wherein the second duration is greater than 10 ms.

6. The method of claim 1, wherein said accumulating is performed coherently.