mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik BCH Code + komprimierter, zyklischer Datenlog


Autor: Richard Scheffenegger (rscheff)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

 ich bin gerade am überlegen, einen Xport Direct etwas umzubauen...

Da das Ding "ewig" laufen soll (zumindest bis NTP überläuft, d.h. 2036), 
sein NOR Flash aber nur für 100 000 Zyklen zertifiziert ist, dachte ich 
daran, einen BCH Encoder/Decoder zu verwenden (mit page erases von 262 
Bytes, und einer Nutzgröße des AT45DB021 von 256 Bytes hätte ich 6 
Bytes, um mindestens 4, ev. 5 Bit-fehler zu korrigieren...)

Natürlich würden die Daten als zyklisches Log gespeichert sein (ca. 128 
kB Effektivgröße).

Kennt jemand eine C-Implementierung eines effizienten BCH Codes mit 
262/256 Bytes, und 3-5 bit-correction?

Das andere wäre noch eine Library zum block-zentrierten komprimieren von 
Datenwerten - wobei jeder block (256 - 1k) selbstreferenzierend sein 
sollte, aber von dynamischer Größe (jeder komprimierte Block kann 
variabel viele Recods enthalten, sollte jedoch die Blockgrenze nicht 
überschreiten...

Hinweise werden dankbar entgegen genommen...

: Verschoben durch Moderator
Autor: DerElektrischeReiter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da sind Beispiele:

http://www.eccpage.com/

cu

Autor: Richard Scheffenegger (rscheff)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hatte ich schon davor gefunden. Bis auf die Kleinigkeit, das die 
Funktion bch_decode in bch3.c "nur" 2,2 MB (oder 4,4 MB - je nach 
sizeof(int)) allocieren versucht - und dann das proggi zuerst  mit stack 
corruption ausstieg, funkt das ja auch - nur in höchstem Maße 
unoptimiert für Platz, Code-Size und Geschwindigkeit...

Momentan sehe ich mir BCH(2096,2048,9) an - und alternativ 
BCH(2048,2000,9), für den Fall das der AT45DS021 auf dem Xport auf 256 
pages formatiert wurde. Generatorpolynom ist in beiden Fällen ident -

1 + x + x^2 + x^5 + x^7 + x^8 + x^9 + x^11 + x^13 + x^14 + x^15 + x^22 + 
x^24 + x^25 + x^27 + x^29 + x^30 + x^32 + x^34 x^35 + x^37 + x^38 + x^41 
+ x^42 + x^46 + x^47 + x^48

Allerdings stimmt das nicht mit einem shortened 4095,4047,4 code überein 
(gibt es für BCH mehrere Lösungen? Ist dann nicht die mit der kleinsten 
Anzahl an Summanden die beste?) die ich sonst gefunden habe (aber ohne 
source code).

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

wenns' nicht unbedingt BCH sein soll sondern Reed-Solomon Codes auch 
gehen, ist möglicherweise die homepage von Phil Karn hilfreich:

http://www.ka9q.net/code/fec/

Seine RS-Codecs hatte ich vor langer Zeit mal ausprobiert, damals waren 
die sexy, d.h. schön, schnell und schlank. Über die aktuelle Version 
weiß ich nichts, ein Erlebnisbericht würde mich aber interessieren.

Cheers
Detlef

Autor: Richard Scheffenegger (rscheff)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
BCH hat den (massiven) Vorteil, viel weniger Overhead zu haben; Das 
encoding ist ein Standard-FIR Filter (mit dem entsprechenden Polynom);

Nachdem ich das Programm bch3.c zurechtgestutzt hatte, ist dieses 
Polynom
herausgekommen; ist vielleicht nicht optimal (da es viele aktive Taps 
hat),
aber dafür ist es mit einer Hamming-Distanz von 9 und einer 
Korrekturrate von
4 für meine Zwecke geeignet.

Hier der Encoder, leicht optimiert (daher nicht so optimal lesbar wie in 
bch3.c):

unsigned char data[256];
unsigned long long int parity;
void bch_encode()
{
  unsigned long long int g = (unsigned long long int)0xC66D6B40EBA7LLU;
  int i;

  parity = 0;

  for (i=2047; i>=0; i--) {
    parity <<= 1;
    if ( ((data[i/8] >> (i%8)) & 1) ^ ((parity >> 48) & 1) )
      parity ^= g;
  }
  parity &= (unsigned long long int) 0xFFFFFFFFFFFFLLU;
}

Als Test: Wenn data 0 ist, ist die parity ebenfalls 0; Wenn in data alle 
bits gesetzt sind, kommt als code 0xAE0B8F1ACE41 heraus.

Nachdem TurboC (für den XPort Direct) leider keine (unsigned long long 
int) 64 bit integer unterstützt, werde ich mir diesen Code noch in 
inline-assembler giessen; sollte ausreichend rasch gehen, das ich vorher 
die Daten noch mit adaptive Huffman nach Vitter (und limitiertem 
Alphabet von 2^6 Einträgen, wg. RAM) komprimieren kann. (Lt ersten Tests 
komme ich kann ich damit in einer 262 Byte Page zwischen 30 und 75 
Records speichern, statt (ohne Huffman) nur 20...

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.