Difference between revisions of "Modulation Methods/Spreading Sequences for CDMA"

From LNTwww
m
(34 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
   
 
   
 
{{Header
 
{{Header
|Untermenü=Vielfachzugriffsverfahren
+
|Untermenü=Multiple Access Methods
|Vorherige Seite=PN–Modulation
+
|Vorherige Seite=Direct-Sequence Spread Spectrum Modulation
|Nächste Seite=Fehlerwahrscheinlichkeit der PN–Modulation
+
|Nächste Seite=Error Probability of Direct-Sequence Spread Spectrum Modulation
 
}}
 
}}
==Eigenschaften der Korrelationsfunktionen==
+
==Properties of the correlation functions==
 
<br>
 
<br>
Wichtige Beurteilungskriterien für Spreizfolgen sind die Korrelationsfunktionen.  
+
Important evaluation criteria for spreading sequences are the correlation functions.
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp; Betrachtet man zwei ergodische Prozesse mit den Musterfunktionen &nbsp;$x(t)$&nbsp; und &nbsp;$y(t)$, so gilt für die &nbsp;[[Stochastische_Signaltheorie/Kreuzkorrelationsfunktion_und_Kreuzleistungsdichte#Definition_der_Kreuzkorrelationsfunktion|'''Kreuzkorrelationsfunktion''']]&nbsp; $\rm (KKF)$&nbsp; der Prozesse:  
+
$\text{Definition:}$&nbsp; Considering two ergodic processes with model functions &nbsp;$x(t)$&nbsp; and &nbsp;$y(t)$,&nbsp; the following applies to their &nbsp;[[Theory_of_Stochastic_Signals/Kreuzkorrelationsfunktion_und_Kreuzleistungsdichte#Definition_der_Kreuzkorrelationsfunktion|'''cross-correlation function''']]&nbsp; $\rm (CCF)$:
 
:$$\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.$$
 
:$$\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.$$
Die überstreichende Linie kennzeichnet hierbei eine &nbsp;''Zeitmittelung.''}}  
+
The line crossing over indicates a &nbsp;"time averaging."}}  
  
  
$φ_{xy}(τ)$&nbsp; ist ein quantitatives Maß für die lineare statistische Abhängigkeit der Augenblickswerte von Musterfunktionen &nbsp;$x(t)$&nbsp; und &nbsp;$y(t + τ)$&nbsp; der beiden Zufallsprozesse und dient somit der Beschreibung der statistischen Verwandtschaft zwischen diesen.&nbsp; Es gilt:  
+
$φ_{xy}(τ)$&nbsp; is a quantitative measure of the linear statistical dependence of the instantaneous values of model functions &nbsp;$x(t)$&nbsp; and &nbsp;$y(t + τ)$&nbsp; of the two random processes, and thus serves to describe the statistical relationship between them.&nbsp; It holds:
*Sind &nbsp;$x(t)$&nbsp; und &nbsp;$y(t)$&nbsp; unkorreliert, so ist &nbsp;$φ_{xy}(τ) \equiv 0$&nbsp; $($also für alle beliebigen Werte von &nbsp;$τ)$.  
+
*If &nbsp;$x(t)$&nbsp; and &nbsp;$y(t)$&nbsp; are uncorrelated,&nbsp; then &nbsp;$φ_{xy}(τ) \equiv 0$&nbsp; $($i.e.,&nbsp; for all arbitrary values of &nbsp;$τ)$.  
*Im allgemeinen ist &nbsp;$φ_{xy}(τ)$&nbsp; nicht symmetrisch, sondern das KKF–Maximum kann auch durchaus bei  &nbsp;$τ_{\rm max} ≠ 0$&nbsp; auftreten.
+
*In general, &nbsp;$φ_{xy}(τ)$&nbsp; is not symmetric,&nbsp; but the CCF maximum may well occur at &nbsp;$τ_{\rm max} ≠ 0$.&nbsp;  
*Dann ergibt sich die maximale Korrelation durch eine gegenseitige Verschiebung der beiden betrachteten Signale um die Zeit &nbsp;$τ_{\rm max}$.  
+
*Then the maximum correlation results from a mutual shift of the two considered signals by the time &nbsp;$τ_{\rm max}$.  
  
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
 
$\text{Definition:}$&nbsp;  
 
$\text{Definition:}$&nbsp;  
Setzt man in obiger Gleichung &nbsp;$y(t) = x(t)$, so kommt man zur &nbsp;[[Stochastische_Signaltheorie/Autokorrelationsfunktion_(AKF)|'''Autokorrelationsfunktion''']]&nbsp; $\rm (AKF)$  
+
If we set &nbsp;$y(t) = x(t)$ in the above equation,&nbsp; we arrive at the &nbsp;[[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)|'''auto-correlation function''']]&nbsp; $\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$$
 
:$$ \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$$
mit folgenden Eigenschaften:  
+
with the following properties:
*Die AKF ist ein Maß für die inneren statistischen Bindungen eines durch die Musterfunktion &nbsp;$x(t)$&nbsp; festgelegten stationären und ergodischen Prozesses.
+
*The ACF is a measure of the internal statistical bindings of a stationary and ergodic process defined by the model function &nbsp;$x(t)$.&nbsp;  
*Ist &nbsp;$x(t)$&nbsp; reell, so ist &nbsp;$φ_{xx}(τ)$&nbsp; eine reelle gerade Funktion: &nbsp; $φ_{xx}(–τ) = φ_{xx}(τ)$.&nbsp; Phasenbeziehungen gehen also in der AKF verloren.  
+
*If &nbsp;$x(t)$&nbsp; is real,&nbsp; then &nbsp;$φ_{xx}(τ)$&nbsp; is a real even function: &nbsp; $φ_{xx}(–τ) = φ_{xx}(τ)$.&nbsp; Phase relations are thus lost in the ACF.  
*Beschreibt &nbsp;$x(t)$&nbsp; einen komplexen Prozesse, so ist auch die AKF komplex.  
+
*If &nbsp;$x(t)$&nbsp; describes a complex process,&nbsp; then the ACF is also complex.
*Der Maximalwert der AKF liegt bei &nbsp;$τ =0$.&nbsp; Es gilt stets &nbsp;$\vert φ_{xx}(τ)\vert ≤ φ_{xx}(τ = 0),$ wobei &nbsp;$φ_{xx}(τ =0)$&nbsp; die Signalleistung &nbsp;$P_x = {\rm E}\big[x^2(t)\big]$&nbsp; angibt.
+
*The maximum value of the ACF is at &nbsp;$τ =0$.&nbsp; It is always &nbsp;$\vert φ_{xx}(τ)\vert ≤ φ_{xx}(τ = 0)$,&nbsp; where &nbsp;$φ_{xx}(τ =0)$&nbsp; indicates the signal power &nbsp;$P_x = {\rm E}\big[x^2(t)\big]$.&nbsp;
*Der Gleichanteil von &nbsp;$x(t)$&nbsp; kann aus dem Grenzwert für  &nbsp;$(τ → ∞)$&nbsp; ermittelt werden, so lange &nbsp;$x(t)$&nbsp; keine periodischen Anteile beinhaltet:  
+
*The DC component of &nbsp;$x(t)$&nbsp; can be determined from the limit value for &nbsp;$(τ → ∞)$&nbsp; as long as &nbsp;$x(t)$&nbsp; 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}.$$}}
 
:$$\overline{ x(t)} =  {\rm E}\big[x(t)\big] = \sqrt{\lim_{\tau\to\infty}\,\varphi_{xx} (\tau)} \hspace{0.05cm}.$$}}
  
  
Autokorrelationsfunktion und Kreuzkorrelationsfunktion beschreiben die inneren Bindungen bzw. die gegenseitigen statistischen Abhängigkeiten im Zeitbereich.&nbsp; Die entsprechenden Beschreibungsfunktionen im Frequenzbereich sind
+
The auto-correlation function and cross-correlation function describe the internal bindings and the mutual statistical dependencies in the time domain.&nbsp; The corresponding description functions in the frequency domain are
*das &nbsp;[[Stochastische_Signaltheorie/Leistungsdichtespektrum_(LDS)|Leistungsdichtespektrum]]&nbsp; ${\it Φ}_{xx}(f)$, sowie
+
*the &nbsp;[[Theory_of_Stochastic_Signals/Leistungsdichtespektrum_(LDS)|power-spectral density]]&nbsp; ${\it Φ}_{xx}(f)$, as well as
*das &nbsp;[[Stochastische_Signaltheorie/Kreuzkorrelationsfunktion_und_Kreuzleistungsdichte#Kreuzleistungsdichtespektrum|Kreuzleistungsdichtespektrum]] &nbsp;${\it Φ}_{xy}(f)$.  
+
*the &nbsp;[[Theory_of_Stochastic_Signals/Kreuzkorrelationsfunktion_und_Kreuzleistungsdichte#Kreuzleistungsdichtespektrum|cross power-spectral density]] &nbsp;${\it Φ}_{xy}(f)$.  
  
  
Bei ergodischen Prozessen ergeben sich diese als die &nbsp;[[Signaldarstellung/Fouriertransformation_und_-rücktransformation#Fouriertransformation|Fouriertransformierten]]&nbsp; von AKF und KKF:
+
For ergodic processes,&nbsp; these are obtained as the &nbsp;[[Signal_Representation/Fourier_Transform_and_Its_Inverse#Fouriertransformation|Fourier transforms]]&nbsp; 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}.$$
 
:$${\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}.$$
  
  
''Hinweis:'' &nbsp; Im Folgenden schreiben wir wie im Buch [[Stochastische Signaltheorie]] vereinfachend für die AKF &nbsp;$φ_x(τ)$&nbsp; anstelle von &nbsp;$φ_{xx}(τ)$&nbsp; und für das LDS &nbsp;${\it Φ}_x(f)$&nbsp; statt &nbsp;${\it Φ}_{xx}(f)$.  
+
'''Note:''' &nbsp; In the following,&nbsp; as in the book [[Theory of Stochastic Signals]],&nbsp; we write simplifying for the ACF &nbsp;$φ_x(τ)$&nbsp; instead of &nbsp;$φ_{xx}(τ)$&nbsp; and for the PSD &nbsp;${\it Φ}_x(f)$&nbsp; instead of &nbsp;${\it Φ}_{xx}(f)$.  
  
==Periodische AKF und KKF==
+
==Periodic ACF and CCF==
 
<br>
 
<br>
Bei periodischen Signalen kann auf den Grenzübergang bei der AKF– und der KKF–Berechnung verzichtet werden, und man erhält mit der Periodendauer &nbsp;$T_0$&nbsp; (diese muss für beide Signale gleich sein):  
+
For periodic signals,&nbsp; the boundary transition can be omitted from the ACF and the CCF calculations,&nbsp; and the period duration &nbsp;$T_0$&nbsp; (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}  ,\\
 
:$$\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*}$$
 
\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 diesem Fall ist die AKF ebenfalls eine periodische Funktion, und man spricht von der &nbsp;''periodischen Autokorrelationsfunktion''&nbsp; $\rm (PAKF)$. Diese zeigt folgende Einenschaft:  
+
In this case,&nbsp; the ACF is also a periodic function,&nbsp; and it is called the &nbsp;"periodic auto-correlation function"&nbsp; $\rm (PACF)$.&nbsp; This shows the following:  
 
:$$\varphi_{x}(\pm T_0) = \varphi_{x}(\pm 2T_0) =\text{ ...} = \varphi_{x}(0)  
 
:$$\varphi_{x}(\pm T_0) = \varphi_{x}(\pm 2T_0) =\text{ ...} = \varphi_{x}(0)  
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Wir wenden nun obige Berechnungsvorschrift auf das Spreizsignal
+
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)$$
 
:$$ c(t) = \sum\limits^{+\infty}_{\nu = -\infty}c_\nu\cdot g_c(t - \nu \cdot T_c)$$
an, wobei ein Rechteckimpuls &nbsp;$g_c(t)$&nbsp; der Breite &nbsp;$T_c$&nbsp; vorausgesetzt wird;&nbsp; $T_c$&nbsp; nennt man die&nbsp; &bdquo;Chipdauer&rdquo;.  
+
assuming a rectangular pulse &nbsp;$g_c(t)$&nbsp; of width &nbsp;$T_c$&nbsp;;&nbsp; $T_c$&nbsp; is called the&nbsp; "chip duration".  
  
Berücksichtigt man die Periodizität &nbsp;$(T_0 = P · T_c)$&nbsp; der Amplitudenkoeffizienten &nbsp;$c_ν ∈ \{±1\}$, so ergeben sich die diskreten AKF–Werte bei Vielfachen $($Parameter $λ)$&nbsp; von &nbsp;$T_c$:  
+
Considering the periodicity &nbsp;$(T_0 = P · T_c)$&nbsp; of the amplitude coefficients &nbsp;$c_ν ∈ \{±1\}$,&nbsp; the discrete ACF values at multiples $($integer parameter $λ)$&nbsp; of &nbsp;$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}.$$
 
:$$\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}.$$
*Der maximale PAKF–Wert ergibt sich für &nbsp;$λ = 0$&nbsp; und für Vielfache der Periodenlänge &nbsp;$P$.  
+
*The maximum PACF value is obtained for &nbsp;$λ = 0$&nbsp; and for multiples of the period length &nbsp;$P$.  
*Aufgrund des rechteckförmigen Impulses &nbsp;$g_c(t)$&nbsp; ist der PAKF–Verlauf zwischen zwei Abtastwerten &nbsp;$λ · T_c$&nbsp; und &nbsp;$(λ + 1) · T_c$&nbsp; stets linear.  
+
*Due to the rectangular pulse &nbsp;$g_c(t)$,&nbsp; the PACF progression between two samples &nbsp;$λ · T_c$&nbsp; and &nbsp;$(λ + 1) · T_c$&nbsp; is always linear.
*Entsprechend ist die &nbsp;''periodische Kreuzkorrelationsfunktion''&nbsp; $\rm (PKKF)$&nbsp; zwischen den zwei Spreizfolgen &nbsp;$〈c_ν〉$&nbsp; und &nbsp;$〈c\hspace{0.04cm}'_ν〉$&nbsp; gleicher Periodenlänge &nbsp;$P$&nbsp; wie folgt gegeben:  
+
*Accordingly, the &nbsp;"periodic cross-correlation function"&nbsp; $\rm (PCCF)$&nbsp; between two spreading sequences &nbsp;$〈c_ν〉$&nbsp; and &nbsp;$〈c\hspace{0.04cm}'_ν〉$&nbsp; of equal period length &nbsp;$P$&nbsp; 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}.$$
 
:$$\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}.$$
  
Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im
 
  
*Kapitel 9: &nbsp; ''Stochastische Prozesse'', Programm „stp”
 
 
 
des Praktikums &bdquo;Simulationsmethoden in der Nachrichtentechnik&rdquo;.&nbsp; Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf
 
*dem Lehrsoftwarepaket&nbsp; [http://en.lntwww.de/downloads/Sonstiges/Programme/LNTsim.zip LNTsim] &nbsp; &rArr; &nbsp; Link verweist auf die ZIP-Version des Programms und
 
*der &nbsp;[http://en.lntwww.de/downloads/Sonstiges/Texte/Praktikum_LNTsim_Teil_B.pdf Praktikumsanleitung]  &nbsp; &rArr; &nbsp; Link verweist auf die PDF-Version; Kapitel 9: Seite 207-228.
 
 
   
 
   
  
==Beurteilungskriterien für PN–Spreizfolgen==
+
==Evaluation criteria for PN spreading sequences==
 
<br>
 
<br>
Die Qualität eines auf PN–Modulation basierenden CDMA–Systems hängt signifikant von den PAKF– und PKKF–Eigenschaften der verwendeten Spreizfolgen ab.&nbsp; Zusammenfassend kann man sagen:  
+
The quality of a CDMA system based on PN modulation depends significantly on the PACF and PCCF properties of the spreading sequences used.&nbsp; In summary:  
*Die PAKF der verwendeten Spreizcodeklasse sollte möglichst durch einen ausgeprägten Peak bei &nbsp;${\it λ} = 0$&nbsp; gekennzeichnet sein, um die Synchronisation beim Empfänger einfach gestalten zu können.&nbsp; Bei Mehrwegeempfang mit einem Echo der Laufzeitdifferenz &nbsp;$λ · T_c$&nbsp; ist zudem die Degradation aufgrund von Impulsinterferenzen um so geringer, je kleiner &nbsp;$|φ_c(λ · T_c)|$&nbsp; ist.  
+
*The PACF of the spreading code class used should be characterized by a pronounced peak at &nbsp;${\it λ} = 0$,&nbsp; if possible,&nbsp; in order to make synchronization at the receiver easy.&nbsp; Moreover,&nbsp; for multipath reception with an echo of delay difference &nbsp;$λ · T_c$,&nbsp; the smaller &nbsp;$|φ_c(λ · T_c)|$&nbsp; is,&nbsp; the smaller is the degradation due to intersymbol interference.
*Der störende Einfluss interferierender CDMA–Teilnehmer lässt sich durch den PKKF–Wert &nbsp;$φ_{cc\hspace{0.04cm}'} (λ = 0)$&nbsp; abschätzen.&nbsp; Ist dieser gleich Null, so spricht man von&nbsp; ''orthogonalen Funktionen''.&nbsp; Die Fehlerwahrscheinlichkeit wird in diesem Fall nicht erhöht.&nbsp; Sind alle Spreizfolgen orthogonal, so ergibt sich auch bei &nbsp;$J$&nbsp; Teilnehmern die gleiche Fehlerwahrscheinlichkeit wie bei nur einem einzigen Nutzer.  
+
*The disruptive influence of interfering CDMA subscribers can be estimated by the PCCF value &nbsp;$φ_{cc\hspace{0.04cm}'} (λ = 0)$.&nbsp; If this is equal to zero,&nbsp; one speaks of &nbsp; "orthogonal functions".&nbsp; The error probability is not increased in this case.&nbsp; If all spreading sequences are orthogonal,&nbsp; then even if there are &nbsp;$J$&nbsp; participants,&nbsp; the error probability is the same as if there were only one user.
*Diese letzte Aussage ist in synchronen Systemen mit verzerrungsfreiem Kanal&nbsp; (zum Beispiel bei AWGN)&nbsp; von besonderer Bedeutung.&nbsp; Bei asynchronem Betrieb oder Mehrwegeempfang kommt es dagegen zu einer &nbsp;''De–Orthogonalisierung''&nbsp; und der strengeren Forderung, dass die PKKF zwischen den einzelnen Folgen zu allen Zeitpunkten (betragsmäßig) möglichst kleine Werte annehmen soll.  
+
*This last statement is of particular importance in synchronous systems with distortion-free channel&nbsp; (for example,&nbsp; in AWGN).&nbsp;&nbsp; On the other hand,&nbsp; in asynchronous operation or multipath reception,&nbsp; "de-orthogonalization"&nbsp; occurs and the stricter requirement that the PCCF between each sequence should take on the smallest possible values&nbsp; (in terms of magnitude)&nbsp; at all times.
  
  
Bei der Auswahl von Codefamilien für ein CDMA–System ist weiter darauf zu achten, dass man bei gegebenem Spreizgrad &nbsp;$J = P$&nbsp; möglichst viele Codefolgen mit günstigen Eigenschaften hinsichtlich dieser drei Kriterien finden kann, um somit auch möglichst viele Teilnehmer gleichzeitig im gleichen Frequenzband versorgen zu können.  
+
When selecting code families for a CDMA system,&nbsp; 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 &nbsp;$J = P$,&nbsp; so that as many subscribers as possible can be supplied simultaneously in the same frequency band.
  
==Pseudo–Noise–Folgen maximaler Länge==
+
==Pseudo-noise sequences of maximum length==
<br>
 
[[File:P_ID1876__Mod_T_5_3_S4a_neu.png|left|frame|PN–Generator (Realisierung mit Schieberegister)]]
 
 
<br>
 
<br>
Mit einem rückgekoppelten Schieberegister lässt sich eine Folge mit günstigen AKF–Eigenschaften erzeugen, wenn man die Rückführungskoeffizienten &nbsp;$g_i$&nbsp; mit Index&nbsp; $i = 1, \text{...} \ , G-1$&nbsp; geeignet wählt.&nbsp;  
+
A feedback shift register can be used to generate a sequence with favorable ACF properties if the feedback coefficients &nbsp;$g_i$&nbsp; with index&nbsp; $i = 1, \text{...} \ , G-1$&nbsp; are chosen appropriately. &nbsp;
*Die Folge &nbsp;$〈c_ν〉$&nbsp; ist im strengen Sinne nicht zufällig, sondern periodisch.&nbsp;  
+
[[File:EN_Mod_T_5_3_S4.png|right|frame|PN generator&nbsp; (realization with shift registers)]]
*Aufgrund der großen Periodenlänge &nbsp;$P$&nbsp; erscheint sie aber für einen unbedarften Betrachter als stochastisch.&nbsp;
+
[[File:EN_Mod_T_5_3_S4b.png|right|frame| Polynomials of M-sequences with degree&nbsp; $G$]]
*Man spricht von einer &nbsp;''Pseudo–Noise–Folge''&nbsp; oder kurz &nbsp;''PN–Folge''.
 
<br clear=all>
 
$\text{PN–Generatoren}$&nbsp; haben folgende Eigenschaften, siehe Kapitel &nbsp;[[Stochastische_Signaltheorie/Erzeugung_von_diskreten_Zufallsgrößen|Erzeugung von diskreten Zufallsgrößen]]&nbsp; im Buch &bdquo;Stochastische Signaltheorie&rdquo;:
 
[[File:P_ID1877__Mod_T_5_3_S4b.png |right|frame| Polynome von M–Sequenzen mit Grad&nbsp; $G$]]
 
*Die zu früheren Zeitpunkten generierten Binärwerte &nbsp;$c_{ν-1}, \text{...} \ , c_{ν-G}$&nbsp; sind in den &nbsp;$G$&nbsp; Speicherzellen des Schieberegisters abgelegt.&nbsp; Man bezeichnet &nbsp;$G$&nbsp; als den ''Grad'' des Schieberegisters.
 
 
   
 
   
*Die Koeffizienten &nbsp;$g_1, \ \text{...} \ , g_{G-1}$&nbsp; sind Binärwerte, wobei eine „1” eine Rückführung an der entsprechenden Stelle des Schieberegisters kennzeichnet und eine „0” keine Rückführung.
+
*The sequence&nbsp;$〈c_ν〉$&nbsp; is not random in the strict sense,&nbsp; but periodic. &nbsp;
 +
*However,&nbsp; due to the large period length &nbsp;$P$&nbsp; it appears stochastic to an uninitiated observer.&nbsp;
 +
*One speaks of a &nbsp;'''pseudo–noise sequence'''&nbsp; or &nbsp;"PN sequence" for short.
 +
 
 +
<br><br> 
 +
$\text{PN generators}$&nbsp; have the following properties,&nbsp; see chapter &nbsp;[[Theory_of_Stochastic_Signals/Erzeugung_von_diskreten_Zufallsgrößen|Generation of Discrete Random Variables]]&nbsp; in the book "Theory of Stochastic Signals":
 +
*The binary values &nbsp;$c_{ν-1}, \text{...} \ , c_{ν-G}$&nbsp; generated at earlier times are stored in the &nbsp;$G$&nbsp; memory cells of the shift register.&nbsp; We refer to &nbsp;$G$&nbsp; as the&nbsp; "degree of the shift register".
 +
 
 +
*The coefficients &nbsp;$g_1, \ \text{...} \ , g_{G-1}$&nbsp; are binary values,&nbsp; where a&nbsp; "1"&nbsp; indicates a feedback at the corresponding location of the shift register and a&nbsp; "0"&nbsp; indicates no feedback.
 
   
 
   
*Für das aktuell erzeugte Symbol gilt mit &nbsp;$g_i ∈ \{0, 1\}$ und $i = 1,\ \text{...}\ , G-1$:  
+
*For the currently generated symbol,&nbsp; with &nbsp;$g_i ∈ \{0, 1\}$&nbsp; and&nbsp; $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.$$
 
:$$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.$$
*Die Modulo–2–Addition kann zum Beispiel durch eine&nbsp; $\rm XOR$–Verknüpfung realisiert werden:  
+
*The modulo-2 addition can be realized for example by an&nbsp; $\rm XOR$&nbsp; 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 &nbsp;$G$&nbsp; memory cells are preallocated with zeros,&nbsp; the result is a periodic random sequence &nbsp;$〈c_ν〉$.&nbsp; The period length &nbsp;$P$&nbsp; of this sequence depends strongly on the feedback coefficients &nbsp;$g_i$.&nbsp;
  
:$$(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 falls\hspace{0.1cm} {\it x}= {\it y},\\          1 & \rm falls\hspace{0.1cm} {\it x}\neq {\it y}. \\              \end{array}    \right.$$
+
*For each degree&nbsp; $G$&nbsp; there are at least two configurations with the maximum period &nbsp;$P_{\rm max} = 2^G – 1$&nbsp; for this.
*Sind nicht alle &nbsp;$G$&nbsp; Speicherzellen mit Nullen vorbelegt, so entsteht eine periodische Zufallsfolge &nbsp;$〈c_ν〉$.&nbsp; Die Periodenlänge &nbsp;$P$&nbsp; dieser Folge hängt stark von den Rückkopplungskoeffizienten &nbsp;$g_i$&nbsp; ab.
 
*Für jeden Grad&nbsp; $G$&nbsp; gibt es zumindest zwei Konfigurationen mit der hierfür maximalen Periode &nbsp;$P_{\rm max} = 2^G – 1$.  
 
  
  
In obiger Tabelle sind für einige Werte von &nbsp;$G$&nbsp; das Generatorpolynom &nbsp;$G(D)$&nbsp; einer solchen M–Sequenz und die zugehörige (maximale) Periodenlänge &nbsp;$P$&nbsp; angegeben, wobei das „M” für „Maximal” steht.&nbsp; Nachfolgend werden die hier gemachten Aussagen am Beispiel &nbsp;$G = 4$&nbsp; verdeutlicht.
+
In the table on the right,&nbsp; for some values of &nbsp;$G$,&nbsp; the generator polynomial &nbsp;$G(D)$&nbsp; of such an M-sequence and the corresponding&nbsp; (maximum)&nbsp; period length &nbsp;$P$&nbsp; are given,&nbsp; where&nbsp; "M"&nbsp; stands for&nbsp; "Maximum".&nbsp; In the following the statements made here are clarified at the example &nbsp;$G = 4$.&nbsp;  
  
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 1:}$&nbsp; Die Grafik zeigt zwei mögliche Anordnungen zur Erzeugung einer PN–Folge maximaler Länge für &nbsp;$G = 4$ &nbsp; ⇒ &nbsp; $P = 15$.
+
$\text{Example 1:}$&nbsp; The diagram shows two possible arrangements for generating a PN sequence of maximum length for &nbsp;$G = 4$ &nbsp; ⇒ &nbsp; $P = 15$.
[[File:P_ID1878__Mod_T_5_3_S4c_ganz_neu.png|right|frame| PN–Generatoren vom Grad &nbsp;$G = 4$]]  
+
[[File:EN_Mod_T_5_3_S4c.png|right|frame| PN generators of degree &nbsp;$G = 4$]]
 +
 
 +
[[File: P_ID1879__Mod_T_5_3_S4d_ganz_neu.png|right|frame|PACF of a PN sequence of maximum length &nbsp;$P = 2^G – 1$]]
 
   
 
   
*Als Kurzbezeichnung wird meist die &nbsp;''Oktaldarstellung''&nbsp; der Binärzahl &nbsp;$(g_G, \ \text{...} \ ,g_2, g_1, g_0)$&nbsp; gewählt.&nbsp; Grundsätzlich ist&nbsp; $g_0 = g_G = 1$&nbsp; zu setzen.
+
*The octal representation of the binary number &nbsp;$(g_G, \ \text{...} \ ,g_2, g_1, g_0)$&nbsp; is usually chosen as the abbreviation.&nbsp; Basically&nbsp; $g_0 = g_G = 1$&nbsp; is to be set.
  
*Die linke Konfiguration wird mit &nbsp;$\rm (11001)_{binär} = (31)_{oktal}$&nbsp; bezeichnet, das dazugehörige Generatorpolynom lautet:
+
*For the left generator:&nbsp; $\rm (11001)_{binary} = (31)_{octal}$.&nbsp; The corresponding generator polynomial is:
:$$G(D) = D^4 + D^3 +1\hspace{0.05cm}.$$
+
:$$G_1(D) = D^4 + D^3 +1\hspace{0.05cm}.$$
*Die rechte Anordnung mit &nbsp;$\rm (10011)_{binär} = (23)_{oktal}$&nbsp; ist dagegen durch das zu &nbsp;$G(D)$&nbsp; reziproke Polynom &nbsp;$G_{\rm R}(D)$&nbsp; beschreibbar:  
 
:$$G_{\rm R}(D) = D^4 \cdot  (D^{-4}  + D^{-3} +1) =D^4 + D +1 \hspace{0.05cm}.$$
 
  
Da sowohl &nbsp;$G(D)$&nbsp; als auch &nbsp;$G_{\rm R}(D)$&nbsp; [[Kanalcodierung/Erweiterungskörper#Primitive_Polynome|primitive Generatorpolynome]]&nbsp; darstellen&nbsp; (der Nachweis hierfür ist nicht einfach), haben beide Ausgangsfolgen die für &nbsp;$G = 4$&nbsp; maximale Periodenlänge &nbsp;$P = 15$. Wie in der  &nbsp;[[Aufgaben:5.3_PAKF_von_PN–Sequenzen|Aufgabe 5.3]]&nbsp; gezeigt wird, ergibt sich die PAKF in der unipolaren Darstellung &nbsp; ⇒ &nbsp; $c_ν ∈ \{0, 1\}$ zu
+
*For the right generator:&nbsp; $\rm (10011)_{binary} = (23)_{octal}$.&nbsp; This generator can be described by the polynomial
[[File: P_ID1879__Mod_T_5_3_S4d_ganz_neu.png|right|frame|PAKF einer PN–Sequenz maximaler Länge &nbsp;$P = 2^G – 1$]]
+
:$$G_2(D) =D^4 + D +1 \hspace{0.05cm}.$$
 +
*The polynomial&nbsp; $G_2(D)$&nbsp; is reciprocal to &nbsp;$G_{\rm 1}(D)$:
 +
:$$G_{\rm 2}(D) = D^4 \cdot  (D^{-4}  + D^{-3} +1) =D^4 + D +1 \hspace{0.05cm}.$$
  
:$${\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{f\ddot{u}r} } \\  {\rm{sonst} } \hspace{0.05cm}.   \\ \end{array}\begin{array}{*{20}c} \lambda = 0, \pm P, \pm 2P, \text{...} \hspace{0.05cm} \\ \\ \end{array}$$
+
Since both &nbsp;$G_1(D)$&nbsp; and &nbsp;$G_{\rm 2}(D)$&nbsp; are&nbsp; [[Channel_Coding/Erweiterungskörper#Bin.C3.A4re_Erweiterungsk.C3.B6rper_.E2.80.93_Primitive_Polynome|primitive generator polynomials]]&nbsp; &nbsp; (the proof for this is not easy),&nbsp; both output sequences have the maximum period length &nbsp;$P = 15$&nbsp; for &nbsp;$G = 4$.  
Nach Umsetzung in bipolare Koeffizienten &nbsp;$($das heißt: &nbsp;$0 \ ⇒  +1$, &nbsp; &nbsp; $1 \ ⇒  -1)$&nbsp; erhält man:
 
:$${\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{f\ddot{u}r} } \\  {\rm{sonst.} } \hspace{0.05cm}  \\ \end{array}\begin{array}{*{20}c} \lambda = 0, \pm P, \pm 2P, \text{...} \hspace{0.05cm} \\ \\ \end{array}$$
 
*Man erkennt aus der unteren Skizze die gewünschten ausgeprägten PAKF–Peaks in Abständen der Periode &nbsp;$P$.  
 
*Weniger gut sind die Kreuzkorrelationseigenschaften der PN–Sequenzen, wie im Kapitel &nbsp;[[Modulationsverfahren/Fehlerwahrscheinlichkeit_der_PN–Modulation|Fehlerwahrscheinlichkeit der PN–Modulation]]&nbsp; noch gezeigt werden wird.}}
 
  
 +
As shown in  &nbsp;[[Aufgaben:Exercise_5.3:_PACF_of_PN_Sequences|Exercise 5.3]],&nbsp; the PACF in unipolar representation &nbsp; ⇒ &nbsp; $c_ν ∈ \{0, 1\}$&nbsp; results in
 +
:$${\it \varphi}_{c{\rm ,\hspace{0.15cm}unipolar} }(\lambda \cdot T_c) = \left\{ \begin{array}{c}(P+1)/(2P) \\ (P+1)/(4P) \\  \end{array} \right. \begin{array}{*{10}c}  \ \  {\rm{for} }\ \lambda = 0, \pm P, \pm 2P, \text{...} \hspace{0.05cm} \\  {\rm{otherwise} } \hspace{0.05cm}.  \\ \end{array}$$
  
Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im
+
After conversion to bipolar coefficients &nbsp;$(0 \ ⇒  +1$, &nbsp; &nbsp; $1 \ ⇒  -1)$,&nbsp; we obtain:
 +
:$${\it \varphi}_{c{\rm ,\hspace{0.15cm}bipolar} }(\lambda \cdot T_c) = \left\{ \begin{array}{c}1 \\ -P \\  \end{array} \right. \begin{array}{*{10}c}  \ \  {\rm{for} }\ \lambda = 0, \pm P, \pm 2P, \text{...} \hspace{0.05cm} \\  {\rm{otherwise} } \hspace{0.05cm}.  \\ \end{array}$$
 +
*One can see from the bottom diagram the desired distinct PACF peaks at intervals of periode &nbsp;$P$.
 +
*The PCCF properties of PN sequences are less good,&nbsp; as will be shown in chapter &nbsp;[[Modulation_Methods/Fehlerwahrscheinlichkeit_der_PN–Modulation|Error Probability of Direct-Sequence Spread Spectrum Modulation]].&nbsp;}}
  
*Kapitel 2: &nbsp; ''Pseudonoise&ndash;Generatoren'', Programm „png”
 
  
  
des Praktikums &bdquo;Simulationsmethoden in der Nachrichtentechnik&rdquo;. Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf
+
==Code families with M-sequences==
*dem Lehrsoftwarepaket &nbsp;[http://en.lntwww.de/downloads/Sonstiges/Programme/LNTsim.zip LNTsim]&nbsp; &nbsp; &rArr; &nbsp; Link verweist auf die ZIP-Version des Programms und
 
*der &nbsp;[http://en.lntwww.de/downloads/Sonstiges/Texte/Praktikum_LNTsim_Teil_A.pdf Praktikumsanleitung]  &nbsp; &rArr; &nbsp; Link verweist auf die PDF-Version; &nbsp; Kapitel 2: Seite 23-32.
 
 
 
 
 
==Codefamilien mit M–Sequenzen==
 
 
<br>
 
<br>
Bei CDMA wird für jeden Teilnehmer eine spezifische Spreizfolge gleicher Periodenlänge benötigt. Als '''Codefamilie''' bezeichnet man eine (möglichst große) Menge an Spreizsequenzen gleicher Periodenlänge &nbsp;$P$, gültig jeweils für einen Registergrad &nbsp;$G$.  
+
In CDMA,&nbsp; a specific spreading sequence of the same period length is required for each subscriber.&nbsp; A&nbsp; '''code family'''&nbsp; is defined as a set&nbsp; (as large as possible)&nbsp; of spreading sequences of the same period length &nbsp;$P$,&nbsp; each valid for a register level &nbsp;$G$.  
  
Die Tabelle zeigt, dass die Anzahl von PN–Sequenzen maximaler Länge sehr gering ist. Für den Grad &nbsp;$G = 5$ &nbsp;  ⇒ &nbsp;  $P = 31$&nbsp; gibt es zum Beispiel gerade einmal sechs M–Sequenzen, nämlich die PN–Generatoren mit den Oktalkennungen &nbsp;$(45), (51), (57), (67), (73)$&nbsp; und &nbsp;$(75)$.  
+
The table shows that the number of PN sequences of maximum length is very small. For the degree &nbsp;$G = 5$ &nbsp;  ⇒ &nbsp;  $P = 31$,&nbsp; for example,&nbsp; there are just six M-sequences,&nbsp; namely the PN generators with the octal identifiers &nbsp;$(45), (51), (57), (67), (73)$&nbsp; and &nbsp;$(75)$.  
  
[[File:P_ID1880__Mod_T_5_3_S5_neu.png |center|frame| Mächtigkeit von M–Sequenz–Codefamilien]]
+
[[File:EN_Mod_T_5_3_S5neu.png|right|frame| M-sequence code family &ndash; powerfullness]]
  
Des Weiteren ist in der Literatur auch der Begriff '''Mächtigkeit''' der Codefamilie zu finden.  
+
Furthermore, the term&nbsp; '''powerfulness'''&nbsp; of the code family can also be found in the literature.  
*Diese Größe gibt an, wie viele M–Sequenzen und damit gleichzeitige CDMA–Teilnehmer möglich sind, wenn man fordert, dass alle Codepaare „günstige PKKF–Eigenschaften” aufweisen.  
+
*This quantity indicates how many M-sequences and thus simultaneous CDMA subscribers are possible if it is required that all code pairs have&nbsp; "favorable PCCF properties".
*Aus Platzgründen kann hier nicht explizit ausgeführt werden, was man unter „günstig” genau zu verstehen hat. Hierzu sei auf die Originalliteratur verwiesen, zum Beispiel [ZP85]<ref>Ziemer, R.; Peterson, R. L.: ''Digital Communication and Spread Spectrum Systems.'' New York: McMillon, 1985.</ref>.   
+
*For reasons of space,&nbsp; it cannot be explicitly stated here what exactly is meant by&nbsp; "favorable".&nbsp; For this,&nbsp; we refer to the original literature,&nbsp; for example [ZP85]<ref>Ziemer, R.; Peterson, R. L.:&nbsp; Digital Communication and Spread Spectrum Systems. New York: McMillon, 1985.</ref>.   
  
  
Die letzte Zeile in obiger Tabelle macht deutlich, dass die Mächtigkeit von M–Sequenz–Codefamilien äußerst beschränkt ist, auch bei großem &nbsp;$G$&nbsp; und damit großer Periodenlänge &nbsp;$P$. Ist &nbsp;$G$&nbsp; ein Vielfaches von $4$ &nbsp; ⇒  &nbsp; $P = 15$, $P = 255$, $P = 4095$ usw., so gibt es grundsätzlich keine günstigen Paare.  
+
The last row in the above table makes it clear that the powerfulness of M-sequence code families is extremely limited,&nbsp; even if &nbsp;$G$&nbsp; is large and thus the period length &nbsp;$P$ is large, too.&nbsp; If &nbsp;$G$&nbsp; is a multiple of&nbsp; $4$ &nbsp; ⇒  &nbsp; $P = 15$,&nbsp; $P = 255$,&nbsp; $P = 4095$ etc.,&nbsp; there are essentially no favorable pairs.
  
==Gold–Codes==
+
==Gold Codes==
 
<br>
 
<br>
Um größere Codefamilien zu erhalten als mit M–Sequenzen, müssen die Anforderungen an die periodische Kreuzkorrelationsfunktion&nbsp; $\rm (PKKF)$&nbsp; abgeschwächt werden.&nbsp; Mit dieser Einschränkung erhält man Codefamilien mit einer weitaus größeren Mächtigkeit, so dass auch mehr CDMA–Teilnehmer versorgt werden können.  
+
To obtain larger code families than with M-sequences,&nbsp; the requirements for the periodic cross-correlation function&nbsp; $\rm (PCCF)$&nbsp; must be weakened.&nbsp; With this restriction,&nbsp; code families with a much greater powerfulness are obtained,&nbsp; so that more CDMA subscribers can also be supplied.
  
[[File:P_ID1881__Mod_T_5_3_S6_neu.png|right|frame|Gold–Codegenerator &nbsp;$(51, \ 75)$&nbsp;  vom Grad &nbsp;$G = 5$]]
+
Gold codes use this principle.&nbsp;  The rule for generating a&nbsp; '''Gold code family''' &nbsp; $\rm (GCF)$&nbsp; is where a&nbsp; „+”&nbsp; 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{...} \  ,\
Gold–Codes verwenden dieses Prinzip.&nbsp; Die Vorschrift zur Erzeugung einer&nbsp; '''Gold–Code–Familie''' &nbsp;$\rm (GCF)$&nbsp; lautet, wobei ein&nbsp; „+”&nbsp; eine Modulo–2–Addition bezeichnet:  
 
:$${\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}.$$
 
C_1 + D^{P-1} \cdot C_2 \} \hspace{0.05cm}.$$
 +
[[File:EN_Mod_T_5_3_S6.png|right|frame|Gold code generator &nbsp;$(51,  75)$&nbsp; of degree &nbsp;$G = 5$]]
  
Das Prinzip ist in der Grafik an einem Beispiel dargestellt:  
+
The principle is illustrated in the diagram by an example:
*Die Folgen &nbsp;$C_1$&nbsp; und &nbsp;$C_2$&nbsp; sind ein günstiges Paar von M–Sequenzen gleicher Periodenlänge, zum Beispiel die PN–Generatoren mit den Oktalkennungen &nbsp;$(51)$&nbsp; und &nbsp;$(75)$&nbsp; vom Grad &nbsp;$G = 5$&nbsp; und damit der Periodenlänge &nbsp;$P = 31$.  
+
*The sequences &nbsp;$C_1$&nbsp; and &nbsp;$C_2$&nbsp; are a convenient pair of&nbsp; "M-sequences"&nbsp; of the same period length,&nbsp; for example,&nbsp; the PN generators with the octal identifiers &nbsp;$(51)$&nbsp; and &nbsp;$(75)$&nbsp; of degree &nbsp;$G = 5$&nbsp; and thus the period length &nbsp;$P = 31$.  
*Die Gold–Code–Familie besteht zum einen aus den M–Sequenzen &nbsp;$C_1$&nbsp; und &nbsp;$C_2$&nbsp; sowie aus einigen Modulo–2–Additionen dieser Folgen.&nbsp; Dabei wird &nbsp;$C_1$&nbsp; mit fester Phase&nbsp; (gekennzeichnet durch die Vorbelegung aller Speicherzellen mit Einsen)&nbsp; verwendet, während für die Folge &nbsp;$C_2$&nbsp; alle &nbsp;$P$&nbsp; möglichen Anfangsphasen zulässig sind&nbsp; (alle Vorbelegungen außer der Nullbelegung).  
+
*The Gold code family consists,&nbsp; on the one hand,&nbsp; of the&nbsp; "M-sequences" &nbsp;$C_1$&nbsp; and &nbsp;$C_2$&nbsp; and of some modulo-2 additions of these sequences.&nbsp; &nbsp;$C_1$&nbsp; is used with a fixed phase&nbsp; (characterized by the preallocation of all memory cells with ones),&nbsp; while all &nbsp;$P$&nbsp; possible initial phases are permissible for the sequence &nbsp;$C_2$&nbsp; (all preallocations except the zero allocation).  
*Verwendet man eine solche Codefamilie für CDMA, so stehen insgesamt &nbsp;$K_{\rm GCF} = P + 2 = 2^G + 1$&nbsp; Folgen zur Verfügung.&nbsp; Die PAKF dieser Folgen ist nun aber nicht mehr zweiwertig wie die beiden PN–Sequenzen&nbsp; &nbsp;$(+1$&nbsp; bzw.&nbsp; $-1/31)$, sondern vierwertig &nbsp;$(+1$,&nbsp; $+7/31$,&nbsp; $-1/31$,&nbsp; $-9/31)$.&nbsp; Durch die Phase von &nbsp;$C_2$&nbsp; ändert sich zwar der spezifische Verlauf, aber nicht die möglichen PAKF–Werte.  
+
*If such a code family is used for CDMA,&nbsp; a total of &nbsp;$K_{\rm GCF} = P + 2 = 2^G + 1$&nbsp; sequences are available.&nbsp; However,&nbsp; the PACF of these sequences is now no longer bivalent like the two PN sequences&nbsp; &nbsp;$(+1$&nbsp; and&nbsp; $-1/31)$, but quadrivalent &nbsp;$(+1$,&nbsp; $+7/31$,&nbsp; $-1/31$,&nbsp; $-9/31)$.&nbsp; The phase of &nbsp;$C_2$&nbsp; changes the specific progression,&nbsp; but not the possible PACF values.
  
  
Gold–Codes werden zum Beispiel bei UMTS zur Verwürfelung herangezogen, wie im Kapitel&nbsp; [[Beispiele_von_Nachrichtensystemen/Nachrichtentechnische_Aspekte_von_UMTS#Spreizcodes_und_Verw.C3.BCrfelung_bei_UMTS|Spreizcodes und Verwürfelung in UMTS]]&nbsp; des Buches „Beispiele von Nachrichtensystemen” ausgeführt ist.  
+
Gold codes are used for scrambling in UMTS,&nbsp; for example,&nbsp; as explained in the chapter&nbsp; [[Examples_of_Communication_Systems/Nachrichtentechnische_Aspekte_von_UMTS#Spreizcodes_und_Verw.C3.BCrfelung_bei_UMTS|Spreading codes and scrambling in UMTS]]&nbsp; in the book "Examples of Communication Systems".
*Die beiden Muttercode–Schieberegister sind dabei jeweils mit &nbsp;$G = 18$&nbsp; Speicherzellen aufgebaut.  
+
*The two master code shift registers are each constructed with &nbsp;$G = 18$&nbsp; memory cells.
*Damit ergibt sich die Periodenlänge &nbsp;$P = 262\hspace{0.05cm} 143$.  
+
*This results in the period length &nbsp;$P = 262\hspace{0.05cm} 143$.  
  
==Walsh–Funktionen==
+
==Walsh functions==
 
<br>
 
<br>
Spreizfolgen mit sehr günstigen PKKF–Eigenschaften sind die so genannten&nbsp; '''Walsh–Funktionen''', deren Konstruktion auf der&nbsp; '''Hadamard–Matrix'''&nbsp; basiert und durch Rekursion in einfacher Weise durchführbar ist.&nbsp; Ausgehend von der Matrix &nbsp;$\mathbf H_2$&nbsp; können weitere Hadamard–Matrizen &nbsp;$\mathbf H_{2J}$&nbsp; wie folgt generiert werden:
+
Spreading sequences with very favorable PCCF properties are the so-called&nbsp; '''Walsh functions''',&nbsp; whose construction is based on the&nbsp; '''Hadamard matrix'''&nbsp; and can be performed in a simple way by recursion.&nbsp; Starting from the matrix &nbsp;$\mathbf H_2$,&nbsp; further Hadamard matrices &nbsp;$\mathbf H_{2J}$&nbsp; can be generated as follows:
[[File:P_ID1882__Mod_T_5_3_S7_neu.png|right|frame| Walsh–Spreizfolgen &nbsp;$(J = 8)$&nbsp; und Hadamard–Matrix &nbsp;$\mathbf H_8$&nbsp;]]  
+
 
 +
[[File:P_ID1882__Mod_T_5_3_S7_neu.png|right|frame| Walsh spreading sequences &nbsp;$(J = 8)$&nbsp; and Hadamard matrix &nbsp;$\mathbf H_8$&nbsp;]]
 +
 
:$${\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] $$
 
:$${\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}
 
:$$\hspace{0.5cm} \Rightarrow \hspace{0.5cm}
 
{\mathbf{H}_{4}} = \left[ \begin{array}{cccc} +1 & +1 & +1 & +1 \\ +1 & -1 & +1 & -1 \\
 
{\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] .$$
 
+1 & +1 & -1 & -1 \\+1 & -1 & -1 & +1 \end{array} \right] .$$
Die &nbsp;$J$&nbsp; Zeilen einer solchen Matrix beschreiben die &nbsp;$J$&nbsp; möglichen Spreizfolgen&nbsp; $($jeweils der Länge &nbsp;$J)$, die mit  &nbsp;$w_0(t)$&nbsp; bis&nbsp; $w_{J–1}(t)$&nbsp; durchnummeriert werden.
+
The &nbsp;$J$&nbsp; rows of such a matrix describe the &nbsp;$J$&nbsp; possible spreading sequences&nbsp; $($each of length &nbsp;$J)$,&nbsp; which are numbered &nbsp;$w_0(t)$&nbsp; to&nbsp; $w_{J–1}(t)$.&nbsp;  
  
Die Grafik zeigt die Hadamard–Matrix &nbsp;$\mathbf H_8$&nbsp; (rechts) und die damit &nbsp;$J -1$&nbsp; konstruierbaren Spreizfolgen.  
+
The diagram shows the Hadamard matrix &nbsp;$\mathbf H_8$&nbsp; (right) and the&nbsp;$J -1$&nbsp; spreading sequences that can be constructed with it.
*$J - 1$ deshalb, da die ungespreizte Folge &nbsp;$w_0(t)$&nbsp; meist nicht verwendet wird.  
+
*$J - 1$ because the sequence &nbsp;$w_0(t)$&nbsp; without spreading effect is usually not used.
*Beachten Sie bitte in der Grafik die farbliche Zuordnung zwischen den Zeilen der Hadamard–Matrix und den Spreizfolgen &nbsp;$w_j(t)$.&nbsp; Die Matrix &nbsp;$\mathbf H_4$&nbsp; ist gelb hinterlegt.  
+
*Please note the color allocation between the rows of the Hadamard matrix and the spreading sequence &nbsp;$w_j(t)$&nbsp; in the graphic. The matrix &nbsp;$\mathbf H_4$&nbsp; is highlighted in yellow.
*Die Animation &nbsp;[[Applets:Zur_Erzeugung_von_Walsh-Funktionen_(neues_Applet)|Zur Erzeugung von Walsh–Funktionen]]&nbsp; zeigt den Konstruktionsalgorithmus solcher Folgen.  
+
*The HTML5/JavaScript applet&nbsp; [[Applets:Generation_of_Walsh_functions|Generation of Walsh functions]]&nbsp; shows the construction algorithm of such sequences.
  
  
Weiter gilt:  
+
Further applies:
#&nbsp;Nimmt man zwei beliebige Zeilen und bildet die Korrelation&nbsp; (Mittelung über die Produkte), so ergibt sich stets der PKKF–Wert Null.&nbsp; Somit sind Walsh–Funktionen für einen verzerrungsfreien Kanal und ein synchrones CDMA–System aufgrund ihrer Orthogonalität optimale Spreizfolgen.  
+
#&nbsp;If one takes any two lines and forms the correlation&nbsp; (averaging over the products),&nbsp; the PCCF value always results in zero.&nbsp; Thus,&nbsp; Walsh functions for a distortion-free channel and a synchronous CDMA system are optimal spreading sequences due to their orthogonality.
#&nbsp;Bei asynchronem Betrieb&nbsp; (Beispiel: &nbsp; Uplink eines Mobilfunksystems)&nbsp; oder De–Orthogonalisierung aufgrund von Mehrwegeausbreitung sind dagegen Walsh–Funktionen allein zur Bandspreizung nicht unbedingt geeignet – siehe &nbsp;[[Aufgaben:5.4_Walsh–Funktionen_(PKKF,_PAKF)|Aufgabe 5.4]].   
+
#&nbsp;In contrast,&nbsp; for asynchronous operation&nbsp; (example: uplink of a mobile radio system)&nbsp; or de-orthogonalization due to multipath propagation,&nbsp; Walsh functions alone are not necessarily suitable for band spreading - see &nbsp;[[Aufgaben:Exercise_5.4:_Walsh_Functions_(PCCF,_PACF)|Exercise 5.4]].   
#&nbsp;Hinsichtlich PAKF&nbsp; (periodische AKF)&nbsp; sind diese Folgen weniger gut: &nbsp; Jede einzelne Walsh–Funktion hat eine andere PAKF und jede einzelne PAKF ist ungünstiger als bei einer vergleichbaren PN–Sequenz.&nbsp; Das bedeutet: &nbsp; Die Synchronisierung ist bei Walsh–Funktionen schwieriger als mit PN–Sequenzen.  
+
#&nbsp;Regarding PACF&nbsp; (periodic ACF),&nbsp; these consequences are less good: &nbsp; Each single Walsh function has a different PACF and each single PACF is less favorable than for a comparable PN sequence.&nbsp; This means: &nbsp; Synchronization is more difficult with Walsh functions than with PN sequences.
  
==Codes mit variablem Spreizfaktor (OVSF–Code)==
+
==Codes with variable spreading factor (OVSF codes)==
 
<br>
 
<br>
Das 3G–Mobilfunksystem &nbsp;[[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_UMTS|UMTS]]&nbsp; stellt verschiedene Datenraten zur Verfügung.&nbsp; Hierzu werden
+
The 3G mobile communications system&nbsp;[[Examples_of_Communication_Systems/Allgemeine_Beschreibung_von_UMTS|UMTS]]&nbsp; provides various data rates.&nbsp; For this purpose
*Spreizfolgen mit unterschiedlichen Spreizfaktoren &nbsp;$J = 4$&nbsp; bis &nbsp;$J = 512$&nbsp; benötigt,  
+
*spreading sequences with different spreading factors &nbsp;$J = 4$&nbsp; to &nbsp;$J = 512$&nbsp; are required,
*die alle zueinander orthogonal sein müssen.  
+
*which must all be orthogonal to each other.
 +
 
 +
[[File:P_ID1883__Mod_T_5_3_S8_neu.png|right|frame | Tree diagram for generating an OVSF code]]
 +
<br>The so-called&nbsp; '''OVSF codes'''&nbsp; ("Orthogonal Variable Spreading Factor")&nbsp; can be created with the help of a code tree.&nbsp; Thereby two new codes &nbsp;$(+C \ +\hspace{-0.05cm}C)$&nbsp; and &nbsp;$(+C \ -\hspace{-0.05cm}C)$&nbsp; are created at each branching from a code&nbsp; $C$,&nbsp; as indicated in the graphic above right.
 +
 
 +
It should be noted that no predecessor and successor of a code may be used by other participants.&nbsp; In this example,&nbsp; the following selection could therefore be made&nbsp; (among others):
 +
*eight codes with the spreading factor &nbsp;$J = 8$,&nbsp; or
 +
*the four highlighted codes – once with &nbsp;$J = 2$, once with &nbsp;$J = 4$&nbsp; and twice with &nbsp;$J = 8$.  
  
[[File:P_ID1883__Mod_T_5_3_S8_neu.png|right|frame | Baumdiagramm zur Erzeugung eines OVSF–Codes]]
 
<br>Die so genannten&nbsp; '''OVSF–Codes'''&nbsp; (''Orthogonal Variable Spreading Factor'')&nbsp; können mit Hilfe eines Codebaumes erstellt werden.&nbsp; Dabei entstehen bei jeder Verzweigung aus einem Code &nbsp;$C$&nbsp; zwei neue Codes &nbsp;$(+C \ +\hspace{-0.05cm}C)$&nbsp; und &nbsp;$(+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.&nbsp; Im Beispiel könnte demnach unter Anderem folgende Auswahl getroffen werden:
+
In the second case, the other six&nbsp; $J = 8$&nbsp; codes cannot be used because they begin with &nbsp;"$+1 \ +\hspace{-0.05cm}1$"&nbsp; or with &nbsp;"$+1 \ -\hspace{-0.05cm}1 \ +\hspace{-0.05cm}1 \ -\hspace{-0.05cm}1$".&nbsp;
*acht Codes mit dem Spreizfaktor &nbsp;$J = 8$, oder
 
*die vier hinterlegten Codes – einmal mit &nbsp;$J = 2$, einmal mit &nbsp;$J = 4$&nbsp; und zweimal mit &nbsp;$J = 8$.
 
<br clear=all>
 
Im zweiten Fall können die weiteren sechs Codes mit &nbsp;$J = 8$&nbsp; nicht verwendet werden, da sie entweder mit &nbsp;$+1 \ +\hspace{-0.05cm}1$&nbsp; oder mit &nbsp;$+1 \ -\hspace{-0.05cm}1 \ +\hspace{-0.05cm}1 \ -\hspace{-0.05cm}1$&nbsp; beginnen.
 
  
Aus den vier zugehörigen Spreizfolgen in der Grafik rechts unten erkennt man, dass bei konstanter Chipdauer &nbsp;$T_c$&nbsp; der Nutzer mit dem Spreizfaktor &nbsp;$J = 2$&nbsp; mit höherer Datenrate übertragen kann als die Teilnehmer mit &nbsp;$J = 4$&nbsp; bzw. &nbsp;$J = 8$, da seine Bitdauer &nbsp;$T_{\rm B}$&nbsp; kleiner ist.  
+
From the four spreading sequences in the graphic at the bottom right,&nbsp; it can be seen that with a constant chip duration &nbsp;$T_c$,&nbsp; the user with spreading factor &nbsp;$J = 2$&nbsp; can transmit at a higher data rate than the users with &nbsp;$J = 4$&nbsp; or &nbsp;$J = 8$ because his bit duration &nbsp;$T_{\rm B}$&nbsp; is smaller.
  
Aus der Grafik erkennt man weiter, dass die periodische KKF an der Stelle &nbsp;$τ = 0$&nbsp; stets Null ist.
+
From the graph,&nbsp; we can further see that the periodic cross-correlation function&nbsp;  $\rm (PCCF)$&nbsp; is always zero at the point &nbsp;$τ = 0$.&nbsp;  
*Das heißt: &nbsp; Bildet man das Produkt von zwei beliebigen dieser Folgen und integriert man über den dargestellten Zeitbereich, so ergibt sich stets der Wert $0$.  
+
*That means: &nbsp; If one forms the product of any two of these sequences and integrates over the represented time range, the value&nbsp; $0$&nbsp; always results.  
*Das bedeutet auch: &nbsp; Ein OVSF–Code ist orthogonal zu allen anderen OVSF–Codes der gleichen Familie, solange es nicht zu Verschiebungen kommt.  
+
*This also means: &nbsp; '''An OVSF code is orthogonal to all other OVSF codes of the same family as long as there are no shifts'''.
  
  
''Hinweis:'' &nbsp; Die Animation &nbsp;[[Applets:OVSF-Codes_(Applet)|OVSF–Codes]]&nbsp; zeigt den Konstruktionsalgorithmus dieser Codes und die zulässige Auswahl der Spreizfolgen.  
+
'''Note:''' &nbsp; The&nbsp; (German language)&nbsp; SWF applet&nbsp; [[Applets:OVSF-Codes_(Applet)|OVSF codes]]&nbsp; shows the construction algorithm of these codes and the allowed selection of spreading sequences.
  
  
==Aufgaben zum Kapitel==
+
==Exercises for the chapter==
 
<br>
 
<br>
  
[[Aufgaben: 5.3 PAKF von PN–Sequenzen|Aufgabe 5.3: PAKF von PN–Sequenzen]]
+
[[Aufgaben:Exercise_5.3:_PACF_of_PN_Sequences|Exercise 5.3: PACF of PN Sequences]]
  
[[Aufgaben:5.3Z Realisierung einer PN–Sequenz|Aufgabe 5.3Z: Realisierung einer PN–Sequenz]]
+
[[Aufgaben:Exercise_5.3Z:_Realization_of_a_PN_Sequence|Exercise 5.3Z: Realization of a PN Sequence]]
  
[[Aufgaben: 5.4 Walsh–Funktionen (PKKF, PAKF)|Aufgabe 5.4: &nbsp; Walsh–Funktionen (PKKF, PAKF)]]
+
[[Aufgaben:Exercise_5.4:_Walsh_Functions_(PCCF,_PACF)|Exercise 5.4: Walsh Functions (PCCF, PACF)]]
  
[[Aufgaben:5.4Z OVSF–Codes|Zusatzaufgabe 5.4Z: &nbsp; OVSF–Codes]]
+
[[Aufgaben:Exercise_5.4Z:_OVSF_Codes|Exercise 5.4Z: OVSF Codes]]
  
  
  
==Quellenverzeichnis==
+
==References==
 
<references/>
 
<references/>
  
 
{{Display}}
 
{{Display}}

Revision as of 15:00, 9 April 2022

Properties of the correlation functions


Important evaluation criteria for spreading sequences are the correlation functions.

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

$$\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 model 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 bindings of a stationary and ergodic process defined by the model 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 bindings and the mutual statistical dependencies in the time domain.  The corresponding description functions in the frequency domain are


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 PSD  ${\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 $($integer 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)$,  the PACF progression between two samples  $λ · 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 spreading 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 intersymbol interference.
  • The disruptive 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


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.  

PN generator  (realization with shift registers)
Polynomials of M-sequences with degree  $G$
  • 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":

  • 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 on the right,  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  "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$
PACF of a PN sequence of maximum length  $P = 2^G – 1$
  • 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.
  • For the left generator:  $\rm (11001)_{binary} = (31)_{octal}$.  The corresponding generator polynomial is:
$$G_1(D) = D^4 + D^3 +1\hspace{0.05cm}.$$
  • For the right generator:  $\rm (10011)_{binary} = (23)_{octal}$.  This generator can be described by the polynomial
$$G_2(D) =D^4 + D +1 \hspace{0.05cm}.$$
  • The polynomial  $G_2(D)$  is reciprocal to  $G_{\rm 1}(D)$:
$$G_{\rm 2}(D) = D^4 \cdot (D^{-4} + D^{-3} +1) =D^4 + D +1 \hspace{0.05cm}.$$

Since both  $G_1(D)$  and  $G_{\rm 2}(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 unipolar representation   ⇒   $c_ν ∈ \{0, 1\}$  results in

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

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

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


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 – powerfullness

Furthermore, the term  powerfulness  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][1].


The last row in the above table makes it clear that the powerfulness of M-sequence code families is extremely limited,  even if  $G$  is large and thus the period length  $P$ is large, too.  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 powerfulness are obtained,  so that more CDMA subscribers can also be supplied.

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}.$$
Gold code generator  $(51, 75)$  of degree  $G = 5$

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 $J -1$  spreading sequences that can be constructed with it.

  • $J - 1$ because the sequence  $w_0(t)$  without spreading effect 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 HTML5/JavaScript applet  Generation of 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


The so-called  OVSF codes  ("Orthogonal Variable Spreading Factor")  can be created with the help of a code tree.  Thereby two new codes  $(+C \ +\hspace{-0.05cm}C)$  and  $(+C \ -\hspace{-0.05cm}C)$  are created at each branching from a code  $C$,  as indicated in the graphic above right.

It should be noted that no predecessor and successor of a code may be used by other participants.  In this example,  the following selection could therefore be made  (among others):

  • eight codes with the spreading factor  $J = 8$,  or
  • the four highlighted codes – once with  $J = 2$, once with  $J = 4$  and twice with  $J = 8$.


In the second case, the other six  $J = 8$  codes cannot be used because they begin with  "$+1 \ +\hspace{-0.05cm}1$"  or with  "$+1 \ -\hspace{-0.05cm}1 \ +\hspace{-0.05cm}1 \ -\hspace{-0.05cm}1$". 

From the four spreading sequences in the graphic at the bottom right,  it can be seen that with a constant chip duration  $T_c$,  the user with spreading factor  $J = 2$  can transmit at a higher data rate than the users with  $J = 4$  or  $J = 8$ because his bit duration  $T_{\rm B}$  is smaller.

From the graph,  we can further see that the periodic cross-correlation function  $\rm (PCCF)$  is always zero at the point  $τ = 0$. 

  • That means:   If one forms the product of any two of these sequences and integrates over the represented time range, the value  $0$  always results.
  • This also means:   An OVSF code is orthogonal to all other OVSF codes of the same family as long as there are no shifts.


Note:   The  (German language)  SWF applet  OVSF codes  shows the construction algorithm of these codes and the allowed selection of spreading sequences.


Exercises for the chapter


Exercise 5.3: PACF of PN Sequences

Exercise 5.3Z: Realization of a PN Sequence

Exercise 5.4: Walsh Functions (PCCF, PACF)

Exercise 5.4Z: OVSF Codes


References

  1. Ziemer, R.; Peterson, R. L.:  Digital Communication and Spread Spectrum Systems. New York: McMillon, 1985.