Forum: Projekte & Code Huffman-Kompression auf dem AVR


von Daniel O. (nerilex)


Angehängte Dateien:

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

von Markus (Gast)


Lesenswert?

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

von Gast (Gast)


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

von Gast (Gast)


Lesenswert?

Ups, mein Huffman Code ist unsinn ... sorry ;)

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

von Werner B. (werner-b)


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

von Läubi .. (laeubi) Benutzerseite


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

von Daniel O. (nerilex)


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

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.