Forum: Digitale Signalverarbeitung / DSP / Machine Learning Filter schneller berechnen, aber wie ?


von Chris c. (chris78)


Lesenswert?

Hallo,
ich beschäftige mich gerade mit der Programmierung von IIR-Filtern. 
Meine ersten Filter habe ich auch sehr zuverlässig auf dem DSP Bord 
TMS320C6713 der Firma Texas Instruments programmiert. Da dieses Bord 
allerdings relativ teuer ist und ich die meisten Funktionen gar nicht 
benötige, habe ich mich nach einer günstigeren Lösung umgesehen. Dabei 
bin ich auf den ATmega32(µC) der Firma Atmel gestoßen, der wirklich 
günstig ist. Zudem ist der A/D-Wandler sogar noch schneller als beim 
Teaxas Instrument Bord. Mir war im Prinzip schon vorher klar, dass ich 
vermutlich Probleme bei der Lösung einer solchen Aufgabe mit einem µC 
bekomme. Schaut man sich allerdings den einfachen C-Code für ein IIR 
2.Ordnung an, kann man vielleicht nachvollziehen, warum ich es dennoch 
versucht habe.
1
// funktionen read_adc und send_dac stehen hier
2
3
void main (void)
4
 {
5
 short a0,a1,a2,b1,b2,u0=0,u1=0,u2=0,u3=0;  //Declare local variables
6
 a0 =  0.2083;     //Zählerkoeffizienten
7
 a1 =  0.4165;
8
 a2 =  0.2083;
9
 b1 =  0.0327;     //Nennerkoeffizienten
10
 b2 = -0.1996;
11
12
 while(1)
13
   {
14
   u0 = read_adc;   //Eingangswert vom AD,  
15
                    //Für Testzwecke short Wert direkt zuweisen
16
   
17
   u3 = a0*u0+u2;
18
   u2 = a1*u0-b1*u3+u1;
19
   u1 = a2*u0-b2*u3;
20
21
   send_dac = u3;     //Für Testzwecke löschen
22
   };
23
 }

Zu Testzwecken habe ich den Funktionsaufruf send_dac herausgenommen und 
u0 einen short Wert direkt zugewiesen.
Nun benötigt der ATmega32 mit 14,745 MHz Quarztakt allerdings 20µs für 
einen Durchlauf der "While(1)-Endlosschleife", was für meine späteren 
Anwendungen viel zu langsam ist.
Nun endlich zu meiner Frage: Kennt jemand eine relativ günstige Lösung 
um z.B. die zeitraubenden Multiplikationen durch einen wesentlich 
schnelleren Hardwaremultiplizierer zu berechnen?
Oder einen Prozessor, FPGA o.ä., der einen solchen Durchlauf in ca.0,1µs 
(10MHz) schafft?
Da die maximale Ordnungszahl des Filters 10 betragen wird, würde mir 
auch eine Durchlaufzeit von ca. 3,2 MHZ - 1 MHz für die 10.Ordnung 
ausreichen.

Auch Anregungen und Ideen könnten mir weiterhelfen...

MfG
Chris

von Simon K. (simon) Benutzerseite


Lesenswert?

Chris Lang wrote:
>  short a0,a1,a2,b1,b2,u0=0,u1=0,u2=0,u3=0;  //Declare local variables
>  a0 =  0.2083;     //Zählerkoeffizienten
>  a1 =  0.4165;
>  a2 =  0.2083;
>  b1 =  0.0327;     //Nennerkoeffizienten
>  b2 = -0.1996;

Du weißt, dass short ein integraler Datentyp ist? Spuckt der Compiler 
keine Warnungen aus an dieser Stelle?
Um solche Zahlen aufnehmen/berechnen zu können, benötigst du Fließkomma 
oder Fixkommaarithmetik.

von Robert S. (razer) Benutzerseite


Lesenswert?

ZU deinem Problem kann ich dir leider nicht helfen.

Du weißt aber schon, dass short ein Ganzzahldatentyp ist. Du brauchst da 
einen Gleitkommadatentyp wie float oder double....

von Chris c. (chris78)


Lesenswert?

@ Simon & razer,

Hast recht, allerdings habe ich es auch mit float und double versucht 
und eine Durchlaufzeit von 160µs (6,25KHz) gemessen.
Danke für den Hinweis.

MfG

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Erstmal musst du die Fließkomma-Rechnungen loswerden; die dauern auf dem 
AVR eine halbe Ewigkeit. Implementier das mal nur mit Integern, das 
sollte das schon mal um ein Faktor >10 beschleunigen. (EDIT: gerade 
gesehen dass du short-Variablen Float-Werte zuweist. Das kann nicht 
gehen.)

Wenn ich das richtig verstanden habe willst du mit Abtastraten im 
MHz-Bereich arbeiten; das hieße ja bei 10. Ordnung dass eine 
Multiplikation nur einen Takt dauern darf - auf dem AVR unmöglich. Ich 
würde mir vielleicht mal einen der ARM7TDMI-Controller (LPC2000, 
AT91SAM7) oder noch besser den dsPIC anschauen.

Allerdings musst du dir bei einem IIR-Filter in Festkommarechnung 
Gedanken um Quantisierungseffekte (-> Grenzzyklen) machen und 
Gegenmaßnahmen treffen (Kaskadenstruktur, Abrundung, begrenzende 
Artithmetik statt Überlauf, ...). Ganz besonders bei 10. Ordnung. Bist 
du dir sicher dass du so hohe Ordnungen überhaupt brauchst? Das macht 
nur Sinn wenn man mit extrem hoher Genauigkeit rechnet, ansonsten 
bringen dir die höheren Ordnungen nichts weil die Pol/Nullstellen nach 
der Quantisierung irgendwo im Nirvana liegen. Welche Anforderungen soll 
denn dein Filter erfüllen, bzw. womit hast du es designt?

von Benedikt K. (benedikt)


Lesenswert?

@ Andreas Schwarz
Kann es sein, dass das Forum einen Bug hat ?
Ich bin mir ziemlich sicher, hier geantwortet zu haben, und ich bin mir 
absolut sicher, dass das Ursprungstopic geändert wurde: Anfangs stand da 
nämlich noch float und 160µs. Kann es sein, dass mein Beitrag dadurch 
verloren ging ?

von Chris c. (chris78)


Lesenswert?

@ Andreas,

Habe es auch mit float Werten versucht und ein Durchlauf dauert 160µs.
Die short Zuweisung ist bei testen dazwischen gerutscht, sorry.

Andreas Schwarz wrote:

> Wenn ich das richtig verstanden habe willst du mit Abtastraten im
> MHz-Bereich arbeiten; das hieße ja bei 10. Ordnung dass eine
> Multiplikation nur einen Takt dauern darf - auf dem AVR unmöglich. Ich
> würde mir vielleicht mal einen der ARM7TDMI-Controller (LPC2000,
> AT91SAM7) oder noch besser den dsPIC anschauen.

Ich will mit ca 50KHz abtasten und dann ein Oversampling im Filter 
durchführen. Das heißt für jeden Abtastwert muß ich bei 100fach 
Oversampling 100mal den Filter mit dem gleichen Eingangswert u0 
berechnen. u1, u2 und u3 ändern sich während der 
"Oversampling-Berechnung".
Werd gleich mal die Datenblätter für den ARM-Controller durchgehen.

> Allerdings musst du dir bei einem IIR-Filter in Festkommarechnung
> Gedanken um Quantisierungseffekte (-> Grenzzyklen) machen und
> Gegenmaßnahmen treffen (Kaskadenstruktur, Abrundung, begrenzende
> Artithmetik statt Überlauf, ...). Ganz besonders bei 10. Ordnung. Bist
> du dir sicher dass du so hohe Ordnungen überhaupt brauchst? Das macht
> nur Sinn wenn man mit extrem hoher Genauigkeit rechnet, ansonsten
> bringen dir die höheren Ordnungen nichts weil die Pol/Nullstellen nach
> der Quantisierung irgendwo im Nirvana liegen. Welche Anforderungen soll
> denn dein Filter erfüllen, bzw. womit hast du es designt?

Ich soll analoge RC-Kettenglieder (siehe auch Beitrag 
"Übertragungsfunktion RC-Kettenschaltung" im DSP-Forum) nachbilden und 
die gehen leider bis zur 8.Ordnung. Gibt es denn evtl. eine Möglichkeit 
die Koeffizienten mit Hilfe von Matlab o.ä. zu "Integer" Werten zu 
transformieren?
Sonst muss ich doch spätestens bei der Verstärkung wieder mit float 
mutiplizieren, da die Werte sonst zu hoch werden?
Werde gleich mal unter begrenzende Artithmetik suchen.

Um die analogen Filtekoeffizienten in digitale zu wandeln habe ich 
MatLab benutzt, und das hat super geklappt, gibt es hierfür evtl. auch 
eine MatLab Funktion.

MfG

von Chris c. (chris78)


Lesenswert?

Hallo zusammen,

habe gerade versucht den short Wert wieder in float zu ändern, da es vom 
Testen noch falsch drin steht.
Dabei ist auch von mir ne Antwort irgendwie verloren gegangen.
Habe es mit float Werten und den richtigen Koeffizienten gemessen --> 
160µs.
Danach einfach mal mit short Werten und falschen Koeffizienten --> 20µs, 
so ist der Feheler reingerutscht.

Kann ich denn die Koeffizienten einfach um den Faktor 10.000 erhöhen und 
später wieder ohne float wert dämpfen (ohne mit 0.0001 zu 
multiplizieren), oder wie funktioniert die Transformation vom 
"Float-Filter" zum "Integer-Filter"?

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Chris Lang wrote:
> Kann ich denn die Koeffizienten einfach um den Faktor 10.000 erhöhen und
> später wieder ohne float wert dämpfen (ohne mit 0.0001 zu
> multiplizieren), oder wie funktioniert die Transformation vom
> "Float-Filter" zum "Integer-Filter"?

Im Prinzip so wie du geschrieben hast: die Koeffizienten so skalieren 
dass sie in deinen Wertebereich passen, und das Ergebnis der 
Rechenoperation auf die gewünschte Bitbreite abschneiden/runden. Wie man 
diese Skalierung genau macht ist bei IIR-Filtern eine Kunst für sich. 
Es gibt kein Patentrezept, man muss simulieren, und genau das würde ich 
an deiner Stelle erst mal machen.

Der erste Schritt sind die Koeffizienten: schau an was der Filter tut, 
wenn man statt mit den vom Filterdesigner berechneten Koeffizienten (in 
quasi unbeschränkter 64 Bit Float-Genauigkeit) mit den quantisierten 
Koeffizienten rechnet; bei 16 Bit und einem IIR-Filter 10ter Ordnung 
wird das nicht mehr viel mit der gewünschten Übertragungsfunktion zu tun 
haben.

Danach kann man sich Gedanken darüber machen wie man die 
Quantisierungsfehler beim Rechnen in den Griff bekommt (Bitbreite, 
Struktur, Grenzzyklen usw.); analytisch kommt man da nicht weit, man 
muss simulieren um herauszufinden ob die Fehler akzeptabel sind.

> Ich soll analoge RC-Kettenglieder (siehe auch Beitrag "Übertragungsfunktion
> RC-Kettenschaltung" im DSP-Forum) nachbilden und die gehen leider bis zur
> 8.Ordnung.

Das halte ich für keine gute Idee. Digital ist nicht Analog, man kann 
nicht einfach analoge Lösungen nehmen und 1:1 auf digitale Hardware 
umsetzen. Besser ausgehend von der Spezifikation eine richtige digitale 
Lösung entwickeln. Wie ist denn deine Spezifikation, also welcher 
konkrete Zweck steckt eigentlich hinter der ganzen Sache?

> Gibt es denn evtl. eine Möglichkeit die Koeffizienten mit Hilfe
> von Matlab o.ä. zu "Integer" Werten zu transformieren?

Wenn ich mich recht erinnere kann der Matlab-Filterdesigner auch direkt 
die Koeffizienten in gewünschter Bitbreite ausgeben.

(EDIT 23:43)

von Chris c. (chris78)


Lesenswert?

Hi,

ich merke schon, ich werde bei der Zwerierkomplementdarstellung landen.
Meld mich wenn ich das gelöst habe, bis dahin würde ich mir gerne auch 
noch ein paar weitere Controller empfehlen lassen, die für meine 
Anforderungen evtl. ausreichen könnten, um vergleichen zu können.

MfG

von Detlef _. (detlef_a)


Lesenswert?

50ksamples/s, 100fach interpoliert, 5 Multiplikation/Additionen (MAC) 
pro Runde macht 25MegaMACs, das kannste mit nem uC getrost vergessen, 
der ARM schafft das vermutlich auch nicht, auch nicht in integer. 8fach 
Kettenleiter sind ja auch nicht mit 5Multiplikationen zu erschlagen. So 
verlangt das nach nem leicht- bis mittelgewichtigem DSP, so einer, wie 
Du schon hattest.

Aber vielleicht läßt sich der Algorithmus noch bißchen tweaken? 50ks/s 
ist Deine Abtastrate für die Kettenleiter? Warum machst Du 100fach 
Oversampling? Wo liegen die Pole der Kettenleiter? Bis zu welchen 
Frequenzen möchtest Du die Geschichte simulieren?

So viele Fragen.
Cheers
Detlef

von Chris c. (chris78)


Lesenswert?

Hi,

werde meine MatLab Simulation dazu benutzen, probiere es auch mal mit 
einer Zwerierkomplementdarstellung um negative Werte darstellen zu 
können.

> Das halte ich für keine gute Idee. Digital ist nicht Analog, man kann
> nicht einfach analoge Lösungen nehmen und 1:1 auf digitale Hardware
> umsetzen.

Ich habe erst die Zeitkonsatnte der analogen RC-Glieder bestimmt und 
dann die analogen Filterkoeffizienten. Diese Koeffizienten habe ich in 
Matlab mit Hilfe der bilinearen Transformation in die digitalen 
Filterkoeffizienten (unter Angabe der Filtersamplefrequenz) gewandelt.
Die bilineare Transformation dient zur Frequenzapproximation des anlogen 
Filters durch einen digitalen (Zeitapproximation mit impulsinvarianter 
Nachbildung).

Aufgabe:
Im Labor der Schule steht ein analoges "Kanalmodell" zur Nachbildung der 
Verzerrungen eines Digitalsignals auf Leitungen. Hinter das Kanalmodell 
wird ein oszi geschaltet, bei dem man je nach Erhöhung der Ordnungszahl 
beobachten kann, wie sich das Augendiagramm schließt. Später wird dann 
ein Entzerrer zwischen Bit-Generator und Kanalmodell geschaltet und das 
ganze unter dem Praktikumsversuch "Entzerrung von Digitalsignalen 
zusammengefaßt.

Meine Aufgabe könnte es werden das analoge Kanalmodell durch ein 
digitales Computerunabhängiges (evtl. nur die Bedienoberfläche über USB 
oder RS232) zu ersetzen, da jedes der 6 vorhandeenen Modelle durch 
diverse Störungseinflüße und Toleranzen andere Eigenschaften aufweist.

Werde mich erstmal an die Zweierkomplementwandlung und die Simulation in 
Matlab machen.

Des weiteren bin ich für weitere Controller Empfehlungen sehr dankbar um 
vergleichen zu können.

MfG

von Chris c. (chris78)


Angehängte Dateien:

Lesenswert?

Hallo Detlef,

Meine Einagansbitfolge kommt mit einer Geschwindigkeit von 64Kbit/s
das heißt ich muss mit mit 64KHz synchron abtasten, um jedes Bit zu 
erfassen.
Die Matlab7.0 Simulink Simulation (siehe Anhang) zeigt, das ca.25fach 
Oversampling also 1,6MHz Filtersamplefrequenz zur anschließenden 
Rekonstruktion ausreicht. Wieviel MegaMACs würde das denn bei 10.Ordnung 
machen und wie krieg ich das in eine Zeit umgerechnet?

In der Simulation sind die Koeffizienten noch mit 100KHz berechnet. Die 
Filterkoeffizienten können je nach Oversamplingfrequenz nach der unter 
dem Beitrag "Impulsantwort Tiefpaß 2.Ordnung" ganz unten beschrieben 
Methode an z.B. 1,6MHz angepasst werden.

Deutlich erkennt man anhand der Oszilloskopbilder exakt das gleiche 
Verhalten von analog Filter (transfer Fcn), digitaler Filter nach der 
bilinearen Methode, Impulsinvarianten Methode und meiner Handrechnung 
ganz unten.

MfG

von Detlef _. (detlef_a)


Lesenswert?

Hi, das Simulink Modell kann ich nicht lesen, mein Simulink ist dafür zu 
alt, ich benutze Simulink auch selbst nie. Kenne mich ebenfalls mit dem 
Umlügen von kontinuierlichen Systemen in digitale nicht gut aus, aber 
eine 25fache Überabtastung fühlt sich für mich nicht sehr effektiv an.

Ein 10 tap IIR mit 1.6Ms/s hat 11 Vorwärts- und 10 
Rückwärtskoeffizienten,, benötigt also (10+11)*1.6 MegaMACS pro Sekunde.

>>wie krieg ich das in eine Zeit umgerechnet

Wieso Zeit? Die Berechnung des Filters erfordert z.B. 25 MegaMACs 
(multiply/accumulate) pro Sekunde. Hat dann Prozessor X 2 
Multiplizierer, die 10 Takte pro Multiplikation/Adiition brauchen, muß 
der Prozessor mit 125 Mhz laufen.

>>Des weiteren bin ich für weitere Controller Empfehlungen sehr dankbar um
vergleichen zu können.<<

Ich würde sowas mit nem FPGA aufbauen, z.B. diesem Spartan 3 evalboard. 
Die Dinger haben, glaube ich, mehrere Multiplizierer drin und lassen 
sich mit etlichen 100MHz takten. Da kann so mancher DSP nicht 
gegenanstinken. Außerdem ist Signalverarbeitung auf FPGAs zukunftsfähig, 
man lernt mal VHDL und kann sehr flotte Sachen basteln.

Gute Nacht
Detlef

von Chris c. (chris78)


Lesenswert?

@ Detlef,

das mit den MeagMACs ist jetzt klar geworden und daran kann ich dann 
auch den passenden FPGA auswählen.
Mein Kollege schwärmt total von dem Spartan 3, allerdings hat mich die 
VHDL Programmierung bisher zurückgehalten, aber die Zeit scheint wohl 
reif...

Vielen Dank für Deine Mühe, (übrigens läuft die Simulation auf Matlab 
4.2 bei mir auch nicht so ohne weiteres).

MfG

von Christoph H. (Gast)


Lesenswert?

Für die Atmegas gibt es eine Filter Application Note von Atmel.

Geschwindigkeit:

2 pol. IIR-Filter: 100Ksamples

Gruss,
Christoph

Bitte 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
Noch kein Account? Hier anmelden.