Syndrom Decodierung (Codierungstheorie)

28.02.2011, 19:38

Corny

Syndrom Decodierung (Codierungstheorie)

Meine Frage:
Hey.
Ich habe eine Verständnisfrage zur Syndromdecodierung.

Der Algorithmus zur Syndrom Decoddierung lautet:

Die Anwendung der Decodierung ist, dass wenn man ein Codewort c versendet und weniger als t-fehler auftreten, kann man das verfälscht ankommende codewort x wieder auf das orginal abgeschickte codewort c bringen.

Das geschieht so.

1) Man erhält ein Codewort x
2) Man berechne x *H^T , multipliziert also das empfangene Codewort mit der Transponierten Kontrollmatrix
3) Man bestimme den Anführer der Nebenklasse v mit x*H^T=v*H^T
4) Man berechne c=x-v
6) Das gesuchte Codewort ist t, wenn weniger als t Fehler aufgetreten sind.

Meine Ideen:
Mein Problem, ist dass mir überhaupt nicht in den Kopf will, warum dieser Algorithmus funktioniert, besonders warum man so das gesendete Codewort wieder aus x rekonstruieren kann.

Kann mir jemand ausführlich und anschaulich erklären wieso der Algorithmus funktioniert und was es damit auf sich hat.

Corny

28.02.2011, 20:25

lgrizu

Auf diesen Beitrag antworten »

RE: Syndrom Decodierung (Codierungstheorie)
Nehmen wir doch einfach mal einen [7,4] Hamming Code, dieser ist 1- Fehlerkorrigierend, man kann sich das ganze veranschaulichen, indem man sich überlegt, dass die Codewörter einen gewissen Abstand voneinander haben, dieser ist beim Hamming-Code 3, legen wir um jedes Codewort eine Kugel mit dem Radius 1, dann kann jedes ankommende Wort, dass auf dem Rand der Kugel liegt genau einem Codewort des Codes zugeordnet werden, der Abstand der Codewörter muss drei Betragen, betrüge er nur 2, so wüsste der Code nicht, welchem Wort er ein auf dem Rand der Kugel liegendes Wort zuordnen würde.

Hier mal eine Skizze:
[attach]18368[/attach]

Die erste Zeichnung zeigt 2 Codewörter x und y, die Codewörter Z1 und Z2, die jeweils um den Betrag von 1 von einem der Codewörter entfernt liegen können eindeutig dem Wort x oder y zugeordnet werden.
Hat ein Wort jedoch zwei Fehler, so wird es einem anderen Codewort zugeordnet, denn es liegt dann auf dem Rand einer anderen Kugel, wir zum Beispiel das Wort x codiert und Z2 empfangen, so wird es dem Wort y zugeordnet werden, es wird also kein Fehler erkannt.

In der zweiten Zeichnung haben die Codewörter nur einen Abstand von 2, das ankommende Wort Z kann zwar als fehlerhaft erkannt werden, jedoch nicht korrigiert, da es keinem der Wörter x und y eindeutig zugeornet werden kann.

So weit zur Visualisierung.

Nun der Beweis, dass der Hamming-Code 1-perfekt ist (der Beweis wird über die Existenz und die Eigenschaften der Hamming-Norm geführt):

Wir behaupten zunächst: Die minimale Hamming-Norm eines Codewortes sein ungleich 0, was gleichbedeutend damit ist, das der minimale Abstand zweier Codewörter zueinander gleich 3 ist.

Nun hat der Code eine Erzeugermatrix der Form $\begin{eqnarray*} G=(E_{n-r}|P) \end{eqnarray*}$ , wobei die Zeilen von P paarweise linear unabhängig sind und jede Zeile Hamming Norm mindestens 2 hat, wäre das nicht der Fall, so hätte die Kontrollmatrix $\begin{eqnarray*} H=(-P^t|E_r) \end{eqnarray*}$ keine paarweise linear unabhängige Spalten.
Wegen der Maximalität von n existieren nun in P auch Zeilen der Hamming-Norm 2, was bedeutet, dass in G Zeilen der Hamming-Norm 3 existieren.
Die gesuchte minimale Norm ist also kleiner oder gleich 3.
Nun hat jede Zeile von G mindestens Hamming-Norm 3, eine nichttriviale Linearkombination von 2 Zeilen hat also ebenfalls (wegen der paarweise linearen Unabhängigkeit der Zeilen von P) mindestens Hamming-Norm 3, für Linearkombinationen von mehr als zwei Zeilen gilt dies erst recht.
Wir schauen uns nun die Bälle vom Radius 1 um die Elemente des Codes an: $\begin{eqnarray*} B_1^n(x)= \left\{y \in \mathbb Z_q^n | d_H(x,y) \leq 1\right\} \end{eqnarray*}$ .

Diese sind disjunkt und jede dieser Kugeln enthält genau $\begin{eqnarray*} n(q-1)+1=q^r \end{eqnarray*}$ Elemente, insgesamt enthalten also alle diese Kugeln $\begin{eqnarray*} q^r \cdot q^{n-r}=q^n \end{eqnarray*}$ Elemente und schöpfen somit den gesamten $\begin{eqnarray*} \mathbb Z_q^n \end{eqnarray*}$ aus.

Bei dem [7,4] Hamming Code ist q=2, da es sich um einen Binären Code handelt;.

28.02.2011, 21:00

Corny

Auf diesen Beitrag antworten »

hey.
Danekschön, soweit hab ichs jetzt verstanden. smile

Womit ich noch mein Problem habe, ist der Zusammenhang zwischen Syndrom und Anführer einer Nebebklasse und was Nebenklassen überhaupt sind.
Sind die Nebenklassen veranschaulicht die Kreise?
Wenn ich zwei beliebige Vektoren aus einem Kreis nehme, haben die dann das gleiche Syndrom?

Dann würde das Prinzip der Decodierung darauf beruhen, dass ich weiß, dass mein verfälschtes Codewort x (sind weniger als t-Fehler aufgetreten) im dem Kreis um c (den richtigen Codewort liegt).

Wie kommt man jetzt zu dem Schluss, dass man von x genau den Anführer der Nebenklasse in der x liegt abziehen muss?

Corny

28.02.2011, 21:32

lgrizu

Auf diesen Beitrag antworten »

Gehen wir die Vorgehensweise doch einmal mit dem [7,4] Hamming Code durch.

Dieser hat die Generatormatrix $\begin{eqnarray*} G=\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&1&1&1\\0&0&0&1&0&1&1 \end{pmatrix} \end{eqnarray*}$

Wir verschlüsseln das Codewort (0,1,1,0), es wird also das Kanalcodewort $\begin{eqnarray*} \begin{pmatrix}0\\1\\1\\0\\0\\1\\0\end{pmatrix} \end{eqnarray*}$ gesendet.

Nun die Entschlüssselung (Wir gehen einmal davon aus, dass das Wort $\begin{eqnarray*} x=\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix} \end{eqnarray*}$ empfangen wird.

Die Kontrollmatrix ist:

$\begin{eqnarray*} H=\begin{pmatrix}1&1&1&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix} \end{eqnarray*}$ , wir kontrollieren das Kanalcodewort:

$\begin{eqnarray*} Hx=\begin{pmatrix}0\\0\\1\end{pmatrix} \end{eqnarray*}$ , wir wissen also, dass ein Fehler aufgetreten ist.

Nun ist $\begin{eqnarray*} \begin{pmatrix}0\\0\\1\end{pmatrix}=He_i \end{eqnarray*}$ , wobei e_i der i-te Einheitsvektor ist, dies ist der Nebenklassenführer, in unserem Fall ist schnell zu überprüfen, dass i=7 ist.

Wir rechnen also noch $\begin{eqnarray*} x-e_i \end{eqnarray*}$ um das gesendete Wort zu erhalten.

Veranschaulicht sind die Nebenklassenführer also die Vektoren, die, wenn man ein (Kanal)Codewort mit ihnen addiert innerhalb dieser Bälle bleibt, also alle möglichen Vektoren, die zu einem Kanalcodewort addiert innerhalb oder auf dem Rand der Bälle liegen.

Welche Vektoren zugelassen werden ist vom Code abhängig, beim Hamming code sind es nur die Einheitsvektoren, es existiert also ein Einheitsvektor der die Gleichung $\begin{eqnarray*} Hx=He_i \end{eqnarray*}$ erfüllt.

Der Betrag dieser Vektoren darf natürlich nicht größer sein, als der Radius der Bälle.

Nach 5 Edits endlich fertg, hoffe ich.

28.02.2011, 22:05

Corny

Auf diesen Beitrag antworten »

Zitat:

Nun ist $\begin{eqnarray*} \begin{pmatrix}0\\0\\1\end{pmatrix}=He_i \end{eqnarray*}$ , wobei e_i der i-te Einheitsvektor ist, dies ist der Nebenklassenführer, in unserem Fall ist schnell zu überprüfen, dass i=7 ist. Wir rechnen also noch $\begin{eqnarray*} x-e_i \end{eqnarray*}$ um das gesendete Wort zu erhalten.

Genau die Zeile ist es, die mir die Probleme bereitet hat, da ich nicht verstanden hab, warum c=x-e_i.

Jetzt glaub ich hab ich verstanden wieso. Ich hoffe mal es stimmt.

Da c und x in der gleichen Nebenklasse liegen, haben sie das gleiche Syndrom.
Es gilt also x*H^T=(c+e_i)*H^T daraus folgt x*H^T=c*H^T+e_i*H^T mit c*H^T =0 gilt weiterhin x*H^T=e_i*H^T also (x-e_i)*H^T=0 und daraus folgt dass c =x-e_i ist.

Kann man das so machen?

Corny

28.02.2011, 22:15

lgrizu

Auf diesen Beitrag antworten »

Jap, kann man so machen.