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         TODO
 109
 110 20 - Wie hängen Dynamikbereich und Genauigkeit bei der Festkommadarstellung
 111      zusammen?
 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
 116
 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.
 127
 128         Die Extreme eines 16-Bit Qm.n sind zum Beispiel:
 129         Q0.15: höchste Präzision, jedoch insgesamt nur ein Wertebereich von
 130                -1 bis 0.999999...
 131         Q15.0: höchster Dynamikbereich, Nachkommaanteil gar nicht vorhanden,
 132                entspricht einem Integer mit Wertebereich -32768 bis 32767!
 133
 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
 142                   gelöst werden
 143
 144         Eigenschaften Gleitkommazahlen:
 145                 - feinere Auflösung für kleine Zahlen, gröbere Auflösung für
 146                   große Zahlen
 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!)
 152
 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.)
 158         fest!
 159
 160         allgemeine Darstellung einer Gleitkommazahl:
 161                 x = s * m * b^e
 162         s ... Vorzeichen (bestehend aus 1 Bit)
 163         m ... Mantisse
 164         b ... Basis (hier b=2)
 165         e ... Exponent
 166
 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)
 173
 174         enthält auch Konventionen für die Darstellungen spezieller Zahlen,
 175         z.B. NaN (not a number), oder Unendlich (Spezialwerte vom Exponent
 176         0 und 255!)
 177
 178 23 - Was ist Pipelining und welche typischen Stufen treten in einer Pipeline
 179      auf?
 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!
 185         Typische Phasen:
 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
 192
 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
 204         Instruktionsebene.
 205
 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.
 209         [doc]
 210
 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!
 219
 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
 225         kann. [inff]
 226
 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]