1 Ausarbeitung der typischen Prüfungsfragen zur Vorlesung "Signalprozessoren"
2 Teil 2/2 - von Sebastian Falbesoner <e0725433@student.tuwien.ac.at>
4 14 - Wie kann mit der DFT das Spektrum einer aperiodischen Funktion annähernd
6 Die DFT funktioniert nur für periodische Folgen, deshalb ist die
7 Signaldarstellung im Zeit- und Frequenzbereich immer periodisch. In
8 der Realität hat jedes Signal aber einen Anfang und ein Ende. Um eine
9 nicht-periodische Funktion anzunähern benutzt man Zero-Padding, d.h.
10 man fügt in die periodische Funktion Nullen ein.
11 Falls man die Anzahl der Nullen gegen Unendlich laufen lässt, erhält
12 man die DTFT (Discrete Time Fourier Transformation), die aber nur von
13 theoretischem Interesse ist, da sie ein unendliches Spektrum hat.
16 15 - Sie wollen benachbarte Spektrallinien der Frequenzen f und f + delta(f)
17 auflösen. Wie stellen Sie sicher, dass die Spektrallinien getrennt werden?
18 Hinweis: Zero Padding verbessert die Trennung zweier Nahe nebeneinander
19 liegender Spektralkomponenten nicht!
20 Um die spektrale Auflösung von zwei Signalen zu verbessern, müssen bei
21 der Abtastung mehr Signalproben (ungleich Null) genommen werden.
23 Um zwei benachbarte Spektrallinien auflösen zu können, muss der Abstand
24 der Spektrallinien >= als der Abstand des Frequenzrasters sein!
26 [Frequenzraster = f_s / N
27 f_s ... Abtastfrequenz des Originalsignals
28 N ... Anzahl der Samples]
30 16 - Was ist die FFT und wie wird sie berechnet?
31 Die FFT (Fast Fourier Transformation) ist ein Algorithmus zur
32 effizienten Berechnung der Werte einer DFT. Es handelt sich um ein
33 "divide and conquer" (Teile und Herrsche) Verfahren und im Gegensatz
34 zur direkten Berechnung werden zuvor berechnete Zwischenergebnisse
35 wiederverwendet, was arithmetische Rechenoperationen einspart.
36 Voraussetzung: Anzahl der Abtastpunkte ist eine Zweierpotenz!
38 Eine N-Punkt-Folge wird aufgeteilt in zwei N/2-Punkt Folgen
39 [Zahl der Operationen: Reduzierung von ~N^2 auf 2x(N/2)^2 = N^2/2]
40 Dieser Prozess wird fortgesetzt bis eine 2-Punkt-Folge übrigbleibt
41 [Zahl der Operationen: Reduzierung von ~N^2 auf N*log_2(N)]
44 Im Text wird der 2-Punkt Algorithmus naeher ausgefuehrt:
45 Im ersten Schritt fuehren wir die Beziehung
46 > W^k_N = e^{-j\frac{2 \pi}{N}k}
47 ein. Man kann erkennen, dass W^k_N fuer alle k=0,1,...,N-1 eine gewissen
49 > W^k_N = -W^{k+(N/2)}_N bzw. W^{k+(N/2)}_N = -W^k_N
50 man kann nun die Folge x[n] in eine gerade und ungerade Liste aufteilen,
51 und erhaelt damit folgenden Term:
52 > X[k] = \sum^{N-1}_{m=0} x[n] W^{kn}_N =
53 > \sum^{N/2 -1}_{m=0} x[2m] W^{2mk}_N +
54 > \sum^{N/2 -1}_{m=0} x[2m+1] W^{(2m+1)k}_N = //W^k_N rausziehen
55 > \sum^{N/2 -1}_{m=0} x[2m] W^{2mk}_N +
56 > W^k_N \sum^{N/2 -1}_{m=0} x[2m+1] W^{2mk}_N
58 weiters kann man nun die Beziehung
60 ausnutzen, die sich wie folgt ergibt:
61 > W^2_N = e^{-j\frac{2\pi 2}{N}} = e^{-j\frac{2\pi}{N/2}}
64 > X[k] = \sum^{N/2 -1}_{m=0} x[2m] W^{mk}_{N/2} +
65 > W^k_N \sum^{N/2 -1}_{m=0} x[2m+1] W^{mk}_{N/2}
67 vereinfacht angeschrieben ist das:
68 > X[k] = X_g[m] + W^k_N \cdot X_u[m]
70 die Symmetrieeigenschaft ausgenutzt, koennen wir nun behaupten:
71 > X[k] = X_g[k] + W^k_N \cdot X_u[k]
72 > X[k + (N/2)] = X_g[k] - W^k_N \cdot X_u[k]
73 > fuer k=0,1,\dots{},(N/2)-1
75 beim 2-Punkt Algorithmus wird x[n] also so lange in geraden und ungeraden
76 Folgen aufgeteilt bis nur noch 2 Elemente in der Liste enthalten sind.
77 Daraus folgt dass x[n] immer eine Laenge von 2^n haben muss bzw. wenn das
78 nicht der Fall ist, mit Nullen aufgefuellt werden muss.
79 Weiters gibts noch leicht abgeaenderte Varianten, z.B. den 4-Punkt bzw.
80 8-Punkt Algorithmus. Hier reduziert sich die Anzahl der Multiplikationen
81 um zirka um 25% bzw. 40%, haben aber den Nachteil dass die Laenge der
82 Eingangsfolge eine Potenz von 4 bzw. 8 sein muss (und dementsprechend
83 groessere Speicherelemente benoetigt).
85 17 - Welche Zahlendarstellungen für negative Festkommazahlen sind in der DSP
86 gebräuchlich und welche Vor- und Nachteile haben Sie?
87 Einerkomplement (One's complement):
88 - Bildung negativer Zahl: alle Bits invertieren
89 - 0 ist zweimal vorhanden (-0, +0)
90 Zweierkomplement (Two's complement):
91 - meistens verwendet in DSPs
92 - Addition und Subtraktion mit selber Hardware möglich
93 - Bildung negativer Zahl: Einerkompliment + 1
94 - 0 ist nur einmal vorhanden
96 - Einfache Erzeugung negativer Zahlen
97 - schlecht geeignet zum Rechnen
98 - nur in speziellen Hardware-Implementierungen verwendet
99 - Bildung negativer Zahl: MSB auf 1 setzen, Rest bleibt gleich
101 - verwendet in A/D-Wandlern
102 - Bildung negativer Zahl: wie Zweierkomplement, MSB vertauschen
104 18 - Wie wirken sich Quantisierungsfehler auf ein Signal aus?
107 19 - Welche Bedeutung hat der Lastfaktor?
108 Der Lastfaktor wird fuer die Berechnung der SNR benoetigt;
109 > SNR = \frac{Signalpower}{Noisepower} =
110 > 10 log (\frac{\sigma^2_{Signal}}{\sigma^2_{A/D-Rauschen}})
111 10log deswegen, weil es sich um einen Leistungsterm handelt.
113 Der Rauschanteil berechnet sich durch statistische Annahmen:
114 > \sigma^2_{A/D-Rauschen} = \int^{q/2}_{-q/2} e^2 p(e) de =
115 > \frac{1}{q} * \int^{q/2}_{-q/2} e^2 de = \frac{q^2}{12}
116 > wobei q = \frac{2 U_p}{2^b} = LSB
118 > \sigma^2_{A/D-Rauschen} = \frac{(2 U_p)^2}{12(2^b)} =
119 > \frac{U^2_p}{3\cdot 2^{2b}}
121 Der Lastfaktor berechnet sich nun wie folgt:
122 > LF = \frac{Effektivwert}{Spitzenwert}
124 Ein Rechtecksignal hat z.B. einen LF=1; ein Sinussignal
125 LF=\frac{1}{\sqrt{2}} = 0.71
127 Anders angeschrieben berechnet sich der Lastfaktor
128 > LF = \frac{\sigma_{Signal}}{U_p}
130 > \sigma^2_{Signal} = (LF)^2 U^2_p
132 in die SNR Formel eingesetzt ergibt das also
133 > SNR = 10log (\frac{(LF)^2 U^2_p}{U^2_p / 3 \cdot 2^{2b}}) =
134 > 10log ((LF)^2 (3\cdot 2^{2b})) =
135 > 4.77 + 6.02 * b + 20 log (LF)
137 Der Lastfaktor wird bei Sinusschwingungen nie groesser als -3dB, daraus
138 koennen wir die maximale Sinusaussteuerung fuer den A/D-Wandler berechnen:
139 > SNR = 4.77 + 6.02 * b + 20 log (1/\sqrt{2}) =
142 Reale A/D-Wandler reduzieren die ideale SNR um 3-6dB. Es ist unvorsichtig
143 einen A/D-Wandler voll auszusteuern, da sonst die Gefahr der Uebersteuerung
144 besteht. Es muss ein Effektivwert gesucht werden, der den A/D-Wandler nicht
146 Weiters ist es unzweckmaessig einen A/D-Wandler einzusetzen der einen
147 deutlich besseres SNR hat als das zu wandlende kontinuierliche Signal!
149 20 - Wie hängen Dynamikbereich und Genauigkeit bei der Festkommadarstellung
151 Bei der Festkommadarstellung befindet sich der Dezimalpunkt für
152 Kommazahlen an einem fixen Punkt und für den Bereich nach und vor
153 diesem wird eine fixe Anzahl an Bits verwendet; man beschreibt daher
154 dieses Format auch mit Qm.n
156 Je mehr Bits man für den Bereich nach dem Fixpunkt spendiert, desto
157 höher wird natürlich die Genauigkeit der Kommazahlen. Das selbe
158 gilt für den Dynamikbereich: je mehr Bits für die Stellen vor dem
159 Fixpunkt verwendet werden, desto mehr ganzzahlige Werte vor dem
160 Dezimalpunkt sind möglich.
161 Die Qm.n Formate haben aber insgesamt eine fixe Größe, deshalb gilt
162 hier, je höher der Dynamikbereich, desto weniger Bits bleiben für
163 den Nachkommaanteil übrig und desto ungenauer werden die Kommazahlen,
164 und umgekehrt fällt der ganzzahlige Anteil umso kleiner aus, je mehr
165 Bits man für hohe Genauigkeit investiert.
167 Die Extreme eines 16-Bit Qm.n sind zum Beispiel:
168 Q0.15: höchste Präzision, jedoch insgesamt nur ein Wertebereich von
170 Q15.0: höchster Dynamikbereich, Nachkommaanteil gar nicht vorhanden,
171 entspricht einem Integer mit Wertebereich -32768 bis 32767!
173 21 - Welche Vor- und Nachteile haben Fest- und Gleitkomma-DSPs?
174 Eigenschaften Festkommazahlen:
175 - gleichmäßige Auflösung über den gesamten Zahlenbereich
176 - kleiner Dynamikbereich
177 - Festkomma-DSPs sind billiger, verbrauchen weniger Strom,
178 haben eine höhere Taktfrequenz, werden aber nur sehr schwach
179 von C-Compilern unterstützt (meist in Assembler programmiert);
180 Overflow- und Quantisierungsfehler müssen softwareseitig
183 Eigenschaften Gleitkommazahlen:
184 - feinere Auflösung für kleine Zahlen, gröbere Auflösung für
186 - größerer Dynamikbereich
187 - Gleitkomma-DSPs sind teurer, verbrauchen mehr Strom,
188 haben eine niedrigere Taktfrequenz, werden aber gut von
189 C-Compilern unterstützt und sind einfacher zu programmieren
190 (keine Skalierung notwendig!)
192 22 - Was ist das IEEE Gleitkomma-Format?
193 genaue Bezeichnung IEEE 754; Norm die Standarddarstellungen für binäre
194 Gleitkommazahlen in Computern definiert, legt aber auch genaue
195 Verfahren für die Durchführung mathematischer Operationen, insbesondere
196 für Rundungen, sowie Exceptions (Division durch Null, Overflow etc.)
199 allgemeine Darstellung einer Gleitkommazahl:
201 s ... Vorzeichen (bestehend aus 1 Bit)
203 b ... Basis (hier b=2)
207 x = (-1)^s * m * 2^{e-127}
208 IEEE 32-Bit floating-point:
210 e ... Bit 1 bis 8 (=8 Bits)
211 m ... Bit 9 bis 31 (=23 Bits)
213 warum 2^{e-127}? Leichtere Vergleichbarkeit!
215 zwei Grunddatenformate:
216 single precision (32 bit, len(m)=23 bit, len(e)=8 bit)
217 double precision (64 bit, len(m)=52 bit, len(e)=11 bit)
218 zwei erweiterte Formate:
219 single extended (>42 bit, len(m)>30 bit, len(e)>10 bit)
220 double extended (>78 bit, len(m)>62 bit, len(e)>14 bit)
222 enthält auch Konventionen für die Darstellungen spezieller Zahlen,
223 z.B. NaN (not a number), oder Unendlich (Spezialwerte vom Exponent
226 23 - Was ist Pipelining und welche typischen Stufen treten in einer Pipeline
228 Prinzip: Instruktionen werden in mehrere Phasen zerlegt, diese
229 Phasen können parallel ausgeführt werden; die Verwendung von
230 unabhängigen Prozessor-Ressourcen wird dadurch optimiert.
231 Sobald die Pipeline voll ist, kann theoretisch eine ganze Instruktion
232 pro Taktzyklus abgearbeitet werden!
234 Instr. PreFetch: store address of instruction to be fetched
235 Instr. Fetch: loads operation code
236 Instr. Decode: decodes the fetched instruction
237 Instr. Access: reading operand address, modifying registers
238 Instr. Read: reads data from the data buses
239 Instr. Execute: executes instruction and writes if required
241 24 - Was versteht man unter Superskalar-Architekturen? Was versteht man unter
242 VLIW-Architekturen? Wodurch unterscheiden sich die beiden?
243 Superskalarität: Fähigkeit eines Prozessors, mehrere Befehle aus einem
244 Befehlsstrom gleichzeitig mit mehreren parallel arbeitenden
245 Funktionseinheiten zu verarbeiten. Es handelt sich dabei um eine
246 Parallelität auf Befehlsebene, bei der die feinkörnige Nebenläufigkeit
247 zwischen den einzelnen Befehlen ausgenutzt wird.
248 VLIW-Architektur: VLIW steht für "Very Long Instruction Word" und
249 bezeichnet eine Befehlssatzarchitektur-Technik, bei der deutlich
250 längere Befehle zum Einsatz kommen, die die parallel auszuführenden
251 Befehle enthalten. Es handelt sich dabei ebenfalls um Parallelität auf
254 Unterschiede: bei superskalaren Architekturen werden die Befehle
255 vom Prozessor dynamisch auf die einzelnen Funktionseinheiten verteilt,
256 während VLIW diese Aufteilung statisch vom Compiler erledigen lässt.
259 25 - Was sind Kaskaden in IIR-Filtern? Warum verwendet man sie?
260 Beim kaskadieren, d.h. hintereinanderschachteln, von IIR-Filtern werden
261 stets welche (max.) 2. Ordnung verwendet, was folgende Vorteile bringt:
262 - einfacher zu entwerfen, weniger Entwicklungsaufwand
263 - weniger anfällig für Quantisierungsfehler
264 - weniger anfällig für Stabilitätsprobleme
265 Ein großer Nachteil ist jedoch, dass die Aufteilung der Pole und
266 Nullstellen auf die Subsysteme 2. Ordnung nicht trivial ist!
268 26 - Was versteht man unter einem Zirkulärbuffer?
269 Auch "Ringbuffer" genannt - in solch einem Buffer wird das älteste
270 Element durch das neueste ersetzt und der Pointer auf dieses Element
271 gesetzt. Er kommt vor allem bei FIR-Filtern zum Einsatz, da mit
272 einem Ringbuffer effizient auf die letzten Elemente zugegriffen werden
275 27 - Was versteht man unter Bit-Reversal bei DSP-Architekturen?
276 Die Bit-Reversed-Adressierung ist nützlich, um FFTs (Fast Fourier
277 Transformationen) schneller zu implementieren. Da die Eingangswerte
278 nicht der ueblichen numerischen Ordnung folgen (bei einer 8-Punktfolge
279 ist die Ordnung 0, 4, 2, 6, 1, 5, 3, 7), kann diese Adressierung
280 dazu verwendet werden, die benoetigten Daten schneller anzulegen
281 Es ist also nicht noetig, die Bits mit zusaetzlichen Befehlen zu
282 korrigieren oder Speicherinhalte auszutauschen. [doc]