Die Mathe-Redaktion - 26.06.2019 04:00 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 295 Gäste und 2 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Hamming-Distanz und Parity-Check: Klausur
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Hamming-Distanz und Parity-Check: Klausur
JensSkywalker
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2015
Mitteilungen: 51
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-03-26


Hallo zusammen,

ich habe eine Aufgabe als PDF mit angehangen und dazu folgende Frage.

www.docdroid.net/7ysnj7j/img-20190326-0001.pdf

Aufgabenstellung a, b und c sollte ich bereits korrekt ausgefüllt haben, oder?^^

in d.) heißt es nun, "Was ist die Hamming-Distanz dieses Codes?"
Soll ich nun die Hamming-Distanz von jedem Codewort zu jedem anderen berechnen und dann das Minimum nehmen? Oder wie kann ich "schneller" die Distanz bestimmen?

Danke schonmal im Voraus!

Gruß
Jens



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3105
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-03-26


Zweiter Anlauf :)

also. Die Parity Bits sind so wie ich es sehe richtig berechnet.

Die Frage nach dem Hamming Abstand bezieht sich m.M.n nicht auf die ( hier zufällig ausgewählten ) angegebenen Datenworte, die in die Matrix geschrieben sind, sondern um das Verfahren im allgemeinen, also die 8x8 Bits in der Matrix anzuordnen und mit den Parities zu versehen. Man muss sich also überlegen, wie sich die Änderung eines Bits in den Daten auf die Gesamtzahl der veränderten Bits auswirkt in der Matrix.


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3105
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-03-26


Dazu nochmal die Interpretation ( ich weiss nicht ob es so gemeint ist )

der code bildet 64 datenbits
in codewords ab, die aus den 9x9 bits incl parity bestehen
von diesen codewords gibt es also 2^64 stück ( für jede Belegung der datenbits eins ) und jedes dieser Codewords ist 81 bits lang.

gefragt ist nach dem hamming abstand dieser codewords

und den kann ich mir überlegen, indem ich betrachte, wie viele Bits sich mindestens zwischen zwei Codewords ändern. Zum Beispiel nur eins der Datenbits verändert, welche Parities ändern sich, und was passiert mit dem Bit unten rechts.

Und dann kann ich zur Kontrolle noch ausprobieren, was passiert, wenn ich zwei bits ändere. Diese könnten zB in einer Spalte liegen, sodass sich das spaltenparity nicht ändert, aber dafür....




-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
JensSkywalker
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2015
Mitteilungen: 51
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-03-27


Das Zeilen?
Ich verstehe aber nicht ganz worauf du hinausmöchtest. Wenn ich ein Bit in einem beliebigem Codewort ändere, ändern sich beide Paritybits ebenfalls.
Genauso bei mehr.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3105
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-03-27


Was ich meinte ist:

Du kannst den Hamming Abstand ( der nach dem was ich oben schrieb vier sein sollte ) dadurch belegen, dass du ein Beispiel für zwei Codewords findest, die diesen Abstand haben ( damit kann der Hamming Abstand nicht größer sein ) und zeigst, dass alle anderen Codewords _mindestens_ diesen Abstand haben ( damit kann er auch nicht kleiner sein ). Kriegst du das mit dem was bisher gesagt wurde hin?

Grüsse
Gerhard/Gonz


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
JensSkywalker
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2015
Mitteilungen: 51
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-03-27


Also quasi für alle einzeln ausrechnen?^^



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3105
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-03-27


Nein das sind doch viel zu viele (eben 2^64). Wenn mein Ansatz stimmt und es um den Code geht, der von den ganzen 9x9 matrizen gebildet wird, dann muss man das allgemein überlegen. Durchprobieren wird da nicht gehen :)


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
JensSkywalker
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2015
Mitteilungen: 51
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2019-03-28


Dann habe ich keine Ahnung, wie genau ich das machen soll.
Die Aufgabe gibt nur einen Punkt, da muss es doch einen kleinen Trick geben, auf den ich nicht komme. :O



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3105
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-03-28


Versuchen wir uns dem nochmal zu nähern. Die Daten sind jeweils die 8x8 Bit in den Bytes B0..B7. Diese werden mit den Parities zusammen zu Codewords aus den 9x9=81 Bits zusammengebaut. Man muss sich jetzt also überlegen, in wie vielen Bits sich je zwei dieser Codewords unterscheiden.

Und eigentlich sind wir doch da schon angelangt:

Zwei Codewords unterscheiden sich in mindestens einem Bit ( sonst wären sie ja gleich). Wenn aber ein Bit unterschiedlich ist, dann sind auch die beiden zugehörigen Parity-Bits unterschiedlich ( das Zeilen- und das Spaltenparity ) und es ist außerdem das Bit unten rechts unterschiedlich, da es aus den Spaltenparities berechnet wird. Damit sind in diesem Fall vier Bits verändert.

Zur Kontrolle überprüfen wir nochmal den Fall, dass sich in den Daten zwei Bits geändert haben. Wenn diese in einer Spalte liegen, dann ändert sich das zugehörige Spalten-Parity nicht ( und damit auch das Bit rechts unten nicht), aber es ändern sich zwei Zeilen-Parities, und damit insgesamt auch wieder vier Bit.

Insgesamt ändern sich also eigentlich _immer_ mindestens vier Bit, und da wir auch Fälle gesehen haben, in denen sich nur genau diese vier Bits ändern, ist der Hammning Abstand des Codes vier.

Im Prinzip könntest du das ungefähr so als Lösung hinschreiben. Warum es dafür nur einen Punkt gibt ( während es für die - doch eher mechanische - Berechnung der der Parities je zwei Punkte gibt, ist mir auch unklar. Vielleicht, weil man bei a) und b) jeweils acht Möglichkeiten hat, Fehler zu machen... * seufz

Grüße
Gerhard/Gonz


-----------------
- das alles muss weg. (Meister Eckhart von Hochheim)



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4780
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-03-28


Ich würde es auch so sehen, dass der Code hier aus den $9 \times 9$-Matrizen besteht. Vertauscht man dabei die Zeilen von $D_2$ und $D_7$, was insgesamt ein Fehler an 4 Stellen der Matrix ist, so würde man das auf der Empfangsseite nicht merken, d.h., die Hammingdistanz ist maximal 4.

Um zu zeigen, dass sie wirklich 4 ist, muss man zweierlei zeigen:

1. Einfachfehler werden nicht nur erkannt, sondern können auch korrigiert werden.

2. Zweifachfehler werden niemals mit Einfachfehlern "verwechselt", d.h., sie werden in diesem Sinne als nicht korrigierbare Fehler "erkannt".

[Die Antwort wurde nach Beitrag No.7 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
JensSkywalker
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2015
Mitteilungen: 51
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-03-28


Wieso tauscht man denn ausgerechnet 2 und 7?



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4780
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-03-28


2019-03-28 18:41 - JensSkywalker in Beitrag No. 10 schreibt:
Wieso tauscht man denn ausgerechnet 2 und 7?

Ich versteh die Frage jetzt vielleicht nicht ganz. Ich hab einfach meinen Blick sekundenlang über die Matrix schweifen lassen und da ist mir gleich aufgefallen, dass mehrere Zeilenvektoren mit 0 1 0 ... beginnen, darunter eben dann besonders die oben genannen Zeilenvektoren, welche sich nur an 2(!) Stellen unterscheiden. Hätte ich mir die Zeilenvektoren vom Ende her angesehen, so wäre ich auf ähnliche Weise sofort auf die Vektoren von $D_0$ und $D_7$ gestoßen, d.h., es gibt da durchaus noch andere Möglichkeiten, wenn du das meinst. Aber irgendeine von ihnen genügt ja dann schon um die Minimaldistanz des Codes zunächst einmal mit 4 nach oben zu begrenzen.



  Profil  Quote  Link auf diesen Beitrag Link
JensSkywalker
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2015
Mitteilungen: 51
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-03-28


Genau. Gesucht ist aber doch der geringste Abstand, oder vertue ich mich jetzt so stark?



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4780
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-03-29


2019-03-28 21:54 - JensSkywalker in Beitrag No. 12 schreibt:
Genau. Gesucht ist aber doch der geringste Abstand, oder vertue ich mich jetzt so stark?

Ja, das beweist ja auch nur, dass die Minimaldistanz des Codes höchstens 4 ist, wie ich oben auch geschrieben hatte. Um zu zeigen, dass sie tasächlich 4 ist, muss du die Punkte 1. und 2. in #9 befolgen.

Wenn nach Punkt 1 ein Code Einfachfehler (=Fehler an einer Position der $9\times 9$-Matrix) korrigieren kann, was hier ja hoffentlich(?) trivial ist, muss der Minimalabstand mindestens 3 sein. Wenn ferner nach Punkt 2 Zweifachfehler niemals mit Einfachfehlern "verwechselt" werden, so ist der Minimalabstand dann sogar mindestens 4. Hast du überhaupt schon versucht, diese zwei Punkte zu zeigen?

Edit: Wahrscheinlich ist der von gonz in #8 eingeschlagene Weg aber begrifflich sogar einfacher. M.E. müsste man da für einen vollständigen Beweis aber auch noch die Möglichkeit betrachten, dass für zwei Codewörter im $8\times 8$-Datenbereich genau 3 Bits unterschiedlich sind und dafür zeigen, dass sie sich dann zusätzlich auch noch in mindestens einem Paritätsbit unterscheiden.

Auch wenn alle diese Überlegungen nicht wirklich schwer sind, ist dieser Aufgabenteil mit 1 Punkt im Vergleich zu den anderen jedenfalls krass unterbewertet. Entweder übersehen wir da alle etwas oder - für mich ist dies die weitaus wahrscheinlchere Möglichkeit - der Aufgabensteller hat sich das Ganze etwas zu einfach gemacht.  confused



  Profil  Quote  Link auf diesen Beitrag Link
JensSkywalker hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]