Momentan verwende ich einen Hamming (7,4,3) Code als Kanalcode für eine
433MHz Verbindung mit einem Atmega32. Der Encoder und Decoder ist als Lookup Tabelle abgelegt. Nun wollte ich das Ganze effektiver/leistungsfähiger gestalten und habe mich in Richtung BCH und Reed-Solomon umgeschaut.
Nun wollte ich fragen ob jemand hier Erfahrung mit 8-bit RISC und RS hat. Wie weit macht das überhaupt Sinn bei einer 16MHz CPU, wenn man ja auch noch was anderes rechnen will. Könnt ihr links zu embedded, optimalerweise AVR optimierten C Code geben?
(google kann ich benutzen, habe schon genügend blabla in Foren wie "könnte gehen" usw. sowie C Beispiele für PC, Verilog FPGAs gefunden)
Copy&Paste und Zeiten habe ich auch nicht. (Hätte ich im Archiv, darf aber nicht :-) ). Vor Jahren hatte ich mich bei einer 868/500mW Kommunikation (bis
10km mit Antenne) für einen Turbo-Code als effizienteste Methode entschieden. Über die Gründe von damals weis ich nicht mehr viel, der Algorithmus wurde aus verschiedenen Quellen und Probiererei zusammengebastelt, funktionierte und wurde lange als Black-Box verwendet. Er wurde flexibilitätshalber auf PC gerechnet, ein kleiner PIC machte nur dumme Modem-Aufgaben. Ich war aber damals der Meinung :-) dass er auf einem etwas größeren µC auch gerechnet werden könnte...
Natürlich. Über eine 433MHz ISM-Verbindung laufen im besten Fall ein paar hundert kBit/s, also ist eine Datenstrom von maximal vielleicht
10kByte/s zu behandeln. Das ist für einen ATMega mit 16MHz Takt keine nennenswerte Belastung, zumal im Flash reichlich Platz für Lookup-Tabellen ist, er also garnicht wirklich ernsthaft rechnen muß.
Wie wär's denn mal mit selber programmieren? Soll ganz gut für das Verständnis der Algorithmen sein. Und wenn man das hat, dann fällt es auch nicht schwer, für andere Zielsysteme geschriebenen Code geeignet anzupassen...
gäbs schon BCH(31,21) ( vgl. POCSAG ) oder auch Golay(23,12). Ist aber ( o Schreck ) nichtmehr ganz kostenlos, nominell FORTH und 68HC908/6502. Der Assemblercode für solche Codes ist simpel, kurz und relativ schnell wenn man ROMs im Decoder verwenden kann.
Könnte auf 8 Bit CPU mühselig werden. In Heft 12 ( ca. 1 Januar ) käme zu dem Thema als erster Schritt die binäre Variante für BCH via Euklid/Berlekamp-Massey/Chien usw. Ist aber nicht unmittelbar für Anwendung auf Controller sinnvoll.
Gäbs zu diesem Buch ( 2. Auflage ) auf der Webseite des Autors:
formatting link
Die 1. Auflage
formatting link
wird bei ebay.uk sporadisch von Buchhändler verramscht. Den C Code fand ich recht lesbar. Nachteil des Buches der wohl auch für 2. Ausgabe ( 278 S. ) gilt: auf 240 Seiten versucht er zuviele Themen abzuhandeln.
Das Thema würde mich auch interessieren im Zusammenhang mit 8-Bit CPUs. Es sollte also ein effizienter Code sein. Effizient also im Sinne von leichtem Code und der Algorithmus passend zur Fehlerverteilung der Nachrichtenverbindung.
Vielleicht mal bei
formatting link
vorbeischauen? Die haben so Sachen schonmal in ihren Satellitenverbindungen benutzt.
Die Seite von Phil Karn sollte auch gelesen werden. Er spielt allerdings gern mit ähem etwas größeren CPUs.
Wie ich oben etwas undeutlich geschrieben habe sind mir die Algorithmen klar. Es geht nicht um eine Lernaufgabe sondern um eine Lösung die wenig Zeit benötigt und bereits implementiert ist.
Es ist nicht immer sinnvoll das Rad neu zu erfinden. Schau dir z.B. die uart library von Peter Fleury an. Natürlich kann man das auch selbst programmieren, aber bis die dann ausführlich getestet ist (auch auf verschiedenen AVRs) geht einige Zeit rum.
Und gerade bei der Geschwindigkeitsoptimierung kann man einige Zeit verbraten. Nimm als Beispiel verschiedene Implementierungen vom Damenproblem...
Also um es klar auszudrücken: selbst implementieren werde ich das sicher nicht, habe mit meiner Arbeit und in der Freizeit mit einem Wireless Stack für die Module genug zu tun.
Ja, auf der Seite war ich schon und habe mir die PDFs angeschaut... Ich dachte zuerst Evince macht Probleme, bis mir klar wurde, das die unschärfe wohl erst durch klingelnde Münzen(metaphorisch) wegzubekommen ist.
Muß man die beiden Grundtypen unterscheiden: Blockcodes und Trellis. Massey hat dazumal gesagt die Blockcodes seien gut für (akademiologische) Papers und Trellis sei gut für Kommunikation. Ganz so einfach ist es zwar nicht, weil RS auch seine festen Anwendungen hat, aber bei Funk ist Trellis sicher auch einen Blick wert. Behandelt meine Zeitchrift allerdings noch nicht.
Manchmal ist man schon so auf Optimierung fixiert, dass man vergisst den Jetzt-Zustand zu messen/profilieren - Zyklen pro MIPS abschätzen, was sehr schnell geht. Dann sieht man doch sehr schnell ob/wo der Coder ausreichend praktikabel ist. Den Faktor kann man sich leicht(er) denken
Wenn Du wirklich Reed Solomon Codes auf einem AVR _de_codieren willst, dann darfst Du Dich ziemlich warm anziehen.
Das ist im Korrekturfall (Syndrom ungleich Null) eine äußerst üble Rechnerei, alleine die Chien Suche, die nix anderes als eine Brute Force Suche ist, welche Additionen und Multiplikationen im erweiterten Galois Feld benötigt, dürfte das Controllerle lange beschäftigen.
Und für Galois braucht es, wenn es schnell gehen soll und nicht gerade GF(2^4) im Raum steht, Hardware oder ganz viel Speicher für Tabellen. Bei DSP's ist das so ab der Klasse TI 64xx verfügbar ...
Im Endeffekt läuft es beim AVR auf eine fade Halbimplementierung (z.B. mit auf vermutete typische Fälle reduzierter Suche) wie bei so manchem CD-Player hinaus, die beim erstbesten echten Korrekturfall versagt.
Dto. bei ADSL Modems (dort ist RS der innere Fehlerkorrekturcode), ich möchte nicht wissen, wieviele Pseudo-Implementationen im Markt sind. Das Wegwerfen weniger IP Pakete fällt nämlich naturgemäß nicht sonderlich auf und wenn der RS Decoder viel beschäftigt wird, folgt meist eh' kurz drauf der Sync. Loss ;-/
Zudem ist es bei Datenübertragungen meist so, dass wenn ständig die RS Fehlerkorrektur anspringt, es bis zum ersten nicht korrigierbaren Fehler nicht mehr weit ist (weswegen z.B. bei ADSL ein äußeres CRC existiert, RS kann den Fall nämlich nicht unbedingt erkennen). Hingegen bringen Verfahren wie Trellis/Viterbi oder Turbo-Codes auch in der Praxis einen echten Codierungsgewinn (da darf dann ständig etwas zu korrigieren sein), ein kleines Viterbi dürfte auf dem AVR noch gehen, Turbo möchtest Du aber auch da nicht wirklich.
Insofern finde ich den Hamming Code für die Zielhardware gar nicht mal so die schlechte Wahl.
Konstruktiver Vorschlag:
Du könntest Dir alternativ auch noch den Meggitt Decoder mit Fehlerfallen-Decodierung ansehen, der liefert bei funktypischen Mehrbit-Bündelfehlern mit wenig Implementierungs- aufwand eine ganz ordentliche Leistung und sollte sich leicht auf dem AVR realisieren lassen. Die ersten Festplatten- ECC waren beispielsweise damit realisiert, entweder liefert das Schieberegister ein Syndrom von Null, dann ist alles ok, oder man schiebt solange weiter, bis das Muster auf ein korrigierbares Fehlerbündel weist (Bitmaske). Die entsprechenden Bits werden dann einfach negiert.
Das mit einem äußeren CRC abgesichert und schon ist eine AVR-kompatible Lösung für Bündelfehler infolge kurzer funktypischer Störungen da.
Den Versuch, mit dem AVR richtig Decodierungsgewinn zu schinden, halte ich hingegen für sehr gewagt ...
Hallo Oliver, ich habe mir den Tag durch diverse Implementierungen angesehen und bin der gleichen Meinung. Reed Solomon fällt somit flach. Vielen Dank für dein ausführliches Posting, ich werde mir die von dir erwähnten Verfahren weiter ansehen.
Hier findet sich was, ganz am Ende, am praktischsten geht wohl das Fehlerfallenprinzip:
formatting link
Das "Gewicht" ist in dem Zusammenhang ganz einfach die Zahl der 1-Bits. Im Grunde rechnet man mit dem Rest und einem Nulldatenwort einfach nochmal die Polynomdivision durch, dann sieht man, wo der Fehler (eben die 1-Bits) reingekommen sind. Unter der Annahme eines Bündelfehlers dürfen eben nur wenige beieinander liegende Bits gesetzt sein, eine Und-Maske auf einem Teil des Schieberegisters mit nachfolgender Abfrage auf Null kann das einfach regeln. Da der AVR problemlos schieben, und das XOR einbringen kann, sollte das Verfahren sehr kompakt zu implementieren sein.
Wichtig ist nur ein Generatorpolynom, welches auch für diesen Zweck geeignet ist (!), am besten man nimmt ein bewährtes solches aus der Literatur. Eine äußere Prüfsumme kann dann zusätzliche Sicherheit gegen eine fehlgeschlagene Korrektur bieten.
Ich verrate jetzt mal ein kleines Geheimnis ;-)
Das Spiel klappt auch mit GF(2^n) und führt dann auf einen Schmalspur-Decoder für Reed Solomon Codes (sozusagen der für die billigen CD-Spieler und Modems ;-). Natürlich kann der bei weitem nicht so schön korrigieren wie Berlekamp-Massey, Forney & Co, aber er ist _viel_ einfacher zu realisieren und packt gewöhnliche Bündelfehler mit relativ vielen defekten Bits. Der Rest, nunja, wozu gibt eine Paketwiederholung ;-)
Wenn man dann eine Tabelle mit einer Umsetzung zwischen der Potenzdarstellung und der Polynomdarstellung der Elemente des erweiterten GF aufbaut, könnte das sogar als Simpel-RS En-/Decoder noch mit einem AVR spielen, es wäre aber einiges an Entwickungs- und vorallem Testarbeit zu leisten.
Meggitt ist Heft 5 , Error Trapping Heft 7. Bei einigen Artikeln kann man auch kostenloser im Archiv der VD fündig werden: http:/
formatting link
Aufwandsabschätzung für RS auf 8 Bit CPU gabs auch schon:
formatting link
Vgl. vorletzte Seite dort: 1,25kBit/sec auf "4 MHz Z80". Der entspricht wohl ca. 1 MHz 6502/68HC08 und letzteren gibts bis 20MHz. Das bezieht sich aber immer auf liebevoll handcodierten Assembler. Der Controller bräuchte einige kByte RAM für FIFOs und wohl
Dein obiger Link ist mir unverständlich. Für Hamming hatte ich irgendwo schonmal eine gute Kochrezept-Anleitung gefunden, aus der man direkt den notwendigen Programmcode zusammenbasteln könnte. Ist mir leider entfallen wo das zu finden war. Das Thema interessiert mich schon gute
15 Jahre. Habe einiges gesammelt und verloren, unsortiert. So wird das also leider nichts. Mir felht einfach die Übersicht und wenn man sich was davon erarbeitet hat, kommt was anderes dazwischen und schon ist das wieder vergessen.
Danke Oliver, aber davon verstehe ich noch weniger.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.