Kanalcodierung/Beispiele binärer Blockcodes

1. Kanalcodierung
2. Binäre Blockcodes zur Kanalcodierung
3. Beispiele binärer Blockcodes

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Single Parity–check Codes (1)

Der Single Parity–check Code (SPC) fügt zu dem Informationsblock u = (u₁, u₂, ... , u_k) ein Prüfbit (englisch: Parity) p hinzu:

\[\underline{u} = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x} = (x_1, x_2,\hspace{0.05cm} ... \hspace{0.05cm} , x_n) = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k, p) \hspace{0.05cm}.\]

Die Grafik zeigt drei Beispiele solcher Codes mit |C| = 4 (k = 2), |C| = 8 (k = 3) und |C| = 16 (k = 4).

Dieser sehr einfache Code ist wie folgt charakterisiert:

• Aus n = k + 1 folgt für die Coderate R = k/n = (n – 1)/n und für die Redundanz 1 – R = 1/n. Für k = 2 ergibt sich zum Beispiel die Coderate 2/3 und die relative Redundanz beträgt 33.3%.

• Das Prüfbit erhält man durch die Modulo–2–Addition. Darunter versteht man die Addition im Galoisfeld zur Basis 2  ⇒  GF(2), sodass 1⊕1 = 0 ergibt:

\[p = u_1 \oplus u_2 \oplus ... \hspace{0.05cm} \oplus u_k \hspace{0.05cm}.\]

• Damit enthält jedes gültige Codewort x eine gerade Anzahl von Einsen. Ausgedrückt mit ⊕ bzw. in vereinfachter Schreibweise entsprechend der zweiten Gleichung lautet diese Bedingung:

\[ x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n = 0 \hspace{0.05cm}, \hspace{0.5cm}{\rm oder:}\hspace{0.15cm} \sum_{i=1}^{n} \hspace{0.2cm} x_i = 0\hspace{0.05cm} , \hspace{0.3cm} {\rm Addition\hspace{0.15cm} in \hspace{0.15cm} GF(2)} \hspace{0.05cm}. \]

• Für k = 2 ⇒ n = 3 ergeben sich die folgenden vier Codeworte, wobei in der ersten Zeile das Prüfbit jeweils durch einen kleinen Pfeil markiert ist:

\[\underline{x}_0 = (0, 0_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_1 = (0, 1_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_2 = (1, 0 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_3 = (1, 1 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\]

• Es handelt sich um einen linearen Code, da die Summe zweier beliebiger Codeworte wieder ein gültiges Codewort ergibt, zum Beispiel x₁ ⊕ x₂ = x₃.
  

• Für beliebiges k  ⇒  n = k + 1 unterscheidet sich jedes Codewort von allen anderen an einer geraden Anzahl von Positionen. Bei diesem Code ist die minimale Distanz d_min = 2.
  
  

Mit der allgemeinen Codebezeichnung (n, k, d_min) lässt sich jeder Single Parity–check Code auch mit (n, n – 1, 2) benennen. Die Grafik zeigt den SPC (3, 2, 2), den SPC (4, 3, 2) und den SPC (5, 4, 2).

: Jeder Single Parity–check Code (SPC) lässt sich formal wie folgt beschreiben: \[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\hspace{-0.15cm}: \hspace{0.15cm}{\rm mit \hspace{0.15cm}geradzahliger\hspace{0.15cm} Anzahl\hspace{0.15cm} von\hspace{0.15cm} Einsen\hspace{0.15cm} in \hspace{0.15cm}} \underline{x} \}\hspace{0.05cm}.\]

Single Parity–check Codes (2)

Der digitale Kanal ändert möglicherweise das Codewort x = (x₁, x₂, ... , x_n) in das Empfangswort y = (y₁, y₂, ... , y_n), wobei mit dem Fehlervektor e = (e₁, e₂, ... , e_n) gilt: y = x ⊕ e. Zur Decodierung des Single Parity–check Codes bildet man das sogenannte Syndrom:

\[s = y_1 \oplus y_2 \oplus ... \hspace{0.05cm} \oplus y_n = \sum_{i=1}^{n} \hspace{0.2cm} y_i \hspace{0.1cm} \in \hspace{0.2cm} \{0, 1 \} \hspace{0.05cm}.\]

Das Ergebnis „s = 1” weist dann auf (mindestens) einen Bitfehler innerhalb des Codewortes hin, während „s = 0” wie folgt zu interpretieren ist:

• Die Übertragung war fehlerfrei, oder:
  

• Die Anzahl der Bitfehler ist geradzahlig.
  
  

: Wir betrachten den SPC (4, 3, 2) und gehen davon aus, dass das Nullwort gesendet wurde. Die Tabelle zeigt alle Möglichkeiten, dass f Bit verfälscht werden und gibt das jeweilige Syndrom s (entweder 0 oder 1) an.

Für das BSC–Modell mit ε = 1% ergeben sich dann folgende Wahrscheinlichkeiten:

• Das Informationswort wird richtig decodiert (blaue Hinterlegung):

\[{\rm Pr}(\underline{v} = \underline{u}) = {\rm Pr}(\underline{y} = \underline{x}) = (1 - \varepsilon)^n = 0.99^4 \approx 96\,\%\hspace{0.05cm}.\]

• Der Decoder erkennt, dass Übertragungsfehler aufgetreten sind (grüne Hinterlegung):

\[{\rm Pr}(s=1) \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{f=1 \atop f \hspace{0.1cm}{\rm ungerade} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} = \]

\[\hspace{1.8cm} = \hspace{-0.1cm} {4 \choose 1} \cdot 0.01 \cdot 0.99^3 + {4 \choose 3} \cdot 0.01^3 \cdot 0.99 \approx 3.9\,\%\hspace{0.05cm}.\]

• Das Informationswort wird falsch decodiert (rote Hinterlegung):

\[{\rm Pr}(\underline{v} \ne \underline{u}) \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{f=2 \atop f \hspace{0.1cm}{\rm gerade} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} = \]

\[\hspace{2cm} = \hspace{-0.1cm} 1 - {\rm Pr}(\underline{v} = \underline{u}) - {\rm Pr}(s=1)\approx 0.1\,\%\hspace{0.05cm}.\]

Wir verweisen hier auf das Modul Ereigniswahrscheinlichkeiten der Binomialverteilung. Please add link and do not upload flash videos.

In der Aufgabe A1.5 werden die hier gewonnenen Ergebnisse noch ausführlich diskutiert.

Single Parity–check Codes (3)

Eine Fehlerkorrektur des Single Parity–check Codes ist beim BSC–Modell nicht möglich im Unterschied zum BEC–Kanal (Binary Erasure Channel). Bei diesem werden Bitfehler ausgeschlossen. Ist nur ein Bit ausgelöscht (englisch: Erasure, E), so ist aufgrund der Tatsache „die Anzahl der Einsen im Codewort ist gerade” auch eine Fehlerkorrektur möglich, zum Beispiel für den SPC (5, 4):

\[\underline{y} \hspace{-0.1cm} = \hspace{-0.1cm} (1, 0, {\rm E}, 1, 1) \hspace{0.2cm}\Rightarrow\hspace{0.2cm}\underline{z} = (1, 0, 1, 1, 1) \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \underline{v} = (1, 0, 1, 1) = \underline{u}\hspace{0.05cm},\] \[\underline{y} \hspace{-0.1cm} = \hspace{-0.1cm} (0, 1, 1, {\rm E}, 0) \hspace{0.2cm}\Rightarrow\hspace{0.2cm}\underline{z} = (0, 1, 1, 0, 0) \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \underline{v} = (0, 1, 1, 0) = \underline{u}\hspace{0.05cm},\] \[\underline{y} \hspace{-0.1cm} = \hspace{-0.1cm} (0, 1, 0, 1, {\rm E}) \hspace{0.2cm}\Rightarrow\hspace{0.2cm}\underline{z} = (0, 1, 0, 1, 0) \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \underline{v} = (0, 1, 0, 1) = \underline{u}\hspace{0.05cm}.\]

Auch beim AWGN–Kanal ist Fehlerkorrektur möglich, wenn man Soft Decision anwendet. Für das Folgende gehen wir von bipolarer Signalisierung aus: x = 0 → x̃ = +1,    x = 1 → x̃ = –1.

Die Grafik verdeutlicht den hier dargelegten Sachverhalt:

• Beispielsweise lautet der Empfangsvektor (rote Punkte):

\[\underline{y} = (+0.8, -1.2, -0.1, +0.5, -0.6) \hspace{0.05cm}.\]

• Bei harter Entscheidung (Schwelle G = 0, nur die Vorzeichen werden ausgewertet) würde man zu folgendem binären Ergebnis kommen (grüne Quadrate Y_i = y_i / |y_i|):

\[\underline{Y} = (+1, -1, -1, +1, -1) \hspace{0.05cm}.\]

• In Symbolschreibweise ergibt sich daraus (0, 1, 1, 0, 1), was kein gültiges Codewort ist  ⇒  Syndrom s = 1. Also müssen ein, drei oder fünf Bit verfälscht worden sein.
  

• Die Wahrscheinlichkeit für drei oder fünf Bitfehler ist allerdings um Größenordnungen kleiner als diejenige für einen einzigen Fehler. Die Annahme „ein Bitfehler” ist deshalb nicht abwegig.
  

• Da der Empfangswert y₃ sehr nahe an der Schwelle G = 0 liegt, geht man davon aus, dass genau dieses Bit verfälscht wurde. Damit fällt bei Soft Decision die Entscheidung für z = (0, 1, 0, 0, 1)  ⇒  υ = (0, 1, 0, 0). Die Blockfehlerwahrscheinlichkeit Pr(υ ≠ u) ist so am geringsten.