www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Formeln zur Ringpuffer-Arithmetik?


Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wo findet man die Formeln zur Ringpuffer-Arithmetik für einfache
Ringpuffer mit n Kanälen und Ringpuffer mit n Kanälen, in denen die
Daten abgelegt weden, die im Repeat-sequence-of-channels Mode gemessen
werden und die anschließend in jedem Kanal m mal aufaddiert werden,
bevor sie im Ringpuffer abgelegt werden?

Ich will damit in C die mit einem AD-Wandler (im
Repeat-sequence-of-channels Mode) eingelesenen Werte in Ringpuffer
packen und die dann mit Applikationen auslesen.
Das Aufaddieren brauche ich um den Netzbrumm rauszufiltern.
Den Applikationen wird jeweils ein Ringpuffer und der Counter (Anzahl
der bisher verarbeiteten AD-Werte) übergeben.
Damit man die Daten aber sowohl lückenlos als auch ohne
Überschneidungen und zeitlich geordnet bekommt, beispielsweise zur
Fourier-Transformation oder zum Plotten der Daten, muß man aber heftig
rumrechnen und irgendwo sollte es diese Formeln doch fertig geben.

Autor: Peter Dannegger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein Ringpuffer ist ein FIFO und damit völlig ungeeignet für sowas.

Warum denn immer alles so kompliziert sehen ?

Nimm einfach ein Feld der Größe der ADC-Kanäle und dann addier die
neuen Werte darin auf und ziehe den Mittelwert ab, z.B.:

unsigned long sum[ADC_CHANNELS];

sum[i] += new_ADC_val - sum[i] / 16;

Das entspricht dann einem einfachen RC-Glied als Tiefpaß.


Peter

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ein Ringpuffer ist ein FIFO und damit völlig ungeeignet für sowas.

Unsinn; einen Ringpuffer kann man auch als FIFO, FILO oder auch Queue
benutzen. Ich benutze Ringpuffer meist zum Austausch der periodisch
gemessenen Daten zusammen mit dem lezten Zähler, damit ich die Daten
lückenlos und ohne Überschneidungen zusammensetzen kann.


> Nimm einfach ein Feld der Größe der ADC-Kanäle und dann addier die
> neuen Werte darin auf und ziehe den Mittelwert ab, z.B.:
> ...
> Das entspricht dann einem einfachen RC-Glied als Tiefpaß.

Das ist nicht das, was ich brauche und zudem rechenaufwändiger.
Zum Auswerten reicht ein Wert pro Kanal nicht aus; ich brauch pro Kanal
einen Ringpuffer.
Außerdem ändert das nichts am grundlegenden Problem. Beispielsweise muß
die speichernde ISR wissen, was mit dem Wert von der Messung xyz gemacht
werden muß; nach der Berechnung des aktuellen Indexes im aktuellen
Rinpuffer muß ja entweder der erste der m Werte nur geschrieben werden
oder die anderen der m addiert werden. Zudem muß nach einem Auslesen
der Werte von einer Applikation u. A. aus dem ausgelesenen Zähler-Wert
der letzte Eintrag im ausgelesenen Ringpuffer berechnet werden.
Im Prinzip ist das mit Modulo-Arithmetik nicht schwer, und die fertige
Software sehr performant, aber dafür braucht man ein bischen viel
Rechnerei um auf die Formeln zu kommen und zudem macht man da leicht
Fehler wie "um 1 daneben".

Autor: Peter Dannegger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"einen Ringpuffer kann man auch als FIFO, FILO oder auch Queue
benutzen."

Sag ich doch !

Ein Ringpuffer kann immer nur der Reihe nach, nicht aber wahlfrei
zugegriffen werden.
Habe ich aber z.B. den Meßwert von Kanal 7, dann muß ich auf das 7.
Element zugreifen, d.h. ein Ringpuffer ist ein Schuß in den Ofen, man
braucht einen Zugriff über einen Index.


"Das ist nicht das, was ich brauche und zudem rechenaufwändiger."

???

Das ist doch wesentlich effektiver als Deine umständlichen "durch die
Brust ins Auge" Herangehensweise.

Was ist denn so aufwendig an einer simplen Addition, Schieben um 4 Bit
und einer Subtraktion ?


Ich hatte Dich so verstanden, daß Du das Brummen unterdrücken willst
und da gibt es nichts einfacheres, effektiveres und Ressorcen
schonenderes als einen RC-Tiefpaß.
Ich benutze diese Routine schon seit Jahren und sie ist sehr
zuverlässig.
Ein Timerinterrupt startet den ADC und macht nach der Wandlung diese 3
simplen Rechenschritte.
Die Applikation kann nun jederzeit (d.h. völlig asynchron) darauf
zugreifen und hat immer einen gültigen gefilterten Wandlerwert in den
Händen (sum[i] / 16).


Es ist mir herzlich egal, womit Du große Mengen Deines SRAM und
Rechenzeit sinnlos verschleuderst. Ich verstehe bloß nicht warum Du so
verschwenderisch sein willst.


Peter

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ein Ringpuffer kann immer nur der Reihe nach, nicht aber wahlfrei
zugegriffen werden.

Unsinn; auf das Array, in dem der Ringpuffer steht, kann man immer
wahlfrei zugreifen!
Ich nehme dafür meist memmove oder memcpy um die Daten zeitlich zu
ordnen und schon einmal eingelesenes abzuschneiden.


> Was ist denn so aufwendig an einer simplen Addition, Schieben um 4
Bit
> und einer Subtraktion ?

Erstens wird damit immer nur abgerundet, zweitens gibt's bei der
Addition keinen Rundungsfehler und drittens kann es etwas allgemeiner
etwas anderes als eine Addition sein, was mit den m Werten gemacht
wird. Wichtig ist erstmal das Rechnen mit dem Zeit-Index.


> Es ist mir herzlich egal, womit Du große Mengen Deines SRAM und
> Rechenzeit sinnlos verschleuderst. Ich verstehe bloß nicht warum Du
so
> verschwenderisch sein willst.

Unsinn, denn Ringpuffer sind die effektivsten Datenstrukturen zum
Zwischenspeichern von Daten, da sie eine feste Größe haben (kein
malloc/calloc +free nötig) und die Daten so lange drinn bleiben, bis
sie von neueren überschrieben werden müssen.

Autor: Rufus T. Firefly (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
.

   "Ich nehme dafür meist memmove oder memcpy um die Daten
   zeitlich zu ordnen und schon einmal eingelesenes abzuschneiden."

Sonderlich effizient ist so eine Vorgehensweise aber nicht, vor allem
wird dadurch der _Ring_puffer irgendwie widersinnig.

Das hast Du ja eigentlich auch erkannt ("Ringpuffer sind die
effektivsten Datenstrukturen zum Zwischenspeichern von Daten"), daher
solltest Du tunlichst auf so Spielereien wie memmove oder memcpy
verzichten.

Autor: Peter Dannegger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nun wird mir manches klarer, daß einige Leute einen 3GHz Pentium
brauchen aber andere für die gleiche Sache auf einem 8051 noch 80% Idle
sind.

Ich bin halt Praktiker und mag deshalb schnelle und einfache Routinen,
memmove, malloc usw. haben daher bei mir nichts verloren.

Warum Daten erst umständlich in einen Puffer klauben, kompliziert
umsortieren und wieder ausspucken, statt sie einfach gleich zu
verarbeiten.


Die Abrundung kompensiert sich vollständig, da ja auch bei der
Subtraktion abgerundet wird.

Rein mathematisch gesehen ginge ja auch:

sum[i] = new_ADC_val + sum[i] * 15 / 16;

Aber praktisch ist es schlichtweg falsch, es erreicht nämlich nie den
Endwert. Das sind halt so die Praktiker-Tricks.


Ringpuffer benutze ich nur für den Datenempfang (UART, CAN), da dort
die Befehle erst abgearbeitet werden können, wenn sie komplett sind.
Und da sind sie wirklich sinnvoll, da ja keine Umsortierung notwendig
ist (kein memmove).


Peter

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Warum Daten erst umständlich in einen Puffer klauben, kompliziert
> umsortieren und wieder ausspucken, statt sie einfach gleich zu
> verarbeiten.

Das geht nicht, denn die Messung und Speicherung wird von einem
Kernel-Thread gemacht und die Auswertung und Speicherung von einem oder
mehreren User-Space-Threads. Alles zusammen zu packen ergäbe
Spagetti-Code, der weder orthogonal noch modular wäre.

Außerdem hat man mit den Ringpuffern ja die Felxibilität die Rohdaten
verschicken zu können, um sie woanders auszuwerten, beispielsweise
mittels Fourier-Analyse.

Autor: Peter Dannegger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Rolf

"Alles zusammen zu packen ergäbe Spagetti-Code, der weder orthogonal
noch modular wäre."

Was ist denn daran Spaghetti, eine sinnvolle Datenverdichtung schon bei
der Datenaufnahme zu machen ?

Spaghetti ist, wenn man kein Konzept hat und ellenlangen Code
hintereinander klatscht.


Der AD-Wandler Prozeß weiß, wann ein neues Datum hereinkommt und kann
dieses sofort verarbeiten. Ein nachfolgender Prozeß muß dagegen erst
umständlich synchronisiert werden. Neben den reinen Wandlerdaten im
Ringpuffer müssen also noch Synchronisationsmechanismen implementiert
werden. Außerdem müssen Pufferüberläufe abgefangen werden, wenn der
nachfolgende Prozeß mal nicht schnell genug die Daten absaugen kann.

Ringpuffer machen daher den Datenaustausch generell sehr aufwendig und
kompliziert.

In Steuerungen sind aber alte Daten in der Regel kalter Kaffe, d.h.
eine einzige Pufferzelle, die regelmäßig mit neuen Daten überschrieben
wird, unabhängig davon, ob der nachfolgende Prozeß die Daten gelesen hat
oder nicht, ist viel einfacher und effektiver.

Ich finde es außerdem nicht sinnvoll, bei z.B. 8 ADC-Kanälen die 8
nachfolgenden Prozesse 8 Filterroutinen laufen zu lassen, statt einfach
nur einer für alle.



"Außerdem hat man mit den Ringpuffern ja die Felxibilität die
Rohdaten
verschicken zu können"

Vergiß es, die eierlegende Wollmilchsau zu entwickeln, die wird ewig
nicht fertig.
Wenn man sich einfach nur auf die aktuell Aufgabe konzentriert, wird
das Programm mindestens 10-mal schneller fertig.


Ich hab früher auch mal so gedacht und das Ende vom Lied war immer:

Mühsam vorausgeplante Erweiterungen wurden nie realisiert, da
inzwischen schon längst andere Hardware, andere CPUs, andere Konzepte
verwendet wurden.

Man verschleißt sich einfach nur an der Featureritis, aber es bringt
überhaupt nichts, Software ist heutzutage viel zu kurzlebig.


Peter

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ein nachfolgender Prozeß muß dagegen erst
> umständlich synchronisiert werden.

Eben nicht; gerde deshalb nehme ich Ringpuffer und deshalb fehlen mir
noch die Formeln für die komplizierteren Ringpuffer. Für den einfachen
Ringpuffer habe ich die Formeln schon:

Der letzte Eintrag ist beim Index (Zeitindex % N) und der Puffer
enthält Min( N, Zeitindex) Werte. Die Zeit-Index-Differenz zweier
direkt benachbarter Puffer-Inhalte ist 1 oder n-1; die Differenz zum
vorherigen Wert ist immer 1.
Der Zeitindex wird mit -1 initialisiert, damit der nach dem ersten
Eintrag in den Puffer gleich 0 ist und so Index = Zeitindex % N immer
erfüllt  ist.
Zweckmäßigerweise speichert man den Zeitindex am Ende des auszugebenden
eldes, damit es mit einer Anweisung mit diesem Datenfeld ausgegeben
werden kann, beispielsweise über Shared Memory (RTAI). Beispiel:

int16_t out_ringbuffer[N + 4];
int64_t * ptr_counter = &out_ringbuffer[N];

Und der Ringpuffer-Index wird über Makros verwendet:

// increment for ring buffer index (0..n-1), also works with start
value -1
#   define mc_RING_INC(x, n) {++(x); (x) %= (n);}

// next value at incrementing, preview
#   define mc_RING_NEXT(x, n) (((x)+1)%(n))

// decrement for ring buffer index (0..n-1), also works with start
value < 0
#   define mc_RING_DEC(x, n) {if((x) > 0)  --(x); else (x)=(n)-1;}

// value before last increment, review
#   define mc_RING_LAST(x, n) ( (x) ? ((x)-1) : ((n)-1))

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nachtrag: Der Puffer enthält Min( N, Zeitindex-1) Werte.

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ähm, Verwechselung; es sind natürlich
(Zeitindex > n-1 ? N : Zeitindex +1)
Werte.

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]
  • [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.