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.
@ 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
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
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
@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
@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
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.
@ 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
> 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).
@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
Thread beobachten
Seitenaufteilung abschaltenBitte 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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.