Hammingcode < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 20:14 Sa 06.12.2008 | | Autor: | otto3333 |
| Aufgabe | Es sei n [mm] \in N\setminus\{1\} [/mm] sowie m [mm] =2^n [/mm] - 1 und H eine(n,m)-Matrix über [mm] \IZ_{2}
[/mm]
, deren Spalten paarweise verschieden und ungleich der Nullspalte sind.Die Menge C ={ x [mm] \in \IZ_{2}^m| H.x^t= 0^t [/mm] }
heißt Hammingcode,ihre Elemente heißen Codewörter.
a) Berechenen Sie die Anzahl der Codewörter d.h. |C|
b) Zeigen Sie,dass sich zwei verschiedene Codewörter an mindestens 3 Stellen unterscheiden.
Vielen Dank schon mal für eure Hilfe......... |
keine Ahnung wie ich das machen soll ??? bitte um hilfe
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:23 Sa 06.12.2008 | | Autor: | otto3333 |
wie bearbeite ich hier nochmal meine Aufgabenstellung ????
|
|
|
| |
|
Hallo,
dies ist ein crossposting ohne entsprechenden hinweis.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:57 Sa 06.12.2008 | | Autor: | otto3333 |
okay alles klar aber wie kann ich meine aufgabenstellung nochmal neu bearbeiten ?????
|
|
|
| |
|
> wie bearbeite ich hier nochmal meine Aufgabenstellung ????
Hallo,
Du kannst Deinen eigenen Artikel aufrufen , dann den Button "eigenen Artikel bearbeiten" (o. so ähnlich) klicken.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:41 Sa 06.12.2008 | | Autor: | otto3333 |
okay habe ich jetzt hinbekommen danke nochmal vielleicht haste ja ne idee zu der aufgabe liebe angela ...
|
|
|
| |
|
Hallo Otto,
Lang ist's her, seit ich einmal eine Arbeit über Hamming-
Codes schrieb. Ich denke aber, dass ich trotzdem noch
ein wenig darüber weiss.
Einmal zu Teilaufgabe a) :
Machen wir ein Beispiel: n=3 , dann ist [mm] m=2^3-1=7.
[/mm]
Die Matrix H hat also 3 Zeilen und 7 Spalten. In der
Matrix stehen nur Nullen und Einsen. Die sieben
Spaltenvektoren müssen alle verschieden voneinander
und vom Nullvektor sein. Dann müssen dies alle
von [mm] \vec{0} [/mm] verschiedenen Dreiervektoren über [mm] \IZ_2^3 [/mm] sein,
denn der enthält ja inkl. Nullvektor nur gerade [mm] 2^3=8 [/mm]
Vektoren. H enthält also in irgend einer Permutation
alle Dreiervektoren [mm] \not=\vec{0} [/mm] . Ein mögliches Beispiel wäre:
$\ [mm] H=\pmat{0&1&1&1&0&1&0\\0&1&0&1&1&0&1\\1&0&1&1&0&0&1}$
[/mm]
Codewörter sind Zeilenvektoren [mm] \pmat{x_1&x_2&x_3& ... & x_7} [/mm] der
Länge 7 ebenfalls aus lauter Nullen und Einsen. Sieben-
stellige Zeilenvektoren gibt es natürlich [mm] 2^7=128. [/mm] Damit
ein solcher Vektor aber wirklich ein Codewort darstellt,
muss er drei Gleichungen erfüllen, denn sein Skalarprodukt
mit jedem der 3 Zeilenvektoren von H soll ja Null ergeben.
Nun ist es so, dass jede der Gleichungen die Anzahl der
noch in Frage kommenden Vektoren genau halbiert.
[mm] 2^7=128 [/mm] dreimal fortgesetzt halbiert ergibt [mm] 2^4=16.
[/mm]
So würde ich sagen, dass es in diesem Code genau 16
Codewörter gibt; also [mm] |C|=2^4=16.
[/mm]
Ich habe dies grad mal ausprobiert:
1 ( 0 0 0 0 0 0 0)
2 ( 0 0 0 1 0 1 1)
3 ( 0 0 1 0 1 1 1)
4 ( 0 0 1 1 1 0 0)
5 ( 0 1 0 0 1 1 0)
6 ( 0 1 0 1 1 0 1)
7 ( 0 1 1 0 0 0 1)
8 ( 0 1 1 1 0 1 0)
9 ( 1 0 0 0 1 0 1)
10 ( 1 0 0 1 1 1 0)
11 ( 1 0 1 0 0 1 0)
12 ( 1 0 1 1 0 0 1)
13 ( 1 1 0 0 0 1 1)
14 ( 1 1 0 1 0 0 0)
15 ( 1 1 1 0 1 0 0)
16 ( 1 1 1 1 1 1 1)
Ich denke, dies lässt sich ganz leicht auf den allge-
meinen Fall erweitern !
Jetzt käme noch die Aufgabe b), in der man zeigen soll,
dass die entstehenden Codewörter paarweise eine
"Hamming-Distanz" von mindestens 3 haben.
Gruß Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 10:32 So 07.12.2008 | | Autor: | otto3333 |
vielen Dank für Deine Antwort.......hast Du auch eine Idee zu b ????
|
|
|
| |
|
Hallo Otto,
meinen damaligen Text habe ich nicht greifbar. Dafür
habe ich etwas viel besseres gefunden. Hier der Link
zum
![[]](/images/popup.gif) Original-Paper von R.W.Hamming
aus dem Bell System Technical Journal vom April 1950,
wo genau das Beispiel mit n=3, m=7 mit 4 Daten- und
3 Kontrollbits und 16 Codewörtern auch besprochen wird.
Gruß al-Chw.
|
|
|
| |
|
ja alles klar für n = 3 aber wie zeige ich das allg. für n ????
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Di 09.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Aufgabe | Es sei $\ [mm] n\in \IN\setminus\{1\}$ [/mm] sowie $\ m [mm] =2^n [/mm] -1$ und $\ H$ eine $\ [mm] n\times{m}$ [/mm] - Matrix über [mm] \IZ_{2} [/mm] ,
deren Spalten paarweise verschieden und ungleich der Nullspalte sind.
Die Menge $\ C [mm] =\{ x \in {\IZ_{2}}^m\ |\ H*x^T= 0^T \}$ [/mm]
heißt Hammingcode, ihre Elemente heißen Codewörter.
a) Berechnen Sie die Anzahl der Codewörter d.h. $\ |C|$
b) Zeigen Sie, dass sich zwei verschiedene Codewörter
an mindestens 3 Stellen unterscheiden. |
Zu Aufgabe b):
x und y seien zwei verschiedene Codewörter,
also [mm] x\in{C} [/mm] und [mm] y\in{C} [/mm] und [mm] x\not=y, [/mm] d.h. [mm] x-y=z\not= [/mm] 0 .
Dann ist [mm] H*x^T=0^T [/mm] und [mm] H*y^T=0^T [/mm] und wegen der
Linearität von auch $\ [mm] H*(x-y)^T= H*x^T- H*y^T=0^T$.
[/mm]
Der Differenzvektor $\ z=x-y$ ist also auch ein
Codewort, und zwar wegen [mm] x\not=y [/mm] nicht der Null-
vektor (der ebenfalls ein Codewort ist).
Die Anzahl der Stellen, an welchen sich x und y
unterscheiden, entspricht genau der Anzahl der
Einsen im Differenzvektor z. Zu zeigen bleibt also:
Jedes Codewort [mm] z\in [/mm] C mit [mm] z\not= [/mm] 0 enthält mindestens
drei Einsen. In meiner obigen Antwort kann man
dies im Beispiel mit n=3 aus der Liste der
16 Codewörter ablesen. Gefragt ist aber ein Beweis,
der auch für andere n gilt.
Gruß Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:27 So 07.12.2008 | | Autor: | otto3333 |
und wie zeige ich das z mindestens drei 1 hat ???
|
|
|
| |
|
> und wie zeige ich das z mindestens drei 1 hat ???
Guten Abend Otto,
das kann mit einem Beweis durch Widerspruch gezeigt
werden. Nehmen wir also z.B. einmal an, ein Codewort
[mm] z\in\IC [/mm] hätte nur eine einzige 1, und zwar an der Stelle
[mm] i\in\{1,2,3, ..... ,2^n-1\} [/mm] und sonst lauter Nullen.
Weil [mm] z\in\IC [/mm] , müsste also gelten:
[mm] H*z^T=0^T
[/mm]
Notiert man sich dies ausführlich, erkennt man, dass
daraus folgen würde, dass H an der i-ten Stelle eine
Spalte aus lauter Nullen haben müsste. Da wir aber
wissen, dass H keine Nullspalte enthält, kann dies
nicht sein.
Wie wär's mit einem Codewort z mit genau zwei
Einsen etwa an den Stellen i und j ? Dann hätten wir:
[mm] H*z^T=H_i+H_j =0^T [/mm]
(Summe aus i-tem und j-tem Spaltenvektor von H)
Weil aber in [mm] \IZ_2 [/mm] und auch in [mm] {\IZ_2}^m [/mm] Addition und
Subtraktion dasselbe sind, würde folgen, dass
[mm] H_i-H_j=0^T [/mm] oder [mm] H_i=H_j [/mm] .
Dies würde bedeuten, dass die Kontrollmatrix H
zwei identische Spalten haben müsste. Da wir aber
wissen, dass auch dies nicht der Fall ist, folgt mit
den obigen Überlegungen zusammen, dass jedes
Codewort [mm] z\in \IC [/mm] entweder gar keine oder aber
mindestens drei Einsen hat. Daraus ergibt sich nach
den schon vorher erläuterten Gründen, dass sich
zwei beliebige verschiedene Codewörter eines solchen
"perfekten" Hamming-Codes in mindestens drei Bits
unterscheiden müssen.
Übrigens kann man bei der praktischen Anwendung
dieser Hamming-Codes aus dem Ergebnis des Produktes
[mm] H*z^T [/mm] dann, wenn es nicht den Nullvektor ergibt,
leicht berechnen, an welcher Position der fehlerhaft
übertragenen Bitfolge der Fehler liegen muss (falls
es wirklich nur ein ein-Bit-Fehler war). Mit dieser
Information kann man also ein-Bit-Fehler nicht
nur erkennen, sondern auch korrigieren. Auf solchen
(und anderen) Codes beruhen deshalb sehr viele
Fehlerkorrekturalgorithmen in unseren heutigen
Kommunikationsgeräten vom Handy über CD-Player
über DAB-Radio bis zu Satellitenfernsehen und dem
Datenverkehr mit Vehikeln, die z.B. auf dem Mars
den Boden untersuchen.
Gruß
al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:30 Mo 08.12.2008 | | Autor: | otto3333 |
vielen dank für Deine ausführliche Antwort
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:24 So 07.12.2008 | | Autor: | felixf |
Hallo zusammen
> [...] Damit
> ein solcher Vektor aber wirklich ein Codewort darstellt,
> muss er drei Gleichungen erfüllen, denn sein Skalarprodukt
> mit jedem der 3 Zeilenvektoren von H soll ja Null ergeben.
> Nun ist es so, dass jede der Gleichungen die Anzahl der
> noch in Frage kommenden Vektoren genau halbiert.
> [mm]2^7=128[/mm] dreimal fortgesetzt halbiert ergibt [mm]2^4=16.[/mm]
> So würde ich sagen, dass es in diesem Code genau 16
> Codewörter gibt; also [mm]|C|=2^4=16.[/mm]
Anders gesagt: die Matrix hat Rang 3, womit der Rechtskern (welcher der Code ist) nach der Dimensionsformel die Dimension $m - 3$ hat, also [mm] $2^{m - 3}$ [/mm] Elemente hat.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:32 Mo 08.12.2008 | | Autor: | otto3333 |
danke felix
|
|
|
|
