www.mikrocontroller.net

Forum: FPGA, VHDL & Co. 210Mbyte/s Komprimieren mit CPLD/FPGA


Autor: Christian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich arbeite grade an meiner Diplomarbeit an der TU-Braunschweig.
Von einem AD-Umsetzer (14Bit120MHz) bekomme ich einem
Messdatenstrom von 210Mbyte/s. Ein 512Mbyte großer DDR SDRAM
kann die Daten zwischenspeichern, aber nach 2,4s ist der
Speicher voll. Über eine USB-Schnittstelle
kann ich maximal nur 30Mbyte zu einem Computer übertragen.

Ich suche einen verlustlosen(!) Komprimierungsalgorithmus
mit dem ich die Messdaten kleiner kriege. Durch Übertragung
von Differenzen der Messdatenwörter erhalte ich bei bestimmten
Messsignalen nur einen Komprimierungsfaktor von ca. 2
und das ist noch zu wenig. Hat jemand eine Idee, wie ich die
Messdaten um den Faktor 7 kleiner kriege? Wichtig ist mir, dass
die Komprimierung verlustlos ist.

Vielen Dank für Eure Mühe!

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du verlustlos komprimieren willst, wäre es u.U. interessant zu
wissen, wo die Daten herkommen. Dann könntest du evtl. redundante Daten
aussortieren. Ansosnten kann ich mir nur vorstellen, daß nur ein paar
(max. zig) Prozent komprimierbar wären. Welche Aufzeichnungsdauer
möchtest du denn haben ?

Gruß THomas

Autor: ope (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mmhh, Faktor 7 ist heftig i.A. Wie Thomas schon sagte, redundante Daten
komprimieren; bzw. Burrows-Wheeler block-sorting text compression
algorithm, und Huffman coding. Also, bzip2/lzh in VHDL - wäre schon
cool. Du darfst aber auch nicht vergessen, diese Meta Daten nehmen auch
Platz/Übertragungszeit weg, so dass (je nach Daten) plötzlich die
Datenmenge größer sein kann (jpeg ist so ein typ. Fall) - hier musst Du
dann abbrechend mit den komprimimieren. Vieles hängt also letzlich von
der Datenbeschaffenheit an sich an.

Viele Grüße
Olaf

Autor: Markus K. (markus-)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei Kompression geht es darum, daß man Muster und Strukturen in den
Daten findet. Zufällige Daten (weißes Rauschen) kann man nicht
komprimieren.

Wenn Du durch Differenzbildung einen Faktor 2 erreichen kannst, dann
heißt das, daß die Meßwerte voneinander abhängig sind. Solche
Informationen sind wichtig, denn nur so kann man überhaupt verlustfrei
komprimieren. Du kannst keine Komprimierung für beliebige Daten bauen!
Denn wenn das möglich wäre, dann könnte man ja einfach mehrere
Kompressoren hintereinanderschalten und beliebig stark komprimieren.

Nehmen wir mal an, die untersten beiden Bits Deiner Messung seien total
verrauscht (bei 120MHz und 14Bit nicht unrealistisch) und enthalten
damit echten Zufall. Echten Zufall kann man nicht komprimieren, d.h. Du
brauchst nur für diese beiden Bits 30MByte/s und es kann kein
Verfahren geben um diese beiden Bits zu komprimieren. Dies eben unter
der Annahme, daß Bit 0+1 verrauscht sind. Ist nur Bit 0 verrauscht,
dann brauchst Du dafür 15MByte/s und mußt die 13 anderen Bits um den
Faktor 13 komprimieren.

Ein paar Kompressionsverfahren:
ADPCM: Differenzenbildung mit Vorhersage. Die Meßwerte seien 200, 300,
400, dann sagt man vorher, der nächste Wert sei 500. Er hat aber nur
490, deswegen überträgt man den Korrekturwert -10 statt der Differenz
+100. Da die Korrekturwerte kleiner sein sollten als die echten
Differenzen kann man hier Bits sparen. Das ganze wird noch adaptiv
angepasst. Die Vorhersage muß auch nicht linear sein.

Huffman/Arithmetische Kodierung: Häufig vorkommende Werte bekommen
kürzere Bitmuster zugewiesen, seltene Werte längere Bitmuster. Um einen
deutschen Text zu komprimieren würde man z.B. dem "e" einen 3Bit-Code
geben und dem "x" einen 12Bit langen Code.

LZW/LZ77: Hierbei geht es darum, sich wiederholende Muster zu finden.
Die können durchaus recht kurz sein, z.B. 2 oder 3 Samples.

Autor: Stefan R. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Christian,

was soll denn genau gemessen werden? Ich denke, es gibt, wenn du eine
Echtzeitverarbeitung der Daten haben willst (d.h. nicht ein paar
Sekunden aufzeichnen und dann mehrere Sekunden lang Daten zum PC
übertragen) nur diese zwei Möglichkeiten:
- schnelleres Interface zum PC. Z.B. zweimal GBit-Ethernet
draufklatschen, Hardware für den PC ist billig, wenn man auf tcp-ip
verzichtet und ein eigenes Lowlevel-Protokoll direkt auf
Ethernetpacketebene realisiert könnte das klappen. Allerdings k.A., ob
der PC das dann schnell genug verarbeiten kann (alleine zum nur
mitschreiben auf Platte reicht ja eine Platte mit höchsten 50MB/s ja
schonmal nicht aus). Ausserdem weiss ich nicht, inwiefern
GBit-Ethernet-Interfaces problemlos erhältlich und an FPGAs
anschliessbar sind (geht bestimmt, Aufwand und Preis ist halt die
Frage).
- Vorverarbeitung der Daten im FPGA. Also Teile dessen, was du sonst im
PC machen würdest, im FPGA machen. Beispiel: Software defined radio, wie
z.B. gnuradio.org. Da würde man im FPGA den momentan interessanten
Frequenzbereich runtermischen und auf die gerade erforderliche
Bandbreite filtern, dann passt es durch den USB.
Eine verlustfreie hohe Kompression von nahezu "zufälligen" Daten aus
der analogen Welt gibt es afaik nicht. Beispiel: Audiocodec FLAC. Der
kann max. ca. zweifach komprimieren. Zum mathematischen Hintergrund:
Besorg dir ein Buch über Nachrichtentechnik und schau dort nach
"Entropie". Du kannst durch Analyse eines Beispielsignals die
maximimale mögliche theoretische Kompression ohne Verluste berechnen.

Gruß,
Stefan

Autor: Diplomtester (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das Diplom für Deinen Ingenieur ist doch nur dann gerechtfertigt, wenn
Du die Erfindung zur 7-fachen Komprimierung selber entwickelst, oder?

Autor: Diplomtesterprüfer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dilpomtester, SETZEN, DURCHGEFALLEN, EXMATRIKULIERT!
Begründung: Oberste Regel lautet: Das Rad nie neu erfinden, wenn nicht
unbedingt nötig!
Primäre Aufgabe nicht aus dem Blick verlieren und Augen auf für
alternative Lösungen!

Sie dürfen den Prüfungssaal jetzt verlassen...

Autor: Diplomtester (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
lach... ich habe nie einen Prüfungssaal betreten. Ich braucht sowas
nicht!

Autor: Markus K. (markus-)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@stefan R:
Die Formel für die maximale Kompression gilt für beliebige Daten. Wenn
man aber außer der Entropie noch weitere Informationen über das Signal
hat, dann kann man durchaus auch stärker komprimieren. Wenn Du z.B. von
einem ZIP-Archiv die Entropie berechnest, dann wird rauskommen, daß man
da nicht viel komprimieren kann. Dann packst Du das Archiv aus und
packst es neu mit RAR - und das Ergebnis kann dann durchaus besser sein
als das theoretische Limit. Das geht aber eben nur, wenn man zusätzliche
Informationen hat. Bei der Meßtechnik könnten das z.B. die maximale
Bandbreite oder irgendwelche Einschwingvorgänge sein.

Markus

Autor: Christian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Leute, vielen Dank für die vielen Ideen.

Zu der Frage wo kommen die Daten her: Auf meine webseite www.alset.de
ist unter Studienarbeit die AD-Umsetzerkarte kurz vorgestellt. (Da
werde ich sie für ein privates Projekt (am Teslatrafo) nutzen).
Was will ich messen: Es soll ein Speicheroszilloskop für beliebige
Messsignale werden. Die Signalart steht also nicht fest. Hier im
Institut soll für die Entwicklung eines THz-Mikroskops ein 10MHz Signal
eines supraleitenden Josephsonkontaktes gemessen werden.
Von den 14Bit des Umsetzers klappern die untersten 3bit. (Sie stellen
Rauschen dar.)

Ich habe mal Eure vielen Ideen ausgewertet. Vielen Dank für die vielen
Beiträge!
Einen Leckerbissen zu dem Thema "Wertdiskrete Informationstheorie"
fand ich übrigens auf:
http://www.lnt.e-technik.tu-muenchen.de/download/L...

Verlustlos lässt sich nicht hoch komprimieren. Sinnvoll ist kleine
Informationsverluste zuzulassen.
Als erste Idee habe ich mir den folgenden Algorithmus überlegt:

1. Von den 14Bit Daten schneide ich die untersten 3Bit ab, da sie
Rauschen darstellen.
2. Ein Schätzmodell (z.B. ADPCM) schätzt aus alten Werten einen neuen
Wert. Dann muss nur noch der Schätzfehler übertragen werden. Nun lasse
ich noch eine weitere Näherung zu:
3. Nur wenn der Schätzfehler einen bestimmten Wert überschreitet wird
die Änderung übertragen.
Damit erreiche ich: Es wird nur ein a=Messwert, der b=Vorhersagewert
und c=die Anzahl der Datenworte (die den Schätzmodell folgen)
übertragen.

Für grosse c-Anzahl habe ich eine hohe Komprimierung. Für Signale mit
konstanter Steigung (egal ob größer, kleiner oder gleich Null) z.B. für
wenig verrauschte Rechteck- oder Dreiecksignale lässt sich also ein
grosser Komprimierungsfaktor erreichen. Ist jedoch die Rauschamplitude
zu gross geht das nicht mehr.

Diesen Algorithmus werde ich in den nächsten Tagen mal testen. Dann
werde ich sehen, was mit realen Signalen möglich ist. Der
Komprimierungsfaktor hängt stark mit der Signalart zusammen. Übrigens
muss ja auch nur der Mittelwert des Komprimierungsfaktors kleiner als 7
sein, da ich Daten in Speicher (im FIFO-Bertrieb) zwischenspeichern
kann.

Bis dann, der Christian

Autor: Markus K. (markus-)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Vorhersagewert muß nicht übertragen werden. Der Empfänger kennt ja
die bisher empfangenen Daten und kann den Wert selber vorhersagen.

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.