www.mikrocontroller.net

Forum: FPGA, VHDL & Co. Entropiecoder in Hardware


Autor: Mame (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe gerade folgende Denkblockade:

Ich möchte Huffman in Hardware implementieren (auf einem FPGA mittels 
VHDL). Das Ergebnis soll mit möglichst niedriger konstanter Bitrate 
übertragen werden und wieder dekodiert.

Mein Problem:
Huffman erzeugt jeden Takt Codewörter unterschiedlicher Länge, z.B. 0 im 
besten (und wahrscheinlichsten) Fall und 111110 im schlechtesten 
(unwahrscheinlichen).
Um meine Bandbreite zur Übertragung festzulegen, müsste ich ja trotzdem 
vom schlechtesten Fall ausgehen, also für jedes Codewort die längste 
Zeit zur Übertragung annehmen, was also keinen Vorteil für die 
Bandbreite bringt, oder?
Mein Ziel ist allerdings, die bit/s so niedrig wie möglich zu halten, 
ist Huffman bzw. Entropiekodierung dafür überhaupt geeignet?

Außerdem ist das Ausgangssignal fester Länge (N downto 0), wie bring ich 
dem ganzen ein kürzeres Codewort bei? Ansatz: Könnte ein Fifo nehmen und 
die Länge mit übergeben, aber wann und wie schick ich das dann ab?

Vielleicht fällt ja jemandem etwas dazu ein. Danke schonmal.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Mame (Gast)

>Ich möchte Huffman in Hardware implementieren (auf einem FPGA mittels
>VHDL). Das Ergebnis soll mit möglichst niedriger konstanter Bitrate
>übertragen werden und wieder dekodiert.

Fein.

>Huffman erzeugt jeden Takt Codewörter unterschiedlicher Länge, z.B. 0 im
>besten (und wahrscheinlichsten) Fall und 111110 im schlechtesten
>(unwahrscheinlichen).

Ja.

>Um meine Bandbreite zur Übertragung festzulegen, müsste ich ja trotzdem
>vom schlechtesten Fall ausgehen,

Jain.

> also für jedes Codewort die längste
>Zeit zur Übertragung annehmen, was also keinen Vorteil für die
>Bandbreite bringt, oder?

Ja.

>Mein Ziel ist allerdings, die bit/s so niedrig wie möglich zu halten,
>ist Huffman bzw. Entropiekodierung dafür überhaupt geeignet?

Kann sein.

>Außerdem ist das Ausgangssignal fester Länge (N downto 0), wie bring ich
>dem ganzen ein kürzeres Codewort bei?

Seriell.

> Ansatz: Könnte ein Fifo nehmen und
>die Länge mit übergeben, aber wann und wie schick ich das dann ab?

Du musst dir sowieso einen Art Blockübertragung ausdenken. Einfach 
Codeworte übertragen is bei Huffmann sinnlos. Man könnte z.B. mit 8B10B 
arbeiten, mit den COMMA Symbolen markiert man Anfang und Ende des 
Datenblocks sowie die Codetabellen.

MFg
Falk

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Angenommen, Sender und Empfänger verfügen bereits über die
Huffman-Tabelle, dann wird z.B. per FIFO blockweise übertragen.
Dazu wird einfach im Sender jedes Zeichen umgewandelt, in den
Buffer (z.B. FIFO) gepumpt und überlauf abgefragt. Falls Buffer
hinreichend voll ist (z.B. bei Blockübertragung n Bits), werden
die Bits übertragen und aus dem Buffer entfernt. Der Empfänger geht
genau umgekehrt vor: Er füllt empfangene Bits in einen FIFO und
entfernt vollständig empfangene Zeichen (zu erkennen anhand der
Prefix-Codierung), setzt sie per Tabelle um. Die Übertragung
zwischen Sender und Empfänger kann dazu unabhängig vom Alphabet
gewählt werden, die Übertragungsgeschwindigkeit hängt dann nur
noch von der Bandbreite ab.
Vergessen darf man aber nicht, das aus dem Eingabestream ja noch
die Huffman-Tabelle erzeugt werden und zum Empfänger gesendet
werden muss (O(n*log(n)), was genau genommen auch noch in die 
Übertragungsgeschwindigkeit einfliest.


Gruss,

Jörg

Autor: Kest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich möchte mich hier mal einklinken. Ich habe schon mal mit C und 
anderen Sprachen Huffman gemacht. Allerdings als ich in Hardware alles 
gießen wollte, war ich total unzufrieden, eben wegen der bitweisen 
Übertragung. Man weis ja nicht im Voraus, wie lang das Codeword sein 
wird. So habe ich Bit per Bit übertragen und in einem "Baum" nach dem 
Zeihen dann gesucht.

Kenn jemand von euch einen Ansatz, wie man mit LUTs und anderen Tabellen 
das geschikter machen kann? Also in eine Richtung habe ich mal so 
gemacht: in einer Tabelle waren für jeden Zeichen das Codeword und 
dessen Länge abgespeichert. Dann habe ich alles zusammengesetz und 
übertragen. z.B. so:

A   0110   4
B   001    3
C   100    3
D   11

ABCD: 011000110011

Für die andere Richtung fehlt mir irgendwie ein Ansatz, wie ich das auch 
Blockweise machen könnte. Oder bin ich da wirklich dazu verdammt 
Bitweise auszulesen und in einem Baum zu suchen? Also wie gesagt, im 
Prinzip ;-) weis ich, wie das theoretisch funktioniert, aber ich möchte 
eine optimale Hardwareimplementierung finden :-) Würde mich für jeden 
Tipp und Stoß in die richtige Richtung freuen.

Grüße,
Kest

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Kest (Gast)

>Kenn jemand von euch einen Ansatz, wie man mit LUTs und anderen Tabellen
>das geschikter machen kann?

Etwa so vielleicht.

In einer grossen LUT, sinnvollerweise BRAM, speichert man seine 
Codewörter. Die Adressierung erfolgt direkt per Huffmann-Codes. Dabei 
bleiben zwar viele Speicherstellen ungenutzt, ist aber egal.
Einige Bits (MSBs) nutzt man in jeder Speicherzelle, um die Länge des 
Huffmann-Codeworts zu signalisieren.
Wenn man nun den einlaufenden, seriellen Datenstrom an die Adresse des 
RAMs anlegt, dekodiert der RAM den Inhalt und Länge des Codeworts. Den 
Inhalt kopiert man in den nächsten Speicher, welcher die dekomprimierten 
Daten aufnehmen soll. Mit der Länge weiss man, um wieviele Bits der 
Datenstrom weitergeschoben werden muss. Das macht man sinnvoll mit einem 
Barrelshifter.
Damit kann man pro Takt ein Codewort dekodieren, unabhängig von dessen 
Länge.

MFG
Falk

Autor: Kest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Falk Brunner (falk):

Danke!

> In einer grossen LUT, sinnvollerweise BRAM, speichert man seine
> Codewörter. Die Adressierung erfolgt direkt per Huffmann-Codes. Dabei
> bleiben zwar viele Speicherstellen ungenutzt, ist aber egal.

Genauso habe ich es mir auch überlegt, nur dachte ich, ich wäre zu 
verschwenderisch :-o ;-)

Oh Mann, dann ist es ja wirklich "einfach" :-)

Grüße,
Kest

Autor: Mame (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für die vielen Denkansätze. Allerdings bringen mich einige 
Antworten etwas ins grübeln für mein Vorhaben:
Und zwar soll der Huffman im Rahmen von M-JPEG in Hardware implementiert 
werden. Also JPEG umgesetzt, und das ganze dann mit mehreren Bilder pro 
Sekunde, als Bewegtbild.

Warum überhaupt: Zwischen Encoder und Decoder steht ein begrenzter 
Übertragunskanal zur Verfügung, der 24-bit-RGB Bilder nicht schnell 
genug schafft. Daher mein Gedanke: Kompression. Der Kanal schafft etwa 
ein Drittel des für RGB-Übertragung benötigten Durchsatzes, also 
Kompression mindestens um 2/3. Generell mit JPEG ja kein Problem denkt 
man.

Was dabei allerdings das Problem ist, sind nun diese unterschiedlich 
langen Codewörter bei Huffman bzw. auch bei Lauflängencodierung.
In Software ist es ja kein Problem, wenn die Datei unterschiedlich groß 
bzw. ein Bildwert innerhalb der Datei mal etwas größer ist, in Hardware 
hierfür schon.

Minimalbeispiel (alle anderen Algorithmen von JPEG vernachlässigt außer 
Entropiecodierung):
Ein Bild hat 4 9-bit Grauwerte (sehr kleines Bild ;-) ), d.h. ein Bild 
hat original 36 Bit. Es sollen 10 Bilder/sec auf einem Kanal übertragen 
werden, der 120 bit/sec schafft. Also genau ein Drittel des notwendigen, 
um das Orignal zu übertragen. Pro Bild stehen also 12 Bit zur Verfügung. 
Die Huffman-Tabellen sind Sender und Empfänger bekannt.

1. Fall: Alle Werte eines Bildes bekommen Huffman best-case (00):
00.00.00.00.
Damit hat ein Bild 8 Bit, Kompression um 1/4, Ziel erreicht.

2. Fall: Alle Werte eines Bildes bekommen Huffman worst-case (11111110):
11111110.11111110.11111110.11111110
Keine Kompression, bei längerem Huffman-Wort sogar Vergrößerung.

Dieser worst-case ist wie gesagt für eine Software-Umsetzung kein 
Problem, jpeg-Datei größer, aber in Hardware kann ich das nicht mehr in 
die 12 Bit packen, die mir pro Bild zur Verfügung stehen. Und vom 
worst-case muss ich ja ausgehen, denn was mach ich wenn meine 12 Bit mal 
nicht ausreichen?
Anders herum betrachtet, wenn mein Kanal von der Übertragungskapazität 
an den worst case angepasst wäre, würde er größtenteils nicht 
ausgelastet sein. Außerdem macht das die ganze Huffman-Codierung 
sinnlos, wenn ich eh immer die längsten Codewörter übertragen könnte und 
die sich Mühe gibt weniger Bits zu erzeugen.

Genauso bei der Lauflängencodierung, im besten Fall stehen viele Nullen 
hintereinander und können kürzer ausgedrückt werden, im schlechtesten 
Fall muss ich alle Werte übertragen.

Ich habe mir dies so allein in meinem Kämmerlein überlegt und möchte 
eigentlich nur wissen, ob ich hier einen Denkfehler hab oder ob die 
Entropie- bzw. Lauflängencodierung für diesen Anwendungsfall einfach 
nicht geeignet ist.

Was meint ihr? Danke für Antworten.

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Mame (Gast)

>Kompression mindestens um 2/3. Generell mit JPEG ja kein Problem denkt
>man.

Naja.

>Was dabei allerdings das Problem ist, sind nun diese unterschiedlich
>langen Codewörter bei Huffman bzw. auch bei Lauflängencodierung.

Warum?

>In Software ist es ja kein Problem, wenn die Datei unterschiedlich groß
>bzw. ein Bildwert innerhalb der Datei mal etwas größer ist, in Hardware
>hierfür schon.

Nöö, du denkst viel zu starr mit fester Bitrate.

>Keine Kompression, bei längerem Huffman-Wort sogar Vergrößerung.

Kann passieren, wenn gleich sehr unwahrscheinlich.

>Dieser worst-case ist wie gesagt für eine Software-Umsetzung kein
>Problem, jpeg-Datei größer, aber in Hardware kann ich das nicht mehr in
>die 12 Bit packen, die mir pro Bild zur Verfügung stehen.

Das Zeuberwort heisst FIFO. Der puffert dir Spitzen im 
Datendurchsatz weg.

>Ich habe mir dies so allein in meinem Kämmerlein überlegt und möchte
>eigentlich nur wissen, ob ich hier einen Denkfehler hab oder ob die
>Entropie- bzw. Lauflängencodierung für diesen Anwendungsfall einfach
>nicht geeignet ist.

Du hast einen Denkfehler. Siehe oben.

MFg
Falk

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ich habe mir dies so allein in meinem Kämmerlein überlegt und möchte
> eigentlich nur wissen, ob ich hier einen Denkfehler hab

Hast du. Dein Kanal muss genug Durchsatz haben, um die gewünschten 
Informationen zu übertragen. Verlustlose Kompression reduziert die größe 
des typischen Falls auf Kosten der größe des seltenen Falls, aber 
niemals die Größe in allen Fällen.

Ohne Information darüber, welche Fälle typisch bzw. untypisch sind, 
bringt verlustlose Kompression dich keinen Schritt weiter.

Wenn die Bilder prinzipiell mehr Information enthalten als nötig, kannst 
du verlustbehaftete Kompression anwenden (d.h. unwichtige Details 
weglassen; was genau unwichtig ist hängt von der Anwendung ab).

Autor: Kest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Mame (Gast):

wenn Du nur 4 Pixel pro Bild hast (4*9 Bit), dann wirst Du auf keinem 
Fall:

> 2. Fall: Alle Werte eines Bildes bekommen Huffman worst-case
> (11111110): 11111110.11111110.11111110.11111110

haben. Ich verstehe nicht, wie Du auf 11111110 kommst.

Mal was anderes: wenn Du nur auf 2/3 kommen möchtest, dann würde ich 
nicht JPEG nehmen, sondern was "einfacheres", "verlustbehaftetes".

Grüße,
Kest

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]
  • [vhdl]VHDL-Code[/vhdl]
  • [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.