Multimediale Signalverarbeitung
Frequenztransformationen

• Zeitdiskete Frequenztransformationen stellen ein zeitveränderliches Signal $\mathrm{f}[n]$ mit $n \in \mathbb{Z}$ als eine Überlagerung von Basisfunktionen $\mathrm{b}_u[n]$ dar, die eine Lokalität im Frequenzbereich haben
  $\mathrm{f}[n] = \sum\limits_u \mathrm{F}[u] \, \mathrm{b}_u[n]$
• Die Koeffizienten $\mathrm{F}[u]$ der Basisfunktionen sind somit eine Repräsentation der zeitveränderliches Signal $\mathrm{f}[n]$ im Frequenzraum (d.h. im Raum der durch die Basisfunktionen aufgespannt wird).
• Durch die Abbildung $\mathrm{f}[n] \mapsto \mathrm{F}[u]$ findet eine Transformation vom Zeitbereich in den Frequenzbereich statt
• Die inverse Abbildung $\mathrm{F}[u] \mapsto \mathrm{f}[n]$ vom Frequenzbereich in den Zeitbereich wird häufig auch als "Rücktransformation" bezeichnet

• Beispiele für diskete Frequenztransformationen sind
  • Diskrete Fourier-Transformation (DFT)
  • Diskrete Kosinus-Transformation (DCT)
  • Diskrete Wavelet-Transformation (DWT)

• Die diskrete Fourier-Transformation (DFT) für ein komplexes periodisches
  Signal $\mathrm{f}[n]$ der Periodenlänge $N$ berechnet sich durch:
  $\mathrm{F}[u] = \sum\limits_{n=0}^{N-1} \mathrm{f}[n] \, e^{-2 \pi i \frac{n\, u}{N} } \quad \quad \forall \, \, u \in [0;N-1]$
• Die inverse diskrete Fourier-Transformation (IDFT) ist definiert als
  $\mathrm{f}[n] = \frac{1}{N} \sum\limits_{u=0}^{N-1} \mathrm{F}[u] \, e^{2 \pi i \, \frac{n\, u}{N} } \quad \quad \forall \, \, n \in [0;N-1]$
• Damit lauten die bei der inversen Fourier-Transformation verwendeten Basisfunktionen:
  $\begin{array}{ll} \mathrm{b}_u[n] &= \frac{1}{N} e^{2 \pi i \frac{n\, u}{N} } \\ &= \frac{1}{N} \cos\left(2 \pi \frac{n\, u}{N} \right) + i\, \frac{1}{N} \sin\left(2 \pi \frac{n\, u}{N} \right) \end{array} $
  d.h. die Basisfunktionen sind komplexe Funktionen mit der
  imaginären Einheit $i = \sqrt{-1}$

• Insgesamt gibt es $N$ verschiedene Basisfunktionen:
  $\mathrm{b}_u[n] = \frac{1}{N} \cos\left(2 \pi \frac{n\, u}{N} \right) + i\, \frac{1}{N} \sin\left(2 \pi \frac{n\, u}{N} \right)$
  • Bei $\mathrm{b}_0[n]$ ist Real- und Imaginärteil konstant
  • Bei $\mathrm{b}_1[n]$ entspricht die Wellenlänge der Kosinus- und Sinusschwingung der Periodenlänge des Einganssignals
  • Für steigende $u$ wird die Wellenlänge jeweils immer halbiert (bzw. die Frequenz verdoppelt)

• Darstellung der Basisfunktionen
  $\mathrm{b}_u[n] = \frac{1}{N} \cos\left(2 \pi \frac{n\, u}{N} \right) + i\, \frac{1}{N} \sin\left(2 \pi \frac{n\, u}{N} \right)$
  für $N=32$:

Realteil

Imaginärteil

$b_0$

$b_1$

$b_2$

$b_3$

$n$

• Darstellung der Basisfunktionen
  $\mathrm{b}_u[n] = \frac{1}{N} \cos\left(2 \pi \frac{n\, u}{N} \right) + i\, \frac{1}{N} \sin\left(2 \pi \frac{n\, u}{N} \right)$
  für $N=32$:

Realteil

Imaginärteil

$b_1$

$b_{16}$

$b_{30}$

$b_{31}$

$n$

• Beobachtungen:
  • Obwohl bei jeder Erhöhung von $u$ die Frequenz eigentlich verdoppelt wird, steigt die beobachtete Frequenz der Schwingung für $u > N/2$ wegen der zeitdiskreten Abtastung nicht weiter
  • Stattdessen sinkt die beobachtete Frequenz. Es gilt:
    $\operatorname{Re}(\mathrm{b}_u[n]) = \operatorname{Re}(\mathrm{b}_{N-u}[n])$ und $\operatorname{Im}(\mathrm{b}_u[n]) = -\operatorname{Im}(\mathrm{b}_{N-u}[n])$
  • Die Basisfunktion mit der höchsten Frequenz ist demnach $\mathrm{b}_{N/2}$
  • Alle Basisfunktionen für $N = 16$:
    

• Da das Eingangssignal und alle Basisfunktionen periodisch in $N$ sind, ist auch $\mathrm{F}[u]$ periodisch in $N$
• Es gilt insbesondere:
  $\mathrm{F}[N-u] = \mathrm{F}[-u] $
• Durch diesen mathematische Betrachtung sind nun negative Frequenzen möglich
• Negative Frequenzen gibt es physikalisch eigentlich nicht. Bei der DFT ist es lediglich eine mathematische Beschreibung für die umgekehrte Rotationsrichtung in der komplexen Ebene
• Wenn wir gedanklich Frequenzen größer als $u > N/2$ als negative Frequenzen interpretieren, dann hat dies den Vorteil, dass es der Vorstellung entspricht, dass die Basisfunktion $\mathrm{b}_{N/2}$ die höchste Frequenz hat
  

• Neben der Verwendung von negativen Frequenzen ist es ebenfalls gebräuchlich Real- und Imaginärteil von $\mathrm{F}[u]$ in Betrag und Phase darzustellen
• Der Betrag berechnet sich zu:
  $\mathrm{b}[u] = \sqrt{\operatorname{Re}(\mathrm{F}[u])^2 + \operatorname{Im}(\mathrm{F}[u])^2}$
• Die Formel für die Phase lautet:
  $\mathrm{\phi}[u] = \operatorname{atan2}(\operatorname{Im}(\mathrm{F}[u]),\operatorname{Re}(\mathrm{F}[u]))$

$\operatorname{Im}(\mathrm{F}[u])$

$\operatorname{Re}(\mathrm{F}[u])$

$\phi$

$sin(\phi)$

$cos(\phi)$

$\begin{array}{ll} \mathrm{F}[u] &= \sum\limits_{u=0}^{N-1} \mathrm{f}[n] \, e^{-2 \pi i \frac{n\, u}{N} } \\ &= \sum\limits_{u=0}^{N-1} \mathrm{f}[n]\left( \cos\left(- 2 \pi \frac{n\, u}{N} \right) + i\, \sin\left(- 2 \pi \frac{n\, u}{N} \right) \right)\\ &= \sum\limits_{u=0}^{N-1} \mathrm{f}[n]\left( \cos\left(2 \pi \frac{n\, u}{N} \right) - i\, \sin\left(2 \pi \frac{n\, u}{N} \right) \right)\\ &= \sum\limits_{u=0}^{N-1} \left(\operatorname{Re}(\mathrm{f}[n]) + i\, \operatorname{Im}(\mathrm{f}[n])\right) \left( \cos\left(2 \pi \frac{n\, u}{N} \right) - i\, \sin\left(2 \pi \frac{n\, u}{N} \right) \right) \\ \operatorname{Re}(\mathrm{F}[u]) &= \sum\limits_{u=0}^{N-1} \operatorname{Re}(\mathrm{f}[n]) \cos\left(2 \pi \frac{n\, u}{N} \right) + \operatorname{Im}(\mathrm{f}[n]) \sin\left(2 \pi \frac{n\, u}{N} \right) \\ \operatorname{Im}(\mathrm{F}[u]) &= \sum\limits_{u=0}^{N-1} \operatorname{Im}(\mathrm{f}[n]) \cos\left(2 \pi \frac{n\, u}{N} \right) - \operatorname{Re}(\mathrm{f}[n]) \sin\left(2 \pi \frac{n\, u}{N} \right) \\ \end{array} $

$\begin{array}{ll} \mathrm{f}[n] &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \mathrm{F}[u] \, e^{2 \pi i \frac{n\, u}{N} } \\ &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \mathrm{F}[u]\left( \cos\left(2 \pi \frac{n\, u}{N} \right) + i\, \sin\left(2 \pi \frac{n\, u}{N} \right) \right)\\ &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \left(\operatorname{Re}(\mathrm{F}[u]) + i\, \operatorname{Im}(\mathrm{F}[u])\right) \left( \cos\left(2 \pi \frac{n\, u}{N} \right) + i\, \sin\left(2 \pi \frac{n\, u}{N} \right) \right) \\ \operatorname{Re}(\mathrm{f}[n]) &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \operatorname{Re}(\mathrm{F}[u]) \cos\left(2 \pi \frac{n\, u}{N} \right) - \operatorname{Im}(\mathrm{F}[u]) \sin\left(2 \pi \frac{n\, u}{N} \right) \\ \operatorname{Im}(\mathrm{f}[n]) &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \operatorname{Im}(\mathrm{F}[u]) \cos\left(2 \pi \frac{n\, u}{N} \right) + \operatorname{Re}(\mathrm{F}[u]) \sin\left(2 \pi \frac{n\, u}{N} \right) \\ \end{array} $

• Beim Realteil von $\mathrm{f}[n]$ werden die Cosinus-Anteile durch die Koeffizienten im Realteil von $\mathrm{F}[u]$ repräsentiert und die Sinus-Anteile durch die Koeffizienten im Imaginärteil
• Beim Imaginärteil von $\mathrm{f}[n]$ ist dies genau umgekehrt

• Für eines reales periodischen Signals $\mathrm{f}[n]$ kann die Berechnung des Real- und Imaginärteils von $\mathrm{F}[u]$ komplett unabhängig von einander durchgeführt werden:
  $\operatorname{Re}(\mathrm{F}[u]) = \sum\limits_{n=0}^{N-1} \mathrm{f}[n] \, \cos(2 \pi \frac{n\, u}{N}) \quad$ und $\quad \operatorname{Im}(\mathrm{F}[u]) = -\sum\limits_{n=0}^{N-1} \mathrm{f}[n] \, \sin(2 \pi \frac{n\, u}{N})$
• Durch die Symmetrie der Basisfunktionen folgt:
  $\operatorname{Re}(\mathrm{F}[u]) = \operatorname{Re}(\mathrm{F}[N-u])\quad$ und $\quad\operatorname{Im}(\mathrm{F}[u]) = -\operatorname{Im}(\mathrm{F}[N-u])$
• D.h. für ein reales Signals $\mathrm{f}[n]$ müssen nur die Koeffizienten $\mathrm{F}[u]$ für $0 \le u \le N/2$ berechnet und gespeichtert werden
• In diesem Fall ist die Rücktransformation gegeben durch:
  $\mathrm{f}[n] = \frac{1}{N} \sum\limits_{u=0}^{N/2} \mathrm{w}[u] \left(\operatorname{Re}(\mathrm{F}[u]) \cos\left(2 \pi \frac{n\, u}{N} \right) - \operatorname{Im}(\mathrm{F}[u]) \sin\left(2 \pi \frac{n\, u}{N} \right) \right)$
  wobei alle Summanden außer für $u=0$ und $u=N/2$ doppelt gewichtet werden:
  $\mathrm{w}[u] = \begin{cases} 1 & \,\,:\,\, u = 0 \lor u=N/2\\ 2 & \,\,:\,\, u \ne 0 \land u \ne N/2 \end{cases}$

• Linearität:
  $a_1 \mathrm{f}_1[n] + a_2 \, \mathrm{f}_2[n] \quad \stackrel{\operatorname{dft}}{\longrightarrow} \quad a_1 \mathrm{F}_1[u] + a_2 \, \mathrm{F}_2[u]$
• Mittelwert:
  $ \frac{1}{N} \sum\limits_{n=0}^{N-1} \mathrm{f}[n] = \frac{1}{N} F(0)$
• Reziprozität von Zeitbereich und Frequenzbereich:
  $\begin{array}{ll} f[n] \quad &\stackrel{\operatorname{dft}}{\longrightarrow}& \quad F[u]\\ F[n] \quad &\stackrel{\operatorname{dft}}{\longrightarrow}& \quad N \, f[u] \end{array}$

• Verschiebung im Zeitbereich:
  $f[n-n_0] \quad \stackrel{\operatorname{dft}}{\longrightarrow} \quad \mathrm{F}[u] \, e^{-2 \pi i \frac{n_0 u}{N} }$
• Verschiebung im Frequenzbereich:
  $\mathrm{f}[n]\, e^{2 \pi i \frac{n u_0}{N} } \quad \stackrel{\operatorname{dft}}{\longrightarrow} \quad F(u-u_0)$
• Faltung im Zeitbereich entspricht der Multiplikation im Frequenzbereich:
  $f_1[n] \ast f_2[n] \quad \stackrel{\operatorname{dft}}{\longrightarrow} \quad F_1[u] \, F_2[u]$
• Faltung im Frequenzbereich entspricht der Multiplikation im Zeitbereich:
  $f_1[n] \, f_2[n] \quad \stackrel{\operatorname{dft}}{\longrightarrow} \quad \frac{1}{N} F_1[u] \ast F_2[u]$

• Für eine beliebiges reales Signal $\mathrm{f}[n]$ ist der Realteil der DFT symmetrisch und der Imaginärteil anti-symmetrisch:
  $\operatorname{Re}(\mathrm{F}[u]) = \operatorname{Re}(\mathrm{F}[N-u])$ und $\operatorname{Im}(\mathrm{F}[u]) = -\operatorname{Im}(\mathrm{F}[N-u])$
• Ist ein reales Signal $\mathrm{f}[n]$ symmetrisch, d.h.
  $\mathrm{f}[n] = f[N-n]$ bzw. $\mathrm{f}[n] = f[-n]$
  dann ist $\operatorname{Im}(\mathrm{F}[u]) = 0$
• Ist ein reales Signal $\mathrm{f}[n]$ anti-symmetrisch, d.h.
  $\mathrm{f}[n] = -f[N-n]$ bzw. $\mathrm{f}[n] = -f[-n]$
  dann ist $\operatorname{Re}(\mathrm{F}[u]) = 0$

$\mathrm{f}[n] = \cos\left(2 \pi \frac{n\, u_0}{N} \right), \quad n \in [0; N-1]$

$\mathrm{F}[u] =\,\frac{N}{2} \delta(u-u_0) + \frac{N}{2} \delta(u-(N-u_0)), \quad u \in [0; N-1]$

Rechnerische Überprüfung:
$\begin{array}{ll} \operatorname{Re}(\mathrm{f}[n]) &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \operatorname{Re}(\mathrm{F}[u]) \cos\left(2 \pi \frac{n\, u}{N} \right) - \operatorname{Im}(\mathrm{F}[u]) \sin\left(2 \pi \frac{n\, u}{N} \right) \\ &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \frac{N}{2} \delta(u-u_0) + \frac{N}{2} \delta(u-(N-u_0)) \cos\left(2 \pi \frac{n\, u}{N} \right) \\ &= \frac{1}{2} \cos\left(2 \pi \frac{n\, u_0}{N} \right) + \frac{1}{2} \cos\left(2 \pi \frac{n\, (N-u_0)}{N} \right) = \cos\left(2 \pi \frac{n\, u_0}{N}\right)\\ \operatorname{Im}(\mathrm{f}[n]) &= \frac{1}{N} \sum\limits_{u=0}^{N-1} \operatorname{Im}(\mathrm{F}[u]) \cos\left(2 \pi \frac{n\, u}{N} \right) + \operatorname{Re}(\mathrm{F}[u]) \sin\left(2 \pi \frac{n\, u}{N} \right) \\ &= \frac{1}{2} \sin\left(2 \pi \frac{n\, u_0}{N} \right) + \frac{1}{2} \sin\left(2 \pi \frac{n\, (N-u_0)}{N} \right) = 0\\ \end{array} $

$\mathrm{f}[n] = \cos\left(2 \pi \frac{n\, u_0}{N} \right), \quad n \in [0; N-1]$

$\mathrm{F}[u] =\,\frac{N}{2} \delta(u-u_0) + \frac{N}{2} \delta(u-(N-u_0)), \quad u \in [0; N-1]$

Zeichnerische Darstellung für $N =16$ und $u_0 = 3$:

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{F}[u])$

$\operatorname{Im}(\mathrm{F}[u])$

$\mathrm{f}[n] = \sin\left(2 \pi \frac{n\, u_0}{N} \right), \quad n \in [0; N-1]$

$\mathrm{F}[u] =\,i \, \frac{N}{2} \left( -\delta(u-u_0) + \delta(u-(N-u_0))\right), \quad u \in [0; N-1]$

Zeichnerische Darstellung für $N =16$ und $u_0 = 3$:

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{F}[u])$

$\operatorname{Im}(\mathrm{F}[u])$

$\mathrm{f}[n] = \cos\left(2 \pi \frac{n\, u_1}{N} \right) + \sin\left(2 \pi \frac{n\, u_2}{N} \right), \quad n \in [0; N-1]$

$\mathrm{F}[u] = {\small \frac{N}{2} \delta(u-u_1) + \frac{N}{2} \delta(u-(N-u_1)) - \frac{iN}{2} \, \delta(u-u_2) + \frac{iN}{2} \delta(u-(N-u_2))}$

Zeichnerische Darstellung für $N =16$, $u_1 = 1$ und $u_2 = 3$:

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{F}[u])$

$\operatorname{Im}(\mathrm{F}[u])$

$\mathrm{f}[n] = \cos\left(2 \pi \frac{n\, u_0}{N} \right) + i\,\sin\left(2 \pi \frac{n\, u_0}{N} \right), \quad n \in [0; N-1]$

$\mathrm{F}[u] =\, N \, \delta(u-u_0)$

Zeichnerische Darstellung für $N =16$ und $u_0 = 4$:

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{f}[n])$

$\operatorname{Im}(\mathrm{f}[n])$

$\operatorname{Re}(\mathrm{F}[u])$

$\operatorname{Im}(\mathrm{F}[u])$

• Einheitsimpuls
  $\mathrm{f}[n] = \delta[n] \quad n \in [0; N-1]$
  $\mathrm{F}[u] = 1, \quad u \in [0; N-1]$
• Konstante Funktion
  $\mathrm{f}[n] = A, \quad n \in [0; N-1]$
  $\mathrm{F}[u] = N \, A\,\delta[n], \quad u \in [0; N-1]$
• Gauss Funktion
  $\mathrm{f}[n] = \frac{1}{\sigma \sqrt{2\pi}} \exp\left(\frac{n^2}{2 \, \sigma^2}\right) \quad n \in [0; N-1]$
  $\mathrm{F}[u] = \exp\Big(\frac{u^2}{2 \, (1 / \sigma)^2}\Big) \quad u \in [0; N-1]$

• $K$ Einheitsimpulse im Abstand $P$ (d.h. Signallänge ist $N=K\,P$ ) :
  $\mathrm{f}[n] = \sum\limits_{k=0}^{K-1} \delta[n - k\,P]$
  ergibt eine DFT bestehend aus $P$ Einheitsimpulsen im Abstand $K$
  $\mathrm{F}[u] = K\,\sum\limits_{p=0}^{P-1} \delta[u - p\,K]$
• Beispiel: $K=8$ und $P=4$

$\mathrm{f}[n]$

$\mathrm{F}[u]$

• Ein zeitdiskreter Rechteckpuls mit der Pulsweite $P$:
  $\mathrm{f}[n] = \begin{cases} 1 & \,\,:\,\, |f| < P/2 \\ 0.5 & \,\,:\,\, |f| = P/2 \\ 0 & \,\,:\,\, |f| > P/2 \\ \end{cases}$
• Die Abbildung zeigt einen Rechteckpuls mit Pulsweite $P=17$ und Länge $N=64$

$\mathrm{f}[n]$

$n$

• Um die DFT anzuwenden, muss $n$ im Bereich $[0; N-1]$ liegen
• Daher zunächst Verschiebung des negativen Anteils nach rechts um $N = 64$
• Dies ist erlaubt, da das Eingangssignal der DFT in $N$ periodisch sein muss

$\mathrm{f}[n]$

$n$

• Die DFT des Rechteckpuls lautet
  $\operatorname{Re}(\mathrm{F}[u]) = \frac{\sin(\pi u P / N)}{\pi u / N}$
• d.h. sie hat den generellen Verlauf einer Sinc-Funktion
  $\operatorname{sinc}(x) = \frac{\sin(\pi x)}{\pi x}$

$\operatorname{Re}(\mathrm{F}[u])$

$u$

• Die diskrete Kosinus-Transformation (DCT) für ein reales Signal $\mathrm{f}[n]$ der Länge $N$ berechnet sich durch:
  $\mathrm{F}[u] = \sum\limits_{n=0}^{N-1} \mathrm{w}[u]\, \mathrm{f}[n] \, \cos(\frac{\pi}{N} \, (n + 0.5) \, u ) \quad \quad \forall \, \, u \in [0;N-1]$
  mit
  $\mathrm{w}[u] = \begin{cases} 1.0 / \sqrt{N} & \,\,:\,\, u = 0 \\ \sqrt{2/N} & \,\,:\,\, u \ne 0 \end{cases}$
• Die korrespondierende inverse diskrete Kosinus-Transformation (IDCT) lautet
  $\mathrm{f}[n] = \sum\limits_{u=0}^{N-1} \mathrm{w}[u]\, \mathrm{F}[u] \, \cos(\frac{\pi}{N} \, (u + 0.5) \, n ) \quad \quad \forall \, \, n \in [0;N-1]$

• Statt einer Kombination aus Sinus- und Kosinusfunktionen, wie bei der DFT, verwenden die Basisfunktionen der DCT ausschließlich den Kosinus
  $\mathrm{b}_u[n] = \cos(\frac{\pi}{N} \, (n + 0.5) \, u )$
• Dabei handelt es sich um Kosinusfunktionen, die um einen halben Abtastwert nach links verschoben sind
• Anderes als bei der DFT, bei der die Funktion bei der Rekonstruktion periodisch vorgesetzt werden, wird bei der DCT die Funktion symmetrisch vorgesetzt

DFT

DCT

$\mathrm{f}[n]$

$N$

$N$

• Damit gibt es weniger Unstetigkeiten an den Rändern, so dass bei der DCT das Originalsignal oftmals mit weniger Koeffizienten rekonstruiert werden kann als bei der DFT
• Daher wird die DCT häufig bei bei Kompressionsverfahren eingesetzt, wie z.B. JPEG oder MP3 (siehe spätere Kapitel)

• Beispiel: Rekonstruktion eines Signals $N=128$ mit nur $32$ DFT bzw. DCT Koeffizienten

DFT Rekonstruktion

DCT Rekonstruktion

Original