frage16: fft mehr ausgefuehrt

diff --git a/ausarb2.txt b/ausarb2.txt
index e7f0901cf7cd7acc8968b2dbcdb4be2d4de78226..83c736d37091f4433e600071c1cb278819f0216a 100755 (executable)
--- a/ausarb2.txt
+++ b/ausarb2.txt
@@ -41,9 +41,46 @@ Teil 2/2 - von Sebastian Falbesoner <e0725433@student.tuwien.ac.at>
        [Zahl der Operationen: Reduzierung von ~N^2 auf N*log_2(N)]
 
        by wurm:
        [Zahl der Operationen: Reduzierung von ~N^2 auf N*log_2(N)]
 
        by wurm:

-       mathematischer ausfuehren.
-       algorithmus (pseudocode?)
-       ned nur fuer 2-Punkt-Folge sondern auch fuer 4-Punkt-Folge?
+       Im Text wird der 2-Punkt Algorithmus naeher ausgefuehrt:
+       Im ersten Schritt fuehren wir die Beziehung
+       > W^k_N = e^{-j\frac{2 \pi}{N}k}
+       ein. Man kann erkennen, dass W^k_N fuer alle k=0,1,...,N-1 eine gewissen
+       Symmetrie aufweist:
+       > W^k_N = -W^{k+(N/2)}_N bzw. W^{k+(N/2)}_N = -W^k_N
+       man kann nun die Folge x[n] in eine gerade und ungerade Liste aufteilen,
+       und erhaelt damit folgenden Term:
+       > X[k] = \sum^{N-1}_{m=0} x[n] W^{kn}_N =
+       > \sum^{N/2 -1}_{m=0} x[2m] W^{2mk}_N +
+       > \sum^{N/2 -1}_{m=0} x[2m+1] W^{(2m+1)k}_N = //W^k_N rausziehen
+       > \sum^{N/2 -1}_{m=0} x[2m] W^{2mk}_N +
+       > W^k_N \sum^{N/2 -1}_{m=0} x[2m+1] W^{2mk}_N
+
+       weiters kann man nun die Beziehung
+       > W^2_N = W_{N/2}
+       ausnutzen, die sich wie folgt ergibt:
+       > W^2_N = e^{-j\frac{2\pi 2}{N}} = e^{-j\frac{2\pi}{N/2}}
+
+       also erhalten wir:
+       > X[k] = \sum^{N/2 -1}_{m=0} x[2m] W^{mk}_{N/2} +
+       > W^k_N \sum^{N/2 -1}_{m=0} x[2m+1] W^{mk}_{N/2}
+
+       vereinfacht angeschrieben ist das:
+       > X[k] = X_g[m] + W^k_N \cdot X_u[m]
+
+       die Symmetrieeigenschaft ausgenutzt, koennen wir nun behaupten:
+       > X[k] = X_g[k] + W^k_N \cdot X_u[k]
+       > X[k + (N/2)] = X_g[k] - W^k_N \cdot X_u[k]
+       > fuer k=0,1,\dots{},(N/2)-1
+
+       beim 2-Punkt Algorithmus wird x[n] also so lange in geraden und ungeraden
+       Folgen aufgeteilt bis nur noch 2 Elemente in der Liste enthalten sind.
+       Daraus folgt dass x[n] immer eine Laenge von 2^n haben muss bzw. wenn das
+       nicht der Fall ist, mit Nullen aufgefuellt werden muss.
+       Weiters gibts noch leicht abgeaenderte Varianten, z.B. den 4-Punkt bzw.
+       8-Punkt Algorithmus. Hier reduziert sich die Anzahl der Multiplikationen
+       um zirka um 25% bzw. 40%, haben aber den Nachteil dass die Laenge der
+       Eingangsfolge eine Potenz von 4 bzw. 8 sein muss (und dementsprechend
+       groessere Speicherelemente benoetigt).

 
 17 - Welche Zahlendarstellungen für negative Festkommazahlen sind in der DSP
      gebräuchlich und welche Vor- und Nachteile haben Sie?
 
 17 - Welche Zahlendarstellungen für negative Festkommazahlen sind in der DSP
      gebräuchlich und welche Vor- und Nachteile haben Sie?