Aufgabe 2.11Z: Erasure–Kanal für Symbole
Das Kanalmodell "Binary Erasure Channel" $\rm (BEC)$ beschreibt einen Auslöschungskanal auf Bitebene:
- Ein Binärsymbol $(0$ bzw. $1)$ wird mit der Wahrscheinlichkeit $1 - \lambda$ richtig übertragen und mit der Wahrscheinlichkeit $\lambda$ als Auslöschung $\rm E$ ("Erasure") markiert.
- Im Gegensatz zum "Binary Symmetric Channel" $\rm (BSC)$ kann es hier nicht zu Verfälschungen $(0 → 1, \ 1 → 0)$ kommen.
Ein Reed–Solomon–Code basiert auf einem Galoisfeld ${\rm GF}(2^m)$ mit ganzzahligem $m$. Somit lässt sich jedes Codesymbol $c$ durch $m$ Bit darstellen. Will man hier das BEC–Modell anwenden, so muss man dieses zum "$m$-BEC-Modell" modifizieren, wie es in der unteren Grafik für $m = 2$ gezeigt ist:
- Alle Codesymbole $($in Binärdarstellung $00, \ 01, \ 10, \ 11)$ werden mit Wahrscheinlichkeit $1 - \lambda_2$ richtig übertragen.
- Damit beträgt die Wahrscheinlichkeit für ein ausgelöschtes Symbol $\lambda_2$.
- Zu beachten ist, dass bereits ein einziges ausgelöschtes Bit zum ausgelöschten Empfangssymbol $y = \rm E$ führt.
Hinweise:
- Die Aufgabe gehört zum Kapitel "Reed–Solomon–Decodierung beim Auslöschungskanal".
- Bei einem auf ${\rm GF}(2^m)$ basierenden Code ist das skizzierte "$2$–BEC–Modell" zum "$m$–BEC" zu erweitern.
- Die Auslöschungswahrscheinlichkeit dieses Modell wird dann mit $\lambda_m$ bezeichnet.
- Für die ersten Teilaufgaben gelte für die Auslöschungswahrscheinlichkeit gemäß der oberen Grafik stets $\lambda = 0.2$.
Fragebogen
Musterlösung
- $$\ {\rm Pr}(y = {\rm E}) = \lambda \ \underline{= 20\%}.$$
Da die Codesymbole $0$ und $1$ gleichwahrscheinlich sind, erhält man für deren Wahrscheinlichkeiten ${\rm Pr}(y = 0) \ \underline{= 40\%}$ und ${\rm Pr}(y = 1) \ \underline{= 40\%}$.
(2) Ohne Einschränkung der Allgemeingültigkeit gehen wir zur Lösung dieser Aufgabe vom Codesymbol $c_{\rm binär} = $ „$00$” aus.
- Entsprechend dem 2–BEC–Modell kann dann das Empfangssymbol $y_{\rm binär}$ entweder „$00$” oder ausgelöscht $(\rm E)$ sein und es gilt:
- $${\rm Pr}(y_{\rm bin} = "00"\hspace{0.05cm} |\hspace{0.05cm} c_{\rm bin} = "00") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} ( 1 - \lambda)^2 = 0.8^2 = 0.64 = 1 - \lambda_2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \lambda_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 - ( 1 - \lambda)^2 \hspace{0.15cm}\underline{= 36\%}\hspace{0.05cm}. $$
- Hierbei ist vorausgesetzt, dass ein Erasure nur vermieden wird, wenn keines der zwei Bit ausgelöscht wurde.
(3) Der $\rm RSC \, (255, \, 223, \, 33)_{256}$ basiert auf dem Galoisfeld $\rm GF(256) = GF(2^8) \ \Rightarrow \ \it m = \rm 8$. Das Ergebnis der Teilaufgabe (2) muss nun an diesen Fall angepasst werden. Für den $8$–BEC gilt:
- $$1 - \lambda_8 = ( 1 - \lambda)^8 = 0.8^8 \approx 0.168 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \lambda_m = \lambda_8 \hspace{0.15cm}\underline{\approx 83.2\%}\hspace{0.05cm}. $$
(4) Aus der Bedingung $\lambda_m ≤ 0.2$ folgt direkt $1 - \lambda_m ≥ 0.8$. Daraus folgt weiter:
- $$( 1 - \lambda)^8 \ge 0.8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 1 - \lambda \ge 0.8^{0.125} \approx 0.9725 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\lambda \hspace{0.15cm} \underline{\le 2.75\%}\hspace{0.05cm}.$$
(5) Hier geht man wie folgt vor:
- Mit $\lambda = 0.0275 \ \Rightarrow \ \lambda_m = 0.2$ sind $20\%$ der Empfangssymbole Erasures.
- Die $2^8 = 256$ Empfangssymbole ($00000000$ ... $11111111$) sind alle gleichwahrscheinlich. Daraus folgt:
- $${\rm Pr}(y_{\rm bin} = 00000000) = \hspace{0.1cm}\text{...} \hspace{0.1cm}= {\rm Pr}(y_{\rm bin} = 11111111)= \frac{0.8}{256} \hspace{0.15cm}\underline{= 0.3125\%}\hspace{0.05cm}.$$
