Komprimieren auf einem Mikrocontroller in C

Welche Komprimierung hier sinnvoll ist hängt von allerlei 
Randbedingungen ab. So kann man beispielsweise Messdaten von Signalen, 
die sich von einem Intervall zum nächsten nur marginal verändert, als 
Differenz übertragen und diese Differenz über Huffman codieren (häufige 
kleine Differenzen in wenig Bits, seltene grosse in viel Bits, siehe 
http://en.wikipedia.org/wiki/Huffman_coding). Vorteil dieses Verfahrens 
ist, dass es bereits ab dem zweiten Paket greift und die Übermittlung 
auch nicht verzögert.

LZ Verfahren hingegen entwickeln einen erheblichen kaum komprimierten 
Vorlauf, weil erst einmal genug Daten eingesammelt werden müssen auf die 
spätere Daten zurückgreifen können. Ausserdem sind diese Verfahren für 
Daten mit stetiger Entwicklung (z.B. A/D Samples von Schwingungen) sehr 
schlecht geeignet, da hierbei im Rahmen der begrenzten Erkennung der 
Engine kaum Redundanzen auftreten.

U.R. Schmitt schrieb:
> allerdings die Differenzen Huffman codieren? Das ist doch (wenn ich mich
> recht erinnere) eine arithmethische Codiereung die auch erst mal eine
> Häufigkeitsanalyse macht und dann Codiertabellen erstellt. Wie soll das
> dann gehen?
Dies kann aber schon vorher geschehen, man arbeitet dabei mit einer 
festen Tabelle (wie bei MP3).

Die "kleinen" deltas bekommen dann die kurzen Sequenzen die großen 
kriegen dann einfach die "langen".

U.R. Schmitt schrieb:

> allerdings die Differenzen Huffman codieren? Das ist doch (wenn ich mich
> recht erinnere) eine arithmethische Codiereung die auch erst mal eine
> Häufigkeitsanalyse macht und dann Codiertabellen erstellt. Wie soll das
> dann gehen?

Wann man diese Analyse macht ist offen. Man kann das im Vorfeld machen, 
indem man sich die Häufigkeit der Differenzwerte in typischen 
Messprotokollen ansieht. Dann ist das zur Laufzeit nicht ganz optimal im 
Platzverbrauch, aber sehr viel einfacher und schneller.

Ausserdem ist das letztlich oft weit einfacher als es in dem etwas 
theorielastigen Wiki-Artikel aussieht. Da kann beispielsweise sowas 
rauskommen:
  0..7  => 0xxx
  8..39 => 10xxxxx
  40..  => 110xxxxx....
usw. Völlig tabellenfrei. Und wenn der entstehende Bitstrom bei 
8-Bittern etwas nerven sollte, dann kann man das auch auf der Basis 
eines Bytestroms machen, verliert dabei etwas an Komprimierung und 
gewinnt dafür an Durchsatz.

Jan S. schrieb:

> Ich benutze den PIC32MX,

Das klingt schonmal gut.

> Heißt das, dass nachdem ich komprimiere ich eigentlich nie weiß
> wieviele Bits rauskommen? Das heißt ich muss dann den (40-Bit) Paketen
> noch einen Overhead mitschicken zu welcher Messung sie gehören.

Ein Protokoll zur Trennung der einzelnen Messungen im Datenstrom lässt 
sich nicht vermeiden. Der einzige Weg, deterministisch jedem 
zufallsverteilten Datenwert eine Länge zuweisen zu können, ist die 
unkomprimierte Übertragung. Es sei denn es gibt systematische 
Redundanzen in der Messung, beispielsweise 11-Bit Samples in 32-Bit 
Worten.

Allerdings lässt sich der Trenner als separater Codewert in den 
Huffman-Stream mit einbauen.

Jan S. schrieb:
> Heißt das, dass nachdem ich komprimiere ich eigentlich nie weiß
> wieviele Bits rauskommen?

Das ist ja der Witz an jeder Kompression.  Bei jedem 
Kompressionsverfahren gibt es schließlich Daten, die nicht komprimierbar 
sind, und die werden dann komprimiert länger als unkomprimiert.  Und es 
gibt Daten, die optimal komprimierbar sind.  Die werden dann kürzer als 
der Durchschnitt.

Irgendwie solltest Du an Deinem Verständnis vom Kompression noch 
arbeiten.

Beispiel wie oben, aber mit (oft auftretendem) Code zur Trennung von 
Messpaketen:
  Trenner => 0000
  0..6    => 0001-0111
  7..38   => 10xxxxx
  39..    => 110xxxxx....

Huffman ist übrigens keine Arithmetische Codierung.

Man kann auch den Baum dynamisch generieren, das hat den vorteil, dass 
er sich selbst anpasst und nicht übertragen werden muss.

Beide Seiten fangen mit einem vordefiniertem Baum an (zB ermittelt aus 
vorliegenden Daten, oder einfach ein gleichverteilter) und passen den 
Baum dann nach jedem gesendeten/empfangenden Zeichen an.

Es gibt verlustbehaftete Komprimierung und verlustfreie Komprimierung. 
Bei unspezifizierten Daten muss man auf verlustfreier Komprimierung 
bestehen. Bei Messwerten hingegen kann man verlustbehaftet arbeiten. Dh 
man kann durch Verlust an Genauigkeit komprimieren. Falls zB die Werte 
als 24bit Werte anfallen, aber eh nur 16bit genau sind, der Rest 
Rauschen ist, dann kann man 8bit wegwerfen. Die sind dDatentechnisch 
zwar Verlust, von den Messdaten her aber verkraftbar. Wenn man nun die 
16 bit auch nicht wirklich braucht, sondern nur an einem Ende des 
Bereiches, dann kann man mit einer Kruemmung, einem Logarithmus, oder 
einer anderen nichtlinearen Funktion komprimieren. Aus 16 bit mach 12 
bit oder so. Bei Telephon-Audio ist das beliebt. Siehe A-Law, oder u-Law