Aufgaben:Aufgabe 4.7Z: Zum Prinzip der Syndromdecodierung: Unterschied zwischen den Versionen
Aus LNTwww
| (3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Grundlegendes zu den Produktcodes}} | {{quiz-Header|Buchseite=Kanalcodierung/Grundlegendes zu den Produktcodes}} | ||
| − | [[Datei:P_ID3013__KC_Z_4_7_v1.png|right|frame|Nebenklassenanführer für $\rm HC \ (7, \ 4, \ 3)$]] | + | [[Datei:P_ID3013__KC_Z_4_7_v1.png|right|frame|Nebenklassenanführer für den betrachteten Code $\rm HC \ (7, \ 4, \ 3)$]] |
| − | Die Syndromdecodierung wurde bereits im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes| Decodierung linearer Blockcodes]] ausführlich behandelt. Bei allen Hammingcodes, die ja bekanntlich perfekt sind, ergibt sich hiermit ein gleich gutes Decodierergebnis wie mit der (im allgemeinen) deutlich komplizierteren Maximum–Likelihood–Decodierung. | + | Die Syndromdecodierung wurde bereits im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes| Decodierung linearer Blockcodes]] ausführlich behandelt. Bei allen Hammingcodes, die ja bekanntlich perfekt sind, ergibt sich hiermit ein gleich gutes Decodierergebnis wie mit der (im allgemeinen) deutlich komplizierteren Maximum–Likelihood–Decodierung. |
Bei der Syndromdecodierung geht man wie folgt vor: | Bei der Syndromdecodierung geht man wie folgt vor: | ||
| − | * Man bildet aus dem Empfangsvektor $\underline{y}$ der Länge $n$ und der Prüfmatrix $\mathbf{H}$ das Syndrom: | + | * Man bildet aus dem Empfangsvektor $\underline{y}$ der Länge $n$ und der Prüfmatrix $\mathbf{H}$ das Syndrom: |
:$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) | :$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) | ||
\hspace{0.05cm}, \hspace{0.5cm}{\rm Anmerkung\hspace{-0.10cm}:} \hspace{0.15cm}m = n-k \hspace{0.05cm}. $$ | \hspace{0.05cm}, \hspace{0.5cm}{\rm Anmerkung\hspace{-0.10cm}:} \hspace{0.15cm}m = n-k \hspace{0.05cm}. $$ | ||
| − | * Das Empfangswort $\underline{y} = \underline{x} \ {\rm (Codewort)} + \underline{e} \ {\rm (Fehlervektor)}$ ist nicht notwendigermaßen ein Element von ${\rm GF}(2^m)$, sicher aber ein Element von ${\rm GF}(2^n)$ und es gilt wegen $\underline{x} \cdot \mathbf{H}^{\rm T} = \underline{0}$ gleichermaßen: | + | * Das Empfangswort $\underline{y} = \underline{x} \ {\rm (Codewort)} + \underline{e} \ {\rm (Fehlervektor)}$ ist nicht notwendigermaßen ein Element von ${\rm GF}(2^m)$, sicher aber ein Element von ${\rm GF}(2^n)$ und es gilt wegen $\underline{x} \cdot \mathbf{H}^{\rm T} = \underline{0}$ gleichermaßen: |
:$$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T}\hspace{0.05cm}. $$ | :$$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T}\hspace{0.05cm}. $$ | ||
| − | * Viele Fehlermuster $\underline{e}$ führen zum gleichen Syndrom $\underline{s}$. Man fasst nun diejenigen Fehlermuster mit gleichem Syndrom $\underline{s}_{\mu}$ zur Nebenklasse ${\it \Psi}_{\mu}$ zusammen. | + | * Viele Fehlermuster $\underline{e}$ führen zum gleichen Syndrom $\underline{s}$. Man fasst nun diejenigen Fehlermuster mit gleichem Syndrom $\underline{s}_{\mu}$ zur Nebenklasse ${\it \Psi}_{\mu}$ zusammen. |
| − | * Als Nebenklassenanführer $\underline{e}_{\mu}$ bezeichnet man denjenigen Fehlervektor, der innerhalb der Klasse ${\it \Psi}_{\mu}$ das geringste Hamming–Gewicht aufweist und dementsprechend am wahrscheinlichsten ist. | + | * Als Nebenklassenanführer $\underline{e}_{\mu}$ bezeichnet man denjenigen Fehlervektor, der innerhalb der Klasse ${\it \Psi}_{\mu}$ das geringste Hamming–Gewicht aufweist und dementsprechend am wahrscheinlichsten ist. |
| − | Die Tabelle | + | Die obige Tabelle zeigt die Liste der Nebenklassenanführer $\underline{e}_{\mu}$ für die einzelnen $\underline{s}_{\mu}$ beim Hammingcode $\rm HC \ (7, \ 4, \ 3)$. Diese Tabelle wird für die Teilaufgabe '''(1)''' benötigt. |
| − | Eine ähnliche Tabelle soll für den verkürzten Hammingcode $\rm HC \ (6, \ 3, \ 3)$erstellt werden. Dieser wurde bereits in der [[Aufgaben:4.6_Produktcode%E2%80%93Generierung| Aufgabe 4.6]] sowie der [[Aufgaben:4.6Z_Grundlagen_der_Produktcodes| Aufgabe 4.6Z]] benutzt und ist durch seine Generatormatrix | + | Eine ähnliche Tabelle soll für den verkürzten Hammingcode $\rm HC \ (6, \ 3, \ 3)$ erstellt werden. Dieser wurde bereits in der [[Aufgaben:4.6_Produktcode%E2%80%93Generierung| Aufgabe 4.6]] sowie der [[Aufgaben:4.6Z_Grundlagen_der_Produktcodes| Aufgabe 4.6Z]] benutzt und ist durch seine Generatormatrix gegeben: |
:$${ \boldsymbol{\rm G}} | :$${ \boldsymbol{\rm G}} | ||
= \begin{pmatrix} | = \begin{pmatrix} | ||
| Zeile 27: | Zeile 27: | ||
\end{pmatrix} \hspace{0.05cm}.$$ | \end{pmatrix} \hspace{0.05cm}.$$ | ||
| − | Im Gegensatz zum originalen $\rm (7, \ 4, \ 3)$–Hammingcode ist der verkürzte $\rm (6, \ 3, \ 3)$–Hammingcode nicht perfekt, so dass sich nicht für alle möglichen $\underline{s}_{\mu}$ ein Einfehler–Nebenklassenanführer $\underline{e}_{\mu}$ finden lässt. | + | Im Gegensatz zum originalen $\rm (7, \ 4, \ 3)$–Hammingcode ist der verkürzte $\rm (6, \ 3, \ 3)$–Hammingcode nicht perfekt, so dass sich nicht für alle möglichen $\underline{s}_{\mu}$ ein Einfehler–Nebenklassenanführer $\underline{e}_{\mu}$ finden lässt. |
| + | |||
| + | |||
| + | |||
| + | |||
| Zeile 34: | Zeile 38: | ||
''Hinweise:'' | ''Hinweise:'' | ||
| − | * Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Grundlegendes_zu_den_Produktcodes| Grundlegendes zu den Produktcodes]] und ist als Ergänzung zur [[Aufgaben:4.7_Produktcode%E2%80%93Decodierung| Aufgabe A4.7]] gedacht. | + | * Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Grundlegendes_zu_den_Produktcodes| Grundlegendes zu den Produktcodes]] und ist als Ergänzung zur [[Aufgaben:4.7_Produktcode%E2%80%93Decodierung| Aufgabe A4.7]] gedacht. |
| − | * Ähnliche Aufgabenstellungen wurden in [[Aufgaben:1.11_Syndromdecodierung| Aufgabe | + | * Ähnliche Aufgabenstellungen wurden in der [[Aufgaben:1.11_Syndromdecodierung| Aufgabe 1.11]] und der [[Aufgaben:1.11Z_Nochmals_Syndromdecodierung| Aufgabe 1.11Z]] im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]] behandelt. |
| − | * Der Zusammenhang zwischen | + | * Der Zusammenhang zwischen Generatormatrix $\mathbf{G}$ und Prüfmatrix $\mathbf{H}$ von systematischen Codes ist im Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes| Allgemeine Beschreibung linearer Blockcodes]] angegeben. |
| Zeile 42: | Zeile 46: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Das Empfangswort sei $\underline{y} = (0, \, 1, \, 1,\, 0, \, 1, \, 1, \, 0)$, das Syndrom $\underline{s} = (0, \, 1, \, 1)$. Für welches Codewort $\underline{x}$ von $ | + | {Das Empfangswort sei $\underline{y} = (0, \, 1, \, 1,\, 0, \, 1, \, 1, \, 0)$, das Syndrom $\underline{s} = (0, \, 1, \, 1)$. Für welches Codewort $\underline{x}$ von $\mathcal{C}_1$ entscheidet sich der Syndromdecoder? |
|type="()"} | |type="()"} | ||
| − | - Das wahrscheinlichste Codewort ist $\ \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0)$. | + | - Das wahrscheinlichste Codewort ist $\ \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0)$. |
| − | + Das wahrscheinlichste Codewort ist $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 0)$. | + | + Das wahrscheinlichste Codewort ist $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 0)$. |
| − | - Das wahrscheinlichste Codewort ist $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 1)$. | + | - Das wahrscheinlichste Codewort ist $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 1)$. |
| − | {Welche Aussagen gelten für die Prüfmatrix $\mathbf{H}$ des verkürzten Codes $ | + | {Welche Aussagen gelten für die Prüfmatrix $\mathbf{H}$ des verkürzten Codes $\mathcal{C}_2$? |
|type="[]"} | |type="[]"} | ||
| − | - Es handelt sich um eine $4 × 6$–Matrix. | + | - Es handelt sich um eine $4 × 6$–Matrix. |
| − | + Die erste Zeile dieser Matrix lautet: $\ 110100$. | + | + Die erste Zeile dieser Matrix lautet: $\ 110100$. |
| − | + Die zweite Zeile dieser Matrix lautet: $\ 101010$. | + | + Die zweite Zeile dieser Matrix lautet: $\ 101010$. |
| − | + Die dritte Zeile dieser Matrix lautet: $\ 011001$. | + | + Die dritte Zeile dieser Matrix lautet: $\ 011001$. |
| − | {Welches Syndrom $\underline{s}$ ergibt sich für das Fehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$? | + | {Welches Syndrom $\underline{s}$ ergibt sich für das Fehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$? |
| − | |type=" | + | |type="()"} |
+ $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_0 = (0, \, 0, \, 0)$, | + $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_0 = (0, \, 0, \, 0)$, | ||
- $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_1 = (0, \, 0, \, 1)$, | - $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_1 = (0, \, 0, \, 1)$, | ||
| Zeile 63: | Zeile 67: | ||
{Welche der folgenden Aussagen stimmen bezüglich der Einfehlermuster? | {Welche der folgenden Aussagen stimmen bezüglich der Einfehlermuster? | ||
|type="[]"} | |type="[]"} | ||
| − | + Einfehlermuster $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_6 = (1, \, 1, \, 0)$, | + | + Einfehlermuster $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_6 = (1, \, 1, \, 0)$, |
| − | + Einfehlermuster $\underline{e} = (0, \, 1, \, 0, \, 0, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_5 = (1, \, 0, \, 1)$, | + | + Einfehlermuster $\underline{e} = (0, \, 1, \, 0, \, 0, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_5 = (1, \, 0, \, 1)$, |
| − | + Einfehlermuster $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_3 = (0, \, 1, \, 1)$, | + | + Einfehlermuster $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_3 = (0, \, 1, \, 1)$, |
| − | + Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 1, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_4 = (1, \, 0, \, 0)$, | + | + Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 1, \, 0, \, 0)$ ⇒ Syndrom $\underline{s}_4 = (1, \, 0, \, 0)$, |
| − | + Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 1, \, 0)$ ⇒ Syndrom $\underline{s}_2 = (0, \, 1, \, 0)$, | + | + Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 1, \, 0)$ ⇒ Syndrom $\underline{s}_2 = (0, \, 1, \, 0)$, |
| − | + Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$ ⇒ Syndrom $\underline{s}_1 = (0, \, 0, \, 1)$, | + | + Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$ ⇒ Syndrom $\underline{s}_1 = (0, \, 0, \, 1)$, |
| − | {Welche der folgenden Fehlermuster führen zum Syndrom $\underline{s}_7 = (1, \, 1, \, 1)$? | + | {Welche der folgenden Fehlermuster führen zum Syndrom $\underline{s}_7 = (1, \, 1, \, 1)$? |
|type="[]"} | |type="[]"} | ||
- $\underline{e} = (1, \, 1, \, 0, \, 0, \, 0, \, 0)$, | - $\underline{e} = (1, \, 1, \, 0, \, 0, \, 0, \, 0)$, | ||
| Zeile 80: | Zeile 84: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Aus der [[Aufgaben:4.7Z_Syndromdecodierung_%E2%80%93_Prinzip| Syndromtabelle]] auf der Angabenseite – gültig für den (7, 4, 3) Hammingcode – kann man ablesen, dass das Syndrom $\underline{s} = \underline{s}_3 = (0, \, 1, \, 1)$ mit dem Fehlermuster $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0)$ korrespondiert. Damit ist das Codewort | + | '''(1)''' Richtig ist der <u>Lösungsvorschlag 2</u>: |
| − | :$$\underline{x} = (0, 1, 1, 0, 1, 1, 0) \hspace{0.15cm}+ \hspace{0.15cm}(0, 0, 1, 0, 0, 0, 0) | + | *Aus der [[Aufgaben:4.7Z_Syndromdecodierung_%E2%80%93_Prinzip| Syndromtabelle]] auf der Angabenseite – gültig für den $\rm (7, \ 4, \ 3)$–Hammingcode – kann man ablesen, dass das Syndrom $\underline{s} = \underline{s}_3 = (0, \, 1, \, 1)$ mit dem Fehlermuster $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0)$ korrespondiert. Damit ist das Codewort |
| + | :$$\underline{x} = \underline{y} \hspace{0.15cm}+ \hspace{0.15cm} \underline{y} = (0, 1, 1, 0, 1, 1, 0) \hspace{0.15cm}+ \hspace{0.15cm}(0, 0, 1, 0, 0, 0, 0) | ||
\hspace{0.15cm}= \hspace{0.15cm}(0, 1, 0, 0, 1, 1, 0)$$ | \hspace{0.15cm}= \hspace{0.15cm}(0, 1, 0, 0, 1, 1, 0)$$ | ||
| − | am wahrscheinlichsten und der Syndromdecoder gibt dieses als Ergebnis aus | + | am wahrscheinlichsten und der Syndromdecoder gibt dieses als Ergebnis aus. |
| − | '''(2)''' Die Prüfmatrix $\mathbf{H}$ des verkürzten (6, 3)–Hammingcodes $C_2$ hat $m = n - k = 3$ Zeilen und $n$ Spalten. Es handelt sich demzufolge | + | '''(2)''' Richtig sind die <u>Lösungsvorschläge 2, 3 und 4</u>: |
| + | *Die Prüfmatrix $\mathbf{H}$ des verkürzten $\rm (6, \ 3)$–Hammingcodes $C_2$ hat $m = n - k = 3$ Zeilen und $n$ Spalten. Es handelt sich demzufolge um eine $3 × 6$–Matrix ⇒ die Aussage 1 ist falsch. | ||
| − | Da es sich auch bei $ | + | *Da es sich auch bei $\mathcal{C}_2$ um einen systematischen Code handelt, kann die Generatormatrix $\mathbf{G}$ in folgender Form dargestellt werden: |
:$${ \boldsymbol{\rm G}} | :$${ \boldsymbol{\rm G}} | ||
= \begin{pmatrix} | = \begin{pmatrix} | ||
| Zeile 106: | Zeile 112: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | Somit kann für die Prüfmatrix geschrieben werden: | + | *Somit kann für die Prüfmatrix geschrieben werden: |
:$${ \boldsymbol{\rm H}} | :$${ \boldsymbol{\rm H}} | ||
= \left ( { \boldsymbol{\rm P}}^{\rm T} ; \hspace{0.15cm} { \boldsymbol{\rm I}}_3 \right ) | = \left ( { \boldsymbol{\rm P}}^{\rm T} ; \hspace{0.15cm} { \boldsymbol{\rm I}}_3 \right ) | ||
| Zeile 116: | Zeile 122: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | Hierbei bezeichnet $\mathbf{I}_3$ eine $3 × 3$–Diagonalmatrix, die typisch ist für den systematischen Code. | + | *Hierbei bezeichnet $\mathbf{I}_3$ eine $3 × 3$–Diagonalmatrix, die typisch ist für den systematischen Code. |
| − | + | *Die Lösungsvorschläge 2, 3 und 4 sind somit richtig: | |
| − | * Zeile 1: $\ 110100$, | + | :* Zeile 1: $\ 110100$, |
| − | * Zeile 2: $\ 101010$, | + | :* Zeile 2: $\ 101010$, |
| − | * Zeile 3: $\ 011001$. | + | :* Zeile 3: $\ 011001$. |
| − | '''(3)''' Nach den Aussagen im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes| Decodierung linearer Blockcodes]] kann für das Syndrom auch $\underline{s} = \underline{e} \cdot \mathbf{H}^{\rm T}$ geschrieben werden. Damit erhält man für den fehlerfreien Fall ⇒ $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$: | + | '''(3)''' Richtig ist der <u>Lösungsvorschlag 1</u>: |
| + | *Nach den Aussagen im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes| Decodierung linearer Blockcodes]] kann für das Syndrom auch $\underline{s} = \underline{e} \cdot \mathbf{H}^{\rm T}$ geschrieben werden. | ||
| + | *Damit erhält man für den fehlerfreien Fall ⇒ $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$: | ||
:$$\underline{s}= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot | :$$\underline{s}= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot | ||
\begin{pmatrix} | \begin{pmatrix} | ||
| Zeile 136: | Zeile 144: | ||
\left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right ) = \underline{s}_0.$$ | \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right ) = \underline{s}_0.$$ | ||
| − | |||
| − | '''(4)''' <u>Alle Aussagen</u> stimmen, wie aus der Musterlösung zur letzten Teilaufgabe zu ersehen ist: Die Zeilen der transponierten Prüfmatrix ergeben von oben nach unten gelesen, die jeweiligen Syndrome für die Fehlermuster $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0), \ ... \ , \ \underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$. | + | '''(4)''' <u>Alle Aussagen</u> stimmen, wie aus der Musterlösung zur letzten Teilaufgabe zu ersehen ist: |
| + | *Die Zeilen der transponierten Prüfmatrix ergeben von oben nach unten gelesen, die jeweiligen Syndrome für die Fehlermuster $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0), \hspace{0.05cm} \text{ ... } \hspace{0.05cm} , \ \underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$. | ||
| + | |||
| − | '''(5)''' Die erste Aussage ist falsch, da die beiden ersten Zeilen der transponierten Prüfmatrix $\mathbf{H}^{\rm T}$ aufsummiert $(1, \, 1, \, 0) + (1, \, 0, \, 1) = (0, \, 1, \, 1) = \underline{s_3} ≠ \underline{s}_7$ ergibt. Die | + | '''(5)''' Richtig sind die <u>Lösungsvorschläge 2, 3 und 4</u>: |
| − | * Erste und letzte Zeile: $\ (1, \, 1, \, 0) + (0, \, 0, \, 1) = (1, \, 1, \, 1) = \underline{s}_7$, | + | *Die erste Aussage ist falsch, da die beiden ersten Zeilen der transponierten Prüfmatrix $\mathbf{H}^{\rm T}$ aufsummiert $(1, \, 1, \, 0) + (1, \, 0, \, 1) = (0, \, 1, \, 1) = \underline{s_3} ≠ \underline{s}_7$ ergibt. |
| − | * zweite und fünfte Zeile: $\ (1, \, 0, \, 1) + (0, \, 1, \, 0) = (1, \, 1, \, 1) = \underline{s}_7$, | + | *Die Aussagen 2, 3 und 4 sind dagegen richtig: |
| − | * Die Summe über alle Zeilen ergibt ebenfalls $\underline{s}_7$, da es in jeder Matrixspalte genau drei Einsen gibt. | + | :* Erste und letzte Zeile: $\ (1, \, 1, \, 0) + (0, \, 0, \, 1) = (1, \, 1, \, 1) = \underline{s}_7$, |
| + | :* zweite und fünfte Zeile: $\ (1, \, 0, \, 1) + (0, \, 1, \, 0) = (1, \, 1, \, 1) = \underline{s}_7$, | ||
| + | :* Die Summe über alle Zeilen ergibt ebenfalls $\underline{s}_7$, da es in jeder Matrixspalte genau drei Einsen gibt. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 8. Juli 2019, 11:29 Uhr
Nebenklassenanführer für den betrachteten Code $\rm HC \ (7, \ 4, \ 3)$
Die Syndromdecodierung wurde bereits im Kapitel Decodierung linearer Blockcodes ausführlich behandelt. Bei allen Hammingcodes, die ja bekanntlich perfekt sind, ergibt sich hiermit ein gleich gutes Decodierergebnis wie mit der (im allgemeinen) deutlich komplizierteren Maximum–Likelihood–Decodierung.
Bei der Syndromdecodierung geht man wie folgt vor:
- Man bildet aus dem Empfangsvektor $\underline{y}$ der Länge $n$ und der Prüfmatrix $\mathbf{H}$ das Syndrom:
- $$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}, \hspace{0.5cm}{\rm Anmerkung\hspace{-0.10cm}:} \hspace{0.15cm}m = n-k \hspace{0.05cm}. $$
- Das Empfangswort $\underline{y} = \underline{x} \ {\rm (Codewort)} + \underline{e} \ {\rm (Fehlervektor)}$ ist nicht notwendigermaßen ein Element von ${\rm GF}(2^m)$, sicher aber ein Element von ${\rm GF}(2^n)$ und es gilt wegen $\underline{x} \cdot \mathbf{H}^{\rm T} = \underline{0}$ gleichermaßen:
- $$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T}\hspace{0.05cm}. $$
- Viele Fehlermuster $\underline{e}$ führen zum gleichen Syndrom $\underline{s}$. Man fasst nun diejenigen Fehlermuster mit gleichem Syndrom $\underline{s}_{\mu}$ zur Nebenklasse ${\it \Psi}_{\mu}$ zusammen.
- Als Nebenklassenanführer $\underline{e}_{\mu}$ bezeichnet man denjenigen Fehlervektor, der innerhalb der Klasse ${\it \Psi}_{\mu}$ das geringste Hamming–Gewicht aufweist und dementsprechend am wahrscheinlichsten ist.
Die obige Tabelle zeigt die Liste der Nebenklassenanführer $\underline{e}_{\mu}$ für die einzelnen $\underline{s}_{\mu}$ beim Hammingcode $\rm HC \ (7, \ 4, \ 3)$. Diese Tabelle wird für die Teilaufgabe (1) benötigt.
Eine ähnliche Tabelle soll für den verkürzten Hammingcode $\rm HC \ (6, \ 3, \ 3)$ erstellt werden. Dieser wurde bereits in der Aufgabe 4.6 sowie der Aufgabe 4.6Z benutzt und ist durch seine Generatormatrix gegeben:
- $${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
Im Gegensatz zum originalen $\rm (7, \ 4, \ 3)$–Hammingcode ist der verkürzte $\rm (6, \ 3, \ 3)$–Hammingcode nicht perfekt, so dass sich nicht für alle möglichen $\underline{s}_{\mu}$ ein Einfehler–Nebenklassenanführer $\underline{e}_{\mu}$ finden lässt.
Hinweise:
- Die Aufgabe bezieht sich auf das Kapitel Grundlegendes zu den Produktcodes und ist als Ergänzung zur Aufgabe A4.7 gedacht.
- Ähnliche Aufgabenstellungen wurden in der Aufgabe 1.11 und der Aufgabe 1.11Z im Kapitel Decodierung linearer Blockcodes behandelt.
- Der Zusammenhang zwischen Generatormatrix $\mathbf{G}$ und Prüfmatrix $\mathbf{H}$ von systematischen Codes ist im Kapitel Allgemeine Beschreibung linearer Blockcodes angegeben.
Fragebogen
Musterlösung
(1) Richtig ist der Lösungsvorschlag 2:
- Aus der Syndromtabelle auf der Angabenseite – gültig für den $\rm (7, \ 4, \ 3)$–Hammingcode – kann man ablesen, dass das Syndrom $\underline{s} = \underline{s}_3 = (0, \, 1, \, 1)$ mit dem Fehlermuster $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0)$ korrespondiert. Damit ist das Codewort
- $$\underline{x} = \underline{y} \hspace{0.15cm}+ \hspace{0.15cm} \underline{y} = (0, 1, 1, 0, 1, 1, 0) \hspace{0.15cm}+ \hspace{0.15cm}(0, 0, 1, 0, 0, 0, 0) \hspace{0.15cm}= \hspace{0.15cm}(0, 1, 0, 0, 1, 1, 0)$$
am wahrscheinlichsten und der Syndromdecoder gibt dieses als Ergebnis aus.
(2) Richtig sind die Lösungsvorschläge 2, 3 und 4:
- Die Prüfmatrix $\mathbf{H}$ des verkürzten $\rm (6, \ 3)$–Hammingcodes $C_2$ hat $m = n - k = 3$ Zeilen und $n$ Spalten. Es handelt sich demzufolge um eine $3 × 6$–Matrix ⇒ die Aussage 1 ist falsch.
- Da es sich auch bei $\mathcal{C}_2$ um einen systematischen Code handelt, kann die Generatormatrix $\mathbf{G}$ in folgender Form dargestellt werden:
- $${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} = \left ( { \boldsymbol{\rm I}}_3 ; \hspace{0.15cm} { \boldsymbol{\rm P}} \right ) \hspace{0.5cm}{\rm mit }\hspace{0.5cm} { \boldsymbol{\rm P}} = \begin{pmatrix} 1 &1 &0 \\ 1 &0 &1 \\ 0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
- Somit kann für die Prüfmatrix geschrieben werden:
- $${ \boldsymbol{\rm H}} = \left ( { \boldsymbol{\rm P}}^{\rm T} ; \hspace{0.15cm} { \boldsymbol{\rm I}}_3 \right ) = \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}.$$
- Hierbei bezeichnet $\mathbf{I}_3$ eine $3 × 3$–Diagonalmatrix, die typisch ist für den systematischen Code.
- Die Lösungsvorschläge 2, 3 und 4 sind somit richtig:
- Zeile 1: $\ 110100$,
- Zeile 2: $\ 101010$,
- Zeile 3: $\ 011001$.
(3) Richtig ist der Lösungsvorschlag 1:
- Nach den Aussagen im Kapitel Decodierung linearer Blockcodes kann für das Syndrom auch $\underline{s} = \underline{e} \cdot \mathbf{H}^{\rm T}$ geschrieben werden.
- Damit erhält man für den fehlerfreien Fall ⇒ $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$:
- $$\underline{s}= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0, \hspace{0.03cm}0, \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 ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right ) = \underline{s}_0.$$
(4) Alle Aussagen stimmen, wie aus der Musterlösung zur letzten Teilaufgabe zu ersehen ist:
- Die Zeilen der transponierten Prüfmatrix ergeben von oben nach unten gelesen, die jeweiligen Syndrome für die Fehlermuster $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0), \hspace{0.05cm} \text{ ... } \hspace{0.05cm} , \ \underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$.
(5) Richtig sind die Lösungsvorschläge 2, 3 und 4:
- Die erste Aussage ist falsch, da die beiden ersten Zeilen der transponierten Prüfmatrix $\mathbf{H}^{\rm T}$ aufsummiert $(1, \, 1, \, 0) + (1, \, 0, \, 1) = (0, \, 1, \, 1) = \underline{s_3} ≠ \underline{s}_7$ ergibt.
- Die Aussagen 2, 3 und 4 sind dagegen richtig:
- Erste und letzte Zeile: $\ (1, \, 1, \, 0) + (0, \, 0, \, 1) = (1, \, 1, \, 1) = \underline{s}_7$,
- zweite und fünfte Zeile: $\ (1, \, 0, \, 1) + (0, \, 1, \, 0) = (1, \, 1, \, 1) = \underline{s}_7$,
- Die Summe über alle Zeilen ergibt ebenfalls $\underline{s}_7$, da es in jeder Matrixspalte genau drei Einsen gibt.
