X-Git-Url: http://wien.tomnetworks.com/gitweb/?p=sigproz.git;a=blobdiff_plain;f=ausarb2.txt;h=83c736d37091f4433e600071c1cb278819f0216a;hp=ea14f27bdc8dd0d50d35411d587bd70f4cae13c0;hb=d00c1f3c765677af0ae81059c87882cd8c013ace;hpb=908686866c93b560c0b2024a366591fd7b858d09 diff --git a/ausarb2.txt b/ausarb2.txt index ea14f27..83c736d 100755 --- a/ausarb2.txt +++ b/ausarb2.txt @@ -40,6 +40,48 @@ Teil 2/2 - von Sebastian Falbesoner Dieser Prozess wird fortgesetzt bis eine 2-Punkt-Folge übrigbleibt [Zahl der Operationen: Reduzierung von ~N^2 auf N*log_2(N)] + 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). + 17 - Welche Zahlendarstellungen für negative Festkommazahlen sind in der DSP gebräuchlich und welche Vor- und Nachteile haben Sie? Einerkomplement (One's complement): @@ -60,8 +102,10 @@ Teil 2/2 - von Sebastian Falbesoner - Bildung negativer Zahl: wie Zweierkomplement, MSB vertauscht 18 - Wie wirken sich Quantisierungsfehler auf ein Signal aus? + TODO 19 - Welche Bedeutung hat der Lastfaktor? + TODO 20 - Wie hängen Dynamikbereich und Genauigkeit bei der Festkommadarstellung zusammen?