Hamming-Distanz < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:10 Sa 21.05.2005 | | Autor: | Reaper |
Hallo...die Überschrift sagt eigentlich alles: Was ist eine Hamming-Distanz. Mir ist der Begriff nur in Bezug auf Codewörter bekannt--sprich Hamming Code.....hab im Skript nachgeschaut und find den Begriff einfach nicht....
Aufgabe lautet: Ist die Hamming Distanz auf [mm] \IZ_{2}^{n} [/mm] eine Metrik?
Also Kapitel wäre eigentlcih Skalarprodukte und nicht Codewörter, deshalb zweifle ich ob die Hamming Distanz mit dem Code in Verbindung gebracht werden kann.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:27 Sa 21.05.2005 | | Autor: | Hanno |
Hallo Hannes.
Seien [mm] $a,b\in\IZ_2^n$, [/mm] so ist der Hamming-Abstand $d(a,b)$ als [mm] $|\{i|a_i\neq b_i, 1\leq i\leq n\}|$ [/mm] definiert.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:39 Sa 21.05.2005 | | Autor: | Micha |
Hallo Reaper!
> Hallo...die Überschrift sagt eigentlich alles: Was ist eine
> Hamming-Distanz. Mir ist der Begriff nur in Bezug auf
> Codewörter bekannt--sprich Hamming Code.....hab im Skript
> nachgeschaut und find den Begriff einfach nicht....
> Aufgabe lautet: Ist die Hamming Distanz auf [mm]\IZ_{2}^{n}[/mm]
> eine Metrik?
Ok also die Definition haben wir ja schon von Hanno. Wenn wir $a,b [mm] \in \IZ_{2}^{n}$ [/mm] haben, dann ist
[mm] $d_H [/mm] (a,b) = [mm] #\{ i | a_i \ne b_i , 1\le i \le n\} [/mm] $
Nun müssen wir eben die Metrikeigenschaften zeigen, also:
(D1) $d (a,b) [mm] \ge [/mm] 0 [mm] \forall [/mm] a,b [mm] \in \IZ_{2}^{n} [/mm] $ und $d (a,b) = 0 [mm] \gdw [/mm] a=b$
Ok das ist klar weil die Kardinalität einer Menge immer positiv ist. und ist
[mm] $d_H [/mm] (a,b) = 0 [mm] \gdw a_i [/mm] = [mm] b_i \forall [/mm] i [mm] \in [/mm] [1,n] [mm] \gdw [/mm] a=b$
(D2) $d (a,b) = d (b,a) $
Nagut das folgt aus der Definition:
[mm] $d_H [/mm] (a,b) = [mm] #\{ i | a_i \ne b_i , 1\le i \le n\} [/mm] = [mm] #\{ i | b_i \ne a_i , 1\le i \le n\} [/mm] = [mm] d_H [/mm] (b,a)$
(D3) $d (x,z) [mm] \le [/mm] d(x,y) + d (y,z)$
Ok hier ist es schon etwas kniffliger. Vielleicht kannst du ha mal einen Versuch hier rein schreiben!
Gruß Micha 
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:52 Sa 21.05.2005 | | Autor: | Reaper |
Hallo
Bezüglich der Hamming Distanz:
sei a,b [mm] \in \IZ^{3}
[/mm]
a = (1,3,5)
b=(2,3,5)
Dann ist die Hammingdistanz = 1 oder?
------
$ d (x,z) [mm] \le [/mm] d(x,y) + d (y,z) $ Dreiecksungleichung
d(x,z) = |{i| [mm] x_{i} [/mm] != [mm] z_{i} [/mm] , 1 <= i <= n}| = [mm] |{i_{x,z}}|
[/mm]
d(x,y) = [mm] |{i_{x,y}}|
[/mm]
d(x,z) = [mm] |{i_{y,z}}|
[/mm]
Ist jetzt [mm] |{i_{x,z}}| [/mm] nicht [mm] |x_{i} [/mm] - [mm] z_{i} [/mm] ohne {0}|?
Denn dann [mm] wäre:|x_{i} [/mm] - [mm] z_{i} [/mm] ohne {0}| = [mm] |x_{i}- y_{i} [/mm] + [mm] y_{i} [/mm] - [mm] z_{i} [/mm] ohne {0}|
und daraus wäre erkenntlich dass d(x,z) kleiner gleich d(x,y) + d (y,z) ist oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:46 Sa 21.05.2005 | | Autor: | Micha |
Hallo!
> Hallo
> Bezüglich der Hamming Distanz:
> sei a,b [mm]\in \IZ^{3}[/mm]
>
> a = (1,3,5)
> b=(2,3,5)
>
> Dann ist die Hammingdistanz = 1 oder?
![[ok]](/images/smileys/ok.gif "[ok]") Das ist richtig.
> ------
>
> [mm]d (x,z) \le d(x,y) + d (y,z)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Dreiecksungleichung
>
> d(x,z) = |{i| [mm]x_{i}[/mm] != [mm]z_{i}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
, 1 <= i <= n}| = [mm]|{i_{x,z}}|[/mm]
> d(x,y) = [mm]|{i_{x,y}}|[/mm]
> d(x,z) = [mm]|{i_{y,z}}|[/mm]
>
> Ist jetzt [mm]|{i_{x,z}}|[/mm] nicht [mm]|x_{i}[/mm] - [mm]z_{i}[/mm] ohne {0}|?
> Denn dann [mm]wäre:|x_{i}[/mm] - [mm]z_{i}[/mm] ohne {0}| = [mm]|x_{i}- y_{i}[/mm] +
> [mm]y_{i}[/mm] - [mm]z_{i}[/mm] ohne {0}|
> und daraus wäre erkenntlich dass d(x,z) kleiner gleich
> d(x,y) + d (y,z) ist oder?
>
Nein die | | - Striche die Hanno verwendet hat, sind keine Beträge, sondern sollen die Kardinalität charakterisieren, also die Anzwahl der Elemente in der Menge.
Angenommen wir haben
[mm] $d_H [/mm] (x,z) = k$ und sei o.E. für $ i [mm] \in [/mm] [1,k] : [mm] x_i \ne z_i$
[/mm]
Wir wissen, dass [mm] $(x_i \ne y_i) \vee (y_i \ne z_i)$ [/mm] für alle $ i [mm] \in [/mm] [1,k]$
Insbsondere können beide Teile ungleich sein (z.B. [mm] $x_i=0$, $y_i [/mm] = 1$ , [mm] $z_i=2$). [/mm] Eine Seite muss aber dann mindestens erfüllt sein.
Für alle $i [mm] \in [/mm] [k+1,n]$ gilt dann allerdings [mm] $x_i [/mm] = [mm] y_i [/mm] = [mm] z_i$ [/mm] oder $ [mm] x_i [/mm] = [mm] z_i \ne y_i$
[/mm]
Der zweite Fall macht dann unsere Ungleichung nur noch größer.
Damit ergibt sich dann die Ungleichung.
Gruß Micha
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:10 Sa 21.05.2005 | | Autor: | Reaper |
Hallo
Also ich kapier da leider einiges nicht was du da sagst.
Du nimmst an d(x,z) = k
k ist die Anzahl der Stellen wo sich in 2xn Matrix die Koeffizienten beider
Matrizen nicht gleichen.
Warum wissen wir dass $ [mm] (x_i \ne y_i) \vee (y_i \ne z_i) [/mm] $ für alle $ i [mm] \in [/mm] [1,k] $?
Wegen der Transitivität?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:13 Sa 21.05.2005 | | Autor: | Micha |
Hallo!
> Hallo
> Also ich kapier da leider einiges nicht was du da sagst.
> Du nimmst an d(x,z) = k
> k ist die Anzahl der Stellen wo sich in 2xn Matrix die
> Koeffizienten beider
> Matrizen nicht gleichen.
Nein nein... [mm] $\IZ^n_2$ [/mm] heißt nicht, dass wir eine 2xn-Matrix haben, sondern wir nehmen alle Zahlen [mm] $\IZ$ [/mm] mod 2, ein Körper bestehend aus den Elementen [mm] $\{0,1\}$, [/mm] als Vektor mit n Einträgen genommen!
>
> Warum wissen wir dass [mm](x_i \ne y_i) \vee (y_i \ne z_i)[/mm] für
> alle [mm]i \in [1,k] [/mm]?
> Wegen der Transitivität?
Nun wir wissen aus unserer Konstruktion, als wir alle Fehlstellen von dem Paar (x,z) nach vorn ordneten als die ersten k Stellen.
Dann muss auf der anderen Seite der Ungleichung an der gleichen Stelle i entweder bei (x,y) eine Fehlstelle sein oder bei (y,z).
Irgendwo muss sich ja die Fehlstelle verstecken, denn sonst wäre an der Stelle [mm] $x_i [/mm] = [mm] y_i [/mm] = [mm] z_i$ [/mm] das ist dann die Transitivität der Gleichheit, wenn du die meinstest.
Gruß Micha
|
|
|
|
