Modulation Methods/Spreading Sequences for CDMA

1. Modulation Methods
2. Multiple Access Methods
3. Spreading Sequences for CDMA

• Previous page
• Next page

• Previous page
• Next page

Properties of the correlation functions

Important evaluation criteria for spread sequences are the correlation functions.

$\text{Definition:}$  Considering two ergodic processes with model functions  $x(t)$  and  $y(t)$, the following applies to the  cross-correlation function  $\rm (CCF)$  of the processes:

$$\varphi_{xy}(\tau)=\overline{x(t)\cdot y(t+\tau)}=\lim_{T_{\rm M}\to\infty}\,\frac{1}{T_{\rm M} }\cdot\int^{T_{\rm M}/{\rm 2} }_{-T_{\rm M}/{\rm 2} }x(t)\cdot y(t+\tau)\,\,\rm d \it t.$$

The line crossing over indicates a  time averaging.

$φ_{xy}(τ)$  is a quantitative measure of the linear statistical dependence of the instantaneous values of sample functions  $x(t)$  and  $y(t + τ)$  of the two random processes, and thus serves to describe the statistical relationship between them.  It holds:

• If  $x(t)$  and  $y(t)$  are uncorrelated, then  $φ_{xy}(τ) \equiv 0$  $($i.e., for all arbitrary values of  $τ)$.
• In general,  $φ_{xy}(τ)$  is not symmetric, but the CCF maximum may well occur at  $τ_{\rm max} ≠ 0$. 
• Then the maximum correlation results from a mutual shift of the two considered signals by the time  $τ_{\rm max}$.

$\text{Definition:}$  If we set  $y(t) = x(t)$ in the above equation, we arrive at the  auto-correlation function  $\rm (ACF)$

$$ \varphi_{xx}(\tau)=\overline{x(t)\cdot x(t+\tau)}=\lim_{T_{\rm M}\to\infty}\,\frac{1}{T_{\rm M} }\cdot\int^{T_{\rm M}/{\rm 2} }_{-T_{\rm M}/{\rm 2} }x(t)\cdot x(t+\tau)\,\,\rm d \it t$$

with the following properties:

• The ACF is a measure of the internal statistical bonds of a stationary and ergodic process defined by the sample function  $x(t)$. 
• If  $x(t)$  is real, then  $φ_{xx}(τ)$  is a real even function:   $φ_{xx}(–τ) = φ_{xx}(τ)$.  Phase relations are thus lost in the ACF.
• If  $x(t)$  describes a complex process, then the ACF is also complex.
• The maximum value of the ACF is at  $τ =0$.  It is always  $\vert φ_{xx}(τ)\vert ≤ φ_{xx}(τ = 0),$ where  $φ_{xx}(τ =0)$  indicates the signal power  $P_x = {\rm E}\big[x^2(t)\big]$. 
• The DC component of  $x(t)$  can be determined from the limit value for  $(τ → ∞)$  as long as  $x(t)$  does not contain any periodic components:

$$\overline{ x(t)} = {\rm E}\big[x(t)\big] = \sqrt{\lim_{\tau\to\infty}\,\varphi_{xx} (\tau)} \hspace{0.05cm}.$$

The auto-correlation function and cross-correlation function describe the internal bonds and the mutual statistical dependencies in the time domain.  The corresponding description functions in the frequency domain are

• the  power density spectrum  ${\it Φ}_{xx}(f)$, as well as
• the  cross power density spectrum  ${\it Φ}_{xy}(f)$.

For ergodic processes, these are obtained as the  Fourier transforms  of ACF and CCF:

$${\it \Phi}_{xx}(f) \hspace{0.2cm} \bullet\!\!-\!\!\!-\!\!\!-\!\!\circ\, \hspace{0.2cm}\varphi_{xx}(\tau)\hspace{0.05cm} ,\hspace{0.3cm} {\it \Phi}_{xy}(f) \hspace{0.2cm} \bullet\!\!-\!\!\!-\!\!\!-\!\!\circ\, \hspace{0.2cm}\varphi_{xy}(\tau)\hspace{0.05cm}.$$

Note:   In the following, as in the book Theory of Stochastic Signals, we write simplifying for the ACF  $φ_x(τ)$  instead of  $φ_{xx}(τ)$  and for the PDS  ${\it Φ}_x(f)$  instead of  ${\it Φ}_{xx}(f)$.

Periodic ACF and CCF

For periodic signals, the boundary transition can be omitted from the ACF and the CCF calculations, and the period duration  $T_0$  (which must be the same for both signals) is used to obtain:

$$\begin{align*}\varphi_{x}(\tau) & = \frac{1}{T_{\rm 0}}\cdot\int^{T_0}_{0}x(t)\cdot x(t+\tau)\,\,\rm d \it t\hspace{0.05cm} ,\\ \varphi_{xy}(\tau) & = \frac{1}{T_{\rm 0}}\cdot\int^{T_0}_{0}x(t)\cdot y(t+\tau)\,\,\rm d \it t\hspace{0.05cm}.\end{align*}$$

In this case, the ACF is also a periodic function, and it is called the  periodic auto-correlation function  $\rm (PACF)$. This shows the following:

$$\varphi_{x}(\pm T_0) = \varphi_{x}(\pm 2T_0) =\text{ ...} = \varphi_{x}(0) \hspace{0.05cm}.$$

We now apply the above calculation rule to the spreading signal

$$ c(t) = \sum\limits^{+\infty}_{\nu = -\infty}c_\nu\cdot g_c(t - \nu \cdot T_c)$$

assuming a rectangular pulse  $g_c(t)$  of width  $T_c$ ;  $T_c$  is called the  "chip duration".

Considering the periodicity  $(T_0 = P · T_c)$  of the amplitude coefficients  $c_ν ∈ \{±1\}$, the discrete ACF values at multiples $($parameter $λ)$  of  $T_c$ are obtained:

$$\varphi_{c}(\lambda \cdot T_c) = \frac{1}{P}\cdot\sum\limits^{P-1}_{\nu = 0} c_\nu \cdot c_{\nu+ {\it \lambda} }\hspace{0.05cm}.$$

• The maximum PACF value is obtained for  $λ = 0$  and for multiples of the period length  $P$.
• Due to the rectangular pulse  $g_c(t)$,  Due to the rectangular pulse  $λ · T_c$  and  $(λ + 1) · T_c$  is always linear.
• Accordingly, the  periodic cross-correlation function  $\rm (PCCF)$  between two spreading sequences  $〈c_ν〉$  and  $〈c\hspace{0.04cm}'_ν〉$  of equal period length  $P$  is given as follows:

$$\varphi_{cc\hspace{0.04cm}'}(\lambda \cdot T_c) = \frac{1}{P}\cdot\sum\limits^{P-1}_{\nu = 0} c_\nu \cdot c\hspace{0.04cm}'_{\nu+ \lambda }\hspace{0.05cm}.$$

Evaluation criteria for PN spread sequences

The quality of a CDMA system based on PN modulation depends significantly on the PACF and PCCF properties of the spreading sequences used.  In summary:

• The PACF of the spreading code class used should be characterized by a pronounced peak at  ${\it λ} = 0$,  if possible, in order to make synchronization at the receiver easy.  Moreover, for multipath reception with an echo of delay difference  $λ · T_c$,  the smaller  $|φ_c(λ · T_c)|$  is, the smaller is the degradation due to impulse interference.
• The interfering influence of interfering CDMA subscribers can be estimated by the PCCF value  $φ_{cc\hspace{0.04cm}'} (λ = 0)$.   If this is equal to zero, one speaks of   orthogonal functions.  The error probability is not increased in this case.  If all spreading sequences are orthogonal, then even if there are  $J$  participants, the error probability is the same as if there were only one user.
• This last statement is of particular importance in synchronous systems with distortion-free channel  (for example, in AWGN).   On the other hand, in asynchronous operation or multipath reception,  de-orthogonalization  occurs and the stricter requirement that the PCCF between each sequence should take on the smallest possible values (in terms of magnitude) at all times.

When selecting code families for a CDMA system, care must also be taken to ensure that as many code sequences as possible with favorable properties with respect to these three criteria can be found for a given spreading factor  $J = P$,  so that as many subscribers as possible can be supplied simultaneously in the same frequency band.

Pseudo-noise sequences of maximum length

PN generator (realization with shift registers)

A feedback shift register can be used to generate a sequence with favorable ACF properties if the feedback coefficients  $g_i$  with index  $i = 1, \text{...} \ , G-1$  are chosen appropriately.  

• The sequence  $〈c_ν〉$  is not random in the strict sense, but periodic.  
• However, due to the large period length  $P$  it appears stochastic to an uninitiated observer. 
• One speaks of a  pseudo–noise sequence  or  PN sequence for short.

$\text{PN generators}$  have the following properties, see chapter  Generation of Discrete Random Variables  in the book "Theory of Stochastic Signals":

Polynomials of M-sequences with degree  $G$

• The binary values  $c_{ν-1}, \text{...} \ , c_{ν-G}$  generated at earlier times are stored in the  $G$  memory cells of the shift register.  We refer to  $G$  as the degree of the shift register.

• The coefficients  $g_1, \ \text{...} \ , g_{G-1}$  are binary values, where a "1" indicates a feedback at the corresponding location of the shift register and a "0" indicates no feedback.

• For the currently generated symbol, with  $g_i ∈ \{0, 1\}$ and $i = 1,\ \text{...}\ , G-1$:

$$c_\nu = (g_1\cdot c_{\nu-1}+g_2\cdot c_{\nu-2}+\ \text{...}\ +g_i\cdot c_{\nu-i}+\ \text{...}\ +g_{G-1}\cdot c_{\nu-G+1}+ c_{\nu-G})\hspace{0.1cm} \rm mod \hspace{0.2cm}2.$$

• The modulo-2 addition can be realized for example by an  $\rm XOR$ operation:

$$(x + y)\hspace{0.2cm} \rm mod\hspace{0.2cm}2 = {\it x}\hspace{0.2cm}\rm XOR\hspace{0.2cm} {\it y} = \left\{ \begin{array}{*{2}{c}} 0 & \rm if\hspace{0.1cm} {\it x}= {\it y},\\ 1 & \rm if\hspace{0.1cm} {\it x}\neq {\it y}. \\ \end{array} \right.$$

• If not all  $G$  memory cells are preallocated with zeros, the result is a periodic random sequence  $〈c_ν〉$.  The period length  $P$  of this sequence depends strongly on the feedback coefficients  $g_i$. 
• For each degree  $G$  there are at least two configurations with the maximum period  $P_{\rm max} = 2^G – 1$ for this.

In the table above, for some values of  $G$,  the generator polynomial  $G(D)$  of such an M-sequence and the corresponding (maximum) period length  $P$  are given, where the "M" stands for "Maximum".  In the following the statements made here are clarified at the example  $G = 4$. 

$\text{Example 1:}$  The diagram shows two possible arrangements for generating a PN sequence of maximum length for  $G = 4$   ⇒   $P = 15$.

PN generators of degree  $G = 4$

• The  octal representation  of the binary number  $(g_G, \ \text{...} \ ,g_2, g_1, g_0)$  is usually chosen as the abbreviation.  Basically  $g_0 = g_G = 1$  is to be set.

• The left configuration is denoted by  $\rm (11001)_{binary} = (31)_{octal}$,  the corresponding generator polynomial is:

$$G(D) = D^4 + D^3 +1\hspace{0.05cm}.$$

• The right configuration with  $\rm (10011)_{binary} = (23)_{octal}$,  on the other hand, can be described by the polynomial  $G(D)$  reciprocal to  $G_{\rm R}(D)$ :

$$G_{\rm R}(D) = D^4 \cdot (D^{-4} + D^{-3} +1) =D^4 + D +1 \hspace{0.05cm}.$$

Since both  $G(D)$  and  $G_{\rm R}(D)$  are primitive generator polynomials   (the proof for this is not easy), both output sequences have the maximum period length  $P = 15$  for  $G = 4$. As shown in  Exercise 5.3,  the PACF in the unipolar representation   ⇒   $c_ν ∈ \{0, 1\}$ results in

PACF of a PN sequence of maximum length  $P = 2^G – 1$

$${\it \varphi}_{c{\rm ,\hspace{0.05cm}unipolar} }(\lambda \cdot T_c) = \left\{ \begin{array}{c}(P+1)/(2P) \\ (P+1)/(4P) \\ \end{array} \right. \begin{array}{*{10}c} {\rm{for} } \\ {\rm{otherwise} } \hspace{0.05cm}. \\ \end{array}\begin{array}{*{20}c} \lambda = 0, \pm P, \pm 2P, \text{...} \hspace{0.05cm} \\ \\ \end{array}$$

After conversion to bipolar coefficients  $($that is:  $0 \ ⇒ +1$,     $1 \ ⇒ -1)$,  we obtain:

$${\it \varphi}_{c{\rm ,\hspace{0.05cm}bipolar} }(\lambda \cdot T_c) = \left\{ \begin{array}{c}1 \\ -P \\ \end{array} \right. \begin{array}{*{10}c} {\rm{for} } \\ {\rm{otherwise.} } \hspace{0.05cm} \\ \end{array}\begin{array}{*{20}c} \lambda = 0, \pm P, \pm 2P, \text{...} \hspace{0.05cm} \\ \\ \end{array}$$

• One can see from the bottom diagram the desired distinct PACF peaks at intervals of periode  $P$.
• The cross-correlation properties of the PN sequences are less good, as will be shown in the chapter  Error Probability of Direct-Sequence Spread Spectrum Modulation. 

Code families with M-sequences

In CDMA, a specific spreading sequence of the same period length is required for each subscriber. A code family is defined as a set (as large as possible) of spreading sequences of the same period length  $P$, each valid for a register level  $G$.

The table shows that the number of PN sequences of maximum length is very small. For the degree  $G = 5$   ⇒   $P = 31$,  for example, there are just six M-sequences, namely the PN generators with the octal identifiers  $(45), (51), (57), (67), (73)$  and  $(75)$.

M-sequence code family power

Furthermore, the term power of the code family can also be found in the literature.

• This quantity indicates how many M-sequences and thus simultaneous CDMA subscribers are possible if it is required that all code pairs have "favorable PCCF properties".
• For reasons of space, it cannot be explicitly stated here what exactly is meant by "favorable". For this, we refer to the original literature, for example [ZP85].

The last row in the above table makes it clear that the power of M-sequence code families is extremely limited, even if  $G$  is large and thus the period length  $P$ is large. If  $G$  is a multiple of $4$   ⇒   $P = 15$, $P = 255$, $P = 4095$ etc., there are essentially no favorable pairs.

Gold Codes

To obtain larger code families than with M-sequences, the requirements for the periodic cross-correlation function  $\rm (PCCF)$  must be weakened.  With this restriction, code families with a much greater power are obtained, so that more CDMA subscribers can also be supplied.

Gold code generator  $(51, \ 75)$  of degree  $G = 5$

Gold codes use this principle.  The rule for generating a  Gold code family  $\rm (GCF)$  is where a  „+”  denotes a modulo-2 addition:

$${\rm GCF}(C_1, C_2) = \{ C_1, C_2, C_1 + C_2, C_1 + D \cdot C_2, C_1 + D^2 \cdot C_2, \ \text{...} \ , C_1 + D^{P-1} \cdot C_2 \} \hspace{0.05cm}.$$

The principle is illustrated in the diagram by an example:

• The sequences  $C_1$  and  $C_2$  are a convenient pair of M-sequences of the same period length, for example, the PN generators with the octal identifiers  $(51)$  and  $(75)$  of degree  $G = 5$  and thus the period length  $P = 31$.
• The Gold code family consists, on the one hand, of the M-sequences  $C_1$  and  $C_2$  and of some modulo-2 additions of these sequences.   $C_1$  is used with a fixed phase  (characterized by the preallocation of all memory cells with ones),  while all  $P$  possible initial phases are permissible for the sequence  $C_2$    (all preallocations except the zero allocation).
• If such a code family is used for CDMA, a total of  $K_{\rm GCF} = P + 2 = 2^G + 1$  sequences are available.  However, the PACF of these sequences is now no longer bivalent like the two PN sequences   $(+1$  and  $-1/31)$, but quadrivalent  $(+1$,  $+7/31$,  $-1/31$,  $-9/31)$.  The phase of  $C_2$  changes the specific progression, but not the possible PACF values.

Gold codes are used for scrambling in UMTS, for example, as explained in the chapter  Spreading codes and scrambling in UMTS  in the book "Examples of Communication Systems".

• The two master code shift registers are each constructed with  $G = 18$  memory cells.
• This results in the period length  $P = 262\hspace{0.05cm} 143$.

Walsh functions

Spreading sequences with very favorable PCCF properties are the so-called  Walsh functions, whose construction is based on the  Hadamard matrix  and can be performed in a simple way by recursion.  Starting from the matrix  $\mathbf H_2$,  further Hadamard matrices  $\mathbf H_{2J}$  can be generated as follows:

Walsh spreading sequences  $(J = 8)$  and Hadamard matrix  $\mathbf H_8$ 

$${\mathbf{H}_{2}} = \left[ \begin{array}{ccc} +1 & +1 \\ +1 & -1 \end{array} \right] \hspace{0.5cm} \Rightarrow \hspace{0.5cm}{\mathbf{H}_{2J}} = \left[ \begin{array}{ccc} \mathbf{H}_J & \mathbf{H}_J \\ \mathbf{H}_J & -\mathbf{H}_J \end{array} \right] $$

$$\hspace{0.5cm} \Rightarrow \hspace{0.5cm} {\mathbf{H}_{4}} = \left[ \begin{array}{cccc} +1 & +1 & +1 & +1 \\ +1 & -1 & +1 & -1 \\ +1 & +1 & -1 & -1 \\+1 & -1 & -1 & +1 \end{array} \right] .$$

The  $J$  rows of such a matrix describe the  $J$  possible spreading sequences  $($each of length  $J)$, which are numbered  $w_0(t)$  to  $w_{J–1}(t)$. 

The diagram shows the Hadamard matrix  $\mathbf H_8$  (right) and the spreading sequences that can be constructed with it,  $J -1$. 

• $J - 1$ because the unspread sequence  $w_0(t)$  is usually not used.
• Please note the color allocation between the rows of the Hadamard matrix and the spreading sequence  $w_j(t)$  in the graphic. The matrix  $\mathbf H_4$  is highlighted in yellow.
• The animation  Generating Walsh functions  shows the construction algorithm of such sequences.

Further applies:

1.  If one takes any two lines and forms the correlation  (averaging over the products), the PCCF value always results in zero.  Thus, Walsh functions for a distortion-free channel and a synchronous CDMA system are optimal spreading sequences due to their orthogonality.
2.  In contrast, for asynchronous operation  (example: uplink of a mobile radio system)  or de-orthogonalization due to multipath propagation, Walsh functions alone are not necessarily suitable for band spreading - see  Exercise 5.4.
3.  Regarding PACF  (periodic ACF),  these consequences are less good:   each single Walsh function has a different PACF and each single PACF is less favorable than for a comparable PN sequence.  This means:   Synchronization is more difficult with Walsh functions than with PN sequences.

Codes with variable spreading factor (OVSF codes)

The 3G mobile communications system UMTS  provides various data rates.  For this purpose

• spreading sequences with different spreading factors  $J = 4$  to  $J = 512$  are required,
• which must all be orthogonal to each other.

Tree diagram for generating an OVSF code

Die so genannten  OVSF codes  (Orthogonal Variable Spreading Factor)  können mit Hilfe eines Codebaumes erstellt werden.  Dabei entstehen bei jeder Verzweigung aus einem Code  $C$  zwei neue Codes  $(+C \ +\hspace{-0.05cm}C)$  und  $(+C \ -\hspace{-0.05cm}C)$, wie in der Grafik oben rechts angedeutet ist.

Anzumerken ist, dass kein Vorgänger und Nachfolger eines Codes von anderen Teilnehmern benutzt werden darf.  Im Beispiel könnte demnach unter Anderem folgende Auswahl getroffen werden:

• acht Codes mit dem Spreizfaktor  $J = 8$, oder
• die vier hinterlegten Codes – einmal mit  $J = 2$, einmal mit  $J = 4$  und zweimal mit  $J = 8$.

Im zweiten Fall können die weiteren sechs Codes mit  $J = 8$  nicht verwendet werden, da sie entweder mit  „$+1 \ +\hspace{-0.05cm}1$”  oder mit  „$+1 \ -\hspace{-0.05cm}1 \ +\hspace{-0.05cm}1 \ -\hspace{-0.05cm}1$”  beginnen.

Aus den vier zugehörigen Spreizfolgen in der Grafik rechts unten erkennt man, dass bei konstanter Chipdauer  $T_c$  der Nutzer mit dem Spreizfaktor  $J = 2$  mit höherer Datenrate übertragen kann als die Teilnehmer mit  $J = 4$  bzw.  $J = 8$, da seine Bitdauer  $T_{\rm B}$  kleiner ist.

Aus der Grafik erkennt man weiter, dass die periodische KKF an der Stelle  $τ = 0$  stets Null ist.

• Das heißt:   Bildet man das Produkt von zwei beliebigen dieser Folgen und integriert man über den dargestellten Zeitbereich, so ergibt sich stets der Wert $0$.
• Das bedeutet auch:   Ein OVSF–Code ist orthogonal zu allen anderen OVSF–Codes der gleichen Familie, solange es nicht zu Verschiebungen kommt.

Note:   Die Animation  OVSF–Codes  zeigt den Konstruktionsalgorithmus dieser Codes und die zulässige Auswahl der Spreizfolgen.

Exercises for the chapter

Exercise 5.3: PAKF von PN–Sequenzen

Exercise 5.3Z: Realisierung einer PN–Sequenz

Exercise 5.4:   Walsh–Funktionen (PKKF, PAKF)

Additional exercise 5.4Z:   OVSF–Codes