mikrocontroller.net

Forum: Projekte & Code Huffman-Kompression auf dem AVR


Autor: Daniel Otte (nerilex)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
Ich möchte hier meine Implementierung der Huffman-Kompression für den 
AVR vorstellen.
Der Vorteil gegenüber der früher in diesem Forum geposteten Software ist 
die Einhaltung der avr-gcc ABI, so dass dieser Code einfach in 
C-Programmen zu verwenden ist.
Im "host"-Verzeichnis liegen die host-tools zum komprimieren und 
dekomprimieren (geschrieben in portablem C, sollten sich eigentlich 
überall compiliere lassen). Im "test"-Verzeichnis liegt eine 
Test-Applikation die auch noch ein paar andere nette Dinge enthält 
(uart, kommandointerface, dump utility, ...).
Das ganze steht unter der GPLv3 Lizenz.
Updates gibt es im svn unter 
http://das-labor.org/svn/microcontroller-2/lib/avr-huffman.

Der AVR kann allerdings nur dekomprimieren, der Assembler Code dafür 
brauch nur 572 Bytes an Flash-Speicher.

Ein wenig Doku findet sich im Labor wiki unter 
http://www.das-labor.org/wiki/AVR-Huffman

Viel Spaß damit,
  nerilex

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nett, nachher mal testen ob das ganze auch am Cevi mit cc65 will. :)

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mal eine Frage ...


unkomprimiert:
> 00000000  61 62 63 61 61 61 62 0a

komprimiert:
> 00000000  c0 de 05 01 61 00 04 63  0a 62 ff 68 35 e0

Ist im komprimierten auch gleich schon der Huffmann-Baum gespeichert, 
oder nur die komprimierten Daten?

Normalerweise sollte aus der oben genannten Sequenz sowas rauskommen:

Generiertes Alphabet:
a: 0
b: 10
c: 110
0x0a: 111

Ergebnis (binär): 0,10,110,0,0,0,111 = 0x587

aber selbst mit gespeichertem Alphabet ...
0x00 0x61 0x02 0x62 0x06 0x63 0x07 0x0a | 0x05 0x87

Aber das ist immer noch weniger als die Sequenz oben ...

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ups, mein Huffman Code ist unsinn ... sorry ;)

Trotzdme, wieso ist das komprimierte soviel größer, als das 
unkomprimierte?

Autor: Werner B. (werner-b)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Trotzdme, wieso ist das komprimierte soviel größer, als das
> unkomprimierte?

Weil es zu wenig Daten sind. Da ist der Overhead für die Kompression im 
Verhältnis zu den Nutzdaten "suboptimal".

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

Bewertung
0 lesenswert
nicht lesenswert
Gast schrieb:
> Trotzdme, wieso ist das komprimierte soviel größer, als das
> unkomprimierte?
Huffman Kompression funktioniert am besten bei einer unendlichen 
gedächtnislosen Quellen Folge.

00000000  61 62 63 61 61 61 62 0a ist zumindest schonmal nicht sehr 
unendlich ;)

Autor: Daniel Otte (nerilex)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
In dem gewählten Beispiel werden die komprimierten Daten von dem Baum 
dominiert.

Die Daten lassen sich wie folgt aufteilen:

Header: c0 de
Baum:   05 01 61 00 04 63  0a 62 ff
Daten:  68 35 e0

Es gibt mehrere Möglichkeiten einen entsprechenden Huffmanbaum zu 
konstruieren. Daher ist es wichtig den Baum so zu speichern, das er 
exakt wieder hergestellt werden kann.
Ich verwende eine spezielle Technik um den Baum zu speichern. Dazu wird 
der Baum so verändert, dass von links nach rechts der Baum immer tiefer 
wird. Dann werden die Ebenen aufsteigend gespeichert. D.h. Es muss nur 
die Anzahl der Blätter je Ebene gespeichert werden gefolgt von den 
Werten der Blätter.

mfg
  nerilex

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.