Zyklische Faltung
Die zyklische Faltung, auch als zirkulare Faltung oder als periodische Faltung bezeichnet, ist in der Funktionalanalysis eine Form der diskreten Faltung. Dabei werden Folgen der Länge periodisch fortgesetzt, welche sich durch die zyklische Verschiebung der Folge ergeben. Anwendung der zyklischen Faltung liegen primär in der digitalen Signalverarbeitung, beispielsweise zur Realisierung von digitalen Filtern.
Allgemeines
In Kombination mit der diskreten Fourier-Transformation (DFT), insbesondere der schnellen Fourier-Transformation (FFT), kann mit der zyklischen Faltung die rechenintensive diskrete aperiodische Faltungsoperation im Zeitbereich durch eine effizientere Multiplikation im Spektralbereich ersetzt werden. Die periodische Faltung hat in dem blockbasierenden Aufbau des FFT-Algorithmus ihren Ursprung.
Zur Bildung der schnellen Faltung wird die zyklische Faltung durch schnelle Fouriertransformation und Verfahren wie dem Overlap-Save-Verfahren oder Overlap-Add-Verfahren erweitert, mit dem Ziel nichtrekursive Digitalfilter (FIR-Filter) höherer Ordnung effizient zu realisieren. Herkömmliche FIR-Filter in der direkten Normalform führen unmittelbar die aperiodische Faltungsoperation aus, welche ab ca. 50 Filterordnung ineffizienter als die schnelle Faltung ist.
Die zyklische Verschiebung um Stellen einer Folge der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} kann mit der Modulooperation ausgedrückt werden:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x[n-m] = x[(n-m) \bmod N]}
wobei periodisch fortgesetzte Folgen mit dem Tildesymbol gekennzeichnet sind. In nebenstehender Abbildung sind links zwei beispielhafte Folgen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_2} der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = 4} und deren aperidoisches Faltungsergebnis dargestellt. Rechts dazu deren periodisch fortgesetzten Folgen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x_1} und und das daraus gebildete zyklische Faltungsprodukt .
Literatur
- Alan V. Oppenheim, Ronald W. Schafer: Zeitdiskrete Signalverarbeitung. 3. Auflage. Oldenbourg, 1999, ISBN 3-486-24145-1.