From d00c1f3c765677af0ae81059c87882cd8c013ace Mon Sep 17 00:00:00 2001 From: Bernhard Urban Date: Wed, 18 Nov 2009 10:34:41 +0100 Subject: [PATCH] frage16: fft mehr ausgefuehrt --- ausarb2.txt | 43 ++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 40 insertions(+), 3 deletions(-) diff --git a/ausarb2.txt b/ausarb2.txt index e7f0901..83c736d 100755 --- a/ausarb2.txt +++ b/ausarb2.txt @@ -41,9 +41,46 @@ Teil 2/2 - von Sebastian Falbesoner [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? -- 2.25.1