Hamming-Code < Sonstige < Schule < Informatik < Vorhilfe
|
| Aufgabe | Decodieren Sie folgenden Code:
010101000010000011001001000001011010010100001100100000000000000011010000000100000000110101000100000110010 |
Hallo!
Habe erst gedacht es würde sich um einen normalen Binärcode handeln. Ich bin jetzt aber sicher das es sich um einen Hamming-Code handelt. Leider haben wir sowas nie gelernt. Habe ein bißchen recherchiert, aber ich finde keinen richtigen Ansatz!Woher weiß ich wieviele Datenbits bzw Paritybits ich wählen muß? Ich habe immerhin 105 Zeichen und soweit ich das verstanden habe gibt es nur eine Gesamtlänge des Codeworts von 57 oder das nächst höhere 120! Das passt ja beides nicht. Und wie sieht das ergebnis im Endeffekt aus: ist das dann ein binärcode den ich wiederrum übersetzen muß oder kommt da text raus?
Fragen über Fragen, hatte gehofft im Netz ein gutes Tool für sowas zu finden, da ich aber die Bit-zahl nicht weiß komm ich gerade nicht weiter!
Gruß
superkermit
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:25 Do 12.03.2009 | | Autor: | Karl_Pech |
Hallo superkermit,
> Leider haben wir sowas nie gelernt.
Welche Code-Arten habt ihr bisher durchgenommen? Gab es für die Aufgabe irgendwelche Tipps? Informationen dazu würde die Anzahl der in Frage kommenden Codes einschränken.
Viele Grüße
Karl
|
|
|
| |
|
Hi!
Wie gesagt, es wird wohl auf den Hamming Code hinauslaufen bzw es muß damit irgendwas zu tun haben. Ansonsten hab ich keine Tipps und bin bisher auch noch keinen Schritt weitergekommen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:17 Do 12.03.2009 | | Autor: | Gilga |
Hammingcodelänge ist [mm] 2^n-1
[/mm]
Ich denke dir fehlt ein Teil der Angabe oder etwas wurde in der Übung dazu gesagt. Einfach 105 Bits interpretieren geht nicht
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:28 Fr 13.03.2009 | | Autor: | bazzzty |
> Decodieren Sie folgenden Code:
> 010101000010000011001001000001011010010100001100100000000000000011010000000100000000110101000100000110010
> Hallo!
> Habe erst gedacht es würde sich um einen normalen
> Binärcode handeln. Ich bin jetzt aber sicher das es sich um
> einen Hamming-Code handelt.
Was macht dich sicher?
Leider haben wir sowas nie
> gelernt. Habe ein bißchen recherchiert, aber ich finde
> keinen richtigen Ansatz!Woher weiß ich wieviele Datenbits
> bzw Paritybits ich wählen muß? Ich habe immerhin 105
> Zeichen und soweit ich das verstanden habe gibt es nur eine
> Gesamtlänge des Codeworts von 57 oder das nächst höhere
> 120! Das passt ja beides nicht.
Wenn Du recht hast, und es ist ein Hamming-Code, dann kann es ja nur entweder einer mit drei Bits (je 1 Datenbit)
handeln, dann würdest Du insgesamt 105*1/3=35 Datenbits herausbekommen, oder Du hast einen Hamming-Code mit 15 Bits (davon 11 Datenbits), dann würdest Du insgesamt 105*11/15=77 Datenbits herausbekommen. Andere Kombinationen fallen aus, weil sich 105 nicht als Vielfache anderer Codelängen darstellen läßt.
Jetzt kannst Du nur rechnen. Und selbst dafür reicht die Information nicht aus:
Nehmen wir mal an, Du hast einen 15-Bit-HC, dann ist das erste Codewort
[mm]\overline{0}\overline{1\overline{0}}\overline{1\overline{0}\overline{1\overline{0}}}\overline{0\overline{0}\overline{0\overline{1}}\overline{0\overline{0}\overline{0\overline{0}}}}[/mm]
Ich hab die Paritäten schon eingezeichnet, unten [mm] p_1, [/mm] oben [mm] p_4. [/mm] Die einzige Parität, die stimmt, ist [mm] p_3, [/mm] also ist die Stelle falsch, wo sich die anderen drei überschneiden.
Damit lautet der korrigierte Code:
[mm]\overline{0}\overline{1\overline{0}}\overline{1\overline{0}\overline{1\overline{0}}}\overline{0\overline{0}\overline{0\overline{\mathbf{0}}}\overline{0\overline{0}\overline{0\overline{0}}}}[/mm]
So, Parity-Bits raus (die stehen genau an den Zweierpotenzen), bleibt: 00100000000
Das gilt natürlich nur, wenn es sich um einen normalen Hamming-Code handelt. Es gibt auch solche mit separierten P-Bits, dann wäre jetzt schon alles falsch. Ansonsten: Weitermachen!
> Und wie sieht das ergebnis
> im Endeffekt aus: ist das dann ein binärcode den ich
> wiederrum übersetzen muß oder kommt da text raus?
Tja. Meine Glaskugel ist in der Werkstatt. Ganz ehrlich: Du hast nichts außer 105 Bits und der Annahme, das sei ein Hamming-Code. Selbst wenn ich recht habe und das ein 15-Bit-HC ist: Woher soll ich wissen, was mit den 77 Datenbits kodiert ist? 7 Bit ASCII? Unwahrscheinlich, dann wäre das erste Zeichen 0010000 nur ein Steuerzeichen.
Naja, es bleibt ja noch der 3-Bit-Hammingcode. Der ist einfacher. Man nimmt einfach das häufiger vorkommende Bit (denn der richtige Code ist ja nur einen Schritt entfernt, und der Code für 0 ist 000 und der Code für 1 111).
Also los:
010 0
101 1
000 0
010 0
000 0
011 1
001 0
001 0
000 0
001 0
011 1
010 0
010 0
100 0
001 0
100 0
100 0
000 0
000 0
000 0
000 0
011 1
010 0
000 0
000 0
100 0
000 0
000 0
110 1
101 1
000 0
100 0
000 0
110 1
010 0
So kommt also 01000100001000000000010000001100010 raus.
Auch nicht besser. 7 Bit-ASCII scheidet wieder aus.
> Fragen über Fragen, hatte gehofft im Netz ein gutes Tool
> für sowas zu finden, da ich aber die Bit-zahl nicht weiß
> komm ich gerade nicht weiter!
Ich fürchte, selbst die Bitzahl hilft Dir nicht.
Kann natürlich noch sein, dass es sich um einen 15-Bit-HC handelt, bei dem in jedem Codewort genau ein 8-Bit-Ascii kodiert ist, oder ich bin irgendwo von der falschen Bitordnung ausgegangen. Du kannst ja mal rumprobieren.
|
|
|
| |
|
Hi bazzzty!
Auch wenn deine Antwort keine Lösung herleitet, so bin ich doch schon ein ganz schönes Stück weiter! Ich hab dank deiner ausführlichen Beschreibung endlich kapiert wie das generell mit dem Hamming-Code funktioniert. MIr war nicht bewußt das man die Parity-Stellen einfach rausstreichen kann 
Eine kleine Frage hab ich allerdings dann doch noch: Woher weißt du das p3 die einzige Parität ist die stimmen kann? Sieht man das einfach, muß man dafür irgendwas rechnen?
Gruß sagt superkermit
PS: Mittlerweile hat unser Lehrer uns den Tip gegeben, das wohl eine Koordinate rauskommen soll!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:51 Fr 13.03.2009 | | Autor: | bazzzty |
> Hi bazzzty!
>
> Auch wenn deine Antwort keine Lösung herleitet, so bin ich
> doch schon ein ganz schönes Stück weiter! Ich hab dank
> deiner ausführlichen Beschreibung endlich kapiert wie das
> generell mit dem Hamming-Code funktioniert. MIr war nicht
> bewußt das man die Parity-Stellen einfach rausstreichen
> kann
Das freut mich. Bei den längeren Codes wie HC15 kann man das besonders gut sehen. Noch ein bißchen einfacher ist es, wenn man
(anders als die Wikipedia) die Parity-Bits [mm] p_0...p_3 [/mm] nennt.
Dann steht [mm] p_0 [/mm] an Stelle [mm] 2^0 [/mm] = 1, und angefangen bei [mm] p_0 [/mm] gehört immer eins dazu, eins nicht dazu usw.
[mm] p_1 [/mm] steht an Stelle [mm] 2^0 [/mm] = 2, und angefangen bei [mm] p_1 [/mm] gehören immer 2
dazu und zwei nicht dazu.
usw.
> Eine kleine Frage hab ich allerdings dann doch noch: Woher
> weißt du das p3 die einzige Parität ist die stimmen kann?
> Sieht man das einfach, muß man dafür irgendwas rechnen?
Muß man rechnen. [mm] p_3 [/mm] stimmt, weil die für [mm] p_3 [/mm] angestrichenen Bits eine gerade Anzahl von 1er enthalten. Bei den anderen gilt das nicht. Und wenn man weiß, welche nicht stimmen, gibt es nur genau eine Stelle, an der man das mit einer einzigen Änderung verbessern kann.
> PS: Mittlerweile hat unser Lehrer uns den Tip gegeben, das
> wohl eine Koordinate rauskommen soll!
Das gibt dem ganzen natürlich eine etwas andere Richtung, viel Spaß beim Knobeln!
|
|
|
| |
|
Hallo!
Prima, das is ja alles gar nicht so schwer! Dann werd ich jetzt den 15er nochmal vorknüpfen, jetzt wo ich weiß worauf es ankommt. Hoffentlich stelt sich dann die Erleuchtung ein
Auf jeden Fall danke für deine ausführliche und schnelle Antwort!
Gruß
superkermit
|
|
|
| |
|
Hi!
EIn paar Minuten später und ein paar Berechnungen weiter, hab ich nun doch noch eine Frage!
Beim nächsten 15 Paket bekomm ich 2 Fehler raus! Kann ich die dann einfach korrigieren? Ich habe nämlich gelesen das nur ein Fehler pro Datenpaket eindeutig korrigiert werden kann?
Gruß superkermit
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:14 Fr 13.03.2009 | | Autor: | bazzzty |
> Hi!
>
> EIn paar Minuten später und ein paar Berechnungen weiter,
> hab ich nun doch noch eine Frage!
> Beim nächsten 15 Paket bekomm ich 2 Fehler raus! Kann ich
> die dann einfach korrigieren? Ich habe nämlich gelesen das
> nur ein Fehler pro Datenpaket eindeutig korrigiert werden
> kann?
Es kann keine zwei Fehler geben, es gibt immer einen gültigen Hamming-Code in Abstand 1. Vielleicht schreibst Du mal, wo das Problem auftaucht?
|
|
|
| |
|
Hi!
Ich habe mir mal den zweiten 15er block vorgenommen
011001001000001 (sprich ich zähle 5 mal 1er, damit ist p1 die einzig richtige Parität die stimmt)
Jetzt habe ich nach überschneidungen von p2-p4 gesucht und finde diese bei den letzten 2 Stellen des 15-er blocks also bei 01! Darf ich dann nur die betrachten/korrigieren an dessen stelle die 0 steht?Also heißt es dann in der Korrektur: 11 oder wenn ich beides als Fehler betrachte 10?
Und dann hab ich noch eine Frage: Wenn 3 Paritäten stimmen, mit was vergleich ich dann die 4 und damit einzig übrigbleibende?
Vielleicht hängen beide Fragen auch zusammen?Ich hoffe ich hab mein Problem gut in Worte fassen können....
Dankend Superkermit
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:30 Sa 14.03.2009 | | Autor: | bazzzty |
> Hi!
>
> Ich habe mir mal den zweiten 15er block vorgenommen
>
> 011001001000001 (sprich ich zähle 5 mal 1er, damit ist p1
> die einzig richtige Parität die stimmt)
Ich bin mir noch nicht sicher, ob Du die Paritäten richtig berechnest:
[mm] p_1 [/mm] sind die Stellen 1,3,5,7,9,11,13,15. Da sind drei 1er dabei, also stimmt die nicht.
[mm] p_2 [/mm] sind die stellen 2-3, 6-7, 10-11, 14-15. Da sind 4 1er dabei, also stimmt die Parität.
[mm] p_3 [/mm] sind die Stellen 4-7 und 12-15. Da sinds zwei 1er, stimmt.
[mm] p_4 [/mm] sind die Stellen 8-15. Zwei einser, stimmt.
Es könnten auch mehrere Paritäten nicht stimmen. Jede Stelle wird von einer eindeutigen Kombination überdeckt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:09 Mo 04.05.2009 | | Autor: | dau45 |
| Aufgabe | | Nun empfangt Ihr die Zahlenfolgen 0100000, 1111011, 1100010, 1000001 und 1100111. Prüft, ob es sich jeweils um fehlerfreie Übertragung handelt. Gebt gegebenenfalls die falsch übertragenen Bits an und korrigiert dann die empfangenen Zahlen. |
Hallo, dank deines Postes habe ich die o.g. AUfgabe (so denke ich) verstanden.
0100000 => 0000000
1111011 => 1111111
1100010 => 1100110
1100111 => 1100110
Wenn ich mich nicht irre? Zumindest werden diese Ergebnisse durch ein kleine Tool (http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl) bestätigt.
Ich habe halt, wie hier geschrieben wurde, immer geschaut welche Datenbits auf welche Prüfbits einfluss haben und dann geschaut, wo sich die Linien überschneiden. Das geht bei so kurzen Codewörter ja realtiv leicht.
Nun komme ich beim letzten Codewort nicht weiter: 1000001.
Ich würde wie folgt rangehen: p1 ist das einzig richtige Prüfbit. Also schauen wo sich die beiden anderen Linien überschneiden; das tun sie bei c6.
Daraus ergibt sich für mich die Korrektur zu 1000011.
Lt. dem Tool ist das Ergebnis aber 1100001. Aber wie kann das
sein?
p3 ist ja = c5 XOR c6 XOR c7.
In dem Fall p3 = 0. 0 XOR 0 XOR 1 ist doch aber 1?!
Danke für eure Hilfe!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:34 Di 19.05.2009 | | Autor: | bazzzty |
> Lt. dem Tool ist das Ergebnis aber 1100001. Aber wie kann
> das
> sein?
Einfache Antwort: Der konstruiert irgendwelche Codes mit Mindestabstand 3 zwischen den Codewörtern. Er schreibt ja auch, dass man aus einer Liste mit Codewörtern durch beliebiges Vertauschen der Bitpositionen wieder neue Codes konstruieren kann. Bei dem ist auch 0000111 ein gültiges Wort. Die anderen Beispiele waren entweder trivial oder zufällig Codewörter in beiden Codes
|
|
|
|
