+ by wurm:
+ 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).
+
projects / sigproz.git / blobdiff