Hallo! Vielleicht habt ihr ja einen Tipp für mich, wonach ich suchen sollte. Ich brauche für eine AVR Datenkommunikation demnächst einen Komprimieralgorithmus, der natürlich auch für einen AVR geeignet sein sollte. Komprimiert werden sollen Blöcke von einer Länge von wenigen Byte bis zu Größenordnungen von kB. Der Inhalt dieser Blöcke ist hauptsächlich Text, also nur eine Untermenge der ASCII Tabelle. Darauf beschränken würde ich es allerdings nicht wollen. Was kann man dafür am besten nehmen? Grüße!
Gast
#564790
Es gibt da Verschiedenes. Fuer kleine Blockgroessen ist allerdings nichts. Das beste, das ich mal antraf war ein Entropiekompressor der hat die Codierungstabelle dynamisch angepasst, dh waehrend dem Vorgang. Der musste auch keine Tabelle vorneweg uebermitteln.
Gast
#564796
Schau mal unter http://www.dspguide.com/pdfbook.htm da gibts auch ein Kapitel zum Thema Komprimierung. Ist zwar alles auf Englisch aber sehr gut beschrieben, vorallem muss man vorher nicht Mathe studiert haben ums zu verstehen. Grüße A_Bu
Hi! Ja, da habe ich mich gerade mal erkundingt. Also der Huffman-Code klingt ja sehr interessant für diesen Zweck. Mit einer statischen Tabelle käme man da ja mit relativ wenig Arbeitsspeicher aus. Vielleicht ist eine Vorwärtsdynamik später ja auch noch machbar. Der LZW scheint ja auszuscheiden, da er ja allein eine Tabelle mit 4096 Einträgen besitzt. So groß ist ja der komplette RAM meines AVR, das ginge ja gar nicht. Scheinbar auch zu schwer zu implementieren. Gibt es bereits ferige Implementiereungen für Huffman speziell auf dem AVR oder einfach Quellen für PC nutzen? Grüße!
Guten Tag, eine kleine Nachfrage was ist das eigentlich zu lösenden Problem - oder geht es nur akademisch um eine Komprimierung an sich -und wie steht es einfach mit RLE? Ahoi D.
Hi RLE funktioniert bei Text nicht wirklich gut. Für einen AVR der Text komprimieren soll würd ich auch einen statischen Huffman vorschlagen. Matthias
Gast
#565003
Hallo! Um was fuer Texte handelt es sich überhaupt ? Muss es wirklich ein universelles Komprimierungsverfahren sein ? Wenn der Text z.B. nur Maschinenbefehle oder Messwerte in Klartext enthält bringt es mehr den Text zu Parsen und in einen Binaercode zu wandeln. mfg, Bjoern
Hi! Getreu nach dem Prinzip häufiges soll wenig Bitlänge, weniger häufiges darf mehr erzeugen, werden Messwerte und andere häufige Parameter bereits binär übertragen und müssen nicht zusätzlich kodiert werden. Da habe ich die Redundanz durch das Modell quasi schon so gut wie entfernt. Mein Projekt besitzt eine serielle Konsole, die quasi zweigeteilt ist. Ich reserviere ein ASCII-Zeichen für meine Verwendung, welches auf einen "binären" Modus umschaltet. Die Rückschaltung auf den üblichen Textmodus erfolgt aufgrund einer bekannten Datenlänge im binären Modus. Dadurch kann im binären Modus jedes Zeichen benutzt werden. Binär wären hierbei die Messwerte und andere häufige Übertragungen. Text ist dann eine normale Konsole mit Befehlsannahme und ausgabe. Die Antworten auf die Befehle sind alle in dt. Sprache verfasst. Diese Konsole mit ihren zwei Funktionen soll nun so wie sie ist verpackt und über Funk verschickt werden. Entweder über GPRS oder einen einfachen Sender/Empfänger. Die Sicherung des Bitstroms im letzteren Fall sollte nicht Gegenstand der Komprimierung werden. Die Datenverbindung ist somit zeit- und kostenintensiv. Der Punkt, der mich zu einer Komprimierung veranlasst. Der binäre Teil wird also einfach so wie er ist verschickt. Der Textteil vorher mit Huffman kodiert. Den könnte ich auch auf die eigentlichen 128 ASCII-Zeichen beschränken. Es sei denn, jemand hat eine bessere Idee für die Realisierung. Aber so scheint mir das z.Z. sehr angebracht, weil die Senderoutinen über uart oder durch die Luft bis auf die Hardwareebene fast identisch sind. Mir fällt beim Schreiben auf, das das mit dem reservierten Zeichen nicht funktioniert, weil Huffman es einbauen könnte. Aber dann könnte ich statt dessen alle Übertragungen in Pakete packen, die ich ausreichend frankiere. Dann ist am Header ersichtlich, was drin ist und für GPRS auch schon vorbereitet. Ein Computerprogramm, welches über ttyS0 eine Huffman-kodierung versteht müsste ich dann wohl sowieso noch schreiben. Grüße!
>ASCII .. also 7 Bit im Befehlsmodus - das lässt mich sofort an Fernschreiberkodierung denken - also mit einer definierten 8. Bit-Seqeunz toggeln >Binärmodus Was wird denn in welchem Wertebereich übertragen >..verschickt werden. Entweder über GPRS oder einen einfachen >Sender/Empfänger.... Die Datenverbindung ist somit >zeit- und kostenintensiv. Der Punkt, der mich zu einer >Komprimierung veranlasst. ich frage nocn mal nach - es erfolgt eine Rekodierung Befehle/Antworten via Hashtable(?) was soll da noch verkürzt werden? AHoi D.
Nein, keine Umkodierung in Befehle/Antworten. Zunächst ist der Textteil eine Befehlskonsole, wie man sie von DOS oder LINUX her kennt mit einfacher Texteingabe und Textausgabe (nur ein bißchen mehr gepuffert). Deshalb die Komprimierung mit Huffman. Nach und nach werde ich natürlich immer mehr Befehle binär gestalten, bis im Idealfall alles paketorientiert binär abläuft. Das ist jedoch eine Frage der Zeit, die ich in das Projekt stecken kann und vorallem an welcher Stelle. Vorerst halt nur für die frequentierteren Pakete existiert halt ein genauer Aufbau. Sprich bit0 bis n hat die und die Funktion usw. Das betrifft jedoch nicht meine ursrüngliche Frage. Die zielte nur auf den eigentlichen Textteil ab, der eben nicht nach diesem Frage/Antwort-Prinzip arbeitet. Da habe ich auch noch die Frage: Gibt es statistische Auswertungen zur dt. Sprache, in denen ich die Häufigkeit der Buchstaben ersehe? Wäre ja eine gute Grundlage. Mit Fernschreiberkodierung verstehe ich nicht, was du damit meinst. Kannst du das genauer ausführen? Ich habe dazu nichts gefunden.
Sind das frei formulierbare Texte, oder ist die Menge der möglichen Texte schon vorab bekannt?
Hehe, guter Ansatz. daran habe ich ja noch gar nicht gedacht. Natürlich ist die Menge der Texte vom MC her beschränkt durch die Stringkonstanten. Dann könnte man die jeweils als Zahl übertragen. Natürlich müssen dann eventuelle Ziffern, die Variablen sind 1:1 übertragen werden. Die Kommandoeingabe wird jedoch nicht so betrachtet werden können. Z.B.: print Hallo Welt!, um "Hallo Welt!" auf ein LCD zu schreiben.
Mit so einem maßgeschneiderten Kompressionssystem für eine endliche Menge Texte erreichst Du eine Kompressionsrate, von der man bei Benutzung allgmeiner Kompressionsalgorithmen, wie lzh, bz2 und wie sie alle heißen, nur träumen kann.
man kann die Tabelle ja auch im Flash ablegen, muss nicht ins SRAM, Nachteil ist halt das die Tabelle nicht mehr wärend dem Betrieb zu ändern ist. bzw. nur über das Neuprogrammieren des AVRs oder Bootloader zu bewerkstelligen ist. Und Flash haben Sie inzwischen ja alle genug.
Servus, ja das was UhUhU vorschlägt, meinte ich schon vorher mit Hashtable - der Controller brauchte die Texte doch nur wenn er sie selber wieder anzeigen soll ;-). Fernschreiber (http://de.wikipedia.org/wiki/Baudot-Code)- flappsig gesagt ein 5-Bit-Code hätte also die Möglichkeit mit 5-BIT (quasie Untermenge im heutigen) ASCII zu verwenden und dann noch 2³-1 Kominationen zum Toggeln von Zuatzmodi - oder anders 40 Bit Frame - einfach mal so als Rechenbeispiel bei 8-Bit/Zeichen können 5 Zeichen übermittelt werden bei 5-Bis/zeichen dann schon 8 je Datgrammen zu den Binärdaten - sind das kontinierliche Werte - freie, fortlaufende Messungen aquidistante Werte - alle x s ein Messewert Trendhysteresewerte - nur bei Überschreitung eines bestimmten Deltas wwerden Daten übertragen (+ regelmässiges Ping) Aber schreib doch einfach mal - meine Schaltung misst das und das und soll das und das machen und dorthin das und das übertragen. Da ist ja scheinbar auch ein GSM-Modem verbaut. AHoi D.