Citation
Adaptive filtering techniques to enhance GPS signal receivability

Material Information

Title:
Adaptive filtering techniques to enhance GPS signal receivability
Creator:
Muckerheide, Kevin M
Place of Publication:
Denver, Colo.
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
180 leaves : ; 28 cm

Thesis/Dissertation Information

Degree:
Master's ( Master of Science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Electrical Engineering, CU Denver
Degree Disciplines:
Electrical Engineering
Committee Chair:
Bose, Tamal
Committee Members:
Sen, Pankaj K.
Bialasiewicz, Jan T.

Subjects

Subjects / Keywords:
Global Positioning System ( lcsh )
Signal processing ( lcsh )
Global Positioning System ( fast )
Signal processing ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 177-180).
General Note:
Department of Electrical Engineering
Statement of Responsibility:
by Kevin M. Muckerheide.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
40336954 ( OCLC )
ocm40336954
Classification:
LD1190.E54 1998m .M83 ( lcc )

Full Text
ADAPTIVE FILTERING TECHNIQUES TO
ENHANCE GPS SIGNAL RECEIVABILITY
by
Kevin M. Muckerheide
B.S., Rose-Hulman Institute of Technology, 1989
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
1998


This thesis for the Master of Science
degree by
Kevin M. Muckerheide
has been approved
by
Tamal Bose
Jan T. Bialasiewicz
3)Mzr$8
Date


Muckerheide, Kevin M. (M.S., Electrical Engineering)
Adaptive Filtering Techniques to Enhance GPS Signal Receivability
Thesis directed by Associate Professor Tamal Bose
ABSTRACT
The Global Positioning System (GPS) of satellites and receivers has
revolutionized the fields of navigation, surveying, and time relay. Knowledge
about one's position in space and time is quickly and cheaply available at
accuracies once only attainable at considerable expense and time.
Unfortunately, the signals transmitted by the GPS satellites share their
portion of the frequency spectrum with terrestrial line-of-sight
communications, requiring a limit to the power at which they are transmitted
to avoid interference. The developers of GPS designed the system with
several techniques, including direct sequence spread spectrum, to meet the
conflicting constraints of transmitting signals that were easily processable in
relatively low-noise environments, yet low powered enough to avoid
interference with the ground-based communication systems.
Designing to this middle ground did not leave much room for
processing signals in a dense radio-frequency (RF) environment.
Unintentional interference can become a problem by itself, and deliberate
jamming is a very real concern for military users and even civilian users
operating in areas prone to terrorist activity.


This thesis explores the utility of adaptive signal processing
techniques to enhance the receivability of GPS signals in high noise
environments, to include broadband noise, multipath, and intentional
spoofing. This requires reasonable simulations of both a clean GPS signal
environment and a GPS receiver. Various types of noise are then introduced
into the environment, and the output of a theoretical GPS receiver is
compared to that of one with the benefit of adaptive signal processing.
This abstract accurately represents the content of the candidate's
thesis. I recommend its publication.
Signed
Tamal Bose


ACKNOWLEDGMENTS
This study would not have been possible without the support of many people
to whom I will always be grateful.
I wish to express my gratitude to Professor Miloje S. Radenkovic for his early
support and guidance during the preparation of this thesis and to Professor
Tamal Bose for picking up the task and guiding me through its completion
when Professor Radenkovic departed on sabbatical. I would also like to
thank Professor Jan T. Bialasiewicz and Professor P. K. Sen for serving on
my committee.
Finally, this thesis is dedicated to my wife, Janet, and my children, Nathan
and Amanda, for putting up with a part-time husband and father much more
often than they should have.


CONTENTS
Chapter
1. Introduction ................................................... 1
1.1 Statement of the Problem ....................................... 1
1.2 Summary of Findings ......................................... 6
1.3 Thesis Outline ................................................ 8
1.4 Notation and Terminology ...................................... 9
2. GPS Signal Environment ....................................... 12
2.1 An Individual GPS Signal ..................................... 12
2.1.1 Signal Modulation ........................................... 12
2.1.2 Basics of Direct Sequence Spread Spectrum .................. 16
2.1.3 Gold Codes ................................................. 19
2.2 Nominal Signal Environment .................................. 25
2.2.1 Microwave Communications .................................... 25
2.2.2 GPS Multiple Access Signals ................................ 28
2.3 Simplifications to the GPS Signal Environment ............... 30
2.3.1 Simplifications for the Ease of Processing ................. 31
2.3.2 Irrelevant Characteristics .................................. 33
2.4 GPS Signal Simulations ....................................... 35
2.4.1 Gold Code Generation ........................................ 35
2.4.2 L, and Multiple Access Noise Generation .................... 36
3. Description of Current GPS Receivers ......................... 45
3.1 Prototype Receiver Description ................................ 45
VI


3.2 GPS Receiver Simulation ...................................... 49
4. Non-Standard Interference ..................................... 66
4.1 Narrowband Noise .............................................. 66
4.1.1 Description ................................................. 67
4.1.2 Method of Insertion ......................................... 67
4.2 Wideband Noise .............................................. 70
4.3 Multipath and Spoofing ....................................... 70
4.3.1 Rationale for Generalization ................................ 70
4.3.2 Description ................................................. 72
4.3.3 Method of Insertion ......................................... 76
5. Review of Adaptive Signal Processing Theory ................. 78
5.1 Using Gradients to Minimize an Unknown Cost Function ........ 79
5.2 Adaptive Noise Cancellation Cost Functions and Algorithms .. 82
5.3 Time Delay Estimation Cost Functions and Algorithms ........ 88
5.4 Examples of Typical Adaptive Signal Processing Output ...... 90
5.4.1 Time Delay Estimation Examples ............................ 90
5.4.2 Noise Cancellation Examples ............................... 94
6. GPS Application of Adaptive Signal Processing ............... 99
6.1 Modifications to the Traditional Adaptive Signal
Processing Scheme ............................................. 99
6.2 Modified GPS Receiver Simulation ........................... 103
7. Results and Conclusions ...................................... 107
7.1 A Clean Environment .......................................... 107
7.2 Multiple Access Noise ....................................... 114
VII


7.3 Thermal and Wideband Noise ............................... 119
7.4 Narrowband Noise ......................................... 130
7.4.1 Tone on the Carrier ..................................... 130
7.4.2 Tone 1.023 MHz Away from the Carrier ................... 136
7.4.3 BPSK Signal Centered on the Carrier .................... 142
7.5 Multipath and Spoofing .................................... 148
7.5.1 Multipath Results with Weak Reflections and no Other Noise 149
7.5.2 Multipath Results with Strong Reflections and
Wideband Noise ........................................... 153
7.6 Conclusions .............................................. 158
Appendix
A. MATLAB Programs ............................................ 160
B. Derivation of White Noise Maximum Values ................... 175
References .................................................... 177
viii


FIGURES
Figure
1.1 Plan of Investigation ......................................... 6
2.1 Baseband Spectra for Data Signal and both C/A and P Codes ... 14
2.2 Circuit Creating L,(t) and L2(t) ............................. 15
2.3 L| Signal at RF .............................................. 18
2.4 Circuit for Producing C/A Gold Codes ......................... 21
2.5 Typical Autocorrelation Results Against PRN Sequences ........ 23
2.6 Typical Cross-correlation Results Against PRN Sequences ...... 24
2.7 Flowchart for the Creation of L-, and Multiple Access Noise .. 37
2.8 Sampled PRN Code from GPS Satellite #1 .......................... 39
2.9 Spectrum of the C/A Code from GPS Satellite #1 .................. 40
2.10 Spectrum of the C/A Code from DC to 100 kHz .................... 41
2.11 C/A Code Spectrum Illustrating 1 kHz Lines ..................... 43
2.12 Spectrum of the Simulated L1 Signal at the Receiver ............ 44
3.1 Block Diagram of a Generic GPS Receiver ....................... 46
3.2 Typical Downconversion Stage ................................. 48
3.3 Flow Chart for the GPS Receiver Simulator ....................... 51
3.4 PSD of the L^ Signal and Thermal Receiver Noise ................. 53
3.5 Pole-Zero Plots for Downconversion Filters ................... 54
3.6 Pre- and Post-Filtering of a Noise-free GPS Signal ........... 55
3.7 Noise-free Baseband Signal After Post-Filtering .............. 56
3.8 Baseband Signals with Noise After Post-Filtering ................ 58
3.9 Cross-correlator Outputs with Varying Levels of Noise ........... 61
IX


3.10 Output of the Despreader .................................. 64
4.1 Narrowband BPSK Signal in Time Domain ......................... 68
4.2 Spectral representation of the Interfering BPSK Signal ....... 69
4.3 Geometry for Multipath and Spoofing Interference ............. 73
4.4 Spacecraft Geometry Relative to Receiver on Earth's Surface .... 74
4.5 Multipath Response ........................................... 76
5.1 Iterative Search for the Minimum of a Cost Function ........... 80
5.2 Minimum Search Results ....................................... 81
5.3 Typical Adaptive Noise Cancellation Problem .................. 82
5.4 Typical Time Delay Estimation Problem ........................ 89
5.5 Time Delay Estimation Using LMS .............................. 91
5.6 Time Delay Estimation Using NG ............................... 92
5.7 Time Delay Estimation Using RLS .............................. 93
5.8 Adaptive Noise Cancellation Using NG - Noise PSD = 1.0 ...... 95
5.9 Adaptive Noise Cancellation Using NG Noise PSD = 10 ....... 97
5.10 Adaptive Noise Cancellation Using NG -- Noise PSD = 100 ... 98
6.1 Proposed Adaptive Signal Processor Block for GPS Receiver ... 100
6.2 GPS Receiver Incorporating Adaptive Signal Processor ........ 103
6.3 Flow Chart for the Adaptive GPS Receiver Simulator .. 104
7.1 GPS Baseband Signal with No Noise ............................ 108
7.2 Identifying the PRN Sequence Starting Point ................. 110
7.3 Four of the 1023 Adaptive Filter Parameters ................. 112
7.4 Despreader Output for Both Receivers ........................ 113
7.5 Baseband Signal with Multiple Access Noise .................. 115
x


7.6 Identifying the PRN Sequence Starting Point with MA Noise ..... 116
7.7 Adaptive Filter Parameters with Multiple Access Noise ......... 117
7.8 Depsreader Output with Multiple Access Noise .................. 118
7.9 GPS Baseband Signal with Wideband Noise ....................... 121
7.10 Identifying the PRN Sequence Starting Point with
Wideband Noise ................................................. 122
7.11 Four of the 1023 Adaptive Filter Parameters in
Wideband Noise ................................................. 123
7.12 Despreader Output for Both Receivers in Wideband Noise 124
7.13 GPS Baseband Signal with Wideband Noise ......................... 125
7.14 Identifying the PRN Sequence Starting Point with
Wideband Noise ................................................. 127
7.15 Four of the 1023 Adaptive Filter Parameters in
Wideband Noise ................................................. 128
7.16 Despreader Output for Both Receivers in Wideband Noise 129
7.17 Spectrum of a Pure Tone on the GPS Carrier ...................... 131
7.18 Pure Tone Down-Converted to DC Component ........................ 132
7.19 Correlator and Filter Outputs with a Pure Tone on the Carrier .. 133
7.20 History of Filter Parameters with a Pure Tone on the Carrier .... 134
7.21 Despreader Output with a Pure Tone on the Carrier .. 135
7.22 Spectrum of a Pure Tone Above the GPS Carrier ................... 136
7.23 Pure Tone Down-Converted to C/A Chip Frequency .... 137
7.24 Correlator and Filter Outputs with a Pure Tone Above
the Carrier .................................................... 139
XI


7.25 History of Filter Parameters with a Pure Tone Above
the Carrier ................................................ 140
7.26 Despreader Output with a Pure Tone Above the Carrier ........ 141
7.27 Spectrum of a BPSK Signal on the GPS Carrier ................ 142
7.26 BPSK Signal's Effect on GPS Baseband ......................... 143
7.29 Correlator and Filter Outputs with a BPSK Signal on
the Carrier ................................................. 144
7.30 History of Filter Parameters with a BPSK Signal on
the Carrier ................................................. 146
7.31 Despreader Output with a BPSK Signal on the Carrier ......... 147
7.32 Cross-Correlation Results of Multiple-Return Multipath ...... 150
7.33 Adaptive Filter Parameter Results of Multiple-Return Multipath 151
7.34 Despreader Output with Multiple-Return Multipath ............ 154
7.35 Cross-Correlation Results of Single-Return Multipath/Spoofing 155
7.36 Adaptive Filter Results of Single-Return Multipath/Spoofing 156
7.37 Despreader Output with Single-Return Multipath/Spoofing ..... 157
xii


TABLES
Table
2.1 Probability of Cross-Correlation Levels ................... 20
2.2 Shift Register Tap Points and Resulting gold Code Values .. 22
7.1 Success Rate for Wideband Noise Trials .................... 120
xiii


1. Introduction
1.1 Statement of the Problem
The Global Positioning System (GPS) was originally conceived and
developed in the 1970's as a means to provide US military users with a quick,
easy, reliable, and highly accurate source of locational information.
However, since reaching Initial Operational Capability (IOC), it has become
the ultimate dual-use technology, with overall civilian use of GPS estimated
to be nearly ten times that of the military's [1], Civilian ships depend on the
system for precision approaches to harbors in bad weather and dense fog,
and railroads and trucking companies use it to track freight as it traverses the
complex transcontinental shipping network. Both airlines and private pilots
have integrated the system to enhance their inertial navigation and landing
systems, surveyors are becoming increasingly dependent on it, and it has
even found use in the scientific and other communities to measure and
record extremely precise timing relationships. Of course, the military also
requires GPS to navigate otherwise featureless terrain, sea, and air
corridors. In addition, it is also integrating GPS receivers into the control
mechanisms of eight different types of precision guided munitions (PGMs)
[2]. Between the civilian and military users, GPS is quickly becoming a
system requiring 100% availability, to include operating in environments with
intentional or unintentional interference.
1


The GPS consists of three subsystems: the control segment, the
space vehicle segment, and the user segment. The US Air Force has
responsibility for the telemetry, tracking, and control (TT&C) functions that
make up the control segment. The master control facility is at Falcon Air
Force Base outside Colorado Springs, CO, but there are remote uplink
stations located around the world. The space vehicle segment is composed
of 24 operational and reserve GPS satellites circling the earth in semi-
synchronous (12-hour) orbits. There are six planes of four satellites each,
resulting in 24-hour visibility of at least four satellites from every point on the
earth. Each satellite transmits its position and a very accurate time hack
using its unique signature signal. The user segment is the myriad of GPS
users and their receivers that receive those signals and triangulate their own
position in space and time based on the received signals. This thesis is
primarily concerned with the receiver segment and the signals from the
satellites, and is peripherally concerned with the space vehicle segment
itself.
The premise behind GPS is that users need to know where they are in
three-dimensional space. Although all three measurements are initially
unknown, one can triangulate from three known positions (those of three
satellites) to solve for the three unknowns. The satellites know very precisely
where they are at a given instant in time, and they transmit that information to
the users. However, several factors require the precise time at the receiver
to also be considered an unknown. These include the satellites rapidly
changing position in their orbits, the varying time delays between when a
2


signal is transmitted and when the receiver receives it, and the fact that the
receiver's clock is not as accurate as that on the spacecraft. The resulting
system of equations becomes
o xj- + (y y^2 + (z-Z1)2 = (r, cedock)2
(x-x2f +(y-y2f +(z~Z2f = (r2 -cectockf
(x x3f + (y y3f + (z z3)2 = (r3 cecloekf
(x-xA)2 + 0 y4)2 + (z z4)2 = (r4 cechck f
where (x, y, z) are the unknown positions of the receiver, ecjock is the
unknown error in the receiver clock, (Xj, yj( Zj) are the locations of the
satellites, Tj is the "pseudorange" to a given satellite as computed based on
the receiver's clock, and c is the speed of light. The positions of the satellites
are obtained by successfully receiving and decoding the data streams in the
satellite signals. Determining the clock error also depends on knowing,
relative to the receiver clock, precisely when a signal reaches the receiver.
These two tasks, accurately determining bit values and when the data
reaches the receiver, are the focus of this thesis. As will be shown, simply
determining bit values is the much easier task of the two.
Unfortunately, the sources of interference are many. The third
harmonic of some UHF transmitters is a significant source of unintentional
interference [3]. Television transmitters are particularly troublesome.
Multipath is another significant source of unintentional interference. This is
especially true with maneuvering aircraft and PGMs since the additional
3


transmission paths vary fairly quickly. Also, one of the GPS frequencies
happens to be in the band allocated for terrestrial line-of-sight microwave
radio transmitters. To make matters worse, as described in Section 2, the
International Telecommunications Union (ITU) has set flux density limits on
GPS to ensure it does not interfere with these terrestrial networks [4], This
limit effectively places the peak power density of the GPS signal 15 dB below
the thermal noise floor associated with the receiver antenna and front-end
electronics [5]. In other words, even in a pristine RF environment, the GPS
receiver must pull the signal out from 15 dB below the noise floor.
As if unintentional interference doesn't cause enough problems, the
GPS signal is very susceptible to jamming. With the transmission power
limits placed on the satellites, jammers require very little output power to
deny signal reception. Tests conducted in England showed a 1 watt
transmitter could interrupt GPS signal reception as far as 95 kilometers away
[6], Such broadband noise is one problem. Another is "spoofing," which is
the attempt by a military enemy or terrorist organization to create a false
signal that the receiver will lock onto and derive incorrect positional data. If
successfully employed against unsuspecting users, aircraft could be forced
to crash on take-off or landing, PGM's could be vectored away from their
targets, and ships in dense shipping channels, such as the Suez Canal,
could be run aground or into each other.
The GPS was designed to largely account for these many problems.
Direct sequence spread spectrum techniques are used to increase the
overall power transmitted by the space vehicles while keeping the flux
4


densities within the constraints set by the ITU. This provides a receiver quite
a bit of signal gain to counter broadband jamming and white noise.
Conveniently, the despreading process also eliminates a great deal of
narrowband noise as well. In addition to the spread spectrum techniques,
the signal also uses the extremely low data rate of 50 baud. By transmitting
only one bit every 20 msec, the white noise tends to cancel itself out and its
effect is significantly reduced.
However, even these signal processing enhancements leave the
signal extremely vulnerable. It was the intent of this thesis to investigate the
usefulness of adaptive signal processing techniques to provide even more
gain for the receivers against broadband noise. Previous coursework proved
it is possible to retrieve data from a signal that was as far as 20 dB below the
noise floor. With appropriate modifications as described in Section 6, it was
hoped similar techniques might be applicable to this area, and with
significant payoff if successful. Additionally, it was hoped a receiver's
robustness against the effects of multipath could be increased and its
vulnerability to spoofing reduced with these adaptive processing techniques.
Research revealed another area that shows great promise for
increasing the capability of GPS receivers in high noise environments.
Adaptive antenna beamforming, it seems, could allow a receiver to focus on
signals coming from satellites while notching out signals from other sources.
Adaptive beamforming uses techniques similar to adaptive signal processing,
but the results of the adaptive algorithms are used to increase or decrease
the gain associated with individual elements of an antenna array rather than
5


affecting the received signal itself. Although certainly worthy of further study,
little time was spent on the topic for this thesis.
1.2 Summary of Findings
The basic idea behind this work is described in Figure 1.1. The first
step was to create reasonably authentic GPS signals, inject noise into them,
and try to process the resulting signals in both a prototypical GPS receiver
and one enhanced with an adaptive signal processor. The results of the two
receivers could then be compared to determine if any processing
improvements were achieved.
Fig 1.1. Plan of Investigation
Based on the results of MATLAB simulations, adaptive signal
processing provided significant gain against both broadband noise and
multipath/spoofing, but this type of signal processing was unable to provide
6


any more gain than that already provided by a GPS receiver's despreading of
the direct sequence spread spectrum signal.
To form a reasonable comparison, both cases used a simulated 4
msec of a 20 msec data bit. Incoming signals were mixed with a local
oscillator to bring the signal down to baseband and filtered to remove the
sum components. For the simulated normal GPS receiver, the 4 msec of
data were averaged, reducing the effect of the white noise, and a cross-
correlation was performed to find the start of the direct sequence pattern.
With the start of the pattern identified, it was possible to despread the signal
and determine the value of the data bit being transmitted. For the
"enhanced" GPS receiver, after mixing and filtering, the 4 msec interval was
adaptively filtered. The resulting filter parameters provided both the start of
the sequence and the value of the data bit. As the level of noise and the
severity of the multipath was increased, both techniques began to fail at
approximately the same time, although the adaptive filtering usually failed
somewhat before the normal despreading techniques.
While performing research for this work, it became apparent that, with
as weak as the signal is at the receiver, the current implementation of GPS
receivers must provide a fairly robust capability against white noise.
However, the multipath problem appeared to be a different matter. Several
articles and conversations with people who have first-hand knowledge of the
multipath problem indicated there was still much room for improvement in
solving this area of concern. Furthermore, it appeared adaptive processing
was the ideal solution to deal with the "smearing effect" of multipath. The
7


simulation results therefore proved quite disappointing when the adaptive
processing techniques provided no more capability than was already inherent
in the conventional receivers.
If the receiver were only required to determine the value of the data
being transmitted, it appears the adaptive processing techniques would have
faired much better. But the nature of the GPS problem requires determining
the precise time a signal is received, and this requirement diminished the
capability of this algorithm.
1.3 Thesis Outline
The second section of this thesis describes the GPS signal and its
non-noisy environment. The section will describe the signal itself, how it is
constructed, and the effect of direct sequence spread spectrum on the
signal's power pattern. It will also compare the simulated signal with
characteristics of the actual signal to show level of fidelity. To be complete,
the section will also describe attributes of the signal environment that were
not modeled.
The third section gives a block component description of the receiver.
It covers signal flow in the prototypical receivers and how the simulations
approximate that flow.
The fourth section then gives a more detailed description of the types
of noise created to corrupt the GPS signals. It also includes a justification for
treating attempted spoofing in the same class as multipath, along with
differences between how the two must be handled.
8


The fifth and sixth sections provide a tutorial review of adaptive signal
processing theory and describe how the classic adaptive algorithms needed
to be modified to suit the particular case of detecting a direct sequence
spread spectrum signal. They also describe the different types of estimation
algorithms and why the ones that were used were chosen.
Finally, the seventh section gives detailed results of the simulations,
comparing the results of the standard receiver to that of the receiver
"enhanced" with the adaptive processing algorithms.
1.4 Notation and Terminology
Abbreviations
BPSK
CDMA
DoD
DS-SS
FFT
FIR
GPS
IF
IOC
ITU
LMLSR
LMS
LNA
Bi-Phase Shift Keyed
Code Division Multiple Access
Department of Defense
Direct Sequence Spread Spectrum
Fast Fourrier Transform
Finite Impulse Response
Global Positioning System
Intermediate Frequency
Initial Operation Capability
International Telecommunications Union
Linear Maximal Length Shift Register
Least Mean Squares
Low Noise Amplifier
9


LO Local Oscillator
LOS Line of Sight
MA Multiple Access
PGM Precision Guided Munition
PRN Pseudo-Random Noise
PSD Power Spectral Density
RF Radio Frequency
SA Selective Availability
SNR Signal-to-Noise Ratio
SOI Signal of Interest
SV (GPS) Space Vehicle
Terminology
C/A Code
C/A(t)
chip
D(t)
E{ }
fc
fd
u
Gs
^ma
L
Course Acquisition Code
C/A Code's 1.023 Mchip/sec signal
Single state in a DS-SS signal, analogous to a data bit
GPS' 50-baud data signal
Expected Value of a Random Variable
Chip frequency (1.023 MHz for C/A Code)
Data signal frequency (50 Hz)
Sampling frequency
PSD of a GPS Signal
PSD of a GPS Signal with multiple access noise
Order of an adaptive filter
10


Li GPS carrier at 1575.42 MHz
*-2 GPS carrier at 1227.60 MHz
N0 PSD of the white noise floor
N0eq PSD of the equivalent noise floor due to G,
P Code Precision Code
P(t) P Code's 10.23 Mchip/sec signal
Ps Total signal power
a2 Variance of a Random Variable
11


2. GPS Signal Environment
A pristine GPS signal environment is still fairly complex. There is
quite a bit to understand about a single GPS signal that is pertinent to this
thesis. To add to the complexity, the developers of the system chose to use
code-division multiplexing rather than time- or frequency-division multiplexing
to distinguish between the signals transmitted by the differing satellites.
Therefore, there can be anywhere between four and eleven similar signals
(using a minimum elevation angle of 10 degrees) [7] in the same time-
frequency space. In addition to these issues, there are several other
characteristics of the environment that were not modeled. In general, these
do not affect the outcome of this thesis. Those that have an effect on one
receiver implementation should have an equal effect on the other as well,
canceling out when the two methods are compared.
2.1 An Individual GPS Signal
2.1.1 Signal Modulation
Each GPS space vehicle transmits two signals, known as L-, and L2, at
the RF's of 1575.42 MHz and 1227.60 MHz, respectively. A data-carrying bit
sequence modulates the carriers with the values of {1, -1} at a rate of 50 bits
per second. This results in narrowband signals of the form:
(2.1)
d(t) = D(t)A cos co0t
12


where D(t) is the data sequence.
In addition to the data modulation, two different codes also modulate
these carriers: the course acquisition (C/A) and the precision (P) codes.
Like the data sequence, both codes use the values {1,-1} to effectively
phase modulate the carrier signals. The L1 signal is modulated by both the
C/A and the P Codes, with the P Code modulating the carrier in quadrature
phase to the C/A Code. Only the P Code is typically used to modulate the L2
carrier. Both codes use pseudo-random noise (PRN) sequences, giving the
signals their direct sequence spread spectrum (DS-SS) attributes. The
resulting spread spectrum signals can be described by
(2.2)
Lx(t) = C / A(t)D(t)Acos (Djt + P(t)D(t)-j=sin coj
(2.3)
L2(t) = P(t)D(t)j= sin (02t
where C/A(t) and P(t) are the C/A and P Codes, respectively. Note that the P
Code is transmitted at half the power of the C/A Code. Figure 2.1 gives a
generalized view of the baseband spectra of the data signal and both the C/A
Code and P Code signals. Figure 2.2 is a simplified schematic of how these
signals are produced.
13


Power Spectral Density for Baseband Data Signal
Hz
PSD for Baseband C/A Spread Spectrum Signal
Fig 2.1. Baseband Spectra for Data Signal and Both C/A and P Codes
14


Kx)<+)--L,(t)
Fig 2.2. Circuit Creating L,(t) and L2(t).
The PRN sequences are known as "chip sequences," and individual
states in the sequence are known as "chips" rather than bits to emphasize
the fact they do not by themselves carry data. The PRN sequences used
with the C/A Code have a chip rate of 1.023 Mchips per second (i.e. just
under 1 psec per chip) and sequence lengths of 1023 chips, resulting in a
chip sequence that repeats every millisecond. The C/A Code PRN
sequences are timed to coincide with the data bits, with each data bit lasting
20 C/A PRN sequences. The P Code uses a chip rate that is ten times
faster, 10.23 Mchips per second, but its sequence lasts exactly one week.
15


2.1.2 Basics of Direct Sequence Spread Spectrum
Direct sequence spread spectrum signals perform their spreading
function by taking a relatively slow bauded signal and giving it the
appearance of one with a high baud rate, thereby spreading the energy in the
signal over a wider bandwidth. However, the actual data rate does not
change, resulting in no more data entropy in the wider signal than was
present in the narrowband signal. Since the data stream and both chip
sequences approximate pulsed sequences, their power spectra approximate
sine functions. With the data stream's low baud rate, its spectrum is
extremely narrow, with the first null at 50 Hz above and below the carrier, as
shown in Figure 2.1. But when the data signal is multiplied by the C/A
Code's chip sequence, the first null is moved out to 1.023 MHz above and
below the carrier. Since the power spectral density is proportional to
(2.4)
G(f) = f
J c
( .
sm
fc
Â¥
fc
the peak power density is reduced by a factor of
16


(2.5)
1
L
h
50
1,023,000
-43 IdB
in the case of the C/A Code and by -53.1 dB with the P Code (or -56.1 dB
when the decrease in transmitted power is taken into account). This is
evident in both Figure 2.1 and Figure 2.3, which shows the spectrum of the
L1 signal at RF. Note the effect of both the C/A and the P Codes are present.
A DS-SS signal such as is used with GPS is very easily despread at
the receiver. Since the chips take on values from the set {1, -1}, multiplying
the received baseband signal by an internally-generated matching chip
sequence results in a constant voltage output, modulated only by the 50
baud data stream. The only difficulty is in identifying and synchronizing to
the start of the chip sequence. As the results of this thesis will show, this is
the critical factor in processing GPS signals in both high noise and
multipath/spoofing environments. With a reasonable signal-to-noise ratio
(SNR), the start of the C/A Code can be found by cross-correlating the
received signal with the PRN code.
17


Power Spectral Density for L1
MHz
Fig 2.3. L, Signal at RF
It is obviously impractical to use this technique to synchronize with the
P Code's week-long sequence. Once the C/A Code is acquired and locked
to, the resulting data stream contains cues to tell the receiver where in the
sequence the P Code is at, thus the term "Course Acquisition Code."
The despreading function has a very interesting effect on narrowband
noise that works its way into the receiver. Since despreading is
accomplished with the same procedure as the original spreading, the
despreader will take narrowband noise and effectively spread it out in the
18


same manner that the data signal was spread in the transmitter, complete
with reduction of the peak power. Unfortunately, the despreading has no
effect whatsoever on broadband white noise. This is apparent when one
recalls that multiplying a signal by the PRN sequence is equivalent to
convolving its spectrum with the sine pattern of the PRN. Convolving the
constant white noise spectrum with the sine-shaped PRN spectrum still
results in a constant spectrum.
2.1.3 Gold Codes
Using the cross-correlation technique to synchronize with the start of
the PRN code requires codes that have very well-behaved cross- and
autocorrelation properties. The system designers chose to use a set of
sequences known as Gold Codes. When applied to the specific case of the
GPS C/A Code, this family of sequences each consists of 511 chips of value
+1 and 512 chips of value -1. Each spacecraft is assigned its own Gold
Code, thereby giving it a unique C/A chip sequence. With a sequence length
of 1023, the autocorrelation sequence has a value of 1023 at the match-up
and values from the set {-65, -1, 63} everywhere else, according to the
probabilities shown in Table 2.1 [8], Similarly, the cross-correlation between
two Gold Codes also results in the same set of values with the same
probabilities.
19


Correlation Level Probability of Level
-65 0.125
-1 0.75
63 0.125
Table 2.1. Probability of Cross-Correlation Levels
The C/A Gold Code sequences are created using two linear maximal
length shift registers (LMLSR), configured as shown in Figure 2.4 [9]. The
process is starting by initializing all registers to ones. All addition is done in
Modulo-2. A linear maximal length shift register is one who's state diagram
cycles through every possible state except that of all zero's. For a ten-
position shift register, this means the register will repeat its pattern every
21 -1 = 1023 clock cycles. Two important properties of codes generated
with maximal length shift registers are that, first, the sequence will have a
nearly equal number of one's and zero's (2n^-i zero's vs. 2n one's), and
second, by adding together two time-offset versions of the same code, the
result is again the same code, but with a phase difference.
All GPS C/A Gold Codes are created using the two linear maximal
length shift registers with taps as shown in Figure 2.4. Note that the output
of the lower register is obtained by adding the contents of two of the digits in
the register. Digits 5 and 7 are used in the figure. This is where the
designers made use of the fact that two time-offset versions of the sequence
20


gives the same code with a phase difference. By choosing different output
tap points for the lower register, the phase of the sequence coming from the
lower register is changed, resulting in a different C/A Gold Code for each
space vehicle. The tap points, listed in Table 2.2, indicate the circuit is
configured to produce the Gold Code for SV 25. The final step in creating
the C/A chip sequences is to map the zero's in the output to +1 and the one's
in the output to -1.
The MATLAB code used to create the chip sequences is listed in
Appendix A.1. As a check, the first ten chips of each sequence were
compared against those listed in Spilker [10], which are included in Table
2.2.
21


Space Vehicle Number LMLSR Tap Points First 10 Chips (Octal)
1 2 & 6 1440
2 3 & 7 1620
3 4 & 8 1710
4 5 & 9 1744
5 1 & 9 1133
6 2 & 10 1455
7 1 &8 1131
8 2 & 9 1454
9 3& 10 1626
10 2 & 3 1504
11 3 & 4 1642
12 5 & 6 1750
13 6 & 7 1764
14 7 & 8 1772
15 8 & 9 1775
16 9& 10 1776
17 1 & 4 1156
18 2 & 5 1467
19 3 & 6 1633
20 4 & 7 1715
21 5 & 8 1746
22 6 & 9 1763
23 1 & 3 1063
24 4 & 6 1706
25 5 & 7 1743
26 6 & 8 1761
27 7 & 9 1770
28 8& 10 1774
29 1 & 6 1127
30 2 & 7 1453
31 3 & 8 1625
32 4 & 9 1712
Table 2.2. Shift Register Tap Points and Resulting Gold Code Values
22


Figure 2.5 is the result of performing an auto-correlation of the chip
sequence from space vehicle (SV) #1. As can be seen in the top plot, the
last entry in the sequence is 1023, signifying a complete match with itself. All
other numbers in the sequence are either -65 (120 occurrences), -1 (782
occurrences), or 63 (120 occurrences), approximately as would be expected
from Table 2.1. The lower plot is a close-up of the first 100 points to more
clearly show the three levels.
Auto-correlation of Gold Code #1
Fig 2.5. Typical Autocorrelation Results Against PRN Sequences
23


Similarly, Figure 2.6 shows the result of a cross-correlation between
the chip sequences from SV #10 and SV #20. In this particular case, -65
occurs 124 times, -1 occurs 759 times, and 63 occurs 140 times.
Cross-correlation Between Codes 10 & 20
80ii>' i \ 1
-801--------1--------'-------1-------1--------1--------
0 200 400 600 800 1000 1200
Fig 2.6. Typical Cross-correlation Results Against PRN Sequences
24


2.2 Nominal Signal Environment
When the idea of GPS was conceived, the system was not granted
exclusive use of a band of RF spectrum. Therefore, a single GPS signal
transmitted by a given SV typically shares its spectrum with a number of
other signals. Probably the two types of signals that had the greatest impact
on the design of the system are line-of-sight (LOS) microwave
communications and other GPS signals coming from the different SVs. In
addition to these, a lesser impact was felt from the need to protect certain
frequencies used in radio astronomy. Before the DS-SS signals are
transmitted, they are specifically filtered to reduce interference on radio
astronomy's RF's of 1420.4, 1665.402, 1667.359, and 1720.530 MHz [11].
2.2.1 Microwave Communications
Not only was GPS not allocated its own frequency band, the designers
chose a band that already had restrictions placed on it to prevent users from
interfering with line-of-sight terrestrial microwave communications. The ITU
has set flux density limits of -154 dBW/m2 for any 4 kHz frequency band
between 1.525 and 2.500 GHz [12]. One of the primary drivers for using DS-
SS for GPS signals was to remain within the constraints of this limitation.
One of Claude Shannon's major findings was that the maximum data rate of a
noisy channel with a bandwidth of H Hz and an SNR of S/N is given by [13]
25


baud _rate ^ = H log2(l + %).
(2-6)
In the case of the GPS' 50-baud data signal, if the signal is bandlimited to
include just the main lobe of the signal, this relationship requires an SNR of
0 dB. But by spreading the data signal with the C/A Code, and bandlimiting
to include just the main lobe, a receiver can theoretically detect and process
a signal with a -44.7 dB SNR. So by spreading the signal out over a wider
bandwidth than required by the data rate, the designers could transmit a
signal from space with sufficient power to be received by an easily
transportable receiver on the surface and still remain under this limit.
The minimum specified strength on the L1 link is Ps = -160 dBW at the
receiver for a satellite at a 5 elevation angle. Since the maximum power
spectral density for a sine-shaped spectrum is Ps/fc, the maximum density is
(2.7)
Ps/fc = -160 dBW -10 log(1,023,000) = -220.1 dBW/Hz.
An ideal lossless antenna has a gain given by
G = AtzAJX2.
(2.8)
Therefore, an ideal antenna with unity gain has an effective aperture area
26


(2.9)
A = X2!A% = 2.8856 x 10"3 m2 = -25.4 dBm2
for the GPS L, signal at 1575.42 MHz (X = 0.1904 m), resulting in a maximum
power flux density per hertz of
Ps/fcA = -194.7 dBW/Hz-m2.
(2.10)
The maximum power flux density a GPS signal injects into a voice grade
channel will be that into one centered on the carrier at a flux density slightly
less than
(2.11)
4 x 103 Ps/fcA = -158.7 dBW/m2,
just under the specification of -154 dBW/m2 [14].
The above calculations are based on the minimum specified power of
-160 dBW. It is interesting to note that the expected maximum power is
-153 dBW, occurring at an elevation angle to the satellite closer to 40. This
7 dB increase raises the flux density above the specified levels. It is unclear
from the source documents, but this may be allowable based on the fact that
LOS radio relay antennas generally have significantly lower gains at these
higher elevation angles.
27


2.2.2 GPS Multiple Access Signals
The one guaranteed source of interference to a given GPS signal is
the three to ten other GPS signals being transmitted simultaneously and on
the same frequency by the other SV's in view of the receiver. (Actually, as
will be explained in Section 3, all are of interest to the receiver. However,
portions of the receiver must be able to focus on only one signal at a time,
disregarding the others as common interference.) However, thanks to the
cross-correlation properties of the Gold Codes and the high chip rate relative
to the data rate, this interference proves to be rather minimal.
Code Division Multiple Access (CDMA) schemes rely on codes, such
as GPS's Gold Codes, that are relatively uncorrelated for all time offsets.
Because this is the case, two received sequences are fairly easy to separate
in a GPS receiver. Two such signals with random offsets can be represented
by s-,(t x.,) + s2(t x2). When the receiver attempts to despread this signal to
obtain s1; it multiplies the signal by a synchronized copy of s^s Gold Code,
resulting in
(2.12)
si(t-*i)k(f Ti) + s2(t-T2)] = l + Si(f- Tj)s2(t-r2),
where the unity term is the one of interest, and the other term is the multiple
access interference. Keep in mind that the unity term is actually the data bit
received during that particular chip sequence. Taken over a longer period of
time, this term is actually the 50 baud data stream D(t). Assuming similar
power levels, Ps, the spectrum of the multiple access term, Gma(f), resulting
28


from the product of the two time-domain signals is the convolution of their
similar spectra:
G..(0 ) = P,\GlWv-
(2.13)
After the despreading function, the receiver can pass the signal through a
bandpass filter with a passband on the order of 50 Hz. Since fcfd, this filter
will eliminate almost all power in the multiple access interference except that
near f = 0. The remaining interfering power can be found to be [15]
(2.14)
G If there are M = 11 GPS satellites in view at a given moment, there will be
M -1 = 10 interfering multiple access signals. This will effectively raise the
noise floor from N0 to
29


(2.15)
N
oeq
= N0 +f(A/-l)
= N
l + f(M-l)|

)}
or in terms of decibels of increase,
(2.16)
N,
oeq
= 1.2157
= 0.8484dB.
Here, we have made use of the fact that the spectral peak of the received
signal is Ps/fc = -220.1 dBW and, as will be discussed in Section 3, the fact
that the thermal noise floor of a typical receiver is N0 = -205.2 dBW. Clearly,
the impact of the interfering signals from the other SVs is measurable, but it
does not add significantly to the processing problem. Such is the utility of
CDMA systems.
2.3 Simplifications to the GPS Signal Environment
In an attempt to bound the scope of this thesis and to make possible
simulations that could be run on a personal computer in a reasonable
timeframe, some simplifications to the model of the GPS signal environment
30


were required. Additionally, there are several characteristics of the
environment that were not modeled simply because they did not appear to
have an effect on the problem being studied, namely retrieving signals from a
high noise environment.
2.3.1 Simplifications for Ease of Processing
The most significant reduction in scope came from focusing on only
the L1 signal, and only the C/A Code on L,. This is not so outlandish as it
may sound. Except on rare occasions when required by the Department of
Defense (DoD), the data on the P Code is encrypted and readable only by
military users with a proper decryption key. Therefore, many civilian
receivers ignore the P Code on both carriers also. In such cases, it is only a
concern in that the receiver must make sure it locks to the C/A Code on the
carrier, and not the P Code in phase quadrature. Also note that the week-
long chip sequence is not encrypted, but only the 50 baud signal under it.
This is done to ensure readable data despite adversaries' attempts to spoof
the receiver with faulty data.
With the P Code's anti-spoof capability, one might question why the
issue of spoofing is even addressed as a potential problem. The first reason
is that civilian receivers are still prone to spoofing from terrorist
organizations. The second is that even a military receiver needs to lock onto
the course acquisition signal and read correct data in order to find where in
the week-long sequence the P Code is. And the third is that even the P
Code is susceptible to a form of spoofing. Since the P Code chip sequence
31


is published and not altered, it is possible for an adversary to transmit the
sequence a couple microseconds ahead or behind the actual signal. A smart
jammer could start with a duplicate signal timed to arrive at the receiver at
the same time as the actual signal. By letting the false signal drift, an enemy
could pull the victim receiver off the actual signal in much the same way a
velocity gate pull-off jammer attacks intercept radars on fighter aircraft. The
small variation introduced should not affect the receivability of the data
stream, but it is more than enough to introduce large errors in the timing
circuitry and subsequent position calculations. Since the GPS signals travel
at 300 m/|isec, if the receiver locks to a false signal that is 3 p.sec ahead of
the actual signal, positional errors on the order of a kilometer could be
introduced.
The second major concession that was required was to limit the
sample signals to 4 msec (4 C/A chip cycles). Simulations took prohibitively
long when more than about 4000 samples were used. With a C/A chip rate
of 1.023 MHz, this dictated a signal length of no more than 4 msec. This
gave considerably poorer performance in the presence of white noise since
the simulation could only add four sets of correlated samples to make use of
white noise's zero-mean value.
The model also did not include the phase-locked loops used in
acquiring the carrier. It was assumed the receiver would be able to
determine the phase of the incoming signal and lock to it. Furthermore, it
was desired to accurately model the signals chipping rate and resulting
bandwidth. But since at least four chip cycles were needed to get reasonable
32


results, it became necessary to sample the RF signal at no higher than 10.23
MHz. To minimize aliasing, the carrier was dropped to approximately
10.23/4 MHz = 2.5575 MHz instead of the actual 1575.42 MHz. As shown in
the figures in Section 3, aliasing was still present, but not prohibitive to good
processing.
2.3.2 Irrelevant Characteristics
In addition to these, there are quite a number of other issues affecting
the GPS signal environment that were not modeled in the pursuit of this
thesis. For the most part, they deal with the timing and the resulting phase
differences associated with incoming signals. Since extremely accurate time
measurements are at the very heart of GPS receivers, these are some highly
significant issues when designing receivers. But the focus at hand was more
on trying to increase the receivability of noisy signals rather than simulate all
the inner details of a receiver.
One of the most significant issues avoided was that of Doppler on the
signals resulting from the moving spacecraft. The range from a stationary
receiver to a single SV can vary by as much as 5600 km, resulting in a range
rate of up to +/- 0.465 km/s. This introduces a maximum of +/- 6 kHz of
Doppler on the carrier [16], Most receivers generally account for this in the
final stage of mixing as the data signal is brought down to baseband.
Another major issue real-life receivers must contend with is that of
tropospheric and ionospheric delays. The time-varying group delays
introduced as the GPS signals travel through the atmosphere can introduce
33


significant errors if not properly accounted for. Many receivers make use of
the fact the group delays are different for the L-, signal as opposed to the L2
signal due to their differing frequencies. Measuring that difference only
depends on being able to reliably follow the chip sequence of the P Code
and not the underlying data, which as previously stated is usually encrypted
[17]. This, by the way, is another reason for introducing an anti-spoofing
measure for the P Code as well as the C/A Code.
Another characteristic not modeled was Selective Availability (SA).
SA is a controversial method the DoD uses to prevent potential adversaries
from using the highly accurate GPS against U.S. forces. This technique
purposely introduces errors in the C/A Code's underlying data stream to
reduce the accuracy of the calculated receiver positions. Even if SA had
been modeled, there is nothing a civilian receiver can do about it, so it would
have had no impact in the receiver simulation.
A final factor worth noting is the effect of relativity on GPS. Due to the
speed of the orbiting SVs and the need for extremely accurate time
measurements, relativistic effects cannot be ignored in finding accurate
position and time transfer solutions [18]. This problem is countered on the
spacecraft, not in the receiver. Before launch, the satellite's rubidium clock is
set slightly slower than real-time so that when the signal is received on the
surface, it appears correct. This does not have any effect on real-life
receivers. It is mentioned here more out of amazement that there is an
everyday technology that must take into account the effects of relativity to
work properly.
34


2.4 GPS Signal Simulations
This section will focus on the MATLAB code created to simulate GPS
signals, briefly expounding on the comments already in the code, and then
showing examples of output and comparing that to what is expected to get an
impression of the simulation fidelity. As mentioned in Section 2.2, the
MATLAB code listing for creating the Gold Codes can be found in Appendix
A.1. The listing for the L1 signal generation is given in Appendix A.2.
2.4.1 Gold Code Generation
The GOLDCODE.M routine is fairly straight-forward. The heart of it is
two nested 'for' loops that perform the function of the LMLSR circuit of Figure
2.4. Once the 32 chip sequences are developed, the values are converted
from the set {0,1} to {1 ,-1}. To verify the routine worked correctly, the
elements of each sequence were added and verified that each sum was '-T,
indicating each was made of 511 one's and 512 negative one's. Choosing
several at random, auto- and cross-correlations were performed to make sure
they produced sequences typical of Figures 2.5 and 2.6. As one last check,
the sequences were converted back to a series of one's and zero's and
compared the first ten chips with the values listed in Table 2.2. Each of
these checks indicates the MATLAB routine created accurate C/A Gold
Codes.
35


2.4.2 L1 and Multiple Access Noise Generation
The code used to create the L1 signal and the multiple access noise is
also fairly straightforward. The major blocks of the program are shown in the
flowchart of Figure 2.7. After creating a carrier, the routine randomly
chooses the attributes to be assigned to the various simulated signals. The
chip sequence for the first signal of interest (SOI) is created, complete with
random starting point, and it is mixed with the carrier signal. The same is
also done with the other signals coming from other SV's to create the multiple
access noise.
As mentioned in Section 2.3, 2.5575 MHz was chosen as the carrier
for the simulations. That, coupled with a sampling rate of fs = 10.23 MHz,
placed the GPS signal in the center of the spectrum. With a chip rate of
1.023 MHz, this choice of parameters allows room for the mainlobe and one
and a half sidebands of the spectral sine pattern before the spectrum repeats
at fs/2 = 5.115 MHz. A higher sampling rate was originally tried so that more
sidebands could be incorporated, but this became prohibitive when it was
realized 4 msec of signal were needed to get usable results.
Once a carrier had been created, various signal parameters for the
SOI and the multiple access GPS signals were chosen. These parameters
included the SV number (i.e. the chip sequence), the data bit that was being
transmitted during the 4 msec time window, the phase of the carrier, and the
phase of the chip sequence. Random carrier phases were created to make
36


Fig 2.7. Flow Chart for the Creation of L-, and Multiple Access Noise
37


the simulations more characteristic of the signal environment, since the
various real-life signals could not possibly be coherent in the general case of
random spacecraft and receiver geometries. The non-coherent signals
introduced a certain amount of processing gain in the receiver, but since the
intent was to compare the results of a prototypical receiver versus one using
adaptive processing and not to necessarily test worst-case conditions, this
seemed an appropriate factor to include in the simulation. Choosing random
data bits and random chip sequence phases also increased simulation
fidelity, but the primary reason they were incorporated was to verify the
results of the two receivers. The real test of the receiver is whether or not it
is able to identify the timing of the chip sequence, and once it has sync'ed up
to it, being able to identify the data bit being transmitted.
After the SVs had been chosen, the chip sequence could be created.
Naturally, these had to be sampled at the same fs = 10.23 MHz rate as the
carrier, resulting in 10 samples per chip. The example shown in Figure 2.8
shows the first 20 chips from SV #1 sampled at 10.23 MHz. Note that the
pattern of the first 10 chips matches the octal code listed in Table 2.2.
38


First 20 Chips from SV#1
1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
0 5 10 15 20
microseconds
Fig 2.8. Sampled PRN Code from GPS Satellite #1
The resulting power spectral density of the C/A Code from SV #1 is
shown in Figure 2.9. This is measured relative to the total signal power, Ps.
The figure only shows the mainlobe and first 3 sidebands, whereas the actual
simulation created a baseband signal with 4 sidebands out to +/- 5.115 MHz.
As should have been expected, the sine pattern has nulls every 1.023 MHz,
corresponding to the chip rate of the C/A Code. What may not have been
expected is the fact that the spectral lines do not trace out a nice smooth sine
envelope. This becomes more apparent with Figure 2.10.
39


-20
Power Spectral Density at Baseband
Figure 2.10 is a close-up of the first 100 spectral lines for the C/A
Code for SV #1. This view brings out a couple features. First, as just stated,
the spectral lines do not trace out a smooth sine pattern. This is associated
with the fact that the autocorrelation function for the Gold Code sequences
occasionally takes on the values of -65 and +63 according to Table 2.1. If
sequences were chosen that always gave autocorrelations of -1 for out-of-
phase shifts, the resulting spectrum would be a much smoother sine pattern.
As further evidence of the high fidelity of the signal generating routine, Figure
2.10 is a perfect match for Figure 27.a. in Spilker [19].
40


PSD for First 100 Line Components
Fig 2.10. Spectrum of the C/A Code from DC to 100 kHz
Also apparent from Figure 2.10 is the extremely small DC component,
resulting from the fact there are very nearly the same number of chips at -1
as there are at +1. In fact, the DC component relative to total signal power is
41


(2.17)
= -60.2dBW
Since the chip sequences last exactly one millisecond, the PSD
should consist of spectral lines at multiples of 1 kHz. This is not so obvious
from Figures 2.9 and 2.10 since they were created by performing an FFT on
just one C/A chip sequence. The PSD plot shown in Figure 2.11 is the result
of an FFT performed on a 4 msec signal containing a full four chip
sequences. In this case, the 1 kHz lines are much more apparent. The
energy at frequencies off the 1 kHz-multiples is almost 350 dB below that on
the multiples. Most of this "energy" is probably the result of MATLAB round-
off errors.
42


0
PSD Showing 1 kHz Lines
Fig 2.11. C/A Code Spectrum Illustrating 1 kHz Lines
Figures 2.8 through 2.11 all depict signals prior to mixing with the
carrier and prior to reducing the power in the signal to levels more typical at
the receiver.
Once the SOI was ready, adding the multiple access noise was simply
a matter of repeating the process, but using the spacecraft, data, and phase
parameters chosen for each of the other signals. A typical resulting signal
spectrum is shown in Figure 2.12. This example reflects the signal at the
modified RF of 2.5575 MHz and at the reduced power level. Note that there
are only one and a half sidebands present, with the others being aliased into
43


the remaining mainlobe and sidebands. The aliasing was unavoidable given
the bandwidth of the signal and the relatively low sampling frequency.
PSD of L1
-210
-220
-230
i -240
O
-250
-260
-270
(
MHz
Fig 2.12 Spectrum of the Simulated L1 Signal at the Receiver
At this point, we have GPS signals typical of what a receiver should
expect to see. There is not yet any additional noise injected into the signal
environment. A description of the noise used to corrupt the signals is given
in Section 4.
44


3. Description of Current GPS Receivers
Section 3 describes the basic functions of most civilian GPS receivers
as they pertain to the task of recovering and processing signals in noisy
environments. Following that, it describes the MATLAB code used to
simulate a generic receiver.
3.1 Prototype Receiver Description
There are a multitude of GPS receivers on the market today, many
designed specifically for applications other than navigation, such as
surveying and precision time measurement. However, all require many of the
same building blocks to acquire GPS signals and reduce them to their
50 baud data signals. Figure 3.1 is a block diagram of a generic GPS
receiver [20]. The differences that arise due to a particular application are
generally contained within the data processing block.
Incoming signals are amplified, mixed with a local oscillator and
filtered to bring them down to an Intermediate Frequency (IF). The signals
are then further downconverted and filtered, bringing them near baseband.
At this point they are digitized and sent simultaneously to multiple channels.
Each channel consists of a correlator and accumulator that is looking for a
specific Gold Code sequence. If a channel is successful at finding and
locking to the PRN sequence it is looking for, it will continue to process that
signal until the satellite drops below the horizon or some other circumstance
45


arises for it to break lock. The resulting 50 baud data stream is fed to the
data processing block. If a channel is not successful at finding its particular
sequence, it will try others until it is successful. The data processing block is
responsible for performing the triangulation and navigation or other
application processing, and providing the data to the user or to other
equipment via output ports.
Pre-Amp and
Downconverter
) Filtering
Frequ Synthe ency sizer Reference Oscillator
IF
-Tr^-
User
Interface
Gold Code
Generator
-----------
ZF
Correlator -Accumulator
^ZF
) Correlator -----$ Accumulator -----)
Data
Processing
ZF
$ Correlator -----^ Accumulator -----^
Fig 3.1. Block Diagram of a Generic GPS Receiver
A critical factor in the front-end electronics of the receiver is the
thermal noise density, given by
N=kT
(3.1)
46


where k is Boltzman's constant (-228.6 dBW/K-Hz) and is the receiver's
equivalent noise temperature. The equivalent noise temperature is defined
as:
t, = Vl +
(L-
1K/L
+ r,
R
(3.2)
where TA is the antenna's noise temperature, L is the loss due to the
transmission line and bandpass filter between the antenna and the low noise
amplifier (LNA), T0 is the ambient temperature, and TR is the receiver noise
temperature, given by
(3.3)
Tr=T0(F-1),
where F is the receiver noise figure, expressed as a plain number not in
decibels [21]. Using typical values, one finds thermal noise densities on the
order of
(3.4)
Nc = (-228.6dBW/K Hz) (1305(.l)+ ((U 1)290%) + 290*(1.259 -1)]
= -205.2dBW/Hz
As described in Section 2.2.1, we know we can expect the peak of the L-,
power spectral density to be approximately
47


(3-5)
Ps/fc = -220.1 dBW/Hz.
Therefore, the most powerful part of the GPS spectrum will typically be about
15 dB below the thermal noise floor of the receiver. With its higher chip rate
and lower transmitted power, the peak of the L2 spectrum is another 13 dB
below this.
Most receivers go through two or more stages of bandpass filtering,
downconversion, and lowpass filtering as the GPS signal is taken from RF
down to baseband. Figure 3.2 depicts one such generic stage. The signal
with wideband noise is bandpass filtered to leave the signal with (relatively)
narrowband noise. This is mixed with a local oscillator (LO) to take the signal
down to an IF or baseband, and the upper image is rejected with a lowpass
filter. As was just shown, the noise level is typically higher than the signal,
but for clarity, the figure shows the peak signal power above the noise.
Generally, receivers attempt to retain 10.23 MHz of signal bandwidth at
baseband. This allows for the mainlobe and nine sidebands of the C/A
spectrum, but only the mainlobe of the P spectrum.
LO
Fig 3.2. Typical Downconversion Stage
48


The analog signal is typically digitized at either one of the latter IF's or
at the end of the downconversion at baseband. The resulting data stream is
then fed into the correlators of each of the receiver's channels to allow
simultaneous tracking of multiple spacecraft. Once a correlator locks up its
locally derived Gold Code with the incoming digital signal, it multiplies the
two to perform the despreading operation. Recall that the PRN sequences
are composed entirely from the set of {-1, +1}. Multiplying such a sequence
by itself results in a steady value of one. The result of this multiplication is
fed to the channel's accumulator.
Although the correlator removed the PRN chip modulation, the
digitized signal is still modulated by the 50 baud data stream, D(t), and by
noise. Generally speaking, the noise has a zero-mean value. This is largely
removed by the accumulator, which effectively acts as a simple lowpass filter.
The extremely low data rate of the GPS signal provides the accumulator with
20 msec of samples to allow the noise values to cancel each other out. At
this point, the signal D(t) should be the primary source of modulation, and its
value of either plus or minus one is converted to zero or one, respectively,
and fed to the data processor.
3.2 GPS Receiver Simulation
Like Section 2.4 did for the GPS signal, this section will explain the
MATLAB code developed to simulate a GPS receiver, pointing out where the
49


simulation varies from the prototype and providing examples of typical output.
The code is listed in Appendix A.3.
Figure 3.3 is a flowchart of the MATLAB code RECEIVER.M. Not
surprisingly, it largely follows the receiver block diagram of Figure 3.1. After
adding thermal noise, it downconverts the signal directly to baseband. It then
performs a cross-correlation with the expected Gold Code, trying to identify
the start of the PRN sequence. After picking what it believes to be the start,
it multiplies the signal by the appropriate Gold Code to despread and makes
a decision as to whether the underlying data bit was a +1 or -1.
The routine assumes there are certain variables available in
MATLAB's variable space. It expects the GPS L-, signal, complete with
multiple access and any other type of noise, to be available in variable 'IT. It
also anticipates the Gold Codes to be resident, as well as the random signal
parameters that were chosen in L1CODE.M when the signal was created.
These parameters include the value of the data bit, the phase of the carrier,
and the phase of the PRN sequence.
The first thing a GPS signal does is pass through the antenna, a
transmission line, and front-end electronics on its way to the LNA,
experiencing a great deal of thermal noise along the way. To account for the
thermal noise of Eqn 3.4, the first thing RECEIVER.M does is creates a white
noise sequence of the appropriate power and adds it to the received signal.
The power spectrum of a white noise sequence is the variance of that
sequence [22]. The variance, and therefore the power of the noise
sequence, can be shown to be
50


Despread & Accumulate
No_
&
Downconvert
s /
Cross-Correlate
S /
Despread & Accumulate
Fig 3.3. Flow Chart for the GPS Receiver Simulator
51


(3-6)
N0-cr- £{(x(fc))2} = jmax2,
where x(k) is the noise sequence, and 'max' is the maximum value achievable
by x(k). The derivation of Eqn 3.6 can be found in Appendix B.1. Solving for
the maximum value needed to achieve a thermal noise density of -205 dBW,
(3-7)
-205dB = ^max2
1(T205 = | max2
max = V3-KT20'5
= 9.7400 HT11.
The resulting sequence is added to the L1 signal. Figure 3.4 shows a PSD
plot typical of such a signal as it enters the LNA. Even the close-up of the
spectrum at the simulated L1 carrier frequency of 2.5575 MHz shows no sign
of the GPS signal.
After the LNA, the next step in processing the GPS signal is to
downconvert it by pre-filtering, mixing it with an LO, and post-filtering to reject
the sum image. Here the simulation must vary from the real-world prototype.
The sampling rate of fs = 10.23 MHz forced the carrier to be at
fs/4 = 2.5575 MHz, well below the actual L., frequency of 1575.42 MHz. It is
therefore senseless to have a series of cascaded downconverters taking the
signal through multiple IF's. Instead, the simulation simply takes the signal
52


dBW dBW
-200
-210
-220
-230
-240
0 1 2 3 4 5
MHz
Close-up of L1 with Thermal Noise Spectrum
-195
-200
-205
-210
-215
-220
-225
-230
2.4 2.45 2.5 2.55 2.6 2.65 2.7
MHz
Fig 3.4. PSD of the L1 Signal and Thermal Receiver Noise
Spectrum of L1 with Thermal Noise
53


directly to baseband. Also, as mentioned in Section 3.1, most GPS receivers
try to maintain 10.23 MHz of bandwidth at baseband, which includes the
mainlobe and nine sidebands of the C/A signal. This is obviously impossible
given the sample rate and carrier frequency, so instead the pre- and post-
filtering was designed to retain only the mainlobe, as is typical of most
receivers when they downconvert the P signal.
Figure 3.5 shows pole-zero plots for the filters used as part of the
downconversion. In both cases, Chebyschev filters with a passband ripple of
0.1 dB were used. The pre- and post-filtering operations are more clearly
illustrated in Figure 3.6. For clarity, the signals in the figure are free of noise,
to include both multiple access and thermal noise.
Band-pass Filter Low-pass Filter
Fig 3.5. Pole-Zero Plots for Downconversion Filters
54


Filtering Prior to Mixing
0 1 2 3 4 5
MHz
MHz
Fig 3.6. Pre- and Post-Filtering of a Noise-free GPS Signal
55


The first 400 samples (40 chips) of the resulting baseband signal from
SV#8 are shown in Figure 3.7. Superimposed on the signal is the
corresponding C/A chip sequence. In the noise-free case, it is pretty easy to
see the C/A chip sequence in the baseband signal. The sharp edges were
lost from the heavy filtering of the sidebands, but it is clear the underlying
structure of the PRN code has made it through the "analog" portion of the
receiver and into the correlators.
Baseband Signal
Fig 3.7. Noise-free Baseband Signal After Post-Filtering
56


Things change rapidly as inherent (i.e. MA and thermal) noise is
introduced. The top plot in Figure 3.8 shows a baseband signal under the
influence of MA noise, and the bottom plot shows a signal with both MA and
thermal noise present. In the figure, the MA noise consisted of three
interfering GPS signals. Their effect was somewhat reduced by the fact the
signal generator, L1CODE.M, chose a random carrier phase for each of the
systems. Since the receiver phase locks onto the carrier of interest, the
baseband signals from the other satellites are attenuated some random
amount, depending on the phase of their carriers. However, their effect is
still clearly noticeable even without the thermal noise, as the signal in the top
plot does not follow the C/A chip pattern nearly as well as it did in Figure 3.7.
When thermal noise is figured in, it becomes surprising the baseband
signal can be recognized at all. The baseband signal varies significantly
from the pattern set by the C/A Code. The level of variation is even more
amazing when one notes the scale on the y-axis. With thermal noise added
in, the fluctuations in the baseband signal are approximately an order of
magnitude higher than with just MA noise or with no noise at all. Note that
the scale on the time-axis was also adjusted for the lower plot. As will be
discussed in greater detail in Section 7, this receiver simulator is not always
successful at locking onto the C/A Code with this level of noise present on
the signal. However, it was successful with the particular trial that produced
the plot in Figure 3.8, correctly identifying the start of the PRN sequence and
the value of the underlying data bit.
57


Baseband Signal with Multiple Access Noise
Fig 3.8. Baseband Signals with Noise After Post-Filtering
58


In a real-world GPS receiver, if the incoming signal was not digitized
while still at an IF, then it is once the analog signal reaches baseband.
Therefore, referring to Figure 3.1, the signal is digital as it is fed to the
various channels to be correlated and accumulated. At this point, the
simulation varies somewhat from the model. Instead of correlating and then
accumulating, RECEIVER.M first accumulates, then correlates, then
accumulates some more.
RECEIVER.M performs its first accumulation by adding corresponding
samples from each of the four PRN cycles contained within the signal. The
value of each sample is composed of the value of the C/A chip (multiplied by
the data bit) and the value of the noise signal at the moment of sampling.
The former component is the same for all four samples, but since the noise
has a zero mean, they tend to cancel each other's effects. As mentioned
earlier, the simulation would have been much more robust against such noise
if it could perform this accumulation over an entire 20 msec data bit epoch,
but this was not feasible.
At first glance, it seems this problem of too few samples to accumulate
might be overcome by taking multiple samples from a single chip. Since
fs = 10.23 MHz and fc = 1.023 MHz, each chip is composed of 10 samples.
By taking five samples from each of the four chips, it seems twenty samples
could be used to filter out the effect of the noise. However, on closer
examination, one realizes the intra-chip noise is no longer uncorrelated. The
white thermal noise (as well as any other broadband noise that entered the
receiver) was filtered along with the signal in the downconverter. In fact, with
59


the filter passbands set to approximately 1 MHz, the noise variation is
reduced to roughly the same order as the chip variation. Therefore, these
samples generally won't serve to cancel each other out. This is apparent
when considering the noisy PRN sequence in the bottom plot of Figure 3.8.
However, this is not a problem when taking samples from corresponding
chips of different PRN cycles. Such samples are roughly 1 msec apart, and
in the "spectral vicinity" of 1 kHz, the noise is basically unfiltered and
therefore the noise samples are effectively uncorrelated.
With some of the broadband noise removed as a result of the first
accumulation, RECEIVER.M is ready to perform a cross-correlation between
the incoming signal and the appropriate Gold Code. In a real receiver, the
cross-correlation serves two roles. First, by trial-and-error, it is used to
determine if a given satellite is in view of the receiver. If the correlator does
not get a match between the incoming data stream and its current Gold
Code, it will try another until it finds a match. Then, once it is using a Gold
Code that results in a strong correlation, the correlator identifies the start of
the PRN sequence and synchronizes to it. However, RECEIVER.M only
uses the correlation calculations to find and synchronize to the start of the
sequence. To save time, the simulation dispenses with the trial-and-error
search for the proper C/A Gold Code and simply checks to see what SV was
randomly selected in L1CODE.M.
Figure 3.9 shows typical outputs from the cross-correlator. The top
plot was obtained with a signal that had no noise on it. The middle was
under the influence of 10 other satellites providing MA noise, and the bottom
60


Cross-correlation with No Noise
0
-500
-1000
-1500
-2000
1 1 JL. JIlILl lMLklllkll.1 ill lll j i 1 r illt.Jkf.UllllJkJIJ 1 IMI..JJ.1JJJL.. A Ifl.I.fJ.IJliLJlJIJIJLLI 1. L jIJL
nffr lit% WiTifl 1WrfW|T i rmmxtwii 'wr'titrmii hi ftitwrfrWiTfywni nwimn i i i i_
200
400
600
800
1000
Cross-correlation with MA Noise
0
-500
-1000
-1500
-2000
0 200 400 600 800 1000
Cross-correlation with MA and Thermal Noise
-2000 :_________i_________i_________i_________i_________i_i
0 200 400 600 800 1000
Fig 3.9. Cross-correlator Outputs with Varying Levels of Noise
61


was with 10 MA noise signals as well as the receiver's thermal noise. If all
works well, the correlator output will peak when the locally generated Gold
Code has shifted such that its start coincides with the start of the received
Gold Code, thus identifying the random phase in the chip sequence.
Note that the sign of the correlation peak is a direct result of the value
of the data bit. Since the PRN code is multiplied on the SV by the value of
the data bit, when the data bit is a '+1the received baseband signal should
have a positive correlation to the locally generated Gold Code. But if the
data bit is a '-1', the chips will be opposite of what is expected, resulting in a
negative correlation. In all three cases, the data bit happened to be '-1'.
As Figure 3.9 shows, the receiver finds a strong correlation when
there is no noise besides that generated by the other GPS signals. In the MA
case, the PRN starting points for all eleven signals were easily detectable.
This is not the case when the thermal noise is added in. In the simulator trial
that generated the bottom plot, only eight of the eleven Gold Codes were
successfully acquired and locked up to.
After finding the C/A Code starting point and synchronizing to it, the
only remaining task for the receiver simulator is to despread the signal,
perform the final accumulation and make a decision as to the value of the
data bit being transmitted. Although this sounds like a fairly significant last
step, in this simulator implementation, it is more a check validating the
correlator than it is a necessary step unto itself. This is because, as just
mentioned, the correlator will provide the value of the data bit if it is
successful in finding the start of the sequence. And if it is not successful, the
62


signal will not be despread correctly, resulting in an accumulation of nothing
but noise.
Figure 3.10 gives three examples of the despreader that correspond to
the three examples in Figure 3.9 of the correlator output. Each point in the
despreader's output is obtained by multiplying the received-and-averaged
value of a PRN chip (i.e. the result of the first accumulator) with the value of
the corresponding locally generated PRN chip. The consistent values in the
top plot indicate the received-and-averaged values were very close to the
expected values (except for a sign change due to the data bit) when there
was no noise present. This is not the case with MA and especially thermal
noise present, as should probably be expected from the baseband examples
shown in Figure 3.8.
The final accumulator merely averages the samples of the despreader
output and determines whether the result is positive or negative. This final
accumulator is probably unnecessary in the noiseless case, but the thermal
noise is more than enough to require this averaging if there is to be any hope
of finding the data's value in the lower plot.
As indicated in Figure 3.1, most modern GPS receivers use multiple
channels to simultaneously track multiple signals. This is obviously not
possible in a MATLAB simulation, so the final part of RECEIVER.M is
devoted to repeating the process of breaking out data for each of the
interfering MA signals. The 'for-loop' picks up the processing thread from the
output of the bandpass filter in the downconverter, using the proper phase on
63


2
Despreader Output with No Noise
Despreader Output with MA Noise
101----------:----------.---------.---------
-10----------1----------1---------1----------1----------
0 200 400 600 800 1000
Despreader Output with MA and Thermal Noise
20
0
-20
0 200 400 600 800 1000
Fig 3.10. Output of the Despreader
64


the various carriers to bring each one down to baseband. From that point on,
the logic is the same as it was to extract data from the first signal.
65


4. Non-Standard Interference
The whole motivation behind this thesis was to explore the possibility
of enhancing GPS signal reception in particularly noisy environments by
incorporating adaptive signal processing techniques. This section describes
the types of noise injected into the nominal signal environment and the
method of injection. Processing results will be given in Section 7. The three
types of noise created are narrowband (NB) noise, wideband (WB) noise,
and multipath/spoofing. Multipath and spoofing are considered to be in the
same class of interference for reasons to be discussed in Section 4.3.1.
4.1 Narrowband Noise
While researching this subject, no references could be found stating
that GPS receivers have much difficulty with narrowband noise. In fact,
Spilker states most receivers are particularly robust against it, primarily
because the despreading function spreads narrowband noise at the same
time it despreads the GPS signal [23], This was not realized at the start of
this work, but since the original problem statement included NB noise
analysis, it was decided this thesis would follow through with it. Besides, it
seemed wise to test with NB noise to help verify simulator fidelity and to
make sure the modified receiver was equally successful in dealing with such
signals. The MATLAB code, NBNOISE.M, used to create and insert the NB
noise is contained in Appendix A.4.
66


4.1.1 Description
Two types of NB noise were created. The first was a simple
unmodulated tone placed directly on the carrier as well as 1.023 MHz above
it. The second was a 2400 baud bi-phase shift-keyed (BPSK) signal. This
particular signal was chosen because it seemed like a fairly realistic signal,
and it seemed likely the BPSK modulation might cause the receiver
additional problems in discriminating it from a GPS signal. Additionally, the
baud rate is sufficient to provide almost ten bits in the 4 msec of simulated
signal.
Figure 4.1 shows an example of the latter type of NB noise. The ten
bits are chosen at random and used to modulate an 1800 Hz subcarrier. The
subcarrier is then mixed to place it directly on the simulated GPS carrier of
2.5575 MHz. Figure 4.2 gives an idea of the signal's spectrum at baseband
as well as at RF.
4.1.2 Method of Insertion
The narrowband noise is created and inserted into the signal
environment by running the NBNOISE.M routine between the L1CODE.M
and RECEIVER.M routines. NBNOISE.M assumes the L1 variable is in
MATLAB's variable space, and that it contains the GPS SOI and any MA
signals that might be present. After creating either or both of the narrowband
signals, it adds them to the L1 variable such that either of the GPS receiver
simulators can start processing the signal as it normally would.
67


2400 Baud BPSK Signal
Fig 4.1. Narrowband BPSK Signal in Time Domain
68


Narrowband Signal at Baseband
Narrowband Signal at RF
Fig 4.2. Spectral Representation of the Interfering BPSK Signal
69


4.2 Wideband Noise
White noise is the only type of WB noise inserted into the signal
environment. This was particularly easy to do, since the GPS receiver
simulators add white thermal noise as their very first step. Rather than
creating a separate routine to develop and insert such noise, the level of
noise presented as thermal was increased. The result is the same.
4.3 Multipath and Spoofing
The MATLAB code, MPATH.M, used to create and insert the multipath
and spoofing interference is contained in Appendix A.5.
4.3.1 Rationale for Generalizing
The problems of multipath and spoofing are very similar. In both
cases, the receiver is forced to deal with a signal that is very nearly a
duplicate of the actual, but offset in time. In the case of multipath, the data
and PRN sequence of the false signal should be exactly the same as it is for
the actual; only the time of reception and received power level should differ.
In the case of spoofing, a case can be made that the most successful method
will also be to send a duplicate of the actual signal, differing only in time of
arrival and received power level.
There are several ways an adversary may wish to inject false signals
into someone's GPS receiver. Methods that come readily to mind include
changing a PRN code, creating a signal for a satellite that is out of view,
changing the data in the 50 baud data link for a satellite that is in view, or
70


trying to mimic the signal of a satellite that is in view. The first of these can
be readily dismissed, since the PRN sequence must still match that of a
proper Gold Code, or the receiver will never recognize it.
Using the PRN code for a satellite that is out of view in an attempt to
inject faulty data will also meet with failure. Conveniently, the data from the
50 baud data link contains the approximate position of each of the 24 SVs in
orbit. Since a receiver must be in view of at least four satellites at all times,
there will be four data streams telling the receiver that the fifth signal could
not possibly be coming from the satellite it claims to be.
The third option, that of changing the data of an in-view satellite, is a
possibility, although not a very viable one. Even most of the low-end
receivers on the market today contain logic that recognizes when a satellite
is supplying blatantly incorrect data. When this occurs, the receiver simply
disregards the signal. This is not a problem, unless it happens to be in one
of those rare circumstances when there are only four SVs in view at the time.
If the data is close enough not to cause the receiver to alarm, it is probably
close enough not to cause substantial harm to the user, unless the user is in
a highly mobile tactical warfighting situation. And if this is the case, the user
is almost certainly locked up to the military's P Code. Since the P Code is
almost always encrypted, the adversary will still not have much success in
denying use of the GPS in this manner, either.
The one method that shows promise is to mimic the signal of a
satellite that is in view. As discussed in Section 2.3.1, if a jammer can
transmit a duplicate GPS signal timed to arrive at the receiver the same time
71


as the actual signal, he might be able to get the receiver to lock to the false
signal instead of the actual one. Then, by letting the false signal's arrival
time slowly drift away from the actual signal, the jammer may be able to
introduce timing delays sufficient to create significant errors in the receiver's
calculations. Once again, if these errors are too large, the receiver's logic
will cause the signal to be ignored. But if the error is on the order of a couple
hundred meters, it may make the difference between mission success or
failure for many military applications, such as targeting with PGM's or finding
critical equipment or lost personnel on smoky battlefields or at night. And
since the jamming signal is transmitting valid PRN codes and correctly
encrypted data, this method will work against the P Code as well as the C/A
Code. Therefore, what appears to be the most successful spoofing option is
merely a special case of the multipath problem: a false signal arriving at the
receiver with all the right data, but with slightly offset timing and a variable
power level. The one key difference is that multipath signals will most
certainly arrive at the receiver with less power than the original signal. Since
the intent of the spoofer is to get the receiver to lock to his signal and drop
lock on the satellite's, it will likely arrive with greater power than the correct
signal, although not so much so that it can be easily recognized as not
coming from a satellite.
4.3.2 Description
Figure 4.3 illustrates the multipath and spoofing problem. Simply put,
a GPS signal reaches a receiver, in this case, onboard an aircraft, via two or
72


more paths. One path, 'a', is direct from the satellite; the other, 'b' and 'c', is
via a reflection off the ground plane at point R. In the case of spoofing, a
jamming transmitter is located at point R.
C
/

h
Fig 4.3. Geometry for Multipath and Spoofing Interference
With its orbital radius at 26,561.75 km, the distance 'b' from a point on
the earths surface 'R' to the GPS SV is between 20,183 km at zenith to
25,784 km at the horizon, as illustrated in Figure 4.4. The elevation angle to
the satellite, 0, and the range to the satellite, 'b', correspond in both figures.
73


zenith
Fig 4.4. Spacecraft Geometry Relative to Receiver on Earth's Surface
For an elevation angle 0 = 20, using the Law of Cosines, the range
from the reflection point to the satellite can be found to be
r2 =r£ +bz 2brE cos(0+ 90).
(4.1)
Solving for b yields
(4.2)
b = 23,695.04 km.
If the aircraft in Figure 4.3 is flying at 5,000 m, the distance from the
reflection point to the aircraft is
(4.3)
74


c=%Lne=u-619hn-
Another application of the Law of Cosines will now provide the distance, 'a',
from the aircraft to the GPS satellite:
(4.4)
a2 =b2 + c2 2bc cos(180 -20)
a = 23,706.2km
Comparing this direct path length with the reflected path length 'b' + 'c', we
find a difference of approximately 3.5 km. Taking the speed of light at
c = 300 m/psec, the multipath signal in this example should arrive at the
receiver about 11.5 psec after the direct signal.
Depending on the reflecting surface, the multipath signal could consist
of just one strong reflection from a smooth surface, such as a calm body of
water, or there could be multiple reflections from a rough surface, such as a
mountainous area with relatively smooth granite faces or mesas. A spoofing
signal would appear as a single strong reflection, assuming it does not reach
the victim receiver by more than one transmission path (i.e. there is no
multipath on the jamming signal).
Figure 4.5 shows the multipath responses for the two specific cases
that were used. The top plot shows a single reflection or spoofing signal of
comparable signal strength at approximately t = 5 psec relative to the arrival
of the original signal. The lower plot shows several smaller reflections at
various times after the original signal. In both cases, the resulting multipath
75


Relative Signal Strength Relative Signal Strength
signal is simply the original signal coming from the spacecraft convolved with
the desired multipath response.
Multipath with Single Reflection (or Spoofing)
1
0.8
0.6
0.4
0.2
0
0 5 10 15
microseconds
Multipath with Multiple Reflections
Fig 4.5. Multipath Response
4.3.3 Method of Insertion
Just as was done with the narrowband noise, the multipath noise is
created and inserted into the signal environment by running the MPATH.M
76


routine between the L1CODE.M and RECEIVER.M routines. MPATH.M
assumes the L1 variable is in MATLAB's variable space, and that it contains
the GPS SOI and any MA signals that might be present. Once the routine
has completed, it leaves the resulting L1 variable in the variable space such
that either of the GPS receiver simulators can start processing the signal as it
normally would.
77


5. Review of Adaptive Signal Processing Theory
It was hoped at the outset of this work was to try to improve the
processability of GPS signals by incorporating a technique known as
adaptive signal processing into the GPS receiver. Adaptive signal
processing techniques can be used in many applications, such as noise
cancellation, optimal signal prediction and time delay estimation. These
techniques will serve two purposes in this work. The first is essentially a time
delay estimation problem, wherein an adaptive filter is used to search for and
lock to the PRN code. The second is something like the inverse of noise
cancellation. Instead of canceling the noise afflicting GPS signals, the
adaptive filter will "teach" the receiver to look for the noisy signal. This is
more along the lines of, "If you can't beat 'em, join 'em." Successive
iterations of the adaptive signal processor should, on the average, come
closer and closer to achieving a filter that will identify the timing and content
of the noisy signal of interest.
The most common implementations of the time delay estimation
technique require as inputs both an on-time and a delayed version of the
signal of interest. Often, the delayed SOI is corrupted by some noise source.
The classic noise cancellation filter requires as inputs the SOI corrupted by
some type of noise, and another noise source that is correlated to the first.
In the case of receiving a GPS signal, the latter input is not available, so the
algorithm requires some level of modification to teach it to "live with" the
78


noise rather than cancel it. This section provides a tutorial review of the
theory and algorithms behind the standard implementations, and the next
section will cover the modifications required for the application of these
techniques to the case of a GPS receiver.
The primary source for the material in this section is notes received
during the Spring '96 offering of EE5805, Adaptive Signal Processing, taught
by Prof. Miloje Radenkovic at the University of Colorado, Denver.
5.1 Using Gradients to Minimize an Unknown Cost Function
The basic premise to adaptive signal processing is that there exists a
controllable independent variable, namely the filter coefficients, that affects
and can therefore be used to minimize an undesirable dependent variable,
namely the noise present on a SOI. The problem is that the relationship
between the two, known as the cost function, is generally unknown.
If the relationship were known, it would be a simple matter to find the
point were the cost function is a minimum, identify the filter coefficients
associated with that minimum, and use them. Since it is not, the cost
function's minimum must be found iteratively by following its gradient to the
point were the gradient is equal to zero.
For a generic cost function, y(x), the minimum can be found iteratively
using the algorithm:
(5.1)
79


where pi is the algorithm's gain factor [24]. The technique is illustrated in
Figure 5.1, which uses a simple quadratic equation for the cost function. The
process is begun at an arbitrary starting point x(0). In this example, the cost
function's gradient is positive at that point, so the algorithm chooses a next
value x(1) at some point to the left of x(0). If some future iteration results in a
point to the left of the minimum, the slope will be negative and the algorithm
will result in a following iteration to the right of the previous one. For an
appropriate choice of pi, the algorithm will produce successive iterations that
tend toward the cost function's minimum. In this case, pi = 0.9 was used.
Cost Function
Fig 5.1. Iterative Search for the Minimum of a Cost Function
80


Figure 5.2 shows the algorithm's output for the first 100 iterations of
the search for the cost function's minimum. The search approaches the true
value of 3 exponentially. The discernible oscillation at the end of the routine
is an effect of MATLAB's plotting and printing. The actual oscillation still
present at the 100th iteration is on the order of 10'9.
Fig 5.2. Minimum Search Results
The choice of |i can be critical to the success of the algorithm. Note
that the example in the figures requires 0 < n < 1. Otherwise, the algorithm is
81


unstable. For p < 0, the iterations of x will monotonically increase
exponentially, and for p > 1, the iterations will increase exponentially,
bouncing back and forth on each side of the actual minimum.
5.2 Adaptive Noise Cancellation Cost Functions and Algorithms
The cost function associated with adaptive signal processing is
generally not quite as simple as the example of Section 5.1. Figure 5.3
shows a typical adaptive noise cancellation problem [25]. In this scenario,
the desired SOI is s(n). It is corrupted by noise v(n), which is correlated to
the noise source x(n) by some unknown transfer function F(z'1), where z is
the unit delay operator.
s(n)
x(n)
Fig 5.3. Typical Adaptive Noise Cancellation Problem
The only signals available to the user are the noisy signal d(n) and the
noise source x(n). To obtain the SOI, the adaptive filter must approximate
82


the transfer function F(z-1) so that it can produce a signal similar to v(n). If it
can do that, it's output can be subtracted from the noisy signal, leaving s(n).
The difference between the noisy SOI and the adaptive filters output
is known as the error signal e(n), although it is ideally very close to the SOI,
s(n). The cost function, J, for this type of problem is basically the expected
value of the error signal:
where F is the vector of adaptive filter coefficients, and <(>(n) is the signal
vector
Note in this case, the filter is a Finite Impulse Response (FIR) filter of order L
[26].
(5.2)
J = E{e(n)2}
= E{(d(n)-y(n)Y}
(5.3)
(5.4)
(ri)T = [jt(w) x(n-\)--x(n- L + 1) x(n-L)\
83


Equation 5.2 is a valid choice for the cost function. Minimizing this
function is equivalent to minimizing
(5.5)
E{{d(ri) y(n))2} = f{([v +s]~ y)2}
= E{v2 + 2vs +s2 2vy 2sy + y2),
where the iteration index, n, has been omitted. The independent variable in
this expression is y(n), which is controlled by appropriate choice of the
adaptive filter parameters. An approximation to this cost function can be
minimized by taking the partial derivative with respect to y(n), setting the
result equal to zero, and solving for the necessary y(n):
(5.6)
f = 2vf + irf + 0-(2v + 2yf)-2i + 2y
= 2(v + s-y)f-2(v + s-y)
= 2(v + s-y)(f-l) = 0.
This results in two possible values for y(n):
84


(5.7)
v +s- y = 0
and
y = v +s
y = v+C
where C is a constant of integration.
Note that since partial derivatives were used instead of full derivatives,
C is a constant only with respect to y(n). Therefore, the left-hand solution is
nothing more than a special case of the right-hand one. Having said this, for
the case of Figure 5.3, the constant C must in fact be zero. This is because
the only signal input to the adaptive filter is x(n), which has zero mean. If the
signal is not available in some correlated form at the input (like v(n) is
available in the correlated form of x(n)), it cannot be available at the output.
And since the input to the filter has zero mean, it's output must also have
zero mean, which means C cannot be a pure non-zero constant, either.
Therefore, minimizing the cost function will result in a filter output y(n) that is
identical to the noise signal v(n), resulting in an "error signal" e(n) to be
identical to the SOI, s(n).
In reality, the user does not adjust the filter output y(n) directly.
Instead, he adjusts the filter parameters, which in turn affect y(n). Therefore,
with the case of adaptive noise cancellation, Equation 5.1 becomes [27]
85


(5.8)
= F^- Mn)(- =£,+<()[<() -&*)]
Equation 5.8 is known as the Least Mean Squares (LMS) Adaptive
Filter algorithm. Variations on this include the Normalized Gradient (NG)
algorithm and the Recursive Least Squares (RLS) algorithm. The only real
difference between the LMS and the NG is the value used for the gain. For
the LMS algorithm, the gain is simply the constant For the NG algorithm, |i
is normalized by (i.e. divided by) the sequence r(n). One such normalization
sequence is
(5.9)
r(n) = r0 + max||0(r)||2 where r0 > 0.
The RLS algorithm uses a slightly different cost function [28],
(5.10)
j.=jy 1=0
86


This results in a vanishing gain factor p(n), used instead of LMS's p. gain
factor, where p(n) is given by
(5.11)
Pin) = p{n-1)-
p{n-l)fa)fa)T p(n-l)
l+fa)Tp(n-l)fa) '
The RLS algorithm is significantly more powerful than the other two, but
requires substantially more computing power as well, since there are several
L x L matrix multiplications for each iteration.
The vanishing gain of the RLS algorithm is particularly attractive in
many noise cancellation problems, because as an algorithm progresses, the
smaller gain in the later iterations will result in the noise having less and less
effect on the output. The gain in the LMS and NG algorithms can also be
made to diminish over time by simply dividing the gain by the iteration
number. There is a significant drawback to the vanishing gain, however. If
the system F(z*1) is time varying, the adaptive filter will have difficulty in later
iterations keeping pace with the system it is trying to match. In some GPS
applications, such as with a stationary receiver, this is not significant. But in
the case of a rapidly moving aircraft or a PGM, rapidly changing receiver
geometry can result in rapidly changing multipath, which will preclude the use
of an algorithm using vanishing gain.
Just as was the case with the generic example in Section 5.1,
restrictions must be placed on the gain factors of adaptive noise cancellation
algorithms to maintain system stability [29], For LMS, the region of stability is
87