Diskrete Fourier-Transformation

Die Diskrete Fourier-Transformation (DFT) ist eine Transformation aus dem Bereich der Fourier-Analysis.[1][2] Sie bildet ein zeitdiskretes endliches Signal, das periodisch fortgesetzt wird, auf ein diskretes, periodisches Frequenzspektrum ab, das auch als Bildbereich bezeichnet wird. Die DFT besitzt in der digitalen Signalverarbeitung zur Signalanalyse große Bedeutung. Hier werden optimierte Varianten in Form der schnellen Fourier-Transformation (englisch fast Fourier transform, FFT) und ihrer Inversen angewandt.

Die DFT wird in der Signalverarbeitung für viele Aufgaben verwendet, so z. B.

Mit der inversen DFT, kurz iDFT kann aus den Frequenzanteilen das Signal im Zeitbereich rekonstruiert werden. Durch Kopplung von DFT und iDFT kann ein Signal im Frequenzbereich manipuliert werden, wie es beim Equalizer angewandt wird. Die Diskrete Fourier-Transformation ist von der verwandten Fouriertransformation für zeitdiskrete Signale (englisch discrete-time Fourier transform, DTFT) zu unterscheiden, die aus zeitdiskreten Signalen ein kontinuierliches Frequenzspektrum bildet.

Definition

Diskrete Fourier-Transformation (DFT)

Die diskrete Fourier-Transformation verarbeitet eine Folge von Zahlen , die zum Beispiel als zeitdiskrete Messwerte entstanden sind. Dabei wird angenommen, dass diese Messwerte einer Periode eines periodischen Signals entsprechen. Die DFT gilt auch für den Fall, dass eine Folge von komplexen Zahlen ist, also:

Das Ergebnis der Transformation ist eine Zerlegung der Folge in harmonische (sinusförmige) Anteile, sowie einen „Gleichanteil“ , der dem Mittelwert der Eingangsfolge entspricht. Das Ergebnis nennt man „diskrete Fourier-Transformierte“ von . Die Koeffizienten von sind die Amplituden der Zerlegungs-Anteile. Man nennt auch Fourierkoeffizienten oder Fourierkomponenten.

Üblicherweise wird bei der Bestimmung der Frequenzanteile/Phasenlage die kompakte mathematische Schreibweise der Polarform verwendet (Eulersche Formel):

Die Fourierkoeffizienten werden damit aus der Eingangsfolge berechnet durch:

  für  

Die Gleichung kann auch als Matrix-Vektor-Produkt geschrieben werden:

  mit  

Die symmetrische Transformationsmatrix mit der Dimension wird „Fourier-Matrix“ genannt.

Inverse Diskrete Fourier-Transformation (iDFT)

Die Summe der sinusförmigen Zerlegungsanteile ergibt wiederum die ursprüngliche Eingangsfolge .

Dafür wird das Transformationsergebnis als Koeffizienten eines Polynoms verwendet, wobei die Amplituden von den zugehörigen harmonischen Schwingungen darstellen.

Die Argumente sind gleich verteilte Punkte auf dem Einheitskreis der komplexen Zahlenebene, d. h. die –ten Einheitswurzeln

Aus dieser Erklärung wird nebenbei auch der Zusammenhang zwischen der diskreten Fourier-Transformation und der z-Transformation ersichtlich. Der Unterschied besteht im Wesentlichen darin, dass die z-Transformation nicht auf den Einheitskreis beschränkt ist und dadurch auch zeitlich dynamische Vorgänge abbilden kann.

Die Koeffizienten der ursprünglichen Folge lassen sich mit der iDFT aus den Fourierkoeffizienten bestimmen:

   für  

In der Schreibweise als Matrix-Vektor-Produkt:

  mit  

wobei hier mit der inversen Matrix von multipliziert wird.

Bestimmung einer zeitkontinuierlichen periodischen Funktion basierend auf der Eingangsfolge

Aus der inversen diskreten Fourier-Transformation lässt sich auch eine zeitkontinuierliche Funktion bestimmen, die durch die zeitdiskreten Messwerte (die Eingangsfolge) führt:

Dazu wird das Polynom mit einer gleichmäßig den Einheitskreis umlaufenden Funktion verknüpft. So ergibt sich eine zeitkontinuierliche periodische Funktion

die zu den Zeiten gerade die Funktionswerte annimmt.

Die Potenzen von haben die Gestalt

und daher die Periode und die Frequenz bzw. die Kreisfrequenz . Somit ist die Folge der Messwerte durch die Superposition eines konstanten Pegels bei , einer Grundschwingung bei und Oberschwingungen bei dargestellt und interpoliert worden.

Diese oben angegebene Interpolationsfunktion ist nicht die einzige, die sich auf diese Art konstruieren lässt. Jede der Funktionen

hat diese Interpolationseigenschaft.

Sonderfall: DFT für einen reellen Vektor

Wie bei der Fourier-Transformation gelten auch für die DFT gewisse Symmetriegesetze. So wird ein reelles Signal im Zeitraum zu einem hermiteschen Signal () im Frequenzraum:

Dies bedeutet, dass im Frequenzraum nur unabhängige komplexe Koeffizienten vorliegen. Diese Tatsache kann bei der Implementierung der DFT ausgenutzt werden, wenn bekannt ist, dass das Eingangssignal rein reell ist. Für die Darstellung des Ergebnisses sind dann keine (wie bei der vollen DFT), sondern nur komplexe Zahlen nötig. Die anderen komplexen Zahlen können durch elementare Rechnung rekonstruiert werden (siehe Formel oben). Die hermitesche Symmetrie bezieht sich auf das mittlere Element des Signals .

Beweis: Wegen der Eulerschen Identität und wegen gilt im reellen Fall :

Umgekehrt gilt entsprechend: Erfüllt die Bedingung für alle sowie , so ist die inverse DFT ein reeller Vektor .

Verallgemeinerung: Mathematische Definition der DFT

In der Mathematik wird die diskrete Fouriertransformation in einem sehr allgemeinen Kontext betrachtet. Sie findet unter anderem in der Computeralgebra bei einer Vielzahl von effizienten Algorithmen zur exakten Arithmetik Anwendung, so zum Beispiel bei der schnellen Multiplikation ganzer Zahlen mit dem Schönhage-Strassen-Algorithmus.

Sei ein kommutativer unitärer Ring, in dem die Zahl (das ist die -fache Summe der ) eine Einheit ist. Des Weiteren gebe es in eine primitive -te Einheitswurzel . Zu einem Tupel ist dann die diskrete Fouriertransformierte durch

für

erklärt. Unter den getroffenen Voraussetzungen existiert damit zu auch die diskrete inverse Fouriertransformierte mit den Koeffizienten

für .

Im überaus wichtigen Spezialfall wird für die DFT üblicherweise die -te Einheitswurzel benutzt. Dies ergibt die Formel im ersten Abschnitt.

Mehrdimensionale DFT

Die DFT kann leicht auf mehrdimensionale Signale erweitert werden. Sie wird dann je einmal auf alle Koordinatenrichtungen angewendet. Im wichtigen Spezialfall von zwei Dimensionen (Bildverarbeitung) gilt etwa:

für und

Die Rücktransformation lautet entsprechend:

für und

Verschiebung und Skalierung in Zeit und Frequenz

In den Berechnungsformeln von DFT und iDFT kann die Summation (Indexvariable oben) statt über ebenso über einen verschobenen Bereich laufen, wenn der Vektor periodisch auf alle ganzzahligen Indizes fortgesetzt wird, denn es gilt . Wir können also die Summationsgrenzen beliebig verschieben, solange ein Segment der Länge in den ganzen Zahlen überstrichen wird.

Wenden wir uns nun wieder dem komplexen Fall zu. In praktischen Anwendungen möchte man die Indizes mit einer äquidistanten Folge von Zeitpunkten verbinden,

für ,

die ebenfalls die Länge hat. Auch ist es wünschenswert, den berechneten Koeffizienten Frequenzen zuzuordnen, die um zentriert sind,

für

und in der Nähe von .

Eine zu den gewählten Zeitpunkten „gemessene“ Funktion ergibt den Beobachtungsvektor mit den Koeffizienten , dessen DFT in der Fourier-Analyse betrachtet wird. Dann ist

und

.

Beispiele

Die Fourier-Transformation transformiert eine Funktion nach von einer Zeitdarstellung in den reziproken Frequenzraum . Dies gilt auch für Ortsfunktionen, die auf ein (1D), zwei (2D) oder mehr Raumrichtungen definiert sind. Diese werden durch die Fouriertransformation, nacheinander in jeder Richtung, in Raumfrequenzen überführt. Beugungserscheinungen in der Optik oder Röntgenanalyse können unmittelbar als die Intensitätsverteilung einer Fouriertransformierten interpretiert werden. Die Phasenbeziehung geht bei der Fotografie normalerweise verloren. Lediglich bei der Holografie wird die Phasenbeziehung durch eine Überlagerung mit einem Referenzstrahl mit aufgezeichnet.

Einfache Blenden

Berechnete 2D Fourier-Trans­formationen. Links Ausgangs­bild, rechts Intensitäts­verteilung der Fourier-Transformation.
Berechnete 2D Fourier-Trans­formationen. Links Ausgangs­bild, rechts Intensitäts­verteilung der Fourier-Transformation.

Die Bilder rechts veranschaulichen zweidimensionale Fourier-Transformationen (2D FFT) an geometrischen Mustern, gerechnet für Quadrate der diskreten Größe von Pixeln. Das Bild oben links zeigt einen Spalt der Größe Pixel, daneben die Intensitätsverteilung des Beugungsbildes. Die Ortsvariable wird überführt in reziproke komplexe Werte . Bei den gewählten Größen wird ein Pixel auf den reziproken Wert von reziproken Pixeln überführt. Die Breite des Spalts von Pixeln erscheint im Reziprokraum als Wert der Größe , die Höhe , mit harmonischen Frequenzen höherer Ordnung. Die berechneten Beugungsbilder geben die Intensitätsverteilungen der komplexen Größe wieder. Dass sie nur die Hälfte der Bildinformation tragen, erkennt man an ihrer Rotationssymmetrie.

Die periodischen Peaks entsprechen den Ortsfrequenzen höherer Ordnung eines Rechtecksignals. Ähnliche Beispiele finden sich unter den Stichworten Fourier-Analyse, Fourier-Transformation oder Beugungsscheibchen.

Im zweiten Teilbild wird ein regelmäßiges Sechseck gebeugt. Wieder erscheint die Größe der Figur als Periode im Beugungsbild rechts. Die 6-zählige Symmetrie ist deutlich zu erkennen. Eine Verschiebung des Ausgangsbildes – im Gegensatz zu einer Drehung – würde sich nur in der Phasenbeziehung auswirken, die in der gewählten Darstellung als Intensitätsverteilung nicht zu erkennen ist.

Das untere Teilbild zeigt rechts das berechnete Beugungsmuster eines Dreiecks. Die 6-zählige Symmetrie ist nur vorgetäuscht, was an der fehlenden Modulation der Beugungssterne zu erkennen ist.

Die zweite Bildserie vergleicht die Beugung zweier Kreisöffnungen. Ein großer Kreis erzeugt ein kleines Beugungsmuster, und umgekehrt. Bei einem Fernrohr begrenzt die Lichtbeugung an der Linsenöffnung die Auflösung. Je größer der Durchmesser ist, desto kleiner ist das Beugungsbild eines Sterns, desto besser können nahe beieinander liegende Sterne voneinander unterschieden werden.

Das untere Bild ist ein Beispiel für eine Beugung an einer Kreisstruktur ohne scharfe Begrenzung. Bei einer sinusförmigen Intensitätsabnahme am Rad treten keine Beugungen höherer Ordnung auf (siehe auch Zonenplatte).

Bild mit periodischen Strukturen

SAR-Bild des indischen Ozeans
FFT des SAR-Bildes

Die Aufnahme links zeigt eine SAR-Aufnahme des indischen Ozeans mit Wasserwellen unterschiedlicher Wellenlänge. Die internen Wellen oben rechts haben eine Wellenlänge von ca. 500 m. Die durch Wind erzeugten Oberflächenwellen sind in der verkleinerten Darstellung nicht erkennbar. Im gerechneten Beugungsbild geben die beiden dunklen Reflexe (siehe kurzer Pfeil) sowohl die Richtung als auch die mittlere Wellenlänge der regelmäßigen langperiodischen Wasserwellen an. Die Wellenlängen der Oberflächenwellen variieren stärker, weshalb sie keine scharfen Reflexe liefern. Es liegen zwei ausgezeichnete Richtungen für die Wellenausbreitung vor, die im Direktbild nur undeutlich zu sehen sind. Die Wellenlängen betragen ca. 150 m (langer Pfeil) und 160 m (etwas kürzerer Pfeil).

Mathematische Grundlagen

Wir betrachten den Vektorraum und statten ihn mit einem Skalarprodukt aus, welches wir unten definieren.

Einheitswurzeln

Die in der diskreten Fouriertransformation auftretenden komplexen Zahlen

sind -te Einheitswurzeln, d. h., sie sind Lösungen der Gleichung . Betrachte nun die „kleinste“ primitive Wurzel im ersten Quadranten . Notiere das Kronecker-Delta mit . Die Einheitswurzel genügt folgender Identität geometrischer Summen von Einheitswurzeln

mit

wegen der Formel für geometrische Reihen

für .

Dieses ist der „tiefe Grund“, weshalb die inverse DFT funktioniert.

Skalarprodukt und ONB

Für zwei Vektoren mit und definieren wir folgendes komplexe Skalarprodukt

Der Faktor dient der Normierung der Skalarproduktnorm, so dass für passende Vektoren gilt.

In definieren wir die Basis durch

für

Diese bilden eine Orthonormalbasis bezüglich des vorher definierten Skalarproduktes (aus der Eigenschaft der Einheitswurzeln), das heißt es gilt

.

Da eine Orthonormalbasis ist, lässt sich jeder Vektor bezüglich dieser Basis darstellen mit der Eigenschaft und daraus folgt die Darstellung

Die Koeffizienten heißen (auch allgemein bei beliebigem Orthonormalsystem) Fourier-Koeffizienten, die DFT ordnet also einem Vektor bis auf eine additive Konstante den Vektor der Fourier-Koeffizienten zu.

Ist mit einem weiteren Vektor , so gilt die Parsevalsche Gleichung für Fourier-Koeffizienten:

.

Interpretationen der DFT

Diskretisierung der Fourier-Transformation

Die Fourier-Transformation erlaubt es, sich Funktionen mit reellem Argument (und diversen Einschränkungen wie: Integrabilität, Periodizität oder Abfall im Unendlichen) aus Schwingungen zusammengesetzt zu denken:

Eine wichtige Erkenntnis der Fouriertheorie ist, dass die Amplitude sich ähnlich bestimmen lässt zu

Wählen wir einen Radius so groß, dass außerhalb des Intervalls nur noch ein unwesentlicher Teil von liegt, ist außerdem stetig und eine Zahl so groß gewählt, dass klein genug ist, um sinnvoll singulär, d. h. durch Funktionswerte , abzutasten, so kann das Fourierintegral in der Transformationsformel sinnvoll durch eine Summe ersetzt werden:

Das entspricht, bis auf einen konstanten Faktor , der Berechnungsformel der DFT. Der Vektor hat Elemente. Wir wissen bereits, dass es ausreicht, die Frequenzkoeffizienten für die Frequenzen mit zu bestimmen, um die Funktionswerte im Vektor zu rekonstruieren. Mit der notwendigen Anpassung der Konstanten in der iDFT erhalten wir

Der Diskretisierungsabstand im Frequenzbereich ist proportional zu , also nach Voraussetzung ebenfalls klein, sodass diese Berechnung der Diskretisierung der inversen Fourier-Transformation entspricht.

Beim Übergang von der Fourier-Transformation zur DFT sind also folgende Veränderungen zu bemerken:

  • Das Signal liegt zu diskreten, äquidistanten Zeitpunkten vor ( Abstand zweier aufeinanderfolgender Zeitpunkte), ist einer dieser Zeitpunkte.
  • Das Signal hat eine endliche Länge ( Anzahl der Werte), die als Werte innerhalb eines großen Intervalls interpretiert werden.
  • Die Integrale bei der Berechnung der Fourier-Koeffizienten werden bei der DFT zu Summen.
  • Das Spektrum wird nur für eine endliche Anzahl von (Kreis-)Frequenzen berechnet mit und ist periodisch in der Frequenz, wobei die Periode nach Voraussetzung ( klein) sehr groß ist.

Diskretisierung von Fourier-Reihen

Jede periodische Funktion mit reellem Argument (und wieder Einschränkungen wie: Integrabilität, keine Polstellen) und Periode kann als Funktionenreihe mit Sinusoiden, die Bruchteile von als Periode haben, dargestellt werden (sogenannte Fourier-Reihen):

mit

Brechen wir die Reihenentwicklung bei großen Grenzen unten und oben ab, so erhalten wir mit

d. h., wir erhalten eine Form der inversen DFT. Damit können die Koeffizienten mittels DFT approximiert werden zu

Im Grenzfall eines unendlich großen ergeben sich die bekannten Koeffizientenintegrale der Fourier-Reihen:

Ausgleichsrechnung mit trigonometrischen Funktionen

Das Ergebnis einer DFT-Berechnung kann auch als eine Modellierung des Originalsignals mit Hilfe von trigonometrischen Funktionen interpretiert werden. Ein verständlicher Nachweis der Relation zwischen Ausgleichsrechnung (Methode der kleinsten Fehlerquadrate) und der diskreten Fourier-Transformation findet sich in [3].

Eigenschaften

Spektrum abgetasteter Funktionen

Abb. 1: Betrag und Phase des Spektrums eines abgetasteten Signals

Die diskrete Fourier-Transformation besitzt ein periodisches Spektrum, es wiederholt sich mit der Abtastfrequenz und ist symmetrisch zur Abtastfrequenz. Es gilt:

(wegen für natürliche Zahlen und )

Enthält das abgetastete Signal Frequenzanteile oberhalb der halben Abtastfrequenz, überlappen sich die Spektren des ursprünglichen Signals mit den an der Abtastfrequenz gespiegelten Signalanteilen, und es kommt zum Alias-Effekt.

Alias-Effekt

In der Regel entsteht das zeitdiskrete Signal durch Diskretisierung eines kontinuierlichen Signals. Die durch die DFT entstehenden Spektren sind nur dann mit den Spektren des zugrundeliegenden kontinuierlichen Signals identisch, wenn bei der Abtastung das Abtasttheorem nicht verletzt wurde. Für Signale im Basisband muss gelten, dass die Abtastfrequenz mehr als doppelt so groß ist wie die maximal auftretende Frequenz (Nyquist-Frequenz). Bei Verletzung des Abtasttheorems tritt eine Verfälschung des Originalsignals auf (Aliasing im Zeitbereich). Eine Möglichkeit des Antialiasing ist die Bandbegrenzung des Signals am Eingang des Systems, um diesen Effekt zu vermeiden.

DFT einer zeitbegrenzten Funktion

Für periodische Funktionen ergibt sich (analog zur kontinuierlichen Fourier-Transformation) ein Linienspektrum mit einem Frequenzlinienabstand von 1/Periodenlänge.

Abb. 2: Fourier-Transformierte eines Rechteck-Fensters

Eine zeitbegrenzte diskrete Funktion kann man aus einer periodischen diskreten Funktion ableiten, indem man über ein Zeitfenster genau eine Periode herausschneidet:

Da bei der Fourier-Transformation eine Multiplikation von Funktionen im Zeitbereich einer Faltung der Fourier-Transformierten im Frequenzbereich entspricht, ergibt sich die DFT der zeitbegrenzten Funktion durch die Faltung der DFT der periodischen Funktion mit der Fourier-Transformierten des Zeitfensters :

Abb. 3: Zusammensetzung des Spektrums einer zeitbegrenzten Funktion

Als Ergebnis erhält man ein Linienspektrum, das durch die Fourier-Transformierte des Zeitfensters verschmiert ist. In Abb. 3 rechts gestrichelt dargestellt ist der Einfluss des Zeitfensters auf die DFT der periodischen Funktion (dicke Linien). Durch die Zeitbegrenzung kommen Frequenzanteile zwischen den analysierten Frequenzlinien hinzu.

Durch den Übergang von einer periodischen Funktion auf eine zeitbegrenzte Funktion muss nicht das Rechenverfahren zur Bestimmung des Spektrums verändert werden. Es werden weiterhin diskrete Frequenzlinien berechnet, als ob eine periodische Funktion dahinterstände. Als Effekt des Zeitfensters steht nun jede berechnete Frequenzlinie stellvertretend für einen ganzen Frequenzbereich, nämlich für den Frequenzbereich, der durch die Fourier-Transformierte des Zeitfensters hinzugekommen ist. Dieses Verhalten bezeichnet man auch als Leck-Effekt.

Leck-Effekt (Leakage effect)

Aufgrund der zeitlichen Begrenzung des Signals kann es dazu kommen, dass das Eingangssignal abgeschnitten wird. Ein abgeschnittenes Eingangssignal kann nur dann korrekt mit der DFT transformiert werden, wenn es periodisch fortsetzbar ist. Falls das Signal nicht periodisch fortsetzbar ist, enthält es Frequenzen, die nicht zu den von der DFT berechneten diskreten Frequenzen gehören. Die DFT „nähert“ diese Frequenzen durch die benachbarten Frequenzen an, dabei wird die Energie auf diese Frequenzen verteilt. Dies wird als Leck-Effekt (englisch leakage effect) bezeichnet.

Die zeitliche Begrenzung kommt einer Multiplikation mit einer Rechteckfunktion gleich und entspricht einer Faltung mit der si-Funktion im Frequenzbereich. Dies ist eine andere Betrachtungsweise, um den Leck-Effekt zu erklären. Das gilt natürlich auch im Falle anderer Fensterfunktionen (z. B. Hamming, von Hann, Gauss). Somit ist das Spektrum der Fensterfunktion (bzw. die Breite des Spektrums) ausschlaggebend für das Leck. Die Amplitudengenauigkeit ist das andere Kriterium einer Fensterfunktion.

Gleitende DFT als Bandfilterbank

Eine DFT einer zeitbegrenzten Funktion kann man auch als Bandfilterbank ansehen.

  • Die Mittenfrequenzen dieser Bandfilter entsprechen den Frequenzlinien der Funktion, die entsteht, wenn man den betrachteten Zeitabschnitt periodisch wiederholt (Vielfache von 1/Fensterbreite).
  • Die Breite und Flankensteilheit der Bandfilter wird durch die Fourier-Transformierten des Zeitfensters bestimmt (siehe Abb. 3).

Durch die Wahl einer geeigneten Zeitfenster-Funktion kann man die Eigenschaften der Bandfilter verändern.

  • Bei einem rechteckförmigen Zeitfenster mit Unstetigkeitsstellen an den Fenstergrenzen werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz abgeschwächt; man erzielt Flankensteilheiten von 6 dB/Oktave (siehe Abb. 2).
  • Ist die Fensterfunktion stetig, werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz2 abgeschwächt; man erzielt Flankensteilheiten von 12 dB/Oktave.
  • Ist die 1. Ableitung der Fensterfunktion stetig, werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz3 abgeschwächt; die Flankensteilheit beträgt 18 dB/Oktave.
  • usw.

Bestimmt man die Fourier-Transformierte von jeweils aufeinanderfolgenden Zeitabschnitten, erhält man die gleitende Fourier-Transformation. Mit der Analyse eines neuen Zeitabschnitts erhält man dann neue Abtastwerte für den Zeitverlauf der Spektrallinien (das heißt den Zeitverlauf der Signale an den Ausgängen der „Bandfilter“).

Unschärfe-Relation der gleitenden DFT

Zeit- und Frequenzauflösung der gleitenden DFT können nicht unabhängig voneinander gewählt werden.

  • Will man Signale mit hoher Frequenzauflösung analysieren, muss man die Zeitfenster sehr groß machen, man erhält eine geringe Zeitauflösung.
  • Benötigt man eine hohe Zeitauflösung, muss man die Breite der Zeitfenster sehr kurz machen, dann kann man aber nur wenige Frequenzlinien bestimmen.
  • Es gilt: Frequenzauflösung ≈ 1/Zeitfensterbreite (wird eine Frequenzauflösung von 1 kHz gewünscht, muss das Zeitfenster mindestens 1 ms lang sein).

FFT

Für Blocklängen , die sich als Potenz von 2 darstellen lassen, kann die Berechnung mit dem Algorithmus der schnellen Fourier-Transformation (FFT) erfolgen. Allgemein gilt: Kann die Blocklänge faktorisiert werden, , so gibt es eine Zerlegung der DFT der Länge in ein Produkt von DFTs der Längen und sowie zweier einfacher Matrizen.

Goertzel-Algorithmus

Für beliebige Blocklängen und zur Bestimmung einer einzigen oder einiger weniger spektraler Komponenten kann auch der Goertzel-Algorithmus verwendet werden. Der Vorteil besteht in einer sehr effizienten Implementierung in Computersystemen, da die Berechnung pro Spektralkomponente nur eine komplexe Multiplikation und zwei komplexe Additionen umfasst.

Anwendungen

  • Berechnung der Fourier-Transformierten eines Signals
  • Signalanalyse
  • Schwingungsanalyse und Modalanalyse
  • Bearbeitung von Signalen
  • Berechnung von Korrelationen
  • Berechnung von Polynomprodukten in

Bei der Berechnung von Oberflächenwellenfiltern (= OFW-Filter = SAW-Filter = surface acoustic wave–filter) wird die Invers–Fouriertransformierte der Übertragungsfunktion benötigt (stellt die Impulsantwort dar). Diese Aufgabe wird von Rechnern übernommen.

Siehe auch

Literatur

Einzelnachweise

  1. Tilman Butz: Fouriertransformation für Fußgänger. 7. Auflage. Vieweg+Teubner Verlag, Wiesbaden 2011, ISBN 978-3-8348-0946-9, Kapitel 4.
  2. M. W. Wong: Discrete Fourier Analysis. Birkhäuser Verlag, Basel 2011, ISBN 978-3-0348-0115-7.
  3. Tilo Strutz: Explaining the Discrete Fourier Transform of real signals based on the least-squares approximation of time-discrete signals using trigonometric functions. 2017, TECHP/2017/11, DOI:10.13140/RG.2.2.34597.81126, "PDF"

Read other articles:

This article may lack focus or may be about more than one topic. In particular, this article is about the 2007 comics, 2009 animated TV adaptation (and tie-in comics to the TV show), etc., etc.. Please help improve this article, possibly by splitting the article and/or by introducing a disambiguation page, or discuss this issue on the talk page. (January 2023) Italian TV series or program Angel's FriendsCover of the first original DVD.GenreContemporary fantasy, romanceCreated bySimona Fe...

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala. Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Panembahan Somala –...

Aleksi Ojala Aleksi Ojala (2015) Voller Name Aleksi Mikael Ojala Nation Finnland Finnland Geburtstag 9. Dezember 1992 (30 Jahre) Geburtsort Urjala, Finnland Größe 180 cm Gewicht 62 kg Karriere Disziplin 50-Kilometer-Gehen Bestleistung 3:46:25 h Verein Turun Weikot Trainer Veli-Matti Ranta Status aktiv letzte Änderung: 27. Mai 2021 Aleksi Mikael Ojala (* 9. Dezember 1992 in Urjala) ist ein finnischer Geher. Inhaltsverzeichnis 1 Sportliche Laufbahn 2 Wichtige Wettbewerbe 3 Persönl...

Truxtun-class destroyer For other ships with the same name, see USS Truxtun. USS Truxtun (DD-14) History United States NameTruxtun NamesakeCommodore Thomas Truxtun awarded Congressional Gold Medal BuilderMaryland Steel Company Sparrows Point, Maryland Laid down13 November 1899 Launched15 August 1901 Sponsored byMiss Isabelle Truxtun, grand daughter of Commodore Tuxtun[1] Commissioned11 September 1902 Decommissioned18 July 1919 Stricken15 September 1919 IdentificationHull symbol: DD-14...

Adriaen de Vries Adriaen de Vries (* um 1545 oder 1556[1] in Den Haag; † vor 15. Dezember 1626 in Prag) war ein niederländischer Bildhauer des Manierismus, der auf Bronzeskulpturen spezialisiert war. Inhaltsverzeichnis 1 Leben und Werke 2 Stilistische Entwicklung 3 Werke 4 Literatur 5 Quellen 6 Weblinks 7 Anmerkungen Leben und Werke Grab- und Auferstehungsmonument im Mausoleum Stadthagen, heute neben dem Taufbecken der Bückeburger Stadtkirche das einzige Werk de Vries’, das noch...

Abchazië en Zuid-Ossetië ten opzichte van Georgië en Rusland Abchazië en Zuid-Ossetië zijn twee geografische entiteiten waarvan de status internationaal omstreden is. Achtergrond Abchazië en Zuid-Ossetië zijn twee zelfverklaarde en de facto van Georgië afgescheiden republieken. Beiden waren binnen de Georgische Sovjetrepubliek autonome deelregio's en verklaarden zich begin jaren 1990 onafhankelijk. In augustus 2008 probeerde Georgië het verloren gezag over Zuid-Ossetië te herstellen...

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يناير 2022) تحتاج هذه المقالة إلى تهذيب لتتناسب مع دليل الأسلوب في ويكي

Artikel utama: Ilmu Al-Qur'an Bagian dari seriIslam Rukun Iman Keesaan Allah Nabi dan Rasul Allah Kitab-kitab Allah Malaikat Hari Kiamat Qada dan Qadar Rukun Islam Syahadat Salat Zakat Puasa Haji Sumber hukum Islam al-Qur'an Sunnah (Hadis, Sirah) Tafsir Akidah Fikih Syariat Sejarah Garis waktu Muhammad Ahlulbait Sahabat Nabi Khulafaur Rasyidin Khalifah Imamah Ilmu pengetahuan Islam abad pertengahan Penyebaran Islam Penerus Muhammad Budaya dan masyarakat Akademik Akhlak Anak-anak Dakwah Demogr...

  Grand Prix Malaysia 2019Detail lombaLomba ke 18 dari 19Grand Prix Sepeda Motor musim 2019Tanggal3 November 2019Nama resmiShell Malaysia Motorcycle Grand PrixLokasiSepang International Circuit, Sepang, Selangor, MalaysiaSirkuitFasilitas balapan permanen5.543 km (3.444 mi)MotoGPPole positionPembalap Fabio Quartararo YamahaCatatan waktu 1:58.303 Putaran tercepatPembalap Valentino Rossi YamahaCatatan waktu 1:59.661 on lap 3 PodiumPertama Maverick Viñales YamahaKedua Marc M�...

Ethnolinguistic community recognized in Ottoman law History of the Ottoman EmpireSocial structure Court and aristocracy Ottoman court Slavery Devshirme Ethnoreligious communities Muslims Millets Greek Orthodox Armenian Aromanian Bulgarian Armenians Jews Greeks Great Fire of 1660 Rise of nationalism Tanzimat Ottomanism Classes Askeri Ayan Giaour Rayah Vlachs vte Part of a series onAromanians Etymology List of Aromanians Geographical distribution By country Albania Bulgaria Greece North Macedon...

24th US national census Twenty-fourth census of the United States ← 2010 April 1, 2020 2030 → Seal of the U.S. Census BureauGeneral informationCountryUnited StatesTopics Census topics People and population Race and ethnicity Families and living arrangements Health Education Business and economy Employment Housing Income and poverty AuthorityU.S. Census BureauWebsitewww.census.govResultsTotal population331,449,281 ( 7.4%)Most populous ​stateCalifornia (39,...

Full-body garment Flying suit redirects here. For the extreme sport, see wingsuit. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Flight suit – news · newspapers · books · scholar · JSTOR (July 2013) (Learn how and when to remove this template message) Flight suit worn by a Thunderbird passenger A flight su...

Хісакава Аяяп. 久川綾Народилася 12 листопада 1968(1968-11-12) (55 років)Кайдзуке, Префектура Осака, ЯпоніяГромадянство  ЯпоніяДіяльність співачка, сейюРоки діяльності 1993 — тепер. часIMDb nm0386752aoni.co.jp/search/hisakawa-aya.html Хісакава Ая (яп. 久川 綾, нар. 12 листопада 1968, Кайдзуке, Префектура Оса...

كارلو الثاني دوق بارما (بالإيطالية: Carlo II di Parma)‏  معلومات شخصية الميلاد 22 ديسمبر 1799(1799-12-22)مدريد الوفاة 16 أبريل 1883 (83 سنة)نيس مواطنة إسبانيا  الزوجة ماريا تيريزا أميرة سافوي (5 سبتمبر 1820–)  الأولاد كارلو الثالث دوق بارما  [لغات أخرى]‏  الأب لويس الأول ملك إترو�...

Former hotel and casino in Las Vegas Vegas WorldVegas World's original eight-story towerShow map of Las Vegas BoulevardShow map of Nevada Location Las Vegas, Nevada Address 2000 South Las Vegas BoulevardOpening dateJuly 13, 1979Closing dateFebruary 1, 1995; 28 years ago (February 1, 1995)ThemeOuter spaceNo. of rooms90(1979) 932(1990)Total gaming space15,000 sq ft (1,400 m2) (1984) 80,000 sq ft (7,400 m2) (1990)Signature attractionsReplica of the Apol...

Scottish actor Ian HanmoreHanmore in 2014OccupationActorYears active1996–present Ian Hanmore is a Scottish actor known for his role as the warlock Pyat Pree in the second season of the HBO series Game of Thrones.[1] Career He also played Albert Flood in The Awakening, Margaret's Father in The Magdalene Sisters, Lord Ruthven in Mary Queen of Scots[2] and Father Angelo in the 2006 Doctor Who episode Tooth and Claw. He played the Guide in James Graham's site specific piece...

Russian Governor-General of Warsaw For Tsarevich Aleksandr Archilovich Imeretinsky, see Prince Alexander of Imereti (1674–1711). You can help expand this article with text translated from the corresponding article in Russian. (December 2017) Click [show] for important translation instructions. View a machine-translated version of the Russian article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as n...

Drawing by Vincent van Gogh SorrowArtistVincent van GoghYear1882 (1882)CatalogueF929aTypeDrawingMediumPencil, pen and ink on paperSubjectNudeDimensions44.5 cm × 27.0 cm (17.5 in × 10.6 in)ConditionGoodLocationThe New Art Gallery Walsall, EnglandAccession1973.128.GR Sorrow is a drawing by Vincent van Gogh, produced in 1882. The work, created two years after Van Gogh had decided to become an artist, depicts 32-year-old pregnant woman Clasina Mari...

Bengali literary genre বাংলাদেশি লোক সাহিত্যBangladeshi folk literatureBengali literature (By category) Bengali languageBengali literary historyHistory of Bengali literatureBengali language authorsChronological list - Alphabetic ListMajor Folk LiteratureMymensingh Gitika Part of a series on theCulture of Bengal History People Bangal Bengali Muslims Bengali Hindus Bengali Buddhists Bengali Christians Bhadralok Dhakaiyas Ghoti Mahimal Sylhetis List of Benga...

Francia en los Juegos Olímpicos Bandera de FranciaCódigo COI FRACON Comité Nacional Olímpico y Deportivo Francés(pág. web)Juegos Olímpicos de Múnich 1972Deportistas 227 en 18 deportesAbanderado Jean-Claude MagnanMedallasPuesto: 17 2 4 7 13 Historia olímpicaJuegos de verano 1896 • 1900 • 1904 • 1908 • 1912 • 1920 • 1924 • 1928 • 1932 • 1936 • 1948 • 1952 &...