Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Aufgabensammlung: Linearer Code/Decodierung zu

Aufgabe 281: Linearer Code, Hamming-Code

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Mit Hilfe der Zuordnung von

[Space] A B C D
$ \mbox{$(0,0,0,0)$}$ $ \mbox{$(0,0,0,1)$}$ $ \mbox{$(0,0,1,0)$}$ $ \mbox{$(0,0,1,1)$}$ $ \mbox{$(0,1,0,0)$}$

wird ein Text buchstabenweise durch die Funktion $ \mbox{$c:\mathbb{F}_2^4\to\mathbb{F}_2^7$}$ mit einem Code der Länge $ \mbox{$7$}$ und Generatormatrix

$ \mbox{$\displaystyle G=\begin{pmatrix}1&0&0&0&0&1&1\\ 0&1&0&0&1&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&1&1 \end{pmatrix}$}$
vermöge $ \mbox{$c(x) = xG$}$ codiert, d.h. die ersten vier Bits enthalten den Buchstaben, die folgenden drei sind Prüfbits.

Erstelle eine Prüfmatrix. Handelt es sich um einen Hamming-Code?

Decodiere den nach einer Übermittlung empfangenen Text $ \mbox{$(0, 0, 0, 0, 0, 1, 1)$}$, $ \mbox{$(1, 1, 0, 1, 0, 0, 0)$}$, $ \mbox{$(0, 0, 1, 0, 0, 0, 0)$}$, $ \mbox{$(1, 1, 1, 1, 1, 1, 1)$}$, $ \mbox{$(1, 1, 1, 1, 0, 0, 0)$}$, $ \mbox{$(1, 1, 0, 0, 1, 1, 0)$}$, $ \mbox{$(1, 0, 0, 1, 1, 0, 0)$}$, $ \mbox{$(1, 1, 0, 1, 0, 0, 0)$}$, $ \mbox{$(0, 1, 0, 1, 1, 1, 1)$}$.

Mit Hilfe der Prüfmatrix

$ \mbox{$\displaystyle H=\begin{pmatrix}0&1&1\\ 1&0&1\\ 1&1&0\\ 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&1\end{pmatrix}, $}$
die zeigt, daß es sich um einen Hamming Code handelt, folgt durch Rechnung folgende Tabelle.
empfangenes Wort Syndrom decodiertes Wort Buchstabe
$ \mbox{$(0, 0, 0, 0, 0, 1, 1)$}$ $ \mbox{$(0,1,1)$}$ $ \mbox{$(1, 0, 0, 0, 0, 1, 1)$}$ H
$ \mbox{$(1, 1, 0, 1, 0, 0, 0)$}$ $ \mbox{$(0,0,1)$}$ $ \mbox{$(1, 1, 0, 1, 0, 0, 1)$}$ M
$ \mbox{$(0, 0, 1, 0, 0, 0, 0)$}$ $ \mbox{$(1,1,0)$}$ $ \mbox{$(0, 0, 0, 0, 0, 0, 0)$}$ [ ]
$ \mbox{$(1, 1, 1, 1, 1, 1, 1)$}$ $ \mbox{$(0,0,0)$}$ $ \mbox{$(1, 1, 1, 1, 1, 1, 1)$}$ O
$ \mbox{$(1, 1, 1, 1, 0, 0, 0)$}$ $ \mbox{$(1,1,1)$}$ $ \mbox{$(1, 1, 1, 0, 0, 0, 0)$}$ N
$ \mbox{$(1, 1, 0, 0, 1, 1, 0)$}$ $ \mbox{$(0,0,0)$}$ $ \mbox{$(1, 1, 0, 0, 1, 1, 0)$}$ L
$ \mbox{$(1, 0, 0, 1, 1, 0, 0)$}$ $ \mbox{$(0,0,0)$}$ $ \mbox{$(1, 0, 0, 1, 1, 0, 0)$}$ I
$ \mbox{$(1, 1, 0, 1, 0, 0, 0)$}$ $ \mbox{$(0,0,1)$}$ $ \mbox{$(1, 1, 0, 1, 0, 0, 1)$}$ M
$ \mbox{$(0, 1, 0, 1, 1, 1, 1)$}$ $ \mbox{$(1,0,1)$}$ $ \mbox{$(0, 0, 0, 1, 1, 1, 1)$}$ A

Es ergibt sich ,,HM ONLIMA``. Beim vorletzten Buchstaben sind bei der Übertragung zwei Bits umgekippt; der MDD eines binären Hamming Codes kann dies jedoch nicht erkennen und hat stattdessen eine Korrektur zum ,,falschen`` Codewort durchgeführt. Beim letzen Buchstaben haben zwei falsch übertragene Prüfbits die ursprünglich richtigen ersten vier Informationsbits verfälscht.

(Autoren: Künzer/Meister/Nebe)
[Zurück zur Aufgabe]
  automatisch erstellt am 7.  6. 2005