Zyklische Faltung

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 N 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

Vergleich diskrete aperiodische Faltung, linke Spalte, und rechts diskrete zyklische Faltung

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 m Stellen einer Folge x[n] der Länge N kann mit der Modulooperation ausgedrückt werden:

\tilde x[n-m] = x[mod_N (n-m)]

wobei periodisch fortgesetzte Folgen mit dem Tildesymbol gekennzeichnet sind. In nebenstehender Abbildung sind links zwei beispielhafte Folgen x1 und x2 der Länge N = 4 und deren aperidoisches Faltungsergebnis dargestellt. Rechts dazu deren periodisch fortgesetzten Folgen \tilde x_1 und \tilde x_1 und das daraus gebildete zyklische Faltungsprodukt \tilde x_1 * \tilde x_2.

Literatur

  • Alan V. Oppenheim, Ronald W. Schafer: Zeitdiskrete Signalverarbeitung. 3. Auflage. Oldenbourg, 1999, ISBN 3-486-24145-1.

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Zyklische Matrix — In der linearen Algebra bezeichnet man eine Matrix als zyklisch oder zirkulant, wenn ihre Zeilen und Spalten eine bestimmte Permutationsbedingung erfüllen. Wegen des unten beschriebenen Zusammenhangs mit der diskreten schnellen Fourier… …   Deutsch Wikipedia

  • Schnelle Faltung — Die Schnelle Faltung ist ein Algorithmus zur Berechnung der diskreten, aperiodischen Faltungsoperation mit Hilfe der schnellen Fourier Transformation (FFT). Dabei wird die rechenintensive aperiodische Faltungsoperation im Zeitbereich durch eine… …   Deutsch Wikipedia

  • Diskrete Faltung — In der Mathematik und besonders in der Funktionalanalysis beschreibt die Faltung einen mathematischen Operator, der für zwei Funktionen f und g eine dritte Funktion liefert. Diese gibt eine Art „Überlappung“ zwischen f und einer gespiegelten und… …   Deutsch Wikipedia

  • Segmentierte Faltung — Die segmentierte Faltung (englisch overlap add, OA, OLA) ist ein Verfahren zur Schnellen Faltung und wird in der digitalen Signalverarbeitung eingesetzt. Dabei wird eine Eingangsfolge in einander überlappende Teilfolgen zerlegt und die… …   Deutsch Wikipedia

  • Bluestein-FFT-Algorithmus — Der Bluestein FFT Algorithmus (1968), normalerweise als Chirp z Transformation bezeichnet (1969, englisch chirp, dt. »zirpen«), ist ein FFT Algorithmus, der die Diskrete Fourier Transformation (DFT) von Datenmengen beliebiger Größe… …   Deutsch Wikipedia

  • Filter mit endlicher Impulsantwort — Ein Filter mit endlicher Impulsantwort (englisch finite impulse response filter, FIR Filter, oder manchmal auch Transversalfilter genannt) ist ein diskreter, meist digital implementierter Filter und wird im Bereich der digitalen… …   Deutsch Wikipedia

  • Overlap-Save-Verfahren — Das Overlap Save Verfahren ist ein Verfahren zur Schnellen Faltung. Dabei wird im Gegensatz zu dem Overlap Add Verfahren die Eingangsfolge x[n] in einander überlappende Teilfolgen zerlegt. Aus den gebildeten periodischen Faltungsprodukten… …   Deutsch Wikipedia

  • Zirkulante Matrix — Eine zirkulante Matrix ist eine spezielle Toeplitz Matrix, bei der jeder Zeilenvektor relativ zum darüberliegenden Zeilenvektor um einen Eintrag nach rechts verschoben ist. Anders ausgedrückt ist sie ein Beispiel für ein Lateinisches Quadrat.… …   Deutsch Wikipedia

  • NTRUEncrypt — ist ein asymmetrisches Verschlüsselungsverfahren, das 1996 von den Mathematikern J. Hoffstein, J.Pipher und J.H. Silverman entwickelt wurde. Es basiert lose auf Gitterproblemen, die selbst mit Quantenrechnern als nicht knackbar gelten. Allerdings …   Deutsch Wikipedia

  • NTRUSign — ist ein digitales Signaturverfahren, das 2003 entwickelt wurde[1]. Es basiert auf dem Goldreich Goldwasser Halewi Signaturverfahren und ist der Nachfolger des unsicheren NSS Verfahrens. Es ist mit NTRUEncrypt verwandt. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”