Aufgaben:Aufgabe 1.11Z: Nochmals Syndromdecodierung: Unterschied zwischen den Versionen
Aus LNTwww
Wael (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Add English interlanguage link |
||
| (12 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes | {{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes}} | ||
[[Datei:P_ID2399__KC_Z_1_10.png|right|frame|Schaubild: Prüfgleichungen]] | |||
Betrachtet wird die gleiche Konstellation wie in [[Aufgaben:1.11_Syndromdecodierung|"Aufgabe 1.11"]], nämlich die Decodierung eines $(7, 4, 3)$–Hamming–Codes mit der Prüfmatrix | |||
Betrachtet wird die gleiche Konstellation wie in | |||
:$${ \boldsymbol{\rm H}}_{\rm } = \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}}_{\rm } = \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}.$$ | ||
Dementsprechend lautet | Dementsprechend lautet die Generatormatrix: | ||
:$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$ | :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$ | ||
Bei der [[Kanalcodierung/Decodierung_linearer_Blockcodes#Prinzip_der_Syndromdecodierung|Syndromdecodierung]] bildet man aus dem Empfangsvektor | Bei der [[Kanalcodierung/Decodierung_linearer_Blockcodes#Prinzip_der_Syndromdecodierung|"Syndromdecodierung"]] bildet man aus dem Empfangsvektor $\underline{y}$ das Syndrom $\underline{s}$ entsprechend der Gleichung | ||
:$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$ | :$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$ | ||
Mit diesem Ergebnis lässt sich beim betrachteten Hamming–Code ein jeder Einzelfehler im Codewort korrigieren. Im fehlerfreien Fall gilt $\underline{s} = \underline{s}_{0} = (0, 0, 0)$. Aber auch bei | Mit diesem Ergebnis lässt sich beim betrachteten Hamming–Code ein jeder Einzelfehler im Codewort korrigieren. | ||
*Im fehlerfreien Fall gilt $\underline{s} = \underline{s}_{0} = (0, 0, 0)$. | |||
*Aber auch bei drei Übertragungsfehlern kann sich unter Umständen $\underline{s}_{0} = (0, 0, 0)$ ergeben, so dass diese Fehler unerkannt bleiben. | |||
Hinweise: | |||
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes|"Decodierung linearer Blockcodes"]]. | |||
* Weitere Informationen zur Syndromdecodierung finden Sie im Angabenblatt zur [[Aufgaben:1.11_Syndromdecodierung|"Aufgabe 1.11"]]. | |||
* Die Grafik verdeutlicht die drei Prüfgleichungen entsprechend der Prüfmatrix: | |||
**erste Zeile: rote Gruppierung, | |||
**zweite Zeile: grüne Gruppierung, | |||
**dritte Zeile: blaue Gruppierung. | |||
===Fragebogen=== | |||
<quiz display=simple> | |||
{Handelt es sich um einen systematischen Code? | {Handelt es sich um einen systematischen Code? | ||
|type=" | |type="()"} | ||
+ Ja, | + Ja, | ||
- Nein. | - Nein. | ||
{Empfangen wurde $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$. Ist dies ein gültiges Codewort? | {Empfangen wurde $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$. Ist dies ein gültiges Codewort? | ||
|type=" | |type="()"} | ||
+ Ja, | + Ja, | ||
- Nein. | - Nein. | ||
{Welches Syndrom ergibt sich mit diesem Empfangswort? | {Welches Syndrom ergibt sich mit diesem Empfangswort? | ||
|type=" | |type="()"} | ||
+ $\underline{s} = \underline{s}_{0} = (0, 0, 0),$ | + $\underline{s} = \underline{s}_{0} = (0, 0, 0),$ | ||
- $\underline{s} = \underline{s}_{3} = (0, 1, 1),$ | - $\underline{s} = \underline{s}_{3} = (0, 1, 1),$ | ||
- $\underline{s} = \underline{s}_{7} = (1, 1, 1).$ | - $\underline{s} = \underline{s}_{7} = (1, 1, 1).$ | ||
{Welche Empfangsworte führen zum gleichen Syndrom wie in Teilaufgabe (3)? | {Welche Empfangsworte führen zum gleichen Syndrom wie in Teilaufgabe '''(3)'''? | ||
|type="[]"} | |type="[]"} | ||
- $\underline{y} = (1, 1, 0, 1, 0, 1, 0),$ | - $\underline{y} = (1, 1, 0, 1, 0, 1, 0),$ | ||
+ $\underline{y} = (0, 1, 0, 1, 0, 0, 1),$ | + $\underline{y} = (0, 1, 0, 1, 0, 0, 1),$ | ||
+ $\underline{y} = (0, 1, 1, 0, 1, 0, 1).$ | + $\underline{y} = (0, 1, 1, 0, 1, 0, 1).$ | ||
</quiz> | |||
===Musterlösung=== | |||
{{ML-Kopf}} | |||
'''(1)''' Die Antwort ist <u>JA</u>, wie man aus der vorgegebenen Prüfmatrix $\mathbf{H}$ erkennt: | |||
*Diese beinhaltet am Ende eine $3×3$–Diagonalmatrix. | |||
*Die Codeworte lauten demzufolge: | |||
:$$ \underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_{3}) \hspace{0.05cm}.$$ | |||
'''(2)''' Mit diesem Empfangsvektor $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ werden alle Prüfgleichungen erfüllt: | |||
</ | :$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$ | ||
:$$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm},$$ | |||
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm}.$$ | |||
Richtig ist dementsprechend die Antwort <u>JA</u>. | |||
'''(3)''' Es gilt $\underline{s} = \underline{y} · \boldsymbol{\rm H}^{\rm T}$: | |||
:$$ \underline{s} = \begin{pmatrix} 1 &0 &0 &1 &0 &1 &0 \end{pmatrix} \cdot \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} = \begin{pmatrix} 0 &0 &0 \end{pmatrix} = \underline{s}_0 \hspace{0.2cm} \Rightarrow\hspace{0.2cm} \hspace{0.15cm} \underline{ \rm Antwort \hspace{0.15cm}1} \hspace{0.05cm}.$$ | |||
'''(4)''' Man könnte nun für jedes $\underline{y}$ die Gleichung $\underline{y} · \boldsymbol{\rm H}^{\rm T} = (0, 0, 0)$ überprüfen. Hier soll nun das Ergebnis auf anderem Wege gewonnen werden: | |||
*$\underline{y}= (1, 1, 0, 1, 0, 1, 0)$ unterscheidet sich von $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ nur im Bit $u_{2}$, das nur in den beiden ersten Prüfgleichungen verwendet wird, nicht jedoch in der letzten ⇒ $\underline{s} = \underline{s}_{6} = (1, 1, 0)$. | |||
*Wendet man die Prüfgleichungen auf $\underline{y} = (0, 1, 0, 1, 0, 0, 1)$ an, so erhält man $\underline{s} = \underline{s}_{0} = (0, 0, 0)$, wie die folgende Rechnung belegt: | |||
:$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$ | |||
:$$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$ | |||
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm}.$$ | |||
*Zum gleichen Ergebnis kommt man mit dem Empfangsvektor $\underline{y} = (0, 1, 1, 0, 1, 0, 1),$ der sich vom Vektor $(1, 0, 0, 1, 0, 1, 0)$ in allen sieben Bitpositionen unterscheidet: | |||
=== | :$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm},$$ | ||
{ | :$$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 1 \oplus 0 \oplus 0 = 0 \hspace{0.05cm},$$ | ||
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm}.$$ | |||
Richtig sind also die <u>Antworten 2 und 3</u>. | |||
{{ML-Fuß}} | |||
^]] | [[Category:Aufgaben zu Kanalcodierung|^1.5 Decodierung linearer Blockcodes^]] | ||
[[en:Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again]] | |||
Aktuelle Version vom 16. März 2026, 14:34 Uhr
Betrachtet wird die gleiche Konstellation wie in "Aufgabe 1.11", nämlich die Decodierung eines $(7, 4, 3)$–Hamming–Codes mit der Prüfmatrix
- $${ \boldsymbol{\rm H}}_{\rm } = \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}.$$
Dementsprechend lautet die Generatormatrix:
- $${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
Bei der "Syndromdecodierung" bildet man aus dem Empfangsvektor $\underline{y}$ das Syndrom $\underline{s}$ entsprechend der Gleichung
- $$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$
Mit diesem Ergebnis lässt sich beim betrachteten Hamming–Code ein jeder Einzelfehler im Codewort korrigieren.
- Im fehlerfreien Fall gilt $\underline{s} = \underline{s}_{0} = (0, 0, 0)$.
- Aber auch bei drei Übertragungsfehlern kann sich unter Umständen $\underline{s}_{0} = (0, 0, 0)$ ergeben, so dass diese Fehler unerkannt bleiben.
Hinweise:
- Die Aufgabe gehört zum Kapitel "Decodierung linearer Blockcodes".
- Weitere Informationen zur Syndromdecodierung finden Sie im Angabenblatt zur "Aufgabe 1.11".
- Die Grafik verdeutlicht die drei Prüfgleichungen entsprechend der Prüfmatrix:
- erste Zeile: rote Gruppierung,
- zweite Zeile: grüne Gruppierung,
- dritte Zeile: blaue Gruppierung.
Fragebogen
Musterlösung
(1) Die Antwort ist JA, wie man aus der vorgegebenen Prüfmatrix $\mathbf{H}$ erkennt:
- Diese beinhaltet am Ende eine $3×3$–Diagonalmatrix.
- Die Codeworte lauten demzufolge:
- $$ \underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_{3}) \hspace{0.05cm}.$$
(2) Mit diesem Empfangsvektor $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ werden alle Prüfgleichungen erfüllt:
- $$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
- $$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm},$$
- $$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm}.$$
Richtig ist dementsprechend die Antwort JA.
(3) Es gilt $\underline{s} = \underline{y} · \boldsymbol{\rm H}^{\rm T}$:
- $$ \underline{s} = \begin{pmatrix} 1 &0 &0 &1 &0 &1 &0 \end{pmatrix} \cdot \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} = \begin{pmatrix} 0 &0 &0 \end{pmatrix} = \underline{s}_0 \hspace{0.2cm} \Rightarrow\hspace{0.2cm} \hspace{0.15cm} \underline{ \rm Antwort \hspace{0.15cm}1} \hspace{0.05cm}.$$
(4) Man könnte nun für jedes $\underline{y}$ die Gleichung $\underline{y} · \boldsymbol{\rm H}^{\rm T} = (0, 0, 0)$ überprüfen. Hier soll nun das Ergebnis auf anderem Wege gewonnen werden:
- $\underline{y}= (1, 1, 0, 1, 0, 1, 0)$ unterscheidet sich von $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ nur im Bit $u_{2}$, das nur in den beiden ersten Prüfgleichungen verwendet wird, nicht jedoch in der letzten ⇒ $\underline{s} = \underline{s}_{6} = (1, 1, 0)$.
- Wendet man die Prüfgleichungen auf $\underline{y} = (0, 1, 0, 1, 0, 0, 1)$ an, so erhält man $\underline{s} = \underline{s}_{0} = (0, 0, 0)$, wie die folgende Rechnung belegt:
- $$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
- $$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
- $$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm}.$$
- Zum gleichen Ergebnis kommt man mit dem Empfangsvektor $\underline{y} = (0, 1, 1, 0, 1, 0, 1),$ der sich vom Vektor $(1, 0, 0, 1, 0, 1, 0)$ in allen sieben Bitpositionen unterscheidet:
- $$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm},$$
- $$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 1 \oplus 0 \oplus 0 = 0 \hspace{0.05cm},$$
- $$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm}.$$
Richtig sind also die Antworten 2 und 3.
