mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP diskrete Kreuzkorrelation berechnen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Dominik W. (do0zy)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von . . (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
Versuch es mit FFT.

von Christian M. (Firma: magnetmotor.ch) (chregu) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
.                                                . 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

von Joe F. (easylife)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Dominik W. (do0zy)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von Joe F. (easylife)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Guest (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von 1000V Dc (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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?

von . . (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von 1000V Dc (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Warum?

von 1000V Dc (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Also man subtrahiert nicht die Samples sondern dir Indexe ihre 
Entsprechung in der LUT. Der so berechnete Index gibt die 
Phasendifferenz an...

von . . (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Detlef _. (detlef_a)


Bewertung
0 lesenswert
nicht lesenswert
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

von . . (Gast)


Bewertung
0 lesenswert
nicht lesenswert
"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 ;)

von Detlef _. (detlef_a)


Bewertung
0 lesenswert
nicht lesenswert
.                                                . 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

von J. V. (janvi)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von BlueSky (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von SysIngMue (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Detlef _. schrieb:
> GoTKucken

kucken?

von Detlef _. (detlef_a)


Bewertung
0 lesenswert
nicht lesenswert
SysIngMue schrieb:
> Detlef _. schrieb:
>> GoTKucken
>
> kucken?

https://www.duden.de/rechtschreibung/kucken

Kuck da ma, Systemingenieur, bayerischer.

Cheers
Detlef

: Bearbeitet durch User
von Joe F. (easylife)


Bewertung
0 lesenswert
nicht lesenswert
Schau schau, da kiek mal einer guck.

von bluesky (Gast)


Bewertung
0 lesenswert
nicht lesenswert
gödoschaugst

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.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.