Ausarbeitung der typischen Prüfungsfragen zur Vorlesung "Signalprozessoren" Teil 2/2 - von Sebastian Falbesoner 14 - Wie kann mit der DFT das Spektrum einer aperiodischen Funktion annähernd berechnet werden? Die DFT funktioniert nur für periodische Folgen, deshalb ist die Signaldarstellung im Zeit- und Frequenzbereich immer periodisch. In der Realität hat jedes Signal aber einen Anfang und ein Ende. Um eine nicht-periodische Funktion anzunähern benutzt man Zero-Padding, d.h. man fügt in die periodische Funktion Nullen ein. Falls man die Anzahl der Nullen gegen Unendlich laufen lässt, erhält man die DTFT (Discrete Time Fourier Transformation), die aber nur von theoretischem Interesse ist, da sie ein unendliches Spektrum hat. [inff] 15 - Sie wollen benachbarte Spektrallinien der Frequenzen f und f + delta(f) auflösen. Wie stellen Sie sicher, dass die Spektrallinien getrennt werden? Hinweis: Zero Padding verbessert die Trennung zweier Nahe nebeneinander liegender Spektralkomponenten nicht! Um die spektrale Auflösung von zwei Signalen zu verbessern, müssen bei der Abtastung mehr Signalproben (ungleich Null) genommen werden. Um zwei benachbarte Spektrallinien auflösen zu können, muss der Abstand der Spektrallinien >= als der Abstand des Frequenzrasters sein! [Frequenzraster = f_s / N f_s ... Abtastfrequenz des Originalsignals N ... Anzahl der Samples] 16 - Was ist die FFT und wie wird sie berechnet? Die FFT (Fast Fourier Transformation) ist ein Algorithmus zur effizienten Berechnung der Werte einer DFT. Es handelt sich um ein "divide and conquer" (Teile und Herrsche) Verfahren und im Gegensatz zur direkten Berechnung werden zuvor berechnete Zwischenergebnisse wiederverwendet, was arithmetische Rechenoperationen einspart. Voraussetzung: Anzahl der Abtastpunkte ist eine Zweierpotenz! Eine N-Punkt-Folge wird aufgeteilt in zwei N/2-Punkt Folgen [Zahl der Operationen: Reduzierung von ~N^2 auf 2x(N/2)^2 = N^2/2] 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: alle Bits invertieren - 0 ist zweimal vorhanden (-0, +0) Zweierkomplement (Two's complement): - meistens verwendet in DSPs - Addition und Subtraktion mit selber Hardware möglich - Bildung negativer Zahl: Einerkompliment + 1 - 0 ist nur einmal vorhanden Sign-Magnitude: - Einfache Erzeugung negativer Zahlen - schlecht geeignet zum Rechnen - nur in speziellen Hardware-Implementierungen verwendet - Bildung negativer Zahl: MSB auf 1 setzen, Rest bleibt gleich Offset Binary: - verwendet in A/D-Wandlern - Bildung negativer Zahl: wie Zweierkomplement, MSB vertauschen 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? Bei der Festkommadarstellung befindet sich der Dezimalpunkt für Kommazahlen an einem fixen Punkt und für den Bereich nach und vor diesem wird eine fixe Anzahl an Bits verwendet; man beschreibt daher dieses Format auch mit Qm.n Je mehr Bits man für den Bereich nach dem Fixpunkt spendiert, desto höher wird natürlich die Genauigkeit der Kommazahlen. Das selbe gilt für den Dynamikbereich: je mehr Bits für die Stellen vor dem Fixpunkt verwendet werden, desto mehr ganzzahlige Werte vor dem Dezimalpunkt sind möglich. Die Qm.n Formate haben aber insgesamt eine fixe Größe, deshalb gilt hier, je höher der Dynamikbereich, desto weniger Bits bleiben für den Nachkommaanteil übrig und desto ungenauer werden die Kommazahlen, und umgekehrt fällt der ganzzahlige Anteil umso kleiner aus, je mehr Bits man für hohe Genauigkeit investiert. Die Extreme eines 16-Bit Qm.n sind zum Beispiel: Q0.15: höchste Präzision, jedoch insgesamt nur ein Wertebereich von -1 bis 0.999999... Q15.0: höchster Dynamikbereich, Nachkommaanteil gar nicht vorhanden, entspricht einem Integer mit Wertebereich -32768 bis 32767! 21 - Welche Vor- und Nachteile haben Fest- und Gleitkomma-DSPs? Eigenschaften Festkommazahlen: - gleichmäßige Auflösung über den gesamten Zahlenbereich - kleiner Dynamikbereich - Festkomma-DSPs sind billiger, verbrauchen weniger Strom, haben eine höhere Taktfrequenz, werden aber nur sehr schwach von C-Compilern unterstützt (meist in Assembler programmiert); Overflow- und Quantisierungsfehler müssen softwareseitig gelöst werden Eigenschaften Gleitkommazahlen: - feinere Auflösung für kleine Zahlen, gröbere Auflösung für große Zahlen - größerer Dynamikbereich - Gleitkomma-DSPs sind teurer, verbrauchen mehr Strom, haben eine niedrigere Taktfrequenz, werden aber gut von C-Compilern unterstützt und sind einfacher zu programmieren (keine Skalierung notwendig!) 22 - Was ist das IEEE Gleitkomma-Format? genaue Bezeichnung IEEE 754; Norm die Standarddarstellungen für binäre Gleitkommazahlen in Computern definiert, legt aber auch genaue Verfahren für die Durchführung mathematischer Operationen, insbesondere für Rundungen, sowie Exceptions (Division durch Null, Overflow etc.) fest! allgemeine Darstellung einer Gleitkommazahl: x = s * m * b^e s ... Vorzeichen (bestehend aus 1 Bit) m ... Mantisse 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) zwei erweiterte Formate: single extended (>42 bit, len(m)>30 bit, len(e)>10 bit) double extended (>78 bit, len(m)>62 bit, len(e)>14 bit) enthält auch Konventionen für die Darstellungen spezieller Zahlen, z.B. NaN (not a number), oder Unendlich (Spezialwerte vom Exponent 0 und 255!) 23 - Was ist Pipelining und welche typischen Stufen treten in einer Pipeline auf? Prinzip: Instruktionen werden in mehrere Phasen zerlegt, diese Phasen können parallel ausgeführt werden; die Verwendung von unabhängigen Prozessor-Ressourcen wird dadurch optimiert. Sobald die Pipeline voll ist, kann theoretisch eine ganze Instruktion pro Taktzyklus abgearbeitet werden! Typische Phasen: Instr. PreFetch: store address of instruction to be fetched Instr. Fetch: loads operation code Instr. Decode: decodes the fetched instruction Instr. Access: reading operand address, modifying registers Instr. Read: reads data from the data buses Instr. Execute: executes instruction and writes if required 24 - Was versteht man unter Superskalar-Architekturen? Was versteht man unter VLIW-Architekturen? Wodurch unterscheiden sich die beiden? Superskalarität: Fähigkeit eines Prozessors, mehrere Befehle aus einem Befehlsstrom gleichzeitig mit mehreren parallel arbeitenden Funktionseinheiten zu verarbeiten. Es handelt sich dabei um eine Parallelität auf Befehlsebene, bei der die feinkörnige Nebenläufigkeit zwischen den einzelnen Befehlen ausgenutzt wird. VLIW-Architektur: VLIW steht für "Very Long Instruction Word" und bezeichnet eine Befehlssatzarchitektur-Technik, bei der deutlich längere Befehle zum Einsatz kommen, die die parallel auszuführenden Befehle enthalten. Es handelt sich dabei ebenfalls um Parallelität auf Instruktionsebene. Unterschiede: bei superskalaren Architekturen werden die Befehle vom Prozessor dynamisch auf die einzelnen Funktionseinheiten verteilt, während VLIW diese Aufteilung statisch vom Compiler erledigen lässt. [doc] 25 - Was sind Kaskaden in IIR-Filtern? Warum verwendet man sie? Beim kaskadieren, d.h. hintereinanderschachteln, von IIR-Filtern werden stets welche (max.) 2. Ordnung verwendet, was folgende Vorteile bringt: - einfacher zu entwerfen, weniger Entwicklungsaufwand - weniger anfällig für Quantisierungsfehler - weniger anfällig für Stabilitätsprobleme Ein großer Nachteil ist jedoch, dass die Aufteilung der Pole und Nullstellen auf die Subsysteme 2. Ordnung nicht trivial ist! 26 - Was versteht man unter einem Zirkulärbuffer? Auch "Ringbuffer" genannt - in solch einem Buffer wird das älteste Element durch das neueste ersetzt und der Pointer auf dieses Element gesetzt. Er kommt vor allem bei FIR-Filtern zum Einsatz, da mit einem Ringbuffer effizient auf die letzten Elemente zugegriffen werden kann. [inff] 27 - Was versteht man unter Bit-Reversal bei DSP-Architekturen? Die Bit-Reversed-Adressierung ist nützlich, um FFTs (Fast Fourier Transformationen) schneller zu implementieren. Da die Eingangswerte nicht der ueblichen numerischen Ordnung folgen (bei einer 8-Punktfolge ist die Ordnung 0, 4, 2, 6, 1, 5, 3, 7), kann diese Adressierung dazu verwendet werden, die benoetigten Daten schneller anzulegen Es ist also nicht noetig, die Bits mit zusaetzlichen Befehlen zu korrigieren oder Speicherinhalte auszutauschen. [doc]