Antwort mit KI erzeugt
Erzeuger- und Prüfmatrix eines \([15,11,3]\)-Hamming-Codes
Der \([15,11,3]\)-Hamming-Code hat die Parametern \( [n,k,d]=[15,11,3] \). Das bedeutet:
- \( n \) ist die Gesamtlänge des Codes (15 Bits),
- \( k \) ist die Länge der Datenbits (11 Bits),
- \( d \) ist die minimale Hamming-Distanz (3).
Schritt 1: Erzeugermatrix \( E \) aufstellen
Die Erzeugermatrix \( E \) hat die Form
\( E = \left(\mathbb{I}_{k} \mid A\right) \)
wobei \(\mathbb{I}_{k}\) eine \( k \times k \)-Einheitsmatrix und \(A\) eine \( k \times (n-k) \)-Matrix mit den Paritätsprüfbits ist. Für den Hamming-Code müssen wir also \( A \) bestimmen.
Für den \([15,11,3]\)-Hamming-Code sieht das folgendermaßen aus:
\( \mathbb{I}_{11} = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix} \)
Die Matrix \( A \) besteht aus den Paritätsprüfbits. Für den Hamming-Code sind die Spalten von \( A \) die Binärdarstellungen der Zahlen 1 bis 4 (weil es 4 Paritätsbits gibt), allerdings transponiert.
Daraus ergibt sich die Erzeugermatrix \( E \):
\( E = \left[
\begin{array}{ccccccccccccccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\
\end{array}
\right] \)
Schritt 2: Prüfmatrix \(P\) aufstellen
Die Prüfmatrix \(P\) hat die Form
\( P = \left(-A^{T} \mid \mathbb{I}_{n-k}\right) \)
\( A^{T} \) ist die Transponierte der Matrix \(A\). Wir können sofort sehen, dass \( P \) sich dann wie folgt ergibt:
\( P = \left[
\begin{array}{ccccccccccccccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
\end{array}
\right] \)
Schritt 3: Vektor kodieren
Der zu kodierende Vektor ist \( (1,1,0,0,1,0,1,0,1,1,1) \).
In Matrixform ist das:
\( \left[
\begin{array}{c}
1 \\
1 \\
0 \\
0 \\
1 \\
0 \\
1 \\
0 \\
1 \\
1 \\
1 \\
\end{array}
\right] \)
Der kodierte Vektor \( c \) wird durch die Multiplikation mit der Erzeugermatrix \( E \) berechnet:
\( c = d \cdot E \)
\( dE = \left[
\begin{array}{c c c c c c c c c c c c c c c}
1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & | & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & | & 1 & 1 & 1 \\
\end{array}
\right]
\)
Das Ergebnis des kodierten Vektors ist:
\( c = \left[ 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0 \right] \)
Schritt 4: Fehler einführen und Syndrom berechnen
Ändern wir jetzt ein Bit im kodierten Vektor, beispielweise das erste Bit von 1 zu 0:
\( c' = \left[ 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0 \right] \)
Das Syndrom \(\mathbf{s}\) wird durch die Multiplikation des geänderten Vektors \( c' \) mit der Prüfmatrix \( P \) berechnet:
\( \mathbf{s} = c' \cdot P \)
Das Ergebnis ist:
\( \mathbf{s} = \left[ 1000 \right] \)
Die Spalte \( 1000 \) im P-Matrix entspricht der korrigierten Position (erste bit)
Damit bestätigen wir korrekt, dass das eingefügte Fehlervektor und unkodierten Vektor den Hamming Code korrekt kodiert und überprüft.
