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):
- Bildung negativer Zahl: wie Zweierkomplement, MSB vertauscht
18 - Wie wirken sich Quantisierungsfehler auf ein Signal aus?
+ TODO
19 - Welche Bedeutung hat der Lastfaktor?
+ Der Lastfaktor wird fuer die Berechnung der SNR benoetigt;
+ > SNR = \frac{Signalpower}{Noisepower} =
+ > 10 log (\frac{\sigma^2_{Signal}}{\sigma^2_{A/D-Rauschen}})
+ 10log deswegen, weil es sich um einen Leistungsterm handelt.
+
+ Der Rauschanteil berechnet sich durch statistische Annahmen:
+ > \sigma^2_{A/D-Rauschen} = \int^{q/2}_{-q/2} e^2 p(e) de =
+ > \frac{1}{q} * \int^{q/2}_{-q/2} e^2 de = \frac{q^2}{12}
+ > wobei q = \frac{2 U_p}{2^b} = LSB
+ > =>
+ > \sigma^2_{A/D-Rauschen} = \frac{(2 U_p)^2}{12(2^b)} =
+ > \frac{U^2_p}{3\cdot 2^{2b}}
+
+ Der Lastfaktor berechnet sich nun wie folgt:
+ > LF = \frac{Effektivwert}{Spitzenwert}
+
+ Ein Rechtecksignal hat z.B. einen LF=1; ein Sinussignal
+ LF=\frac{1}{\sqrt{2}} = 0.71
+
+ Anders angeschrieben berechnet sich der Lastfaktor
+ > LF = \frac{\sigma_{Signal}}{U_p}
+ daraus folgt
+ > \sigma^2_{Signal} = (LF)^2 U^2_p
+
+ in die SNR Formel eingesetzt ergibt das also
+ > SNR = 10log (\frac{(LF)^2 U^2_p}{U^2_p / 3 \cdot 2^{2b}}) =
+ > 10log ((LF)^2 (3\cdot 2^{2b})) =
+ > 4.77 + 6.02 * b + 20 log (LF)
+
+ Der Lastfaktor wird bei Sinusschwingungen nie groesser als -3dB, daraus
+ koennen wir die maximale Sinusaussteuerung fuer den A/D-Wandler berechnen:
+ > SNR = 4.77 + 6.02 * b + 20 log (1/\sqrt{2}) =
+ > 1.76 + 6.02 * b
+
+ Reale A/D-Wandler reduzieren die ideale SNR um 3-6dB. Es ist unvorsichtig
+ einen A/D-Wandler voll auszusteuern, da sonst die Gefahr der Uebersteuerung
+ besteht. Es muss ein Effektivwert gesucht werden, der den A/D-Wandler nicht
+ uebersteuert!
+ Weiters ist es unzweckmaessig einen A/D-Wandler einzusetzen der einen
+ deutlich besseres SNR hat als das zu wandlende kontinuierliche Signal!
20 - Wie hängen Dynamikbereich und Genauigkeit bei der Festkommadarstellung
zusammen?
b ... Basis (hier b=2)
e ... Exponent
+ bei IEEE 754:
+ x = (-1)^s * m * 2^{e-127}
+ IEEE 32-Bit floating-point:
+ s ... 1 Bit
+ e ... Bit 1 bis 8 (=8 Bits)
+ m ... Bit 9 bis 31 (=23 Bits)
+
+ warum 2^{e-127}? Leichtere Vergleichbarkeit!
+
zwei Grunddatenformate:
single precision (32 bit, len(m)=23 bit, len(e)=8 bit)
double precision (64 bit, len(m)=52 bit, len(e)=11 bit)
projects / sigproz.git / blobdiff