Hammingcodes - Fehler < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:57 Di 27.08.2013 | | Autor: | AntonK |
Hallo Leute,
ich habe ein paar Probleme mit Hammingcodes. Und zwar verstehe ich das Geschichte mit t-fehlerkorrigierend und Fehler erkennen nicht. Ich fang am besten mal von vorne an, also damit, was mir klar ist.
Ich habe beispielsweise den Raum C=((0000),(1000),(0100),(1100)) mit eben diesen 4 Codewörtern. Meine Generatormatrix ist demnach:
G= [mm] \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{pmatrix}
[/mm]
Also ein [4,2]-Code.
Die Prüfmatrix H muss folgendes Kriterium erfüllen:
[mm] H*G^{t}=0
[/mm]
Meine erste Frage dazu ist jetzt:
Gibt es mehrere Möglichkeiten für H? Denn sowohl [mm] H=\begin{pmatrix}
0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0
\end{pmatrix} [/mm] als auch [mm] H=\begin{pmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix} [/mm] erfüllen das oben genannte Kriterium.
2. Frage:
Der Mindestabstand ist d(C)=1. In unserem Skript steht ein Code ist genau dann t-fehlerkorrigierend wenn d>2t. Also in unserem Fall 1>2t. Das heißt doch dann, das der Code 0-fehlerkorrigierend ist oder?
Danke schonmal im vorraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:16 Mi 28.08.2013 | | Autor: | felixf |
Moin!
> ich habe ein paar Probleme mit Hammingcodes. Und zwar
> verstehe ich das Geschichte mit t-fehlerkorrigierend und
> Fehler erkennen nicht. Ich fang am besten mal von vorne an,
> also damit, was mir klar ist.
>
> Ich habe beispielsweise den Raum
> C=((0000),(1000),(0100),(1100)) mit eben diesen 4
> Codewörtern. Meine Generatormatrix ist demnach:
>
> G= [mm] \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{pmatrix}[/mm]
>
> Also ein [4,2]-Code.
![[ok]](/images/smileys/ok.gif "[ok]")
> Die Prüfmatrix H muss folgendes Kriterium erfüllen:
>
> [mm]H*G^{t}=0[/mm]
>
> Meine erste Frage dazu ist jetzt:
>
> Gibt es mehrere Möglichkeiten für H? Denn sowohl
> [mm]H=\begin{pmatrix}
0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0
\end{pmatrix}[/mm] als auch
> [mm]H=\begin{pmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}[/mm] erfüllen
> das oben genannte Kriterium.
Ja, es gibt viele Moeglichkeiten fuer $H$. Die Spalten von $H$ sind eine Basis eines [mm] $\IF_2$-dimensionalen [/mm] Vektorraums von Dimension $4 - [mm] \rank [/mm] G = 4 - 2 = 2$. Damit kann man nachrechnen, dass es 6 solche Matrizen $H$ gibt (mit zwei Zeilen).
> 2. Frage:
>
> Der Mindestabstand ist d(C)=1. In unserem Skript steht ein
> Code ist genau dann t-fehlerkorrigierend wenn d>2t. Also in
> unserem Fall 1>2t. Das heißt doch dann, das der Code
> 0-fehlerkorrigierend ist oder?
Ja.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:56 Mi 28.08.2013 | | Autor: | AntonK |
Danke dir für deine Antwort, nun habe ich aber ein Problem und zwar haben wir ja gesagt, dass ich dort keine Fehler korrigieren kann.
Nun nehmen wir einmal das fehlerhafte Wort: (1110)
(1110)* [mm] \begin{pmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}^{t}=(10)
[/mm]
Da kann ich doch eindeutig sagen, dass der Fehler an der 3. Stelle liegt also kann ich doch einen Feheler korrigieren oder sehe ich das falsch?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:33 Mi 28.08.2013 | | Autor: | felixf |
Moin!
> Danke dir für deine Antwort, nun habe ich aber ein Problem
> und zwar haben wir ja gesagt, dass ich dort keine Fehler
> korrigieren kann.
>
> Nun nehmen wir einmal das fehlerhafte Wort: (1110)
>
> (1110)* [mm] \begin{pmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}^{t}=(10)[/mm]
>
> Da kann ich doch eindeutig sagen, dass der Fehler an der 3.
> Stelle liegt also kann ich doch einen Feheler korrigieren
> oder sehe ich das falsch?
Woher weisst du denn, dass nur ein Fehler aufgetreten ist?
Und nur, weil der Code 0-fehlerkorrigierend ist, heisst es noch lange nicht, dass man wenn man einen Fehler hat diesen nicht korrigieren kann. Es heisst nur: es gibt mindestens einen Vektor mit Hammingabstand 1 zu einem Codewort, der nicht eindeutig zu diesem dekodiert werden kann.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:32 Mi 28.08.2013 | | Autor: | AntonK |
Was heißt denn dann beispielweise 2- Fehlerkorrigierend?
Wir hatten auch mal eine Aufgabe bei der wir eine [5,2]-Generatormatrix bauen sollten mit Einträgen aus [mm] \IZ/3\IZ, [/mm] die 2-fehlerkorrigierend sein sollte.
Mit meine Ungleichung erhalte ich:
d<2t wobei t=2
=> d<4
Das heißt der Mindestabstand muss 3 oder kleiner sein.
Mein G lautet also:
G= [mm] \begin{pmatrix}
1 & 0 & 1& 0 & 1 \\
1 & 0 & 0& 0 & 1
\end{pmatrix}
[/mm]
Dami erhalte ich die Codewörter:
10101
10101+10101=20202
10101+10101+10101=00000
10001
10001+10001=20002
10001+10001+10101=00100
10101+10101+10001=00200
10001+10101=20102
Die 8 Codewörter haben jeweils den Abstand entweder 3 oder kleiner.
Wäre die Aufgabe zu korrekt gelöst?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:46 Mi 28.08.2013 | | Autor: | felixf |
Moin!
> Was heißt denn dann beispielweise 2- Fehlerkorrigierend?
Edit: Aussage vorher war falsch.
Wenn $v$ ein Vektor ist so dass es ein Codewort $c$ gibt mit $d(v, c) [mm] \le [/mm] 2$, dann gibt es kein weiteres Codewort $c' [mm] \neq [/mm] c$ mit $d(v, c) [mm] \le [/mm] 2$.
Oder anders gesagt: je zwei Baelle mit Hamming-Radius 2 um zwei verschiedene Codewoerter haben kein Element gemeinsam.
> Wir hatten auch mal eine Aufgabe bei der wir eine
> [5,2]-Generatormatrix bauen sollten mit Einträgen aus
> [mm]\IZ/3\IZ,[/mm] die 2-fehlerkorrigierend sein sollte.
>
> Mit meine Ungleichung erhalte ich:
>
> d<2t wobei t=2
Umgekehrt! Du brauchst $d > 2 t$ mit $t = 2$, also
> => d<4
bekommst du $d > 4$ und somit muss $d$ mindestens 5 sein!
> Das heißt der Mindestabstand muss 3 oder kleiner sein.
>
> Mein G lautet also:
>
> G= [mm] \begin{pmatrix}
1 & 0 & 1& 0 & 1 \\
1 & 0 & 0& 0 & 1
\end{pmatrix}[/mm]
Der Mindestabstand $d$ ist hier aber nur 1, da $10101 - 10001 = 00100$ im Code liegt.
> Die 8 Codewörter haben jeweils den Abstand entweder 3 oder
> kleiner.
Sie sollten wenn schon den Abstand 3 oder groesser haben! Bzw. damit der Code 2-fehlerkorrigierend ist, mindestens den Abstand 5 oder groesser.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:06 Mi 28.08.2013 | | Autor: | AntonK |
Ja klar, hab mich beim zweiten Teil vertan, würde das gerne zu erst klären, da ich ja den Mindestabstand von 5 brauche dürfte eigentlich nur diese Matrix funktionieren oder?
$ [mm] \begin{pmatrix} 1 & 1 & 1& 1 & 1 \\ 2 & 2 & 2 & 2 & 2 \end{pmatrix} [/mm] $
Anders geht es ja ansich nicht, wobei jetzt natürlich eine neue Frage im Raum steht. Die Matrix hat ja nun nur noch den Rang 1, weil erste und zweite Zeile abhängig, darf man das trotzdem machen?
Und nun zur ersten Sache, warum muss v=c sein? Wenn die gleich sind, ist doch d(v,c)=0 oder? Sorry wenn ich nerve, aber will das unbedingt bis ins kleinste Detail begreifen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:52 Do 29.08.2013 | | Autor: | felixf |
Moin!
> Ja klar, hab mich beim zweiten Teil vertan, würde das
> gerne zu erst klären, da ich ja den Mindestabstand von 5
> brauche dürfte eigentlich nur diese Matrix funktionieren
> oder?
>
> [mm]\begin{pmatrix} 1 & 1 & 1& 1 & 1 \\ 2 & 2 & 2 & 2 & 2 \end{pmatrix}[/mm]
>
> Anders geht es ja ansich nicht, wobei jetzt natürlich eine
> neue Frage im Raum steht. Die Matrix hat ja nun nur noch
> den Rang 1, weil erste und zweite Zeile abhängig, darf man
> das trotzdem machen?
Diese Matrix erzeugt einen $[5, 1]$-Code. Die Zeilen muessen linear abhaengig sein, damit es ein $[5, 2]$-Code wird.
Apropos: es gibt keinen $[5, 2]$-Code mit Minimalabstand 5.
> Und nun zur ersten Sache, warum muss v=c sein? Wenn die
> gleich sind, ist doch d(v,c)=0 oder? Sorry wenn ich nerve,
> aber will das unbedingt bis ins kleinste Detail begreifen.
Sorry, das war ein Fehler von mir. Ich korrigier das mal.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:31 Fr 30.08.2013 | | Autor: | AntonK |
Nochmals danke, ich hab das jetzt soweit verstanden.
Hätte noch eine Frage zu zyklischen Codes und zwar zu folgendem Beispiel aus unserem Skript:
http://www.myimg.de/?img=zyklischd8430.png (sorry für das Bild)
Es geht um Matrix H. Die erste und zweite Zeile sind mir absolut klar. Das Kontrollpolynom lautet ja [mm] x^4+x^2+x+1, [/mm] wenn ich dieses nun mit x multipliziere erhalte ich die 2. Zeile, auch klar. Wenn ich h jetzt nochmal mit [mm] x^2 [/mm] multipliziere erhalte ich als dritte Zeile [mm] x^6+x^4+x^3+x^2, [/mm] somit müsste doch meiner Meinung nach die letzte Zeile lauten: (1011100).
Oder sehe ich das falsch?
Danke schonmal!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:46 Sa 31.08.2013 | | Autor: | felixf |
Moin,
> Nochmals danke, ich hab das jetzt soweit verstanden.
>
> Hätte noch eine Frage zu zyklischen Codes und zwar zu
> folgendem Beispiel aus unserem Skript:
>
> http://www.myimg.de/?img=zyklischd8430.png (sorry für das
> Bild)
>
> Es geht um Matrix H. Die erste und zweite Zeile sind mir
> absolut klar. Das Kontrollpolynom lautet ja [mm]x^4+x^2+x+1,[/mm]
> wenn ich dieses nun mit x multipliziere erhalte ich die 2.
> Zeile, auch klar. Wenn ich h jetzt nochmal mit [mm]x^2[/mm]
> multipliziere erhalte ich als dritte Zeile [mm]x^6+x^4+x^3+x^2,[/mm]
> somit müsste doch meiner Meinung nach die letzte Zeile
> lauten: (1011100).
Das wuerde ebenfalls eine korrekte Matrix $H$ geben. Wenn du nun die erste Zeile deiner Matrix zur dritten dazuaddierst, bekommst du genau die Matrix aus dem Bild. Daraus kannst du erkennen, dass beide Matrizen zum selben Code gehoeren.
Die Matrix in der Grafik ist (vermutlich) deswegen so veraendert, damit sie eine schoenere Form hat: die $3 [mm] \times [/mm] 3$-Teilmatrix ganz links ist eine Antidiagonalmatrix. Damit uebersetzt sich $H$ in drei Gleichungen der Form [mm] $x_1 [/mm] = ...$, [mm] $x_2 [/mm] = ...$, [mm] $x_3 [/mm] = ...$, wobei $...$ jeweils ein Ausdruck in [mm] $x_4, \dots, x_7$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:41 Sa 31.08.2013 | | Autor: | AntonK |
Verstehe, danke!
Dann noch eine Sache und zwar steht bei uns auch noch folgender Satz:
Sei C [mm] \subset P^{n} [/mm] der Hammingcode mit der Kontrollmatrix H wie oben und [mm] f=a_0+a_1x+...+a_{n-1}x^{n-1} \in [/mm] R
[mm] (a_0,...,a_{n-1}) [/mm] <=> [mm] f(\alpha)=0 [/mm] in K
Ich verstehe nicht ganz, was das bedeuten soll. Also wenn ich für das Kontrollpolynom ein [mm] \alpha [/mm] mit [mm] f(\alpha)=0 [/mm] dann ist die dazugehörige Reihe ein Codewort?
Weil wenn ich nun [mm] x^4+x^2+x+1 [/mm] anschauen, dann würde x=1 die Nullstelle von dem Ding sein, also habe ich ein [mm] \alpha [/mm] gefunden für das es 0 ist, also ist das ein Codewort? Oder wie muss ich das sehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:26 So 01.09.2013 | | Autor: | felixf |
Moin!
> Verstehe, danke!
>
> Dann noch eine Sache und zwar steht bei uns auch noch
> folgender Satz:
>
> Sei C [mm]\subset P^{n}[/mm] der Hammingcode mit der Kontrollmatrix
> H wie oben und [mm]f=a_0+a_1x+...+a_{n-1}x^{n-1} \in[/mm] R
> [mm](a_0,...,a_{n-1})[/mm] <=> [mm]f(\alpha)=0[/mm] in K
Da fehlt irgendetwas.
Meinst du [mm] "$(a_0, \dots, a_{n-1}) \in [/mm] C [mm] \Leftrightarrow f(\alpha) [/mm] = 0$"?
> Ich verstehe nicht ganz, was das bedeuten soll. Also wenn
> ich für das Kontrollpolynom ein [mm]\alpha[/mm] mit [mm]f(\alpha)=0[/mm]
> dann ist die dazugehörige Reihe ein Codewort?
Was ist hier das Kontrollpolynom? Es geht hier doch einfach um irgendein Polynom, das genau dann zu einem Codewort gehoert (ueber die Koeffizientenreihe), wenn es [mm] $\alpha$ [/mm] als Nullstelle hat.
> Weil wenn ich nun [mm]x^4+x^2+x+1[/mm] anschauen, dann würde x=1
> die Nullstelle von dem Ding sein, also habe ich ein [mm]\alpha[/mm]
Das ist eine Nullstelle. Es kann aber durchaus mehr als nur eine geben.
> gefunden für das es 0 ist, also ist das ein Codewort? Oder
> wie muss ich das sehen?
Das macht so keinen Sinn ohne mehr Kontext.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:54 So 01.09.2013 | | Autor: | AntonK |
Sorry, ja ich meinte genau das:
$ [mm] (a_0, \dots, a_{n-1}) \in [/mm] C [mm] \Leftrightarrow f(\alpha) [/mm] = 0 $
Das heißt, wenn ich eine Nullstelle finde, dann gehört das Codewort zu C, richtig?
Dann mal eine ganze blöde Frage:
f(x)=x hat ja offensichtlicherweise die Nullstelle bei x=0, aber (0000010) ist doch kein Codewort oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:47 So 01.09.2013 | | Autor: | felixf |
Moin!
> Sorry, ja ich meinte genau das:
>
> [mm](a_0, \dots, a_{n-1}) \in C \Leftrightarrow f(\alpha) = 0[/mm]
>
> Das heißt, wenn ich eine Nullstelle finde, dann gehört
> das Codewort zu C, richtig?
Nein: das [mm] $\alpha$ [/mm] ist fest gewaehlt und haengt von $C$ ab. Zu $C$ gehoeren also genau die Polynome (Codewoerter), die in diesem festen [mm] $\alpha$ [/mm] eine Nullstelle haben.
> Dann mal eine ganze blöde Frage:
>
> f(x)=x hat ja offensichtlicherweise die Nullstelle bei x=0,
> aber (0000010) ist doch kein Codewort oder?
[mm] $\alpha [/mm] = 0$ ist nicht zulaessig. Es muss [mm] $\alpha^n [/mm] = 1$ gelten, und fuer [mm] $\alpha [/mm] = 0$ gilt das nicht.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:40 Mo 02.09.2013 | | Autor: | AntonK |
Vielen Dank für die Antworten, das hat mir einiges erleichtert!
|
|
|
|
