fast universal compression scheme and its implementation in VHDL

Die könnten im Erstsemester Kurse abhalten "wie benutze ich das Internet".

• Anfragen an newsgroups auf 1-2 relevante Gruppen beschränken
• die jeweilige Sprache verwenden.

Wenn der Algorithmus komplexer ist, kann ein Mikroprozessor die günstigere Lösung sein. Maximale Geschwindigeit bei unsinnigen Kosten ist oft wirtschaftlich nicht relevant. Das Komprssionsverfahren Verzögerung bewirken schränkt ihre Vorteile oft ein.

Modems in den 80er Jahren die Datenkompression mit begrenzten Resourcen ( 8051 Controller, 8kSRAM ) machten verwendeten LZW in der Variante LZW-BT ( Standard V42bis ).

Aus patentrechtlichen Gründen die für LZW heute nichtmehr ( für LZW-BT eventuell schon noch ) relevant sind gab es ein einfacheres Verfahren ( MNP ) das zwar nicht ganz so effizient aber patentfrei war.

Eine neuere patentierte Standardisierung ( V44 ) basiert auf LZJH.

" John Border Hughes Network Systems holds patents on the LZJH algorithm. Licenses are available on a fair and reasonable basis. Source code is also available at no additional cost. For information contact: Hughes Network Systems. Additional information can be obtained from either

Inwieweit das praktische Verbreitung gefunden hat weiss ich nicht, ich hab mir wegen des ( noch nicht ablaufenden ) Patents den Code auch nicht angesehen. Für reine Hobby/Forschungsarbeiten sind Patente natürlich kein Hindernis.

Aus Copyrightgründen wohl nicht. Es gibt bei sehr alten Büchern wo Urheberrecht oft nichtmehr greift Fotokopien gebunden a la books-on-demand. Das Preis/Leistungsverhältnis ist jedoch so mau dass ein zerlesenes Orginal besser und billiger ist.

Gut lesbar: Held "Data and Image Compression" Wiley 1996 Das hat Verbreitung und ist eventuell antiquarisch noch zu finden. Enthält LZW, LZW-BT. Für LZW gibt es auch eine Beschreibung auf

MfG JRD

Jens Mander schrieb:

ng

its

Hallo,

wenn man nichts =FCber die Eigenschaften der zu komprimierenden Daten=20 wei=DF, dann kann man auch nichts =FCber die theoretischen Grenzen der=20 Kompression aussagen.

Bye

Wenn man Verfahren implementiert hat: Best-case Test a la "File enthält nur Bits 0 bzw nur Bits 1" hat wenig Nährwert. Worst-case Test ist sinnvoller: Zufallszahlen einfüttern. Komprimierbar ist dann praktisch nichts. Mit etwas Pech wird der Echtzeit-Kompressor overhead zufügen und das File wird leicht expandiert statt komprimiert.

MfG JRD

Die Wahl des "richtigen" Algorithmus wird ganz wesentlich von den zu erwartenden Daten bestimmt. Für beliebige Daten schneiden statistische Verfahren (Huffmann & Co.) eher schlecht ab. Wörterbuch-basierte Verfahren wie LZ können besser sein, lassen sich in Hardware aber nur eingeschränkt implementieren. Alle etablierten Formate verwenden daher mehrere Algorithmen in Folge (etwa: RLE -> LZ -> Huffmann)

Ganz allgemein gilt für alle Verfahren, daß sie besser komprimieren, wenn sie mehr Daten (größere Blöcke) zur Verfügung haben. Das macht eine Hardware-Implementierung aber recht aufwendig. Spezielle Algo- rithmen für niedrigen Speicherbedarf (insbesondere beim Kompressor) erreichen deswegen nur geringe Kompressionsraten.

Eine Software Implementierung eines solchen low-memory--near-real-time- Kompressors findest du hier:

Synchroner Betrieb ist ohnehin eine schlechte Idee. Aus theoretischen Gründen [1] gibt es für jedes Kompressionsverfahren Eingabedaten, die nach der Kompression *mehr* Platz brauchen als vorher. Für ein wirklich universelles Gerät müßten also sowohl im Eingang als auch im Ausgang FIFOs vorgesehen werden. Und streng genommen müßten diese FIFOs unendlich groß sein um einen Überlauf sicher zu vermeiden.

XL

Have a look at bzip2: bzip2 compresses files using the Burrows-Wheeler block sorting text compression algorithm, and Huffman coding. Compression is generally considerably better than that achieved by more conventional LZ77/LZ78-based compressors, and approaches the performance of the PPM family of statistical compressors.

It's the most effective I have stumbled upon in terms of bytes saved so far. I have however not made any deep research into this ;) It can however take considerble amount of processor time. Thus a good candidate for hardware implementation.

I too am interested in this and I would be interested to see results of Jens findings and work in this area if he decides to work on it and publish it.

Josh

"Rafael Deliano" schrieb im Newsbeitrag news: snipped-for-privacy@t-online.de...

Ohje. Wieder mal Schwarz-Weiss Malerei. Wenn man das so hört könnte man glauben, dass (Online)Kompression alles nur Mist ist und nie funktioniert. Du warst irgendwie schon wesentlich konstruktiver. :-(

MfG Falk

P.S. Der OP hat geschrieben, er wäre Student und interessiert sich demzufolge zu Studienzwecken für VHDL & Kompressionsverfahren. Die direkte Anwendung in einem komerziellen Produkt ist davon weit weg.

"Axel Schwenke" schrieb im Newsbeitrag news: snipped-for-privacy@idefix.xl.local...

Man kann auch relativ grosse RAMs ans FPGA hängen (für wenig Geld) Heutige FPGAs haben schon recht ordentlich interne RAMS.

Ja und? Wo ist das Problem?

Quark.

Quark^2. Du bist theoretischer Informatiker?

MFG Falk

Hallo Falk,

Quark gibts bei Aldi und der Gute hat einfach recht, wie sein indirekter Beweis auch allen offenbart, die das Hirn nicht nur auf dem Kopf tragen, damit es nicht in den Hals regnet.

Ein Packer für streamingdaten kann nur sinn machen, wenn die Art der Daten bekannt sind z.B. Videodaten etc. Dann geht das. Sollen ALLE möglichen Daten durch, dann muss man schon mit hochkomprimierten Daten rechnen, die quasi nicht mehr zu komprimieren sind, die werden durch erneutes komprimieren größer -> Datenrate müsste steigen, was er ja vermeiden wollte, bzw nicht hat. -> Datenstau und sehr bald Überlauf. Du brauchst da nur mal ne CD voll gepackte Installationsdateien drüberschieben und sehr schnell weisst Du, dass auch ein paar MB RAM das Problem nicht beheben.

Marte

"Marte Schwarz" schrieb im Newsbeitrag news:d8ci8v$vp1$ snipped-for-privacy@news2.rz.uni-karlsruhe.de...

Kompressionsverfahren,

Stimmt, Quark gibts bei Aldi. Aber auch Sülze, wie man mal wieder sieht/liest. Man lese sich obigen "Beweis" nochmal gaaanz langsam durch. Merkt er was? Es gibt kein Kompressionsverfahren, welches jegliche Daten immer verkleinert. Die Entrophie lässt grüssen.

Wer im Glashaus sitzt, sollte sich im Dunkeln ausziehen ;-)

Daten

Jedes technische Gerät hat seine Einsatzdefinition und Spezifikation. So auch Packer für Streamingdaten. Wer mit nem Teelöffel versucht nen Tunnel unter dem Ärmelkanal zu graben ist selber Schuld.

voll

Richtig, doch vor dem Überlauf setzt hoffentlich das "Hirn" der Anwendung ein. Entweder es handelt sich um paketorientierte Übertragung ala Ethernet & Co., dann signalisiert der Packer der Datenquelle, mach mal langsam, ich muss erstmal meinen Eingangspuffer wieder leer(er) kriegen. Dann dauerts halt etwas länger, ehe eine WWW-Seite aufgebaut ist oder ein paar Dateien via FTP gezogen sind. Das macht jeder Ethrnet MAC, auch ohne Komprimierung. Ist die Datenquelle nun aber nicht auzubremsen bzw. ein kontinuierlicher Datenfluss wünschenswert (Voice over IP etc.) muss der Algorithmuss wohl oder übel in den sauren Apfel beissen und Daten wegschmeissen. Je nach Fähigkeit der Anwendung solche Aussetzer interpolieren zu können gibts grössere oder kleinere Knackser. Aber gerade bei solchen Sachen kann man recht gut darauf vertrauen, dass die Eingangsdaten gut kompimierbar sind.

Dicke Muskeln (RAM + Prozessor) helfen wenig, wenn das Hirn (die Software) nix taugt. Wie sagte mein Mathelehrer immer (Gott hab ihn selig) "Nur selber Denken macht geistig fett."

MfG Falk

P.S. Irgendwie ist das mal wieder typisch deutsch. Es wird erstmal "ganz klar" lang und breit theoretisch "bewiesen" dass es gar nicht gehen kann, anstatt zu fragen wie es möglicherweise gehen kann. Gute Nacht, Deutschland.

War schon anno V42bis umstritten: Packen auf dem PC bringt mehr. Applikation auf PC weis was sie loss-less und was lossy komprimieren darf. PC hat billigere Rechenleistung, billigeres RAM. Hat ziemlich lasche Echtzeitanforderungen und kann deshalb bessere Algorithmen verwenden. Konzentratoren/Multiplexer in den 80ern bei Endgeräten die nicht selber komprimierten machten Sinn. Wenn Endgeräte heute komprimieren oder gar noch Pakete verschlüsseln ist nichtmehr viel zu holen. Das wäre aber eben heute die Anwendung für FPGA.

VHDL & FPGAs scheint Mode zu sein. Besonders bei Hobbyisten & Studenten. Selbst wenn man sich als hypothetische Anwendung z.B. ein Glasfaser-Seekabel vorstellt das von sowas profitieren könnte: Glasfaser hat manchmal so hohe Bruttobitrate daß bei Fehlersicherungsverfahren primitive Verfahren aus den

MfG JRD

"Rafael Deliano" schrieb im Newsbeitrag news: snipped-for-privacy@t-online.de...

Ja. Das heisst aber noch lange nicht, dass der Ansatz der Echtzeit-Datenkompression falsch ist. Auch das FPGA kann dann quasi die Kompression übernehmen, sozusagen als Coprozessor. JAAA, um einem 3GHz Pentium/AMD Komkurrenz zu machen braucht schon ein bissel gösseres FPGA von jemandem programmiert der weiss was er tut. Aber nochmal, es geht hier in erster Linie um Studienzwecke, die können (und müssen) manchmal einen gewissen Abstand zur direkten Praxis haben.

Why not. Bist du nicht einer von denen, die für praxisbezogenen Lehrinhalte plädieren? FPGAs und VHDL sind SEHR praxisbezogen.

Naja, bei 40 Gbit/s gibts auch schon FEC, die ist sicher nicht so gaaanz einfach. Ich kenne keine Gbit-Übertragung die mit Parity oder ähnlichen Scherzen arbeitet.

MFG Falk

P.S. Und trotzdem gibt TONNENWEISE Anwendungen für Echtzeitkompression. Camcorder, Mobiltelephone, etc.

It is again surpassed by 7-zip

Again, source code is available.

Thomas

/me wrote

Und? Wo ist nun der Widerspruch zu meiner Aussage? IMNSHO ist obiger Beweis wesentlich einfacher zu verstehen, als Quellenentropie a'la Shannon.

Genau. Statt einer einfachen, allgemeinverständlichen Darlegung bemüht man lieber komplizierte Theorie, um seine geistige Überlegenheit nur recht deutlich herauszustellen.

Und BTW habe ich nirgendwo geschrieben, daß das nicht geht, sondern lediglich, daß synchrone Ein-/Ausgabe bei Kompressoren nicht ohne Probleme ist. Insbesondere kann man auch nicht davon ausgehen, daß die Ausgaberate

r=20

,=20

Habt Ihr Euch jetzt ausgetobt? Ich meine, wenn hinterher noch kon- struktive Argumente kommen, und das ist ja bei beiden von Euch der Fall, warum dann erstmal rumgiften?

Daten=20

n Daten=20

Man kann versuchen, die Daten zu analysieren. Das *ideale* Packverfahren kann das eh. Es muss nur noch jemand erfinden.

si=20

=20

bzw nicht=20

Was spricht dagegen, da=DF der Packer zumindest so intelligent ist und er=

- kennt, da=DF die komprimierten Daten gr=F6sser sind (gr=F6sser? mehr!) un= d dann die unkomprimierten schickt? Wenn er 'ideal' ist, bleiben die Daten in dem Fall eh gleich.

D voll=20

Du,=20

Daf=FCr hat das Teil ja sicher ein /DATA_READY Bit, mit dem es der Datenquelle sagen kann, da=DF es nun nicht mehr hinterherkommt. Vollaufenden RAM kann man heutzutage auch fr=FCh genug erkennen und entsprechend reagieren. Ich halte das Projekt eigentlich f=FCr sinnvoll, um viel dran zu lernen. Und wenn es ist, da=DF Streaming- Kompressoren nicht (immer gut) funktionieren :-)

Markus

"Axel Schwenke" schrieb im Newsbeitrag news: snipped-for-privacy@idefix.xl.local...

Kompressionsverfahren,

mehrfache

offen-

existieren.

BEWEIS??? Das ist alles andere als ein Beweis. Ein dahergeplappertes Zeugs. Nicht mal pseudowissenschaftlich, einfach nur Quark.

Ahja, wozu fundiertes Fachwissen wenn Hausfrauenlogik auch Quantenphysik erklären kann. Dolle Show. :-(

Das ist keine losless compression. Es gibt tonnenweise Literatur in IEEE Transactions on Consumer Electronics von Japanern/Taiwanern wie man MPEG/JPEG in Hardware wurstelt. Wenn er nicht gerade bei Micronas werkelt wird er in Europa davon nicht berührt, der Zug ist lange abgefahren.

Daran wirds an deutschen Unis gewiss nicht mangeln. Wenn er aber nicht Akademiologe werden will ...

Es handelt sich hier um jemand der sich ohne sich die Algorithmen angesehen zu haben für FPGAs entschieden hat weil das wohl derzeit "cool" ist. Praxisbezug hat auch was mit Abschätzung wo das wohl in Produkt anwendbar wäre und was eine kosteneffektive Lösung für das Problem ist zu tun. Unabhängig von den technischen Begrenzungen des FPGAs-Bausteins bezüglich Pins, äquivalenten Gates usw. die ihn bald zwicken werden, glaube ich auch nicht daß man solche Algorithmen ohne Hierarchie im Design zum Laufen bringt. D.h. es wird wohl sowas wie ein mikrocodierter Prozessor. Der muß dann dokumentiert werden, braucht debugging-Hilfsmittel wie jeder andere Controller auch. Nur daß das der Anwender dann alles selber wursteln muß.

Historisches Beispiel für "Algorithmus-durch-die-Hardware-prügeln" wäre der Rechner von AEG für Klarschriftenleser für Adressen auf Briefen von ca. 1977. Basierte auf Schottky Bit-Slice von Intel mit 180nsec Befehlszyklus ( Slice selber war 70nsec, PROMs 50nsec ), 16 Bit Datenwort,

MfG JRD

"Rafael Deliano" schrieb im Newsbeitrag news: snipped-for-privacy@t-online.de...

;-)

Du willst es nicht verstehen? Er ist KEIN Entwickler, er ist STUDENT! Da darf man auch mal rumwurstlen. Und wenn am Ende die Erkenntnis steht, dass es so nicht sonderlich gut geht. Das kann man bisweilen NICHT durch predigen vermitteln, man muss einfach mal selber auf die Nase fallen. Lernen durch Schmerz.

Alles schön und gut, und aus Entwicklersicht sicher ein eher trauriges Kapitel. Aber nochmal, das hat mit der eigentlichen Anfrage wenig zu tun.

MFG Falk

Im weiteren Sinne der Projektabwicklung schon. Spätestens wenn er Diplomarbeit macht sollte er technische Komplexität, Zeitabschätzung in den Griff bekommen. Diplomarbeit als Papiertiger kann man noch schöndoktern. Wenn man danach in der Industrie Entwicklungen macht, werden Fehler ( und seien es nur verpaßte Termine ) irgendjemand echtes Geld kosten.

Lernen durch eigene Fehler ist sicher möglich und meist nicht vermeidbar aber nicht effizient. Ich wühle mich deshalb durch die Literatur um die Fehler anderer Leute nicht selber nochmal zu machen. Ist billiger.

MfG JRD