Difference between revisions of "Theory of Stochastic Signals/Auto-Correlation Function"

From LNTwww
 
(80 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
   
 
   
 
{{Header
 
{{Header
|Untermenü=Zufallsgrößen mit statistischen Bindungen
+
|Untermenü=Random Variables with Statistical Dependence
|Vorherige Seite=Linearkombinationen von Zufallsgrößen
+
|Vorherige Seite=Linear Combinations of Random Variables
|Nächste Seite=Leistungsdichtespektrum (LDS)
+
|Nächste Seite=Power-Spectral Density
 
}}
 
}}
==Zufallsprozesse (1)==
+
==Random processes==
Ein wichtiger Begriff der stochastischen Signaltheorie ist der Zufallsprozess. Nachfolgend sind einige Charakteristika eines solchen ''stochastischen Prozesses'' – diese Bezeichnungen werden sowohl in der Literatur als auch in unserem Tutorial synonym verwendet – zusammengestellt:
+
<br>
*Unter einem Zufallsprozess { $x_i(t)$} verstehen wir ein ''mathematisches Modell'' für ein Ensemble von (vielen) Zufallssignalen, die sich zwar im Detail durchaus voneinander unterscheiden können, trotzdem aber gewisse gemeinsame Eigenschaften aufweisen.  
+
An important concept in stochastic signal theory is the&nbsp; "random process".&nbsp; Below are some characteristics of such a&nbsp; "stochastic process" - these terms are used synonymously both in the literature and in our tutorial.
*Zur Beschreibung eines Zufallsprozesses { $x_i(t)$} gehen wir von der Vorstellung aus, dass beliebig viele, in ihren physikalischen und statistischen Eigenschaften völlig gleiche Zufallsgeneratoren vorhanden sind, von denen jeder ein Zufallssignal $x_i(t)$ liefert.  
+
*Jeder Zufallsgenerator gibt trotz gleicher physikalischer Realisierung ein anderes Zeitsignal $x_i(t)$ ab, das für alle Zeiten von $–∞$ bis $+∞$ existiert. Man bezeichnet dieses spezifische Zufallssignal als das $i$-te ''Mustersignal.''
+
{{BlaueBox|TEXT= 
*Jeder Zufallsprozess beinhaltet mindestens eine stochastische Komponente – zum Beispiel die Amplitude, Frequenz oder Phase eines Nachrichtensignals – und kann daher von einem Beobachter nicht exakt vorausgesagt werden.  
+
$\text{Definitions:}$&nbsp; By a&nbsp; &raquo;'''random process'''&laquo;&nbsp; $\{x_i(t)\}$&nbsp; we understand a mathematical model&nbsp; for an ensemble of (many) random signals,&nbsp; which can and will differ from each other in detail,&nbsp; but nevertheless they have certain common properties.  
*Der Zufallsprozess unterscheidet sich von den sonst in der Wahrscheinlichkeitsrechnung bzw. der Statistik üblichen Zufallsexperimenten dadurch, dass das Ergebnis kein ''Ereignis'' ist, sondern ein ''Funktionsverlauf'' (Zeitsignal).  
+
*To describe a random process&nbsp; $\{x_i(t)\}$&nbsp; we start from the notion that there are any number of random generators,&nbsp; completely identical in their physical and statistical properties,&nbsp; each of which yields a random signal&nbsp; $x_i(t)$.  
*Betrachtet man den Zufallsprozess { $x_i(t)$} zu einem festen Zeitpunkt, so gelangt man wieder zu dem einfacheren Modell von Kapitel 2.1, nach dem das Versuchsergebnis ein Ereignis ist, das einer Zufallsgröße zugeordnet werden kann.  
+
*Each random generator,&nbsp; despite having the same physical realization,&nbsp; outputs a different time signal&nbsp; $x_i(t)$&nbsp; that exists for all times from&nbsp; $-∞$&nbsp; to&nbsp; $+∞$.&nbsp; This specific random signal is called the&nbsp; &raquo;'''$i$-th pattern signal'''&laquo;.  
 +
*Every random process involves at least one stochastic component - for example:&nbsp; the amplitude,&nbsp; frequency,&nbsp; or phase of a message signal - and therefore cannot be accurately predicted by an observer.  
 +
*The random process differs from the usual random experiments in probability theory or statistics in that the result is not an&nbsp; "event"&nbsp; but a&nbsp; "function"&nbsp; (time signal).  
 +
*If we consider the random process&nbsp; $\{x_i(t)\}$&nbsp; at a fixed time,&nbsp; we return to the simpler model from the former chapter&nbsp; [[Theory_of_Stochastic_Signals/From_Random_Experiment_to_Random_Variable|"From Random Experiment to Random Variable"]],&nbsp; according to which the experimental result is an event that can be assigned to a random variable.}}
  
==Zufallsprozesse (2)==
 
Die Aussagen der vorherigen Seite werden nun am Beispiel eines binären Zufallsgenerators verdeutlicht, der – zumindest gedanklich – beliebig oft realisiert werden kann.
 
  
 +
These statements are now illustrated by the example of a binary random generator,&nbsp; which - at least in thought - can be realized arbitrarily often.
  
[[File:P_ID369__Sto_T_4_4_S1_neu.png | Zur Definition der Zufallsprozesse]]
+
{{GraueBox|TEXT= 
 +
$\text{Example 1:}$&nbsp; The graph shows three different pattern signals of a random process with the following properties:
  
 +
[[File:Sto_T_4_4_S1.png|450px|right|frame| On the definition of a random process]]
 +
*The random process&nbsp; $\{x_i(t)\}$&nbsp; consists of an ensemble of rectangular pattern functions,&nbsp; which can be described as follows:
 +
:$$x_i(t)=\sum^{+\infty}_{\nu=-\infty} (a_\nu)_i\cdot g(t-\nu \cdot T ).$$
 +
*The basic pulse&nbsp; $g(t)$&nbsp; has in the range from&nbsp; $-T/2$&nbsp; to&nbsp; $+T/2$&nbsp; the value&nbsp; $2\hspace{0.03cm}\rm V$; outside it is zero and exactly at&nbsp; $\pm T/2$&nbsp; only half as large&nbsp; $(1\hspace{0.03cm}\rm V)$.&nbsp;
 +
*Remember:&nbsp; A pulse,&nbsp; as defined in the chapter&nbsp; [[Signal_Representation/Signal_classification|"Signal Classification"]]&nbsp; in the book&nbsp; "Signal Representation", is both a&nbsp; "deterministic"&nbsp; and&nbsp; "energy-limited"&nbsp; signal.
 +
*The statistics of the random process under consideration is due solely to the dimensionless amplitude coefficients&nbsp; $(a_ν)_i ∈ \{0, 1\}$&nbsp; which are time-indexed by&nbsp; $ν$&nbsp;&nbsp; for the&nbsp; $i$-th pattern function.
 +
*Despite the different signal courses in detail, the sketched signals&nbsp; $x_1(t)$,&nbsp; $x_2(t)$,&nbsp; $x_3(t)$&nbsp; and also all further pattern signals&nbsp; $x_4(t)$,&nbsp; $x_5(t)$,&nbsp; $x_6(t)$, ...&nbsp; have certain common features,&nbsp; which will be elaborated in the following. }}
  
Die Grafik zeigt drei unterschiedliche Mustersignale mit folgenden Eigenschaften:  
+
==Stationary random processes==
*Der hier vorliegende Zufallsprozess { $x_i(t)$} besteht aus einem Ensemble rechteckförmiger Musterfunktionen, die jeweils wie folgt beschrieben werden können:
+
<br>
$$x_i(t)=\sum^{+\infty}_{\nu=-\infty} (a_\nu)_i\cdot g(t-\nu \cdot T ).$$
+
[[File:EN_Sto_T_4_4_S2.png|450px |right|frame| On the definition of stationary random processes]]
*Der Grundimpuls $g(t)$ besitzt im Bereich von $–T/2$ bis $+T/2$ den Wert 2V; außerhalb ist er 0. Unter einem Impuls verstehen wir gemäß der Definition im Buch „Signaldarstellung” ein sowohl ''deterministisches'' als auch ''energiebegrenztes'' Signal.
+
If one defines the instantaneous value of all pattern functions&nbsp; $x_i(t)$&nbsp; at a fixed time&nbsp; $t = t_1$&nbsp; as a new random variable&nbsp; $x_1 = \{ x_i(t_1)\}$,&nbsp; its statistical properties can be described according to the statements
*Die Statistik des hier betrachteten Zufallsprozesses ist aomit allein auf die dimensionslosen Amplitudenkoeffizienten $(a_ν)_i ∈$ {0, 1} zurückzuführen, die bei der $i$-ten Musterfunktion mit dem Zeitindex $ν$ versehen sind.
+
*of the second chapter&nbsp; "Discrete Random Variables"&nbsp; and
*Trotz der im Detail unterschiedlichen Signalverläufe weisen die skizzierten Mustersignale $x_1(t), x_2(t) , x_3(t)$ und auch alle weiteren Mustersignale $x_4(t), x_5(t), x_6(t),$ ... gewisse Gemeinsamkeiten auf, die nachfolgend herausgearbeitet werden sollen.  
+
*of the third chapter&nbsp; "Continuous Random Variables"&nbsp; in this book.
  
==Stationäre Zufallsprozesse==
 
Definiert man den Momentanwert aller Musterfunktionen $x_i(t)$ zu einem festen Zeitpunkt $t = t_1$ als eine neue Zufallsgröße $x_1 =$ { $x_i(t_1)$}, so lassen sich deren statistische Eigenschaften nach den Aussagen von Kapitel 2  und Kapitel 3  beschreiben. In gleicher Weise erhalten wir für den Betrachtungszeitpunkt $t = t_2$ die Zufallsgröße $x_2 =$ { $x_i(t_2)$}.
 
  
''Hinweis:'' Beachten Sie bitte, dass $x_1(t)$ und $x_2(t)$ Musterfunktionen des Zufallsprozesses { $x_i(t)$} sind, während die Zufallsgrößen $x_1$ und $x_2$ den Prozess zu den Zeiten $t_1$ und $t_2$ charakterisieren.  
+
Similarly, for the time of observation&nbsp; $t = t_2$&nbsp; we obtain the random variable&nbsp; $x_2 = \{ x_i(t_2)\}$.  
  
  
[[File:P_ID370__Sto_T_4_4_S2_neu.png | Zur Definition stationärer Zufallsprozesse]]
+
Note on nomenclature:  
 +
*$x_1(t)$&nbsp; and&nbsp; $x_2(t)$&nbsp; are&nbsp; "pattern functions"&nbsp; of the random process&nbsp; $\{x_i(t)\}$&nbsp;,
 +
*while the random variables&nbsp; $x_1$&nbsp; and&nbsp; $x_2$&nbsp; "characterize the whole process"&nbsp; at times&nbsp; $t_1$&nbsp; and&nbsp; $t_2$&nbsp; resp.  
  
  
Die Berechnung der statistischen Kenngrößen muss durch Scharmittelung über alle möglichen Musterfunktionen erfolgen (Mittelung über die Laufvariable $i$, also über alle Realisierungen).
+
The calculation of the statistical characteristics must be done
 +
:by&nbsp; &raquo;'''coulter averaging'''&laquo;&nbsp; over all possible pattern functions &nbsp;
 +
:&rArr; &nbsp; averaging over the control variable&nbsp; $i$, i.e. over all realizations.
 +
<br clear=all>
 +
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp;
 +
For a&nbsp; &raquo;'''stationary random process'''&laquo;&nbsp; $\{x_i(t)\}$&nbsp; all statistical parameters&nbsp; $($mean, standard deviation, higher order moments, probabilities, etc. $)$&nbsp; of the random variables&nbsp; $x_1 = \{ x_i(t_1)\}$&nbsp; and&nbsp; $x_2 = \{ x_i(t_2)\}$&nbsp; are equal.
 +
 +
*Also at other times,&nbsp; the values are exactly the same.
 +
*The converse is: &nbsp; One calls a random process&nbsp; $\{x_i(t)\}$&nbsp; a&nbsp; "non-stationary process"&nbsp;  if it has different statistical properties at different times. }}
  
{{Definition}}
+
 
Bei einem stationären Zufallsprozess { $x_i(t)$} sind alle statistischen Kenngrößen der Zufallsgrößen $x_1$ und $x_2$ gleich. Auch zu jedem anderen Zeitpunkt ergeben sich genau gleiche Werte.  
+
{{GraueBox|TEXT= 
{{end}}
+
$\text{Example 2:}$&nbsp; 
 +
A large number of measuring stations at the equator determine the temperature daily at 12 o'clock local time.&nbsp;
 +
*If one averages over all these measured values,&nbsp;  one can eliminate the influence of local indicators (e.g. Gulf Stream).&nbsp;
 +
*If one plots the mean values&nbsp; (coulter averaging)&nbsp; over time,&nbsp; almost a constant will result,&nbsp; and one can speak of a "stationary process".
 +
*A comparable series of measurements at 50° latitude would indicate a&nbsp; "non-stationary process"&nbsp; due to the seasonal variations,&nbsp; with significant differences in mean and variance of the noon temperature between January and July.
 +
}}
 +
 
 +
==Ergodic random processes==
 +
<br>
 +
An important subclass of stationary random processes are the so-called&nbsp; "ergodic processes"&nbsp; with the following properties:
 +
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp; In an&nbsp; &raquo;'''ergodic process'''&laquo;&nbsp; $\{x_i(t)\}$&nbsp; each individual pattern function&nbsp; $x_i(t)$&nbsp; is representative of the entire ensemble.
 +
 
 +
*All statistical descriptive variables of an ergodic process can be obtained from a single pattern function by time averaging&nbsp; <br>$($referring to the control variables&nbsp; $ν = t/T$ &nbsp; &rArr; &nbsp; normalized time$)$&nbsp; .  
 +
*This also means: &nbsp; '''With ergodicity,&nbsp; the time averages of each pattern function coincide with the corresponding coulter averages at arbitrary time points&nbsp; $ν$'''.&nbsp; }}
  
  
Die Umkehrung lautet: Man bezeichnet einen Zufallsprozess { $x_i(t)$} als ''nichtstationär,'' wenn er zu verschiedenen Zeitpunkten unterschiedliche statistische Eigenschaften (Mittelwert, Streuung, Momente höherer Ordnung, Auftrittswahrscheinlichkeiten, etc.) aufweist.  
+
[[File:EN_Sto_T_4_4_S3.png|450px |right|frame|450px| On the definition of ergodic random processes]]
 +
For example,&nbsp; with ergodicity,&nbsp; for the moment&nbsp; $k$-th order:
 +
:$$m_k=\overline{x^k(t)}={\rm E}\big[x^k\big].$$
 +
Here,&nbsp; the sweeping line denotes the time mean,&nbsp; while the coulter mean is to be determined by expected value generation&nbsp; $\rm E\big[ \hspace{0.1cm}\text{...} \hspace{0.1cm} \big]$&nbsp; as described in chapter&nbsp; [[Theory_of_Stochastic_Signals/Moments_of_a_Discrete_Random_Variable|"Moments of a discrete random variable"]].
  
{{Beispiel}}
 
Eine große Anzahl von Mess-Stationen am Äquator ermitteln täglich um 12 Uhr Ortszeit die Temperatur. Mittelt man über all diese Messwerte, so kann man den Einfluss lokaler Indikatoren (z. B. Golfstrom) eliminieren. Trägt man die Mittelwerte (Scharmittelung) über der Zeit auf, so wird sich nahezu eine Konstante ergeben, und man kann von einem ''stationären Prozess'' sprechen.
 
  
Eine vergleichbare Messreihe am 50. Breitengrad würde aufgrund der jahreszeitlichen Schwankungen auf einen ''nichtstationären Prozess'' hinweisen mit deutlichen Unterschieden hinsichtlich Mittelwert und Varianz der Mittagstemperatur zwischen Januar und Juli.
 
{{end}}
 
  
==Ergodische Zufallsprozesse==
 
Eine wichtige Unterklasse der stationären Zufallsprozesse sind die so genannten ergodischen Prozesse mit folgenden Eigenschaften:
 
*Bei einem ergodischen Prozess { $x_i(t)$} ist jede einzelne Musterfunktion $x_i(t)$ repräsentativ für das gesamte Ensemble. 
 
*Alle statistischen Beschreibungsgrößen eines ergodischen Prozesses kann man aus einer einzigen Musterfunktion durch Zeitmittelung (bezüglich der Laufvariablen $ν$) gewinnen.
 
*Das bedeutet auch: Bei Ergodizität stimmen die Zeitmittelwerte einer jeden Musterfunktion mit den entsprechenden Scharmittelwerten zu beliebigen Zeitpunkten überein.
 
*Beispielsweise gilt bei Ergodizität für das Moment $k$-ter Ordnung:
 
$$m_k=\overline{x^k(t)}={\rm E}[x^k].$$
 
  
 +
'''Note:''' &nbsp;
 +
#Ergodicity cannot be proved from a finite number of pattern functions and finite signal sections.
 +
#However, ergodicity is hypothetically - but nevertheless quite justifiably - assumed in most applications.
 +
#On the basis of the results found,&nbsp; the plausibility of this&nbsp; &raquo;'''ergodicity hypothesis'''&laquo;&nbsp; must subsequently be checked.
 +
<br clear=all>
 +
==Generally valid description of random processes==
 +
<br>
 +
If the random process&nbsp; $\{x_i(t)\}$&nbsp;  to be analyzed is not stationary and thus certainly not ergodic,&nbsp; the moments must always be determined as coulter averages.&nbsp;
 +
*In general,&nbsp; these are time-dependent:
 +
:$$m_k(t_1) \ne m_k(t_2).$$
 +
*However,&nbsp; since by the moments also the&nbsp; [[Theory_of_Stochastic_Signals/Expected_Values_and_Moments#Characteristic_function|$\text{characteristic function}$]]&nbsp; (Fourier retransform of the PDF):
 +
:$$ C_x(\Omega) ={\rm\sum^{\infty}_{{\it k}=0}}\ \frac{m_k}{k!}\cdot \Omega^{k}\ \circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\,\ f_{x}(x)$$
 +
:is fixed,&nbsp; the probability density function $f_{x}(x)$&nbsp; is also time-dependent.
  
Die überstreichende Linie kennzeichnet hierbei den Zeitmittelwert, während der Scharmittelwert durch Erwartungswertswertbildung E[ ... ] zu ermitteln ist, wie in Kapitel 2.2  beschrieben.
+
*If not only the amplitude distributions at different times&nbsp; $t_1,&nbsp; t_2$, ...&nbsp; are to be determined,&nbsp; but also the statistical bindings between the signal values at these times,&nbsp; one has to pass to the&nbsp; [[Theory_of_Stochastic_Signals/Two-Dimensional_Random_Variables#Joint_probability_density_function|$\text{two-dimensional probability density function}$]].  
  
  
[[File:P_ID371__Sto_T_4_4_S3_neu.png | Zur Definition ergodischer Zufallsprozesse]]
+
For example,&nbsp; considering the two time points&nbsp; $t_1$&nbsp; and&nbsp; $t_2$,&nbsp; note the following:
 +
#The two-dimensional PDF is obtained according to the specifications in section&nbsp; [[Theory_of_Stochastic_Signals/Two-Dimensional_Random_Variables#Properties_and_examples|"Properties and examples of two-dimensional random variables"]]&nbsp; with&nbsp; $x = x(t_1)$&nbsp; and&nbsp; $y = x(t_2)$.&nbsp; It is obvious that already the determination of this variable is very complex.
 +
#If one further considers that to capture all statistical bindings within the random process actually the&nbsp; $n$-dimensional probability density function would have to be used,&nbsp; where if possible the limit&nbsp; $n → ∞$&nbsp; still has to be formed,&nbsp; one recognizes the difficulties for the solution of practical problems.
 +
#For these reasons,&nbsp; in order to describe the statistical bindings of a random process,&nbsp; one proceeds to the auto-correlation function,&nbsp; which simplifies the problem.&nbsp; This is first defined in the following section for the general case.
  
 +
==General definition of the auto-correlation function==
 +
<br>
 +
{{BlaueBox|TEXT= 
 +
$\text{General Definition:}$&nbsp;
  
'''Anmerkung:''' Die Ergodizität lässt sich aus einer endlichen Anzahl von Musterfunktionen und endlichen Signalausschnitten nicht nachweisen. Allerdings wird in den meisten Anwendungen zwar hypothetisch – aber trotzdem durchaus berechtigt – von Ergodizität ausgegangen. Anhand der gefundenen Ergebnisse muss anschließend die Plausibilität dieser Ergodizitätshypothese überprüft werden.  
+
The&nbsp; &raquo;'''auto-correlation function'''&laquo;&nbsp; $\rm (ACF)$&nbsp; of a random process&nbsp; $\{x_i(t)\}$&nbsp; is equal to the expected value of the product of the signal values at two time points&nbsp; $t_1$&nbsp; and&nbsp; $t_2$:
 +
:$$\varphi_x(t_1,t_2)={\rm E}\big[x(t_{\rm 1})\cdot x(t_{\rm 2})\big].$$
 +
This definition holds whether the random process is ergodic or non-ergodic,&nbsp; and it also holds in principle for non-stationary processes. }}
  
==Allgemeingültige Beschreibung von Zufallsprozessen==
 
Ist der zu analysierende Zufallsprozess { $x_i(t)$} nicht stationär und damit mit Sicherheit auch nicht ergodisch, so müssen die Momente stets als Scharmittelwerte bestimmt werden. Im Allgemeinen sind diese zeitabhängig:
 
$$m_k(t_1) \ne m_k(t_2).$$
 
Da durch die Momente aber auch die charakteristische Funktion (Fourierrücktransformierte der WDF)
 
$$ C_x(\Omega) ={\rm\sum^{\infty}_{{\it k}=0}}\frac{m_k}{k!}\cdot \Omega^{k}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\,f_{\rm x}(x)$$
 
festliegt, ist die Wahrscheinlichkeitsdichtefunktion $f_{\rm x}(x)$ ebenfalls zeitabhängig.
 
  
Sollen nun nicht nur die Amplitudenverteilungen zu den verschiedenen Zeitpunkten $t_1, t_2,$ ... ermittelt werden, sondern auch die statistischen Bindungen zwischen den Signalwerten zu diesen Zeiten, so muss man auf die zweidimensionale Verbundwahrscheinlichkeitsdichtefunktion übergehen.
+
:Note on nomenclature:
  
 +
:In order to establish the relationship with the&nbsp; [[Theory_of_Stochastic_Signals/Cross-Correlation_Function_and_Cross_Power_Density|$\text{cross-correlation function}$]]&nbsp; $φ_{xy}$&nbsp; between the two statistical variables&nbsp; $x$&nbsp; and&nbsp; $y$&nbsp; to make clear,&nbsp;  in some literature for the auto-correlation function instead of&nbsp;  $\varphi_x$&nbsp;  the notation&nbsp;  $\varphi_{xx}$&nbsp; is also often used.&nbsp;  In our learning tutorial,&nbsp; we refrain from doing so.
  
Betrachtet man beispielsweise die beiden Zeitpunkte $t_1$ und $t_2$, so ist folgendes zu vermerken:
 
*Die 2D-WDF ergibt sich entsprechend den Angaben in Kapitel 4.1  mit $x = x(t_1)$ und $y = x(t_2)$. Es ist offensichtlich, dass bereits die Ermittlung dieser Größe sehr aufwändig ist.
 
*Berücksichtigt man weiter, dass zur Erfassung aller statistischen Bindungen innerhalb des Zufallsprozesses eigentlich die $n$-dimensionale Verbundwahrscheinlichkeitsdichtefunktion (VWDF) herangezogen werden müsste, wobei möglichst noch der Grenzwert $n → ∞$ zu bilden ist, so erkennt man die Schwierigkeiten für die Lösung praktischer Probleme.
 
*Aus diesen Gründen geht man zur Beschreibung der statistischen Bindungen eines Zufallsprozesses auf die Autokorrelationsfunktion über, die nachfolgend definiert wird.
 
  
==Allgemeine Definition der Autokorrelationsfunktion==
+
A comparison with the section&nbsp; [[Theory_of_Stochastic_Signals/Two-Dimensional_Random_Variables#Expected_values_of_two-dimensional_random_variables|"Expected values of two-dimensional random variables"]]&nbsp; shows that the ACF&ndash;value&nbsp; $φ_x(t_1, t_2)$&nbsp; indicates the joint moment&nbsp; $m_{11}$&nbsp; between the two random variables&nbsp; $x(t_1)$&nbsp; and&nbsp; $x(t_2)$.  
{{Definition}}
 
Die Autokorrelationsfunktion (AKF) eines beliebigen Zufallsprozesses { $x_i(t)$} ist gleich dem Erwartungswert des Produkts der Signalwerte zu zwei Zeitpunkten $t_1$ und $t_2$:
 
$$\varphi_x(t_1,t_2)={\rm E}[x(t_{\rm 1})\cdot x(t_{\rm 2})].$$
 
Diese Definition gilt unabhängig davon, ob der Zufallsprozess ergodisch oder nichtergodisch ist, und sie gilt auch für nichtstationäre Prozesse.  
 
{{end}}
 
  
 +
While exact statements regarding the statistical bindings of a random process actually require the&nbsp; $n$&ndash;dimensional joint probability density&nbsp; $($with&nbsp; $n → ∞)$,&nbsp; the following simplifications are implicitly made by moving to the auto-correlation function:
 +
#Instead of infinitely many time points,&nbsp; only two are considered here,&nbsp; and instead of all moments&nbsp; $m_{\hspace{0.05cm}k\hspace{0.05cm}l}$&nbsp; at the two time points&nbsp; $t_1$&nbsp; and&nbsp; $t_2$&nbsp; with&nbsp; $k, \ l ∈ \{1, 2, 3, \text{...} \}$&nbsp; only the joint moment&nbsp; $m_{11}$&nbsp; is captured.
 +
#The moment&nbsp; $m_{11}$&nbsp; exclusively reflects the linear dependence&nbsp; ("correlation")&nbsp; of the process.&nbsp; All higher order statistical bindings,&nbsp; on the other hand,&nbsp; are not considered.
 +
#Therefore,&nbsp; when evaluating random processes by means of ACF,&nbsp; it should always be taken into account that it allows only very limited statements about the statistical bindings in general.
  
Ein Vergleich mit Kapitel 4.1  zeigt, dass der AKF-Wert $φ_x(t_1, t_2)$ das gemeinsame Moment $m_{11}$ zwischen den beiden Zufallsgrößen $x(t_1)$ und $x(t_2)$ angibt.
 
  
''Hinweis:'' Um den Zusammenhang mit der Kreuzkorrelationsfunktion $φ_{xy}$ zwischen den beiden statistischen Größen $x$ und $y$ deutlich zu machen (siehe Kapitel 4.6), wird in mancher Literatur für die AKF auch häufig die Schreibweise $φ_{xx}(t_1, t_2)$ verwendet.  
+
{{GraueBox|TEXT= 
 +
$\text{Example 3:}$&nbsp; The above definition of the auto-correlation function applies in general,&nbsp; i.e. also to non-stationary and non-ergodic processes.  
  
Während für exakte Aussagen hinsichtlich der statistischen Bindungen eines Zufallsprozesses eigentlich die $n$-dimensionale Verbunddichte (mit $n → ∞$) benötigt wird, werden durch den Übergang auf die Autokorrelationsfunktion implizit folgende Vereinfachungen getroffen:
+
*An example of a non-stationary process is the occurrence of&nbsp; "intersymbol interference"&nbsp; in the telephone network caused by dial pulses in adjacent lines.  
*Anstelle von unendlich vielen Zeitpunkten werden hier nur zwei betrachtet.  
+
*In digital signal transmission,&nbsp; such non-stationary interference processes usually lead to trunking errors.}}
*Anstelle aller Momente $m_{kl}$ zu den beiden Zeitpunkten $t_1$ und $t_2$ mit $k, l ∈$ {1, 2, 3, ...} wird hier nur das gemeinsame Moment $m_{11}$ erfasst.
 
*Das Moment $m_{11}$ gibt ausschließlich die lineare Abhängigkeit (Korrelation) des Prozesses wieder. Alle statistische Bindungen höherer Ordnung werden dagegen nicht berücksichtigt.
 
*Deshalb sollte bei der Bewertung von Zufallsprozessen mittels AKF stets berücksichtigt werden, dass diese nur sehr beschränkte Aussagen über die statistischen Bindungen erlaubt.
 
  
  
Die obige Definition der Autokorrelationsfunktion gilt allgemein, also auch für nichtstationäre und nichtergodische Prozesse. Ein Beispiel eines nichtstationären Vorgangs ist das Auftreten von Impulsstörungen im Fernsprechnetz, verursacht durch Wählimpulse in benachbarten Leitungen. Bei Digitalsignalübertragung führen solche nichtstationären Störprozesse meist zu Bündelfehlern.  
+
==Auto-correlation function for stationary and ergodic processes==
 +
<br>
 +
[[File:EN_Sto_T_4_4_S8.png|400px |right|frame| On the auto-correlation function in ergodic processes]]
 +
In the following,&nbsp; we restrict ourselves to stationary and ergodic processes.
  
==Autokorrelationsfunktion bei ergodischen Prozessen (1)==
+
Such a random process&nbsp; $\{x_i(t)\}$&nbsp; is e.g. used as a basis in the study of&nbsp; [[Aufgaben:Exercise_1.3Z:_Thermal_Noise|$\text{thermal noise}$]].&nbsp; This is based on the notion that
Im Folgenden beschränken wir uns auf stationäre und ergodische Prozesse. Ein solcher Prozess { $x_i(t)$} wird zum Beispiel bei der Untersuchung von Thermischem Rauschen zugrunde gelegt. Dabei wird von der Vorstellung ausgegangen, dass beliebig viele, in ihren physikalischen und statistischen Eigenschaften völlig gleiche Widerstände vorhanden sind, von denen jeder ein anderes Zufallssignal $x_i(t)$ abgibt.  
+
*there are any number of resistors, completely identical in their physical and statistical properties,  
 +
*each of which emits a different random signal&nbsp; $x_i(t)$&nbsp;.  
  
 +
<br><br>
 +
The graphic shows such a stationary and ergodic process:
 +
#The individual pattern functions&nbsp; $x_i(t)$&nbsp; can take on any arbitrary values at any arbitrary times.&nbsp; This means that the random process&nbsp; $\{x_i(t)\}$&nbsp; considered here is both continuous in value and continuous in time.
 +
#Although no conclusions can be drawn about the actual signal values of the individual pattern functions due to stochasticity,&nbsp; $\{x_i(t)\}$&nbsp; the moments and the PDF are the same at all time points.
 +
#In the graph,&nbsp;  for reasons of a generalized representation,&nbsp; a DC component&nbsp; $m_x$&nbsp; is also considered,&nbsp; which is not present in thermal noise.
 +
<br clear=all>
 +
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp; One speaks of a&nbsp; &raquo;'''stationary random process'''&laquo;&nbsp; $\{x_i(t)\}$ if its statistical properties are invariant to time shifts.
  
[[File:P_ID372__Sto_T_4_4_S6_neu.png | Zur Autokorrelationsfunktion bei ergodischen Prozessen]]
+
*For the auto-correlation function&nbsp; $\rm (ACF)$,&nbsp; this statement means that it is no longer a function of the two independent time variables&nbsp; $t_1$&nbsp; and&nbsp; $t_2$&nbsp; but depends only on the time difference&nbsp; $τ = t_2 - t_1$&nbsp;:
 +
:$$\varphi_x(t_1,t_2)\ \rightarrow \ {\varphi_x(\tau)={\rm E}\big[x(t)\cdot x(t+\tau)\big]}.$$
 +
*The coulter averaging can be done at any time&nbsp; $t$&nbsp; in this case. }}
  
  
Zu dieser Grafik ist anzumerken:
+
#Under the further assumption of an ergodic random process,&nbsp; all moments can also be obtained by time averaging over a single selected pattern function&nbsp; $x(t)$.&nbsp;
*Die einzelnen Musterfunktionen $x_i(t)$ können zu allen beliebigen Zeiten alle beliebigen Werte annehmen. Das bedeutet, dass der hier betrachtete Zufallsprozess { $x_i(t)$} sowohl wert– als auch zeitkontinuierlich ist.  
+
#All these time averages coincide with the corresponding coulter averages in this special case.  
*Auch wenn über die tatsächlichen Signalwerte der einzelnen Musterfunktionen aufgrund der Stochastik keine Aussagen getroffen werden können, so sind die Momente und die WDF zu allen Zeitpunkten gleich.
 
*In obiger Grafik ist aus Gründen einer verallgemeinerten Darstellung auch ein Gleichanteil $m_x$ berücksichtigt, der bei Thermischem Rauschen nicht vorhanden ist.  
 
  
==Autokorrelationsfunktion bei ergodischen Prozessen (2)==
 
{{Definition}}
 
Von einem stationären Zufallsprozess { $x_i(t)$} spricht man, wenn seine statistischen Eigenschaften invariant gegenüber Zeitverschiebungen sind. Für die Autokorrelationsfunktion (AKF) bedeutet diese Aussage, dass sie nicht mehr eine Funktion der beiden unabhängigen Zeitvariablen $t_1$ und $t_2$ ist, sondern nur noch von der Zeitdifferenz $τ = t_2 – t_1$ abhängt:
 
$$\varphi_x(t_1,t_2)\rightarrow{\varphi_x(\tau)={\rm E}[x(t)\cdot x(t+\tau)]}.$$
 
Die Scharmittelung kann dabei zu jeder beliebigen Zeit $t$ erfolgen.
 
{{end}}
 
  
 +
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp; Thus,&nbsp; for the&nbsp; &raquo;'''ACF of an ergodic random process'''&laquo;&nbsp; whose pattern signals each range from&nbsp; $-∞$&nbsp; to&nbsp; $+∞$&nbsp; follows:
 +
:$$\varphi_x(\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}t.$$
 +
*The sweeping line denotes time averaging over the infinitely extended time interval.
 +
*$T_{\rm M}$&nbsp; denotes the measurement duration.  }}
  
Unter der weiteren Annahme eines ergodischen Zufallsprozesses können alle Momente auch durch Zeitmittelung über eine einzige ausgewählte Musterfunktion $x(t)$ ermittelt werden. Diese Zeitmittelwerte stimmen mit den entsprechenden Scharmittelwerten überein.
 
  
{{Box}}
+
For periodic signals,&nbsp;  the boundary crossing can be omitted,&nbsp; so in this special case the auto-correlation function with period&nbsp; $T_0$&nbsp; can also be written in the following way:  
Damit folgt für die AKF eines ergodischen Prozesses, dessen Mustersignale jeweils von $–∞$ bis $+∞$ reichen $(T_{\rm M}$ bezeichnet die Messdauer):  
+
:$$\varphi_x(\tau)=\frac{1}{T_{\rm 0}}\cdot\int^{T_{\rm 0}/2}_{-T_{\rm 0}/2}x(t)\cdot x(t+\tau)\,\,{\rm d}t=\frac{1}{T_{\rm 0}}\cdot\int^{T_{\rm 0}}_{\rm 0}x(t)\cdot x(t+\tau)\,\,{\rm d}t .$$
$$\varphi_x(\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}t.$$
+
It is only important that in total exactly over a period duration&nbsp; $T_0$&nbsp; $($or multiples of it$)$&nbsp; is averaged.&nbsp; It does not matter which time section one uses.  
Die überstreichende Linie kennzeichnet die Zeitmittelung über das unendlich ausgedehnte Zeitintervall.  
 
{{end}}
 
  
 +
==Properties of the auto-correlation function==
 +
<br>
 +
Here we compile important properties of the auto-correlation function&nbsp;  $\rm (ACF)$,&nbsp;  starting from the ergodic ACF&ndash;form&nbsp; $φ_x(τ)$:
 +
*If the random process under consideration is real, so is its auto-correlation function is also real.
 +
*The ACF has the unit of a power, e.g.&nbsp;  "Watt"&nbsp; $\rm (W)$.&nbsp; Often one relates it to the resistance&nbsp; $1\hspace{0.03cm} Ω$;&nbsp; $φ_x(τ)$&nbsp; then with the unit&nbsp; $\rm V^2$&nbsp; resp.&nbsp; $\rm A^2$.
 +
*The ACF is always an even function&nbsp; ⇒ &nbsp; $φ_x(-τ) = φ_x(τ)$. &nbsp; All phase relations of the random process are lost in the ACF.
 +
*The ACF at the point&nbsp; $τ = 0$&nbsp; gives the second order moment&nbsp; $m_2$&nbsp; and thus the total signal power of the random process&nbsp; (DC and AC components):
 +
:$$\varphi_x(\tau = 0)= m_2=\overline{ x^2(t)}.$$
 +
*The ACF maximum always occurs at&nbsp; $τ = 0$.&nbsp; It holds: &nbsp; $|φ_x(τ)| ≤ φ_x(0)$.&nbsp; For non-periodic processes,&nbsp; the magnitude&nbsp; $|φ_x(τ)|$&nbsp; for&nbsp; $τ ≠ 0$&nbsp; is always less than&nbsp; $φ_x(\tau =0)$.
 +
*For a periodic random process, the ACF has the same period&nbsp; $T_0$&nbsp; as the individual pattern signals&nbsp; $x_i(t)$&nbsp; :
 +
:$$\varphi_x(\pm{T_0})=\varphi_x(\pm{2\cdot T_0})= \hspace{0.1cm}\text{...} \hspace{0.1cm}= \varphi_x(0).$$
 +
*The DC component&nbsp; $m_1$&nbsp; of a non-periodic signal can be calculated from the limit of the auto-correlation function for&nbsp; $τ → ∞$.&nbsp; Here,&nbsp; the following holds:
 +
:$$\lim_{\tau\to\infty}\,\varphi_x(\tau)= m_1^2=\big [\overline{ x(t)}\big]^2.$$
 +
*In contrast,&nbsp; for signals with periodic components,&nbsp; the limit value of the ACF for&nbsp; $τ → ∞$&nbsp; varies around this final value&nbsp; (square of the DC component).
  
Bei periodischen Signalen kann man auf den Grenzübergang verzichten, so dass in diesem Sonderfall die Autokorrelationsfunktion mit der Periodendauer $T_0$ auch in folgender Weise geschrieben werden kann:
+
==Interpretation of the auto-correlation function==
$$\varphi_x(\tau)=\frac{1}{T_{\rm 0}}\cdot\int^{T_{\rm 0}/2}_{-T_{\rm 0}/2}x(t)\cdot x(t+\tau)\,\,{\rm d}t=\frac{1}{T_{\rm 0}}\cdot\int^{T_{\rm 0}}_{\rm 0}x(t)\cdot x(t+\tau)\,\,{\rm d}t .$$
+
<br>
Wichtig ist dabei nur, dass insgesamt genau über eine Periodendauer $T_0$ (oder Vielfache davon) gemittelt wird. Es ist egal, welcher Zeitausschnitt dabei verwendet wird.  
+
The graph shows pattern signals of each of two random processes&nbsp; $\{x_i(t)\}$&nbsp; and&nbsp; $\{y_i(t)\}$ at the top,&nbsp; and the corresponding auto-correlation functions at the bottom.
 +
[[File: P_ID373__Sto_T_4_4_S8_neu.png |right|frame| ACF of high-frequency and low-frequency processes]]
 +
Based on these representations,&nbsp; the following statements are possible:
 +
#$\{y_i(t)\}$&nbsp; has stronger internal statistical bindings than&nbsp; $\{x_i(t)\}$.&nbsp; Spectrally,&nbsp; the process $\{y_i(t)\}$&nbsp; is thus lower frequency.
 +
#The sketched pattern signals&nbsp; $x(t)$&nbsp; and&nbsp; $y(t)$&nbsp; already suggest that both processes are zero mean and have the same standard deviation.
 +
#The above auto-correlation functions confirm these statements.&nbsp; The linear mean values&nbsp; $m_x = m_y = 0$&nbsp; result in each case from the ACF limit for&nbsp; $τ → ∞$.
 +
#Because&nbsp; $m_x = 0$&nbsp; applies here to the variance: &nbsp; $σ_x^2 = φ_x(0) = 0.01 \hspace{0.05cm} \rm V^2$, and the standard deviation is consequently&nbsp; $σ_x = 0.1 \hspace{0.05cm}\rm V$.
 +
#$y(t)$&nbsp; has the same variance and and standard deviation as&nbsp; $x(t)$.&nbsp; The ACF values fall off more slowly the stronger the internal statistical bindings are.
 +
#The signal&nbsp; $x(t)$&nbsp; with narrow ACF changes very fast in time,&nbsp; while for the lower frequency signal&nbsp; $y(t)$&nbsp; the statistical bindings are much wider.  
 +
#But this also means that the signal value&nbsp; $y(t + τ)$&nbsp; from&nbsp; $y(t)$&nbsp; can be better predicted than&nbsp; $x(t + τ)$&nbsp; from&nbsp; $x(t)$.  
  
==Eigenschaften der Autokorrelationsfunktion==
 
Nachfolgend sind wichtige Eigenschaften der Autokorrelationsfunktion (AKF) zusammengestellt:
 
*Ist der betrachtete Zufallsprozess reell, so gilt dies auch für seine AKF.
 
*Die AKF besitzt die Einheit einer Leistung, beispielsweise Watt („W”). Häufig bezieht man diese auf den Einheitswiderstand 1 Ω; in diesem Fall hat $φ_x(τ)$ die Einheit $„\rm V^2”$ bzw. $„\rm A^2”.$
 
*Die AKF ist immer eine gerade Funktion  ⇒  $φ_x(–τ) = φ_x(τ)$. Alle Phasenbeziehungen des Zufallsprozesses gehen in der AKF verloren.
 
*Die AKF an der Stelle $τ =$ 0 gibt den quadratischen Mittelwert $m_2$ (Moment 2. Ordnung) und damit die gesamte Signalleistung (Gleich– und Wechselanteil) an:
 
$$\varphi_x(0)= m_2=\overline{ x^2(t)}.$$
 
*Das AKF–Maximum ist stets bei $τ =$ 0, und es gilt: $|φ_x(τ)| ≤ φ_x(0)$. Bei nichtperiodischen Prozessen ist für $τ ≠$ 0 der Betrag $|φ_x(τ)|$ stets kleiner als die Leistung $φ_x(0)$.
 
*Bei einem periodischen Zufallsprozess weist die AKF die gleiche Periodendauer $T_0$ wie die einzelnen Mustersignale $x_i(t)$ auf:
 
$$\varphi_x(\pm{T_0})=\varphi_x(\pm{2\cdot T_0})= \hspace{0.1cm}... \hspace{0.1cm}= \varphi_x(0).$$
 
*Der Gleichanteil $m_1$ eines nichtperiodischen Signals kann aus dem Grenzwert der AKF für $τ → ∞$ berechnet werden. Hierbei gilt:
 
$$\lim_{\tau\to\infty}\,\varphi_x(\tau)= m_1^2=[\overline{ x(t)}]^2.$$
 
*Dagegen schwankt bei Signalen mit periodischen Anteilen der Grenzwert der AKF für $τ → ∞$ um diesen Endwert (Quadrat des Gleichanteils).
 
  
==Interpretation der Autokorrelationsfunktion==
+
{{BlaueBox|TEXT=
Das nachfolgende Bild zeigt oben je ein Mustersignal zweier verschiedener Prozesse { $x_i(t)$} und { $y_i(t)$}, unten die zugehörigen Autokorrelationsfunktionen. Der Prozess { $y_i(t)$} weist stärkere innere statistische Bindungen auf als { $x_i(t)$}. Spektral gesehen ist er niederfrequenter.
+
$\text{Definition:}$&nbsp; A quantitative measure of the strength of statistical bindings is the&nbsp; &raquo;'''equivalent ACF duration'''&laquo;&nbsp; $∇τ$&nbsp; ("Nabla-tau"),&nbsp; which can be determined from the ACF over the equal-area rectangle:
 +
:$${ {\rm \nabla} }\tau =\frac{1}{\varphi_x(0)}\cdot\int^{\infty}_{-\infty}\ \varphi_x(\tau)\,\,{\rm d}\tau. $$
 +
}}  
  
  
[[File: P_ID373__Sto_T_4_4_S8_neu.png | AKF von hochfrequenten und niederfrequenten Prozessen]]
+
*For the processes considered here&nbsp; (with Gaussian-like ACF)&nbsp; holds according to the above sketch: &nbsp; $∇τ_x = 0.33 \hspace{0.05cm} \rm &micro; s$ &nbsp; resp. &nbsp; $∇τ_y = 1 \hspace{0.05cm} \rm &micro;s$.
 +
*As another measure of the strength of the statistical bindings, the&nbsp; [[Digital_Signal_Transmission/Burst_Error_Channels#Error_correlation_function_of_the_Gilbert-Elliott_model|$\text{correlation duration}$]]&nbsp; $T_{\rm K}$&nbsp; is often used in the literature.&nbsp;
 +
*This indicates the time duration at which the auto-correlation function has dropped to half of its maximum value.
  
 +
==Numerical ACF determination==
 +
<br>
 +
So far,&nbsp; we have always considered continuous-time signals&nbsp; $x(t)$&nbsp; which are unsuitable for representation and simulation by means of digital computers.&nbsp; Instead,&nbsp; a discrete-time signal representation&nbsp; $〈x_ν〉$&nbsp; is required for this purpose,&nbsp; as outlined in the chapter&nbsp; [[Signal_Representation/Discrete-Time_Signal_Representation|"Discrete-Time Signal Representation"]]&nbsp; of our first book.
  
Anhand dieser Grafiken sind folgende Aussagen möglich:  
+
Here is a brief summary:  
*Die beiden Mustersignale lassen bereits vermuten, dass beide Prozesse mittelwertfrei sind den gleichen Effektivwert aufweisen.
 
*Anhand der Autokorrelationsfunktionen werden diese Aussagen bestätigt. Die liearen Mittelwerte $m_x = m_y =$ 0 ergeben sich jeweils aus dem AKF-Grenzwert für $τ → ∞$.
 
*Wegen $m_x =$ 0 gilt für die Varianz: $σ_x^2 = φ_x(0) = 0.01 \rm V^2$, und der Effektivwert ist somit $σ_x = 0.1 \rm V$. Das Signal $y(t)$ weist die gleiche Varianz und und den gleichen Effektivwert auf.
 
*Die AKF-Werte fallen um so langsamer ab, je stärker die inneren statistischen Bindungen sind. Während sich das Signal $x(t)$ mit relativ schmaler AKF zeitlich sehr schnell ändert, reichen bei dem niederfrequenteren Signal $y(t)$ die statistischen Bindungen deutlich weiter.
 
*Das bedeutet aber auch, dass der Signalwert $y(t + τ)$ aus $y(t)$ besser vorhergesagt werden kann als $x(t + τ)$ aus $x(t)$.
 
*Eine quantitative Kenngröße für die Stärke der statistischen Bindungen ist die äquivalente AKF-Dauer $∇τ$, die sich aus der AKF über das flächengleiche Rechteck ermitteln lässt:
 
$${ {\rm \nabla} }\tau =\frac{1}{\varphi_x(0)}\cdot\int^{\infty}_{-\infty}\ \varphi_x(\tau)\,\,{\rm d}\tau. \hspace{2cm} \it {Hinweis:} \ {\rm Man \ spricht \ „Nabla–tau”.} $$
 
:Beim hier betrachteten Prozess (mit gaußähnlicher AKF) ist $∇τ =$ 0.33 μs bzw. $∇τ =$ 1 μs.
 
*Als ein weiteres Maß für die Stärke der statistischen Bindungen wird in der Literatur häufig die Korrelationsdauer $T_{\rm K}$ verwendet. Diese gibt die Zeitdauer an, bei der die AKF auf die Häfte ihres Maximalwertes abgefallen ist.
 
  
==Numerische AKF-Ermittlung (1)==
+
*The discrete-time signal&nbsp; $〈x_ν〉$&nbsp; is the sequence of samples&nbsp; $x_ν = x(ν - T_{\rm A}).$&nbsp;
Bisher haben wir stets zeitkontinuierliche Signale $x(t)$ betrachtet, die für die Darstellung und Simulation mittels Digitalrechner ungeeignet sind. Hierzu ist eine zeitdiskrete Signaldarstellung $〈x_ν〉$ erforderlich, wie im Kapitel 5.1 von Buch „Signaldarstellung” dargelegt. Hier eine kurze Zusammenfassung:
+
*The continuous-time signal&nbsp; $x(t)$&nbsp; is fully described by the sequence&nbsp; $〈x_ν〉$&nbsp; when the sampling theorem is satisfied:
 +
:$$T_{\rm A} \le \frac{1}{2 \cdot B_x}.$$
  
Das zeitdiskrete Signal $〈x_ν〉$ ist die Folge der Abtastwerte $x_ν = x(ν · T_{\rm A}).$ Das zeitkontinuierliche Signal $x(t)$ wird durch die Folge $〈x_ν〉$ vollständig beschrieben, wenn das Abtasttheorem erfüllt ist:
+
*$B_x$&nbsp; denotes the absolute&nbsp; (one-sided)&nbsp; bandwidth of the analog signal&nbsp; $x(t)$.&nbsp; This states that the spectral function&nbsp; $X(f)$&nbsp; is zero for all frequencies&nbsp; $| f | > B_x$.  
$$T_{\rm A} \le \frac{1}{\rm 2 \cdot B_x}.$$
 
  
$B_x$ bezeichnet hierbei die absolute (einseitige) Bandbreite des Analogsignals $x(t)$. Diese sagt aus, dass die Spektralfunktion $X(f)$ für alle Frequenzen $| f | > B_x$ gleich 0 ist.
 
  
 +
{{GraueBox|TEXT=
 +
[[File:P_ID638__Sto_T_4_4_S9_ganz_neu.png |frame| Sampling an audio signal]]
 +
$\text{Example 4:}$&nbsp; 
 +
The image shows a short section of an audio signal of duration&nbsp; $10$&nbsp; milliseconds.
  
{{Beispiel}}
+
Although the entire signal has a broad spectrum with the center frequency at about&nbsp; $500 \hspace{0.05cm} \rm Hz$,&nbsp; in the considered&nbsp; (short)&nbsp; time interval a&nbsp; (nearly)&nbsp; periodic signal with about period duration&nbsp; $T_0 = 4.3 \hspace{0.08cm} \rm ms$.&nbsp; From this,&nbsp; the basic frequency is obtained to&nbsp; 
Das Bild zeigt einen Ausschnitt eines Audiosignals der Dauer 10 Millisekunden. Obwohl das gesamte Signal ein breites Spektrum mit der Mittenfrequenz bei etwa 500 Hz besitzt, ist während des betrachteten Zeitintervalls ein (nahezu) periodisches Signal mit Periodendauer $T_0 =$ 4.3 Millisekunden zu erkennen. Daraus ergibt sich die Grundfrequenz zu etwa $f_0 =$ 230 Hz.  
+
:$$f_0 = 1/T_0 \approx 230 \hspace{0.08cm} \rm Hz.$$
  
 +
Drawn in blue are the samples at distance&nbsp; $T_{\rm A} = 0.5 \hspace{0.08cm} \rm ms$.
 +
*However, this sequence&nbsp; $〈x_ν〉$&nbsp; of samples would only contain all the information about the analog signal&nbsp; $x(t)$&nbsp; if&nbsp; $x(t)$&nbsp; were limited to the frequency range up to&nbsp; $1 \hspace{0.08cm} \rm kHz$.&nbsp;
 +
*If higher frequency components are included in the signal&nbsp; $x(t)$ &nbsp; &rArr; &nbsp; $T_{\rm A}$&nbsp; must be chosen to be correspondingly smaller.}}
  
[[File:P_ID638__Sto_T_4_4_S9_ganz_neu.png | Abtastung eines Audiosignals]]
+
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Conclusion:}$&nbsp; 
 +
#If the signal values are only available at discrete times&nbsp; $($multiples of&nbsp; $T_{\rm A})$,&nbsp; one can also determine the auto-correlation function only at integer multiples of&nbsp; $T_{\rm A}$.
 +
#The ACF calculation can thus be represented as follows&nbsp; (the sweeping line again denotes time averaging):
 +
::$$\varphi_k = \overline {x_\nu \cdot x_{\nu + k} },$$
 +
:*with the discrete-time signal values &nbsp;$x_ν = x(ν - T_{\rm A})$&nbsp; and &nbsp;$x_{ν+k} = x((ν+k) - T_{\rm A})$,&nbsp; and
 +
:* the discrete-time ACF&nbsp; $φ_k = φ_x(k - T_{\rm A})$.  
 +
}}
  
  
Blau eingezeichnet sind die Abtastwerte im Abstand $T_{\rm A} =$ 0.5 ms. Diese Folge $〈x_ν〉$ von Abtastwerten würde die gesamte Information über das Signal $x(t)$ beinhalten, wenn das Analogsignal $x(t)$ auf den Frequenzbereich bis 1 kHz begrenzt wäre. Sind im Signal $x(t)$ höhere Frequenzanteile enthalten, so muss $T_{\rm A}$ entsprechend kleiner gewählt werden.  
+
We now set ourselves the task of finding the ACF support points&nbsp; $φ_0, \hspace{0.1cm}\text{...}\hspace{0.1cm} , φ_l$
{{end}}
+
*from&nbsp; $N$&nbsp; samples&nbsp; $(x_1, \hspace{0.1cm}\text{...}\hspace{0.1cm} , x_N)$&nbsp;
 +
*assuming the parameter&nbsp; $l \ll N$.&nbsp;
  
  
Da nun die Signalwerte nur zu diskreten Zeitpunkten (bei Vielfachen von $T_{\rm A}$) vorliegen, kann man auch die Autokorrelationsfunktion nur zu ganzzahligen Vielfachen von $T_{\rm A}$ bestimmen. Mit den zeitdiskreten Signalwerten $x_ν = x(ν · T_{\rm A})$ und $x_{ν+k} = x((ν+k) · T_{\rm A})$ sowie der zeitdiskreten AKF $φ_k = φ_x(k · T_{\rm A})$ lässt sich somit die AKF–Berechnung wie folgt dargestellen:  
+
For example,&nbsp; let&nbsp; $l = 100$&nbsp; and&nbsp; $N = 100000$.&nbsp; The ACF calculation rule is now&nbsp; $($with&nbsp; $0 ≤ k ≤ l)$:
$$\varphi_k = \overline {x_\nu \cdot x_{\nu + k}}.$$
+
:$$\varphi_k = \frac{1}{N- k} \cdot \sum_{\nu = 1}^{N - k} x_{\nu} \cdot x_{\nu + k}.$$
Die überstreichende Linie kennzeichnet hierbei wieder die Zeitmittelung.
+
Bringing the factor&nbsp; $(N - k)$&nbsp; to the left-hand side,&nbsp; we obtain&nbsp; $l + 1$&nbsp; equations,&nbsp; namely:
 +
:$$k = 0\text{:} \hspace{0.4cm}N \cdot \varphi_0 \hspace{1.03cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{\rm 1} \hspace{0.35cm}+ x_{\rm 2} \cdot x_{\rm 2} \hspace{0.3cm}+\text{ ...} \hspace{0.25cm}+x_{\nu} \cdot x_{\nu}\hspace{0.35cm}+\text{ ...} \hspace{0.05cm}+x_{N} \cdot x_{N},$$
 +
:$$k= 1\text{:}  \hspace{0.3cm}(N-1) \cdot \varphi_1 \hspace{0.08cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{\rm 2} \hspace{0.4cm}+ x_{\rm 2} \cdot x_{\rm 3} \hspace{0.3cm}+ \text{ ...} \hspace{0.18cm}+x_{\nu} \cdot x_{\nu + 1}\hspace{0.01cm}+\text{ ...}\hspace{0.08cm}+x_{N-1} \cdot x_{N},$$
 +
:$$\text{..................................................}$$
 +
:$$k \hspace{0.2cm}{\rm general\hspace{-0.1cm}:}\hspace{0.15cm}(N - k) \cdot \varphi_k \hspace{0.01cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{ {\rm 1} + k} \hspace{0.01cm}+ x_{\rm 2} \cdot x_{ {\rm 2}+ k}\hspace{0.1cm} + \text{ ...}\hspace{0.01cm}+x_{\nu} \cdot x_{\nu+k}\hspace{0.1cm}+\text{ ...}\hspace{0.01cm}+x_{N-k} \cdot x_{N},$$
 +
:$$\text{..................................................}$$
 +
:$$k = l\text{:} \hspace{0.3cm}(N - l) \cdot \varphi_l \hspace{0.14cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{ {\rm 1}+l} \hspace{0.09cm}+ x_{\rm 2} \cdot x_{ {\rm 2}+ l} \hspace{0.09cm}+ \text{ ...}\hspace{0.09cm}+x_{\nu} \cdot x_{\nu+ l} \hspace{0.09cm}+ \text{ ...}\hspace{0.09cm}+x_{N- l} \cdot x_{N}.$$
  
==Numerische AKF-Ermittlung (2)==
+
{{BlaueBox|TEXT=  
Wir stellen uns nun die Aufgabe, die AKF-Stützstellen $φ_0, ... , φ_l$ aus $N$ Abtastwerten $(x_1, .... , x_N)$ zu ermitteln, wobei der Parameter $l$ sehr viel kleiner als $N$ vorausgesetzt wird. Beispielsweise gelte $l =$ 100 und $N =$ 100000.
+
$\text{Conclusions:}$&nbsp; 
 +
Following this scheme results in the following algorithm:
 +
#You define the field&nbsp; $\rm ACF\big[\hspace{0.05cm}0 : {\it l}\hspace{0.1cm}\big]$&nbsp; of type&nbsp; "float"&nbsp; and preallocate zeros to all elements.  
 +
#On each loop pass&nbsp; $($indexed with variable&nbsp; $k)$,&nbsp; the&nbsp; $l + 1$&nbsp; field elements&nbsp; ${\rm ACF}\big[\hspace{0.03cm}k\hspace{0.03cm}\big]$&nbsp; are incremented by the contribution &nbsp;$x_ν \cdot x_{ν+k}$.  
 +
#All&nbsp; $l+1$&nbsp; field elements are processed,&nbsp; however,&nbsp; only as long as the control variable&nbsp; $k$&nbsp; is not greater than&nbsp; $N - l$.
 +
#It must always be considered that&nbsp; $ν + k ≤ N$&nbsp; must hold.&nbsp; This means that the averaging in the different fields&nbsp; $\rm ACF\big[\hspace{0.03cm}0\hspace{0.03cm}\big]$ ... ${\rm ACF}\big[\hspace{0.03cm}l\hspace{0.03cm}\big]$&nbsp; must be done over a different number of summands.
 +
#If,&nbsp; at the end of the calculation,&nbsp; the values stored in&nbsp; ${\rm ACF}\big[\hspace{0.03cm}k\hspace{0.03cm}\big]$&nbsp; are still divided by the number of summands&nbsp; $(N - k)$&nbsp; this field contains the discrete ACF values we are looking for:
 +
::$$\varphi_x(k \cdot T_A)= {\rm ACF} \big[\hspace{0.03cm}k\hspace{0.03cm}\big].$$
  
Die AKF-Berechnungsvorschrift lautet nun (mit 0 ≤ $k$ $l$):  
+
$\text{Note:}$ &nbsp; For&nbsp; $l \ll N$&nbsp; one can simplify the algorithm by choosing the number of summands to be the same for all&nbsp; $k$&ndash;values:  
$$\varphi_k = \frac{1}{N- k} \cdot \sum_{\nu = 1}^{N - \lambda} x_{\nu} \cdot x_{\nu + k}.$$
+
::$$\varphi_k = \frac{1}{N- l} \cdot \sum_{\nu = 1}^{N - l} x_{\nu} \cdot x_{\nu + k}.$$}}
Bringen wir $N – k$ auf die linke Seite, so erhalten wir daraus $l +$ 1 Gleichungen, nämlich:
 
$$k = 0: \hspace{0.4cm}N \cdot \varphi_0 \hspace{1.03cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{\rm 1} \hspace{0.35cm}+ x_{\rm 2} \cdot x_{\rm 2} \hspace{0.3cm}+ ... \hspace{0.25cm}+x_{\nu} \cdot x_{\nu}\hspace{0.35cm}+ ... \hspace{0.05cm}+x_{N} \cdot x_{N},$$
 
$$k= 1: \hspace{0.3cm}(N-1) \cdot \varphi_1 \hspace{0.08cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{\rm 2} \hspace{0.4cm}+ x_{\rm 2} \cdot x_{\rm 3} \hspace{0.3cm}+ ... \hspace{0.18cm}+x_{\nu} \cdot x_{\nu + 1}\hspace{0.01cm}+ ... \hspace{0.08cm}+x_{N-1} \cdot x_{N},$$
 
$$..................................................$$
 
$$k \hspace{0.2cm}{\rm allg.:}\hspace{0.31cm}(N - k) \cdot \varphi_k \hspace{0.01cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{ {\rm 1} + k} \hspace{0.01cm}+ x_{\rm 2} \cdot x_{ {\rm 2}+ k}\hspace{0.1cm} + ... \hspace{0.01cm}+x_{\nu} \cdot x_{\nu+k}\hspace{0.1cm}+ ... \hspace{0.01cm}+x_{N-k} \cdot x_{N},$$
 
$$..................................................$$
 
$$k = l: \hspace{0.3cm}(N - l) \cdot \varphi_l \hspace{0.14cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{ {\rm 1}+l} \hspace{0.09cm}+ x_{\rm 2} \cdot x_{ {\rm 2}+ l} \hspace{0.09cm}+ ... \hspace{0.09cm}+x_{\nu} \cdot x_{\nu+ l} \hspace{0.09cm}+ ... \hspace{0.09cm}+x_{N- l} \cdot x_{N}.$$
 
  
Hieraus ergibt sich der folgende Algorithmus:
+
==Accuracy of the numerical ACF calculation==
*Man definiert das Feld AKF[0 : $l$] vom Typ ''float'' und belegt alle Elemente mit Nullen vor.
+
<br>
*Bei jedem Schleifendurchlauf (indiziert mit der Variablen $k$) werden die $l$ + 1 Feldelemente AKF[ $k$] jeweils um den Betrag $x_ν · x_{ν+k}$ erhöht.
+
{{GraueBox|TEXT= 
*Alle $l$ + 1 Feldelemente werden allerdings nur dann bearbeitet, so lange die Laufvariable $k$ nicht größer als $N – l$ ist. Es ist stets zu berücksichtigen, dass $ν + k ≤ N$ gelten muss. Das bedeutet, dass die Mittelung in den unterschiedlichen Feldern AKF[0] ... AKF[ $l$] über eine unterschiedliche Anzahl von Summanden erfolgt.
+
$\text{Example 5:}$&nbsp; 
*Werden am Ende der Berechnung noch die in AKF[ $k$] gespeicherten Werte durch die Anzahl der Summanden $(N – k)$ dividiert, so enthält dieses Feld die gesuchten diskreten AKF-Werte:
+
The crucial parameter for the quality of numerical ACF calculation is the number&nbsp; $N$&nbsp; of considered samples.
$$\varphi_x(k \cdot T_A)= {\rm AKF} \left[k \right].$$
+
[[File:EN Sto T 4 4 S9a v1.png |right|frame| ACF for statistically independent samples]]
 +
 +
The upper graph shows the result of the numerical ACF calculation for&nbsp; $N = 1000$.&nbsp; The lower graph is for&nbsp; $N = 10000$&nbsp; samples.  
  
 +
*The considered random variables are here statistically independent from each other.&nbsp;
 +
*Thus,&nbsp; all ACF values should actually be zero with the exception of the value at&nbsp; $k = 0$.
  
'''Anmerkung:''' Bei $l << N$ kann man den Algorithmus vereinfachen, indem die Anzahl der Summanden für alle $k$-Werte gleich gewählt werden:
 
$$\varphi_k = \frac{1}{N- l} \cdot \sum_{\nu = 1}^{N - l} x_{\nu} \cdot x_{\nu + k}.$$
 
  
==Genauigkeit der numerischen AKF-Berechnung (1)==
 
Der entscheidende Parameter für die Qualität der numerischen AKF-Berechnung ist die Anzahl $N$ der berücksichtigten Abtastwerte. Im nachfolgenden oberen Bild sehen Sie das Ergebnis für $N =$ 1000 und darunten für $N =$ 10000 Zufallsgrößen.
 
  
 +
 +
*For&nbsp; $N = 10000$&nbsp; (lower graph) the maximum error is only about&nbsp; $1\%$&nbsp; and is almost invisible in this plot.
 +
*In contrast,&nbsp; for&nbsp; $N = 1000$&nbsp; (upper graph),&nbsp; the error grows to $±6\%$. }}
 +
<br clear = all>
 +
{{GraueBox|TEXT= 
 +
$\text{Example 6:}$&nbsp;
 +
The results change when there is a random variable with internal statistical bindings.
 +
[[File:EN_Sto_T_4_4_S9b_v1.png|right|frame| ACF for correlated samples]]
  
[[File:P_ID639__Sto_T_4_4_S9a_Ganz_neu.png | AKF bei statistisch unabhängigen Abtastwerten]]
+
For example,&nbsp; if we consider a triangular ACF with&nbsp; $φ_x(k) ≠ 0$&nbsp; for&nbsp; $\vert k \vert ≤ 10$,&nbsp; we see much larger deviations, viz.
 +
* errors up to about&nbsp; $±15\%$&nbsp; for&nbsp; $N = 1000$,
 +
* errors up to about&nbsp; $±5\%$&nbsp; at&nbsp; $N = 10000$.  
  
  
Die betrachteten Zufallsgrößen sind hier voneinander statistisch unabhängig. Somit sollten eigentlich alle AKF-Werte mit Ausnahme des Wertes bei $k =$ 0 identisch Null sein. Bei $N =$ 10000 (untere Grafik) beträgt der maximale Fehler nur etwa 1% und ist bei dieser Darstellung fast gar nicht sichtbar. Dagegen wächst der Fehler bei $N =$ 1000 bis auf ±6% an (Markierung beachten).  
+
Justification of the worse result according to this&nbsp; $\text{Example 6}$:
 +
*Due to the internal statistical bindings,&nbsp; not all samples now provide full information about the underlying random process.
 +
*Furthermore,&nbsp; the images reveal that in numerical ACF calculation of a random variable with statistical bindings,&nbsp; also the errors are correlated.  
 +
*If,&nbsp; for example,&nbsp; as seen in the upper image,&nbsp; the ACF value&nbsp; $φ_x({\rm 26})$&nbsp; is spuriously positive and large,&nbsp; the neighboring ACF values&nbsp; $φ_x({\rm 25})$&nbsp; and&nbsp; $φ_x({\rm 27})$&nbsp; will also be positive with similar numerical values.&nbsp; This area is marked by the rectangle in the upper graph.}}
  
==Genauigkeit der numerischen AKF-Berechnung (2)==
+
==Exercises for the chapter==
Die Ergebnisse ändern sich, wenn eine Zufallsgröße mit inneren statistischen Bindungen vorliegt. Betrachten wir beispielsweise eine dreieckförmige AKF mit $φ_x(k) ≠$ 0 für $|k|$ ≤ 10, so erkennt man deutlich größere Abweichungen, nämlich Fehler bis zu
+
<br>
*etwa ±15% bei $N =$ 1000,
+
[[Aufgaben:Exercise_4.09:_Cyclo-Ergodicity|Exercise 4.09: Cyclo-Ergodicity]]
*etwa ±5% bei $N =$ 10000.  
 
  
 +
[[Aufgaben:Exercise_4.09Z:_Periodic_ACF|Exercise 4.09Z: Periodic ACF]]
  
 +
[[Aufgaben:Exercise_4.10:_Binary_and_Quaternary|Exercise 4.10: Binary and Quaternary]]
  
[[File:P_ID640__Sto_T_4_4_S9b_Ganz_neu.png | AKF bei korrelierten Abtastwerten]]
+
[[Aufgaben:Exercise_4.10Z:_Correlation_Duration|Exercise 4.10Z: Correlation Duration]]
  
 +
[[Aufgaben:Exercise_4.11:_C_Program_"acf1"|Exercise 4.11: C Program "acf1"]]
  
''Begründung des schlechteren Ergebnisses:''
+
[[Aufgaben:Exercise_4.11Z:_C_Program_"acf2"|Exercise 4.11Z: C Program "acf2"]]
*Aufgrund der inneren statistischen Bindungen liefern nun nicht mehr alle Abtastwerte die volle Information über den zugrundeliegenden Zufallsprozess.  
 
*Außerdem lassen die Bilder erkennen, dass bei der numerischen AKF-Berechnung einer Zufallsgröße mit statistischen Bindungen auch die Fehler korreliert sind.
 
*Ist – wie beispielsweise im oberen Bild zu sehen – der AKF-Wert $φ_x({\rm 26})$ fälschlicherweise positiv und groß, so ergeben sich auch die benachbarten AKF-Werte $φ_x({\rm 25})$ und $φ_x({\rm 27})$ als positiv und mit ähnlichen Zahlenwerten. Dieser Bereich ist durch das Rechteck markiert.  
 
  
  
 
{{Display}}
 
{{Display}}

Latest revision as of 10:07, 22 December 2022

Random processes


An important concept in stochastic signal theory is the  "random process".  Below are some characteristics of such a  "stochastic process" - these terms are used synonymously both in the literature and in our tutorial.

$\text{Definitions:}$  By a  »random process«  $\{x_i(t)\}$  we understand a mathematical model  for an ensemble of (many) random signals,  which can and will differ from each other in detail,  but nevertheless they have certain common properties.

  • To describe a random process  $\{x_i(t)\}$  we start from the notion that there are any number of random generators,  completely identical in their physical and statistical properties,  each of which yields a random signal  $x_i(t)$.
  • Each random generator,  despite having the same physical realization,  outputs a different time signal  $x_i(t)$  that exists for all times from  $-∞$  to  $+∞$.  This specific random signal is called the  »$i$-th pattern signal«.
  • Every random process involves at least one stochastic component - for example:  the amplitude,  frequency,  or phase of a message signal - and therefore cannot be accurately predicted by an observer.
  • The random process differs from the usual random experiments in probability theory or statistics in that the result is not an  "event"  but a  "function"  (time signal).
  • If we consider the random process  $\{x_i(t)\}$  at a fixed time,  we return to the simpler model from the former chapter  "From Random Experiment to Random Variable",  according to which the experimental result is an event that can be assigned to a random variable.


These statements are now illustrated by the example of a binary random generator,  which - at least in thought - can be realized arbitrarily often.

$\text{Example 1:}$  The graph shows three different pattern signals of a random process with the following properties:

On the definition of a random process
  • The random process  $\{x_i(t)\}$  consists of an ensemble of rectangular pattern functions,  which can be described as follows:
$$x_i(t)=\sum^{+\infty}_{\nu=-\infty} (a_\nu)_i\cdot g(t-\nu \cdot T ).$$
  • The basic pulse  $g(t)$  has in the range from  $-T/2$  to  $+T/2$  the value  $2\hspace{0.03cm}\rm V$; outside it is zero and exactly at  $\pm T/2$  only half as large  $(1\hspace{0.03cm}\rm V)$. 
  • Remember:  A pulse,  as defined in the chapter  "Signal Classification"  in the book  "Signal Representation", is both a  "deterministic"  and  "energy-limited"  signal.
  • The statistics of the random process under consideration is due solely to the dimensionless amplitude coefficients  $(a_ν)_i ∈ \{0, 1\}$  which are time-indexed by  $ν$   for the  $i$-th pattern function.
  • Despite the different signal courses in detail, the sketched signals  $x_1(t)$,  $x_2(t)$,  $x_3(t)$  and also all further pattern signals  $x_4(t)$,  $x_5(t)$,  $x_6(t)$, ...  have certain common features,  which will be elaborated in the following.

Stationary random processes


On the definition of stationary random processes

If one defines the instantaneous value of all pattern functions  $x_i(t)$  at a fixed time  $t = t_1$  as a new random variable  $x_1 = \{ x_i(t_1)\}$,  its statistical properties can be described according to the statements

  • of the second chapter  "Discrete Random Variables"  and
  • of the third chapter  "Continuous Random Variables"  in this book.


Similarly, for the time of observation  $t = t_2$  we obtain the random variable  $x_2 = \{ x_i(t_2)\}$.


Note on nomenclature:

  • $x_1(t)$  and  $x_2(t)$  are  "pattern functions"  of the random process  $\{x_i(t)\}$ ,
  • while the random variables  $x_1$  and  $x_2$  "characterize the whole process"  at times  $t_1$  and  $t_2$  resp.


The calculation of the statistical characteristics must be done

by  »coulter averaging«  over all possible pattern functions  
⇒   averaging over the control variable  $i$, i.e. over all realizations.


$\text{Definition:}$  For a  »stationary random process«  $\{x_i(t)\}$  all statistical parameters  $($mean, standard deviation, higher order moments, probabilities, etc. $)$  of the random variables  $x_1 = \{ x_i(t_1)\}$  and  $x_2 = \{ x_i(t_2)\}$  are equal.

  • Also at other times,  the values are exactly the same.
  • The converse is:   One calls a random process  $\{x_i(t)\}$  a  "non-stationary process"  if it has different statistical properties at different times.


$\text{Example 2:}$  A large number of measuring stations at the equator determine the temperature daily at 12 o'clock local time. 

  • If one averages over all these measured values,  one can eliminate the influence of local indicators (e.g. Gulf Stream). 
  • If one plots the mean values  (coulter averaging)  over time,  almost a constant will result,  and one can speak of a "stationary process".
  • A comparable series of measurements at 50° latitude would indicate a  "non-stationary process"  due to the seasonal variations,  with significant differences in mean and variance of the noon temperature between January and July.

Ergodic random processes


An important subclass of stationary random processes are the so-called  "ergodic processes"  with the following properties:

$\text{Definition:}$  In an  »ergodic process«  $\{x_i(t)\}$  each individual pattern function  $x_i(t)$  is representative of the entire ensemble.

  • All statistical descriptive variables of an ergodic process can be obtained from a single pattern function by time averaging 
    $($referring to the control variables  $ν = t/T$   ⇒   normalized time$)$  .
  • This also means:   With ergodicity,  the time averages of each pattern function coincide with the corresponding coulter averages at arbitrary time points  $ν$


On the definition of ergodic random processes

For example,  with ergodicity,  for the moment  $k$-th order:

$$m_k=\overline{x^k(t)}={\rm E}\big[x^k\big].$$

Here,  the sweeping line denotes the time mean,  while the coulter mean is to be determined by expected value generation  $\rm E\big[ \hspace{0.1cm}\text{...} \hspace{0.1cm} \big]$  as described in chapter  "Moments of a discrete random variable".



Note:  

  1. Ergodicity cannot be proved from a finite number of pattern functions and finite signal sections.
  2. However, ergodicity is hypothetically - but nevertheless quite justifiably - assumed in most applications.
  3. On the basis of the results found,  the plausibility of this  »ergodicity hypothesis«  must subsequently be checked.


Generally valid description of random processes


If the random process  $\{x_i(t)\}$  to be analyzed is not stationary and thus certainly not ergodic,  the moments must always be determined as coulter averages. 

  • In general,  these are time-dependent:
$$m_k(t_1) \ne m_k(t_2).$$
$$ C_x(\Omega) ={\rm\sum^{\infty}_{{\it k}=0}}\ \frac{m_k}{k!}\cdot \Omega^{k}\ \circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\,\ f_{x}(x)$$
is fixed,  the probability density function $f_{x}(x)$  is also time-dependent.


For example,  considering the two time points  $t_1$  and  $t_2$,  note the following:

  1. The two-dimensional PDF is obtained according to the specifications in section  "Properties and examples of two-dimensional random variables"  with  $x = x(t_1)$  and  $y = x(t_2)$.  It is obvious that already the determination of this variable is very complex.
  2. If one further considers that to capture all statistical bindings within the random process actually the  $n$-dimensional probability density function would have to be used,  where if possible the limit  $n → ∞$  still has to be formed,  one recognizes the difficulties for the solution of practical problems.
  3. For these reasons,  in order to describe the statistical bindings of a random process,  one proceeds to the auto-correlation function,  which simplifies the problem.  This is first defined in the following section for the general case.

General definition of the auto-correlation function


$\text{General Definition:}$ 

The  »auto-correlation function«  $\rm (ACF)$  of a random process  $\{x_i(t)\}$  is equal to the expected value of the product of the signal values at two time points  $t_1$  and  $t_2$:

$$\varphi_x(t_1,t_2)={\rm E}\big[x(t_{\rm 1})\cdot x(t_{\rm 2})\big].$$

This definition holds whether the random process is ergodic or non-ergodic,  and it also holds in principle for non-stationary processes.


Note on nomenclature:
In order to establish the relationship with the  $\text{cross-correlation function}$  $φ_{xy}$  between the two statistical variables  $x$  and  $y$  to make clear,  in some literature for the auto-correlation function instead of  $\varphi_x$  the notation  $\varphi_{xx}$  is also often used.  In our learning tutorial,  we refrain from doing so.


A comparison with the section  "Expected values of two-dimensional random variables"  shows that the ACF–value  $φ_x(t_1, t_2)$  indicates the joint moment  $m_{11}$  between the two random variables  $x(t_1)$  and  $x(t_2)$.

While exact statements regarding the statistical bindings of a random process actually require the  $n$–dimensional joint probability density  $($with  $n → ∞)$,  the following simplifications are implicitly made by moving to the auto-correlation function:

  1. Instead of infinitely many time points,  only two are considered here,  and instead of all moments  $m_{\hspace{0.05cm}k\hspace{0.05cm}l}$  at the two time points  $t_1$  and  $t_2$  with  $k, \ l ∈ \{1, 2, 3, \text{...} \}$  only the joint moment  $m_{11}$  is captured.
  2. The moment  $m_{11}$  exclusively reflects the linear dependence  ("correlation")  of the process.  All higher order statistical bindings,  on the other hand,  are not considered.
  3. Therefore,  when evaluating random processes by means of ACF,  it should always be taken into account that it allows only very limited statements about the statistical bindings in general.


$\text{Example 3:}$  The above definition of the auto-correlation function applies in general,  i.e. also to non-stationary and non-ergodic processes.

  • An example of a non-stationary process is the occurrence of  "intersymbol interference"  in the telephone network caused by dial pulses in adjacent lines.
  • In digital signal transmission,  such non-stationary interference processes usually lead to trunking errors.


Auto-correlation function for stationary and ergodic processes


On the auto-correlation function in ergodic processes

In the following,  we restrict ourselves to stationary and ergodic processes.

Such a random process  $\{x_i(t)\}$  is e.g. used as a basis in the study of  $\text{thermal noise}$.  This is based on the notion that

  • there are any number of resistors, completely identical in their physical and statistical properties,
  • each of which emits a different random signal  $x_i(t)$ .



The graphic shows such a stationary and ergodic process:

  1. The individual pattern functions  $x_i(t)$  can take on any arbitrary values at any arbitrary times.  This means that the random process  $\{x_i(t)\}$  considered here is both continuous in value and continuous in time.
  2. Although no conclusions can be drawn about the actual signal values of the individual pattern functions due to stochasticity,  $\{x_i(t)\}$  the moments and the PDF are the same at all time points.
  3. In the graph,  for reasons of a generalized representation,  a DC component  $m_x$  is also considered,  which is not present in thermal noise.


$\text{Definition:}$  One speaks of a  »stationary random process«  $\{x_i(t)\}$ if its statistical properties are invariant to time shifts.

  • For the auto-correlation function  $\rm (ACF)$,  this statement means that it is no longer a function of the two independent time variables  $t_1$  and  $t_2$  but depends only on the time difference  $τ = t_2 - t_1$ :
$$\varphi_x(t_1,t_2)\ \rightarrow \ {\varphi_x(\tau)={\rm E}\big[x(t)\cdot x(t+\tau)\big]}.$$
  • The coulter averaging can be done at any time  $t$  in this case.


  1. Under the further assumption of an ergodic random process,  all moments can also be obtained by time averaging over a single selected pattern function  $x(t)$. 
  2. All these time averages coincide with the corresponding coulter averages in this special case.


$\text{Definition:}$  Thus,  for the  »ACF of an ergodic random process«  whose pattern signals each range from  $-∞$  to  $+∞$  follows:

$$\varphi_x(\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}t.$$
  • The sweeping line denotes time averaging over the infinitely extended time interval.
  • $T_{\rm M}$  denotes the measurement duration.


For periodic signals,  the boundary crossing can be omitted,  so in this special case the auto-correlation function with period  $T_0$  can also be written in the following way:

$$\varphi_x(\tau)=\frac{1}{T_{\rm 0}}\cdot\int^{T_{\rm 0}/2}_{-T_{\rm 0}/2}x(t)\cdot x(t+\tau)\,\,{\rm d}t=\frac{1}{T_{\rm 0}}\cdot\int^{T_{\rm 0}}_{\rm 0}x(t)\cdot x(t+\tau)\,\,{\rm d}t .$$

It is only important that in total exactly over a period duration  $T_0$  $($or multiples of it$)$  is averaged.  It does not matter which time section one uses.

Properties of the auto-correlation function


Here we compile important properties of the auto-correlation function  $\rm (ACF)$,  starting from the ergodic ACF–form  $φ_x(τ)$:

  • If the random process under consideration is real, so is its auto-correlation function is also real.
  • The ACF has the unit of a power, e.g.  "Watt"  $\rm (W)$.  Often one relates it to the resistance  $1\hspace{0.03cm} Ω$;  $φ_x(τ)$  then with the unit  $\rm V^2$  resp.  $\rm A^2$.
  • The ACF is always an even function  ⇒   $φ_x(-τ) = φ_x(τ)$.   All phase relations of the random process are lost in the ACF.
  • The ACF at the point  $τ = 0$  gives the second order moment  $m_2$  and thus the total signal power of the random process  (DC and AC components):
$$\varphi_x(\tau = 0)= m_2=\overline{ x^2(t)}.$$
  • The ACF maximum always occurs at  $τ = 0$.  It holds:   $|φ_x(τ)| ≤ φ_x(0)$.  For non-periodic processes,  the magnitude  $|φ_x(τ)|$  for  $τ ≠ 0$  is always less than  $φ_x(\tau =0)$.
  • For a periodic random process, the ACF has the same period  $T_0$  as the individual pattern signals  $x_i(t)$  :
$$\varphi_x(\pm{T_0})=\varphi_x(\pm{2\cdot T_0})= \hspace{0.1cm}\text{...} \hspace{0.1cm}= \varphi_x(0).$$
  • The DC component  $m_1$  of a non-periodic signal can be calculated from the limit of the auto-correlation function for  $τ → ∞$.  Here,  the following holds:
$$\lim_{\tau\to\infty}\,\varphi_x(\tau)= m_1^2=\big [\overline{ x(t)}\big]^2.$$
  • In contrast,  for signals with periodic components,  the limit value of the ACF for  $τ → ∞$  varies around this final value  (square of the DC component).

Interpretation of the auto-correlation function


The graph shows pattern signals of each of two random processes  $\{x_i(t)\}$  and  $\{y_i(t)\}$ at the top,  and the corresponding auto-correlation functions at the bottom.

ACF of high-frequency and low-frequency processes

Based on these representations,  the following statements are possible:

  1. $\{y_i(t)\}$  has stronger internal statistical bindings than  $\{x_i(t)\}$.  Spectrally,  the process $\{y_i(t)\}$  is thus lower frequency.
  2. The sketched pattern signals  $x(t)$  and  $y(t)$  already suggest that both processes are zero mean and have the same standard deviation.
  3. The above auto-correlation functions confirm these statements.  The linear mean values  $m_x = m_y = 0$  result in each case from the ACF limit for  $τ → ∞$.
  4. Because  $m_x = 0$  applies here to the variance:   $σ_x^2 = φ_x(0) = 0.01 \hspace{0.05cm} \rm V^2$, and the standard deviation is consequently  $σ_x = 0.1 \hspace{0.05cm}\rm V$.
  5. $y(t)$  has the same variance and and standard deviation as  $x(t)$.  The ACF values fall off more slowly the stronger the internal statistical bindings are.
  6. The signal  $x(t)$  with narrow ACF changes very fast in time,  while for the lower frequency signal  $y(t)$  the statistical bindings are much wider.
  7. But this also means that the signal value  $y(t + τ)$  from  $y(t)$  can be better predicted than  $x(t + τ)$  from  $x(t)$.


$\text{Definition:}$  A quantitative measure of the strength of statistical bindings is the  »equivalent ACF duration«  $∇τ$  ("Nabla-tau"),  which can be determined from the ACF over the equal-area rectangle:

$${ {\rm \nabla} }\tau =\frac{1}{\varphi_x(0)}\cdot\int^{\infty}_{-\infty}\ \varphi_x(\tau)\,\,{\rm d}\tau. $$


  • For the processes considered here  (with Gaussian-like ACF)  holds according to the above sketch:   $∇τ_x = 0.33 \hspace{0.05cm} \rm µ s$   resp.   $∇τ_y = 1 \hspace{0.05cm} \rm µs$.
  • As another measure of the strength of the statistical bindings, the  $\text{correlation duration}$  $T_{\rm K}$  is often used in the literature. 
  • This indicates the time duration at which the auto-correlation function has dropped to half of its maximum value.

Numerical ACF determination


So far,  we have always considered continuous-time signals  $x(t)$  which are unsuitable for representation and simulation by means of digital computers.  Instead,  a discrete-time signal representation  $〈x_ν〉$  is required for this purpose,  as outlined in the chapter  "Discrete-Time Signal Representation"  of our first book.

Here is a brief summary:

  • The discrete-time signal  $〈x_ν〉$  is the sequence of samples  $x_ν = x(ν - T_{\rm A}).$ 
  • The continuous-time signal  $x(t)$  is fully described by the sequence  $〈x_ν〉$  when the sampling theorem is satisfied:
$$T_{\rm A} \le \frac{1}{2 \cdot B_x}.$$
  • $B_x$  denotes the absolute  (one-sided)  bandwidth of the analog signal  $x(t)$.  This states that the spectral function  $X(f)$  is zero for all frequencies  $| f | > B_x$.


Sampling an audio signal

$\text{Example 4:}$  The image shows a short section of an audio signal of duration  $10$  milliseconds.

Although the entire signal has a broad spectrum with the center frequency at about  $500 \hspace{0.05cm} \rm Hz$,  in the considered  (short)  time interval a  (nearly)  periodic signal with about period duration  $T_0 = 4.3 \hspace{0.08cm} \rm ms$.  From this,  the basic frequency is obtained to 

$$f_0 = 1/T_0 \approx 230 \hspace{0.08cm} \rm Hz.$$

Drawn in blue are the samples at distance  $T_{\rm A} = 0.5 \hspace{0.08cm} \rm ms$.

  • However, this sequence  $〈x_ν〉$  of samples would only contain all the information about the analog signal  $x(t)$  if  $x(t)$  were limited to the frequency range up to  $1 \hspace{0.08cm} \rm kHz$. 
  • If higher frequency components are included in the signal  $x(t)$   ⇒   $T_{\rm A}$  must be chosen to be correspondingly smaller.


$\text{Conclusion:}$ 

  1. If the signal values are only available at discrete times  $($multiples of  $T_{\rm A})$,  one can also determine the auto-correlation function only at integer multiples of  $T_{\rm A}$.
  2. The ACF calculation can thus be represented as follows  (the sweeping line again denotes time averaging):
$$\varphi_k = \overline {x_\nu \cdot x_{\nu + k} },$$
  • with the discrete-time signal values  $x_ν = x(ν - T_{\rm A})$  and  $x_{ν+k} = x((ν+k) - T_{\rm A})$,  and
  • the discrete-time ACF  $φ_k = φ_x(k - T_{\rm A})$.


We now set ourselves the task of finding the ACF support points  $φ_0, \hspace{0.1cm}\text{...}\hspace{0.1cm} , φ_l$

  • from  $N$  samples  $(x_1, \hspace{0.1cm}\text{...}\hspace{0.1cm} , x_N)$ 
  • assuming the parameter  $l \ll N$. 


For example,  let  $l = 100$  and  $N = 100000$.  The ACF calculation rule is now  $($with  $0 ≤ k ≤ l)$:

$$\varphi_k = \frac{1}{N- k} \cdot \sum_{\nu = 1}^{N - k} x_{\nu} \cdot x_{\nu + k}.$$

Bringing the factor  $(N - k)$  to the left-hand side,  we obtain  $l + 1$  equations,  namely:

$$k = 0\text{:} \hspace{0.4cm}N \cdot \varphi_0 \hspace{1.03cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{\rm 1} \hspace{0.35cm}+ x_{\rm 2} \cdot x_{\rm 2} \hspace{0.3cm}+\text{ ...} \hspace{0.25cm}+x_{\nu} \cdot x_{\nu}\hspace{0.35cm}+\text{ ...} \hspace{0.05cm}+x_{N} \cdot x_{N},$$
$$k= 1\text{:} \hspace{0.3cm}(N-1) \cdot \varphi_1 \hspace{0.08cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{\rm 2} \hspace{0.4cm}+ x_{\rm 2} \cdot x_{\rm 3} \hspace{0.3cm}+ \text{ ...} \hspace{0.18cm}+x_{\nu} \cdot x_{\nu + 1}\hspace{0.01cm}+\text{ ...}\hspace{0.08cm}+x_{N-1} \cdot x_{N},$$
$$\text{..................................................}$$
$$k \hspace{0.2cm}{\rm general\hspace{-0.1cm}:}\hspace{0.15cm}(N - k) \cdot \varphi_k \hspace{0.01cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{ {\rm 1} + k} \hspace{0.01cm}+ x_{\rm 2} \cdot x_{ {\rm 2}+ k}\hspace{0.1cm} + \text{ ...}\hspace{0.01cm}+x_{\nu} \cdot x_{\nu+k}\hspace{0.1cm}+\text{ ...}\hspace{0.01cm}+x_{N-k} \cdot x_{N},$$
$$\text{..................................................}$$
$$k = l\text{:} \hspace{0.3cm}(N - l) \cdot \varphi_l \hspace{0.14cm}=\hspace{0.1cm} x_{\rm 1} \cdot x_{ {\rm 1}+l} \hspace{0.09cm}+ x_{\rm 2} \cdot x_{ {\rm 2}+ l} \hspace{0.09cm}+ \text{ ...}\hspace{0.09cm}+x_{\nu} \cdot x_{\nu+ l} \hspace{0.09cm}+ \text{ ...}\hspace{0.09cm}+x_{N- l} \cdot x_{N}.$$

$\text{Conclusions:}$  Following this scheme results in the following algorithm:

  1. You define the field  $\rm ACF\big[\hspace{0.05cm}0 : {\it l}\hspace{0.1cm}\big]$  of type  "float"  and preallocate zeros to all elements.
  2. On each loop pass  $($indexed with variable  $k)$,  the  $l + 1$  field elements  ${\rm ACF}\big[\hspace{0.03cm}k\hspace{0.03cm}\big]$  are incremented by the contribution  $x_ν \cdot x_{ν+k}$.
  3. All  $l+1$  field elements are processed,  however,  only as long as the control variable  $k$  is not greater than  $N - l$.
  4. It must always be considered that  $ν + k ≤ N$  must hold.  This means that the averaging in the different fields  $\rm ACF\big[\hspace{0.03cm}0\hspace{0.03cm}\big]$ ... ${\rm ACF}\big[\hspace{0.03cm}l\hspace{0.03cm}\big]$  must be done over a different number of summands.
  5. If,  at the end of the calculation,  the values stored in  ${\rm ACF}\big[\hspace{0.03cm}k\hspace{0.03cm}\big]$  are still divided by the number of summands  $(N - k)$  this field contains the discrete ACF values we are looking for:
$$\varphi_x(k \cdot T_A)= {\rm ACF} \big[\hspace{0.03cm}k\hspace{0.03cm}\big].$$

$\text{Note:}$   For  $l \ll N$  one can simplify the algorithm by choosing the number of summands to be the same for all  $k$–values:

$$\varphi_k = \frac{1}{N- l} \cdot \sum_{\nu = 1}^{N - l} x_{\nu} \cdot x_{\nu + k}.$$

Accuracy of the numerical ACF calculation


$\text{Example 5:}$  The crucial parameter for the quality of numerical ACF calculation is the number  $N$  of considered samples.

ACF for statistically independent samples

The upper graph shows the result of the numerical ACF calculation for  $N = 1000$.  The lower graph is for  $N = 10000$  samples.

  • The considered random variables are here statistically independent from each other. 
  • Thus,  all ACF values should actually be zero with the exception of the value at  $k = 0$.



  • For  $N = 10000$  (lower graph) the maximum error is only about  $1\%$  and is almost invisible in this plot.
  • In contrast,  for  $N = 1000$  (upper graph),  the error grows to $±6\%$.


$\text{Example 6:}$  The results change when there is a random variable with internal statistical bindings.

ACF for correlated samples

For example,  if we consider a triangular ACF with  $φ_x(k) ≠ 0$  for  $\vert k \vert ≤ 10$,  we see much larger deviations, viz.

  • errors up to about  $±15\%$  for  $N = 1000$,
  • errors up to about  $±5\%$  at  $N = 10000$.


Justification of the worse result according to this  $\text{Example 6}$:

  • Due to the internal statistical bindings,  not all samples now provide full information about the underlying random process.
  • Furthermore,  the images reveal that in numerical ACF calculation of a random variable with statistical bindings,  also the errors are correlated.
  • If,  for example,  as seen in the upper image,  the ACF value  $φ_x({\rm 26})$  is spuriously positive and large,  the neighboring ACF values  $φ_x({\rm 25})$  and  $φ_x({\rm 27})$  will also be positive with similar numerical values.  This area is marked by the rectangle in the upper graph.

Exercises for the chapter


Exercise 4.09: Cyclo-Ergodicity

Exercise 4.09Z: Periodic ACF

Exercise 4.10: Binary and Quaternary

Exercise 4.10Z: Correlation Duration

Exercise 4.11: C Program "acf1"

Exercise 4.11Z: C Program "acf2"