Difference between revisions of "Theory of Stochastic Signals/Gaussian Distributed Random Variables"
m (Text replacement - "”" to """) |
|||
Line 165: | Line 165: | ||
:$$y=m_y+\sigma_{y}\cdot \sin(2 \pi u)\cdot\sqrt{-2\cdot \ln(v)}.$$ | :$$y=m_y+\sigma_{y}\cdot \sin(2 \pi u)\cdot\sqrt{-2\cdot \ln(v)}.$$ | ||
− | Das Verfahren nach Box und Muller – im Folgenden mit „BM | + | Das Verfahren nach Box und Muller – im Folgenden mit „BM" abgekürzt – kann wie folgt charakterisiert werden: |
*Der theoretische Hintergrund für die Gültigkeit obiger Generierungsvorschriften basiert auf den Gesetzmäßigkeiten für [[Theory_of_Stochastic_Signals/Zweidimensionale_Zufallsgrößen|zweidimensionale Zufallsgrößen]]. | *Der theoretische Hintergrund für die Gültigkeit obiger Generierungsvorschriften basiert auf den Gesetzmäßigkeiten für [[Theory_of_Stochastic_Signals/Zweidimensionale_Zufallsgrößen|zweidimensionale Zufallsgrößen]]. | ||
*Obige Gleichungen liefern sukszessive zwei Gaußwerte ohne statistische Bindungen. Diese Tatsache kann man zur Verkürzung der Simulationszeit nutzen, indem man bei jedem Funktionsaufruf ein Tupel $(x, \ y)$ von Gaußwerten generiert. | *Obige Gleichungen liefern sukszessive zwei Gaußwerte ohne statistische Bindungen. Diese Tatsache kann man zur Verkürzung der Simulationszeit nutzen, indem man bei jedem Funktionsaufruf ein Tupel $(x, \ y)$ von Gaußwerten generiert. |
Revision as of 15:20, 28 May 2021
Contents
- 1 Allgemeine Beschreibung
- 2 Wahrscheinlichkeitsdichte- und Verteilungsfunktion
- 3 Überschreitungswahrscheinlichkeit
- 4 Zentralmomente und Momente
- 5 Gauß–Erzeugung mittels Additionsmethode
- 6 Gauß–Erzeugung mit dem Box/Muller–Verfahren
- 7 Gauß–Erzeugung gemäß „Tabulated Inversion”
- 8 Aufgaben zum Kapitel
- 9 Quellenverzeichnis
Allgemeine Beschreibung
Zufallsgrößen mit Gaußscher Wahrscheinlichkeitsdichtefunktion – die Namensgebung geht dabei auf den bedeutenden Mathematiker, Physiker und Astronomen Carl Friedrich Gauß zurück – sind wirklichkeitsnahe Modelle für viele physikalische Größen und haben auch für die Nachrichtentechnik eine große Bedeutung.
$\text{Definition:}$ Zur Beschreibung der Gaußverteilung betrachten wir eine Summe aus $I$ statistischen Größen:
- $$x=\sum\limits_{i=\rm 1}^{\it I}x_i .$$
- Nach dem zentralen Grenzwertsatz der Statistik besitzt diese Summe im Grenzfall $(I → ∞)$ eine Gaußsche WDF, so lange die einzelnen Komponenten $x_i$ keine statistischen Bindungen besitzen. Dies gilt (nahezu) für alle Dichtefunktionen der einzelnen Summanden.
- Viele Rauschprozesse erfüllen genau diese Voraussetzung, das heißt, sie setzen sich additiv aus einer großen Anzahl voneinander unabhängiger Einzelbeiträge zusammen, so dass ihre Musterfunktionen (Rauschsignale) eine Gaußsche Amplitudenverteilung aufweisen.
- Legt man ein gaußverteiltes Signal zur spektralen Formung an ein lineares Filter, so ist das Ausgangssignal ebenfalls gaußverteilt. Es ändern sich nur die Verteilungsparameter wie Mittelwert und Streuung sowie die inneren statistischen Bindungen der Abtastwerte.
$\text{Beispiel 1:}$ Die Grafik zeigt im Vergleich
- links ein Gaußsches Zufallssignal $x_1(t)$ und
- rechts ein gleichverteiltes Signal $x_2(t)$ mit
gleichem Mittelwert $m_1$ und gleicher Streuung $σ$.
Man erkennt, dass bei der Gaußverteilung im Gegensatz zur Gleichverteilung
- beliebig große und beliebig kleine Amplitudenwerte auftreten können,
- auch wenn diese unwahrscheinlich sind im Vergleich zum mittleren Amplitudenbereich.
Wahrscheinlichkeitsdichte- und Verteilungsfunktion
$\text{Definition:}$ Die Wahrscheinlichkeitsdichtefunktion (WDF) einer gaußverteilten Zufallsgröße lautet allgemein:
$$\hspace{0.4cm}f_x(x) = \frac{1}{\sqrt{2\pi}\cdot\sigma}\cdot {\rm e}^{-(x-m_1)^2 /(2\sigma^2) }.$$ Die Parameter einer solchen Gaußschen WDF sind
- $m_1$ (Mittelwert bzw. Gleichanteil),
- $σ$ (Streuung bzw. Effektivwert).
Ist $m_1 = 0$ und $σ = 1$, so spricht man oft auch von der Normalverteilung.
Aus der linken Darstellung der oberen Grafik geht hervor, dass die Streuung $σ$ als der Abstand von Maximalwert und Wendepunkt aus der glockenförmigen WDF $f_{x}(x)$ auch grafisch ermittelt werden kann.
Rechts ist die Verteilungsfunktion $F_{x}(r)$ der gaußverteilten Zufallsgröße dargestellt. Man erkennt:
- Die VTF ist punktsymmetrisch um den Mittelwert $m_1$.
- Durch Integration über die Gaußsche WDF erhält man:
- $$F_x(r)= \phi(\frac{\it r-m_{\rm 1}}{\sigma})\hspace{0.5cm}\rm mit\hspace{0.5cm}\rm \phi (\it x\rm ) = \frac{\rm 1}{\sqrt{\rm 2\it \pi}}\int_{-\rm\infty}^{\it x} \rm e^{\it -u^{\rm 2}/\rm 2}\,\, d \it u.$$
Man bezeichnet $ϕ(x)$ als das Gaußsche Fehlerintegral.
- Dessen Funktionsverlauf ist analytisch nicht berechenbar und muss deshalb aus Tabellen entnommen werden.
- $ϕ(x)$ lässt sich durch eine Taylorreihe annähern oder aus der in Programmbibliotheken oft vorhandenen Funktion ${\rm erfc}(x)$ berechnen.
Weitere Informationen zu den gaußverteilten Zufallsgrößen liefert das Lernvideo Der AWGN–Kanal, insbesondere im zweiten Teil.
Überschreitungswahrscheinlichkeit
Bei der Untersuchung digitaler Übertragungssysteme muss oft die Wahrscheinlichkeit bestimmt werden, dass eine (mittelwertfreie) gaußverteilte Zufallsgröße $x$ mit Varianz $σ^2$ einen vorgegebenen Wert $x_0$ überschreitet.
$\text{Definition:}$ Für diese Überschreitungswahrscheinlichkeit gilt:
- $${\rm Pr}(x > x_{\rm 0})={\rm Q}({x_{\rm 0} }/{\sigma}).$$
- Hierbei bezeichnet ${\rm Q}(x) = 1 − {\rm ϕ}(x)$ die Komplementärfunktion zu $ {\rm ϕ}(x)$.
- Man nennt diese Funktion das Komplementäre Gaußsche Fehlerintegral und es gilt folgende Berechnungsvorschrift:
- $$\rm Q (\it x\rm ) = \rm 1- \phi (\it x)$$
- $$\Rightarrow \hspace{0.3cm}\rm Q (\it x\rm ) = \frac{\rm 1}{\sqrt{\rm 2\pi} }\int_{\it x}^{\rm +\infty}\hspace{-0.4cm}\rm e^{\it - u^{\rm 2}/\hspace{0.05cm} \rm 2}\,d \it u .$$
${\rm Q}(x)$ ist wie ${\rm \phi}(x)$ nicht analytisch lösbar und muss aus Tabellen entnommen werden.
In Bibliotheken findet man oft die Funktion ${\rm erfc}(x)$, die mit ${\rm Q}(x)$ wie folgt zusammenhängt:
- $${\rm Q}(x)={\rm 1}/\hspace{0.05cm}{\rm 2}\cdot \rm erfc({\it x}/{\sqrt{\rm 2} }).$$
Speziell für größere $x$–Werte (also für kleine Fehlerwahrscheinlichkeiten) liefern die nachfolgend angegebenen Schranken brauchbare Abschätzungen für das Komplementäre Gaußsche Fehlerintegral:
- Obere Schranke:
- $${\rm Q_o}(x ) \ge {\rm Q}(x)=\frac{ 1}{\sqrt{2\pi}\cdot x}\cdot {\rm e}^{- x^{2}/\hspace{0.05cm}2}. $$
- Untere Schranke:
- $${\rm Q_u}(x )\le {\rm Q}(x)=\frac{\rm 1-{\rm 1}/{\it x^{\rm 2}}}{\sqrt{\rm 2\pi}\cdot \it x}\cdot \rm e^{-\it x^{\rm 2}/\hspace{0.05cm}\rm 2} =\rm Q_0(\it x \rm ) \cdot \left(\rm 1-{\rm 1}/{\it x^{\rm 2}}\right) .$$
$\text{Fazit:}$ Das Grafik zeigt die $\rm Q$-Funktion in logarithmischer Darstellung für lineare (obere Achse) und logarithmische Abszissenwerte (untere Achse).
- Die obere Schranke (rote Kreise) ist ab ca. $x = 1$ brauchbar, die untere Schranke (grüne Rauten) ab $x ≈ 2$.
- Für $x ≥ 4$ sind beide Schranken innerhalb der Zeichengenauigkeit vom tatsächlichen Verlauf ${\rm Q}(x)$ nicht mehr zu unterscheiden.
Das interaktive Applet Komplementäre Gaußsche Fehlerfunktionen liefert
- die Zahlenwerte der Funktionen ${\rm Q}(x)$ und $1/2 \cdot {\rm erfc}(x)$
- inklusive der hier angegebenen Schranken.
Zentralmomente und Momente
Die Kenngrößen der Gaußverteilung weisen folgende Eigenschaften auf:
- Die Zentralmomente $\mu_k$ $($identisch mit den Momenten $m_k$ der äquivalenten mittelwertfreien Zufallsgröße $x - m_1$ sind bei der Gaußschen WDF wie auch bei der Gleichverteilung aufgrund der symmetrischen Verhältnisse für ungerade Werte von $k$ identisch Null.
- Das zweite Zentralmoment ist definitionsgemäß gleich $\mu_2 = σ^2$.
- Alle höheren Zentralmomente mit geradzahligen Werten von $k$ lassen sich bei gaußförmiger WDF – wohlgemerkt: ausschließlich bei dieser – durch die Varianz $σ^2$ ausdrücken:
- $$\mu_{k}=(k- 1)\cdot (k- 3) \ \cdots \ 3\cdot 1\cdot\sigma^k\hspace{0.2cm}\rm (falls\hspace{0.1cm}\it k\hspace{0.1cm}\rm gerade).$$
- Daraus können die nichtzentrierten Momente $m_k$ wie folgt bestimmt werden:
- $$m_k = \sum\limits_{\kappa= 0}^{k} \left( \begin{array}{*{2}{c}} k \\ \kappa \\ \end{array} \right)\cdot \mu_\kappa \cdot {m_1}^{k-\kappa}.$$
- Diese Gleichung gilt allgemein, also für beliebige Verteilungen.
$\text{Fazit:}$
- Aus der oberen Gleichung folgt direkt $\mu_4 = 3 \cdot σ^4$ und daraus für die Kurtosis der Wert $K = 3$.
- Man bezeichnet deshalb auch häufig $K-3$ als die Gaußabweichung oder als den Excess.
- Ist die Gaußabweichung negativ, so erfolgt der WDF-Abfall schneller als bei der Gaußverteilung. Beispielsweise hat bei einer Gleichverteilung die Gaußabweichung stets den Zahlenwert $1.8 - 3 = -1.2$.
$\text{Beispiel 2:}$ Die ersten Zentralmomente einer Gaußschen Zufallsgröße mit Streuung $σ = 1/2$ sind:
- $$\mu_2 = \frac{1}{4}, \hspace{0.4cm}\mu_4 = \frac{3}{16},\hspace{0.4cm}\mu_6 = \frac{15}{64}, \hspace{0.4cm}\mu_8 = \frac{105}{256}.$$
Alle Zentralmomente mit ungeradem Index sind identisch Null.
Das interaktive Applet WDF, VTF und Momente spezieller Verteilungen gibt u.a. die Kenngrößen der Gaußverteilung an.
Gauß–Erzeugung mittels Additionsmethode
Dieses einfache, auf dem zentralen Grenzwertsatz der Statistik basierende Verfahren zur rechnertechnischen Generierung einer Gaußschen Zufallsgröße soll hier nur stichpunktartig skizziert werden:
(1) Man geht von (zwischen $0$ und $1)$ gleichverteilten und statistisch voneinander unabhängigen Zufallsgrößen $u_i$ aus ⇒ Mittelwert $m_u = 1/2$, Varianz $\sigma_u^2 = 1/12.$
(2) Man bildet nun die Summe über $I$ Summanden, wobei $I$ hinreichend groß gewählt werden muss:
- $$s=\sum\limits_{i=1}^{I}u_i.$$
(3) Nach dem zentralen Grenzwertsatz ist die Zufallsgröße $s$ mit guter Näherung gaußverteilt, wenn $I$ hinreichend groß ist. Dagegen ergibt sich beispielsweise für $I =2$ nur eine amplitudenbegrenzte Dreieck–WDF $($mit Werten zwischen $0$ und $2)$ ⇒ Faltung zweier Rechtecke.
(4) Der Mittelwert der Zufallsgröße $s$ ist somit $m_s = I/2$. Da die gleichverteilten Zufallsgrößen $u_i$ als statistisch voneinander unabhängig vorausgesetzt wurden, können auch ihre Varianzen addiert werden, so dass sich für die Varianz von $s$ der Wert $\sigma_s^2 = I/12$ ergibt.
(5) Soll eine gaußverteilte Zufallsgröße $x$ mit anderem Mittelwert $m_x$ und anderer Streuung $σ_x$ erzeugt werden, so muss noch folgende lineare Transformation durchgeführt werden:
- $$x=m_x+\frac{\sigma_x}{\sqrt{I/\rm 12}}\cdot \bigg[\big (\sum\limits_{\it i=\rm 1}^{\it I}u_i\big )-{I}/{\rm 2}\bigg].$$
(6) Mit dem Parameter $I =12$ vereinfacht sich die Generierungsvorschrift, was man insbesondere bei rechenzeitkritischen Anwendungen ausnutzen kann, zum Beispiel bei einer Echtzeitsimulation:
- $$x=m_x+\sigma_x\cdot \left [\big(\sum\limits_{i=\rm 1}^{12}\it u_i \rm \big )-\rm 6 \right ].$$
$\text{Fazit:}$ Die nach der Additionsmethode $($mit Parameter $I)$ approximierte Gaußsche Zufallsgröße liefert allerdings nur Werte in einem begrenzten Bereich um den Mittelwert $m_x$. Allgemein gilt:
- $$m_x-\sqrt{3 I}\cdot \sigma_x\le x \le m_x+\sqrt{3 I}\cdot \sigma_x.$$
- Der Fehler gegenüber der theoretischen Gaußverteilung ist an diesen Grenzen am größten und wird für steigendes $I$ kleiner.
- Diesen Sachverhalt können Sie sich anhand des Lernvideos Prinzip der Additionsmethode verdeutlichen.
Gauß–Erzeugung mit dem Box/Muller–Verfahren
Bei dieser Methode werden zwei statistisch voneinander unabhängige gaußverteilte Zufallsgrößen $x$ und $y$ aus den beiden zwischen $0$ und $1$ gleichverteilten und statistisch unabhängigen Zufallsgrößen $u$ und $v$ durch nichtlineare Transformation (approximativ) erzeugt:
- $$x=m_x+\sigma_{x}\cdot \cos(2 \pi u)\cdot\sqrt{-2\cdot \ln(v)},$$
- $$y=m_y+\sigma_{y}\cdot \sin(2 \pi u)\cdot\sqrt{-2\cdot \ln(v)}.$$
Das Verfahren nach Box und Muller – im Folgenden mit „BM" abgekürzt – kann wie folgt charakterisiert werden:
- Der theoretische Hintergrund für die Gültigkeit obiger Generierungsvorschriften basiert auf den Gesetzmäßigkeiten für zweidimensionale Zufallsgrößen.
- Obige Gleichungen liefern sukszessive zwei Gaußwerte ohne statistische Bindungen. Diese Tatsache kann man zur Verkürzung der Simulationszeit nutzen, indem man bei jedem Funktionsaufruf ein Tupel $(x, \ y)$ von Gaußwerten generiert.
- Ein Vergleich der Rechenzeiten zeigt, dass – bei jeweils bestmöglicher Implementierung – das BM-Verfahren der Additionsmethode mit $I =12$ etwa um den Faktor $3$ überlegen ist.
- Der Wertebereich ist beim BM-Verfahren weniger begrenzt als bei der Additionsmethode, so dass auch kleine Wahrscheinlichkeiten genauer simuliert werden. Aber auch mit dem BM-Verfahren lassen sich keine beliebig kleinen Fehlerwahrscheinlichkeiten simulieren.
$\text{Beispiel 3:}$ Für die nachfolgende Abschätzung setzen wir die Parameter $m_x = m_y = 0$ und $σ_x = σ_y = 1$ voraus.
- Bei einem 32 Bit-Rechner ist die kleinste darstellbare Floatzahl $2^{-31} ≈ 0.466 · 10^{-9}$. Der Maximalwert des Wurzelausdrucks in der Generierungsvorschrift des BM-Verfahrens kann somit nicht größer als ca. $6.55$ werden und ist zudem äußerst unwahrscheinlich.
- Da sowohl die Cosinus– als auch die Sinusfunktion betragsmäßig auf $1$ beschränkt ist, wäre das gleichzeitig der maximal mögliche Wert für $x$ und $y$.
Eine in [ES96][1] dokumentierte Simulation über $10^{9}$ Abtastwerte hat aber gezeigt, dass das BM-Verfahren nur bis zu Fehlerwahrscheinlichkeiten von $10^{-5}$ die Q-Funktion sehr gut approximiert, dann aber der Kurvenverlauf steil abbricht.
- Der maximal auftretende Wert des Wurzelausdrucks war dabei nicht $6.55$, sondern aufgrund der aktuellen Zufallsgrößen $u$ und $v$ nur etwa $4.6$, womit sich der schlagartige Abfall ab etwa $10^{–5}$ erklären lässt.
- Bei 64 Bit-Rechenoperationen arbeitet dieses Verfahren natürlich deutlich besser.
Gauß–Erzeugung gemäß „Tabulated Inversion”
Bei diesem von Peter Eck und Günter Söder entwickelten Verfahren [ES96][1] wird wie folgt vorgegangen:
(1) Die Gauß–WDF wird in $J$ Intervalle mit gleichen Flächeninhalten – und dementsprechend unterschiedlicher Breite – aufgeteilt, wobei $J$ eine Zweierpotenz darstellt.
(2) Dem Intervall mit Index $j$ wird ein charakteristischer Wert $C_j$ zugeordnet. Somit genügt es, für jeden neuen Funktionswert nur einen Integer-Zahlengenerator aufzurufen, der die ganzzahligen Werte $j = ±1, \hspace{0.1cm}\text{...} \hspace{0.1cm}, ±J/2$ mit gleicher Wahrscheinlichkeit liefert und damit eines der $C_j$ auswählt.
(3) Wird $J$ hinreichend groß gewählt, zum Beispiel $J = 2^{15} = 32\hspace{0.03cm}768,$ so können die $C_j$ vereinfachend gleich den Intervallmittelwerten gesetzt werden. Diese Werte muss man nur einmal berechnen und können bereits vor der eigentlichen Simulation in einer Datei abgelegt werden.
(4) Die Randbereiche sind dagegen problematisch und müssen gesondert behandelt werden. Mittels nichtlinearer Transformation wird hierfür ein Floatwert gemäß den Ausläufern der Gauß-WDF bestimmt.
$\text{Beispiel 4:}$ Die Skizze zeigt die WDF–Aufteilung für $J = 16$ durch die Grenzen $I_{–7}$, ... , $ I_7$.
- Diese Intervallgrenzen wurden so gewählt, dass jedes Intervall die gleiche Fläche $p_j = 1/J = 1/16$ aufweist.
- Der charakteristische Wert $C_j$ eines jeden Intervalls liegt genau in der Mitte zwischen $I_{j–1}$ und $I_j$.
Man erzeugt nun eine gleichverteilte diskrete Zufallsgröße $k$ $($mit Werten zwischen $1$ und $8)$ und zusätzlich ein Vorzeichenbit.
- Bei negativem Vorzeichenbit und $k =4$ wird beispielsweise folgender Wert ausgegeben:
- $$C_{-4} = -C_4 =-(0.49+0.67)/2 =-0.58.$$
- Bei $k =8$ tritt der Sonderfall ein, dass man den Zufallswert $C_8$ durch nichtlineare Transformation entsprechend den Ausläufern der Gaußkurve ermitteln muss.
$\text{Fazit:}$ Die Eigenschaften von „Tabulated Inversion” können wie folgt zusammengefasst werden:
- Diese Methode ist mit $J = 2^{15}$ bei vergleichbarer Simulationsgenauigkeit etwa um den Faktor $8$ schneller als das BM-Verfahren.
- Nachteilig ist, dass nun die Überschreitungswahrscheinlichkeit ${\rm Pr}(x > r)$ in den inneren Bereichen nicht mehr kontinuierlich ist, sondern sich aufgrund der Diskretisierung eine Treppenkurve ergibt. Dieses Manko kann man durch ein größeres $J$ ausgleichen.
- Durch die Sonderbehandlung der Ränder eignet sich das Verfahren auch für sehr kleine Fehlerwahrscheinlichkeiten.
Aufgaben zum Kapitel
Aufgabe 3.6: Verrauschtes Gleichsignal
Aufgabe 3.6Z: Prüfungskorrektur
Aufgabe 3.7: Bitfehlerquote (BER)
Aufgabe 3.7Z: Error Performance
Quellenverzeichnis