Bündelfehlerkanäle

Aus LNTwww
Wechseln zu:Navigation, Suche

Kanalmodell nach Gilbert–Elliott (1)


Dieses auf E. N. Gilbert Gilbert, E. N.: Capacity of Burst–Noise Channel. In: Bell Syst. Techn. J. Vol. 39, 1960, pp. 1253–1266 und E. O. Elliott Elliott, E.O.: Estimates of Error Rates for Codes on Burst–Noise Channels. In: Bell Syst. Techn. J., Vol. 42, (1963), pp. 1253 – 1266 zurückgehende Kanalmodell eignet sich zur Beschreibung und Simulation von digitalen Übertragungssystemen mit Bündelfehlercharakteristik.

Gilbert–Elliott–Kanalmodell

Das Gilbert–Elliott–Modell (Kurzbezeichnung: GE–Modell) lässt sich wie folgt charakterisieren:

  • Die unterschiedliche Übertragungsqualität zu unterschiedlichen Zeiten wird durch eine endliche Anzahl g von Kanalzuständen (Z1, Z2, ..., Zg) ausgedrückt.
  • Die in Wirklichkeit fließenden Übergänge der Störintensität – im Extremfall von völlig fehlerfreier Übertragung bis hin zum Totalausfall – werden beim GE–Modell durch feste Wahrscheinlichkeiten in den einzelnen Kanalzuständen approximiert.
  • Die Übergänge zwischen den g Zuständen erfolgen gemäß einem Markovprozess (1. Ordnung) und werden durch g · (g – 1) Übergangswahrscheinlichkeiten gekennzeichnet. Zusammen mit den g Fehlerwahrscheinlichkeiten in den einzelnen Zuständen gibt es somit g2 freie Modellparameter.
  • Aus Gründen der mathematischen Handhabbarkeit beschränkt man sich meist auf g = 2 Zustände und bezeichnet diese mit „G” (GOOD) und „B” (BAD). Meist wird die Fehlerwahrscheinlichkeit im Zustand „G” sehr viel kleiner sein als im Zustand „B”.
  • Im Folgenden benutzen wir diese beiden Fehlerwahrscheinlichkeiten pG und pB, wobei pG < pB gelten soll, sowie die Übergangswahrscheinlichkeiten Pr(B|G) und Pr(G|B). Damit sind auch die beiden anderen Übergangswahrscheinlichkeiten festgelegt:
\[{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} G) = 1 - {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G), \hspace{0.2cm} {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} B) = 1 - {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)\hspace{0.05cm}.\]

Kanalmodell nach Gilbert–Elliott (2)


Beispielhaft betrachten wir nun das GE–Modell mit den Parametern

\[p_{\rm G} = 0.01, \hspace{0.2cm}p_{\rm B} = 0.4, \hspace{0.2cm}{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) = 0.1, \hspace{0.2cm} {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) = 0.01\hspace{0.05cm}.\]

Betrachtetes GE–Modell

Die nachfolgende Grafik zeigt eine dazugehörige (mögliche) Fehlerfolge der Länge N = 800.

Beispielhafte GE–Fehlerfolge

Befindet sich das GE–Modell im Zustand „BAD”, so erkennt man dies an der grauen Hinterlegung. Die Wahrscheinlichkeiten, dass sich die Markovkette im Zustand „G” bzw. „B” befindet, lassen sich aus der vorausgesetzten Homogenität und Stationarität berechnen. Man erhält mit den obigen Zahlenwerten:

\[w_{\rm G} \hspace{-0.15cm} = \hspace{-0.15cm} {\rm Pr(im\hspace{0.15cm} Zustand \hspace{0.15cm}G)}= \frac{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)}{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) + {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)} = \frac{0.1}{0.1 + 0.01} = {10}/{11}\hspace{0.05cm},\] \[w_{\rm B} \hspace{-0.15cm} = \hspace{-0.15cm} {\rm Pr(im\hspace{0.15cm} Zustand \hspace{0.15cm}B)}= \frac{{\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)}{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) + {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)} = \frac{0.11}{0.1 + 0.01} = {1}/{11}\hspace{0.05cm}.\]

Damit kann auch die mittlere Fehlerwahrscheinlichkeit des GE–Modells ermittelt werden:

\[p_{\rm M} = w_{\rm G} \cdot p_{\rm G} + w_{\rm B} \cdot p_{\rm B} = \frac{p_{\rm G} \cdot {\rm Pr}({\rm G\hspace{0.05cm}|\hspace{0.05cm} B)}+ p_{\rm B} \cdot {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)}{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) + {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)} \hspace{0.05cm}.\]

Insbesondere gilt für das hier beispielhaft betrachtete Modell:

\[p_{\rm M} ={10}/{11} \cdot 0.01 +{1}/{11} \cdot 0.4 = {1}/{22} \approx 4.55\%\hspace{0.05cm}.\]

Zur Simulation einer GE–Fehlerfolge wird zwischen den Zuständen „G” und „B” entsprechend den vier Übergangswahrscheinlichkeiten umgeschaltet. Beim ersten Aufruf erfolgt die Auswahl des Zustandes zweckmäßigerweise entsprechend den Wahrscheinlichkeiten wG und wB.

Zu jedem Taktzeitpunkt wird genau ein Element der Fehlerfolge 〈eν〉 entsprechend der aktuellen Fehlerwahrscheinlichkeit (pG bzw. pB) erzeugt. Die Simulation des Fehlerabstandes ist hier nicht anwendbar, da ein Zustandswechsel nach jedem Symbol (und nicht nur nach einem Fehler) möglich ist.

Fehlerabstandsverteilung des GE–Modells


In Huber, J.: Codierung für gedächtnisbehaftete Kanäle. Dissertation – Universität der Bundeswehr München, 1982 finden sich die analytischen Berechnungen

  • der Wahrscheinlichkeit des Fehlerabstandes k:
\[{\rm Pr}(a=k) = \alpha_{\rm G} \cdot \beta_{\rm G}^{\hspace{0.05cm}k-1} \cdot (1- \beta_{\rm G}) + \alpha_{\rm B} \cdot \beta_{\rm B}^{\hspace{0.05cm}k-1} \cdot (1- \beta_{\rm B})\hspace{0.05cm},\]
  • der Fehlerabstandsverteilung:
\[V_a(k) = {\rm Pr}(a \ge k) = \alpha_{\rm G} \cdot \beta_{\rm G}^{\hspace{0.05cm}k-1} + \alpha_{\rm B} \cdot \beta_{\rm B}^{\hspace{0.05cm}k-1} \hspace{0.05cm}.\]

Hierbei sind folgende Hilfsgrößen verwendet:

\[u_{\rm GG} \hspace{-0.1cm} = \hspace{-0.1cm}{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} G ) \cdot (1-{\it p}_{\rm G}) \hspace{0.05cm},\hspace{0.2cm} {\it u}_{\rm GB} ={\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G ) \cdot (1-{\it p}_{\hspace{0.03cm} \rm G}) \hspace{0.05cm},\] \[u_{\rm BB} \hspace{-0.1cm} = \hspace{-0.1cm} {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} B ) \cdot (1-{\it p}_{\hspace{0.03cm}\rm B}) \hspace{0.05cm},\hspace{0.29cm} {\it u}_{\rm BG} ={\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B ) \cdot (1-{\it p}_{\hspace{0.03cm}\rm B})\hspace{0.05cm}\]

\[\Rightarrow \hspace{0.3cm} \beta_{\rm G} \hspace{-0.1cm} = \hspace{-0.1cm}\frac{u_{\rm GG} + u_{\rm BB} + \sqrt{(u_{\rm GG} - u_{\rm BB})^2 + 4 \cdot u_{\rm GB}\cdot u_{\rm BG}}}{2} \hspace{0.05cm},\] \[\hspace{0.8cm}\beta_{\rm B} \hspace{-0.1cm} = \hspace{-0.1cm}\frac{u_{\rm GG} + u_{\rm BB} - \sqrt{(u_{\rm GG} - u_{\rm BB})^2 + 4 \cdot u_{\rm GB}\cdot u_{\rm BG}}}{2}\hspace{0.05cm}.\]

\[x_{\rm G} =\frac{u_{\rm BG}}{\beta_{\rm G}-u_{\rm BB}} \hspace{0.05cm},\hspace{0.2cm} x_{\rm B} =\frac{u_{\rm BG}}{\beta_{\rm B}-u_{\rm BB}}\]

\[\Rightarrow \hspace{0.3cm} \alpha_{\rm G} = \frac{(w_{\rm G} \cdot p_{\rm G} + w_{\rm B} \cdot p_{\rm B}\cdot x_{\rm G})( x_{\rm B}-1)}{p_{\rm M} \cdot( x_{\rm B}-x_{\rm G})} \hspace{0.05cm}, \hspace{0.2cm}\alpha_{\rm B} = 1-\alpha_{\rm G}\hspace{0.05cm}.\]

Die angegebenen Gleichungen sind das Ergebnis umfangreicher Matrizenoperationen.

Fehlerabstandsverteilung von GE– und BSC–Modell

  • Die Abbildung zeigt die Fehlerabstandsverteilung (FAV) des GE–Modells (rote Kurve) in linearer und logarithmischer Darstellung für Pr(G|B) = 0.1, Pr(B|G) = 0.01, pG = 0.001 und pB = 0.4.
  • Zum Vergleich ist auch der Verlauf von Va(k) für das BSC–Modell mit der gleichen mittleren Fehlerwahrscheinlichkeit pM = 4.5% als blaue Kurve eingezeichnet.

Fehlerkorrelationsfunktion des GE–Modells


Für die Fehlerkorrelationsfunktion (FKF) ergibt sich mit der mittleren Fehlerwahrscheinlichkeit pM, den Übergangswahrscheinlichkeiten Pr(B|G) und Pr(G|B) sowie den Fehlerwahrscheinlichkeiten pG und pB in den zwei Zuständen „G” und „B” nach umfangreichen Matrizenoperationen der relativ einfache Ausdruck

\[\varphi_{e}(k) = \left\{ \begin{array}{c} p_{\rm M} \\ p_{\rm M}^2 + (p_{\rm B} - p_{\rm M}) (p_{\rm M} - p_{\rm G}) [1 - {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G )- {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B )]^k \end{array} \right.\quad \begin{array}{*{1}c} f{\rm \ddot{u}r }\hspace{0.15cm}k = 0 \hspace{0.05cm}, \\ f{\rm \ddot{u}r }\hspace{0.15cm} k > 0 \hspace{0.05cm}.\\ \end{array}\]

Der nur für „erneuernde Modelle” gültige Zusammenhang zwischen FKF und FAV ist hier nicht gegeben (GE–Modell ist nicht erneuernd!)  ⇒  Zur Berechnung unbedingt φe(k) = E[eν · eν+k] verwenden.

In der Grafik ist ein beispielhafter FKF–Verlauf des GE–Modells mit roten Kreisen markiert eingetragen. Während beim gedächtnislosen Kanal (BSC–Modell, blaue Kurve) alle FKF–Werte φe(k ≠ 0) gleich pM2 sind, nähern sich die FKF–Werte beim Bündelfehlerkanal diesem Endwert deutlich langsamer.

Fehlerkorrelationsfunktion von GE-Modell (Kreise) und BSC-Modell (Kreuze)

Weiter erkennt man aus dieser Darstellung:

  • Beim Übergang von k = 0 nach k = 1 tritt eine gewisse Unstetigkeit auf. Während φe(k = 0) = pM ist, ergibt sich mit der für k > 0 gültigen zweiten Gleichung für k = 0 folgender extrapolierter Wert:
\[\varphi_{e0} = p_{\rm M}^2 + (p_{\rm B} - p_{\rm M}) \cdot (p_{\rm M} - p_{\rm G})\hspace{0.05cm}.\]
  • Ein quantitatives Maß für die Länge der statistischen Bindungen ist die Korrelationsdauer DK, die allgemein als die Breite eines flächengleichen Rechtecks mit der Höhe φe0pM2 definiert ist:
\[D_{\rm K} = \frac{1}{\varphi_{e0} - p_{\rm M}^2} \cdot \sum_{k = 1 }^{\infty}\hspace{0.1cm} [\varphi_{e}(k) - p_{\rm M}^2]\hspace{0.05cm}.\]
  • Beim Gilbert–Elliott–Modell erhält man hierfür den einfachen, analytisch angebbaren Ausdruck
\[D_{\rm K} =\frac{1}{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B ) + {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G )}-1 \hspace{0.05cm}.\]
  • DK ist umso größer, je kleiner Pr(B|G) und Pr(G|B) sind (also Zustandswechsel selten auftreten). Für das BSC–Modell (pB = pG = pM, DK = 0) ist die Gleichung nicht anwendbar.

Kanalmodell nach McCullough (1)


Der wesentliche Nachteil des GE–Modells ist, dass damit eine Fehlerabstandssimulation nicht möglich ist. Wie in der Aufgabe A5.5 herausgearbeitet wurde, hat diese gegenüber der symbolweisen Generierung der Fehlerfolge 〈eν〉 große Vorteile hinsichtlich Rechengeschwindigkeit und Speicherbedarf.

McCullough McCullough, R.H.: The Binary Regenerative Channel. In: Bell Syst. Techn. J. (47), 1968 hat das drei Jahre zuvor von Gilbert und Elliott entwickelte Modell dahingehend modifiziert, dass eine Fehlerabstandssimulation in den beiden Zustände „GOOD” und „BAD” jeweils für sich anwendbar ist. Die Grafik zeigt unten das Modell von McCullough, im Folgenden als MC–Modell bezeichnet, während oben das GE–Modell nach Umbenennung der Übergangswahrscheinlichkeiten ⇒ p(B|G) = Pr(B|G), p(G|B) = Pr(G|B) usw. dargestellt ist.

Kanalmodelle nach Gilbert–Elliott (oben) und McCullough (unten)

Zwischen den beiden Modellen bestehen viele Gemeinsamkeiten und einige wenige Unterschiede:

  • Das McCullough–Kanalmodell beruht wie das Gilbert–Elliott–Modell auf einem Markovprozess erster Ordnung mit den beiden Zuständen „G” (GOOD) und „B” (BAD). Hinsichtlich der Modellstruktur ist kein Unterschied feststellbar.
  • Der wesentliche Unterschied zum GE–Modell besteht darin, dass ein Zustandswechsel zwischen „G” und „B” jeweils nur nach einem Fehler – also einer „1” in der Fehlerfolge – möglich ist. Dies ermöglicht eine Fehlerabstandssimulation.
  • Die vier frei wählbaren GE–Parameter pG, pB, p(B|G) und p(G|B) können – wie auf der nächsten Seite gezeigt – so in die MC–Parameter qG, qB, q(B|G) und q(G|B) umgerechnet werden, dass eine in ihren statistischen Eigenschaften gleiche Fehlerfolge wie beim GE–Modell erzeugt wird.
  • Beispielsweise bezeichnet q(B|G) die Übergangswahrscheinlichkeit von dem Zustand „G” in den Zustand „B” unter der Voraussetzung, dass im Zustand „G” gerade ein Fehler aufgetreten ist. Der GE–Parameter p(B|G) kennzeichnet diese Übergangswahrscheinlichkeit ohne Zusatzbedingung.