Implementierung Kreuzkorrelation

[Supa M. (supa_micha)]

Hi,

ich hoffe, ihr könnt mir helfen. Und zwar führe ich eine 
Kreuzkorrelation zwischen zwei Signalen durch:

// alle Variablen als int16_t deklariert
#undef  STEP
#define STEP(k) (s1[k] * s2[k - lambda])

  for (lambda = 40; lambda <= 120; lambda++) 
  {   
    int32_t  result;

    L_result  = STEP(0);  L_result += STEP(1);
    L_result += STEP(2);  L_result += STEP(3);
    L_result += STEP(4);  L_result += STEP(5);
    L_result += STEP(6);  L_result += STEP(7);
    L_result += STEP(8);  L_result += STEP(9);
    L_result += STEP(10); L_result += STEP(11);
    L_result += STEP(12); L_result += STEP(13);
    L_result += STEP(14); L_result += STEP(15);
    L_result += STEP(16); L_result += STEP(17);
    L_result += STEP(18); L_result += STEP(19);
    L_result += STEP(20); L_result += STEP(21);
    L_result += STEP(22); L_result += STEP(23);
    L_result += STEP(24); L_result += STEP(25);
    L_result += STEP(26); L_result += STEP(27);
    L_result += STEP(28); L_result += STEP(29);
    L_result += STEP(30); L_result += STEP(31);
    L_result += STEP(32); L_result += STEP(33);
    L_result += STEP(34); L_result += STEP(35);
    L_result += STEP(36); L_result += STEP(37);
    L_result += STEP(38); L_result += STEP(39);

    if (result > max) 
    {
      x   = lambda;
      max = result;
    }
  }

Eigentlich interessiert mich aber nur die Stelle der maximalen 
Kreuzkorrelation und der entsprechende Wert. Letztendlich benötige ich 
für die Berechnung also eine Menge Rechenzeit (um nicht zu sagen, zu 
viel), obwohl mich nur ein Wert interessiert. Gibt es eine Möglichkeit, 
hier ohne eine vollständige Kreuzkorrelation auszukommen? Oder evtl. 
eine einfache Abschätzung, mit der ich dann die Suche nach dem Maximum 
auf einige wenige Berechnungen begrenzen kann?

Vielleicht habt ihr eine Idee? Mir ist leider bislang nichts eingefallen 
:-(

Vielen dank schonmal im Vorraus!
Viele Grüße
Michael

[der mechatroniker (Gast)]

Wenn der zu erwartende Peak nicht allzu scharf ist, sollte es doch 
reichen, jeden 10. Wert zu berechnen. Dann kann man an den Stellen, die 
interessant werden könnten (Umgebung der relativen Maxima), die 
restlichen Werte bestimmen.

[Detlef _. (detlef_a)]

Korrelation ist über die FFT berechenbar:

a korreliert mit b = ifft(fft(a)*conjugiert komplex(fft(b)))

Enweder direkt, wie Du das machst, oder über die FFT. Sonst gibs da 
keine Tricks, da muß man viel rechnen.


Cheers
Detlef

[Supa M. (supa_micha)]

Entschuldigung, dass ich mich so pät erst wieder melde. Ich war Ende der 
letzten Woche unterwegs und hatte so keine Zeit, weiterzuarbeiten.

@der mechatroniker:
Deine Idee ist echt gut. Habe mir daraufhin mal die Ergebnisse der 
Kreukorellation aufzeichen lassen. Leider weisen sie überhaupt keine 
Stetigkeit auf. Schade!

@Detlef:
Daran habe ich auch zunächst gedacht. Da ich vor allem nur das Maximum 
benötige, bräuchte ich keine vollständige IFFT durchführen. Nach ersten 
Berechnungen sind aber meine Datenblöcke zu kurz, damit sich das lohnen 
würde.

Dennoch habe ich es jetzt sowiet optimiert, wie es für mcih ausreicht. 
Und zwar sind die Werte von s1 fourierverteilt, d.h. kleine Werte kommen 
sehr sehr häufig vor. Damit ist es bedeutend schneller (Faktor 5), die 
Werte entsprechend aufzuaddieren anstand eine vollständige 
Multiplikation durchzuführen.

Viele Grüße
Michael