www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Komprimieralgorithmen speziell für MC


Autor: Günther Frings (taraquedo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo!

Vielleicht habt ihr ja einen Tipp für mich, wonach ich suchen sollte. 
Ich brauche für eine AVR Datenkommunikation demnächst einen 
Komprimieralgorithmus, der natürlich auch für einen AVR geeignet sein 
sollte.

Komprimiert werden sollen Blöcke von einer Länge von wenigen Byte bis zu 
Größenordnungen von kB. Der Inhalt dieser Blöcke ist hauptsächlich Text, 
also nur eine Untermenge der ASCII Tabelle. Darauf beschränken würde ich 
es allerdings nicht wollen.

Was kann man dafür am besten nehmen?

Grüße!

Autor: Null (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es gibt da Verschiedenes. Fuer kleine Blockgroessen ist allerdings 
nichts. Das beste, das ich mal antraf war ein Entropiekompressor der hat 
die Codierungstabelle dynamisch angepasst, dh waehrend dem Vorgang. Der 
musste auch keine Tabelle vorneweg uebermitteln.

Autor: ABu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schau mal unter http://www.dspguide.com/pdfbook.htm da gibts auch ein 
Kapitel zum Thema Komprimierung. Ist zwar alles auf Englisch aber sehr 
gut beschrieben, vorallem muss man vorher nicht Mathe studiert haben ums 
zu verstehen.

Grüße
A_Bu

Autor: Günther Frings (taraquedo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi!

Ja, da habe ich mich gerade mal erkundingt. Also der Huffman-Code klingt 
ja sehr interessant für diesen Zweck. Mit einer statischen Tabelle käme 
man da ja mit relativ wenig Arbeitsspeicher aus. Vielleicht ist eine 
Vorwärtsdynamik später ja auch noch machbar.

Der LZW scheint ja auszuscheiden, da er ja allein eine Tabelle mit 4096 
Einträgen besitzt. So groß ist ja der komplette RAM meines AVR, das 
ginge ja gar nicht. Scheinbar auch zu schwer zu implementieren.

Gibt es bereits ferige Implementiereungen für Huffman speziell auf dem 
AVR oder einfach Quellen für PC nutzen?

Grüße!

Autor: Nachdenklicher ... (dms)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guten Tag,
eine kleine Nachfrage  was ist das eigentlich zu lösenden Problem -
oder geht es nur akademisch um eine Komprimierung an sich -und wie steht 
es einfach mit RLE?

Ahoi D.

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

RLE funktioniert bei Text nicht wirklich gut. Für einen AVR der Text 
komprimieren soll würd ich auch einen statischen Huffman vorschlagen.

Matthias

Autor: Tishima (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo!

Um was fuer Texte handelt es sich überhaupt ?
Muss es wirklich ein universelles Komprimierungsverfahren sein ?

Wenn der Text z.B. nur Maschinenbefehle oder Messwerte in Klartext 
enthält bringt es mehr den Text zu Parsen und in einen Binaercode zu 
wandeln.

mfg,
Bjoern

Autor: Günther Frings (taraquedo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi!

Getreu nach dem Prinzip häufiges soll wenig Bitlänge, weniger häufiges 
darf mehr erzeugen, werden Messwerte und andere häufige Parameter 
bereits binär übertragen und müssen nicht zusätzlich kodiert werden. Da 
habe ich die Redundanz durch das Modell quasi schon so gut wie entfernt.

Mein Projekt besitzt eine serielle Konsole, die quasi zweigeteilt ist. 
Ich reserviere ein ASCII-Zeichen für meine Verwendung, welches auf einen 
"binären" Modus umschaltet. Die Rückschaltung auf den üblichen Textmodus 
erfolgt aufgrund einer bekannten Datenlänge im binären Modus. Dadurch 
kann im binären Modus jedes Zeichen benutzt werden. Binär wären hierbei 
die Messwerte und andere häufige Übertragungen. Text ist dann eine 
normale Konsole mit Befehlsannahme und ausgabe. Die Antworten auf die 
Befehle sind alle in dt. Sprache verfasst.

Diese Konsole mit ihren zwei Funktionen soll nun so wie sie ist verpackt 
und über Funk verschickt werden. Entweder über GPRS oder einen einfachen 
Sender/Empfänger. Die Sicherung des Bitstroms im letzteren Fall sollte 
nicht Gegenstand der Komprimierung werden. Die Datenverbindung ist somit 
zeit- und kostenintensiv. Der Punkt, der mich zu einer Komprimierung 
veranlasst.

Der binäre Teil wird also einfach so wie er ist verschickt. Der Textteil 
vorher mit Huffman kodiert. Den könnte ich auch auf die eigentlichen 128 
ASCII-Zeichen beschränken.

Es sei denn, jemand hat eine bessere Idee für die Realisierung. Aber so 
scheint mir das z.Z. sehr angebracht, weil die Senderoutinen über uart 
oder durch die Luft bis auf die Hardwareebene fast identisch sind.

Mir fällt beim Schreiben auf, das das mit dem reservierten Zeichen nicht 
funktioniert, weil Huffman es einbauen könnte. Aber dann könnte ich 
statt dessen alle Übertragungen in Pakete packen, die ich ausreichend 
frankiere. Dann ist am Header ersichtlich, was drin ist und für GPRS 
auch schon vorbereitet. Ein Computerprogramm, welches über ttyS0 eine 
Huffman-kodierung versteht müsste ich dann wohl sowieso noch schreiben.

Grüße!

Autor: Nachdenklicher ... (dms)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>ASCII
.. also 7 Bit im Befehlsmodus - das lässt mich sofort an 
Fernschreiberkodierung denken - also mit einer definierten 8. 
Bit-Seqeunz  toggeln

>Binärmodus
Was wird denn in welchem Wertebereich übertragen



>..verschickt werden. Entweder über GPRS oder einen einfachen
>Sender/Empfänger.... Die Datenverbindung ist somit
>zeit- und kostenintensiv. Der Punkt, der mich zu einer
>Komprimierung veranlasst.

ich frage nocn mal nach - es erfolgt eine Rekodierung Befehle/Antworten 
via Hashtable(?) was soll da noch verkürzt werden?



AHoi D.

Autor: Günther Frings (taraquedo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein, keine Umkodierung in Befehle/Antworten. Zunächst ist der Textteil 
eine Befehlskonsole, wie man sie von DOS oder LINUX her kennt mit 
einfacher Texteingabe und Textausgabe (nur ein bißchen mehr gepuffert). 
Deshalb die Komprimierung mit Huffman.

Nach und nach werde ich natürlich immer mehr Befehle binär gestalten, 
bis im Idealfall alles paketorientiert binär abläuft. Das ist jedoch 
eine Frage der Zeit, die ich in das Projekt stecken kann und vorallem an 
welcher Stelle.

Vorerst halt nur für die frequentierteren Pakete existiert halt ein 
genauer Aufbau. Sprich bit0 bis n hat die und die Funktion usw. Das 
betrifft jedoch nicht meine ursrüngliche Frage. Die zielte nur auf den 
eigentlichen Textteil ab, der eben nicht nach diesem 
Frage/Antwort-Prinzip arbeitet.

Da habe ich auch noch die Frage: Gibt es statistische Auswertungen zur 
dt. Sprache, in denen ich die Häufigkeit der Buchstaben ersehe? Wäre ja 
eine gute Grundlage.

Mit Fernschreiberkodierung verstehe ich nicht, was du damit meinst. 
Kannst du das genauer ausführen? Ich habe dazu nichts gefunden.

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sind das frei formulierbare Texte, oder ist die Menge der möglichen 
Texte schon vorab bekannt?

Autor: Günther Frings (taraquedo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hehe, guter Ansatz. daran habe ich ja noch gar nicht gedacht. Natürlich 
ist die Menge der Texte vom MC her beschränkt durch die 
Stringkonstanten. Dann könnte man die jeweils als Zahl übertragen. 
Natürlich müssen dann eventuelle Ziffern, die Variablen sind 1:1 
übertragen werden.
Die Kommandoeingabe wird jedoch nicht so betrachtet werden können. Z.B.: 
print Hallo Welt!, um "Hallo Welt!" auf ein LCD zu schreiben.

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit so einem maßgeschneiderten Kompressionssystem für eine endliche 
Menge Texte erreichst Du eine Kompressionsrate, von der man bei 
Benutzung allgmeiner Kompressionsalgorithmen, wie lzh, bz2 und wie sie 
alle heißen, nur träumen kann.

Autor: Thomas O. (kosmos)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
man kann die Tabelle ja auch im Flash ablegen, muss nicht ins SRAM, 
Nachteil ist halt das die Tabelle nicht mehr wärend dem Betrieb zu 
ändern ist. bzw. nur über das Neuprogrammieren des AVRs oder Bootloader 
zu bewerkstelligen ist. Und Flash haben Sie inzwischen ja alle genug.

Autor: Nachdenklicher ... (dms)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Servus,

ja das was UhUhU vorschlägt, meinte ich schon vorher mit Hashtable - der 
Controller brauchte die Texte doch nur wenn er sie selber wieder 
anzeigen soll ;-).


Fernschreiber (http://de.wikipedia.org/wiki/Baudot-Code)- flappsig 
gesagt ein 5-Bit-Code hätte also die Möglichkeit mit 5-BIT (quasie 
Untermenge im heutigen) ASCII zu verwenden und dann noch 2³-1 
Kominationen zum Toggeln von Zuatzmodi - oder anders

40 Bit Frame - einfach mal so als Rechenbeispiel

bei 8-Bit/Zeichen können 5 Zeichen übermittelt werden
bei 5-Bis/zeichen dann schon 8 je Datgrammen

zu den Binärdaten - sind das
kontinierliche Werte - freie, fortlaufende Messungen
aquidistante Werte - alle x s ein Messewert
Trendhysteresewerte - nur bei Überschreitung eines bestimmten Deltas 
wwerden Daten übertragen  (+ regelmässiges Ping)


Aber schreib doch einfach mal - meine Schaltung misst das und das und 
soll das und das machen und dorthin das und das übertragen. Da ist ja 
scheinbar auch ein GSM-Modem verbaut.

AHoi D.

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.