Hi, gibt es eine fertigen Algorithmus, der sagen wir mal ein Array aus 1000 8-bit Werten komprimiert und das so dass es auf einem Atmega in Echtzeit läuft? Also 1000 Werte übergeben und 900 oder so zurückbekommen, die dann natürlich auch wieder decodiert werden können in die 1000 ursprünglichen Werte. Ich hab davon nicht den hauch einer Ahnung, würde so was aber gerne nutzen und kann mir gut vorstellen, das es in der heutigen "fertig code" Zeit alla Arduino so was zuhauf gibt.
es kommt auf die Werte an. Es gibt auch werte die sich überhaupt nicht komprimieren lassen.
Dshing Sung schrieb: > Also 1000 Werte übergeben und 900 oder so zurückbekommen, die dann > natürlich auch wieder decodiert werden können in die 1000 ursprünglichen > Werte. Selbstverständlich geht das. Brauchst nur ein kleines Hilfsarray mit exact 1000 Keys.
Und wie geht das mit dem Hilfsarray? Es müssen auch nicht unbedingt 900 oder konstant viele sein.
Dshing Sung schrieb: > und das so dass es auf einem Atmega in Echtzeit läuft? Was verstehst du unter "Echtzeit"?
Dshing Sung schrieb: > Ich hab davon nicht den hauch einer Ahnung, würde so was aber gerne > nutzen und kann mir gut vorstellen, das es in der heutigen "fertig code" > Zeit alla Arduino so was zuhauf gibt. Könntest du dir auch vorstellen, selber mal die Suchmaschine deiner Wahl zu bemühen. Die würden dir Dinge wie http://stackoverflow.com/questions/1606102/arduino-lightweight-compression-algorithm-to-store-data-in-eeprom http://forum.arduino.cc/index.php/topic,39436.0.html o.ä. begegnen. Und die Fragen sind die gleichen, die dir hier auch schon gestellt wurden.
Dshing Sung schrieb: > Und wie geht das mit dem Hilfsarray? > Es müssen auch nicht unbedingt 900 oder konstant viele sein. Sorry, war nicht ernst gemeint. Aber 8bit Werte in Echtzeit komprimieren geht gar nicht. Du kannst höchstens versuchen, die Differenz zwischen 2 aufeinanderfolgenden Bytes zu speichern. Wenn die Differenz nicht größer als: 16 - 4Bit genügen 32 - 5bit 64 - 6bit 128 - 7bit Ob sich das allerdings lohnt (außer für 4bit) ist fraglich. Und auch für 4bit must du zwei Werte abwarten, bei 5bit müssen schon 8 Werte abgewartet werden, also keine Echtzeit. Allerdings kann ein fertiges Array mit 1000 Bytes komprimiert werden. Wie hoch die Kompression wird, hängt sehr stark von der verwendeten Methode und Werten die in diesem Array vorkommen. Es lohnt sich aber mit Sicherheit nicht, benötigter RAM, Programmcode und Ausführungzeit stehen in keinem Verhältnis zur erzielten Einsparung. Wenn überhaupt etwas eingespart wird...
Marc Vesely schrieb: > Aber 8bit Werte in Echtzeit komprimieren geht gar nicht. Naja, ich kenne den Begriff "Echtzeit" so, das die Daten spätestens dann zur Verfügung stehen müssen wenn sie benötigt werden. Wann immer das in diesem Fall sein mag. Insofern ginge das an und für sich schon. Dshing, wie schon von Peter II gesagt, kommt es (für eine erfolgreiche Kompression) bei der Wahl des Kompressionsalgorithmuses sehr darauf an zu wissen wie die Daten beschaffen sind. Pauschal würde ich vorschlagen: Nimm dir die Zeit und google nach LZW und Arithmetic Coder. Beides sind gute Verfahren die sich für deinen Zweck eignen könnten. Sie sind leicht zu verstehen und mit recht wenig Code zu implementieren (oder von mir aus ergoogle dir auch Quellcodes dazu). Wichtig wäre aber, das du dir mal durchliest wie sie arbeiten, damit du entscheiden kannst welches von beiden Verfahren für deine konkreten Daten tauglicher ist. PS: Falls LZW zu langsam für deine Aufgabe ist würden sich freilich auch andere LZ-Varianten (oder überhaupt andere Algorithmen) anbieten, die man im Voraus entsprechend maßschneidern könnte. Aber dafür wäre halt entsprechendes Wissen über die Daten nötig. Wenn du lustig bist kannst du da ruhig mal weiter forschen, viele Kompressionsverfahren sind im Grunde ziemlich einsichtig.
Michael H. schrieb: > Dshing, wie schon von Peter II gesagt, kommt es (für eine erfolgreiche > Kompression) bei der Wahl des Kompressionsalgorithmuses sehr darauf an > zu wissen wie die Daten beschaffen sind. Pauschal würde ich vorschlagen: > Nimm dir die Zeit und google nach LZW und Arithmetic Coder. Beides sind > gute Verfahren die sich für deinen Zweck eignen könnten. Pauschal würde ich vorschlagen: Lass es sein, es lohnt sich nicht. Was Michael hier schreibt, ist sowieso nur googlewissen. Michael H. schrieb: > Aber dafür wäre halt entsprechendes Wissen über die Daten nötig. Sicher, wenn er im voraus weisst, was für Daten ankommen, dann könnte er vielleicht das Einschreiben in ein Array ganz überspringen und gleich die Daten beim Empfänger ausgeben.
Marc Vesely schrieb: > Lass es sein, es lohnt sich nicht. Was Michael hier schreibt, ist > sowieso nur googlewissen. Lol, ach ja, ist das so? :)) > Michael H. schrieb: >> Aber dafür wäre halt entsprechendes Wissen über die Daten nötig. > Sicher, wenn er im voraus weisst, was für Daten ankommen, dann könnte > er vielleicht das Einschreiben in ein Array ganz überspringen und > gleich die Daten beim Empfänger ausgeben. Soso. Klingt für mich, als könntest du nur zwischen nichts wissen und Allwissenheit unterscheiden. Hmm. Wäre es wohl möglich, das du keinen allzu großen Plan von Datenkompression hast?
Michael H. schrieb: > Allwissenheit unterscheiden. Hmm. Wäre es wohl möglich, das du keinen > allzu großen Plan von Datenkompression hast? Ich glaube eher, du weisst gar nicht wie das alles funktioniert. Ich bin bestimmt kein Experte auf dem Gebiet, lasse mich aber gern belehren wie man zufällige 8bit Werte in Echtzeit komprimiert. Also, leg mal los.
Marc Vesely schrieb: > Ich bin bestimmt kein Experte auf dem Gebiet, lasse mich aber gern > belehren wie man zufällige 8bit Werte in Echtzeit komprimiert. Na, das muss ich dich hoffentlich nicht lehren: Genau gar nicht. Die interessantere Frage wäre jedoch wie du jetzt darauf kommst?! Hat Dshing bereits erklärt das seine Daten zufällig sind? Wenn man per se davon ausgehen müsste das "Daten" zufällig sind, dann hätte es nie einen Algorithmus zur Kompression gegeben. Gibt's aber doch. Daraus kann man was folgern. Aber so wie's aussieht reden wir glaube ich gerade ziemlich aneinander vorbei, wodurch nu' auch niemandem geholfen ist. Ich möchte dir nicht zu nahe treten, halte meinen pauschalen Vorschlag einen AC zu testen aber aufrecht. Wenn du Argumente (ohne willkürliche Hypothesen wie "Daten sind 100% zufällig") nennen möchtest die dagegen sprechen würden sie mich interessieren. (Unabhängig davon willst du aber doch hoffentlich auch nicht behaupten, das dein Vorschlag mit den Differenzen der Stein der Weisen ist. Schon gar nicht für "zufällige Daten". ;-) Aber lass uns unseren Disput mal nicht weiter eskalieren lassen sondern erstmal abwarten ob Dshing noch weitere Infos beiträgt. Deal? :)
Michael H. schrieb: > Hat Dshing bereits erklärt das seine Daten zufällig sind? Genau genommen, hat Dshing noch gar nichts erklärt, außer dass er "sagen wir mal" Blöcke von 1000 Bytes hat. Ohne weitere Infos bleibt das hier Kristallkugelleserei und Stochern im Nebel. Angesichts dessen ist es es wohl wenig lohnend, sich weiter in Allgemeinplätzen zur Datenkompression zu ergehen.
Michael H. schrieb: > Aber lass uns unseren Disput mal nicht weiter eskalieren lassen sondern > erstmal abwarten ob Dshing noch weitere Infos beiträgt. Deal? :) Sure. Aber dass er Sätze wie: 'Wenn fliegen hinter fliegen fliegen, fliegen fliegen fliegen nach' komprimiert, ist kaum anzunehmen. Wenn es völlig zufällige Werte sind, ist eine komprimierung sowieso sinnlos, vor allem bei nur 1000 Werten. Wenn es sich aber um Messwerte handelt, ist die Wahrscheinlichkeit sehr gross, dass diese nicht willkürlich von 0 bis 255 vor- und zurückspringen, sondern in einer ab- oder aufsteigender Kurve deren Wert verändern. Falls dies der Fall sein sollte, kann die Differenz zwischen zwei aufeinanderfolgenden Werten mit weniger bits ausgedrückt werden als mit jeder anderen Methode.
Ok, also ein ganz exakten Einzelfall hab ich jetzt noch gar nicht vorgesehen. Wenn ich es irgendwo nutzen will, dann sind es wahrscheinlich Messwerte, die für eine gewisse Zeit eine gewisse Wahrscheinlichkeit aufweisen mit entsprechender Streuung(Konstanter Messwert), oder zeitlich wiederkehrend eine Wertefolge bilden, die kontinuierlich abweicht (Wechselsignal). Und unter Echtzeit verstehe ich, dass es bei einem Dauerbetrieb nicht zu einem Aufstau der Daten kommt und es für einen Mensch so aussieht/hört/schmeckt/reicht/fühlt, dass es ungefähr im Moment des Entstehens der Daten diese auch in codierter Form gibt. Also die typische Reaktionszeit eines Menschen nicht massiv übersteigt. Z.B ein Tachometer am Auto zeigt Werte, die aus meiner Sicht als Echtzeit zu verstehen sind. Es kommen permanent neue Werte, diese sind aber so aktuell, dass die Zeitverzögerung für den Betrachter keine Rolle spielt, aber dennoch ist eine für die µElektronik gewaltige Zeitverzögerung vorhanden, nämlich die bis ein Rad min. eine Umdrehung vollführt hat. Also LZ bzw LZW und Arithmetic Coder sind die Anhaltspunkte nach den ich Ausschau halten soll, bzw. ich mich schlau machen soll. Danke schon mal dafür :) Wir können aber gerne weiter diskutieren, das macht das Lernen interessanter ;) Mich würde interessieren, warum Zufällige Daten überhaupt nicht komprimierbar sind? Wir können ja auch je vier 8bit Werte zu 32bits zusammen schieben und anders herum. Ich stelle mir dann vor ich betrachte eine matrix aus 1 und 0 und sortiere die so dass sich möglicht viele inseln in dieser Matrix bilden (können auch andere Muster sein die sich gut zusammen fassen lassen) anschließen muss ich die Verschiebungsvorschrifft (mir geistert das Gaussverfahren als Beispiel im Kopf rum) speichern und die sich dann leicht zusammen fassende Matrix und dann kann ich das auch wieder rückgängig machen.
Dshing Sung schrieb: > Also LZ bzw LZW und Arithmetic Coder sind die Anhaltspunkte nach den ich > Ausschau halten soll, bzw. ich mich schlau machen soll. Naja, das sind jetzt auch nicht die Alleskoenner (sowas gibt's leider net), aber bewaehrte Methoden zur verlustfreien Kompression, die man fuer solche Zwecke einsetzen koennte. Neben anderen Methoden. Wenn's Sinn macht. Aber wie schon erwaehnt, pauschal kann man kaum sagen welche Verfahren Sinn machen, das kommt halt sehr auf die Daten (und andere Constraints) an. > Wir können aber gerne weiter diskutieren, das macht das Lernen > interessanter ;) Wenn du dich allgemein in das Thema Datenkompression einlesen moechtest, dann solltest du mit den Klassikern anfangen (RLE, Byte-Pair-Coding, LZ77, Huffman usw.). Die Grundideen dabei sind alle ziemlich simpel, konkrete Implementationen lassen sich weiterentwickeln solange die Phantasie reicht. :) > Mich würde interessieren, warum Zufällige Daten überhaupt nicht > komprimierbar sind? Wir können ja auch je vier 8bit Werte zu 32bits > zusammen schieben und anders herum. Ich stelle mir dann vor ich > betrachte eine matrix aus 1 und 0 und sortiere die so dass sich möglicht > viele inseln in dieser Matrix bilden (können auch andere Muster sein die > sich gut zusammen fassen lassen) anschließen muss ich die > Verschiebungsvorschrifft (mir geistert das Gaussverfahren als Beispiel > im Kopf rum) speichern und die sich dann leicht zusammen fassende Matrix > und dann kann ich das auch wieder rückgängig machen. Da muesstest du jetzt aber noch zeigen das sich die zusammengefasste Matrix + die Abbildungsvorschrift in weniger Bits speichern laessen als die Originaldaten. Und das wird schwierig. Sowas haben schon eine Menge Leute vor dir versucht... Als Faustregel: Wenn du keinen plausiblen Grund benennen kannst warum das fuer eine halbwegs sinnvolle Eingabe kuerzer werden sollte, dann kannst du davon ausgehen, das es auch nicht kuerzer wird. "Kann doch zufaellig sein" zählt nicht als Grund. ;-) Tatsaechlich gibt es da umfangreiche Theorien drueber, das (und warum) sich zufaellige - im Sinne der Datenkompression - Daten eben nicht komprimieren lassen. So als Gedankenanstoss: Ein verlustfreier Kompressor soll ja eine bijektive Abbildung zwischen Eingabe und Ausgabe darstellen. Wenn er nun manche Eingaben von n Bits Laenge auf Ausgaben mit weniger als n Bits abbildet, dann folgt daraus, das er andere Eingaben der Laenge n auf Ausgaben mit mehr als n Bits abbilden muss. Beispiel: Fuer n=2 Bits gibt es insgesamt 4 verschiedene Eingaben. Die koennen wir nicht alle bijektiv auf nur ein Bit abbilden; manche der Ausgaben muessen zwanglaeufig mindestens 3 Bits lang werden (wie sich ja leicht nachzaehlen laesst). Jetzt wissen wir aber, das es verschiedene Kompressionsalgorithmen gibt, die sich jeweils fuer unterschiedliche Daten eignen. Warum sollte es nun nicht fuer alle Arten von Daten irgendwelche Packer geben, welche ihre Eingabe um wenigstens ein Bit verkuerzen koennen? Na, nehmen wir mal an es gaebe sie. Dann koennten wir fuer unsere Daten den passenden Packer auswaehlen, und der macht sie um (wenigstens) 1 Bit kuerzer*. Fuer die gepackten Daten koennten wir aber ebenfalls wieder einen passenden Packer auswaehlen, und der macht sie nochmal um 1 Bit kuerzer. Und fuer die nun doppelt gepackten Daten koennten wir erneut den passenden Packer auswaehlen, und so weiter und so fort. Das machen wir solange wir lustig sind und landen schließlich bei 0 Bits. Fuer alle erdenklichen Ursprungsdaten. Hmm... * zweckmaessigerweise muesste man auch noch in irgendeiner Form mit abspeichern welcher Packer gewaehlt wurde, einfach um fuer die Dekompression den passenden Entpacker waehlen zu koennen. Diese Information benoetigt nun aber ebenfalls Speicherplatz (so minimal er auch sein mag), welchen man mit beruecksichtigen muss. Selbst bei einem "Packer", der als Abbildung nur die Identitaet verwendet werden die Ausgabedaten dadurch schon ein kleines Stueckchen laenger.
Dshing Sung schrieb: > Mich würde interessieren, warum Zufällige Daten überhaupt nicht > komprimierbar sind? Wenn du unter Daten 8bit Werte verstehst und immer noch fragst warum, dann ist ja eine Erklärung überflüssig, da vollkommen nutzlos. > Wir können ja auch je vier 8bit Werte zu 32bits > zusammen schieben und anders herum. Ich stelle mir dann vor ich > betrachte eine matrix aus 1 und 0 und sortiere die so dass sich möglicht > viele inseln in dieser Matrix bilden (können auch andere Muster sein die > sich gut zusammen fassen lassen) anschließen muss ich die > Verschiebungsvorschrifft (mir geistert das Gaussverfahren als Beispiel > im Kopf rum) speichern und die sich dann leicht zusammen fassende Matrix > und dann kann ich das auch wieder rückgängig machen. Man kann vieles machen, ob das auch Sinn hat, ist eine andere Frage. Nach der Logik von Michael und dir kann man auch 1 Byt komprimieren, nur wird damit dein Programm mit Sicherheit länger als die eingesparten bits. Was Michael da schreibt, mag vielleicht für PC und größer gelten, aber für Mikrocontroller ganz bestimmt nicht. Vor allem nicht bei nur 1000 Bytes und nicht bei MEGA. Man muss sich fragen ob es nicht besser wäre, mit kleineren Arrays zu arbeiten, anstatt mit 1000 Bytes. Warum überhaupt 1000 Bytes ? Wenn man mit Mikrocontrollern arbeitet, dann ist oberstes Gebot Geschwindigkeit und kompakter Code. Aber wenn sich jemand unbedingt das Leben schwer machen will, indem er den verkehrten Weg geht - von mir aus. Nur dann halt nicht schreiben, dass das so sein muss, sondern dass das von dir so gewollt ist. 1000 Werte sammeln, dann komprimieren, dekomprimieren, verarbeiten und von Echtzeit reden, das passt irgendwie nicht zusammen... 4 Mal 250 Werte bearbeiten oder 1 Mal 1000 ist vom Ergebnis her dasselbe, aber nicht von der Bearbeitungszeit, Speicher- und Programm- bedarf. Also ist die von dir gewählte Lösung schon vom Start weg die schlechtere und langsamere. ARM, 168MHz, 1MB Flash, 192KB RAM und dann von komprimieren in Echtzeit reden. Aber du und Michael könnt ja ruhig über Sachen weiterdiskutieren von denen ihr beide keine Ahnung habt. EOD.
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.