Spread Spectrum, CDMA and GPS

For radio systems there are two resources, frequency and time. Division by frequency, so that each pair of communicators is allocated part of the spectrum for all of the time, results in Frequency Division Multiple Access (FDMA). Division by time, so that each pair of communicators is allocated all (or at least a large part) of the spectrum for part of the time results in Time Division Multiple Access (TDMA). In Code Division Multiple Access (CDMA), every communicator will be allocated the entire spectrum all of the time. Multiple simultaneous transmissions are separated using coding theory. CDMA also relaxes the assumption that colliding frames are totally garbled. Instead, it assumes that multiple signals add linearly. The key to CDMA is to be able to extract the desired signal while rejecting everything else as random noise. 

 In CDMA, each bit time is subdivided into m short intervals called chips. Typically there are 64 or 128 chips per bit. Each station is assigned a a unique m-bit chip sequence. To transmit a 1 bit, a station sends its chip sequence. To transmit a 0 bit, it sends the one's complement of its chip sequence. No other patterns are permitted. Thus for m = 8, if station A is assigned the chip sequence 00011011, it sends a 1 bit by sending 00011011 and a 0 bit by sending 11100100. 

 Increasing the amount of information to be sent from b bits/sec to mb chips/sec can only be done if the bandwidth available is increased by a factor of m, making CDMA a form of spread spectrum communication (assuming no changes in the modulation or encoding techniques). In order to protect the signal, the chip sequence code used is pseudo-random. It appears random, but is actually deterministic, so that the receiver can reconstruct the code for synchronous detection. This pseudo-random code is also called pseudo-noise (PN).

 It is more easier to use a bipolar notation, with binary 0 being -1 and binary 1 being +1. We will show chip sequences in parentheses, so a 1 bit for station A now becomes (-1 -1 -1 +1 +1 -1 +1 +1). Each station has its own chip sequence. Let us use the symbol S to indicate the m-chip vector for station S and ~S for its negation.. All chip sequences are pairwise orthogonal, by which we mean that the normalized inner product of any two distinct chip sequences, S and T (written as S*T,  pronounced S dot T) is 0. In mathematical terms, 

                        S*T = 1/m [Sum over all i from 1 to m, Si*Ti] = 0

 This orthogonality property is crucial. Note that, if S*T = 0 then S*(~T) is also 0. The normalized inner product with any chip sequence with itself is 1  This is because each m terms in the inner product is 1, so the sum is m. Also note that, S*(~S) is -1.

 During each bit time, a station can transmit a 1 by sending its chip sequence, it can transmit a 0 by sending the inverse of its chip sequence, or it can be silent and transmit nothing. For the moment, we assume that all stations are synchronized in time, so all chip sequences begin at the same instant. When two or more stations transmit simultaneously, their bipolar signals gets added linearly. For example, if in one chip period, three stations transmit +1 and one station transmit -1, then the result is +2. 

A: 00011011

B: 00101110

C; 01011100

D: 01000010

A: (-1 -1 -1 +1 +1 -1 +1 +1)

B: (-1 -1 +1 -1 +1 +1 +1 -1)

C: (-1 +1 -1 +1 +1 +1 -1 -1)

D: (-1 +1 -1 -1 -1 -1 +1 -1)

1 0 1 _  A+ ~B + C S1 = (-1 +1 -3 +3 +1 -1 -1 +1)
1 1 1 1  A + B + C + D S2 = (-4 0 -2 0 +2 0 +2 -2)
S1 * B = (-1 +1 -3 +3 +1 -1 -1 +1) * (-1 -1 +1 -1 +1 +1 +1 -1) = (+1 -1 -3 -3 +1 -1 -1 -1) = -8 i.e. normalized is -1 i.e. B output = 0
S2 * B = (-4 0 -2 0 +2 0 +2 -2) * (-1 -1 +1 -1 +1 +1 +1 -1) = (+4 0 -2 0 +2 0 +2 +2) = +8 i.e. normalized is +1 i.e. B output = 1

First row shows chip sequence assignments to four stations. Second and third row shows different transmissions. Fourth and fifth row demonstrates how to get the signal of a particular station from the received signal.

 WCDMA uses Direct Sequence spreading, where spreading process is done by directly combining the baseband information to high chip rate binary code. The Spreading Factor is the ratio of the chips (UMTS = 3.84Mchips/s) to baseband information rate. Spreading factors vary from 4 to 512 in FDD UMTS.

 

CDMA is a Direct Sequence Spread Spectrum system. The CDMA system works directly on 64 kbit/sec digital signals. A simplified Direct Sequence Spread Spectrum system is illustrated in the following diagram.

Signal transmission consists of the following steps:

1. A pseudo-random code is generated, different for each channel and each successive connection.

2. The Information data modulates the pseudo-random code (the Information data is “spread”). Chip vector for 1, inverse of it for 0.

3. The resulting signal modulates a carrier.

4. The modulated carrier is amplified and broadcast.

Signal reception consists of the following steps:

1. The carrier is received and amplified.

2. The received signal is mixed with a local carrier to recover the spread digital signal.

3. A pseudo-random code is generated, matching the anticipated signal.

4. The receiver acquires the received code and phase locks its own code to it.

5. The received signal is correlated with the generated code, extracting the Information data.

 

To recover the bit stream of an individual station, the receiver must know that station's chip sequence in advance. It does the recovery by computing the normalized inner product of the received chip sequence and the chip sequence of the station whose bit stream it is trying to recover. The reason is,

S1*C = (A+ ~B + C) * C = A*B + ~B*C + C*C = 0 + 0 + 1 = 1

 In an ideal noiseless CDMA system, the capacity (no. of stations) can be made arbitrarily large. In practice, physical limitations reduce the capacity considerably. First, we have assumed that all the chips are synchronized in time. In reality, doing so is impossible. What can be done is that sender and receiver synchronize by having the sender transmit a long enough known chip sequence that the receiver can lock onto. All the other (unsynchronized) transmissions are seen as random noise. The longer the chip sequence the higher is the probability of detecting in presence of noise. For extra security, bit sequences can use error correcting codes. Chip sequences never use error correcting codes. 

Generating Chip Sequences or Pseudo-Random Codes

For each channel the base station generates a unique code that changes for every connection. The pseudo-random code must have the following properties:

1. It must be deterministic. The subscriber station must be able to independently generate the code that matches the base station code.

2. It must appear random to a listener without prior knowledge of the code (i.e. it has the statistical properties of sampled white noise).

3. The cross-correlation between any two codes must be small (see below for more information on code correlation).

4. The code must have a long period (i.e. a long time before the code repeats itself).

Code Correlation

In this context, correlation has a specific mathematical meaning. In general the correlation function has these properties:

Intermediate values indicate how much the codes have in common. The more they have in common, the harder it is for the receiver to extract the appropriate signal.

There are two correlation functions:

The receiver uses cross-correlation to separate the appropriate signal from signals meant for other receivers, and auto-correlation to reject multi-path interference.

Some terminology related to the pseudo-random code:

Transmitting Data

The resultant coded signal next modulates an RF carrier for transmission using Quadrature Phase Shift Keying (QPSK). QPSK uses four different states to encode each symbol. The four states are phase shifts of the carrier spaced 90degrees  apart. By convention, the phase shifts are 45, 135, 225, and 315 degrees. Since there are four possible states used to encode binary information, each state represents two bits. This two bit “word” is called a symbol.

Algebraically, a carrier wave with an applied phase shift, Y(t), can be expressed as a sum of two components, a Cosine wave and a Sine wave, as:

I(t) is called the real, or In-phase, component of the data, and Q(t) is called the imaginary, or Quadrature-phase, component of the data. We end up with two Binary PSK waves superimposed. These are easier to modulate and later demodulate.

This is not only an algebraic identity, but also forms the basis for the actual modulation/demodulation scheme. The transmitter generates two carrier waves of the same frequency, a sine and cosine. I(t) and Q(t) are binary, modulating each component by phase shifting it either 0 or 180 degrees. Both components are then summed together. Since I(t) and Q(t) are binary, we’ll refer to them as simply I and Q.

The receiver generates the two reference waves, and demodulates each component. It is easier to detect 180degrees  phase shifts than 90degrees  phase shifts. The following table summarizes this modulation scheme. Note that I and Q are normalized to 1.

Symbol

I

Q

Phase shift

00

+1

+1

45°

01

+1

-1

315°

10

-1

+1

135°

11

-1

-1

225°

For Digital Signal Processing, the two-bit symbols are considered to be complex numbers, I +jQ.

Working with Complex Data

In order to make full use of the efficiency of Digital Signal Processing, the conversion of the Information data into complex symbols occurs before the modulation. The system generates complex PN codes made up of 2 independent components, PNi +jPNq. To spread the Information data the system performs complex multiplication between the complex PN codes and the complex data.

 

Summing Many Channels Together

Many channels are added together and transmitted simultaneously. This addition happens digitally at the chip rate. 

At the Chip Rate

For each component (I or Q):

Since I and Q are no longer limited to 1 or -1, the phase shift of the composite carrier is not limited to the four states, the phase and amplitude vary as

A2 = I2 + Q2

Tan((Y) = Q/I

At the Symbol Rate

Since the PN-code has the statistical properties of random noise, it averages to zero over long periods of time (such as the symbol period). Therefore, fluctuations in I and Q, and hence the phase modulation of the carrier, that occur at the chip frequency, average to zero. Over the symbol period the modulation averages to one of the four states of QPSK, which determine what the symbol is.

The symbol only sees the QPSK, and obeys all the statistical properties of QPSK transmission, including Bit Error Rate.

Receiving Data

The receiver performs the following steps to extract the Information:

 

Demodulation

The receiver generates two reference waves, a Cosine wave and a Sine wave. Separately mixing each with the received carrier, the receiver extracts I(t) and Q(t). Analog to Digital converters restore the 8-bit words representing the I and Q chips.

Code Acquisition and Lock

The receiver, as described earlier, generates its own complex PN code that matches the code generated by the transmitter. However, the local code must be phase-locked to the encoded data. The base station and mobile station each have different ways of acquiring and locking onto the other’s transmitted code. Each method will be covered in more detail in later sections.

Correlation and Data Despreading

Once the PN code is phase-locked to the pilot, the received signal is sent to a correlator that multiplies it with the complex PN code, extracting the I and Q data meant for that receiver. The receiver reconstructs the Information data from the I and Q data.

Automatic Power Control

 CDMA is typically used for wireless systems with fixed base stations and many mobile stations at varying distances from it. The power level received at the base station depend on how far away the transmitters are. The receiver (base station) can listen to all senders at once by running the decoding algorithm for each of them in parallel. 

The base station gets bombarded by signals from many mobile stations. Some of these mobile stations are close and their signals are much stronger than mobile stations farther away. This results in the Near/Far problem inherent in CDMA communications. System Capacity is also dependant on signal power. For these reasons, both the base station and mobile station measure the received power and send signals to control the other’s transmit power.

Near/Far Problem

Because the cross-correlation between two PN codes is not exactly equal to zero, the system must overcome what we call the Near/Far problem.

The output of the correlator consists of two components:

Mathematically, if we are trying to decode the kth signal, we have:

Where:

Aj is the amplitude of the jth signal,
rjk is the cross-correlation between the kth and jth signal, and
S is the sum over all the j signals (excluding k).

Since the cross-correlation is small (ideally, it is zero), the sum of cross-correlation terms should be much less than the amplitude of the desired signal. However, if the desired signal is broadcast from far away, and undesired signals are broadcast from much closer, the desired signal may be so small as to be drowned out by the cross-correlation terms.

Note that this problem only exists in the reverse direction. The base station is receiving signals from many mobile stations at different distances, but the mobile station is receiving all signals from one base station. The base station controls the power of each mobile station so that the signals received from all mobile stations are the same strength.

 

Global Positioning System (GPS)

GPS is a satellite based radio navigation system. There are 24 GPS satellites orbiting the Earth and transmitting radio signals. Based on measurements of the amount of time that the radio signals travel from a satellite to a receiver, GPS receivers calculate the distance and determine the locations in terms of longitude, latitude and altitude. 

Satellite signals

GPS satellite transmissions utilize direct sequence spread spectrum (DSSS) modulation. DSSS provides the structure for the transmission of ranging signal and essential navigation data such as satellite co-ordinates and health. The ranging signal are pseudo random noise (PRN) codes that binary phase shift key (BPSK) modulate the satellite carrier frequencies. 

 Each GPS satellite broadcasts two types of PRN ranging codes:

There is a basic frequency f0 = 10.23 Mhz. The satellite transmits at two different frequencies: L1 = 154f0 and L2 = 120f0

Chipping rate:

The C/A code has 1-msec period and repeats constantly, whereas the P-code satellite transmission is 7-day sequence that repeats every midnight Saturday/Sunday. 

There are Standard Positioning Service (SPS) and Precision Positioning Service (PPS). P-code can be denied to SPS users if the anti-spoofing code is activated in the satellite vehicle. In that case, P-code is encrypted and known as Y-code. Y-code has same chipping rate as P-code.

 

GPS Satellite Signal Characteristics

GPS satellites transmit two carrier frequencies: the primary frequency L1 and the secondary frequency L2.Satellites transmit at two frequencies simultaneously, but, their signals do not interfere significantly with each other due to PRN code code modulation. Since each satellite is assigned a unique PRN code and all of the PRN code sequences are nearly uncorrelated with respect to each other, the satellite signals can be separated and detected by CDMA technique. 

 In order to track one satellite in common view with several other satellites by the CDMA technique, a GPS receiver must replicate the PRN sequence for the desired satellite along with the replica carrier signal. Two carrier frequencies are provided to permit the two frequency user to measure the ionospheric delay since this delay is related by a scale factor to the difference in signal time of arrival (TOA) for the tow carrier frequencies. Single frequency (L1) users must estimate the ionospheric delay using modeling parameters that are broadcast to the user in navigation message. 

 50 bytes/sec Navigation message Data is combined with both the C/A-code and P(Y)-code prior to modulation with the L1 carrier. This combination uses the XOR process. Since C/A-code XOR Data and P(Y)-code XOR Data is synchronous operation, the bit transition rate cannot exceed the chipping rate of the PRN codes. The P(Y)-code XOR Data is modulated in-phase quadrature with the C/A-code XOR Data. There fore there 90 degrees phase shift between these two combined carrier frequencies.

 The L2 frequency can be modulated by either P(Y)-code XOR Data or C/A-code XOR Data or with P(Y)-code alone as selected by the control segment. P(Y)-code and C/A-codes are never present simultaneously on L2, as is the case with L1. In general, P(Y)-code XOR Data is the one selected by the control segment. 

 The PPS user has access to all signals on L1 and L2 and to the full accuracy of GPS. PPS users have classified algorithms and the classifies key to remove certain errors. However, differential GPS techniques have successfully mitigated these effects.

 

GPS signal acquisition and tracking

At each phase of operation, the system (satellite) broadcasts pilot signals. These pilot signals are the unmodulated PN codes associated with each channel, used to synchronize and track the locally generated PN codes for despreading. Global Pilot: Broadcast by the RCS. All FSUs use the Global Pilot for all received channels.

 At the receivers, the PRN code is derived by combination of two code generators. Code generators are nothing but linear feedback shift registers. After derivation, the receiver must shift the phase of the replica code until it correlates with the satellite PRN code. The same correlation properties occur when cross correlating the transmitted PRN code with a replica code as occurs for the mathematical autocorrelation process for a given PRN code. When the phase of the GPS receiver replica code matches the phase of the incoming satellite code, there is maximum correlation. When the phase of the replica code is offset by more than one chip on either side of the incoming satellite code, there is minimum correlation. This is indeed the manner in which a GPS receiver detects the satellite signal when acquiring or tracking the satellite signal in code-phase dimension. It is important to understand that the GPS receiver must also detect the satellite in carrier phase dimension by replicating the carrier frequency (plus Doppler). Thus, the GPS signal acquisition and tracking process is a two-dimensional (code and carrier) signal replication process.

 

 

 

References:

  1. Andrew S. Tanenbaum Computer Networks, 3rd Edition. Prentice Hall.
  2. http://www.bee.net/mhendry/vrml/library/cdma/cdma.htm
  3. http://www.umtsworld.com/technology/spreading.htm
  4. Understanding GPS : principles and applications. Elliott D. Kaplan, editor. Boston : Artech House, 1996.