Ich suche nach einer zeit- und speichereffizienten Lösung, um einen gleitenden Durchschnitt in C zu berechnen . Ich muss das Teilen vermeiden, weil ich auf einem PIC 16 bin, der keine dedizierte Divisionseinheit hat.
Im Moment speichere ich einfach alle Werte in einem Ringpuffer und speichere und aktualisiere die Summe jedes Mal, wenn ein neuer Wert eintrifft. Das ist sehr effizient, nutzt aber leider den größten Teil meines verfügbaren Speichers ...
Antworten:
Wie bereits erwähnt, sollten Sie einen IIR-Filter (Infinite Impulse Response) anstelle des FIR-Filters (Finite Impulse Response) in Betracht ziehen, den Sie derzeit verwenden. Es gibt noch mehr, aber auf den ersten Blick sind FIR-Filter als explizite Faltungen und IIR-Filter mit Gleichungen implementiert.
Das spezielle IIR-Filter, das ich häufig in Mikrocontrollern verwende, ist ein einpoliges Tiefpassfilter. Dies ist das digitale Äquivalent eines einfachen RC-Analogfilters. Für die meisten Anwendungen weisen diese bessere Eigenschaften auf als der von Ihnen verwendete Boxfilter. Die meisten Anwendungen eines Boxfilters, auf die ich gestoßen bin, sind das Ergebnis von jemandem, der in der Klasse der digitalen Signalverarbeitung nicht aufpasst, nicht weil er seine besonderen Eigenschaften benötigt. Wenn Sie nur hohe Frequenzen dämpfen möchten, von denen Sie wissen, dass sie Rauschen sind, ist ein einpoliger Tiefpassfilter besser. Der beste Weg, einen digital in einem Mikrocontroller zu implementieren, ist normalerweise:
FILT <- FILT + FF (NEU - FILT)
FILT ist ein hartnäckiger Zustand. Dies ist die einzige persistente Variable, die Sie zur Berechnung dieses Filters benötigen. NEU ist der neue Wert, den der Filter mit dieser Iteration aktualisiert. FF ist die Filterfraktion , die die "Schwere" des Filters einstellt. Schauen Sie sich diesen Algorithmus an und sehen Sie, dass der Filter für FF = 0 unendlich schwer ist, da sich die Ausgabe nie ändert. Für FF = 1 ist es wirklich überhaupt kein Filter, da die Ausgabe nur der Eingabe folgt. Nützliche Werte liegen dazwischen. Bei kleinen Systemen wählen Sie FF mit 1/2 Nso dass die Multiplikation mit FF als Rechtsverschiebung um N Bits ausgeführt werden kann. Beispielsweise könnte FF 1/16 sein und das Multiplizieren mit FF daher eine Rechtsverschiebung von 4 Bits. Andernfalls benötigt dieser Filter nur ein Subtrahieren und ein Addieren, obwohl die Zahlen normalerweise breiter als der Eingabewert sein müssen (mehr zur numerischen Genauigkeit in einem separaten Abschnitt weiter unten).
Normalerweise nehme ich A / D-Messungen deutlich schneller vor, als sie benötigt werden, und wende zwei dieser Filter kaskadiert an. Dies ist das digitale Äquivalent von zwei in Reihe geschalteten RC-Filtern und dämpft um 12 dB / Oktave über der Rolloff-Frequenz. Bei A / D-Messungen ist es jedoch in der Regel relevanter, den Filter im Zeitbereich unter Berücksichtigung seiner Sprungantwort zu betrachten. Hier erfahren Sie, wie schnell Ihr System eine Änderung erkennt, wenn sich das Messobjekt ändert.
Um das Entwerfen dieser Filter zu erleichtern (was nur bedeutet, FF auszuwählen und zu entscheiden, wie viele davon kaskadiert werden sollen), verwende ich mein Programm FILTBITS. Sie geben die Anzahl der Schiebebits für jeden FF in der kaskadierten Reihe von Filtern an und errechnen die Sprungantwort und andere Werte. Eigentlich starte ich das normalerweise über mein Wrapper-Skript PLOTFILT. Dadurch wird FILTBITS ausgeführt, wodurch eine CSV-Datei erstellt und anschließend die CSV-Datei geplottet wird. Zum Beispiel ist hier das Ergebnis von "PLOTFILT 4 4":
Die beiden Parameter für PLOTFILT bedeuten, dass zwei Filter des oben beschriebenen Typs kaskadiert werden. Die Werte von 4 geben die Anzahl der Schiebebits an, um die Multiplikation mit FF zu realisieren. Die beiden FF-Werte betragen in diesem Fall also 1/16.
Die rote Kurve ist die Einheitsschrittantwort und die Hauptsache, auf die Sie achten müssen. Dies zeigt Ihnen beispielsweise an, dass bei einer sofortigen Änderung der Eingabe die Ausgabe des kombinierten Filters in 60 Iterationen auf 90% des neuen Werts eingestellt wird. Wenn Sie 95% der Einschwingzeit benötigen, müssen Sie 73 Iterationen abwarten, und für 50% der Einschwingzeit nur 26 Iterationen.
Die grüne Kurve zeigt Ihnen die Ausgabe einer einzelnen Spitze mit voller Amplitude. Dies gibt Ihnen eine Vorstellung von der Unterdrückung von zufälligem Rauschen. Es sieht so aus, als würde kein einziges Sample mehr als 2,5% Veränderung in der Ausgabe verursachen.
Die blaue Spur soll ein subjektives Gefühl dafür vermitteln, wie dieser Filter mit weißem Rauschen umgeht. Dies ist kein strenger Test, da keine Garantie dafür besteht, wie genau der Inhalt der Zufallszahlen lautete, die als Eingabe für das weiße Rauschen für diesen Durchlauf von PLOTFILT ausgewählt wurden. Es ist nur, um Ihnen ein grobes Gefühl dafür zu geben, wie stark es zerdrückt wird und wie glatt es ist.
PLOTFILT, möglicherweise FILTBITS und viele andere nützliche Dinge, insbesondere für die PIC-Firmware-Entwicklung, finden Sie in der Softwareversion der PIC Development Tools auf meiner Seite zum Herunterladen von Software .
Hinzugefügt über numerische Präzision
Ich sehe aus den Kommentaren und nun aus einer neuen Antwort, dass Interesse besteht, die Anzahl der Bits zu diskutieren, die zur Implementierung dieses Filters benötigt werden. Beachten Sie, dass das Multiplizieren mit FF neue Log 2 (FF) -Bits unterhalb des Binärpunkts erzeugt. Bei kleinen Systemen wird FF normalerweise mit 1/2 N gewählt, so dass diese Multiplikation tatsächlich durch eine Verschiebung von N Bits nach rechts realisiert wird.
FILT ist daher normalerweise eine Festkommazahl. Beachten Sie, dass dies aus Sicht des Prozessors nichts an der Mathematik ändert. Wenn Sie beispielsweise 10-Bit-A / D-Messwerte und N = 4 (FF = 1/16) filtern, benötigen Sie 4 Bruchbits unterhalb der 10-Bit-Ganzzahl-A / D-Messwerte. Bei den meisten Prozessoren würden Sie aufgrund der 10-Bit-A / D-Messwerte 16-Bit-Ganzzahloperationen ausführen. In diesem Fall können Sie immer noch genau die gleichen 16-Bit-Ganzzahloperationen ausführen, aber mit den A / D-Messwerten beginnen, die um 4 Bit nach links verschoben sind. Der Prozessor kennt den Unterschied nicht und muss es auch nicht. Die Berechnung ganzer 16-Bit-Ganzzahlen funktioniert unabhängig davon, ob Sie sie als 12,4-Fixpunkt- oder echte 16-Bit-Ganzzahlen (16,0-Fixpunkt) betrachten.
Im Allgemeinen müssen Sie für jeden Filterpol N Bits hinzufügen, wenn Sie aufgrund der numerischen Darstellung kein Rauschen hinzufügen möchten. Im obigen Beispiel müsste der zweite von zwei Filtern 10 + 4 + 4 = 18 Bits haben, um keine Informationen zu verlieren. In der Praxis bedeutet dies auf einem 8-Bit-Computer, dass Sie 24-Bit-Werte verwenden. Technisch würde nur der zweite von zwei Polen den breiteren Wert benötigen, aber zur Vereinfachung der Firmware verwende ich normalerweise die gleiche Darstellung und damit den gleichen Code für alle Pole eines Filters.
Normalerweise schreibe ich eine Subroutine oder ein Makro, um eine Filterpoloperation durchzuführen, und wende diese dann auf jeden Pol an. Ob ein Unterprogramm oder ein Makro vorhanden ist, hängt davon ab, ob Zyklen oder der Programmspeicher in diesem bestimmten Projekt wichtiger sind. In beiden Fällen verwende ich einen Scratch-Status, um NEW an die Subroutine / das Makro zu übergeben, die / das FILT aktualisiert, aber auch in denselben Scratch-Status lädt, in dem NEW sich befand. Dies erleichtert das Anwenden mehrerer Pole, da der aktualisierte FILT eines Pols ist das NEUE vom nächsten. Bei einer Unterroutine ist es nützlich, einen Zeiger auf FILT auf dem Weg nach innen zu haben, der beim Verlassen auf FILT aktualisiert wird. Auf diese Weise bearbeitet das Unterprogramm automatisch aufeinanderfolgende Filter im Speicher, wenn es mehrmals aufgerufen wird. Mit einem Makro benötigen Sie keinen Zeiger, da Sie die Adresse übergeben, um mit jeder Iteration zu arbeiten.
Codebeispiele
Hier ist ein Beispiel eines Makros wie oben für einen PIC 18 beschrieben:
Und hier ist ein ähnliches Makro für ein PIC 24 oder dsPIC 30 oder 33:
Diese beiden Beispiele werden als Makros mit meinem PIC-Assembler-Präprozessor implementiert , der leistungsfähiger ist als jede der integrierten Makrofunktionen.
quelle
Wenn Sie mit der Beschränkung einer Potenz von zwei Elementen auf einen Durchschnittswert (dh 2,4,8,16,32 usw.) leben können, kann die Aufteilung einfach und effizient auf einem leistungsschwachen Mikro ohne dedizierte Aufteilung durchgeführt werden, da dies der Fall ist kann als Bitverschiebung erfolgen. Jede Verschiebung nach rechts ist eine Zweierpotenz, zB:
oder
etc.
quelle
Es gibt eine Antwort auf einen echten Filter für den gleitenden Durchschnitt (auch "Boxcar-Filter" genannt) mit weniger Speicherbedarf, wenn Sie nichts dagegen haben, das Bild zu verkleinern. Es wird als kaskadiertes Integrator-Kamm-Filter (CIC) bezeichnet. Die Idee ist, dass Sie einen Integrator haben, dessen Differenzen Sie über einen bestimmten Zeitraum hinweg berücksichtigen, und das wichtigste speichersparende Element ist, dass Sie durch ein Downsampling nicht jeden Wert des Integrators speichern müssen. Es kann mit dem folgenden Pseudocode implementiert werden:
Ihre effektive gleitende durchschnittliche Länge ist,
decimationFactor*statesize
aber Sie müssen nur um diestatesize
Proben herum aufbewahren . Offensichtlich können Sie eine bessere Leistung erzielen, wenn Siestatesize
unddecimationFactor
Zweierpotenzen haben, sodass die Divisions- und Restoperatoren durch Verschiebungen und Masken-und-Ands ersetzt werden.Nachtrag: Ich stimme Olin zu, dass Sie immer einfache IIR-Filter vor einem Filter mit gleitendem Durchschnitt in Betracht ziehen sollten. Wenn Sie die Frequenznullstellen eines Boxcar-Filters nicht benötigen, funktioniert wahrscheinlich ein 1- oder 2-poliger Tiefpassfilter.
Wenn Sie andererseits zum Zwecke der Dezimierung filtern (indem Sie einen Eingang mit hoher Abtastrate nehmen und ihn für einen Prozess mit niedriger Abtastrate mitteln), ist ein CIC-Filter möglicherweise genau das, wonach Sie suchen. (insbesondere, wenn Sie statesize = 1 verwenden und den Ringpuffer mit nur einem einzigen vorherigen Integratorwert ganz vermeiden können)
quelle
Es gibt eine eingehende Analyse der Mathematik, die dahinter steckt, und zwar unter Verwendung des IIR-Filters erster Ordnung, den Olin Lathrop auf der bereits beschrieben hat Austausch des Stapels digitale Signalverarbeitung (enthält viele hübsche Bilder). Die Gleichung für diesen IIR-Filter lautet:
y [n] = αx [n] + (1 - α) y [n - 1]
Dies kann implementiert werden, indem nur Ganzzahlen und keine Division mit dem folgenden Code verwendet werden (möglicherweise ist ein Debugging erforderlich, während ich aus dem Speicher eingabe.)
Dieser Filter approximiert einen gleitenden Durchschnitt der letzten K Abtastwerte, indem der Wert von alpha auf 1 / K gesetzt wird. Tun Sie dies im vorhergehenden Code, indem
#define
SieBITS
auf LOG2 (K) gehen, dh für K = 16 einstellenBITS
auf 4, für K = 4BITS
auf 2 usw.(Ich überprüfe den hier aufgeführten Code, sobald ich eine Änderung erhalte, und bearbeite diese Antwort, falls erforderlich.)
quelle
Hier ist ein einpoliger Tiefpassfilter (gleitender Durchschnitt mit Grenzfrequenz = Grenzfrequenz). Sehr einfach, sehr schnell, funktioniert hervorragend und fast ohne Speicheraufwand.
Hinweis: Alle Variablen haben einen Bereich, der über die Filterfunktion hinausgeht, mit Ausnahme der in newInput übergebenen
Hinweis: Dies ist ein einstufiger Filter. Es können mehrere Stufen hintereinander geschaltet werden, um die Schärfe des Filters zu erhöhen. Wenn Sie mehr als eine Stufe verwenden, müssen Sie DecayFactor (bezogen auf die Grenzfrequenz) anpassen, um dies zu kompensieren.
Und alles, was Sie brauchen, sind diese beiden Leitungen, die an einer beliebigen Stelle platziert sind. Sie benötigen keine eigene Funktion. Dieses Filter hat eine Hochlaufzeit, bevor der gleitende Durchschnitt den des Eingangssignals darstellt. Wenn Sie diese Hochlaufzeit umgehen müssen, können Sie MovingAverage einfach auf den ersten Wert von newInput anstelle von 0 initialisieren und hoffen, dass der erste newInput kein Ausreißer ist.
(CutoffFrequency / SampleRate) hat einen Bereich zwischen 0 und 0,5. DecayFactor ist ein Wert zwischen 0 und 1, normalerweise nahe 1.
Einfach präzise Schwimmer sind für die meisten Dinge gut genug, ich bevorzuge nur Doppelschwimmer. Wenn Sie sich an Ganzzahlen halten müssen, können Sie DecayFactor und Amplitude Factor in gebrochene Ganzzahlen konvertieren, in denen der Zähler als Ganzzahl gespeichert ist und der Nenner eine ganzzahlige Potenz von 2 ist (sodass Sie die Bitverschiebung nach rechts durchführen können) Nenner anstatt sich während der Filterschleife teilen zu müssen). Wenn zum Beispiel DecayFactor = 0.99 ist und Sie Ganzzahlen verwenden möchten, können Sie DecayFactor = 0.99 * 65536 = 64881 setzen. Und jedes Mal, wenn Sie mit DecayFactor in Ihrer Filterschleife multiplizieren, verschieben Sie einfach das Ergebnis >> 16.
Weitere Informationen zu diesem hervorragenden Online-Buch, Kapitel 19 über rekursive Filter: http://www.dspguide.com/ch19.htm
PS Für das Paradigma des gleitenden Durchschnitts, einen anderen Ansatz zum Festlegen von DecayFactor und AmplitudeFactor, der für Ihre Anforderungen relevanter sein kann, nehmen wir an, Sie möchten, dass die vorherigen, etwa 6 Elemente, diskret gemittelt werden, Sie würden 6 Elemente hinzufügen und durch dividieren 6, so können Sie den AmplitudeFactor auf 1/6 und DecayFactor auf (1.0 - AmplitudeFactor) einstellen.
quelle
Mit einem einfachen IIR-Filter können Sie für einige Anwendungen einen sich bewegenden Durchschnitt schätzen.
gewicht ist 0..255 wert, hohe werte = kürzere zeitskala für avaraging
Wert = (neuer Wert * Gewicht + Wert * (256-Gewicht)) / 256
Um Rundungsfehler zu vermeiden, ist der Wert normalerweise ein langer Wert, von dem Sie nur höherwertige Bytes als "tatsächlichen" Wert verwenden.
quelle
Alle anderen haben den Nutzen von IIR gegenüber FIR und die Zweiteilungskraft gründlich kommentiert. Ich möchte nur einige Implementierungsdetails nennen. Das Folgende funktioniert gut auf kleinen Mikrocontrollern ohne FPU. Es gibt keine Multiplikation, und wenn Sie N eine Zweierpotenz halten, erfolgt die Division durch Bitverschiebung in einem Zyklus.
Grundlegender FIR-Ringpuffer: Behalte einen laufenden Puffer mit den letzten N Werten und eine laufende SUMME aller Werte im Puffer. Subtrahieren Sie bei jedem Eintreffen eines neuen Samples den ältesten Wert im Puffer von SUM, ersetzen Sie ihn durch das neue Sample, fügen Sie das neue Sample zu SUM hinzu und geben Sie SUM / N aus.
Modifizierter IIR-Ringpuffer: Halten Sie eine laufende SUMME der letzten N Werte. Jedes Mal, wenn ein neues Sample eingeht, ist SUM - = SUM / N, fügen Sie das neue Sample hinzu und geben Sie SUM / N aus.
quelle
Wie mikeselectricstuff sagte, würde ich mich für einen exponentiellen Moving Average- Filter entscheiden , wenn Sie Ihren Speicherbedarf wirklich reduzieren müssen und es Ihnen nichts ausmacht , wenn Ihre Impulsantwort exponentiell ist (anstelle eines rechteckigen Impulses) . Ich benutze sie ausgiebig. Bei diesem Filtertyp benötigen Sie keinen Puffer. Sie müssen nicht N frühere Proben speichern. Nur einer. Ihr Speicherbedarf wird also um den Faktor N verringert.
Auch dafür brauchen Sie keine Unterteilung. Nur Multiplikationen. Wenn Sie Zugriff auf Gleitkomma-Arithmetik haben, verwenden Sie Gleitkomma-Multiplikationen. Andernfalls multiplizieren Sie die Zahlen und verschieben Sie sie nach rechts. Wir sind jedoch im Jahr 2012 und ich würde Ihnen empfehlen, Compiler (und MCUs) zu verwenden, mit denen Sie mit Gleitkommazahlen arbeiten können.
Abgesehen davon, dass es speichereffizienter und schneller ist (Sie müssen keine Elemente in einem Umlaufpuffer aktualisieren), würde ich sagen, dass es auch natürlicher ist , da eine exponentielle Impulsantwort in den meisten Fällen besser mit dem Verhalten der Natur übereinstimmt.
quelle
Ein Problem mit dem IIR-Filter, das von @olin und @supercat fast berührt, aber von anderen offenbar ignoriert wird, ist, dass durch das Abrunden eine gewisse Ungenauigkeit (und möglicherweise eine Verzerrung / Verkürzung) eintritt: Angenommen, N ist eine Potenz von zwei und nur eine Ganzzahlarithmetik Mit der Rechtsverschiebung werden die LSBs des neuen Samples systematisch entfernt. Das bedeutet, dass der Durchschnitt niemals berücksichtigt, wie lang die Serie jemals sein könnte.
Nehmen Sie zum Beispiel eine langsam abnehmende Reihe an (8,8,8, ..., 8,7,7,7, ... 7,6,6,) und nehmen Sie an, dass der Durchschnitt am Anfang tatsächlich 8 ist. Die erste "7" Probe wird den Durchschnitt auf 7 bringen, unabhängig von der Filterstärke. Nur für eine Probe. Gleiche Geschichte für 6, usw. Nun denken Sie an das Gegenteil: Die Serie steigt. Der Durchschnitt bleibt für immer bei 7, bis die Stichprobe groß genug ist, um eine Änderung herbeizuführen.
Natürlich können Sie die "Verzerrung" korrigieren, indem Sie 1/2 ^ N / 2 hinzufügen, aber das wird das Präzisionsproblem nicht wirklich lösen: In diesem Fall bleibt die abnehmende Reihe für immer bei 8, bis das Sample 8-1 beträgt / 2 ^ (N / 2). Bei N = 4 bleibt der Durchschnitt beispielsweise bei Stichproben über Null unverändert.
Ich glaube, eine Lösung dafür würde bedeuten, einen Akkumulator der verlorenen LSBs zu halten. Aber ich habe es nicht weit genug geschafft, um den Code fertig zu haben, und ich bin mir nicht sicher, ob dies die IIR-Leistung in einigen anderen Fällen von Serien nicht beeinträchtigen würde (zum Beispiel, ob 7,9,7,9 dann im Durchschnitt 8 ergeben würde). .
@Olin, deine zweistufige Kaskade würde auch eine Erklärung brauchen. Meinen Sie damit, zwei Durchschnittswerte zu halten, wobei das Ergebnis der ersten in jeder Iteration in die zweite eingespeist wird? Was ist der Vorteil davon?
quelle