Diskrete Fouriertransformation Flashcards
Motivation der Diskreten Fouriertransformation
Wir haben ein Signal der, das wir als eine Funktion s’ : R -> R sehen. Dieses Signal disrektisieren wir indem wir es nur über ein Intervall i = [0, n) mit Sidkretisierungsschrittweite 1 abbilden. So kann das Signal als Vektor s \in R^n dargestellt werden. Aus komplexitätsgründen nehmen wir an das s zyklisch verläuft, also s’(t) = s_(t mod n). s wollen wir jetzt mit einem Operator A verarbeiten. Dabei bildet A dann auf neues Signal ab.
Wie nennt man die Veränderung des Signals
filtern
Wie heißt die Anwendung des Operators zum filtern
falten
Wie kann man die Matrix A auch nennen
Filter
Wie heißt die Matrixmultiplikation As
Faltung
Was bedeutet zeitinvariant
Es spielt keine Rolle, ob wir das Signal zunächst verschieben oder denn Operator anwenden und dann das Signal verschieben.
Ist der Filter zeitinvariant
Ja
zyklische Verschiebungsmatrix
Welche Eigenschaft hat die Matrix A dadurch, das sie zeitinvariant ist in Verbindung mit der zyklischen Verschiebungsmatrix
Wie sieht die Faltungsmatix A aus?
Wir können alle Spalten aus A durch Verschiebung von a’ beschreiben
A als Linearkombination der Potenzen von Z
Was gilt für den Vektor a’ der Faltungsmatrix A
a’ bestimmt die Matrix A vollständig
Was ist der Kern des Faltungsoperators *
der Vektor a’
Faltungsoperator als Funktion, die nur von a’ abhängt
Wie kann man a’ berechnen, wenn der Filter unbekannt ist?
In dem man sich das Ergebnis für das Signal (1,0,…,0)^T, den sog. Einheitsimpuls betrachtet. Das Ergebnis nennt man Impulsanwort.
Was ist die normale Komplexität der Faltungsoperation
0(n^2)
Wie schnell kann man die Faltung ausrechnen
O(n log n)
Was gilt für die Eigenvektoren von Z bezüglich den Eigenvektoren von A
Die Eigenvektoren von Z sind auch die Eigenvektoren von A
Was sind die n Eigenwerte von Z
Das sind die n-ten Einheitswurzeln
wie berechnet man die Lösung der Einheitswurzeln
Für die k-te Lösung wird w_n hoch k gerechnet
Wie sehen die Eigenvektoren von Z aus?
Wie stehen die Eigenvekoren von Z v_j und v_k zueinander?
v_j und v_k sind orthogonal
Interpretation der Eigenvektoren als Frequenzen für gerades n
Interpretation der Eigenvektoren als Frequenzen für ungerades n
Was ist die DFT -Matrix
Die normierten Eigenvektoren bilden die DFT Matrix
Was ist die Fourientransformation
In welchen Raum überträgt die Fourientransformation die Sinale vom Frequenzraum
In den Ortsraum
In welchen Raum überträgt die inverse Fourientransformation die Signale vom Ortsraum
In den Frequenzraum
Was ist die Inverse der DFT-Matrix
Wie kann man J verstehen
J erhält bei einem Vektor das erste Element und spielet die Reihnfolge der berbleibenden Elemente. Im Kontext der Zeit bedeutet das, das Zeitsignal rückwärts zu betrachten. Im Kontext destes bedeutes das, das Ortssignal ind die andere Richtung zu verstehen
Wie kann man den Kern a’ der Filtermatrix a durch J beschreiben
Austauschung von Vorwärtstransformation und Rückwärtstransformation
Vorwärts- und Rückwärtstranformation sind austauschbar. Wir brauchen auch nur eine Transforamtion auszurechnen. Die inverse Transformation erhalten wir einfach dadurch, das wir entweder im Signal die Reihnfolge vertauschen oder im Ergebnis.
wie hätten wir w_n wählen müssen um die Inverse der DFX-Matrix zu erhalten
Faltungsopertaion mit der Fouriertransformation darstellen
Die Faltung von a’ und s können wir berechnen, indem wir zunächst sowohl von a wie auch von s die inverse Fouriertransformation bestimmen. die resultierenden Vektoren multiplizieren wir dann elementweise und wenden die Fouriertransformation an. Bei diesem Vorgehen können wir die Rollen der Fouriertransformation und ihrer Inverse ohne Einschränkung vertauschen.
Was entspricht der Faltung im Ortsraum?
Die Produktbildung im Frequenzraum
Was entspricht der Produktbildung im Ortsraum?
Die Faltung im Frequenzraum
Idee der Rekursive diskrete Fouriertranformation
Wir teilen den Signalverktor in Elemente mit geradem und mit ungeradem Index. Von beiden Vektoren der Länge n bilden wir die Fouriertranformation. Das Ergebnis des ungeraden Teil multiplizieren wir elementeweise mit einem Vektor F.
Vektor F der rekursiven diskreten Furiertransformation
Matrix P der rekursiven diskreten Fouriertransformation
Wie kann man sie Diskrete Fourierentransformation mit der rekursiven Fouriertransformation ausrechnen?
Schritt 1 der schnellen disrekten Fouriertransformation
Sortieren des Signals: Entspricht der Umkehrung der Bits in Binärdarstellung
Schritt 2 der schnellen Fouriertransformation