mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Hamming Code


Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karsten (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Holger S. (strabe)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Benedikt K. (benedikt) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Benedikt K. (benedikt) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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"...

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: John-eric K. (mockup)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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=+G...

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hans M (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mein String sieht z.B. so aus

UI11111111, also 2 Buchstaben am Anfang, dann 8 Zahlen danach = ingesamt 
10 bit.

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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?

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)?

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So ist es.

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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=+G...

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du kannst das anze auch über ein Polynom berechnen:
http://www.ee.unb.ca/cgi-bin/tervo/galois.pl?binar...

Autor: Hans M. (fuxdancer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.