Difference between revisions of "Aufgaben:Exercise 4.7: Product Code Decoding"
| Line 126: | Line 126: | ||
| − | '''(3)''' | + | '''(3)''' Vergleicht man die Coder– und Empfangsmatrizen (Unterschiede sind blau markiert), so kann man entsprechend der folgenden Grafik durch Modulo–2–Additionen die Fehlermatrix erstellen. |
| + | |||
| + | [[File:P_ID3010__KC_A_4_7c_v2.png|center|frame|Matrizendarstellung von Coder, Empfänger und Fehlermuster]] | ||
| + | |||
| + | Die Fehlermatrix ist gleich der Empfangsmatrix von $\mathbf{A}$ ⇒ auch hier ist der <u>Lösungsvorschlag 3</u> richtig. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Revision as of 13:11, 10 December 2017
Wir betrachten wie in Aufgabe A4.6 einen Produktcode, basierend auf
- dem Hammingcode (7, 4, 3) ⇒ Code $C_1$,
- dem verkürzten Hammingcode (6, 3, 3) ⇒ $C_2$.
Die Prüfmatrizen dieser Codes lauten:
- $${ \boldsymbol{\rm H}}_1 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 \\ 0 &1 &1 &1 &0 &1 &0 \\ 1 &0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},$$
- $${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &0 &0 \\ 1 &0 &1 &0 &1 &0 \\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
Die Hard Decision Decodierung dieses Codes geschieht vorzugsweise iterativ, indem abwechselnd alle Zeilen und anschließend alle Spalten syndromdecodiert werden.
Hinweis: Die Syndromdecodierung soll entsprechend der zweiten Theorieseite von Kapitel 4.2 erfolgen.
Die folgende Grafik zeigt drei verschiedene Coder– und Empfangsmatrizen, die in den Teilaufgaben (1), (2) und (3) zu analysieren sind. Wir benennen diese mit Konstellation (A), (B) und (C). Gelb markiert sind die Unterschiede der Empfangsmatrix von Konstellation (B) gegenüber (A). In beiden Fällen besteht die Codermatrix nur aus Nullen. Die Codematrix von (C) wurde in Aufgabe A4.6 ermittelt.
Die Syndromdecodierung (eindimensionaler) Blockcodes wurde bereits im Kapitel Decodierung linearer Blockcodes behandelt. Hier eine kurze Zusammenfassung und eine Adaption an den zweidimensionalen Fall:
- Aus dem Empfangswort $\underline{y}$ (einer Zeile bzw. einer Spalte der vorgegebenen Empfangsmatrix) wird das Syndrom entsprechend $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$ bzw. $\underline{s} = \underline{y} \cdot \mathbf{H}_2^{\rm T}$ gebildet.
- Mit dem Ergebnis $\underline{s} = \underline{s}_{\mu}$ kann man in obigen Tabellen den so genannten Nebenklassenanfüherer $\underline{e}_{\mu}$ ablesen. Das korrigierte Codewort ist dann $\underline{y} + \underline{e}_{\mu}$.
Fragebogen
Musterlösung
- Die Einzelfehler in den Zeilen 1, 3, 5 und 6 werden vom (7, 4, 3)–Hammingcode erkannt und können korrigiert werden ⇒ grüne Markierungen in der Grafik „1. Iteration horizontal”.
- Für die zweite Zeile ergibt sich das Syndrom
- $$\underline{s} = \underline{y}_2 \hspace{-0.03cm}\cdot \hspace{-0.03cm}{ \boldsymbol{\rm H}}_1^[[:Template:\rm T]] = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot \hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 \\ 1 &1 &0 \\ 0 &1 &1 \\ 1 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix} \hspace{-0.05cm}= \left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right ) + \left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}1 \right )= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}1 \right ) = \underline{s}_1 \hspace{0.03cm}.$$
Nach der oberen Syndromtabelle auf der Angabenseite wird somit fälschlicherweise das letzte Bit „korrigiert”. Fehlerkorrekturen sind in der oberen Grafik rot eingetragen.
- Entsprechend gilt für die vierte Zeile:
- $$\underline{s} = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0 \right ) \cdot { \boldsymbol{\rm H}}_1^[[:Template:\rm T]] = \left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right ) + \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right )= \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right )= \underline{s}_4 \hspace{0.05cm}.$$
- Dies bewirkt eine Fehlkorrektur von Bit 5.
- Die vertikale Decodierung der Spalten 1, 3, 4, 5, 6 und 7 ist problemlos, da höchstens ein Fehler pro Spalte auftritt, der durch den verkürzten Hammingcode (6, 3, 3) korrigiert werden kann.
- In Spalte 2 kommt es dagegen zu einer Fehlkorrektur des letzten Bits entsprechend der unteren Syndromtabelle. Mit der Transponierten der (6, 3)–Prüfmatrix $\mathbf{H}_2$ ergibt sich nämlich:
- $$\underline{s}= \underline{y}_{2{\rm S}}\cdot { \boldsymbol{\rm H}}_2^[[:Template:\rm T]] = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot \begin{pmatrix} 1 &1 &0 \\ 1 &0 &1 \\ 0 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}= \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}1 \right ) + \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right )= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}1 \right ) = \underline{s}_1.$$
- Die zweite Horizontaldecodierung ist problemlos, da nun in jeder Zeile maximal ein Fehler auftritt ⇒ Lösungsvorschlag 3.
(2) Die folgende Grafik zeigt den Decodiervorgang entsprechend den Vorgaben gemäß $\mathbf{B}$.
Trotz nur geringfügigen Modifikationen gegenüber $\mathbf{A}$ gibt es nun gravierende Unterschiede:
- Durch die erste Horizontaldecodierung lauten nun die „korrigierten” Zeilen 2 und 4 gleichermaßen: $(0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1)$, das heißt, das letzte Bit dieser Zeilen wird jeweils fehlkorrigiert.
- Die Vertikaldecodierung führt zu gleichlautenden Spalten 2, 4 und 6, nämlich $(0, \, 1, \, 0, \, 1, \, 0, \, 1)$. Danach gibt es in jeder Zeile und in jeder Spalte drei Einsen (oder keine einzige).
- Diese Konstellation bleibt für beliebig weitere (horizontale oder vertikale) Decodierungen erhalten, weil sich für $d_{\rm min} = 3$ stets das Syndrom $\underline{s}_0 (0, \, 0, \, 0)$ ergibt.
Richtig ist also der Lösungsvorschlag 5.
(3) Vergleicht man die Coder– und Empfangsmatrizen (Unterschiede sind blau markiert), so kann man entsprechend der folgenden Grafik durch Modulo–2–Additionen die Fehlermatrix erstellen.
Die Fehlermatrix ist gleich der Empfangsmatrix von $\mathbf{A}$ ⇒ auch hier ist der Lösungsvorschlag 3 richtig.
