Hallo! Ich möchte in meinem Projekt eine Fehlerkorrektur einbauen und hab mich hierfür über Kanalcodierung informiert. Ich habe diverse Verfahren kennengelernt und hab erkannt, dass die meisten mehr als komplex sind z.B. Reed Solomon Code oder BCH-Code. Nun bin ich auf den Hamming-Code gestoßen, der sieht noch relativ am machbarsten aus. Mir reicht das eigentlich schon aus mit der Erkennung von einem einzigen Bitfehler und die Erkennung von mehreren, wie es der Hamming-Code kann. Meine Nachricht wäre genau 60 bit Informationsdaten lang, kann man sowas mit diesem Code überhaupt realisieren? Hoffe auf Hilfe! Fux
Könnt ihr mir vielleicht einmal zeigen, wie sowas aussehen würde oder wo ich über die Berechung eines solchen Codes etwas in Erfahrung kriegen könnte? Hat vielleicht jemand von euch schon einmal damit zu tun gehabt?
Hier wird Hammingcode verwendet, um zumindest einzelne Bitfehler zu korrigieren: Beitrag "bidirektionale RS232 Funkbrücke mit RFM12" Allerdings verdoppelt sich damit die Datenrate und wenn sich Bits verschieben ist der Code nutzlos. In der Praxis bringt der Hammingcode also nicht sehr viel. Wenn dir nur die Erkennung von Fehlern reicht, dann würde ich einfach eine CRC über die ganze Nachricht machen und diese mitsenden. Das sollte relativ sicher einen Fehler erkennen können.
Benedikt K. schrieb: > Allerdings verdoppelt sich damit die Datenrate Und ich hätte gedacht sie halbiert sich ;) > In der Praxis bringt der Hammingcode > also nicht sehr viel. Zumindest nicht für kurze Codesequenzen.
Läubi .. schrieb: > Benedikt K. schrieb: >> Allerdings verdoppelt sich damit die Datenrate > Und ich hätte gedacht sie halbiert sich ;) Stimmt, da fehlt ein "benötigte"...
Nein CRC-Prüfung ist mir leider zu wenig. Ich muss einen fehlerkorrigierenden Code entwickeln. Ok, wirklich für die Praxis ist er nicht. Also aus meinen 60bits würden dann 120bit werden oder wie? Aber was gibt es sonst für einen Code, der noch realisierbar wäre? Reed-Solomon ist wirklich schon mehr als schwierig, denn ich muss einen Encoder in LabVIEW programmieren, wo die Daten weggesendet und einen Encoder in C mit CCS-Compiler für das PIC-Board programmieren. Wisst ihr vielleicht einen anderen besseren Code?
Was sind den das für Daten? Was für ein Kanal liegt vor (Fehlerrate, Analog/Digital etc.) Wieviele Fehler müssen detektiert/korrigiert werden? Ist eine Blockweise kommunikation, vieleicht sogar das neu senden von Datenpaketen möglich? Damit läßt sich erst eine vernünftige Aussage treffen.
Genauso ist zu wissen wie die Fehler verteilt sind. RS-Code ist ein Code zur Korrektur von Bündelfehlern. Hamming mehr zufällig verteilte Fehler.
> Was sind den das für Daten? Es sind Strings mit ingesamt 10 Character. Diese Character können entweder A-Z oder 0-9 (36 Zeichen) haben, also hat jeder Character 6bit Mal 10 Character = 60 Zeichen. > Was für ein Kanal liegt vor (Fehlerrate, Analog/Digital etc.) Eigentlich wird der Kanal so gut wie fehlerfrei sein. Ich sende via LabVIEW Daten auf die USB-Schnittstelle, welche mittels USB-RS485-Konverter konvertiert werden, zum PIC. Also treten praktisch keine Fehler auf, eine Übertragung erfolgt nur, wenn ich das mit einem Button in LabVIEW starte und dann nur einmal! Fehler soll ich dann sozusagen künstlich erzeugen, einfach mit einem Button in LabVIEW auf fehlerhafte Übertragung umschalten und dann soll der Blockcode arbeiten. > Wieviele Fehler müssen detektiert/korrigiert werden? Das wär mir egal. Einer alleine reicht schon aus, die anderen müsste ich nur erkennen, denn sofern der Fehler größer als 1 ist, würde ich einfach eine neue Übertragung anfordern und hoffen, dass der Fehler maximal 1 bit groß ist. Aber ich werde das sowieso so einstellen, dass mein künstlicher Fehler maximal 1bit betreffen wird. > Ist eine Blockweise kommunikation, vieleicht sogar das neu senden von > Datenpaketen möglich? Ja ist möglich. > Damit läßt sich erst eine vernünftige Aussage treffen. Ja verstehe. Ich weiß sowieso, dass so ein Blockcode bei mir e nicht notwendig ist, aber es ist leider Gottes eine Aufgabe, die ich erfüllen muss, CRC-Prüfung wäre ja überhaupt kein Problem gewesen. > Genauso ist zu wissen wie die Fehler verteilt sind. Die zu korrigierenden Fehler sollen nur Einbitfehler sein. Bei Bündelfehlern etc. soll einfach eine neue Übertragung gestartet werden.
Dann benutze einfach einen Hammingcode der einen Fehler sicher korrigieren kann und zwei Fehler sicher erkennen kann. Dann kannst du Korrektur von Einbitfehlern und Erkennung von Mehrbitfehlern simulieren. > also hat jeder Character 6bit Wenn du noch etwas über die Verteilung der auftretenden Zeichen weißt ist das nicht zwangsläufig so, du könntest das ganze z.B. Huffmancodieren, dann wären nur die Datenpaklete nicht fix. Wichtiger ist denke ich hier das du Anfang und Ende sicher detektieren kannst. RS485 hört sich zudem nach 8/9 Bit Datenrahmen aus, dann könntest du einen 6/2 (bzw. 6/3) Kode auf jedes "byte" anwenden. Hier gibts doch sogar einen Generator dafür: http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl?X=+Generate+&L=6&D=2&T=000000
Läubi .. schrieb: > Dann benutze einfach einen Hammingcode der einen Fehler sicher > korrigieren kann und zwei Fehler sicher erkennen kann. > Dann kannst du Korrektur von Einbitfehlern und Erkennung von > Mehrbitfehlern simulieren. Ich denke auch, denn ob nun bei meiner Anwendung die Redundanz viel zu groß ist, das ist mir eigentlich egal, solang sich das ganze noch übertragen lässt. >> also hat jeder Character 6bit > Wenn du noch etwas über die Verteilung der auftretenden Zeichen weißt > ist das nicht zwangsläufig so, du könntest das ganze z.B. > Huffmancodieren, dann wären nur die Datenpaklete nicht fix. > Wichtiger ist denke ich hier das du Anfang und Ende sicher detektieren > kannst. Also du meinst zuvor mit Hilfe von Huffman oder Fano, also Quellcodierung, die ganze Nachricht codieren und anschließend das Codewort mittels Hamming codieren. Aber wenn sich meine Nachricht wieder verändert, dann muss ich ja wieder neu Huffman-Codieren. Gibt es da schon fertige Implementierungen? > RS485 hört sich zudem nach 8/9 Bit Datenrahmen aus, dann könntest du > einen 6/2 (bzw. 6/3) Kode auf jedes "byte" anwenden. Wie meinst du das genau? 6/2, 6/3, was bedeutet das genau, bei Hamming bin ich momentan noch sehr, sehr schlecht? Du meinst ingesamt 10 hamming-Codes?
Naja Quellencodierung lohnt hier nur wenn du vorher die Verteilung kennst und denn dann ist der Baum fest. Sonst hast du zuviel Overhead. Das hängt halt davon ab was für Daten gesendet werden (zufällig, Deutsche/Englische/... Texte, o.ä.) 6/3 heißt 6 "Codebits" (deine ursprünglichen Daten) + 3 Paritätsbits (deine "Datensicherung") = 9 zu übertragende Bits/Codewort wo später wieder 6 "Nutzdatenbits" rauskommen. Die Seite wo der Generator angegeben ist enthält eigentlich ganz nette Infos.
Mein String sieht z.B. so aus UI11111111, also 2 Buchstaben am Anfang, dann 8 Zahlen danach = ingesamt 10 bit.
>RS485 hört sich zudem nach 8/9 Bit Datenrahmen aus, dann könntest du >einen 6/2 (bzw. 6/3) Kode auf jedes "byte" anwenden. Meinst du jetz mit Byte nur die 6bit für jeden Character?
6 bit für einen Char + 3 bit Hamming Sicherung. Zu deinen Daten: Wenn Zahlen häufiger vorkommen kannst du diese mit kürzeren Bitsequenzen codieren bringt hier aber denke ich nicht soviel sondern macht die Sache nur komplizierter.
Das heißt, wenn ich jetzt 10 Char habe, brauche ich für meine gesamte Nachricht 90 Bit, weil ich ja 10 Hamming Codes verwenden soll (9 Bits pro Code)?
OK, hört sich gut an. Dann werd ich mal das ganze mir genauer anschauen und mit der Programmierung in C beginnen, kennt ihr vielleicht schon irgendwelche Implementierungen von Hamming-Codes in dieser Programmiersprache und könntet ihr mir diese vielleicht senden oder mir einen Link dazu geben? Dann kann ich mir das ganze einmal in C ansehen, ich muss es ohnehin auch in LabVIEW realisieren und mir dann das ganze noch einmal in einer anderen Programmiersprache durchdenken.
Leider habe ich noch immer Probleme mit diesen Hamming-Codes, könnt ihr mir vielleicht noch ein paar Beispielprogramme senden oder mir Links zu solchen geben? In C für den PIC muss ich den Decodierer programmieren, den Codierer muss ich in LabVIEW programmieren, und hier bin ich schon relativ weit mit der Programmierung.
Bitte nur eine letzte Frage noch beantworten! Welchen Hamming-Code muss ich verwenden, dass ich 64 Codewörter erhalte? Ich soll aber weiterhin 1-bit-Fehler korrigieren, 2-bit-Fehler erkennen können. Bei dem 6,2 und 6,3-Code ist das ja nicht möglich, da hab ich nur 32 bzw. 8 Codewörter laut dem Calculator auf dieser Website: http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl?X=+Generate+&L=6&D=2&T=000000
Läubi .. schrieb:
>6,2 oder 6,3 Hamming Code verwenden
Das funktioniert ja nicht so einfach, wie du vielleicht denkst, mit so
einem 6,2 oder 6,3 Code funktionieren diese Hamming-Codes nicht mehr,
also, dass ich 1 Fehler korrigieren, 2 erkennen kann. Wenn ich nämlich
in den Calculator Codewortlänge 9 und Distanz 3 eingebe, wird das
Codewort beim Empfangen von 2 Fehlern schon fälschlich zugeordnet! Wenn
ich nun die Hamming Distanz auf 4 Stelle, hab ich schon viel zu wenig
Codewörter für meinen Gebrauch, obwohl dann das Ganze wieder
funktionieren würde.
Ich habe nun bei diesem Online Calculator länger herumprobiert und bin
auf einen Code mit 10bit Codewortlänge und einer Hamming-Distanz von 4
gestoßen.
Wenn der Hamming-Code-Calculator 10bit Codewortlänge ausgibt, würde das
bedeuten, dass es ein (6,4)-Hamming Code ist oder, aber haben
Hamming-Codes nicht immer Hamming-Distanz 3?
Gibt es irgendeinen Algorithmus, mit den ich diesen Hamming-Code per
Hand berechnen kann, also nicht nur immer (7,4)-Code?
Der 7,4-Code würde ja bei diesem Online-Calculator der Einstellung 11,4
entsprechen oder?
Du kannst das anze auch über ein Polynom berechnen: http://www.ee.unb.ca/cgi-bin/tervo/galois.pl?binary=1011&s=9&m=1&c=1&d=1
Ich habe aber jetz nachgelesen, dass es nur die (3,1), (7,4), (15,11), ... -Hamming-Code gibt. (6,2) usw. gibt es gar nicht oder? Beim (7,4)-Code erhält man 16 Codewörter, also könnte ich theoretisch 16 unterschiedliche Character übertragen z.b. 0-9 A-F Ich bräuchte aber für meine Anwendung 32 Codewörter, denn ich will 0-9, U, I, A, O, S, F,: und bei einem möglichen Nachfolgeprojekt noch 2 bis 3 Character mehr übertragen. Wie viele Codewörter liefert der (15,11)er bzw. der(31,26)er-Code?
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.