Decodierung linearer Blockcodes

1. Kanalcodierung
2. Binäre Blockcodes zur Kanalcodierung
3. Decodierung linearer Blockcodes

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Blockschaltbild und Voraussetzungen

Wir gehen von dem bereits im Kapitel 1.2 gezeigten Blockschaltbild aus, wobei als Kanalmodell meist der Binary Symmetric Channel (BSC) verwendet wird. Zur Codewortschätzung verwenden wir den Maximum–Likelihood–Entscheider (ML), der für binäre Codes ⇒ x ∈ GF(2ⁿ) das gleiche Ergebnis liefert wie der MAP–Empfänger.

Die Aufgabe des Kanaldecoders kann wie folgt beschrieben werden:

• Der Vektor υ nach der Decodierung (an der Sinke) soll möglichst gut mit dem Informationswort u übereinstimmen. Das heißt: Die Blockfehlerwahrscheinlichkeit soll möglichst klein sein:

\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{v} \ne \underline{u}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.\]

• Aufgrund der deterministischen Zuweisungen x = enc(u) bzw. υ = enc^–1(z) gilt aber auch:

\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{z} \ne \underline{x}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.\]

• Gesucht ist somit das zum gegebenen Empfangswort y = x + e am wahrscheinlichsten gesendete Codewort x_i, das als Ergebnis z weiter gegeben wird:

\[\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}|\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.\]

• Beim BSC–Kanal gilt sowohl x_i ∈ GF(2ⁿ) als auch y ∈ GF(2ⁿ), so dass die ML–Regel auch mit der Hamming–Distanz d_H(y, x_i) geschrieben werden kann:

\[\underline{z} = {\rm arg} \min_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} d_{\rm H}(\underline{y} \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})\hspace{0.05cm}.\]

Prinzip der Syndromdecodierung

Vorausgesetzt wird hier ein (n, k)–Blockcode mit der Prüfmatrix H und den systematischen Codeworten

\[\underline{x}\hspace{0.05cm} = (x_1, x_2, ... \hspace{0.05cm}, x_i, ... \hspace{0.05cm}, x_n) = (u_1, u_2, ... \hspace{0.05cm}, u_k, p_1, ... \hspace{0.05cm}, p_{n-k})\hspace{0.05cm}. \]

Mit dem Fehlervektor e gilt dann für das Empfangswort:

\[\underline{y} = \underline{x} + \underline{e} \hspace{0.05cm}, \hspace{0.4cm} \underline{y} \in \hspace{0.1cm} {\rm GF}(2^n) \hspace{0.05cm}, \hspace{0.1cm} \underline{x} \in \hspace{0.1cm} {\rm GF}(2^n) \hspace{0.05cm}, \hspace{0.1cm} \underline{e} \in \hspace{0.1cm} {\rm GF}(2^n) \hspace{0.05cm}.\]

Ein Bitfehler an der Position i, das heißt y_i ≠ x_i, wird ausgedrückt durch den Fehlerkoeffizienten e_i = 1.

: Das Syndrom s = (s₀, s₁, ... , s_m–1) berechnet sich (als Zeilen– bzw. Spaltenvektor) aus dem Empfangswort y und der Prüfmatrix H in folgender Weise:

\[\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T}\hspace{0.3cm}{\rm bzw.}\hspace{0.3cm} \underline{s}^{\rm T} = { \boldsymbol{\rm H}} \cdot \underline{y}^{\rm T}\hspace{0.05cm}.\]

Die Vektorlänge von s ist gleich m = n – k (Zeilenzahl von H).

Das Syndrom s zeigt folgende Charakteristika:

• Wegen x · H^T = 0 hängt s nicht vom Codewort x ab, sondern allein vom Fehlervektor e:

\[\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} = \hspace{0.05cm} \underline{x} \cdot { \boldsymbol{\rm H}}^{\rm T} + \hspace{0.05cm} \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T} = \hspace{0.05cm} \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T} \hspace{0.05cm}.\]

• Bei hinreichend wenig Bitfehlern liefert s einen eindeutigen Hinweis auf die Fehlerpositionen und ermöglicht so eine vollständige Fehlerkorrektur.
  
  

: Ausgehend vom systematischen (7, 4, 3)–Hamming–Code erhält man beispielsweise für den Empfangsvektor y = (0, 1, 1, 1, 0, 0, 1) das folgende Ergebnis:

\[{ \boldsymbol{\rm H}} \cdot \underline{y}^{\rm T} = \begin{pmatrix} 1 &1 &1 &0 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} = \underline{s}^{\rm T} \hspace{0.05cm}.\]

Vergleicht man das Syndrom mit den Prüfgleichungen des Hamming–Codes, so erkennt man, dass

• am wahrscheinlichsten das vierte Symbol (x₄ = u₄) des Codewortes verfälscht wurde,
  

• der Codewortschätzer somit das Ergebnis z = (0, 1, 1, 0, 0, 0, 1) liefern wird.
  

• die Entscheidung nur dann richtig ist, wenn bei der Übertragung nur ein Bit verfälscht wurde.
  
  

Nachfolgend sind die erforderlichen Korrekturen für den (7, 4, 3)–Hamming–Code angegeben, die sich aus dem errechneten Syndrom s entsprechend den Spalten der Prüfmatrix ergeben:

\[\underline{s} \hspace{-0.15cm} = \hspace{-0.15cm} (0, 0, 0) \hspace{0.10cm} \Rightarrow\hspace{0.10cm}{\rm keine\hspace{0.15cm} Korrektur}\hspace{0.05cm};\hspace{0.4cm}\underline{s} = (1, 0, 0)\hspace{0.10cm} \Rightarrow\hspace{0.10cm}p_1{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\] \[\underline{s} \hspace{-0.15cm} = \hspace{-0.15cm}(0, 0, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} p_3{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\hspace{0.82cm}\underline{s} = (1, 0, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_1{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\] \[\underline{s} \hspace{-0.15cm} = \hspace{-0.15cm}(0, 1, 0)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} p_2{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\hspace{0.82cm}\underline{s} = (1, 1, 0)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_3{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\]

\[\underline{s} \hspace{-0.15cm} = \hspace{-0.15cm}(0, 1, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_4{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\hspace{0.82cm}\underline{s} = (1, 1, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_2{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm}. \]

Verallgemeinerung der Syndromdecodierung (1)

Wir fassen die Ergebnisse der letzten Seiten zusammen, wobei wir weiterhin vom BSC–Kanalmodell ausgehen. Das bedeutet: y und e sind Elemente von GF(2ⁿ), während die möglichen Codeworte x_i zum Code C gehören, der einen (n – k)–dimensionalen Untervektorraum von GF(2ⁿ) darstellt. Dann gilt:

• Die Syndromdecodierung ist eine Realisierungsmöglichkeit der Maximum–Likelihood–Detektion von Blockcodes. Man entscheidet sich für das Codewort mit der geringsten Hamming–Distanz zum Empfangswort:

\[\underline{z} = {\rm arg} \min_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} d_{\rm H}(\underline{y} \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})\hspace{0.05cm}.\]

• Die Syndromdecodierung ist aber auch die Suche nach dem wahrscheinlichsten Fehlervektor e, der die Bedingung e · H^T = s erfüllt. Das Syndrom liegt dabei durch s = y · H^T fest.

• Mit dem Hamming–Gewicht w_H(e) kann die zweite Interpretation auch wie folgt mathematisch formuliert werden:

\[\underline{z} = \underline{y} + {\rm arg} \min_{\underline{e}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} {\rm GF}(2^n)} \hspace{0.1cm} w_{\rm H}(\underline{e}_{\hspace{0.03cm}i})\hspace{0.05cm}.\]

Zu beachten ist, dass der Fehlervektor e ebenso wie der Empfangsvektor y ein Element von GF(2ⁿ) ist im Gegensatz zum Syndrom s ∈ GF(2^m) mit der Anzahl m = n – k der Prüfgleichungen. Das bedeutet,

• dass die Zuordnung zwischen Syndrom s und Fehlervektor e nicht eindeutig ist, sondern
  

• dass jeweils 2^k Fehlervektoren zum gleichen Syndrom s führen, die man zu einer Nebenklasse (englisch: Coset) zusammenfasst.
  

Die Grafik verdeutlicht diesen Sachverhalt am Beispiel n = 5 und k = 2 ⇒ m = n – k = 3.

• Die insgesamt 2ⁿ = 32 möglichen Fehlervektoren e werden in 2^m = 8 Nebenklassen Ψ₀, ... , Ψ₇ aufgeteilt, auch „Cosets” genannt. Explizit gezeichnet sind hier nur die Cosets Ψ₀ und Ψ₅.
  

• Alle 2^k = 4 Fehlervektoren des Cosets Ψ_μ führen zum gleichen Syndrom s_μ. Zudem hat jede Nebenklasse einen Anführer e_μ, nämlich denjenigen mit dem minimalen Hamming–Gewicht.
  
  

Die Vorgehensweise bei der Syndromdecodierung wird auf den nächsten Seiten nochmals ausführlich an einem Beispiel erläutert.

Verallgemeinerung der Syndromdecodierung (2)

Die Syndromdecodierung wird hier am Beispiel eines systematischen (5, 2, 3)–Codes beschrieben:

\[\mathcal{C} = \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm}(0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0) \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \}\hspace{0.05cm}.\]

Generatormatrix und Prüfmatrix lauten:

\[{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &1 &1 &0 \\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.4cm} { \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &1 &0 &0 \\ 1 &1 &0 &1 &0 \\ 0 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.\]

Die Tabelle fasst das Endergebnis zusammen.

Zur Herleitung dieser Tabelle ist anzumerken:

• Die Zeile 1 bezieht sich auf das Syndrom s₀ = (0, 0, 0) und die dazugehörige Nebenklasse Ψ₀. Am wahrscheinlichsten ist hier die Fehlerfolge (0, 0, 0, 0, 0) ⇒ kein Bitfehler, die wir als Nebenklassenanführer e₀ bezeichnen. Auch die weiteren Einträge in der ersten Zeile, nämlich (1, 0, 1, 1, 0 ), (0, 1, 0, 1, 1) und (1, 1, 1, 0, 1 ), liefern jeweils das Syndrom s₀ = (0, 0, 0), ergeben sich aber nur mit mindestens drei Bitfehlern und sind entsprechend unwahrscheinlich.
  

• In den Zeilen 2 bis 6 beinhaltet der jeweilige Nebenklassenanführer e_μ genau eine einzige Eins. Dementsprechend ist e_μ stets das wahrscheinlichste Fehlermuster der Klasse Ψ_μ (μ = 1, ... , 5). Die „Mitläufer” ergeben sich erst bei mindestens zwei Übertragungsfehlern.
  

• Das Syndrom s₆ = (1, 0, 1) ist mit nur einem Bitfehler nicht möglich. Bei der Erstellung obiger Tabelle wurden daraufhin alle „5 über 2” = 10 Fehlermuster e mit Gewicht w_H(e) = 2 betrachtet. Die zuerst gefundene Folge mit Syndrom s₆ = (1, 0, 1) wurde als e₆ = (1, 1, 0, 0, 0) ausgewählt. Bei anderer Probierreihenfolge hätte sich auch die Folge (0, 0, 1, 0, 1) aus Ψ₆ ergeben können.
  

• Ähnlich wurde bei der Bestimmung des Anführers e₇ = (0, 1, 1, 0, 0) der Nebenklasse Ψ₇ vorgegangen, die durch das einheitliche Syndrom s₇ = (1, 1, 1) gekennzeichnet ist. Auch in der Klasse Ψ₇ gibt es eine weitere Folge mit Hamming–Gewicht w_H(e) = 2, nämlich (1, 0, 0, 0, 1).
  
  

Die Beschreibung wird auf der nächsten Seite fortgesetzt.

Verallgemeinerung der Syndromdecodierung (3)

Das Beispiel der letzten Seite wird fortgesetzt. Beachten Sie bitte bei der Tabelle, dass der Index μ nicht identisch ist mit dem Binärwert von s_μ. Die Reihenfolge ergibt sich vielmehr durch die Anzahl der Einsen im Nebenklassenanführer e_μ. So ergibt sich beispielsweise das Syndrom s₅ zu (1, 1, 0) und das Syndrom s₆ = (1, 0, 1).

Die obige Tabelle muss nur einmal erstellt und kann beliebig oft genutzt werden. Lautet beispielsweise der Empfangsvektor y = (0, 1, 0, 0, 1), so muss zunächst das Syndrom ermittelt werden:

\[\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 0 &1 &0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 &1 &0 \\ 0 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \\ \end{pmatrix} = \begin{pmatrix} 0 &1 &0 \end{pmatrix}= \underline{s}_2 \hspace{0.05cm}.\]

Mit dem Nebenklassenanführer e₂ = (0, 0, 0, 1, 0) aus obiger Tabelle (roter Eintrag für Index 2) gelangt man schließlich zum Decodierergebnis:

\[\underline{z} = \underline{y} + \underline{e}_2 = (0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1) + (0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0) = (0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1) \hspace{0.05cm}.\]

Aus dieser Kurzzusammenfassung geht schon hervor, dass die Syndromdecodierung mit einem enormen Aufwand verbunden ist, wenn man nicht wie bei zyklischen Codes gewisse Eigenschaften nutzen kann. Bei großen Blockcodelängen versagt diese Methode vollständig. So müsste man zur Decodierung eines BCH–Codes – die Abkürzung steht für deren Erfinder Bose, Chaudhuri und Hocquenghem – mit den Codeparametern n = 511, k = 259 und d_min = 61 genau 2^511–259 ≈ 10⁷⁶ Fehlermuster der Länge 511 auswerten und abspeichern. Für diese Codes und auch für andere Codes großer Blocklänge gibt es aber spezielle Decodieralgorithmen, die mit weniger Aufwand zum Erfolg führen.