perfekte Codes < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Huhu und ein frohes neues Jahr 2013 :)
Ich hab bald ein Proseminar in LinA wobei es um Codierungstheorie geht. Meine Thema sind "perfekte Codes" Dabei finde ich bei wiki erstmal:
Blockcode C [mm] \subset A^n [/mm] , |A| = q .
Ist es so, dass ein Blockcode ein n- dimensionaler Vektor ist? und dass q die Anzahl der Elemente des Codes? (also binär z.b. 0 und 1 , q = 2)
"Damit ein Code perfekt ist, muss die minimale hammingdistanz zwischen zwei Wörtern eines Code ungerade sein"
hamming- Abstand:
[mm] \Delta(x,y) [/mm] = [mm] \summe_{x_i \not= y_i} [/mm] 1 ; x,y [mm] \in A^n [/mm] . Den Hammingabstand verstehe ich, wenn nur eine Zahl unterschiedlich ist im Vektor, so ist der Abstand am minimalsten.
Dann versteh ich aber nicht den zitierten Satz von mir darüber, das stimmt nicht ganz überein...
Also perfekt wäre dann:
Wenn ich nur 2 Wörter habe z.b. : [mm] \vektor{1 \\ 0} \vektor{0 \\ 0}, [/mm] Abstand = 1
oder [mm] \vektor{1 \\ 0 \\ 1} [/mm] und [mm] \vektor{0 \\ 1 \\ 0}
[/mm]
Abstand = 3
und nicht perfekt z.b. : [mm] \vektor{1 \\ 0 \\ 1 \\ 0} [/mm] und [mm] \vektor{1 \\ 1 \\ 0 \\ 0}
[/mm]
Abstand = 2
Habe ich das soweit richtig verstanden?
Lg,
Eve
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:03 Mi 02.01.2013 | | Autor: | meili |
Hallo Eve,
> Huhu und ein frohes neues Jahr 2013 :)
>
> Ich hab bald ein Proseminar in LinA wobei es um
> Codierungstheorie geht. Meine Thema sind "perfekte Codes"
> Dabei finde ich bei wiki erstmal:
>
> Blockcode C [mm]\subset A^n[/mm] , |A| = q .
>
> Ist es so, dass ein Blockcode ein n- dimensionaler Vektor
> ist?
Ja
> und dass q die Anzahl der Elemente des Codes? (also
> binär z.b. 0 und 1 , q = 2)
q ist die Anzahl der Elemente des verwendeten Alphabets.
Bei deinem Beispiel binär, mit A = {0;1} ist q=2 richtig.
>
> "Damit ein Code perfekt ist, muss die minimale
> hammingdistanz zwischen zwei Wörtern eines Code ungerade
> sein"
>
> hamming- Abstand:
>
> [mm]\Delta(x,y)[/mm] = [mm]\summe_{x_i \not= y_i}[/mm] 1 ; x,y [mm]\in A^n[/mm] . Den
> Hammingabstand verstehe ich, wenn nur eine Zahl
> unterschiedlich ist im Vektor, so ist der Abstand am
> minimalsten.
>
> Dann versteh ich aber nicht den zitierten Satz von mir
> darüber, das stimmt nicht ganz überein...
Zitat: "Ein perfekter Code, oder auch dicht gepackter Code,
bezeichnet in der Codierungstheorie einen Blockcode C [mm] $\subset A^n$, [/mm]
bei dem jedes Wort x [mm] $\in A^n$ [/mm] nur zu genau einem Codewort c [mm] $\in$ [/mm] C
eine minimale Hamming-Distanz hat. ... Um perfekt zu sein muss die
minimale Hammingdistanz zwischen zwei Wörtern eines Codes ungerade
sein, da es sonst für [mm] $c_1,c_2 \in$ [/mm] C : [mm] $d_H(c_1,c_2)$=d [/mm] ein Wort x mit
[mm] $d_H(x,c_1)=\frac{d}{2}=d_H(x,c_2)$ [/mm] gibt, was im Widerspruch zur
Definition eines perfekten Codes steht"
Das Problem liegt vielleicht darin, dass man C [mm]\subset A^n[/mm] betrachtet.
Wenn C eine echte Teilmenge von [mm] $A^n$, [/mm] ungleich [mm] $A^n$, [/mm] ist, kann der
minimale Hammingabstand von zwei verschiedenen Elementen aus C
min [mm] $\{ d_H(c,\overline{c}) | c \in C, \overline{c} \in C, c \not= \overline{c} \} [/mm] auch 3, 4, 5 oder ... sein,
vorausgesetzt n ist groß genug.
>
>
> Also perfekt wäre dann:
>
> Wenn ich nur 2 Wörter habe z.b. : [mm]\vektor{1 \\ 0} \vektor{0 \\ 0},[/mm]
> Abstand = 1
![[ok]](/images/smileys/ok.gif "[ok]")
So könnte man als Beispiel für einen perfekten Code C,
A = {0;1}, [mm] $A^2 [/mm] = [mm] \{ \vektor{0 \\ 0}; \vektor{1 \\ 0}; \vektor{0 \\ 1}; \vektor{1 \\ 1} \}$ [/mm] und C = [mm] $\{ \vektor{1 \\ 0}; \vektor{0 \\ 0} \}$ [/mm]
nehmen.
>
> oder [mm]\vektor{1 \\ 0 \\ 1}[/mm] und [mm]\vektor{0 \\ 1 \\ 0}[/mm]
> Abstand
> = 3
>
> und nicht perfekt z.b. : [mm]\vektor{1 \\ 0 \\ 1 \\ 0}[/mm] und
> [mm]\vektor{1 \\ 1 \\ 0 \\ 0}[/mm]
> Abstand = 2
>
>
> Habe ich das soweit richtig verstanden?
>
>
> Lg,
>
> Eve
Gruß
meili
|
|
|
| |
|
> Hallo Eve,
>
> > Huhu und ein frohes neues Jahr 2013 :)
> >
> > Ich hab bald ein Proseminar in LinA wobei es um
> > Codierungstheorie geht. Meine Thema sind "perfekte Codes"
> > Dabei finde ich bei wiki erstmal:
> >
> > Blockcode C [mm]\subset A^n[/mm] , |A| = q .
> >
> > Ist es so, dass ein Blockcode ein n- dimensionaler Vektor
> > ist?
> Ja
>
> > und dass q die Anzahl der Elemente des Codes? (also
> > binär z.b. 0 und 1 , q = 2)
> q ist die Anzahl der Elemente des verwendeten Alphabets.
> Bei deinem Beispiel binär, mit A = {0;1} ist q=2
> richtig.
>
> >
> > "Damit ein Code perfekt ist, muss die minimale
> > hammingdistanz zwischen zwei Wörtern eines Code ungerade
> > sein"
> >
> > hamming- Abstand:
> >
> > [mm]\Delta(x,y)[/mm] = [mm]\summe_{x_i \not= y_i}[/mm] 1 ; x,y [mm]\in A^n[/mm] . Den
> > Hammingabstand verstehe ich, wenn nur eine Zahl
> > unterschiedlich ist im Vektor, so ist der Abstand am
> > minimalsten.
> >
> > Dann versteh ich aber nicht den zitierten Satz von mir
> > darüber, das stimmt nicht ganz überein...
> Zitat: "Ein perfekter Code, oder auch dicht gepackter
> Code,
> bezeichnet in der Codierungstheorie einen Blockcode C
> [mm]\subset A^n[/mm],
> bei dem jedes Wort x [mm]\in A^n[/mm] nur zu genau einem Codewort c
> [mm]\in[/mm] C
> eine minimale Hamming-Distanz hat. ... Um perfekt zu sein
> muss die
> minimale Hammingdistanz zwischen zwei Wörtern eines Codes
> ungerade
> sein, da es sonst für [mm]c_1,c_2 \in[/mm] C : [mm]d_H(c_1,c_2)[/mm]=d ein
> Wort x mit
> [mm]d_H(x,c_1)=\frac{d}{2}=d_H(x,c_2)[/mm] gibt, was im Widerspruch
> zur
> Definition eines perfekten Codes steht"
>
> Das Problem liegt vielleicht darin, dass man C [mm]\subset A^n[/mm]
> betrachtet.
> Wenn C eine echte Teilmenge von [mm]A^n[/mm], ungleich [mm]A^n[/mm], ist,
> kann der
> minimale Hammingabstand von zwei verschiedenen Elementen
> aus C
> min [mm]$\{ d_H(c,\overline{c}) | c \in C, \overline{c} \in C, c \not= \overline{c} \}[/mm]
> auch 3, 4, 5 oder ... sein,
> vorausgesetzt n ist groß genug.
> >
> >
> > Also perfekt wäre dann:
> >
> > Wenn ich nur 2 Wörter habe z.b. : [mm]\vektor{1 \\ 0} \vektor{0 \\ 0},[/mm]
> > Abstand = 1
>
>
> So könnte man als Beispiel für einen perfekten Code C,
>
> A = {0;1}, [mm]A^2 = \{ \vektor{0 \\ 0}; \vektor{1 \\ 0}; \vektor{0 \\ 1}; \vektor{1 \\ 1} \}[/mm]
> und C = [mm]\{ \vektor{1 \\ 0}; \vektor{0 \\ 0} \}[/mm]
> nehmen.
Also ist, wenn ich mein n ehöhe, die Vektoren jeweils alle möglichen Kombinationen der Elemente q? z.b. Also wäre es bei [mm] A^3
[/mm]
[mm] \vektor{1 \\ 0 \\ 0} [/mm] , [mm] \vektor{0 \\ 0 \\ 0} [/mm] , [mm] \vektor{1 \\ 1 \\ 1}, \vektor{0 \\ 1 \\ 0} [/mm] , [mm] \vektor{0 \\ 0 \\ 1}
[/mm]
, [mm] \vektor{1 \\ 1 \\ 0} [/mm] , [mm] \vektor{0 \\ 1 \\ 1}, \vektor{1 \\ 0 \\ 1} [/mm]
?
Was mich hier nun noch sehr interessiert: Was hat es mit dem [mm] A^n [/mm] auf sich? Was ändert sich für einen Code, desto größer n ist? Welche Auswirkungen hat es?
Und ist ein Blockcode ein "Fehler korrigierender" Code? Bzw der Blockcode dient ja als Decoder, richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:51 Do 03.01.2013 | | Autor: | Infinit |
Hallo Eve,
ja, solch ein Blockcode ist ein fehlerkorrigierender Code, wenigstens aber ein fehlererkennender Code. Da die Gesamtdatenmenge, die man überträgt aus den ursprünglichen Daten und dem Blockcode besteht und beide natürlich übertragen werden müssen, spricht man in der Nachrichtentechnik von einem FEC-Code (FEC=Forward Error Correction).
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:08 Do 03.01.2013 | | Autor: | felixf |
Moin,
> ja, solch ein Blockcode ist ein fehlerkorrigierender Code,
> wenigstens aber ein fehlererkennender Code.
haengt ein wenig davon ab, wie man was definiert 
Wenn man voraussetzt, dass der Hamming-Abstand mindestens 2 ist (ansonsten kann man Fehler i.A. weder erkennen noch korrigieren), ist der triviale Code [mm] $A^n$ [/mm] kein fehlererkennender/fehlerkorrigierender Code, aber immer noch ein Blockcode. (Wenn auch ein trivialer.)
> Da die
> Gesamtdatenmenge, die man überträgt aus den
> ursprünglichen Daten und dem Blockcode besteht
Werden die Daten nicht mit Hilfe des Blockcodes codiert dargestellt und dann uebertragen? (Je nach Codierung sehen die codierten Daten dann aus wie die urspruenglichen + zusaetzliche Informationen.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Sa 05.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:12 Do 03.01.2013 | | Autor: | felixf |
Moin!
> So könnte man als Beispiel für einen perfekten Code C,
>
> A = {0;1}, [mm]A^2 = \{ \vektor{0 \\ 0}; \vektor{1 \\ 0}; \vektor{0 \\ 1}; \vektor{1 \\ 1} \}[/mm]
> und C = [mm]\{ \vektor{1 \\ 0}; \vektor{0 \\ 0} \}[/mm]
> nehmen.
Vorsicht, der zweite Code ist nicht perfekt, da [mm] $\vektor{1 \\ 1}$ [/mm] zu beiden Codewoertern den gleichen Abstand hat. Ueber [mm] $\IF_2$ [/mm] gibt es nur zwei perfekte Codes der Laenge 2: die beiden trivialen Codes.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:40 Do 03.01.2013 | | Autor: | meili |
Hallo,
ist $ [mm] \Delta \left( \vektor{1 \\ 1}, \vektor{1 \\ 0} \right) [/mm] = 1$ und
$ [mm] \Delta \left( \vektor{1 \\ 1}, \vektor{0 \\ 0} \right) [/mm] = 2$ ?
(Hamming-Abstand)
Gruß
meili
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:57 Fr 04.01.2013 | | Autor: | felixf |
Moin!
> ist [mm]\Delta \left( \vektor{1 \\ 1}, \vektor{1 \\ 0} \right) = 1[/mm]
> und
>
> [mm]\Delta \left( \vektor{1 \\ 1}, \vektor{0 \\ 0} \right) = 2[/mm]
> ?
Oh, stimmt, sorry.
Mir faellt da gerade auf, dass es offenbar verschiedene, nicht-aequivalente Definitionen eines perfekten Codes gibt. Einmal steht ![[]](/images/popup.gif) hier, dass ein Code perfekt ist, wenn jedes Element aus dem [mm] $A^n$ [/mm] zu genau einem Codewort minimalen Abstand hat. Diese Eigenschaft wird von deinem Code erfuellt.
Weiter unten auf der Wikipedia-Seite steht "Bei einem perfekten Code sind alle Wörter $x [mm] \in A^n$ [/mm] in einer der Kugeln enthalten (anders ausgedrückt: Die Kugeln überdecken den Raum). Deshalb gilt bei der Hammingschranke für diesen Code dann die Gleichheit." (Das ist die entscheidene Eigenschaft, die ich intuitiv von einem perfektem Code erwarte.) Diese Eigenschaft wird nicht von deinem Code erfuellt: der Minimalabstand des Codes ist 1, und die zwei Kugeln von Radius 1 ueberdecken nur die Haelfte von [mm] $A^n$ [/mm] -- naemlich genau den Code selber. Fuer den Code ist die Hamming-Schranke also nicht erfuellt -- der groesste binaere Code der Laenge 2 mit Minimalabstand 1 ist der triviale Code --, womit er nicht perfekt ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:21 Do 03.01.2013 | | Autor: | Marcel |
Hallo,
nur mal ein Sprachgebrauch:
> hamming- Abstand:
>
> [mm]\Delta(x,y)[/mm] = [mm]\summe_{x_i \not= y_i}[/mm] 1 ; x,y [mm]\in A^n[/mm] . Den
> Hammingabstand verstehe ich, wenn nur eine Zahl
> unterschiedlich ist im Vektor, so ist der Abstand am
> minimalsten.
denk' mal über den Sinn nach. Macht es Sinn, sowas zu benutzen wie:
[mm] $\bullet$ [/mm] minimal, minimaler, am minimalsten
[mm] $\bullet$ [/mm] maximal, maximaler, am maximalsten
[mm] $\bullet$ [/mm] optimal, optimaler, am optimalsten
??
Soweit ich weiß, ist minimal "das kleinstmögliche", minimaler wäre also
noch kleiner als kleinstmöglich??
P.S. Ich weiß, dass das ein bisschen "Klugscheißerei" ist, aber dennoch
sollte man aufpassen, bei wem und wo man sowas sagt bzw. dass man
das dann besser nicht sagt: Manche Leute reiten gerne auf sowas rum. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:10 Do 03.01.2013 | | Autor: | felixf |
Moin!
> Huhu und ein frohes neues Jahr 2013 :)
Danke gleichfalls!
> Blockcode C [mm]\subset A^n[/mm] , |A| = q .
>
> Ist es so, dass ein Blockcode ein n- dimensionaler Vektor
> ist?
Vorsicht, hier musst du auch aufpassen. Ein Blockcode ist eine Menge/Ansammlung von $n$-dimensionalen Vektoren. Jedes Element dieser Menge ist ein Codewort.
LG Felix
|
|
|
| |
|
Entschuldigt ihr habt natürlich Recht was meine Ausdrucksweise angeht..^^
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:01 Fr 04.01.2013 | | Autor: | Marcel |
Hallo,
> Entschuldigt ihr habt natürlich Recht was meine
> Ausdrucksweise angeht..^^
Du brauchst Dich dafür nicht zu entschuldigen. Ich wollte nur drauf
aufmerksam machen, weil ich halt früher auch immer von der optimalsten
Lösung etwa gesprochen habe.
Gruß,
Marcel
|
|
|
| |
|
Mir fällt da noch was wichtiges auf, womit ich nicht ganz einverstanden bin:
Laut Wikipedia Artikel:
"Ein perfekter Code bezeichnet in der Codierungstheorie einen Blockcode.., bei dem jedes Wort nur zu genau einem Codewort eine minimale Hammingdistanz hat"
und
"Da der Code t fehlerkorrigierend ist (t = [mm] \bruch{d-1}{2} [/mm] in der Abrundungsfunktion, d Hammingdistanz von C.) kann ein Wort einem Codewort eindeutig zugeordnet werden, wenn [mm] d_H (x,c_1) \le [/mm] t ist.
Also wenn das gilt, ist der Code perfekt?
Aber in dem Beispiel von oben geht das gar nicht auf, und überhaupt, wie kann diese Gleichung überhaupt funktionieren? Ist ja irgendwie so als hätte ich da
d [mm] \le \bruch{d-1}{2} [/mm] in der Abrundungsfunktion stehe, was nie funktionieren kann ?
Oder überseh ich da was?
lg,
Evelyn
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:16 Fr 04.01.2013 | | Autor: | felixf |
Moin!
> Mir fällt da noch was wichtiges auf, womit ich nicht ganz
> einverstanden bin:
>
> Laut Wikipedia Artikel:
>
>
> "Ein perfekter Code bezeichnet in der Codierungstheorie
> einen Blockcode.., bei dem jedes Wort nur zu genau einem
> Codewort eine minimale Hammingdistanz hat"
Ich denke, diese Definition ist falsch. Sie beschreibt eine Familie von Codes, die zwar die perfekten Codes umfasst, aber eben auch Codes, die nicht perfekt sind -- wie das Beispiel von meili. Ich hab mal in der Wiki-Diskussionsseite darauf hingewiesen.
> und
>
> "Da der Code t fehlerkorrigierend ist (t = [mm]\bruch{d-1}{2}[/mm]
> in der Abrundungsfunktion, d Hammingdistanz von C.) kann
> ein Wort einem Codewort eindeutig zugeordnet werden, wenn
> [mm]d_H (x,c_1) \le[/mm] t ist.
>
> Also wenn das gilt, ist der Code perfekt?
Nein, erstmal nicht. Es muss gelten, dass fuer jedes $x$ gilt [mm] $d_H(x, c_1) \le [/mm] t$ fuer ein passendes [mm] $c_1$ [/mm] (von $x$ abhaengig). Dann ist der Code perfekt.
Besser ist die Definition: der Code heisst perfekt, wenn bei der Hamming-Schranke (oder auch Kugelpackungsschranke) Gleichheit auftritt.
LG Felix
|
|
|
|
