ausarb2.txt

   1 Ausarbeitung der typischen Prüfungsfragen zur Vorlesung "Signalprozessoren"
   2 Teil 2/2 - von Sebastian Falbesoner <e0725433@student.tuwien.ac.at>
   3
   4 14 - Wie kann mit der DFT das Spektrum einer aperiodischen Funktion annähernd
   5      berechnet werden?
   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.
  14         [inff]
  15
  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.
  22
  23         Um zwei benachbarte Spektrallinien auflösen zu können, muss der Abstand
  24         der Spektrallinien <= als der Abstand des Frequenzrasters sein!
  25
  26         [Frequenzraster = f_s / N
  27          f_s ... Abtastfrequenz des Originalsignals
  28          N   ... Anzahl der Samples]
  29
  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!
  37
  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)]
  42
  43         by wurm:
  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
  48         Symmetrie aufweist:
  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
  57
  58         weiters kann man nun die Beziehung
  59         > W^2_N = W_{N/2}
  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}}
  62
  63         also erhalten wir:
  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}
  66
  67         vereinfacht angeschrieben ist das:
  68         > X[k] = X_g[m] + W^k_N \cdot X_u[m]
  69
  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
  74
  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).
  84
  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
  95         Sign-Magnitude:
  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
 100         Offset Binary:
 101                 - verwendet in A/D-Wandlern
 102                 - Bildung negativer Zahl: wie Zweierkomplement, MSB vertauscht
 103
 104 18 - Wie wirken sich Quantisierungsfehler auf ein Signal aus?
 105         TODO
 106
 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.
 112
 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
 117         > =>
 118         > \sigma^2_{A/D-Rauschen} = \frac{(2 U_p)^2}{12(2^b)} =
 119         > \frac{U^2_p}{3\cdot 2^{2b}}
 120
 121         Der Lastfaktor berechnet sich nun wie folgt:
 122         > LF = \frac{Effektivwert}{Spitzenwert}
 123
 124         Ein Rechtecksignal hat z.B. einen LF=1; ein Sinussignal
 125         LF=\frac{1}{\sqrt{2}} = 0.71
 126
 127         Anders angeschrieben berechnet sich der Lastfaktor
 128         > LF = \frac{\sigma_{Signal}}{U_p}
 129         daraus folgt
 130         > \sigma^2_{Signal} = (LF)^2 U^2_p
 131
 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)
 136
 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}) =
 140         > 1.76 + 6.02 * b
 141
 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
 145         uebersteuert!
 146         Weiters ist es unzweckmaessig einen A/D-Wandler einzusetzen der einen
 147         deutlich besseres SNR hat als das zu wandlende kontinuierliche Signal!
 148
 149 20 - Wie hängen Dynamikbereich und Genauigkeit bei der Festkommadarstellung
 150      zusammen?
 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
 155
 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.
 166
 167         Die Extreme eines 16-Bit Qm.n sind zum Beispiel:
 168         Q0.15: höchste Präzision, jedoch insgesamt nur ein Wertebereich von
 169                -1 bis 0.999999...
 170         Q15.0: höchster Dynamikbereich, Nachkommaanteil gar nicht vorhanden,
 171                entspricht einem Integer mit Wertebereich -32768 bis 32767!
 172
 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
 181                   gelöst werden
 182
 183         Eigenschaften Gleitkommazahlen:
 184                 - feinere Auflösung für kleine Zahlen, gröbere Auflösung für
 185                   große Zahlen
 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!)
 191
 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.)
 197         fest!
 198
 199         allgemeine Darstellung einer Gleitkommazahl:
 200                 x = s * m * b^e
 201         s ... Vorzeichen (bestehend aus 1 Bit)
 202         m ... Mantisse
 203         b ... Basis (hier b=2)
 204         e ... Exponent
 205
 206         bei IEEE 754:
 207         x = (-1)^s * m * 2^{e-127}
 208         IEEE 32-Bit floating-point:
 209         s ... 1 Bit
 210         e ... Bit 1 bis 8 (=8 Bits)
 211         m ... Bit 9 bis 31 (=23 Bits)
 212
 213         warum 2^{e-127}? Leichtere Vergleichbarkeit!
 214
 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)
 221
 222         enthält auch Konventionen für die Darstellungen spezieller Zahlen,
 223         z.B. NaN (not a number), oder Unendlich (Spezialwerte vom Exponent
 224         0 und 255!)
 225
 226 23 - Was ist Pipelining und welche typischen Stufen treten in einer Pipeline
 227      auf?
 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!
 233         Typische Phasen:
 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
 240
 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
 252         Instruktionsebene.
 253
 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.
 257         [doc]
 258
 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!
 267
 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
 273         kann. [inff]
 274
 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 das Endergebnis
 278         solcher Transformationen "bit-reversed" ist, kann diese Adressierung
 279         dazu verwendet werden, die errechneten Daten in brauchbarer Form im
 280         Speicher abzulegen. Es ist also nicht nötig, die Bits mit zusätzlichen
 281         Befehlen zu korrigieren und Speicherinhalte auszutauschen. [doc]