Digitale Signalverarbeitung Formeln Zusammenfassung PDF

Preview

Summary

Zusammenfassung der Formeln von der ganze Vorlesung...

Description

DSV Formelsammlung

WS 17/18

30.10.17

DSV Formelsammlung 1 Allgemeines SV: Verarbeitung von Signalen zu Info oder anderem Signal Sinus-Cosinus-Tabelle: φ sin(φ) 0 0 𝜋⁄ 1⁄ 6 2 𝜋⁄ 1⁄ 4 √2 𝜋⁄ √3 ⁄ 3 2 𝜋⁄ 1 2

cos(φ) 1 √3⁄ 2 1⁄ √2 1⁄ 2 0

Unschärferelation: 𝐴𝑏𝑡𝑎𝑠𝑡𝑓𝑟𝑒𝑞𝑢𝑒𝑛𝑧 ∙ 𝐾𝑜𝑚𝑝𝑙𝑒𝑥𝑖𝑡ä𝑡 ≤ 𝑣𝑒𝑟𝑓ü𝑔𝑏𝑎𝑟𝑒 𝑅𝑒𝑐ℎ𝑒𝑛𝑙𝑒𝑖𝑠𝑡𝑢𝑛𝑔 Zeitdiskrete Fourier-Reihe: • •

Fourierkoeffizienten: 𝑐𝑘 = Fourier-Reihe: 𝑥(𝑛) =

1

𝑁

𝑗 𝑘𝑛 ∑ 𝑁−1 𝑛=0 𝑥(𝑛)𝑒 𝑁 (= 𝑐𝑘+𝑁 )

∑𝑁−1 𝑘=0 𝑐𝑘

∙ 𝑒𝑗

2𝜋 𝑘𝑛 𝑁

2𝜋

AD-Wandler: • Abtastung (zeitdiskret): 𝑥(𝑛) = 𝑥𝑎 (𝑛 ∙ 𝑇𝑛 ), Ts: Abtastintervall, fs: Abtastfrequenz Kein Aliasing: Nyquist-Bedingung (𝐹𝑠 ≥ 𝐵𝑎𝑛𝑑𝑏𝑟𝑒𝑖𝑡𝑒 𝑣𝑜𝑛 𝑥𝑎 (𝑡)) (Antialiasing-Filter) • Quantisierung (wertdiskret): 𝑥𝑞 (𝑛) = 𝑄(𝑥(𝑛)) = 𝑥(𝑛) + 𝑒(𝑛), e(n): Quantisierungsrauschen ~ 𝑏, b: Wortbreite 2 1

• •

Kenndaten: fs (Abtastfrequenz), b (Wortbreite)  𝑥 2 (𝑛)

SNR: 𝑆𝑁𝑅[𝑑𝐵] = 10 ∙ 𝑙𝑜𝑔  = 𝑘𝑜𝑛𝑠𝑡 + 6 ∙ 𝑏 𝑒 2 (𝑛)

Fehlerfreie Interpolation: 𝑦𝑎 (𝑡) = ∑ ∞ 𝑛=−∞ 𝑦𝑞 (𝑛) ∙ 𝑔(𝑡 − 𝑡0 − 𝑛𝑇𝑠,)𝑔(𝑡) = 𝑠𝑖𝑛𝑐(

DA-Wandler: • •

Praktisch: Nichtideale TP-Filter

SuSy-Grundlagen: • Zeitdiskrete Fourier-Reihe: Fourierkoeffizienten: 𝑐𝑘 =

•

•

1

𝑁

𝑗 𝑘𝑛 ∑ 𝑁−1 𝑛=0 𝑥(𝑛)𝑒 𝑁 (= 𝑐𝑘+𝑁 )

∑𝑁−1 𝑘=0 𝑐𝑘

Fourier-Reihe: 𝑥(𝑛) = Leistungsdichtespektrum:

∙ 𝑒𝑗

2𝜋 𝑘𝑛 𝑁

Periodisches Signal: 𝜌𝑃,𝑥 (𝑘) = |𝑐𝑘 |2 = Aperiodisches Signal: 𝜌𝑃,𝑥 (𝜔) = Periodisches Signal: 𝑃𝑥 =

Signalleistung:

1

𝑁

Aperiodisches Signal: 𝑃𝑥 =

𝜋𝑡 ) 𝑇𝑠

1

2𝜋

𝑗 𝑘𝑛 ∑ 𝑁−1 𝑛=0 |𝑥(𝑛) ∙ 𝑒 𝑁 |

𝑁 1 𝑗𝜔)|2 | 𝑋 ( 𝑒 2𝜋

2 ∑ 𝑁−1 𝑛=0 |𝑥(𝑛)| = ∑

2𝜋

2

𝑁−1|𝑐 |2 𝑘=0 𝑘

1 ∞ 1 |𝑥(𝑛)|2 ∫ |𝑋(𝑒 𝑗𝜔)|2 𝑑𝜔 = 2𝜋 ∑ 𝑛=−∞ 4𝜋2 2𝜋

1

DSV Formelsammlung

2

WS 17/18

30.10.17

DSV Formelsammlung

WS 17/18

30.10.17

3

DSV Formelsammlung

WS 17/18

2 z-Transformation Definition: ∞ 𝑋(𝑧) = 𝑍(𝑥(𝑛)) = ∑𝑛=−∞ 𝑥(𝑛) ∙ 𝑧 −𝑛𝜖 ℂ

Konvergenzbereich (KB): 𝐾𝐵 = {𝑧|𝑋(𝑧) < ∞}

Geometrische Reihen: • •

𝑘 ∑𝑁−1 𝑘=𝑀 𝑞 = 𝑘 ∑∞ 𝑘=0 𝑞 =

𝑞𝑚 −𝑞𝑁 1−𝑞 1 1−𝑞

Analog Laplace im Kontinuierlichen Eigenschaften:

4

30.10.17

DSV Formelsammlung

WS 17/18

30.10.17

Rationale z-Transformierte:

• • •

• • •

𝐵(𝑧)

=

𝑧 −𝑀

Übertragungsfkt. – LTI-Systeme:

𝐻(𝑧) = 𝑍(ℎ(𝑛)) =

• •

⁄ ⁄ 𝑧 𝑀−1 + ⋯ + 𝑏𝑀 𝑏 0 𝑏 𝑁 + 𝑎11⁄ 𝑧 𝑁−1 + ⋯ + 𝑎𝑁 ⁄ 𝑧𝑀 𝑎0 𝑏𝑎00

𝑏0 𝑧 𝑏0 + 𝑏1 + ⋯ + 𝑏𝑀 ∙ = −1 −𝑁 𝑎0 𝐴(𝑧) 𝑎0 + 𝑎1 𝑧 + ⋯ + 𝑎𝑁 𝑧 −𝑁 ∙ Polstelle pi: 𝑋(𝑝𝑖 ) → ∞; 𝐵(𝑝𝑖 ) → ∞/ 𝐴(𝑝𝑖 ) = 0 𝑧 -> NIE im KB! Nullstelle ni: 𝑋(𝑝𝑖 ) = 0; 𝐵(𝑛𝑖 ) = 0/ 𝐴(𝑛𝑖 ) → ∞ Trivial: 𝑛𝑖 , 𝑝𝑖 = 0, ∞ o N>M: (N-M) triviale Nullstellen an z=0 o N 2-12 im Skript) o Lage relativ zum Einheitskreis bestimmt Zeitverhalten o Polstellen innerhalb (kausal)/ außerhalb (antikausal) -> |x(n)| klingt ab o Polstellen außerhalb (kausal)/ innerhalb (antikausal) -> |x(n)| steigt unbeschränkt o Einfache Polstelle auf Einheitskreis -> |x(n)| beschränkt o Mehrfache Polstelle auf Einheitskreis -> |x(n)| wächst unbeschränkt o Abstand von Polstellen zum EK groß/klein -> |x(n)| langsame/schnelle Veränderung

𝑋(𝑧) =

𝑧 −1

−𝑀

𝛽(𝑧 −1 ) 𝑌(𝑧) 𝐷𝑖𝑓𝑓.−𝑔𝑙 ⇒ 𝐻(𝑧) = 𝛼(𝑧 −1 ) 𝑋(𝑧)

Diff-gl im Zeitbereich H(z) rational Pol- & Nullstellen Amplitudengang: -> 𝐴(𝜔) = |𝐻(𝑧 = 𝑒 𝑗𝜔 )| nur, wenn 𝐾𝐵 ⊇ {𝑧 ∈ ℂ| |𝑧| = 1}

Stabilität: Kriterien für Stabilität: • ∑∞ 𝑛=−∞ |ℎ(𝑛)|< ∞ |𝑝𝑖 | < 1 ∀𝑖, 𝑤𝑒𝑛𝑛 ℎ(𝑛) 𝑘𝑎𝑢𝑠𝑎𝑙 • { |𝑝𝑖 | > 1 ∀𝑖, 𝑤𝑒𝑛𝑛 ℎ(𝑛) 𝑎𝑛𝑡𝑖𝑘𝑎𝑢𝑠𝑎𝑙 • KB von H(z) enthält EK • Auf Pol- & Nullstellenkürzung achten!

5

DSV Formelsammlung

WS 17/18

30.10.17

Vor- & Nachteile: + + + –

X(z) allgemeiner als 𝑋(𝑒 𝑗𝜔 ) X(z) kann existieren, wenn 𝑋(𝑒 𝑗𝜔 ) nicht existent X(z) ermöglicht Pol- & Nulstellenanalyse, Lösung von Differenzengl., Berechnung der Faltung 𝑋(𝑒 𝑗𝜔 ) = 𝐴(𝜔) ∙ 𝑒𝑗𝜃(𝜔) besser zu interpretieren

Inverse z-Trafo: • Wenn keine Spezifikation -> ALLE Lösungen angeben • Potenzreihenentwicklung: ∞

𝑋(𝑧) = ∑𝑥(𝑛) ∙ 𝑧 −𝑛

•

𝑛

𝑛=−∞

𝑟

𝑑𝑗 𝑐1 +∑ 𝑋(𝑧) = ∑ (1 − 𝑝𝑖 𝑧 −1)𝑗 (1 − 𝑝𝑖 𝑧 −1 )

Partialbruchzerlegung:

𝑖=1

𝑗=1

n: Anzahl der Polstellen, r: Vielfachheit der mehrfachen Polstelle

6

DSV Formelsammlung

WS 17/18

3 Einseitige z-Trafo

𝑋+ (𝑧)

=

𝑍+

30.10.17

∞

(𝑥(𝑛)) = ∑ 𝑥(𝑛) ∙ 𝑧−𝑛 𝑛=0

Allgemeines: • Anwendung, wenn x(n) für n 𝑟} • 𝑋1 + (𝑧) = 𝑋2 + (𝑧) ≠> 𝑋1 (𝑧) = 𝑋2 (𝑧) (kann sein, muss aber nicht!)

Lösen von Differenzengleichungen: Gegeben: • 𝛼(𝐷) ∙ 𝑦(𝑛) = 𝛽(𝐷) ∙ 𝑥(𝑛) • 𝑥(𝑛), 𝑛 ≥ 0 • Anfangswerte: y(-i), x(-i) Gesucht: y(n) • Berechnung: o 𝑍 + (𝛼(𝐷) ∙ 𝑦(𝑛)) = 𝑎0 𝑌 +(𝑧) + ⋯ + 𝑎𝑛 𝑧 −𝑛 (𝑌 +(𝑧) + ⋯ + 𝑦 (−𝑛) ∙ 𝑧 𝑛 ) = 𝛼(𝑧 −1 ) ∙ 𝑌 + (𝑧) + 𝛾(𝑧 −1 , 𝑦 (−1), … , 𝑦(−𝑛)) o 𝑍 + (𝛽(𝐷) ∙ 𝑥(𝑛)) = 𝑏0 𝑋+ (𝑧) + ⋯ + 𝑏𝑀 𝑧 −𝑚(𝑋+ (𝑧) + ⋯ + 𝑥(−𝑚) ∙ 𝑧 𝑚 ) = 𝛽(𝑧 −1 ) ∙ 𝑋 + (𝑧) + 𝜎(𝑧 −1 , 𝑥(−1), … , 𝑥(−𝑛)) •

•

𝑌 + (𝑧) =

𝛽(𝑧 −1)

𝛼(𝑧 −1)

𝑋+ (𝑧) +

𝜎(𝑧−1,𝑥(−1),…,𝑥(−𝑛))− 𝛾(𝑧−1,𝑦(−1),…,𝑦(−𝑛)) 𝛼(𝑧−1)

Y(n) mit Rücktrafo (ACHTUNG: Auch AW in Lösung aufnehmen!) 7

DSV Formelsammlung

WS 17/18

30.10.17

4 Digitale Filter (LTI) System, das Eingangssignal nach (frequenzselektivem) Kriterium verarbeitet und Ausgangssignal liefert. Ideale Filter: 𝐻(𝑒 𝑗𝜔 ) = 𝐴(𝜔) ∙ 𝑋(𝑒 𝑗𝜔 ) •

• • •

Keine Verzerrung (konst. Amplitudengang) im Durchlassbereich -> 𝐴(𝜔) = |𝐻 (𝑧 = 𝑒 𝑗𝜔 )| nur, wenn 𝐾𝐵 ⊇ {𝑧 ∈ ℂ| |𝑧| = 1} Komplett gesperrt im Sperrbereich Unendlich schneller Übergang 1 ,𝑧 = 0 𝑠𝑖𝑛𝑐(𝑧) = { sin(𝑧) ,𝑧 ≠ 0 𝑧 (Problem: Filter nicht kausal, Bruch der Unschärferelation)

Entwurfsmethoden: 1. Pol-Nullstellen-Plazierung:

−1 ∏𝑀 1+∑ 𝑀 𝑏𝑖 𝑧 −𝑖 𝑖=1 𝑖=1 (1 − 𝑛𝑖 𝑧 ) = 𝑐 𝑁 𝑁 ∏𝑖=1 (1 − 𝑝𝑖 𝑧 −1 ) 1 ∑ 𝑖=1 𝑎𝑖 𝑧 −𝑖 + Abstand der Pol- /Nullstellen zum EK entscheidet über Filterverhalten

𝐻(𝑧) = 𝑐

8

DSV Formelsammlung

WS 17/18

30.10.17

2. Approximation eines idealen Filters: a. Filterspezifikation (Toleranzschema) Bereiche mit Ripple δs & Grenzfrequenz ωg b. Suche nach N,M, ai, bi, sodass Filterspezifikation erfüllt Vor- & Nachteile: + Systematisch (alle Filtertypen) + Kontrollierte Filterqualität – Aufwändiger Entwurf Tiefpass (TP): • Polstelle um 0, Nullstelle um 𝜋 • Gleitender MW:

•

o

ℎ(𝑛) =

o

ℎ(𝑛) = (1 − 𝑎) ∙ 𝑎 𝑛 ∙ 𝑢(𝑛) → 𝐻(𝑧) = 1−𝑎𝑧 −1

−𝑛 ∙ (𝑢(𝑛) − 𝑢(𝑛 − 𝑀)) → 𝐻(𝑧) = 𝑀 ∑ 𝑀−1 𝑛=0 𝑧 o Sequentiell: Multiplikationen: 1, Additionen: M, Speicher M-1, Gedächtnis: M-1 o Rekursiv: Multiplikationen: 1, Additionen: 2, Speicher M+1, Gedächtnis: M-1 Exponentiell gewichteter MW:

o

1

1

𝑀

1−𝑎

Sequentiell: Multiplikationen: 2, Additionen: 1, Speicher 1, Gedächtnis: 1/(1-a)

Hochpass (HP): • Nullstelle um 0, Polstelle um 𝜋 • HP aus TP: HHP(z)=HTP(-z) (Spiegelung in z ist Verschiebung um 𝜋 in Spektrum) Bandpass (BP): • Polstellen um ±𝜔0, Nullstellen bei 0, 𝜋 •

𝐻(𝑧) = 𝑐

(1−𝑧−2)

(1−𝑟𝑒 𝑗𝜔0 𝑧 −1)(1−𝑟𝑒 −𝑗𝜔0 𝑧−1)

, r1: Kerb schmaler, aber längere (1−𝑒 𝑗𝜔0 𝑧−1)(1−𝑒 −𝑗𝜔0 𝑧 −1)

Transientzeit) Wenn mehrere Störungen: Kaskadierung Variable Frequenz -> adaptives Filter

Kammfilter (notch-filter): • Ansätze: Kaskadierung Kerbfilter, Überabtastung Gleichanteil-Kerbfilter

1−𝑧−𝑛 ℎ ( ) , 𝑛 = 𝑘𝑁, 𝑘 ∈ ℤ → 𝐻𝐾𝑎𝑚𝑚 (𝑧) = 𝐻𝐾𝑒𝑟𝑏 (𝑧 𝑛 ) = 𝑐 1−𝑟∙𝑧−𝑛 (Streckung ℎ𝐾𝑎𝑚𝑚 (𝑛) = { 𝐾𝑒𝑟𝑏 𝑁 0, 𝑠𝑜𝑛𝑠𝑡 der ω-Achse um Faktor n (Bei Pol- & Nullstellenberechnung auf komplexe Wurzel achten!) Vor- & Nachteile:

•

• •

𝑛

Kammfilter einsetzbar, wenn Grundfrequenz von i: 𝑓𝑖 =

Kaskade von Kerbfiltern immer einsetzbar

𝐹𝑠 𝑁

9

DSV Formelsammlung

WS 17/18

Digitaler Sinusgenerator: Methoden zur Erstellung: • •

Taylor-Reihe: sin 𝑧 = 𝑧 − 𝑧 3 + 1 𝑧 5 − ⋯ 5 3 1

𝑏𝑧 𝑦(𝑛) = 𝐴 ∙ sin(𝜔0 𝑛) → 𝑌 + (𝑧) = 1+𝑎𝑧 −1+𝑧−2 = −1

30.10.17

(𝐴∙sin (𝜔0 ))𝑧−1

1−(2∙cos(𝜔0 ))𝑧−1+𝑧 −2

Lösung 1: y(-1)=y(-2)=0 -> 𝑥(𝑛) = 𝑏 ∙ 𝛿(𝑛 − 1) Lösung 2: x(n)=0, 𝑦(−1) = −𝑏 = −𝐴 ∙ sin(𝜔0 ), 𝑦(−2) = 𝑎𝑏 = −𝐴 ∙ sin(𝜔0 )

Digitaler Sinusgenerator instabil (𝐴(±𝜔0 ) = ∞), Polstellen 𝑝1/2 = 𝑒 ±𝑗𝜔0 erforderlich

Linearphasige Filter: Definition: • 𝑙𝑖𝑛𝑒𝑎𝑟𝑝ℎ𝑎𝑠𝑖𝑔 ↔ 𝐻(𝑒 𝑗𝜔 ) = 𝐴(𝜔) ∙ 𝑒 𝑗𝜃(𝜔) = 𝐻0 (𝜔) ∙ 𝑒 𝑗𝜃0−𝜔∙𝛼 /𝐻0 (𝜔) ∙ 𝑒 𝑗𝜃0 −𝜔∙𝛼+𝜋 (stückweise linear) •

𝐺𝑟𝑢𝑝𝑝𝑒𝑛𝑙𝑎𝑢𝑓𝑧𝑒𝑖𝑡: 𝜏𝑔 (𝜔) = −

Typen: • FIR-Filter: Siehe Tabelle • IIR-Filter: Nicht realisierbar!!!!!

𝑑𝜃(𝜔) = 𝑑𝜔

𝛼

Warum: • Gleiche Laufzeit für alle Freq. -> Keine Phasenverzerrung (manchmal wichtig) • Ca. M/2 anstatt M Multiplikationen

Allpass: 𝐴(𝜔) = 1 für alle Frequenzen! Allgemein: 𝐻(𝑧) =

stabil -> 0< 1 Minimalphasige Filter:

Eigenschaften: • Kanalentzerrung: Kausales, stabiles minimalphasiges inverses Filter YH zu jedem kausalen, stabilen, minimalphasigen Filter H (Vertauschen von Pol & Nullstellen) • Jedes kausale, stabile Filter: 𝐻(𝑧) = 𝐻𝑚𝑖𝑛 (𝑧) ∙ 𝐻𝐴𝑃 (𝑧) mit 𝐴(𝜔) = 𝐴𝑚𝑖𝑛 (𝜔), 𝜃(𝜔) = 𝜃𝑚𝑖𝑛 (𝜔) ∙ 𝜃𝐴𝑃 (𝜔), 𝜏𝑔 (𝜔) = 𝜏𝑔,𝑚𝑖𝑛 (𝜔) + 𝜏𝑔,𝐴𝑃 (𝜔) > 𝜏𝑔,𝑚𝑖𝑛 (𝜔) Unter allen Filtern mit gleichem 𝐴(𝜔) hat Hmin das kleinste 𝜏𝑔 (𝜔) 2 (gleiche Gesamtenergie), aber ∞ |ℎ(𝑛)|2 = ∑ ∞|ℎ ∑ • 𝑛=0𝑚𝑖𝑛 (𝑛)| 𝑛=0 2 𝐿 𝐿 ∑𝑛=0 |ℎ(𝑛)| < ∑ 𝑛=0 |ℎ𝑚𝑖𝑛 (𝑛)|2 (größte partielle Energie um 0 herum) (Jede Spiegelung einer NS an EK verringert part. Energie von h(n)) •

𝐻(𝑧) hat M verschiedene NS ≠ 1, Spiegelung 𝑛𝑖 → M

1

𝑛∗𝑖

verändert 𝐴(𝜔) nicht

-> 2 versch Pol-NS-Diagramme (1x minimalphasig, 1x maximalphasig, 2(M-1) gemischte Phase)

11

DSV Formelsammlung

WS 17/18

30.10.17

5 Korrelationsanalyse 5.1 Lineare Korrelation (Pearson-Korrelation) Schwächen lin. Analyse: • |𝜌𝑥𝑦 | = 1, lediglich bei linearem Zsm.-hang • 𝑦(𝑛) = 𝑎 ∙ 𝑥(𝑛) + 𝑏 Hermetisches Transformieren: 𝑦 𝐻 = (𝑦 𝑇 )∗ = (𝑦 ∗)𝑇

Eigenschaften: • Cauchy-Schwarz-Ungl: |𝑦 𝐻 ∙ 𝑥| ≤ ||𝑥|| ∙ ||𝑦|| Gleichheit ↔ 𝑦 = 𝑎 ∙ 𝑥, 𝑎 > 0 → ↑↑, 𝑎 < 0 → ↑↓,

Korrelation: ∗ 𝑟𝑥𝑦 = 𝛼 ∙ ∑ 𝑁  𝐻 ∙ 𝑥 𝑛=1 𝑥(𝑛) ∙ 𝑦 (𝑛)= 𝑦

Eigenschaften: • Maß für linearen Zsm.-hang zweier Signale • 𝛼 = 1/ 𝛼 = 1/𝑁 • Nachteil: Bei Offset keine maximale Korrelation, nicht normiert (𝑥(𝑛) − 𝑚𝑥 ) ∙ (𝑦(𝑛) − 𝑚𝑦 ) = 𝑦 𝐻 ∙ 𝑥 mit 𝑚𝑥 = 𝑐𝑥𝑦 = 𝛼 ∙ ∑ 𝑁 𝑛=1 Kovarianz:

1

𝑁

∙ ∑𝑁 , 𝑚𝑦 = 𝑛=1 𝑥(𝑛)

Eigenschaften: • Korrelation für lin. Zusammenhang zweier mittelwertfreier Signale • 𝛼 = 1/ 𝛼 = 1/𝑁 • Nachteil: Nicht normiert (𝑥(𝑛) − 𝑚𝑥 )2 = 𝛼 ∙ ||𝑥|| ≥ 0 • Spezialfall Varianz: 𝑐𝑥𝑥 = 𝛼 ∙ ∑ 𝑁 𝑛=1 Korrelationskoeffizient: 𝜌𝑥𝑦 =

𝑐𝑥𝑦

√𝑐𝑥𝑥∙𝑐𝑦𝑦

=

𝑦 󰇍 𝐻 ∙𝑥 ||𝑦󰇍||∙||𝑥||

Eigenschaften: • Normierte Kovarianz zweier Signale • Unabhängig von α und Skalierung • |𝜌𝑥𝑦 | ≤ 1 Gleichheit ↔ 𝑦8𝑛) = 𝑎 ∙ 𝑥(𝑛) + 𝑏

X und y heißen: • Unkorreliert: 𝜌𝑥𝑦 = 0 • Korreliert: 𝜌𝑥𝑦 ≠ 0 • Positiv korreliert: 𝜌𝑥𝑦 > 0 • Negativ korreliert: 𝜌𝑥𝑦 < 0 • Kohärent / max. korreliert: |𝜌𝑥𝑦 | = 1

12

1

𝑁

∙ ∑𝑁 𝑛=1 𝑦(𝑛)

DSV Formelsammlung

WS 17/18

30.10.17

𝑟𝑥𝑦 (𝑘) = 𝛼 ∙ ∑ 𝑛=1 𝑥(𝑛 + 𝑘) ∙ 𝑦 ∗(𝑛)mit 0 ≤ 𝑘 ≤ 𝑀 − 𝑁 -> Längen der Signale verschieden (x:M, y:N, M>N) Kreuzkorrelationsfunktion: 𝑁

Eigenschaften: • Wo findet man y in x? Korrelation zweier Signale zum Zeitversatz k • 𝛼 = 1/ 𝛼 = 1/𝑁 • Enge Verknüpfung zur Faltung (Faltung von x mit matched Filter): ∗ 𝑟𝑥𝑦 (𝑘) = ∑𝑁 𝑛=1 𝑥(𝑛 + 𝑘) ∙ 𝑦 (𝑛)= (𝑥(𝑘) ∗ 𝑦(−𝑘))

(𝑥(𝑛 + 𝑘) − 𝑚𝑥 ) ∙ (𝑦(𝑛) − 𝑚𝑦 ) mit 𝑚𝑥 = 𝑐𝑥𝑦 (𝑘) = 𝛼 ∙ ∑𝑁 𝑛=1 Kreuzkovarianz:

1

𝑁

∑𝑁 𝑛=1 𝑥(𝑛 + 𝑘,)𝑚𝑦 =

Eigenschaften: • Kreuzkorrelation für lin. Zusammenhang zweier mittelwertfreier Signale • 𝛼 = 1/ 𝛼 = 1/𝑁 • Oft Lage des Maximums & nicht Wert entscheidend -> Skalierung egal! • Häufige Vereinfachung, indem mx MW über gesamtes Signal

1

𝑁

∑𝑁 𝑛=1 𝑦(𝑛)

∗ 𝛼(𝑘) ∙ ∑𝑁−𝑘 𝑛=1 𝑥(𝑛 + 𝑘) ∙ 𝑥 (𝑛), 0 ≤ 𝑘 ≤ 𝑁 − 1 𝑟(𝑘) = 𝑟𝑥𝑥 (𝑘) = { 𝑟 ∗(−𝑘), −(𝑁 − 1) ≤ 𝑘 < 0

Autokorrelation:

Eigenschaften: • Selbstähnlichkeit von x(n) (Betrachtung von Teilstücken) • 𝛼 = 1/ 𝛼 = 1/𝑁 / 𝛼 =1/(N-k) [Beste Lösung] • Keine Offset-Bereinigung

Autokovarianzfunktion:

𝑐(𝑘) = 𝑐𝑥𝑥(𝑘) = 𝛼(𝑘) ∙ ∑𝑁−𝑘 𝑛=1 [𝑥(𝑛 + 𝑘) −

1

𝑁−𝑘 1

∑ 𝑁−𝑘 ) [𝑥(𝑛) − 𝑛=1 𝑥(𝑛 + 𝑘 ]

∗ 1 ∑ 𝑁−𝑘 𝑥(𝑛)] 𝑛=1 𝑁−𝑘 𝑥

𝑁 ] [𝑥(𝑛) − ∑ 𝑁 𝑥(𝑛]) , 0 ≤ 𝑘 < 𝑁 𝛼(𝑘) ∑𝑁−𝑘 𝑛=1 [𝑥(𝑛 + 𝑘) − 𝑁 ∑ 𝑛=1 𝑥(𝑛) 𝑁 𝑛=1 𝑐(𝑘) = 𝑐𝑥𝑥(𝑘) = { 𝑐 ∗(−𝑘), −(𝑁 − 1) ≤ 𝑘 < 0 1

Eigenschaften: • Autokorrelation für lin. Zusammenhang zweier mittelwertfreier Signale • 𝛼 = 1/ 𝛼 = 1/𝑁 / 𝛼 =1/(N-k) [Beste Lösung] • Am Rand sehr ungenau, da nur über wenige Werte gemittelt

5.2 Analyse allgemeiner Signale Rangkorrelationsanalyse nach Spearman: Prüfung auf monotone Abhängigkeit (±1 für monotone Funktion) Vorgehen: • Sortieren von x(n), y(n) nach Größe und bestimmen des Rangs der Elemente in dieser Liste • Ersetzen der Funktionswerte mit Rängen • Vergleichen der Ränge der einzelnen Koeffizienten → 𝑟𝑠 =

∑ 𝑖(𝑟𝑔(𝑥𝑖 )𝑟𝑔  𝑦) 𝑥)(𝑟𝑔(𝑦𝑖 )𝑟𝑔

2

2 √(∑𝑖 (𝑟𝑔(𝑥𝑖 )𝑟𝑔 )  ) 𝑥 ) )(∑ 𝑖(𝑟𝑔 (𝑦𝑖 )𝑟𝑔 𝑦

Schätzung des Signalmodells: Beliebige Abhängigkeit zw. x & y -> Master SASP verwenden 13

DSV Formelsammlung

WS 17/18

30.10.17

6 Diskrete (DFT) & Schnelle Fouriertransformation (FFT) Abtastung Frequenzbereich:

−𝑗 𝑋(𝑘) = 𝑋(𝑒 𝑗𝜔𝑘 ) = ∑ ∞ 𝑛=−∞ 𝑥(𝑛)𝑒

=∑

2𝜋 𝑘𝑛 𝑁

−𝑗 𝑁−1 𝑛=0𝑥𝑝 (𝑛)𝑒

2𝜋

𝑁

= 𝑋(𝑘 + 𝑁)

𝑘𝑛

Eigenschaften: • xp: Periodische Fortsetzung von x • Abgetastetes Signal ist Fourierreihe von xp • Nyquist-Bedingung nach Abtasttheorem: 𝑁 ≥ 𝐿ä𝑛𝑔𝑒 𝑥(𝑛) (Andere Werte als im Zeitbereich)

6.1 DFT

−𝑗 𝑘𝑛 X(k) = ∑𝑁−1 𝑛=0 𝑥𝑝 (𝑛)𝑒 𝑁 = ∑ 2𝜋

𝑁−1 𝑘𝑛 𝑛=0𝑥𝑝 (𝑛)𝑊𝑁

, 𝑥(𝑛) =

1

𝑁

𝑗 𝑘𝑛 ∑ 𝑁−1 𝑘=0 𝑋(𝑘 )𝑒 𝑁 = 2𝜋

1

𝑁

𝑥(0) 𝑊0 … 𝑊0 1  … ], 𝑥𝑁𝑥1 = ∙ 𝑊 ∗ 𝑋𝑁𝑥1 = 𝑊𝑁𝑥𝑁 ∙ 𝑥𝑁𝑥1 = [ … … ∙ 𝑋𝑁𝑥1 … ][ 𝑁 𝑁𝑥𝑁 (𝑁−1)2 0 𝑥(𝑁 − 1) 𝑊 … 𝑊

−𝑘𝑛 ∑ 𝑁−1 𝑘=0 X(k)𝑊𝑁

Allgemeines: • Abgetastete Version von 𝑋(𝑒 𝑗𝜔 ) / Fourier-Koeff. von xp(n) • Zero-Padding für N>L (glattere Kurve von X(k) durch feinere Abtastung, aber kein Informationsgewinn) • Darstellung von xp(n): 𝑥𝑝 (𝑛) = 𝑥(𝑛 𝑚𝑜𝑑 𝑁), zirkulare Notation (auf Kreis) •

Eigenschaften von W:

•

1

√𝑁

[(

𝑊)

−1

=(

1

√𝑁

1

√𝑁 𝐻

𝑊 ist unitär (orthonormale Spalten/Zeilen), einfache Invertierung

𝑊) ], 𝑊 𝑇 = 𝑊

Aufwand: N2 kmplx. Multiplikationen, N(N-1) kmplx. Additionen

Eigenschaften:

Zu Beachten: • xp(n) unendlicht lang • 𝑥(𝑛) ≠ 𝑥𝑝 (𝑛), für 𝑁 ≥ 𝐿: 𝑥(𝑛) = 𝑥𝑝 (𝑛) (0 ≤ 𝑛 < 𝑁) • Zirkulare Eig. ungleich linearen

14

• 𝑋(𝑁 − 𝑘) = 𝑋 ∗(𝑘) • 𝑥(𝑛) ∈ ℝ → 𝑥(𝑛) = 𝑥𝑅𝑒 (𝑛) + 𝑥𝐼𝑚 (𝑛) 𝑋(𝑘) = 𝑋𝑅𝑒 (𝑘) + 𝑗𝑋𝐼𝑚 (𝑘)

DSV Formelsammlung

WS 17/18

Lineare & zirkulare Faltung: • • • •

30.10.17

𝐹𝑇

𝑗𝜔 𝑗𝜔 Lineare Faltung: (𝑥1 ∗ 𝑥2 )(𝑛) = ∑∞ 𝑚=−∞ 𝑥1 (𝑚) ∙ 𝑥2 (𝑛 − 𝑚) → 𝑋1 (𝑒 ) ∙ 𝑋2 (𝑒 ), Länge: N1+N2-1 𝐷𝐹𝑇

Zirkulare Faltung: : (𝑥1 ⊛ 𝑥2 )(𝑛) = ∑𝑁−1 𝑚=0 𝑥1𝑝 (𝑚) ∙ 𝑥2𝑝 (𝑛 − 𝑚 ) → 𝑋1 (𝑘) ∙ 𝑋2 (𝑘), Länge: N=max(N1,N2), periodisch mit N Zirkulare Faltung aus lin. Faltung: Werte von (𝑥1 ∗ 𝑥2 )(𝑛) für (n mod N) aufaddieren Gleicheit für: 𝑁 ≥ 𝑁1 + 𝑁2 − 1

6.2 FFT

Allgemeines: • Familie schneller Algorithmen zur Berechnung der DFT durch Ausnutzung von Symetrien • •

Aufwand: 2 log 2 𝑁 kmplx. Multiplikationen, 𝑁 log 2 𝑁 kmplx. Additionen (Um Faktor 100 𝑁

geringer) Falls Längen nicht gewünschtem N entsprechen -> Zero-Padding

•

Verwendete Eigenschaften von 𝑊𝑁𝑘 : Periodizität (𝑊𝑁𝑘 = 𝑊𝑁𝑘+𝑁 ), Symmetrie (𝑊 𝑁

•

Vermeidung redundanter Operationen durch Zerlegung in kleinere DFTs

Zerlegung (𝑊𝑁2𝑘 = 𝑊𝑁𝑘 ) 2

𝑁

𝑘+ 2

= −𝑊𝑁𝑘 ),

Formen: • Mixed-radix (𝑁 = 𝑟1 ⋅ … ⋅ 𝑟𝑁 ) • Radix-r (𝑁 = 𝑟𝑑 ) [einfacher] • Radix-2 (𝑁 = 2𝑑 ) [am Einfachsten] • Radix-3 (𝑁 = 3𝑑 ) [in Spezialanwendungen]

15

DSV Formelsammlung Radix-2-FFT: Zeitzerlegung:

• • • • •

∑

WS 17/18

𝑁/2−1 𝑛=0

𝑥(2𝑛) ⋅ 𝑊𝑁2

𝑊𝑁𝑘 ∑

𝑋(𝑘) = { ∑𝑁/2−1 𝑥(2𝑛) ⋅ 𝑊𝑁𝑘𝑛− 𝑊𝑁𝑘 ∑ 𝑛=0 2

𝑁/2−1 𝑛=0 𝑥(2𝑛 𝑁 −1 2

𝑥(2𝑛 𝑛=0

+ 1) ⋅ 𝑊𝑁

+ 1) ⋅ 𝑊𝑁

𝑘𝑛, 0

2

,

𝑘𝑛 𝑁

2

2

≤𝑛<

𝑁

2

≤𝑛 Umkehr der Signalflussrichtung: Radix-2-FFT mit Frequenzzerlegung

2

𝐷𝐹𝑇𝑁(𝑥(𝑛) − 𝑥 (𝑛 + )), 𝑘 𝑢𝑛𝑔𝑒𝑟𝑎𝑑𝑒 2 2

𝑁

DSV Formelsammlung Radix-3-FFT: Zeitzerlegung: • N=3d •

WS 17/18

𝑋(𝑘) = ∑2𝑏=0 𝑥(𝑛) ∙ 𝑒 𝑗 3 𝑘𝑛= ∑ 2𝜋

2 𝑏=0𝑥(𝑛) ∙

30.10.17

𝑊3 𝑘𝑛

Radix-r-FFT: Zeitzerlegung: • N=rd • Zerlegung in r Teilfolgen (x(0), x(r), …, x(N-r)) und dann DFTN/R Zusammenfassung: • D=logr(N) • N/r Radix-r-Butterflies pro Stufe • Wichtig für 𝑊4 𝑘 = ±1, ±𝑗

FFT von rellen Signalen: • FFT immer für 𝑥 ∈ ℂ ausgelegt •

•

2 reelle Signale: 𝑥(𝑛) = 𝑥1 (𝑛) + 𝑗𝑥2 (𝑛), 𝑋1 (𝑘) = 2 [𝑋(𝑘) + 𝑋(𝑘)∗], 1

𝑋2 (𝑘) = [𝑋(𝑘) − 𝑋(𝑘)∗] 2 1

1 reelles Signal: Zeitzerlegung in 2 Signale (x1(n)=y(2n), x2(n)=y(2n+1)) 𝑌(𝑘) = 𝑋1 (𝑘) + 𝑊2𝑁 𝑋2 (𝑘), 𝑌(𝑘 + 𝑁) = 𝑋1 (𝑘) − 𝑊2𝑁 𝑋2 (𝑘)

6.3 Schnelle Faltung • • • •

Geschwindigkeitsvorteil von FFT gegenüber DFT Multiplikation H(k)X(k) schneller als Faltung (ℎ ∗ 𝑥)(𝑛) Für x(n) & h(n) mit Länge N -> y(n) mit Länge 2N-1 => FFT-Länge≥ 2𝑁 − 1 Verwendung für Filterung eines langen Signals (1. Batch-Filterung des gesamten Signals, 2. Blockfilterung)

Blockfaltung: • Teilung von x(n) in n Blöcke (nicht überlappend) der Länge B • Schnelle Faltung aller Blöcke mit h(n) • Addition der Ergebnisse nach Overlap-Add/Overlap-Save •

Anzahl an Radix-2-FFT-Butterflys: 𝑅 =

𝐾𝑁∙𝑙𝑜𝑔2 𝑁 𝑁𝑔𝑒𝑠

(K: Anzahl der

Blöcke, N:FFT-Länge, Nges: Anzahl aller Abtastwerte Originalsignal) -> Ansonsten M Rechenoperationen (M: Ordnung/Anzahl Abtastwerte h(n))

Overlap-Add: • FFT-Länge: 𝑁 ≥ (𝑀 + 1) + 𝐵 − 1 = 𝑀 + 𝐵 • Vorgehen: Zerlegung von x(n) in m Blöcke der Länge B, Zero-Padding von h(n) und Blöcken von x(n), FFTN aller Blöcke und von h(n), Multiplikation: Yi(k)=Xi(k)H(k), IFFTN von Yi(k), Addition: 𝑦(𝑘) = ∑ 𝑚 𝑖=1 𝑦𝑖 (𝑛 + (𝑖 − 1)𝐵) • Keine...