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


von Richard S. (rscheff)


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 User
von DerElektrischeReiter (Gast)


Lesenswert?

Da sind Beispiele:

http://www.eccpage.com/

cu

von Richard S. (rscheff)


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).

von Detlef _. (detlef_a)


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

von Richard S. (rscheff)


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...

Bitte 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
Noch kein Account? Hier anmelden.