Hallo zusammen,
für ein aktuelles Projekt möchte ich die Kreuzkorrelation zweier
zeitdiskreter Signale auf einem uC berechnen. Verwenden möchste ich
einen Atmel SAMD21 Controller. Meine Frage bezieht sich aber nur auf die
Mathematik der Berechnung bzw. der implementierung in c-Code.
Die Signale möchte ich für den den Test zunächst nur "simulieren" d.h.
ich habe mir zwei "perfekte" Sinus (0->2pi) Signale mit einer
Phasenverschiebung von pi/4 zueinander als diskrete Werte mit 100
Datenpunkten in zwei Arrays gespeichtert.
Ziel meiner Berechung ist es, möglichst genau zu berechnen in welchem
zeitlichen Abstand die beiden Signale zueinander verschoben sind. Hierzu
meine Frage:
Kann ich die Kreuzkorrelation der beiden Signale für alle möglichen
Zeitverschiebungen berechen und dann nur noch nachschauen, bei welcher
Zeitverschiebung die "Überlappung" beider Signale am größten ist?
D.h. die beiden Signale können ja maximal 100 Datenpunkte außeinander
liegen und bei einer der 100 möglichen Verschiebungen müsste das
Ergebnis der Kreuzkorrelationsfunktion am größten sein. Oder bin ich mit
der Methode eher aufm dem Holzweg?
In meinem Programmcode würde das dann bedeuten ich müsste 100 mal die
Kreuzkorrelation der beiden Signale berechnen, wobei jede dieser
Berechnungen wieder aus 100 mal "Aufsummieren" der Produkte bestehen
würde. Ohne es bisher getestet zu haben scheint mir das ganz schön viel
Rechenaufwand für den uC zu sein.
Danke für eure Hilfe.
. . schrieb im Beitrag
#6089507:
> Versuch es mit FFT
Ja klar!
Dominik W. schrieb:> ganz schön viel Rechenaufwand für den uC zu sein
Deshalb nimmt man normalerweise einen DSP dafür...
Gruss Chregu
Dominik W. schrieb:> Ohne es bisher getestet zu haben scheint mir das ganz schön viel> Rechenaufwand für den uC zu sein.
Um genau zu sein: es sind 100x100 = 10000 Multiplikationen.
Auch für einen uC durchaus machbar, die Frage ist halt, wie oft pro
Sekunde erwartet man ein Ergebnis.
Christian M. schrieb:> Deshalb nimmt man normalerweise einen DSP dafür...
Mit einem DSP hab ich bisher noch nicht gearbeitet, aber vieleicht ist
das ja jetzt die richtige Gelegenheit dazu, danke.
Joe F. schrieb:> Um genau zu sein: es sind 100x100 = 10000 Multiplikationen.> Auch für einen uC durchaus machbar, die Frage ist halt, wie oft pro> Sekunde erwartet man ein Ergebnis.
Ich denke auch, dass ich da am Ende von der Rechenzeit des uCs auf eine
maximale Aktuallisierungsrate limitiert sein werde.
Dominik W. schrieb:> Kann ich die Kreuzkorrelation der beiden Signale für alle möglichen> Zeitverschiebungen berechen und dann nur noch nachschauen, bei welcher> Zeitverschiebung die "Überlappung" beider Signale am größten ist?
Nachdem niemand etwas gegen diese Methode gesagt hat, gehe ich mal davon
aus, dass ich damit richtig liegen könnte und werde anfangen das so zu
implementieren, danke.
Falls doch noch jemand einen effizienteren Weg kennt, würde ich mich
natürlich nochmal über eine Antwort freuen.
Dominik W. schrieb:> Falls doch noch jemand einen effizienteren Weg kennt, würde ich mich> natürlich nochmal über eine Antwort freuen.
FFT (bzw genauer: Faltung mittels FFT und IFFT) wurde ja genannt. Ist
mit Sicherheit schneller, aber auch deutlich komplizierter zu
implementieren.
Joe F. schrieb:> FFT (bzw genauer: Faltung mittels FFT und IFFT) wurde ja genannt. Ist> mit Sicherheit schneller, aber auch deutlich komplizierter zu> implementieren.
Sehe ich auch so, diese Art der Berechnung sollte deutlich schneller
sein
Auch auf die Gefahr hin das gleich jemand um die Ecke kommt und rum
meckert in der CMSIS lib ist eine Implementierung für die FFT vorhanden.
Davon abgesehen hält sich die Komplexzeit für die eigene Implementierung
im Rahmen.
Vereinfachen wir mal: die LUT hat 180 Einträge für ein Grad
Phasenauflösung. Wenn ich dann zwei Samples aufnehme, kann ich durch
Subtraktion einfach die Phadendifferenz der Signale ermitteln?
1000V Dc schrieb:> Vereinfachen wir mal: die LUT hat 180 Einträge für ein Grad> Phasenauflösung. Wenn ich dann zwei Samples aufnehme, kann ich durch> Subtraktion einfach die Phadendifferenz der Signale ermitteln?
nein
1000V Dc schrieb:> Also man subtrahiert nicht die Samples sondern dir Indexe ihre> Entsprechung in der LUT. Der so berechnete Index gibt die> Phasendifferenz an...
Ahja, wieder was gelernt.
Dominik W. schrieb:> Hallo zusammen,>> Kann ich die Kreuzkorrelation der beiden Signale für alle möglichen> Zeitverschiebungen berechen und dann nur noch nachschauen, bei welcher> Zeitverschiebung die "Überlappung" beider Signale am größten> In meinem Programmcode würde das dann bedeuten ich müsste 100 mal die> Kreuzkorrelation der beiden Signale berechnen, wobei jede dieser> Berechnungen wieder aus 100 mal "Aufsummieren" der Produkte bestehen
Ja, der Aufwand der brute force Kreuzkorrrelation steigt mit dem Quadrat
der Anzahl der samples, Auflösung ist ein sample.
Die Kreuzkorrelation kann man auch per FFT berechnen, dann ist der
Aufwand kleiner, O(n*log(n)), Auflösung immer noch ein sample.
Oder man nimmt direkt das Ergebnis der FFT und vergleicht die Phasen,
Auflösung besser als ein sample. Wenn eine Sinuswelle nicht genau in das
'Betrachtungsfenster' reinpaßt muss man Maßnahmen treffen, ist ein
eigenes Thema.
Man brechnet die Phase mit dem Görtzel-Algorithmus, das nennen die
Kommunikationstechniker 'runtermischen mit einem komplexen Träger'. Die
Auflösung ist besser als ein sample, man muss die Frequenz genau wissen.
Wenn man die Frequenz nicht so genau kennt geht das mit
Beitrag "Frequenz, Amplitude und Phase eines Sinussignals bestimmen"
und einem Phasenvergleich, subsample Auflösung aber qudratischer Aufwand
O(n^2).
Cheers
Detlef
"subsample Auflösung"
Das ist wie, wenn Du dir die erste, die letzte Folge und irgendeine aus
der Mitte von GoT ansiehst, und daraus den Inhalt der restlichen Folgen
bestimmst ;)
. . schrieb im Beitrag
#6096985:
> "subsample Auflösung"> Das ist wie, wenn Du dir die erste, die letzte Folge und irgendeine aus> der Mitte von GoT ansiehst, und daraus den Inhalt der restlichen Folgen> bestimmst ;)
Nein, ist es nicht. Das ist Signalverarbeitung. Lernt man nich bei
GoTKucken.
Cheers
Detlef
probier deinen Prototypen mit Matlab aus. Da geht eine Kreuzkorrelation
mit zwei fft in eine einzige Codezeile rein. Daten dann über File oder
live Schnittstelle draufgeben. Die heutigen PCs sind von der
Rechenleistung überraschend schnell, (sogar noch mit Matlab). Du siehst
dann was funktioniert und wie lange es dauert um einen Anhaltspunkt zu
kriegen was du auf einer eigenen Hardware brauchst. An der gleichen
Sache bin ich mal mit FPGA gescheitert weil 22 bit Breite nötig gewesen
wäre und die Bibliotheken bei 20 bit aufhören.
Dominik W. schrieb:> Oder bin ich mit> der Methode eher aufm dem Holzweg?
Das kommt darauf an, was du im Endeffekt willst, wie die
Rahmenbedingungen aussehen, und was du über das zu erwartende Signal von
vornherein schon weisst.
Mitunter kann eine Abwandlung bzw Weiterentwicklung von Korrelation eine
elgante Lösung sein, manchmal eine Ressourcenvergeudung und sehr oft
kommt es auf das Selbe raus, ob du korrelierst oder fourrieranalysierst.
