mikrocontroller.net

Forum: FPGA, VHDL & Co. Komprimierungsalgorithmen


Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich möchte Daten von einem FPGA zum PC schicken. Um die USB-Datenrate 
nicht unnötig auszulasten suche ich nach einem einfachen (muss nicht 
extrem effizient sein, wichtig ist eine schnelle Implementierung) 
Streamkomprimierungsalgorithmus.
Am FPGA hängt ein 14Bit ADC (könnte max. 60MSPS) und ein FX2 soll die 
Daten in den PC schaffen.
Welche Methode ist an sinnvollsten?

Autor: Li-La-Launebär (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
haengt vom analogsignal ab

Autor: Bernd (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn das Signal nur kleine Änderungen hat versuchs in dem du nur sendest 
was sich verändert.

Also:
Anfangswert ist 500
Wert verändert sich auf 540, sendest du nur +40
Wert verändert sich danach auf 520, sendest du -20
Wert geht auf 455, sende -45
Und so weiter...

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Normale Deltamodulation bringt bei wirklich zufälligen Signalen nicht 
besonders viel...
Höchstens Adaptive Deltamodulation aber damit habe ich leider keine 
Erfahrung.
Da ich die Daten nicht in Echtzeit brauche wäre ev. ein 
Blockkomprimieralgorithmus überlegenswert, auch wenn ich dann externes 
RAM brauche (habe nur einen kleinen Spartan3)
Wie viel kann man mit Verlustlosen Blockkompriemieralgorithmen 
rausholen?

Autor: Christian Aurich (cau) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Wie viel kann man mit Verlustlosen Blockkompriemieralgorithmen
> rausholen?

hängt ganz von deinen Daten ab - wie sind die Änderungen? Bzw. was misst 
du?

Man kann von nahezu 100% bis zu nahezu 0% Komprimierung alles erreichen 
- wenn deine Daten wirklich Zufällig sind, wird eine Komprimierung 
absolut nix bringen, da nur Overhead entsteht.

Christian

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wirklich zufällig sind sie natürlich nicht. Aber es treten sehr steile 
Pulse auf und eine Deltamodulation verfälscht eben die Steilheit und für 
Adaptive Deltamodulation sind die Daten eben "zu zufällig". Man kann vom 
bisherigen Signalverlauf eben nicht auf den nächsten Wert schließen.
Bleibt wohl nur eine Blockkomprimierung.

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man den Dateninhalt in etwa vorhersehen kann, dann geht es relativ 
einfach.

Man benötigt eine Statistik der Werte. Die am häufigsten vorkommenden 
Werte
werden mit dem kürzesten Code übertragen.

Wenn es eine passende statistische Verteilung gibt, die eine solche 
Kodierung ermöglicht, dann schau mal unter "Huffmann Code" im Netz.

Autor: Michael Appelt (micha54)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

die aus meiner Sicht wichtigste Frage wurde hier nicht gestellt:
Sollen die Daten per ASCII ausgetauscht werden oder darf es auch binär 
sein ?

ASCII sind das 40 bit pro Wert, binär nur 14....
Bei ASCII wäre BCD als Alternative zu prüfen, macht 20bit rpo Wert.

Gruß,
Michael

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So eine Verteilung gibt es wahrscheinlich eben nicht. Es sind Störungen 
die erfasst werden sollen.

Autor: Alter Hase (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>So eine Verteilung gibt es wahrscheinlich eben nicht. Es sind Störungen
>die erfasst werden sollen.

Na, wenn du die Störung im FPGA detektierst und nur in diesem Fall Daten 
überträgst...

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
so einfach ist es leider nun doch nicht da halt dauernd was passiert und 
manchmal kommen ebne pulse oder andere höherfrequente Anteile und die 
müssen auch übertragen werden...

Autor: Klugscheisser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Verstehe ich das richtig:

1. Die Daten haben keinerlei Redundanz
2. Du musst 840MBit/s über eine 480MBit/s-Leitung kriegen.

Das geht natürlich so nicht. Du kannst nur hoffen, das da eine Redundanz 
in den Werten ist und eine Komprimierung anwenden. Am besten Mal messen.

Und:
>Um die USB-Datenrate nicht unnötig auszulasten

scheint mir da eher ein Euphemismus zu sein.

Und:
Du kannst einen Komprimierungsalgorithmus (im FPGA?) ausführen aber 
keine Auswertung des Signals? Hmmm.

Und:
>muss nicht extrem effizient sein
Aha.

Was ist denn die Quelle für das Signal?

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es sind Breitbandpulse.
Die Daten sollen auf dem PC verarbeitet werden. Von 2:1 Komprimierung 
war keine Rede. Sollte halt "so gut wie möglich" sein, ich bin um jedes 
MSps mehr was fehlerfrei gestreamt werden kann froh. Dies ist ein 
Experiment und keine Endanwendung wo die Rahmenbedingungen genau gegeben 
sind...
Der FPGA macht bereits die TP-Filterung und Abtastratenreduktion. Die 
Rohdaten sollen aber in den PC um dort relativ Aufwändig verarbeitet zu 
werden.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei Huffman muß die Verteilung nicht bekannt sein, du mußt dann nur den 
Baum mitübertragen.
Hier: Beitrag "[AVR ASM] Huffman (de)kompression" hab ich sowas in ASM 
umgesezt, das geht auf nem FPGA natürlich bedeutend eleganter (braucht 
halt relativ viele Bitmanupulationen).
Diesen overhead kann man sich sparen wenn man sich auf eine feste 
Tabelle einigt, dann ist aber die Kompressionsleitung geringer.
Sosntige Verfahren die recht einfach sind und nichts über die Quelle 
wissen müssen sind LZW und (ich glaub es hieß so hab leider mein NT 
Skript nicht hier) Willamscodierung...
Beide verfahren sind relativ einfach und auch mit kleinem 
SPeicheraufwand realisierbar, wenn auch kein Streaming möglich ist (bei 
Huffman ginge es wenn der Baum im Vorraus bekannt ist)

Oder dieser dynamisch angepaßt wird: 
http://de.wikipedia.org/wiki/Shannon-Fano-Kodierun...

Autor: Klugscheisser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man kann bei Huffmann den Baum auch gleichzeitig auf der Sende- und 
Empfangsseite berechnen. Dann braucht man ihn nicht zu übertragen.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann muß aber beiden Seiten die Verteilung bekannt sein oder nicht? Und 
das ist hier ja nicht der Fall!

Autor: Klugscheisser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Läubi

>Dann muß aber beiden Seiten die Verteilung bekannt sein oder nicht?

Richtig. Das ist sie aber auch.
Der Sender kennt ja die Verteilung beim senden und die Baumveränderung 
durch das neue Zeichen.
Und der Empfänger kennt sie, nachdem er das nächste Zeichen empfangen 
hat.
Der Baum hinkt halt sozusagen immer ein Zeichen hinterher.
Klar?
Man kann entweder von einem leeren Baum oder einem sinnvoll vorbesetzten 
ausgehen.

Das geht dann so:
Sender:
1. Neues Zeichen verfügbar
2. Nach Huffmann kodieren mit vorhandenem Baum
3. Kodiertes Zeichen senden.
4. Baum ändern
5. Zu 1.

Empfänger:
1. Zeichen empfangen
2. Zeichen nach Huffmann dekodieren mit vorhandenem Baum
3. Dekodiertes Zeichen wegspeichern
4. Baum ändern
5. Zu 1.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ah okay das stimmt allerdings! Muß man dann halt sehen was einfacher ist 
und wieviel das bringt. Auf jedenfall ein interesanter Ansatz den ich 
mal bei gelgenheit verfolgen werde :)

Autor: Alter Hase (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Der FPGA macht bereits die TP-Filterung und Abtastratenreduktion. Die
>Rohdaten sollen aber in den PC um dort relativ Aufwändig verarbeitet zu
>werden.

Das ist doch bereits eine Komprimierung. Wieviel Datenrate bleibt denn 
übrig nach dem Downsamplung? Führt der TP nicht zu einem geglättetenden 
Signal, das man besser als Differenz übertragen kann?

MfG, AH

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Daten werden mit 60MSps abgetastet und dann TP-gefiltert und mit 
einem Dezimator auf 15MSps konvertiert. Da der ADC mit 14Bit abtastet 
komme ich so schon an die Grenze der Übertragungsrate des FX2.
Die Daten ineinander zu verschachteln habe ich noch implementiert. 
Momentan verschenke ich also 2 Bit da ich die 14Bit als 2x 8Bit 
verschicke.
Ein 8Bit Differenzwert scheint aber wirklich am sinnvollsten zu sein...

Autor: ahem (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eine wichtige Entscheidung ist : verlustfreie oder verlustbehaftete 
Kompression.

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit verlustfreier Komprimierung werde ich nicht besonders weit kommen. 
Bleibt also nur verlustlose Komprimierung, wenn möglich mit ein paar 
Parametern zum einstellen

Autor: Klaus Falser (kfalser)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was ist der Unterschied zwischen verlustfrei und verlustlos, bitte ?

Autor: Luky S. (luky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein Schreibfehler wie er aus dem Kontext sehr leicht erkennbar ist. Soll 
natürlich verlustbehaftet sein...

Autor: Michael Appelt (micha54)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Luky S. wrote:
> Die Daten werden mit 60MSps abgetastet und dann TP-gefiltert und mit
> einem Dezimator auf 15MSps konvertiert. Da der ADC mit 14Bit abtastet
> komme ich so schon an die Grenze der Übertragungsrate des FX2.
> Die Daten ineinander zu verschachteln habe ich noch implementiert.
> Momentan verschenke ich also 2 Bit da ich die 14Bit als 2x 8Bit
> verschicke.
> Ein 8Bit Differenzwert scheint aber wirklich am sinnvollsten zu sein...

8-bit Differenzwert als Float wert mit 3 bit Exponent und 5 bit 
Mantisse. Sowas habe ich mal implemetiert um statistische Daten sehr 
sparsam zu übertragen.

Beispiel: Differenz sind 13 bit, ergibt die obersten 5 bit und Exponent 
7
EDIT!!! Im nächsten Byte würde die kleinere verbleibende Differenz
EDIT!!! mit Exponent 2 folgen, danach der Rest. d.h. der Wert hinkt
EDIT!!! maximal 2 Zyklen hinterher.


Die 2. Übertragung hatte ich damals nicht benötigt, weil ich nur an 
logaritmischen Werten geringer Genauigkeit interessiert war.

Gruß,
Michael

Autor: Klaus Falser (kfalser)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man kann hin und herdiskutieren wie man will :
Komprimieren kann man etwas nur, wenn es redundante Information enthält, 
die bei der Kompression entfernt werden.
Daten von einem ADC Wandler sind eben nur dann redundant, wenn die 
Bandbreite kleiner als die doppelte Abtastrate ist, oder die Amplitude 
nicht ausgenützt wird.

Eine Übertragung von Differenzen ist nur dann effizienter, wenn die 
Differenzen beschränkter als die Originaldaten sind (weil eben die 
Bandbreite beschränkt ist). Die vorgeschlagene Übertragung der Differenz 
als Mantisse und Exponent erzeugt eine verlustbehaftete Kompression, 
ganz abgesehen davon dass der Quantisierungsfehler aufsummiert wird und 
das rekonstruierte Signal "davonlaufen" kann.
Da ist es wahrscheinlich besser gleich die Orignaldaten als 
Fließkommazahl zu übertragen.

Autor: jens (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Die Daten werden mit 60MSps abgetastet und dann TP-gefiltert und mit
> einem Dezimator auf 15MSps konvertiert. Da der ADC mit 14Bit abtastet
> komme ich so schon an die Grenze der Übertragungsrate des FX2.

Die 15MSps bei 16Bit kann der FX2 ohne Komprimierung in Echtzeit 
übertragen. Es sind etwa 40Mbyte/s möglich, da hast du mit deinen 
30Mbyte/s sogar noch etwas Reserve.

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.