Überlappungs-Add-Methode

In der Signalverarbeitung ist die Überlappungs-Add-Methode ein effizientes Verfahren zur Auswertung der diskreten Faltung eines sehr langen Signals mit einem FIR-Filter ( Finite Impulse Response ) :${\displaystyle x[n]}$${\displaystyle h[n]}$

wo außerhalb der Region${\displaystyle h[m]=0}$${\displaystyle m}$${\displaystyle [1,M].}$ 

In diesem Artikel werden gängige abstrakte Notationen verwendet, wie z. B. oder , bei denen davon ausgegangen wird, dass die Funktionen in ihrer Gesamtheit und nicht zu bestimmten Zeitpunkten betrachtet werden sollten (siehe Faltung#Notation ). ${\textstyle y(t)=x(t)*h(t),}$${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$${\textstyle t}$

Das Konzept besteht darin, das Problem in mehrere Faltungen mit kurzen Segmenten von zu unterteilen :${\displaystyle h[n]}$${\displaystyle x[n]}$

${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}$

wobei eine beliebige Segmentlänge ist. Dann :${\displaystyle L}$

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}$

und kann als Summe kurzer Faltungen geschrieben werden : ^{[ 1 ]}${\displaystyle y[n]}$

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}$

wobei die lineare Faltung außerhalb des Bereichs null ist. Und für jeden Parameter ^{[ A ]} ist sie äquivalent zur -Punkt -Kreisfaltung von mit im Bereich.   Der Vorteil besteht darin, dass die Kreisfaltung gemäß dem Kreisfaltungssatz effizienter berechnet werden kann als die lineare Faltung :${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,}$${\displaystyle [1,L+M-1].}$${\displaystyle N\geq L+M-1,\,}$${\displaystyle N}$${\displaystyle x_{k}[n]\,}$${\displaystyle h[n]\,}$${\displaystyle [1,N].}$

Wo :

• DFT _N und IDFT _N bezeichnen die diskrete Fourier-Transformation und ihre Inverse, ausgewertet über diskrete Punkte, und${\displaystyle N}$
• ${\displaystyle L}$Üblicherweise wird so gewählt, dass es sich um eine Zweierpotenz handelt, und die Transformationen werden aus Effizienzgründen mit dem FFT- Algorithmus implementiert .${\displaystyle N=L+M-1}$

Nachfolgend die Pseudocode -Darstellung des Algorithmus :

( Überlappungs-Add-Algorithmus für lineare Faltung ) h = FIR-Filter M = Länge(h) Nx = Länge(x) N = 8 × 2^ceiling( log2(M) ) (8 mal die kleinste Zweierpotenz größer als die Filterlänge M. Siehe nächsten Abschnitt für eine etwas bessere Wahl.) Schrittweite = N - (M-1) (L im obigen Text) H = DFT(h, N) Position = 0 y(1 : Nx + M-1) = 0 solange Position + Schrittweite ≤ Nx tue y(position+(1:N)) = y(position+(1:N)) + IDFT(DFT(x(position+(1:step_size)), N) × H) Position = Position + Schrittweite Ende

Wenn DFT und IDFT durch den FFT-Algorithmus implementiert werden, benötigt der obige Pseudocode etwa N (log₂ ₍ N) + 1) komplexe Multiplikationen für die FFT, das Produkt von Arrays und die IFFT. ^{[ B ]} Jede Iteration erzeugt N-M+1 Ausgabewerte, sodass die Anzahl der komplexen Multiplikationen pro Ausgabewert etwa beträgt :

Wenn beispielsweise und Gl. 3 gleich ist , würde die direkte Auswertung von Gl. 1 bis zu komplexen Multiplikationen pro Ausgabewert erfordern, wobei der ungünstigste Fall eintritt, wenn sowohl als auch komplexwertig sind. Beachten Sie außerdem, dass Gl. 3 für jedes gegebene ein Minimum bezüglich besitzt. Abbildung 2 zeigt die Werte von , die Gl. 3 für verschiedene Filterlängen minimieren ( ). ${\displaystyle M=201}$${\displaystyle N=1024,}$${\displaystyle 13.67,}$${\displaystyle 201}$${\displaystyle x}$${\displaystyle h}$${\displaystyle M,}$${\displaystyle N.}$${\displaystyle N}$${\displaystyle M}$

Anstelle von Gl. 1 können wir auch Gl. 2 auf eine lange Folge von Längenabtastwerten anwenden . Die Gesamtzahl der komplexen Multiplikationen wäre dann: ${\displaystyle N_{x}}$

${\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}$

Im Vergleich dazu ist die Anzahl der komplexen Multiplikationen, die der Pseudocode-Algorithmus benötigt, folgende:

${\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}$

Daher skalieren die Kosten der Überlappungs-Additions-Methode nahezu proportional zu den Kosten einer einzelnen, großen kreisförmigen Faltung . Die beiden Methoden werden auch in Abbildung 3 verglichen, die mittels MATLAB- Simulation erstellt wurde. Die Konturen stellen Linien mit konstantem Verhältnis der Laufzeiten beider Methoden dar. Ist die Überlappungs-Additions-Methode schneller, übersteigt das Verhältnis 1, und es werden sogar Werte bis zu 3 beobachtet. ${\displaystyle O\left(N_{x}\log _{2}N\right)}$${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$

• Überlappungs-Speichermethode
• Zirkuläre Faltung#Beispiel

• Oppenheim, Alan V.; Schafer, Ronald W. (1975). Digitale Signalverarbeitung . Englewood Cliffs, NJ: Prentice-Hall. ISBN 0-13-214635-5Die
• Hayes, M. Horace (1999). Digitale Signalverarbeitung . Schaum's Outline Series. New York: McGraw Hill. ISBN 0-07-027389-8Die
• Senobari, Nader Shakibay; Funning, Gareth J.; Keogh, Eamonn; Zhu, Yan; Yeh, Chin-Chia Michael; Zimmerman, Zachary; Mueen, Abdullah (2019). „Super-Efficient Cross-Correlation (SEC-C): Ein schneller Matched-Filtering-Code für Desktop-Computer“ (PDF) . Seismological Research Letters . 90 (1): 322–334 . doi : 10.1785/0220180122 . ISSN  0895-0695 .