# Device and method of high-speed detection of gps signals

FIELD: radar-location.

SUBSTANCE: invention relates to methods and a device for establishing location of a receiver using GPS signals. The invention employs signals of GPS transmitters, which comprise a unique periodically recurring pseudonoise (PN) sequence. The invention is especially useful in non-synchronised systems, for example A-GPS, used in GSM and UMTS systems for mobile telephones. A received signal is stored in a receiver for at least two repetition periods of the PN sequence. A fast Fourier transformation operation is done (FFT), and frequency samples of data are obtained, which are curtailed in response to a hypothetical residual frequency. This cuts the number of the next required calculations and processing time. Correlation series are determined from the curtailed samples and reference frequency samples of the corresponding hypothetical transmission. If conformity is detected, the displacement of code shift is determined. Otherwise the process is repeated with another hypothetical residual frequency. Several similar obtained correlation series can be joined incoherently.

EFFECT: device and method of detecting GPS signals.

25 cl, 13 dwg

__The technical field to which the invention relates__

The present invention relates to a device and methods for calculating the location of a mobile device using radio signals, such as GPS systems.

__The level of technology__

Device location is becoming more and more popular. This contributes to the development of high-speed, highly sensitive methods of detection signals used for positioning.

Technology positioning is usually used to determine the position of the radio signals simultaneously transmitted from known locations. In GPS systems these signals are simultaneously transmitted from multiple satellites at a certain time and at a predefined frequency. On earth, the GPS receiver detects the signal from each satellite within its field of view. The times of arrival of the signals, along with the exact location in the field of view of the satellites, and the exact time of signals transmitted from each satellite are used to determine the location of the GPS receiver using the trilateration calculations.

Detection signals from GPS satellites can be difficult due to many factors. For example, GPS signals are passed with relatively low power and long distance. During the passage of GPS signals from earth orbit to their receiver and the initial low power is greatly reduced, providing an extremely weak signal receiver. The levels of the received signal can be further weakened by the effects of shading by buildings, for example, during the reception in the room or reception in urban conditions.

There are two main functions of the GPS receiver: (1) the calculation of the pseudorange to the various GPS satellites, and (2) calculating the location of the GPS receiver using these pseudorange, satellite synchronization and ephemeris data (location). The pseudorange relate to the time delay (or equivalent distance) between the satellites and the GPS receiver, as measured by the offset hours local time. In conventional standalone GPS receivers, the ephemerides of the satellites and the time data extracted from the GPS signal, after he was discovered and tracked. The collection of this information usually takes a relatively long time (30 seconds to several minutes) and should be performed with a good level of the received signal to achieve low coefficients of error.

In fact, all known GPS receivers use the methods of correlation or their mathematical equivalents to calculate the pseudorange. These methods of correlation are performed in real time, often with the help of hardware correlators. The GPS signals include signals with a high rate of repeat is rhenium, which are modulated in accordance with the special sequences or codes, called pseudo-random (PN) sequences. Codes available for civil applications, called codes C/A and are used to provide speed binary tipping phase or speed of transmission of the signal elements equal to 1.023 MHz, and the repetition period of 1023 elements of the signal over the period of the code, equal to 1 MS. Pseudo-random sequence in the GPS belong to the family known as "Gold codes". Each GPS satellite transmits a signal with a unique Gold code.

For brevity, the following discussion we can use the terminology signal contains a pseudo-random sequence (or code), by which we mean that it contains an oscillatory signal that is modulated in accordance with a pseudorandom sequence or code. The frame length pseudorandom sequence represents the number of symbols of the sequence before it repeats. The duration (in time) pseudo-random sequence, we mean that the length of the oscillating signal modulated in accordance with a pseudorandom sequence. Similarly, when we say "the frame rate pseudo-random sequence, m is implied repetition rate of the oscillating signal, modulated in accordance with a pseudorandom sequence. From the context it should be clear whether the term "pseudo-random sequence to the sequence of numbers or oscillatory signal, modulated according to the following sequence of numbers.

After the signal was passed from a particular GPS satellite, followed by the conversion process with decreasing frequency to baseband, the signal is correlated with a reference signal. For example, the simple correlation receiver multiplies the received signal to a locally generated reference signal containing the stored repeat the corresponding Golden code contained in its local memory, and then integrates (for example, performs low pass filtering the result to obtain an indication of signal presence.

The process is simple individual correlations can lead to the same number of (possibly complex). However, many of interest, calculates the set of such numbers according to different reference sequences (e.g., versions with delay), in series or in parallel, by performing similar operations. This set of numbers referred to in this description as "the correlation series. The end result of a merger of one or more sequence is selected correlation series is called "the final correlation series.

Incrementally adjusting the relative synchronization of the stored replica related to the adopted signal, and for tracking the emergence of high power in the final correlation series, a simple receiver can determine the time delay between the received signal and the local clock. This time delay modulo the period of the code, one millisecond, called "shift code". Unfortunately, the process of detecting correlation requires time-consuming, especially if received signals are weak. To improve the detection time most conventional GPS receivers use multiple correlators (usually up to 12), which allows parallel search for correlation peaks.

Some GPS receivers use the methods fast Fourier transform (FFT) to determine the Doppler frequency of the received GPS signal. These receivers use the normal operations of the correlation for narrowing the spectrum of the GPS signal and provide a narrowband signal with a wide range, generally being in the range from 10 to 30 KHz. Then the received narrowband signal is analyzed using Fourier analysis, using the algorithm of fast Fourier transform (FFT) to determine the carrier frequency. The definition of such carrier concurrently provides the features is also that the local reference PN corrected with the right shift code of the received signal and provides an accurate measurement of the carrier frequency. Then, this frequency can be used in subsequent operations tracking receivers.

For example, one method of positioning algorithm uses the fast Fourier transform (FFT) to calculate the pseudorange at the location of the centralized data processing, and not in a mobile unit. According to this method, a snapshot of the data collected using the GPS receiver and then transmitted over the data transmission channel to a remote receiver where it is processed using a fast Fourier transform (FFT) to calculate the final correlation series. However, to perform a set of correlations is usually calculated only direct and inverse fast Fourier transform (corresponding to four periods (intervals) PN).

Another method uses the methods fast Fourier transform for the detection of GPS signals and includes the digitization, preservation and processing of a long block of raw data. For example, data corresponding to one of the secondary interval can be digitized, and then processed locally using the method of signal processing based on the fast Fourier transform (FFT)to detect GPS signals, when westwoodi captured in this data block. This method involves many operations, fast Fourier transform (FFT), each forming a correlation series and the results are coherent and non-coherent transactions processing to form the final correlation series.

Unfortunately, the detection method of the GPS signal in such systems becomes less efficient at executing a long coherent integration, for example, exceeding the period of one bit of data (for example, 20 frames GPS, which is equal to 20 milliseconds). The efficiency loss is particularly large when the inaccuracy of the carrier frequency of the GPS is great. In addition, widespread receiver GPS coherent integration for periods greater than one bit of data requires that the GPS receiver a priori was known sequence of bits. Therefore, the coherent integration is usually performed for periods greater than one bit of data through the transfer of such information from the server to the mobile station. This General method has been standardized in several cellular standards, including IS-95, CDMA2000, GSM and UMTS.

Other prior methods of coherent processing can be applied when (1) takes a long coherent integration, (2) requires a search through a wide range of Doppler frequencies (3), should be the issue is lnen search shift code for all 1023 elements of each signal of the GPS signal, which will be processed. However, such prior methods have many limitations and interference. For example, these algorithms may require data in the form of a two-dimensional array, and also to limit the amount which can be efficiently searched Doppler shift frequency.

__Disclosure of invention__

The described method and device for receiving and processing one or more signals transmitted from multiple transmitters at predetermined frequencies. Each of the transmitted signals includes an oscillatory signal that is encoded according to a recurrent sequence that uniquely identifies the transmitter that sent each corresponding signal. The received signals are used in determining the location of the receiver. The transmitters may include multiple GPS satellites that transmit GPS signals to the GPS frequency, each GPS satellite transmitting the oscillating signal encoded according to a unique repetitive sequences. Shift shift code signal is at the receiver, and using this information from several transmitters can be installed in the location of the receiver using GPS algorithms.

Higher sensitivity and a higher processing speed can be the ü achieved through the operations of the fast Fourier transform (FFT) on the monitoring data; together with the operations of the fast Fourier transform (FFT) used special operations reduction, based on a hypothetical residual error in frequency to reduce the overall number of calculations and therefore reduce the time of processing.

In particular, in the receiver the signal is recorded and digitized at a predetermined frequency for a predetermined period of time corresponding to at least two repetitions of the repetitive sequences (two frames). One of the many transmitters is hypothetical and is provided with a set of samples of the reference frequency corresponding to the hypothetical transmitter. The first subset of the digitized data is selected from a duration at least equal to two frames, thereby defining a block of data. Then this block calculates the set of samples of frequency data, for example, by using techniques of Fourier transform.

The first residual frequency is hypothetical, and then the sampling frequency reduced data, depending on the hypothetical first residual frequency to provide periodically spaced first subset of samples of frequency data. Then processed the first subset of samples of frequency data, and samples reference frequency (usually with multiplication and procedure about the feats of the fast Fourier transform (FFT)) to provide the first series of the correlation data.

Then this procedure can be repeated for additional data blocks (usually continuous), and many similar correlation was found series can be found and added to form the final correlation series. Then in this last series of searches to identify matching signal, usually by finding a strong peak in the final correlation series. If the corresponding signal is found, the offset shift code is determined from a finite series data correlation; however, if the corresponding signal is not found, the other residual frequency can be hypothetical, and then the process is repeated, usually using the same sets of samples of frequency data, and samples reference frequency, to match the signal. Similar processing is performed to find a match signal, or until it will be put forward hypotheses about the residual frequencies without compliance with the hypothesis that the signal from a hypothetical transmitter may not be detected.

Typically, there are multiple transmitters, which may be in a field of view of the receiver, and this process can be repeated for each of these transmitters to identify signals and, if possible, determine the displacement of the shift code from each transmitter.

Can be done many is estvo other embodiments. In one embodiment, the step of reducing further comprises the step of selecting a subset of samples of frequency data, and the subset includes many samples with indexes, placed at intervals relative to each other by an integer K, and K represents the number of frames of the sequence PN in the data block.

It should be noted that in this paper we sometimes use the terminology "PN sequence" or "frame PN for F(t), repeated recruitment of the PN sequence that is not strictly correct, since the PN sequence is actually a sequence of numbers that is used to form the modulating carrier signal, thus forming an oscillatory signal F(t). However, from the context it should be clear whether "PN sequence" refer to the fact that the oscillating signal is modulated by a PN sequence F(t) or direct sequence.

In another embodiment, the method further comprises the step of multiplying the subset of samples of frequency data on a set of samples of the reference frequency to generate a set of weighted samples frequency.

Sample reference frequency obtained using any suitable method, for example, the receiver may perform an operation of thesis the specific Fourier transform (DFT) in one or more periods of repetitive sequences to determine samples of the reference frequency, moreover, the sampling reference frequency can be pre-computed for each transmitter and stored in the receiver, or the sampling frequency reference can be downloaded from described in this document server, for example, the PDE.

The step of performing the correlation operation may include a step of performing inverse discrete Fourier transform to a set of weighted sampling frequency to generate a series of data correlation.

Each data block may have a size that corresponds to an integer number of repetitions of the repetitive sequences is 2 or more, for example, 5, 10, 20 or more. The data block in some embodiments, the implementation may have a size within a range of approximately 5-20 repetitions of the repetitive sequences. In other embodiments, implementation of the data block may have a size of about 100 repetitions.

The aforementioned method can be implemented in suitable hardware and/or software in the receiver, and/or on one or more servers in the wireless network. For example, some functions may be implemented in the receiver, and some features can be implemented in a logical object location (PDE).

Disclosed herein an apparatus and method is particularly useful on the I auxiliary systems GPS ("A-GPS"), they are not synchronized communication system that provides supporting information to the GPS receiver, as in the case of the cellular standards GSM and UMTS. Despite the fact that in the synchronized communication systems, such as CDMA2000, the requirements imposed on the search shift code is very relaxed, there is still benefit from the use discussed here improved algorithms.

__Brief description of drawings__

Further reference is made to the accompanying drawings, which depict the following:

Figure 1 is a perspective view of the system of communications and positioning, which includes satellites that emit GPS signals, which are received by the GPS receiver in the mobile station that communicate with multiple base stations;

Figure 2 - block diagram of one possible implementation of the mobile station includes a GPS receiver and cellular radio communications system;

Figure 3 is a block diagram that illustrates described in this document the process of coherent integration;

4 is a block diagram that illustrates the structure and components of the oscillating signal of theoretical signal GPS;

5 is a chart that depicts the power spectrum as a function of frequency of the GPS signal (Golden code #1 in this example), repeated 20 times, and the residual carrier frequency f_{e}=0;

6 is a chart that is such is depicted in Figure 5, depicting the power spectrum as a function of frequency of the GPS signal (Golden code #1 in this example), repeated 20 times, but with a residual carrier frequency approximately equal to 4.5 kHz;

Fig.7 is a diagram of one example of results of operations for the filtration of conformity, showing amplitude as a function of frequency;

Figa, 8B and 8C is a set of graphs comparing the results of matched filtering for differences of Doppler frequency hypotheses;

Fig.9 is a diagram that depicts a set of frequency data, which represents the frequency spectrum typical of actual data; and

Figure 10 is a table that depicts the subset of samples of frequency data corresponding to the displacements of the hypothetical frequency, illustrating the method, as defined subset for frequency selection hypothetical residual frequency.

11 is a block diagram that illustrates the processing includes combining results of multiple processes of coherent integration.

In the various figures the same reference numbers denote identical or similar parts.

__The implementation of the invention__

Figure 1 illustrates the environment of the GPS, which includes many 11 GPS satellites (SV). Despite the fact that the environment GPS already described, the system described herein may be implemented in any system positioning (positioning). The 11 satellites emit signals 12 GPS that are accepted by many terrestrial base stations 10 that are part of a communication network, and a mobile station (MS) 14 that communicate with the base stations. Mobile station 14 (MS) includes a GPS receiver and two-way communication system for communication with the base stations using the signals 20 two-way communication. The GPS receiver can be implemented in a wide variety of options for the implementation of mobile stations (excluding cell phones)that communicate with one or more base stations. The user 13, owning a mobile station (MS) 14, which may be placed in a wide variety of environments that can be fixed or be in motion.

11 GPS satellites (SV) include a group of satellites that transmit signals that are used to determine the location of the GPS receiver. The satellites are synchronized to send radio signals 12, phased to GPS time. These signals are generated at a predefined frequency and a predefined format. In the current implementation each GPS satellite (SV) passes civil type of GPS signal in the frequency band L1 (1575.42 MHz), formatted in accordance with the standards of the GPS. Upon detection of GPS signals through a conventional GPS receiver in the mobile station (MS) GPS system calculates the pseudorange for each is about from GPS satellites, of which can be calculated location of the mobile station (MS).

Pseudomallei is defined as: s·(T_{user}-T_{sv})+cT_{bias}where C is the speed of light, T_{user}- the GPS time when the signal was taken from this satellite (SV), T_{sv}- the GPS time when the satellite has transmitted the signal, and T_{bias}error in hours local time the user normally present in the GPS receiver. Sometimes pseudomallei is determined by omitting the constant "c". In the General case, the receiver must solve four unknowns: X, Y, Z coordinates of the receiver antenna) and T_{bias}. The solution of these four unknowns usually requires measurements from four other satellites (SV); however, under certain circumstances, this restriction can be weakened. For example, if the available accurate estimate of the height, the required number of satellites (SV) can be reduced from four to three. In the process, A-GPS

T_{sv}not necessarily available to the receiver, and instead of handling the true pseudorange receiver relies primarily on changes to the code. In the current implementation of GPS code changes have the error of measurement of time equal to one millisecond, as the PN codes are repeated every millisecond. Sometimes it can be installed boundaries bits of data, thereby producing only the measurement time is 20 milliseconds.

BA the new station 10 contain any collection of base stations, used as part of a communication network that communicates with a mobile station (MS) 14 using radio signals 20. The base stations are connected to the infrastructure of the cellular network 15, which provides communication services to a variety of other communication networks, such as telephone system (network) 16 General use, the computer network 17, for example, the Internet, the logical object 18 location (PDE) and a variety of other communication systems, which together are shown in block 17a. The reference GPS receiver (or receivers) 19, which may be located inside or near the base station 10, or in any other suitable location that is reported with the PDE 18 to provide useful information in determining the location of, for example, information about the location of the satellite (SV) (ephemeris).

The ground infrastructure of the cellular network 15 typically provides communication services that allow the user cell phone to connect to another phone on the telephone system 16 for General use. However, the base station can also be used to connect with other devices and/or for other communication purposes, for example, for Internet connection with laptop pocket computer (PDA). For example, the base station 10 can be part of a network GSM communication, but they can also be used in other types of communication networks synchronous (in the example, CDMA2000) or asynchronous transfer.

Figure 2 - block diagram of one possible implementation of the mobile device 14 connected to the communication system and positioning. System 22 two-way communication, such as cellular communication system associated with the antenna 21, which communicates using the signals 20 cellular communication. Cellular communication system 22 may include a suitable device, for example, a modem 23, hardware and software for messages and/or signals 20 detection of base stations and processing of transmitted or received information.

System 27 of GPS location in a mobile station (MS) connected to the antenna 28 GPS to receive 12 GPS signals, which are transmitted on the perfect GPS frequency or close to it. System 27 contains GPS receiver 29 GPS, which includes a bias circuit frequency and analog-to-digital Converter, watch GPS, control logic to control the desired functions of the GPS receiver, and appropriate hardware and software for receiving and processing GPS signals and to perform calculations necessary for determining location using a suitable algorithm for determining location. In the illustrated embodiment, the location system analog-to-digital Converter connected to the buffer memory is, while the buffer memory is connected with the scheme of the discrete Fourier transform (DFT) to provide and store data during operation of the discrete Fourier transform (DFT). In some implementations, A-GPS end computing location (e.g. latitude and longitude) can be executed on the remote server, based on the shifts of the code and other information sent from the GPS receiver to the remote server. Some examples of GPS systems are disclosed in U.S. Patent No. 5841396, 6002363 and 6421002.

GPS watch designed to support accurate GPS time, however, as is often the exact time is not available to establish the location, it is common practice to support time in the software of hours GPS through its hypothetical values and inaccuracies associated with this value. It may be noted that after the establishment of the precise location of the GPS time, GPS will often be known exactly (within uncertainties, equal to several tens of nanoseconds in the current implementation of GPS). However, after the final calculation of the location on the remote server, this is the exact time may only be available on the server.

System 25 controls the mobile device is connected with the system 22 two-way communication with the system 27 of the positioning. System 25 in the manage mobile device includes any suitable structure, for example, one or more microprocessors, memory, other hardware, firmware and software to ensure the appropriate management functions connected with them system. Described in this document, the processing steps can be carried out in any suitable way.

System 25 control connected with the user interface 26, which includes any suitable components for the front-end user interaction, for example, a keypad, a microphone/speaker for services (services), voice communication, and display such as a liquid crystal display with backlight. System 25 mobile device management and user interface 26 is connected to the system 27 location and provide appropriate input-output GPS receiver and two-way communication system, for example, control user input and presentation of results.

Next, with reference to Figure 3 and other figures, described is an example of how coherent processing. Figure 3 is a block diagram that depicts a series of steps that are performed in the mobile station for processing the received GPS signal to identify whether or not it corresponds to the hypothesis that selects the GPS code and carrier frequency offset. The algorithm to magamiskoht all possible shift shift code (for example, 1023 offset) to attempt to match the displacement of the shift code for the selected code GPS. The algorithm then coherent processing is repeated for each GPS code, which may be in a field of view of the mobile station. Additional non-coherent processing can be added to the algorithm shown in figure 3, to further improve the sensitivity. For simplicity, this added complexity is discussed later with reference to 11.

Figure 3, on the stage 30 is designated, the operation for monitoring a GPS signal. Essentially, the receiver receives electromagnetic energy from the carrier frequency close to the carrier frequency of the GPS, with the hypothesis that GPS signals are present and are findable. The GPS signal (if present) are observed over time, at least, a period of T_{c}period of time for which the block of data is taken for coherent processing (T_{c}can also be referred to as a "data block" or time coherent integration (processing) signal).

In the absence of noise functional form of the GPS signal s(t) can theoretically be represented at any time t as follows:

s(t)=Ad(t)P(t)exp(j2□ft+□) (A1)

where A is the amplitude of the signal d(t) is a sequence of data having a relatively low transmission speed (for example, 50 bps), which modulates the carrier (for example, pose the STV-off phase manipulation),
P(t) is oscillatory signal, consisting of a set of repeating frames of the sequence PN F(t), f is the carrier frequency (which is ideally equal to f_{0}), and □ - phase carrier. For example, if the transmission rate (for example, elements of signal) is 1.023 MHz, F(t) has a length of 1023 elements of the signal, therefore, the frame rate PN must be equal to 1 kHz, and P(t) to have a length equal to K□1023 elements of the signal.

It may be noted that equation (A1) is a complex representation of the carrier, which can be useful when using selective quadrature methods for signal processing, of course, that can be used and other views as appropriate. In the real environment must be recognized that the various parameters can not be completely constant, but for explanatory purposes, we assume that the signal amplitude and varying the modulation speed is approximately constant.

4 is a diagram that represents the structure of the ideal GPS signal described in equation (A1). The GPS signal is formed from the series of frames PN marked with the reference number 45, each of which includes an oscillatory signal F(t) 46, which dwuhfazno modulated according to the specific noise ("PN") sequence and the carrier frequency 47. Individual repeat F(t) is called the by "frame PN".
Each frame PN has a predefined period of T_{r}. Under the reference number 48 shows data transition data sequence d(t)occurring at the beginning of one of the illustrated frame PN, however, that the sequence of data d(t) has a relatively low transmission rate, the data 48 transition occur only once in 20 PN frames (for codes C/A American GPS) and therefore, data transfer can meet or not to meet at the beginning of the arbitrarily selected frame PN.

Each GPS satellite (SV) transmits a unique oscillating signal F(t) of the frame PN, marked reference position 46, which is a series of signal elements transmitted at a predefined speed. Oscillatory signals PN differ from each other by a specific PN sequence used for two-phase manipulation of the carrier. For example, these sequences can be selected from a set of Gold codes in the vibrational signals C/A of the American GPS system.

In one example, the transmission speed of the signal elements is equal to 1.023 MHz and, therefore, the frame rate PN is equal to approximately 1 kHz. The oscillatory signal F(t) is repeated continuously, for example, the first code from the first satellite SV_{1}repeatedly transmits a unique sequence F_{1}(t), SV_{2}repeatedly passes from calinou sequence PN F_{
2}(t), etc. GPS Receiver is programmed with a unique PN sequences for all GPS satellites that may be in sight. These sequences PN can be used in the algorithm to identify a particular satellite, in particular, when a satellite signal is accepted in the GPS receiver, the PN sequence is used to identify a companion that gave the received signal. However, initially the GPS receiver is not known the actual moment of the received shift code, which, as described above, may be located within the entire frame PN (for example, the period of one millisecond or 1023 elements of the signal). In addition, the receiver is not known whether the GPS signal is associated with a particular PN code, findable, as it can be attenuated by a variety of obstacles and/or, possibly, by the fact of not finding the particular satellite SV in the field of view. Therefore, the receiver must perform serial or parallel search over the range of time of uncertainty in an attempt to detect a hypothetical signal and to synchronize the time of the received frame with GPS point locally generated reference frame.

In actual use conditions, the GPS receiver simultaneously receives multiple signals, such theoretical signal defined in equation (A1), each of to the which has a unique PN sequence F(t). For example, in a typical situation, the GPS receiver typically takes 8-12 signals from many in the field of view of the satellites at any time and the various parameters that differ from each other due to different path lengths, direction of arrival and, for example, the Doppler frequency shifts. For illustrative purposes, first discusses the processing of one of the signals of theoretical form of equation (A1), followed by a demonstration of how can be used are described in this document processing algorithms for processing multiple signals, each of which has a theoretical form of equation (A1).

When GPS signals reach the receiver, they are often greatly distorted by additive noise, and may also be distorted by other noise or interference. In addition, it may seem that the carrier frequency and the transmission speed of the signal elements are slightly shifted from its original value, primarily by Doppler effects. Thus, the carrier frequency can be slightly shifted, as observed by a receiver in a mobile station (MS), due to the motion of the satellite (SV) and mobile station (MS), and, therefore, when the receiver receives the signal actually received carrier frequency varies from its ideal predetermined carrier frequency f_{0}by size, name is Noah "residual frequency".
In addition, errors in the local oscillator of the mobile station (MS) also causes the carrier frequency to vary from the ideal frequency.

Returning again to Figure 3, at step 31 the carrier frequency is "removed" from the GPS signal by means of a suitable circuit for the frequency offset, leaving a residual frequency f_{e}. To remove the carrier frequency is usually the GPS signal is first converted into an intermediate frequency (IF) by means of the frequency Converter is then treated to reduce the remaining component IF for approximate zero by any suitable analog or digital techniques. For example, the frequency of the IF can be approximately removed by another frequency Converter or after converting GPS to a digital signal in analog-to-digital Converter can be used mixed methods of digital processing. In some implementations diagram of the frequency conversion can provide end frequency having a known frequency offset plus the aforementioned residual frequency. Because it is a little known frequency offset is a known constant, post-processing is only needed to determine the residual frequency. For simplicity, the following discussion we assume that it is a little known offset is zero. However discussed in this paper methods and eliminate the STV is equally applicable to the case,
which is known offset is non-zero.

Typically, the residual frequency occurs primarily due to Doppler effects. In addition, the receiver may enter a small frequency shift for signal processing. The sum of these two errors from the ideal carrier frequency can be represented by a maximum permissible deviation (∆f). Therefore, the actual received carrier frequency is typically in the range of f_{0}±∆f. Residual frequency f_{e}that is equal to the frequency remaining after the receiver attempts to reduce the initial carrier to zero, is typically in the range from several hundred Hertz to several kilohertz, despite the fact that the residual frequency can be greater or lesser in any given set of circumstances.

In systems with A-GPS predictable correction of the Doppler frequency for all GPS signals transmitted from one to the other) from the PDE to the GPS receiver, and a list of GPS satellites that may be in the field of view, also send to the receiver so that the GPS receiver can more effectively search for satellite signals. Projected flow data can be provided by PDE.

In his memory, the receiver stores the PN codes (or their representation, for example a discrete Fourier transform of these is W), appropriate for all GPS satellites that may be in his field of vision.

At step 32 the processed GPS signal is digitized (i.e. selected) for a predefined period of time in an analog-to-digital Converter (if it was not previously converted), and then stored in the buffer memory in the GPS receiver. There is not a theoretical limit to the size of the data set or the rate of data sampling, although it is sometimes advantageous to the sampling rate was divisible by the number 1,024 MHz, and that the data set size was an exact multiple of 1024. Therefore, the signal of equation (A2) is assumed to be selected (discretized) signal, where the sampling rate can be set equal to 1,024 or 2,048 MHz, so in order to 1024 or 2048 samples occurred during the period of the frame PN, one millisecond. Due to errors caused by Doppler shift, this sampling rate is not quite equal to the transfer speed of signal elements or double the transfer speed of signal elements. One reason for choosing this rate of sampling is that, if sampling is performed on 1024 or 2048 MHz, the resulting number of samples per period of the frame, one millisecond, is a quadratic power that is convenient for efficient processing fast Fourier transform (FFT). Thus, one frame of data is to ATiM 1024 samples and has a convenient size for efficient fast Fourier transform (FFT), and the full size of the dataset (for coherent processing) is also a multiple of 1024 and the second degree of this length. This limitation, however, is not essential because there are efficient algorithms for the case when the number of samples per frame is not a multiple of the second degree.

At step 33, the data block for coherent processing is determined by selecting a part of the stored digital data for a predetermined period of T_{c}coherent processing. The time period for which data are combined for coherent processing, is usually chosen in order to include large integer frame PN (for example, 20 frames PN). However, the unit of coherent processing should not be chosen too long, because the stability of the residual carrier frequency f_{c}and other effects of multipath propagation (and possibly other factors) for long periods of time may limit or prevent the increase of efficiency. As discussed, it may be advantageous to choose T_{c}the exact number multiple of one period T_{r}frame PN.

Figure 4 the GPS signal is observed at time T_{c}that identifies the data block, for example, the first data block 49a or the second data block 49b, and the time T_{c}is chosen so that the data block had an integer number of frames 45 PN. Due to the fact that the actual block of data taking which is without prior knowledge about the beginning of the frame PN,
the beginning and end of the data block can be located anywhere within the boundaries of the frame PN. For example, by matching the data block may be extended from the beginning of the first frame PN until the end of the last frame PN, as shown by the reference number 49a (shift shift code is zero), but it is more likely that the data block will be extended arbitrarily from approximately the middle of the first frame PN to about the middle of the frame following the last whole frame PN (as shown at reference number 49b), so that the displacement of the shift code is not equal to zero. As will be explained with reference to the shown in figure 3 stages 39-42, for example, the shift of the shift code can be specified using the operation by matched filtering.

In figure 3, at step 34, the sequence optionally removed. After removal of the data sequence d(t) and theoretical conversion of the signal of equation (A1) to the frequency close to the group range, the remaining signal S_{b}(t), ignoring the noise and interference, is of the form:

S_{b}(t)=AP(t)exp(j2□f_{e}t+□) (A2)

where f_{e}residual frequency after conversion of the carrier frequency in a close group range.

Despite an optional feature, removing sequences of data d(t) before treatment can be useful. To aid in the removal sequence given what's in some systems, A-GPS predicted data sequence d(t) send (for example, from the server) on the GPS receiver together with several approximate times of arrival of GPS signals. In these cases, the GPS receiver can delete a sequence of data d(t) and, consequently, to remove the pseudo-random inversion of polarity, which can occur every twenty milliseconds in the signal equation (A1) because of the data sequence d(t). By removing random inversions of polarity (i.e. by removing d(t)), time coherent integration can be extended to longer time intervals than one bit period of the data, for example, more than 100 milliseconds. The increase in time coherent integration may increase the sensitivity of the detection process GPS. As was indicated earlier, some of the future GPS modes may include reporting components that do not contain data. In these situations, the period of coherent integration is not limited to the bit period of the data.

Figure 3 the carrier frequency was approximately removed to ensure signal S_{b}(t) of equation (A2) with a residual frequency f_{e}and the block T_{c}was strictly selected multiple of the period T_{r}frame PN. In other words, T_{c}=KT_{r}where K - the number of frames per period unit. For example, T_{c}could be 100 milliseconds, if K=100, and T_{r}=1 MS.

At step 35, the block of data coherently vrabatyvaetsja,
using the process of the Fourier transform. This stage can be called a process of "direct conversion". For example, fast Fourier transform (e.g., FFT or DFT) of the signal S_{b}(t), is selected for the period of time T_{c}can be done as follows:

y(f)=FFT(S_{b}(t) from t=0 to t=T_{c}) (A3)

The process of direct conversion can be performed in different ways. One widely known method is the decimation in time, the other way - decimation in frequency. As relevant or useful can be used other fast algorithms, such as the z-transform unwanted frequency modulation of the carrier or convert theoretical numbers.

Fast Fourier transform (FFT) of an arbitrary signal (for example, depicted in Figure 9 and discussed with reference to this figure) includes a series of samples of frequency data, separated in frequency by the reciprocal of the duration of the processed block of data. For example, if the duration (T_{c}unit is equal to 20 milliseconds, the sampling frequency spaced by 50 Hz. If the duration of the block is equal to 80 milliseconds, the sampling frequencies are located at intervals by means of 12.5 Hz. Each sample frequency data can be identified by its frequency in Hz or, more conveniently, through its index is (indicator) frequency.
In particular, each sample frequency data of the discrete Fourier transform (DFT) can be defined as a whole number (frequency index), which may, for example, begin with a zero index for the zero frequency. For N-point fast Fourier transform (FFT) the frequency index N/2 corresponds to the frequency in Hz half the speed of the sample, that is S/2. Sampling frequency index N/2+1, N/2+2, etc. correspond to the frequencies in Hz, is equal to-S/2+l/T_{c}, -S/2+2/T_{c}and so on, that is, they represent data corresponding to negative frequencies. If we reorders the data sample by sample selection index N/2, N/2+1, N/2+2... N-1,0,1,2,..., N/2-1, then these frequencies are combined in ascending order (in Hz), starting with the negative frequency and ending with the highest frequency. This reordering is used, for example, figure 5 and 6. In essence, the index frequency is considered circular in order that the index m is equivalent to m+N and m-N. Therefore, the index N/2+m is equivalent to the index-N/2+m.

5 is a graph of a frequency spectrum of theoretical silent GPS signal is close to zero frequency (0) with the above reordering. Figure 5 shows a fast Fourier transform (FFT) with the advent of the characteristics due to the periodic repetition of a PN sequence, which is repeated every millisecond code for the C/A to the American GPS. Pictured quiet fast Fourier transform (FFT) includes a subset of samples of frequency data (spectral lines) 51 with a powerful energy exploded through a set of intermediate samples (not shown) with weak energy. This range is sometimes called the spectrum of the "comb structure and the spacing between successive powerful sampling - frequency index that corresponds K.

In particular, depicted in Figure 5 spectrum of the comb structure - magnitude versus frequency graph of the power spectrum corresponding to the Golden code GPS #1, repeated 20 times, selected within 20 milliseconds and with a residual carrier frequency f_{c}=0, normalized by the largest line amplitude (209 kHz, which is not shown on the graph). In this example, the series of spectral lines with the powerful energy is apart up to about 1000 Hz (1 kHz). Line at 0.0 Hz 51a has an amplitude of approximately-38db line at 1.0 kHz 51b has an amplitude of approximately-11db line at 2.0 kHz 51c has an amplitude of about-13db. Between each pair of powerful spectral lines are present nineteen intermediate lines with an energy that is too low in amplitude to be represented on a logarithmic chart, depicted in Figure 5. For example, at the stage 51a spectral lines are present at a frequency of 0 Hz and 100 Hz.
Spectral lines are present at a frequency of 50 Hz, 100 Hz...up to 950 Hz, but have such a weak energy, they are not shown in the figure. A similar analysis exists for each a powerful pair of spectral lines. Diversity is a powerful spectral lines comb structure, measured in Hz, is equal to the rate (f_{r}) transfer of personnel. Measured in the frequency index differences is the index K, i.e. the number of frames in a coherent block of data.

While Figure 5 depicts theoretical result without the presence of noise, the fast Fourier transform (FFT) of the actual received signal, for example, depicted in Fig.9, would show such a noise that the spectral lines would not be visible directly. In the example depicted in Figure 5, the average noise level of the fast Fourier transform (FFT), which is depicted by reference number 52, normally exceeds the amplitude of even the most powerful of spectral lines.

Figure 9, which depicts a diagram illustrating the frequency spectrum of the fast Fourier transform (FFT) of a typical actual data, which includes many samples of frequency data, generally shown by reference number 90, which together are called the "set frequency"data. Set the frequency of data continues until the highest frequency index (which corresponds to the frequency in Hz S-1/T_{c}). uznesenie frequencies between each of the sampling frequency of the data is equal to the inverse value of the duration of the block (i.e. the inverse value of the time period sample 1/T_{
with}), in this regard, when using the initial ordering of the fast Fourier transform (FFT) the highest frequency index equals STC-1.

In contrast to Figure 5, each of the 90 samples of frequency data, depicted in Figure 9, includes noise, therefore a large amount of energy in each frequency index, in contrast to theoretical spectrum GPS depicted in Figure 5, in which only periodic spectral line at frequency index K) have a large amount of energy. In other words, because of the noise amplitude spectral lines associated with the received GPS signal will be below the noise level and therefore will not be directly visible. As stated otherwise, in the fast Fourier transform (FFT) of the actual data, the average noise energy may be similar in all frequency lines, and therefore the spectrum of the comb structure shown in Figure 5, will not be noticeable and will remain unknown until further processing.

Returning to Figure 3, at the stage 36a created the initial hypothesis for the beginning of the algorithm. It should be noted that the GPS receiver simultaneously receives multiple signals, such as defined in equation (A1) theoretical signal, each of which has a unique PN sequence F(t), and therefore each one provides a unique fast Fourier transformation (FT) of the sequence PN. For example, in a typical situation, the GPS receiver is usually at any time takes 8-12 signals from multiple satellites that are in view, but many of those signals may be too weak to detect. Therefore, there is uncertainty (inaccuracy), against which the satellites provide subject to receiving the signal, and, in addition, even if detectable shift shift code subject to any signal, which determines the time of arrival, is a priori unknown.

On stage 36a is selected or "assumes" a satellite, which may be in sight. The choice of any particular satellite may be random or may be based on any suitable information, such as history (history) or the list provided by PDE. As will be discussed below, the PN code for a selected satellite is checked against the set of hypotheses frequencies (in the range of, usually determined by the receiver), at least until a match is found or all the hypotheses will not be exhausted, and then on the stage 36c selects the next satellite and the corresponding PN code is checked against the set of hypotheses frequency and so on, until all satellites candidates will not be selected or until the signals from a sufficient number of satellites, will not be found to complete the establishment of the location.

She is on the stage 36a is constructed initial hypothesis about the residual frequency. If sufficient information is available to the GPS receiver (for example, it was found the previous location or available estimated correction for Doppler frequency), can be constructed in this initial hypothesis and subsequent hypotheses on the basis of this information. If the information is not available, it can be done best hypothesis and begin searching.

In figure 3, at step 37, is the Fourier transform code GPS, corresponding to a hypothetical satellite. This code, which may be locally generated or pre-calculated and stored, sometimes referred to as "anchor" ID. These codes GPS is widely known, and they are suitable for pre-calculating and storing values for each code GPS GPS receiver. Then these codes GPS can be processed by the Fourier transform, or before or after it is stored in the GPS receiver. For example, the Fourier transform (for example, fast Fourier transform (FFT) or discrete Fourier transform (DFT)may be performed on the holdout data set, consisting of repetitions of the sequence PN F(t), denoted by P(t), as follows:

B(f)=FFT(P(t)) from t=0 to t=KT_{r}=T_{c}) (A4)

The result is a range of comb structure comprising a series of evenly-split lines like the example depicted in Figure 5, which can be called "samples the reference frequency is". Only every K-th sampling frequency B(f) is different from zero, this fact reduces the necessary preservation after a non-zero value will need to be saved.

However, it is likely that it will be more efficient to pre-compute the Fourier transform repeat sequence P(t), and then store only the nonzero processed using Fourier transform values for each code GPS to allow quick use of every time on demand. It is easy to see that these non-zero values can be obtained from the Fourier transform of F(t), not P(t), this fact can reduce the load of calculation. Usually it is enough to compute the fast Fourier transform (FFT) only one recurrence F(t)and not the repetitions, as indicated in equation (A4)as fast Fourier transform (FFT) repeat sequence can be obtained from this shortened fast Fourier transform (FFT). Moreover, the control code GPS, as is usually assumed, is offset shift code zero and the offset of the carrier frequency of zero and, therefore, should be focused on 0.0 Hz and should be similar to the graphic description of Figure 5, and not 6.

The subtlety in the above calculation concerns the fact that the PN code of the American GPS has a length equal to 1023, and the preferred size of the fast is th Fourier transform (FFT) is a power of two, usually or 1024, or 2048 in this discussion. If the pre-computation of the fast Fourier transform (FFT) is performed, the appropriate procedure to create a fast Fourier transform (FFT) of the appropriate size corresponding to the speed of the sample, equal to 1.023 MHz must comply 1023 point fast Fourier transform (FFT) of the reference and added additional sampling zero values between indexes 512 and 513. Similarly, the corresponding procedure to create a fast Fourier transform (FFT) of the appropriate size corresponding to the speed of the sample, equal 2,046 MHz must comply 2046 point fast Fourier transform (FFT) of the reference PN (selected up to two samples per element signal) and to add two additional sampling zero values between the indices of 1024 and 1025. These procedures are methods of interpolation performed in the frequency domain, and are more effective when calculating than running an equivalent way of re-sampling in the time domain. In any case, the fast Fourier transform (FFT) repeatable control sequence can be computed simply by inserting the appropriate number of samples of zero value between each of the samples of the reference frequency, the corresponding fast Fourier transform (FFT) of one frame PN.

In block 35 the ri initial calculation of the sampling frequency during data fast Fourier transform (FFT) of the residual frequency is unknown. For accurate and efficient detection of the GPS signal is this unknown residual frequency must be found. To determine the residual frequency can be used a process of "trial and error", in which a series of residual frequency is hypothetical, performed calculations for each hypothesis and analyzed the results to match. It should be recognized that the number of hypotheses can be increased more, and the processing time increases with the number of hypotheses to be tested.

At stage 38 is selected subset secured on the stage 37 samples of frequency data, that is "reduced" in response to hypothetical residual frequency. As shown and discussed with reference to Figure 5, the ideal GPS signal P(t) has a spectrum comb structure with a periodic frequency spacing (frequency interval) f_{r}that is the frequency interval of the fast Fourier transform (FFT), multiplied by the number of samples in the block, that is, (l/T_{c})**□**K=f_{r}. Because this range of comb structure has a sample different from zero, which occupy only a portion of the actual sampling frequency of the data, it is possible to reduce the complexity and time requirements on the search frequency. As was previously noted, the frequency spacing F_{r}expressed in Hz, is equal to the frame rate PN. Expressed in the indices of the frequency spacing is Aven number of repeated frames PN (K) in the data block.

For example, referring again to Figure 9, if K=20, the sampling frequency of the data corresponding to the hypothetical residual frequency can be selected by selecting specific groups of spectral lines, such as 92a or 92b. Subsequently, P(t) has a spectrum of comb-like structure, which makes the group of narrow-band noiseless received signal s_{b}(t) (see equation A2), due to the fact that it contains a shifted version of the frequency P(t). However, the actual line comb structure of s_{b}not located in the exact same sets of 1 kHz, but is offset by the residual frequency (see Fig.6), which must be defined.

If the sampling rate is equal to 1.024 MHz, the block size is equal to 20 MS, and in block contains 20 sequences PN, then there are only 1024 lines of the discrete Fourier transform (DFT) P(t) with a noticeable energy, as the spacing of adjacent lines of the comb structure of the received signal is 1 kHz. This separation comb structure limits the subset of only 1024 lines frequency data, and therefore, accordingly, in subsequent processing can be used reduced size reverse fast reverse fast Fourier transform (FFT).

In another example, if the sampling rate is equal to 2,048 MHz, 2048 present line comb structure different from zero values, again with the interval of the m frequency comb structure,
equal to 1.0 kHz, but now the energy is distributed over a larger bandwidth in 2,048 MHz. There is no need to sample at a speed that is a multiple of the frequency spacing (for example, 1.0 kHz), and thus it is not necessary that the sampling rate was the capacity of the two times of 1.0 kHz, the spectrum of the comb patterns for S_{b}(t) remains. However, it is desirable that the total period of T_{c}the sample was a multiple of one millisecond to achieve true periodic convolution. Even this requirement may be relieved, as discussed below, likely some performance or speed reduction.

6, which is similar to Figure 5, represents a diagram of the power spectrum of the example of the GPS satellite (code #1), repeated 20 times, but with a residual carrier frequency of approximately 1.5 kHz (i.e. f_{e}=1.5 kHz), and with the spectrum, normalized by the largest line amplitude (occurring at 209 kHz). Comparing Figure 5 and 6 shows the presence of the spectrum of the comb structure in both cases, and also shows that the spectrum depicted in Fig.6, just shifted relative to the spectrum depicted in Figure 5, by the residual frequency f_{c}which in this example is equal to approximately 1500 Hz. Therefore, the hypothesis 1500 Hz (in this example, the true offset of the carrier frequency) will result in the appropriate is the current choice set line frequency,
containing the signal energy. In addition, accented that, even if the spectrum GPS signal appears similar to Fig.6, it can be obscured by noise, similar to that shown in Fig.9, which appears in each sample frequency (not only in the samples of comb-like structures). But the noises that occur between samples of the frequency comb structure of the GPS signal is inappropriate to detect a GPS signal, as they contain a small amount of energy for a GPS signal. Accordingly, in order to detect a GPS signal, we must use only the information about the frequency locations of the lines of the comb structure. As will be discussed below, each frequency hypothesis requires that has been treated with a different set of possible frequency comb structure, in fact, these different sets of possible frequency comb patterns are just a circularly shifted versions of each other.

The terminology "reduction" refers to the fact that we choose only every K-th sample of the data frequency. In the previous example, where T_{c}was equal to 20 HR PN, K was equal to 20, that is, we need to select only every 20th sample data fast Fourier transform (FFT) for use in subsequent processing. More broadly, It is the number of repetitions of the PN code in the coherently processed the m data block.
This reduction leads to a reduction in the number of post-processing.

Further reference is made to figures 9 and 10. Fig.9 is an example of a typical sampling frequency of the data, including noise, which obscures the GPS signal; Figure 10 is a table that shows the subset of samples of frequency data corresponding to the positive displacement hypothetical frequency (for ease of explanation), illustrating the selection of every K-th sample, to determine the subset to select the frequency of the residual hypothetical frequency. For the development of the hypothesis of zero bias frequency, we move the selection to the first subset 92a, which includes every K-th sample, starting from zero frequency index (A_{0}And_{To}...), which shows the reference number 92a in figures 9 and 10 and corresponds to line 0, depicted in Figure 10. For hypothesis one index offset frequency is selected second subset 92b, which includes every K-th sample, but shifted by the same frequency index (A_{1}, A_{K+1}...)that corresponds to the row 1, depicted in Figure 10. For the second hypothesis index offset frequency is selected the third subset 92c, which includes every K-th sample bias on the second frequency index (A_{2}And_{K+2}...). For hypotheses each subsequent frequency offset this process, sometimes referred to as the circular rotation,
continues by converting the selected sampling frequency by an integer. The number of frequency offset may exceed K (respectively greater than the frame rate).

The data set frequency is cyclic, that is, the frequency is similar To, for example, K-N and K+N. Thus, it is seen that the last few data samples of a specific row can actually live up to the first sampling data of the first line. For example, in line 92c, if equal To 2, the last row index 92c will look like this: N-K+2-N=-K+2=0 and the last index of the row 92-d will look like this: N-K+3-N=-K+3=l. Thus, in this example, the last element of the row and 92 92c-d will look like this: A_{0}and a_{1}respectively. Similarly, the hypothesis about the negative offset frequency (not shown in table) will be nominated by selecting the original "negative frequencies". As an example, the hypothesis smallest negative frequency corresponds to the selected data A_{1}, A_{K-1}And_{2K-1}And_{3K-1,}...And_{N-K-1}that is identical to A_{N-1}And_{K-1}And_{2K-1}And_{3K-1}... , And_{N-K-1}. Thus, the first sample of this array is actually the last of the sampling frequency FFT. It may be convenient to rearrange the array, starting from 2, to increase the frequency bol is the most data frequency.

Figure 10 columns define the index of the frequency comb structure", i.e. the index of acronyms arrays containing only elements of N/K Each row defines the values at indices hypothetical frequency comb structure. Undoubtedly, the comb-like structure, starting with a negative frequency offset, are valid and have the line, as indicated above.

Thus, information pertinent to identify the presence of the GPS signal is essentially contained within the spectral lines, which are shifted from each other by a constant (1 kHz in this example) and offset by the residual frequency. Therefore, after the hypothesis of residual frequency can be selected set of spectral lines (comb structure)that corresponds to the offset frequency from FFT and ignore the rest for later purposes of calculating the matched filtering, the corresponding residual hypothetical frequency. This reduced the number of spectral lines can reduce the number of required calculations and, thus, to reduce the processing time for each hypothetical residual frequency. For example, if the sampling rate S, instead of performing inverse fast Fourier transform (FFT) size ST_{C}as it would be otherwise necessary in the operation of the harmonization of the Noah filtering stage 39,
should only be done by inverse fast Fourier transform (FFT) size S/l kHz. Thus, if we assume that T_{c}=128 MS, we may usually have to perform inverse fast Fourier transform (FFT) of size 128 1024, if the sampling rate was equal to 1.024 MHz. Now, taking advantage of the sparsity of the spectrum (i.e. the fact that the GPS signal has a spectrum comb structure), we need to calculate only the inverse fast Fourier transform (FFT) of size 1,024 MHz/1 kHz (i.e. 1024), the savings in processing greatly increases the coefficient of 128 (more precisely: 1,7 128). In addition, the savings in processing improve the total time T_{c}coherent processing. Therefore, it can be seen that reducing the size of the fast Fourier transform (FFT) is associated with the number of repetitions of the sequence PN F(t), i.e. the ratio of the size of the fast Fourier transform (FFT) is improved with a large number of coherently combined PN frames.

At step 39 is executed, the operation for forming the correlation series from a subset of samples of frequency data, and samples reference frequency (for example, code GPS). To achieve this goal, based on the fast Fourier transform (FFT), the matched filtering operation can be performed as follows:

multiplying the selected subset of the frequency data on who is integrated-conjugate of the number of FFT code GPS (A5) and

performing inverse fast Fourier transform (FFT) of the equations A5 and performing discovery operations on the resulting dataset (A6).

The result is a cyclic convolution of S_{b}(t) and P(t), which will provide appropriate information correlation, assuming that the length of S_{b}(t) is an integer number of frames PN. This basic procedure requires the processing of long data sets of length T_{c}i.e. this procedure requires a great amount of the direct fast Fourier transform (FFT). However, there are effective methods of performing such a large fast Fourier transform (FFT), and are widely known. Benefits calculations arise from the need to perform only a small amount of inverse fast Fourier transform (FFT) due to the reduction procedures. As many inverse fast Fourier transform (FFT) may need to be executed, corresponding to many hypotheses frequencies can be realized savings in the calculation. Next it will be mathematically demonstrated in a later discussion.

For purposes of explanation, the method steps 33-39 corresponds to the processing of a single block of data coherent way, which is a type of correlation, which is herein referred to as "coherent correlation" or "coherent, and less the ka". To improve the sensitivity of the correlation results from multiple processes coherent correlation can be detected and grouped by number (for example, from 2 to 2000 units, typically from 5 to 200 units) adjacent time intervals to provide correlation results. This process is called "incoherent correlation", and he later discussed in more detail with reference to 11.

At step 40, is shown in figure 3, the correlation results (series) is analyzed to determine whether a match is found. This operation can be executed in any number of suitable algorithms, similar to those described below.

7 is a graphical example of the results of the correlation operation performed on the stage 39, representing amplitude as a function of a hypothetical shift of the code. The results of the operation matched filtering or correlation operation performed on the stage 39, called the "correlation series. As discussed below, many of the correlation series can be combined coherently and/or decoherence) to provide improved effectiveness. This combined series called "final correlation series, as this series of numbers can be examined to determine conformance conditions. As shown in Fig.7 depicts the result is a series of lines 70, corresponding to different the m code phases, located at regular intervals, typically corresponding to a single element signal or half element signal. To determine whether there was a match is found, can be used in any suitable type of search algorithm to find the peak. For example, you can consider the value of each line. For example, if the magnitude of the line for a particular hypothetical shift code is the greatest of all lines and its amplitude corresponds to or exceeds a predefined threshold value, it can be assumed that a match was found. Depicted in Fig.7 line 72 seems to be the greatest, therefore, if the detection threshold (for example, shown by the reference number 74) is a predefined threshold, the shift code line 72 (i.e. the position 18 of the shift code) is supposed to indicate compliance. Can be used in other algorithms, similar to those that determine all peaks above a predetermined threshold, and then retain all such peaks as potential matches.

Figure 3, after step 40, if a match is not identified, then the process moves to step 41. At step 41, if found greater amount of residual frequency, phase 36b built another hypothesis, and stages 37-40 repeat. However, if a greater amount of residual frequencies are not on the Deno, the process goes from step 41 discussed below in step 43, where it is determined whether there is more satellites to search for. If at step 40, it was a match is found, the process moves to step 42, which is determined by the displacement of the shift code.

As discussed above, for example, with reference to Figure 4, when the selection data block shift code is not known, it is the beginning and the end of the period of the frame PN is not yet established. In particular, despite the fact that the data block has an integer number of frames, PN 45, the original position of the block of data is unknown and therefore the beginning and end of the data block can be located anywhere within the frame PN. For example, the data block may, by coincidence, to continue from the beginning of the first frame PN until the end of the last frame PN, as shown by reference number 49a (shift shift code is 0), but it is more likely that the data block will last from a randomly selected point within the first frame PN, as shown by reference number 49b, to the same point within the frame after the last whole frame PN (shift shift code is not equal to 0).

At step 42, after a positive result of the search (i.e. after stage 40 was a match is found), the shift of the shift code is determined from the results of the matched filtering operation performed in the step 39. the particular before matched filtering operation is known, the number of possible code offsets. In the example described in this document 7, the number of possible code offsets is in the range from 0 to 1023 (a total of 1024 possible code changes if you are using a 1024-point fast Fourier transform (FFT)), and this number is offset shift code steps through the interval of one millisecond. After surgery, matched filtering line 72 (which identifies the correspondence also indicates the offset shift code as the number of stages from zero. In the example depicted in Fig.7, the shift of the shift code is in the location 18 of the shift code, which in this example is shifted by approximately 18/1024 milliseconds. This offset phase refers to the phase of the locally generated clock of the GPS receiver. In many cases, the accuracy of the phase offset improved by the interpolation procedure, which combines the level in the specified shift code with levels in its vicinity.

At step 43, the decision regarding whether or not the signals from more satellites are available for searching. This decision is made in accordance with any suitable criteria. For example, if signals from a sufficient number of satellites have already been found to establish the location and the and if the list of satellites might be in the field of view has been exhausted, it may be decided to terminate the search, and therefore, as indicated at step 44, the operation is detected. However, if you are searching for signals from more satellites than on stage 36c selects the next satellite, it is assumed initial residual frequency and stages 37-42 run with new hypotheses.

When using information about multiple repeat sequences PN F(t) in the coherent processing of the data block, as discussed in this document, it was recognized that a simpler procedure inverse fast Fourier transform (FFT) is available as part of the whole procedure, matched filtering, which reduces the computation time. If you want to find only one hypothesis Doppler frequency shift, the improvement of processing time may not be particularly significant. However, due to the fact that searches are typically performed on a large number of hypotheses Doppler frequency shift (for example, a search for ±500 Hz is not exclusive), then this advantage is the savings in processing, as described in this document, once it becomes significant. One reason for saving in processing is that each hypothesis Doppler frequency shift requires a separate reverse Bystrov the Fourier transform (FFT); however, in discussing here the way the size of the inverse fast Fourier transform (FFT) does not depend on the size of the coherent unit of frequency due to the fact that only requires the processing sampling frequency in the hypothetical locations of the frequency comb structure. The number of such samples frequencies, as can be easily seen, is equal to the number of samples of frequency data one frame PN. In the above example, the size of the processed block is 128 milliseconds, the required dimensions of the inverse fast Fourier transform (FFT) is required to reduce by the value 128, resulting in increased processing speed by the value greater than 128. Despite the fact that must be made large direct fast Fourier transform (FFT), as at step 35, it is a big operation must be performed only once found the GPS code, and in some cases one direct fast Fourier transform (FFT) can be jointly used for a variety of hypothetical GPS codes.

As a rule, to search for a large range of Doppler frequency shift is consistently put forward a large number of hypotheses Doppler frequency shift and are executed one after the other, which thus requires a large number of inverse fast Fourier transform (FFT). For example, the R, to search for a range of residual carrier frequencies fe=±2 kHz, with time coherent integration, equal to 128 milliseconds, requires a number of hypotheses Doppler frequency shift, so there should be plenty of inverse fast Fourier transform (FFT), is equal to at least 512 (4000 kHz×128 MS). In the previous example, the dimensions of the inverse fast Fourier transform (FFT) should only be equal to 1024 points, and not 131072, resulting in time savings calculations by rate approximately equal to 218 (it should be noted that the processing time fast Fourier transform (FFT) is proportional to N log(N), where N is the size of the transform). For example, using currently available technology 1024-point fast Fourier transform (FFT) can be performed for 0.5 milliseconds, using cheap integrated circuit DSP, thus, the resulting total processing time for the entire set of inverse fast Fourier transform (FFT) is less of 0.26 seconds; whereas, if you do not take advantage of the sparsity of data, the processing time will be approximately 1 minute. In addition, because there is a need to search many hypothetical GPS PN codes, the processing time required for conventional processing fast Fourier transform (FFT), may article is to be impractical, whereas with my method it easily becomes practical.

Search on various hypotheses Doppler frequency shift is simplified by recognizing that adjacent spectral lines of the fast Fourier transform (FFT) are separated from each other by a predefined number, which in this example is equal to 1/T_{with}Hz (for example, if T_{c}=128 MS, 1/T_{with}=1/128 MS=7,813 Hz). Therefore, for a given PN code there is no need to perform a direct fast Fourier transform (FFT) for each frequency. To change the frequency hypothesis, we only need to move fast Fourier transform s_{b}through a single location index (the index value is determined as the proper discharge detection signal applied without unnecessary effort). Let y equal the fast Fourier transform (FFT) s_{b}. In the example where the sampling rate is equal to 1.024 MHz, and T=128 MS, if the hypothesis of frequency equal to zero, then we process the sample y, numbered 0, 128, 256,..., etc. If the hypothesis of the residual frequency - 7,813 Hz, then we processed the samples, numbered 1, 129, 257, etc. If the hypothesis of the residual frequency - -7,813 Hz, then we process the sample 131071, 127, 255, and so on (it Should be noted that the index 131071 equivalent to -1, because the spectrum is periodic with period 131071.) Abbreviated printing handling the p block for each case is multiplied by a complex conjugate of the number of non-zero samples of the fast Fourier transform (FFT) GPS reference signal.
The result is converted back to ensure output of the matched filtering, representing one frame of PN.

Peak value (or quadratic value), found above the threshold, the output is a representation of the presence and time of arrival of the received GPS signal with the number of the GPS signal and the Doppler frequency corresponding to used in sequence processing. As discussed below, in some cases we might want to move fast Fourier transform (FFT) by part number index. This can be done by using methods of interpolation frequency, as discussed below, and not by a simple cyclic shift or shift of the set frequency.

On Figa, 8B and 8C shows an example of the results of operations, matched filtering, respectively, for each of the three hypothetical frequency (f_{h}-50Hz, f_{h}f_{h}+50Hz) for the case when T_{c}=20 milliseconds (and therefore spectral line direct fast Fourier transform (FFT) separated by 50 Hz). On FIGU hypothetical frequency is the true frequency, and you can see that there is a strong peaks 82 lead to one particular shift shift code (index 18). On Figa and 8C respectively hypothetical frequencies are below and above truly the frequency of 50 Hz;
therefore, in these cases, you can see that a strong peak at the location 18 of the index is no longer present (as shown by the reference numbers 81 and 83) and that any other peaks are not above the detection threshold. It may be noted that for simplicity of illustration, graphic depicted on Figa, 8B and 8C show only the indexes of the shift code 30, whereas when using a 1024-point fast Fourier transform (FFT) index actually would lie in the range from 0 to 1023.

The method is shown in figure 3, corresponds to the processing of a single block of data coherent way, which is a type of correlation, which is called in this document "coherent correlation". However, in practice, the coherent correlation may not lead to sufficient sensitivity to detect weak GPS signal and measuring the shift code. To improve the sensitivity can be detected and combined outputs of the correlation from multiple processes coherent correlation (i.e. correlation series), a procedure which is called "incoherent correlation" or "non-coherent processing," In particular, the processes of coherent integration on the above-mentioned steps 33-39 can be repeated for one or more additional adjacent intervals of time (usually in the range of 5-200 blocks), and then the results of the detection is given (for example, calculation of their value or the square of their size) and are merged.

This modification can be understood more precisely by using 11. 11 is a modification of Figure 3, in which the combination of multiple correlation series is to search the status of compliance. The numbering of the blocks shown figure 11, similar numbering is shown in figure 3, except for the addition of the front of the numeral "1". For example, the upper block "observation of energy in the band GPS", depicted on the two drawings, designated 30 and 130. 11 contains additional processing associated with the accumulation of postabargain multiple correlation series. Thus, the main addition is a loop (circuit) feedback from the output of block 147 to the input 138, which iterates with many blocks of data. At step 146 merges multiple correlation series.

When considering 11 we see that at the stage 133 we have selected the data corresponding to the set of blocks of length T_{c}compared to a separate block on the stage 33. Then at step 134 we perform a fast Fourier transform (FFT) of each of the individual data blocks. These data are typically stored in a buffer for later use. Stages 136a and 137 are similar to the stages 36a and 37. Then steps 138 and 139 use the reduce algorithm as part of the calculation to the relational series of samples of the reference frequency (corresponding to the satellite (SV) and the residual frequency) and sampling frequency of the given data block.
It is like the stages 38 and 39. However, at step 146 we combine the resulting correlation series like the previous data block. Typically, this Association is performed by the operation detection type values or square values of the correlation series, and then adding the result to like made in previous blocks. In some cases, the Association can be as simple as adding, or other coherent combining. Recent cases are relevant, if computational resources limit the ability to perform coherent processing on large data sets.

At step 147, the process branches off to the right to repeat the processing 138, 139 and 146 in the next data block, if all data blocks have been processed, then at this point, the processing flow goes to step 140. When the process moves to step 140, it has all the desirable combined correlation series to determine the status of compliance. The combined correlation series at the moment called "the final correlation series. The final correlation series is examined for a match condition, usually the peak is above the detection threshold, and the corresponding offset shift code is in a manner similar to explained for Figure 3.

In Viseu amanuta noted, the repetition of operations 138, 139 and 146 is performed on consecutive blocks of data, but a hypothetical satellite (SV), the sampling reference frequency and the residual frequencies are the same for each repetition. If at step 140 a match is not found, then at step 136b is selected, a new residual frequency (if the set has not been fully identified), and processing 138, 139, 146 starts again with the first data block (step 145 is reinitialized block number). After step 135 it is pre-computed by the fast Fourier transform (FFT) on all blocks of data, there is no more need to do direct fast Fourier transform (FFT), changing the following hypothetical residual frequency. Thus, the sampling frequency for each of the data blocks stored in the buffer and can be reused for each subsequent hypotheses residual frequency.

Once a match was found or after all of the residual frequency have been exhausted, the process moves to step 143, where if should be investigated more satellites (SV), it selects the next satellite (SV) and the initial frequency phase 136c, and then proceeds to step 133. In some cases, such as those where the sequence data is not present, it can alternatively go in this moment on this is paragraph 136a and reuse sampling frequency data from step 135, which have already been calculated through the foregoing operations, fast Fourier transform (FFT).

The following description is one explanation of the operation of one disclosed in this document.

First consider the way in which the operation is performed inverse fast Fourier transform (FFT). Originally selected time data can be represented as x(n): n=0, 1,2,..., which is a shorthand for the data samples x(0), x(T_{s}), x(2T_{s}),..., where T_{s}- sampling time period. Discrete Fourier transform ("DFT") of these selected data is designated as y(0,1,2,...). Discrete Fourier transform (DFT) of these data actually indicates the sampling frequency at frequencies 0, 1/(NT_{S}), 2/(NT_{s}),..., m/(NT_{s}),..., where m is the number of samples. Discrete Fourier transform (DFT) y(m) is defined for each m by:

The frequency of the discrete Fourier transform (DFT), the corresponding m>N/2, are actually negative frequencies, as by a circular symmetry frequency corresponding to the index m (i.e. the frequency m/(NT_{s})), is equivalent to one program corresponding to the index m-N (i.e. the frequency of the (m-N)/(NT_{s})). Now, for the purposes of this explanation, it is assumed: 1) that the period of the GPS frame corresponds to the R samples of the input data, (2) above is shown,
any satellite data has been removed, 3) the size N of the block corresponds To frames, i.e., N=KR, and (4) any Doppler effects on the modulation of the signal is negligible. These hypotheses allow the algorithm of the fast Fourier transform (FFT) to perform periodic convolution.

We are only interested in the detection of R samples of the filtering operation of compliance, since the matched filtering operation, in essence, is the cyclic convolution of the data signal with periodically recurring reference signal, as was previously pointed out. Therefore, the result of the matched filtering will also be periodic with period R. Under these circumstances, we can provide the output of the matched filtering through the operation on y(m) from equation (B1) in a known manner:

where g is the fast Fourier transform FFT of the reference signal GPS PN [selected at speeds similar to x(n)], repeated It again, the asterisk represents the complex conjugate of the number, and r is the time variable output, which is required only in the range [0, 1,..., R-l]. In equation (B2) we construct the hypothesis that the residual carrier frequency of the signal y(m) is equal to zero. As was indicated earlier, due to the fact that the sequence PN is the frequency of each frame, that is, every R samples, the functional g (m) C is achene, different from zero, each N/R=(KR/R)=sample (frequency). For example, if N corresponds to 20 HR{frames} GPS data, only every 20th sample FFT (starting with the first) is different from zero. Accordingly, the product within the summation of equation (B2) is different from zero only for every 20th sample, and hence we can write (B2) as:

The last summation is an R-point inverse discrete Fourier transform (DFT). Therefore, this shows that the inverse discrete Fourier transform (DFT) is required to perform the matched filtering operation using only the R-selective algorithm fast Fourier transform (FFT), which reduces the processing time and the required quantities and memory configuration. In addition, as long as you fulfilled the above conditions, requires only R-point inverse discrete Fourier transform (DFT), regardless of the number K of frames PN data is processed. It should be noted that equation (B3) is mathematically identical to that which would be obtained if the full N-point inverse fast Fourier transform (FFT) would be performed, as in equation (B2). It should also be noted that equation (B3) clearly shows a selection of every K-th point of the rapid transformation Fu is rd (FFT) to perform inverse fast Fourier transform (FFT).
It is the basis for the process of "reduction", that is, selection of a subset of points to perform inverse fast Fourier transform (FFT). Equation (B3) determines whether the hypothetical error residual carrier frequency is correct. However, this process only produces the display simply detect when the error residual carrier frequency is small compared to 1/T_{with}.

The above-mentioned equation (B3) corresponds to the processing of transformed data samples, assuming that the Doppler shift of the residual carrier is equal to zero. This produces a strong correlation peak only when the residual frequency is close to zero. To change this assumption Doppler frequency shift is assumed to be equal to d/(NT_{s}), where d is an integer, equation (B3) is changed as follows:

where []_{mod N}the value in brackets modulo N. In essence, we have the frequency shift of the input signal so that he was close to zero (i.e. much less than 1/T_{c}) residual frequency, suggesting that our hypothesis Doppler frequency shift is correct. Equation (B4) takes advantage of the cyclical nature of y. It should be noted that this modification is a simple frequency offset through the d spectral the s lines and directly by using the indexing sequence (cyclic way)
since d locations relative to the first element of y. This method addresses the limitations of the prior art discussed in the section "prior art", which is otherwise effectively limiting the search range, greater than approximately -500 to 500 Hz. The only limitation on the hypothesis of Doppler shift d frequency is implicit restriction concerning the length of the transient Doppler effects (i.e. the Doppler effect on the signal modulation). This limitation can be eliminated, as discussed below.

One suitable aspect of equation (B4) is that for processing other code GPS may not be a need to perform another direct conversion. In some circumstances corresponding to "g" code GPS (for example, corresponding to the Golden Code) can be replaced in the above, as previously converted data can continue to be used. This can be done, if the information about the satellite data (message) is present in more than one simultaneously adopted the GPS signal is substantially similar. This condition allows parallel erasing data on the simultaneously received signals. This is possible if the following two conditions: (A) differential ranges from the satellites are quite small (e.g. the measures within 300 km) and (B) information about the message is the same between the transmission of SV. Paragraph (B) often occurs, for example, when transmitting satellite almanac. In addition, the item may not be significant if the time coherent integration equal to less than 20 milliseconds. In GPS modes that do not contain data, for example, proposed for future execution, the condition (B) does not apply, and this modification can be more widely used.

In the previous explanation, it was implied that the effects of Doppler frequency shifts (including Doppler effect caused by the reference heterodyne receiver) mainly affect the carrier frequency. However, if the time NT_{S}coherent integration becomes large enough, it is impossible to ignore the Doppler effects after modulation signal (i.e. after the PN sequence P(t)). For the present purpose this Doppler modulation effect or the effect of Doppler shift time" first of all change the modulation speed, actually "expanding" or "squeezing" of the oscillating signal relative to the reference signal generated in the GPS receiver.

For example, for processing code C/A for the standard location service (civil service), the GPS attitude of the carrier frequency to the modulation rate of the element with the drove approximately 1575,42e6/1,023e6=1540.
Therefore, the Doppler frequency shift is approximately equal to 5000 Hz carrier, leads to a Doppler frequency shift is approximately equal to 5000/1540=3,25 Hz modulation. For coherent processing of relatively short blocks of data (e.g., 20 milliseconds) is the time of the Doppler frequency shift can be significant. But when processing long data blocks, the effect may degrade the sensitivity of the system by reducing the magnitude of the corresponding output of the peak filter. As an empirical rule, if the Doppler frequency shift modulation (including the effects of local oscillator (lo) is equal to p Hertz, and the total size N of the block corresponds to T_{c}seconds, without additional processing number pT_{c}must hold less than 1/2 to reduce the harmful effects.

Consider the above case in which the Doppler frequency shift of 10 000 Hz carrier leads to a Doppler frequency shift on 7,143 Hz modulation PN. If the size of the coherent unit is approximately equal to 100 milliseconds, then pT_{c}=0,7143, and will notice a deterioration in system performance. In addition, the output time of the peak of the matched filtering is replaced by pT_{c}/2 elements of the signal, relative to the case of zero Doppler frequency shift. Thus, it is clear that the big d is Amazon search of Doppler frequency shift and a great time coherent integration result in the loss of Doppler effects time,
if left uncorrected. In particular, this problem is amplified in two important situations:

(1) Large differences between the Doppler shifts the frequency of one signal of the GPS satellite to another, as observed by the GPS receiver. This item was already discussed above.

(2) the Effective Doppler frequency shift due to the frequency error of the GPS local oscillator relative to its ideal frequency.

With regard to item (2), the heterodyne GPS may differ from the ideal frequency GPS. For example, sometimes the GPS receiver can obtain the frequency of its local oscillator of the synchronized cell phone and, consequently, to achieve a low error rate. However, in some situations this is not possible. Even good thermally stabilized crystal oscillators can have errors in frequency to the GPS frequency (1575.42 MHz) of more than ±3000 Hz. Although such errors in frequency are not true Doppler shifts, they create shifts and the carrier and modulation in GPS receiver that is similar to the Doppler frequency shifts observed from a moving platform. Such errors in frequency are common to all GPS receivers and therefore affect all GPS signals that have been processed to some extent. However, these errors frequency can lead to poor performance, particularly for sizes long coherent the s blocks.

One way of coping with the above problem, is to re-sample sequence input by a speed commensurate with the hypothesis of the Doppler frequency shift of the GPS SV (satellite vehicle) and/or due to error of the local oscillator. By re-sampling the signal using digital signal processing, the input signal may in fact be stretched or compressed so that an integer number of frames PN GPS data again was within a block of coherent processing. Without such re-sampling the number of such personnel in the coherent block will no longer be an integer, but is estimated by the quantity that can be sized in a few samples, which can lead to serious degradation of the peak signal generated by the matched filtering operation.

However, re-sampling in the time domain may require to re-sample and completion of a direct fast Fourier transform (FFT) to the frequency domain and for this SV. Range, such as |pT_{c}| is less than about 1/2, as was indicated earlier. Unfortunately, this requirement perform many direct fast Fourier transform (FFT) can lead to an increase of the required system sizes and configurations of memory is to increase the time of processing.

However, the above-mentioned disadvantages are eliminated, and, in particular, the need to perform additional direct fast Fourier transform (FFT) can be eliminated by performing the functions of re-sampling in the frequency domain. In other words, the function of re-sampling can be performed on the transformed signal y, and not in the time domain. This approach avoids the need to perform additional direct fast Fourier transform (FFT); however, depending on implementation may need some extra storage.

The basic principle behind the re-sampling of the frequency domain can be explained from the ratio of the Fourier transform:

where x is the time of the oscillating signal, the Fourier transform x and a - shift scale or stretch. Thus, you can stretch in any field.

Stretching or compression include re-sampling the sampling frequency, a process that involves forms of partial re-sampling. From equation (B5), we see that if the sampling frequency is called y(m) and, thus, these samples are initially provided at frequencies m=[0, 1, 2,...]/(NT_{s}), these samples are replaced by samples, calculated at the frequencies of m/a; that is, by means of samples, calculated at frequencies m=[0, 1, 2,...]/(aNT_{s}
)-[0, 1/a, 2/a,...].

This last result is corrected only for positive frequencies, as we must ensure that sampling data are symmetric about 0 Hz. If we reorders the initial set in order: -N/2-1,N/2,..., -1,0,1,..., N/2-1, n/2, then re-selected set is reselected at frequencies of:

that is, if we use the original order, the set is reselected at frequencies of:

**m/a: for m=0, 1, 2, ..., N/2 (B7)**

**N+(m-N)/a: for m=N/2+l, N/2+2,.., N-l (B8)**

where we note the circular nature of the frequency due to the frequency index m is similar to m+N or m-n

Resampling equations (B6) and (B7) requires computing the frequency response at frequencies that are "between" normal discrete frequencies calculated by the discrete Fourier transform (DFT). But it is relatively easy to do, for example, interpolator "sinc". Since the input data is limited in time, we can compute the (complex) frequency response at a frequency of**□**|**□**| <0.5 Hz, relative to the number of spectral lines, through the process of convolution. For example, to calculate the spectral characteristics at the frequency of y(m_{0}+**□**), where m_{0}- integer, we form the result:

where m ranges over all in zmeinym values (i.e. m-N/2+1 to m+N/2).

The simple approach to this computation requires only two or three values of m. Assessment of losses due to the binomial calculation equation (B9) indicates that this loss in sensitivity does not exceed 1 dB, if**□**is in the range from-0.5 to 0.5 Hz. For most interest Doppler shifts of the modulation frequency stretching, defined by equation (B5)can be regarded as constant for a relatively large number of sequential sampling frequency. Therefore, the interpolation equation (B9) can use the same values for the weighting coefficients of the sinc to determine a large number of consecutive re-selected spectral values.

Thus, the above-described method of re-sampling allows the use of the algorithm in which the data of the frequency divided into a series of smaller blocks, for example, the size of each block is 1024, and each block is reselected using the procedure of interpolation with a fixed set of coefficients. Before processing block coefficients or calculated or found in the table. This procedure can significantly reduce the burden of processing for the subsequent sampling. For example, when using the procedure of two-point interpolation, similar to equation (B9), the procedure is repeated Vyborg which requires only four steps of multiplication and two additions for the calculation of each interpolated values (ignoring the above search in the table). This method can be compared with, for example, eight "butterflies" on the sample data necessary for calculating the fast Fourier transform (FFT) block size is 64 KB. These "butterflies" require 32 multiplication and 48 action addition, the calculation is increased by the value approximately equal to 16, relative to the interpolation in the frequency domain. Therefore, resampling the frequency domain is believed to be much more practical and efficient than re-sampling the time domain.

Resampling is used to compensate for Doppler frequency shift modulation at any processing large ranges of Doppler shifts in the frequency and/or processing of signals from different satellites (SV). In such cases, it may be used the same set of transformed using the Fourier transform of the data, and therefore do not have to deal with the initial time data. As was indicated earlier, however, the processing of different SV with a similar set of transformed using the Fourier transform of the data may be limited to situations in which the satellite data messages are similar to allow its removal to the initial coherent processing. In any case, it is used to store the initial set of transformed using the preobrazovaniya Fourier data even after performing the operation, re-sampling, when required secondary and additional re-sampling. If the initial set is transformed using a Fourier transform of the data is not available, you must re-sampling, re-set, an approach that could lead to cumulative errors, if accurate re-sampling should not be performed.

The reduction operation is defined as a subset of the data frequency of the direct fast Fourier transform (FFT) because of the sparsity of the spectrum associated with repeated signal PN, that is, the shape of the line comb structure. When required spectral interpolation, as discussed above, we create instead of simply selecting the subset by interpolation between the sampling frequency. However, the size of the thus created subsets of similar occasion, which made a simple choice. Thus, it is typically equal to the number of samples of the signal at each frame PN. For example, in the previous examples it was equal to 1024 or 2048 samples, corresponding to velocities of samples equal to 1,024 or 2,048 MHz. The dimensions of inverse fast Fourier transform (FFT) respectively are the two sizes. Therefore, the definition of "reduction" refers to the formation of a subset of samples frequency through the interpolation procedure, as well as the direct selection of the subset is of Borok frequency.

This method can be used in the interpolation, when she wants to change the serial hypothesis frequency through increases that are smaller than the interval between the lines of the fast Fourier transform (FFT); for example, it may be desirable to increase the half-spacing between lines. In addition, the determination of the reduction applies to the formation of a subset of samples frequency through the procedure of interpolation, in which the hypothesis of frequency is changed by a part of the interval between the lines of the fast Fourier transform (FFT).

Specialists in this field of technology will be assessed in view of this idea, the alternative implementation that can be easily implemented.

For example, in the preceding discussion, as illustrated, for example, by Figure 2 or Figure 3, there is an operation of shifting the initial frequency to shift the frequency of the signal to a frequency close to zero. This can be done with conventional local oscillators and frequency converters, in a way known in the prior art. Also this can be done by filtering the incoming RF energy near the band GPS, and then direct select this filtered power for speed commensurate with the bandwidth of the filter. It is widely known that this approach can privest the effective frequency offset.
Therefore, the terminology "frequency offset" refers to those methods of direct RF sampling, as well as to the usual methods of frequency offset. In addition, although figure 3 assumes that the carrier frequency is removed before conversion to digital form, leaving a residual frequency f_{e}often only removes a large part of the carrier frequency and the signal frequency is shifted to a low IF frequency, say f_{IF}+f_{e}before digitization. After the operation of digitizing the IF frequency f_{IF}typically substantially removed by means of digital signal processing. Then the result follows, as shown in step 33, is shown in figure 3. Such changes initial pre-processing of the signal should be obvious to experts in the given field of technology.

1. A method of processing a signal that was transmitted at predetermined carrier frequency from one of the many transmitters and includes an oscillatory signal, modulated according to the pseudonoise (PN) sequence, which identifies the said transmitter, comprising stages, which are:

take electromagnetic signal within the mentioned carrier frequency and referred to digitize the signal for a predefined period of time;

put forward the hypothesis that the signal is associated with one of upomanouther.html and with its carrier frequency;

provide a set of samples of the reference frequency corresponding to the aforementioned hypothetical signal;

suggest first residual frequency mentioned hypothetical signal;

choose from the mentioned self-energy of the first subset of data of length equal to at least two repetitions mentioned repeating sequence PN;

calculate the first set of samples of frequency data using the aforementioned first subset of data;

reduce the aforementioned first set of samples of frequency data using the aforementioned hypothetical first residual frequency to produce a first subset of the above-mentioned sampling frequency data;

calculate the final correlation series using as input at least the correlation of a series of the above-mentioned first subset of samples of frequency data and the above-mentioned sampling reference frequency to produce an indication of whether there is a match condition between the said transmitted signal and the above-mentioned hypothetical signal.

2. The method according to claim 1, further comprising stages, which are selected from the aforementioned digital signal to a second subset of the data length at least equal to two repetitions of said sequence PN;

calculate a second set of samples of frequency data, use what I mentioned a second subset of data;

reduce the aforementioned second set of samples of frequency data dependent mentioned hypothetical first residual frequency, to provide a subset of this second set of samples of frequency data;

moreover, the above-mentioned step of calculating includes calculating the final correlation series using as input at least mentioned correlation series calculated from the above-mentioned first subset of samples of frequency data and the above-mentioned samples of the reference frequency, the correlation series calculated from the above-mentioned second subset of samples of frequency data, and the above-mentioned samples of the reference frequency to produce said indication of whether there is a match condition between the said transmitted signal and the above-mentioned hypothetical signal.

3. The method according to claim 2, in which the said step of calculating includes, at least, the stage at which detect and combine the aforementioned first and said second correlation series.

4. The method according to claim 1 in which the said step of reducing further comprises the step on which you choose from the mentioned first subset of samples of frequency data set of samples containing the indices spaced intervals relative to each other by an integer K, and K represents the number of members is of telestai PN in the above-mentioned first data set, each of the sampling frequency of the data are identified with an integer.

5. The method according to claim 1 in which the said subset contains many samples of frequency data, separated by intervals determined by the repetition rate of said PN sequence.

6. The method according to claim 1 in which the said reduction stage includes a stage on which interpolate between the first-mentioned set of samples of frequency data.

7. The method according to claim 1 in which the said stage of the sampling reference frequency includes a stage on which to perform the discrete Fourier transform (DFT) to the PN sequence.

8. The method according to claim 1 in which the said step of calculating includes a step in which the aforementioned first subset of the above-mentioned sampling frequency of the data is multiplied by the set of samples of the reference frequency to generate a set of weighted samples frequency.

9. The method of claim 8 in which the said step of calculating includes a stage on which to perform the inverse discrete Fourier transform (DFT) on the above-mentioned set of weighted sampling frequency to produce first mentioned correlation series.

10. The method according to claim 1 in which the said multiple transmitters contain multiple GPS satellites that transmit GPS signals at predetermined essay frequency, each GPS satellite transmits a unique PN sequence.

11. The method according to claim 1, in which the searches mentioned final correlation series to identify the presence of the GPS signal, and if the presence of the GPS signal is identified, then determine the offset of the PN code, and determine the time of arrival of the GPS signal in the above-mentioned receiver.

12. The method according to claim 1 additionally containing phases in which:

suggest second residual frequency;

reduce the aforementioned first set of samples of frequency data based on the aforementioned hypothetical second residual frequency to provide a third subset of samples of frequency data;

calculate a third correlation series of the above-mentioned third subset of samples of frequency data and the above-mentioned sampling frequency reference;

calculate the second end of the correlation series containing at least mentioned the third correlation series;

check the second end of the correlation series to determine whether a match condition between the said transmitted signal and the above-mentioned hypothetical signal.

13. The method according to item 12, in which the said data block has a size within a range from 5 to 20 repetitions of said PN sequence.

14. The method according to claim 11, further containing this is, by using time of arrival information to determine the location of the mentioned receiver.

15. The method of signal processing, which has been transmitted from one of the many transmitters and containing an oscillatory signal, modulated by the repetition of a PN sequence containing phases in which:

put forward the hypothesis that the signal is associated with one of these transmitters and with its carrier frequency;

extract a subset of data of length at least equal to two repetitions of the above-mentioned repetition of the sequence PN of the electromagnetic signal received within the carrier frequency of the above-mentioned signal to be processed;

reduce the set of samples of frequency data calculated from the above-mentioned subset of data, in response to the aforementioned hypothetical carrier frequency to generate a subset of the above-mentioned sampling frequency data; and

calculate the final correlation series using as input at least the correlation series, some of the mentioned subset of samples of frequency data, and samples reference frequency corresponding to the aforementioned hypothetical signal;

examine mentioned the final correlation series to determine whether there is a match condition between the said transmitted signal and manuchim hypothetical signal.

16. A mobile station that includes a location system, which receives the signal transmitted at the predetermined carrier frequency from one of the many transmitters, referred transmitted signal includes periodically repeating sequence that uniquely identifies the transmitter that sent the signal, the specified mobile station includes:

tool to monitor and digitize the electromagnetic signal at a predetermined carrier frequency for a predefined time interval,

means for proposing hypotheses about one of the above-mentioned multiple transmitters and provide a set of samples of the reference frequency corresponding to the hypothetical signal transmitted from the aforementioned hypothetical transmitter;

means for proposing hypotheses about the residual frequency;

means for selecting the first part mentioned digitized electromagnetic signal length at least equal to two repetitions mentioned recurring sequences, thereby determining the data block;

means, which in response to the above-mentioned data block, and calculates the number of samples of frequency data;

the means for reducing the above-mentioned sampling frequency data in response to the aforementioned hypothetical residual frequency to ensure uridicheski posted subset of the above-mentioned sampling frequency data;

means for calculating a first correlation of a series of the above-mentioned subset of the above-mentioned sampling frequency data and the above-mentioned sampling frequency reference;

means for calculating the final correlation series containing at least mentioned first correlation series; and

the means for finding mentioned final correlation series to identify whether the compliance status of the signal between these hypothetical signal and said received signal, and if the state match was found between these hypothetical signal and said received signal, determine timing information.

17. Mobile station according to clause 16, which mentions periodically spaced subset contains many samples that have been posted indexes relative to each other by an integer K, and K is the number of repetitions mentioned periodically repeating sequence in said first set of data in which each of the sampling frequency of the data are identified with an integer.

18. Mobile station according to clause 16, which mentions periodically spaced subset contains many samples, with adjacent samples that are spaced from each other in Hertz at intervals determined by the speed of p is torenia mentioned periodically repeating sequence.

19. Mobile station according to clause 16, in which the said means of reducing includes means for interpolating between the samples of frequency data.

20. Mobile station according to clause 16, in which said mobile station includes a memory for saving the above-mentioned sampling frequency reference.

21. Mobile station according to clause 16, in which the said means for calculating the final correlation series includes means for incoherent associations mentioned first correlation series with the second correlation sequence calculated from the second part referred to the digitized electromagnetic signal, different from the first mentioned part.

22. Mobile station according to clause 16, in which the said step of calculating the first correlation series includes means for multiplying mentioned first subset of the above-mentioned sampling frequency data with the mentioned set of samples of the reference frequency to generate a set of weighted samples of the frequency and the means for performing inverse discrete Fourier transform (DFT) on the above-mentioned set of weighted samples frequency for forming the aforementioned first correlation series.

23. Mobile station according to clause 16, which mentions many transmitters contain multiple GPS satellites that transmit GPS signals at predetermined chosen to replace the first frequency, each GPS satellite transmits a unique recurrent sequence.

24. Mobile station according to clause 16, in which the said data block has a size that corresponds to an integer number of repetitions mentioned recurring sequences.

25. The method according to item 16, further containing a system of GPS location for use of the aforementioned information synchronization for determining the location of said mobile station.

**Same patents:**

FIELD: radar-location.

SUBSTANCE: invention relates to methods and a device for establishing location of a receiver using GPS signals. The invention employs signals of GPS transmitters, which comprise a unique periodically recurring pseudonoise (PN) sequence. The invention is especially useful in non-synchronised systems, for example A-GPS, used in GSM and UMTS systems for mobile telephones. A received signal is stored in a receiver for at least two repetition periods of the PN sequence. A fast Fourier transformation operation is done (FFT), and frequency samples of data are obtained, which are curtailed in response to a hypothetical residual frequency. This cuts the number of the next required calculations and processing time. Correlation series are determined from the curtailed samples and reference frequency samples of the corresponding hypothetical transmission. If conformity is detected, the displacement of code shift is determined. Otherwise the process is repeated with another hypothetical residual frequency. Several similar obtained correlation series can be joined incoherently.

EFFECT: device and method of detecting GPS signals.

25 cl, 13 dwg

FIELD: physics, measurement.

SUBSTANCE: invention is related to the field of passive radio location and is intended for performance of full-scale tests of pilot samples of passive range-difference system (RDS) in case of absence of one of receiving posts. Substance of suggested method consists in the fact that mutual-correlation measurement of RRS signals time delays received by master and slave receiving posts, and missing slave receiving post is additionally imitated by definition of its location coordinates, which is symmetrical to location of slave receiving post relative to the line "master receiving post - RRS", and as RRS signal received by imitated slave receiving post, signal is used from existing slave receiving post, and then RRS location is defined by full-scale test method.

EFFECT: provides for possibility to evaluate accuracy in detection of radio-wave radiation source (RRS) location by passive RDS in case of one receiving posts in not available in its composition.

2 dwg

FIELD: radio engineering.

SUBSTANCE: measuring base implements the removal of signal amplitudes proportional to the field intensity, as per which the main lobe of antenna beam of radiation sources is restored in linear measure. Determination of the distance to radiation sources is achieved by means of calculation of the ratio of calculated width of radiation source antenna beam in linear units to the width value of antenna beam, which is taken from database, in angular radian measure.

EFFECT: possibility of passive determination of the distance to radiation sources with directional antenna oriented with its main lobe to direction finder antenna; the latter forms together with antennae of additional receiving stations the measuring base the size of which is much smaller than that during implementation of the known time-difference direction determining method, which in its turn allows eliminating communication channels for transfer of received signals to distance calculation station, and as a whole, applying the method on movable direction finder carrying object.

5 dwg

FIELD: radio engineering, communication.

SUBSTANCE: method and system for determining the position of a signal transmitter from the signal arrival time employ separate processing of a signal received by multiple antennae and receiving channels, waiting for characteristic points of the received signal, measuring the time of arrival of characteristic points of the received signal, summation with accumulation to determine the average arithmetic of measured values of the time of arrival of characteristic points of the received signal and calculating the position of the signal transmitter using the average arithmetic of the measured values of the time of arrival of the characteristic points of the received signal as the time of arrival of the signal.

EFFECT: high accuracy and longer range for determining position of a signal transmitter.

3 cl, 4 dwg

FIELD: radio engineering, communication.

SUBSTANCE: system includes receiving stations (4) for receiving signals transmitted from the spacecraft (6) and a processing station (2) for receiving data from the receiving stations (4), where each receiving station (4) records, during a recording window (8), signals transmitted from the spacecraft (6) and transmits, to the processing station (2), data representing the recorded signals. The recording windows (8) associated with each of the receiving stations (4) are offset and/or have different size with respect to each other. The processing station (2) correlates the recorded signals to estimate the distance difference between the spacecraft (6) and each of a plurality of receiving stations and to estimate the spacecraft (6) position.

EFFECT: avoiding the need to send a reference signal pattern, emission by the spacecraft of any trigger sequence and the need to adapt the spacecraft, and improved estimation of the position of the spacecraft.

22 cl, 10 dwg, 1 tbl

FIELD: radio engineering, communication.

SUBSTANCE: invention presents a method, a device and computer program product for clocking using the relative behaviour of clocks of individual receiving stations as well as corresponding modelling to derive a time difference of arrival of a signal from a user device which can be used to correct the time difference of arrival based on the modelled clock behaviour and leads to a correct clocking of received user signals, which is applicable to a plurality of pairs of receiving stations and transmitted beacon signals and allows to correct location estimation of a user device.

EFFECT: enabling estimation of the location of a mobile device without the need to synchronise clocks at different receiving stations.

15 cl, 6 dwg

FIELD: radio engineering, communication.

SUBSTANCE: electronic surveillance system calculates estimates _{in,i}(k), obtained at the k-th moment in time, are identified with the corresponding radio-frequency sources, wherein for each status coordinate of each detected and tracked radio-frequency source, the method includes determining an interval of values which depends on variance of measurement of X_{in,i}(k), the variance of the rate of measuring status coordinates _{in}(k) at the k-th moment in time falls in said gate, the result is identified with, for example, a specific radio-frequency source. If the measured vector X_{in}(k) does not fall within any of the gates of the j-th radio-frequency source, where

EFFECT: high reliability of identifying signals in a multi-target environment.

2 dwg

FIELD: radio engineering and communications.

SUBSTANCE: invention relates to radio engineering and can be used in radio monitoring systems when solving the problem of determining coordinates of objects concealed-carriers of radio-frequency sources.

EFFECT: technical result is possibility of determining distance to radiation source, mainly stations VHF range of operating outside the horizon, antenna which can be omnidirectional or highly-directional, scanning or fixed.

1 cl, 2 dwg, 1 tbl

FIELD: wireless communications.

SUBSTANCE: invention relates to navigation and radar systems and can be used to create non-emitting receiver multiposition radar system, using navigation signals of space navigation system for air target illumination purposes. Nature of invention is that when a weak scattered navigation signal is received a powerful feedforward navigation signal is compensated, which in this case plays a role of a structurally determined interference. To this end when receiving an input as a mixture of high-power direct navigation signal, weak navigation signal diffused in the air, and intrinsic noise of the receiver the first procedure is detection of the powerful direct signal, accurate determination of its parameters, the whole input is stored in memory. Further, an exact copy of the direct signal is formed and subtracted from the recorded input implementation. Result contains only the intrinsic noise of the receiver and the weak scattered signal which is detected in a conventional manner. Impact of the main lobe of the correlation function of a not fully compensated direct propagation of the navigation signal is excluded by limiting the range of possible values of the delay in finding the weak scattered signal, as based on the geometry of the spread of direct and indirect signals, the delay of the scattered signal is always greater than that of the direct signal.

EFFECT: achievable technical result is an increase in the probability of correct detection of the navigation signal scattered by the air target.

2 cl, 1 dwg

FIELD: radio electronics.

SUBSTANCE: invention relates to radio electronics and can be used when determining locations of pulse emitters. Technical result is reduction of dimensions of the device while maintaining accuracy of determining range to a pulsed radiation source and the direction to it. Mentioned result is achieved due to that the detection device comprises three widely directed in azimuth antennae, three receivers, two variable delay lines, two units for determining a small time interval, a computer, a unit of two sensors of the reference distance, a secondary processing unit, an indicator.

EFFECT: listed devices are interconnected in a certain manner.

1 cl, 1 dwg