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 vertauscht
104 18 - Wie wirken sich Quantisierungsfehler auf ein Signal aus?
107 19 - Welche Bedeutung hat der Lastfaktor?
110 20 - Wie hängen Dynamikbereich und Genauigkeit bei der Festkommadarstellung
112 Bei der Festkommadarstellung befindet sich der Dezimalpunkt für
113 Kommazahlen an einem fixen Punkt und für den Bereich nach und vor
114 diesem wird eine fixe Anzahl an Bits verwendet; man beschreibt daher
115 dieses Format auch mit Qm.n
117 Je mehr Bits man für den Bereich nach dem Fixpunkt spendiert, desto
118 höher wird natürlich die Genauigkeit der Kommazahlen. Das selbe
119 gilt für den Dynamikbereich: je mehr Bits für die Stellen vor dem
120 Fixpunkt verwendet werden, desto mehr ganzzahlige Werte vor dem
121 Dezimalpunkt sind möglich.
122 Die Qm.n Formate haben aber insgesamt eine fixe Größe, deshalb gilt
123 hier, je höher der Dynamikbereich, desto weniger Bits bleiben für
124 den Nachkommaanteil übrig und desto ungenauer werden die Kommazahlen,
125 und umgekehrt fällt der ganzzahlige Anteil umso kleiner aus, je mehr
126 Bits man für hohe Genauigkeit investiert.
128 Die Extreme eines 16-Bit Qm.n sind zum Beispiel:
129 Q0.15: höchste Präzision, jedoch insgesamt nur ein Wertebereich von
131 Q15.0: höchster Dynamikbereich, Nachkommaanteil gar nicht vorhanden,
132 entspricht einem Integer mit Wertebereich -32768 bis 32767!
134 21 - Welche Vor- und Nachteile haben Fest- und Gleitkomma-DSPs?
135 Eigenschaften Festkommazahlen:
136 - gleichmäßige Auflösung über den gesamten Zahlenbereich
137 - kleiner Dynamikbereich
138 - Festkomma-DSPs sind billiger, verbrauchen weniger Strom,
139 haben eine höhere Taktfrequenz, werden aber nur sehr schwach
140 von C-Compilern unterstützt (meist in Assembler programmiert);
141 Overflow- und Quantisierungsfehler müssen softwareseitig
144 Eigenschaften Gleitkommazahlen:
145 - feinere Auflösung für kleine Zahlen, gröbere Auflösung für
147 - größerer Dynamikbereich
148 - Gleitkomma-DSPs sind teurer, verbrauchen mehr Strom,
149 haben eine niedrigere Taktfrequenz, werden aber gut von
150 C-Compilern unterstützt und sind einfacher zu programmieren
151 (keine Skalierung notwendig!)
153 22 - Was ist das IEEE Gleitkomma-Format?
154 genaue Bezeichnung IEEE 754; Norm die Standarddarstellungen für binäre
155 Gleitkommazahlen in Computern definiert, legt aber auch genaue
156 Verfahren für die Durchführung mathematischer Operationen, insbesondere
157 für Rundungen, sowie Exceptions (Division durch Null, Overflow etc.)
160 allgemeine Darstellung einer Gleitkommazahl:
162 s ... Vorzeichen (bestehend aus 1 Bit)
164 b ... Basis (hier b=2)
167 zwei Grunddatenformate:
168 single precision (32 bit, len(m)=23 bit, len(e)=8 bit)
169 double precision (64 bit, len(m)=52 bit, len(e)=11 bit)
170 zwei erweiterte Formate:
171 single extended (>42 bit, len(m)>30 bit, len(e)>10 bit)
172 double extended (>78 bit, len(m)>62 bit, len(e)>14 bit)
174 enthält auch Konventionen für die Darstellungen spezieller Zahlen,
175 z.B. NaN (not a number), oder Unendlich (Spezialwerte vom Exponent
178 23 - Was ist Pipelining und welche typischen Stufen treten in einer Pipeline
180 Prinzip: Instruktionen werden in mehrere Phasen zerlegt, diese
181 Phasen können parallel ausgeführt werden; die Verwendung von
182 unabhängigen Prozessor-Ressourcen wird dadurch optimiert.
183 Sobald die Pipeline voll ist, kann theoretisch eine ganze Instruktion
184 pro Taktzyklus abgearbeitet werden!
186 Instr. PreFetch: store address of instruction to be fetched
187 Instr. Fetch: loads operation code
188 Instr. Decode: decodes the fetched instruction
189 Instr. Access: reading operand address, modifying registers
190 Instr. Read: reads data from the data buses
191 Instr. Execute: executes instruction and writes if required
193 24 - Was versteht man unter Superskalar-Architekturen? Was versteht man unter
194 VLIW-Architekturen? Wodurch unterscheiden sich die beiden?
195 Superskalarität: Fähigkeit eines Prozessors, mehrere Befehle aus einem
196 Befehlsstrom gleichzeitig mit mehreren parallel arbeitenden
197 Funktionseinheiten zu verarbeiten. Es handelt sich dabei um eine
198 Parallelität auf Befehlsebene, bei der die feinkörnige Nebenläufigkeit
199 zwischen den einzelnen Befehlen ausgenutzt wird.
200 VLIW-Architektur: VLIW steht für "Very Long Instruction Word" und
201 bezeichnet eine Befehlssatzarchitektur-Technik, bei der deutlich
202 längere Befehle zum Einsatz kommen, die die parallel auszuführenden
203 Befehle enthalten. Es handelt sich dabei ebenfalls um Parallelität auf
206 Unterschiede: bei superskalaren Architekturen werden die Befehle
207 vom Prozessor dynamisch auf die einzelnen Funktionseinheiten verteilt,
208 während VLIW diese Aufteilung statisch vom Compiler erledigen lässt.
211 25 - Was sind Kaskaden in IIR-Filtern? Warum verwendet man sie?
212 Beim kaskadieren, d.h. hintereinanderschachteln, von IIR-Filtern werden
213 stets welche (max.) 2. Ordnung verwendet, was folgende Vorteile bringt:
214 - einfacher zu entwerfen, weniger Entwicklungsaufwand
215 - weniger anfällig für Quantisierungsfehler
216 - weniger anfällig für Stabilitätsprobleme
217 Ein großer Nachteil ist jedoch, dass die Aufteilung der Pole und
218 Nullstellen auf die Subsysteme 2. Ordnung nicht trivial ist!
220 26 - Was versteht man unter einem Zirkulärbuffer?
221 Auch "Ringbuffer" genannt - in solch einem Buffer wird das älteste
222 Element durch das neueste ersetzt und der Pointer auf dieses Element
223 gesetzt. Er kommt vor allem bei FIR-Filtern zum Einsatz, da mit
224 einem Ringbuffer effizient auf die letzten Elemente zugegriffen werden
227 27 - Was versteht man unter Bit-Reversal bei DSP-Architekturen?
228 Die Bit-Reversed-Adressierung ist nützlich, um FFTs (Fast Fourier
229 Transformationen) schneller zu implementieren. Da das Endergebnis
230 solcher Transformationen "bit-reversed" ist, kann diese Adressierung
231 dazu verwendet werden, die errechneten Daten in brauchbarer Form im
232 Speicher abzulegen. Es ist also nicht nötig, die Bits mit zusätzlichen
233 Befehlen zu korrigieren und Speicherinhalte auszutauschen. [doc]