mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Komprimieren auf einem Mikrocontroller in C


Autor: Jan S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich würde gerne einen 24 Byte Kraftmessungs-Datensatz komprimieren.
und am besten auf minimal Anzahl von 40 Bit - Paketen verteilen.

Auf der Suche bin ich auf http://www.quicklz.com/download.html
gestoßen und würde das gerne verwenden.

Allerdings werden hier fopen und fread, etc. Befehle verwendet.
Sind diese überhaupt möglich auf einem Mikrocontroller auszuführen.

Welche Alternativen habe ich, um obiges zu implementieren.

Gruß
Jan

Autor: Olaf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Allerdings werden hier fopen und fread, etc. Befehle verwendet.

Also auf meinem Controller kann ich die verwenden. :-)
Und wenn man es nicht koennte, dann koennte man sie ja nachprogrammieren 
oder das Programm aendern.

Aber denke doch erstmal ueber etwas anderes nach. Du willst von 24Byte 
auf 8Byte komprimieren. Das ist ja schon sehr heftig. Aber bei 
Computerdaten oftmals sogar drin. Aber dein Kompressionsfaktor haengt 
von deinen Messdaten ab. Was machst du wenn du eine Messung hast die 
sich nicht soweit komprimieren laesst? Kommt dein Uebertragungskanal 
damit klar?

Olaf

Autor: A. K. (prx)
Datum:

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

Autor: U.R. Schmitt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jan S. schrieb:
> ch würde gerne einen 24 Byte Kraftmessungs-Datensatz komprimieren.
> und am besten auf minimal Anzahl von 40 Bit - Paketen verteilen.

Wenn Du mal liest was in dem Link den Du gepostet hast steht:
Zitat:
"Because LZ compression is based on finding repeated strings, 
compression ratio can degrade if a data entity is being split into 
smaller packets"

Dann solltest Du erkennen daß es so nicht funktionieren kann.
Der LZ Algorithmus baut sich einfach gesagt eine art Dictionary 
(Wörterbuch) auf mit dem er sich wiederholende Char (Oder auch Byte) 
Folgen kürzer darstellen kann.
Bei 8Byte Gesamtlänge kannst Du da gar nichts komprimieren.
Falls Deine Messwerte zu einem Großteil aus 0-Bits bestehen könnte man 
es mit einem binären RunLength Encoding versuchen.
Ansonsten müsste man viele Deiner 8Byte Pakete nehmen, die dann in ein 
Paket komprimieren und senden. Aber das kannst Du auf einem kleinen µC 
nicht zwischenspeichern, unabhängig davon ob die Daten überhaupt so 
lange verzögert werden dürfen.

Sorry aber sas sieht mir irgendwie nach: "Ich will was erreichen, aber 
nicht darüber nachdenken oder es verstehen sondern die Lösung aus dem 
Internet kopieren" aus.

Autor: U.R. Schmitt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> 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

Oder so,
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?

Autor: Jan S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich benutze den PIC32MX,
da kommt dann irgendwas von "R_MIPS_26 against 'fopen'" oder so.


Mit den Messdaten hast du recht.
Prinzipiell will ich nur übertragen, wenn sich die Werte ändern.
Dazu müsste ich denke ich erst einmal einen Schwellwert verwenden.

Und danach könnte ich dann Compressionsalgorithmen drüber laufen lassen, 
korrekt.

> Was machst du wenn du eine Messung hast die sich nicht soweit komprimieren 
laesst?

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.

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

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

Autor: A. K. (prx)
Datum:

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

Autor: A. K. (prx)
Datum:

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

Autor: U.R. Schmitt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ A. K. und Läubi
Stimmt, danke.

Autor: Hc Zimmerer (mizch)
Datum:

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

Autor: A. K. (prx)
Datum:

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

Autor: Olaf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Heißt das, dass nachdem ich komprimiere ich eigentlich nie weiß
> wieviele Bits rauskommen?

Darueber darfst du selber nachdenken. Das haengt naemlich von deinen 
Daten ab.

Ein Beispiel, du willst Kraefte messen...
Es koennte sein das sich deine Kraft langsam aufbaut, immer groesser 
wird und dann wieder abbaut.
Dann ist die Uebertragung von Differenzen wie es dir hier empfohlen 
wurde natuerlich ziemlich genial und eine gute Loesung.

Jetzt nehmen wir mal an es kommt zu erheblichen Spruengen im Signal. Das 
kann ein Fehler in deinem System sein, z.B ein lockeres Kabel. Dann ist 
es okay wenn die Daten nicht richtig uebertragen werden koennen.
Aber was ist wenn solche Daten in deiner Realitaet vorkommen? Dann musst 
du vielleicht ploetzlich mehr Daten uebertragen als dein 
Uebertragungskanal breit ist.

Letztlich ist das ein Spiel mit Wahrscheinlichkeiten. Je laenger du 
darueber nachdenkst und umso besser du deinen Algorthmus an deine Daten 
anpasst umso besser funktioniert das. Aber es gibt eben keine Garantie. 
Und dann musst du dich fragen ob du damit leben kannst wenn mal etwas 
verloren geht.

Olaf

Autor: Jan S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke euch.

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

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

Autor: Zwölf Mal Acht (hacky)
Datum:

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

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.