Re: DFT und DCT

Andreas Weishaupt wrote:
Hallo!

Wie die DFT und die DCT berechnet werden, ist mir eigentlich seit
einiger Zeit klar. Leider habe ich die Bedeutung einiger grundlegenden
Konzepte vergessen:
- DFT: Weshalb wird eigentlich eine komplexe Basis verwendet (an Stelle
von Kosinus), um ein Signal aus Zeit-/Raumbereich in den Frequenzbereich
zu transformieren und worin liegt der Vorteil/Nutzen?
Weshalb entstehen bei der Transformation "negative" Frequenzen und wozu
dienen diese?
- DCT: Wo liegt der Unterschied (bezüglich dem Resultat) zur DFT wenn
ich eine Frequenztransformation durchführen will?

Der Unterschied liegt in den Randbedingungen. Mit der DFT erhält man
für einen gegebenen Vektor eine periodische Darstellung, wärend man
mit der DCT eine gerade periodische (und natürlich mit der DST eine
ungerade periodische) Darstellung erhält. Es gibt verschiedene
Varianten, wie man die gerade periodische Randbedingung erzwingen
kann, und jede Variante resultiert in einer anderen DCT (Typ I-IV).
Wikipedia verrät die Details.

Für eine periodische Darstellung (ohne Symmetrien) reichen im
allgemeinen Cos-Komponenten nicht aus, sondern man braucht auch noch
die Sin-Komponenten. Ob man die Komponenten einzeln und reell oder
gemeinsam und dafür komplex nimmt ist lediglich eine Frage der
Notation.

Die negativen Frequenzen hat man bei allen periodischen
Transformationen. Für reelle Vektoren sind die negativen Frequenzen
jedoch (wie bereits von Christopher erwähnt) redundant (die Dimension
der Vektorräume bleibt gleich) und werden daher meist nicht
dargestellt / übertragen / gespeichert / etc.

Wie entscheidet man, welche Transformation man braucht? Ein paar
Beispiele:
Für Spektralanalyse und wird meistens (immer?) die DFT gewählt
(Periodogramm und verwandte wie Welch-Schätzer). Für schnelle Faltung
(Filterung im Frequenzbereich) wird ebenfalls die DFT benutzt und mit
der FFT berechnet. Für Transform Coding (Reduktion von 1-D und 2-D
Daten) hat die DCT jedoch Vorteile (wegen den geraden periodischen
Randbedingung fallen die Spektralkoeffizienten schneller ab) und wird
daher gegenüber der DFT bevorzugt. Für den Entwurf linear-phasiger FIR
Filter (via Windowing) werden DCT (Typ 1+2) und DST (Typ 3+4)
gebraucht, obwohl man auch die DFT benutzen und die entsprechenden
Randbedingungen durch Konstruktion der notwendingen Symmetrien (in
Zeit- oder Frequenzbereich) von Hand generieren kann (das gilt
natürlich für alle Anwendungen).

Den Trick mit der Konstruktion der Symmetrien "von Hand" kann man auch
benutzen, um die DCT/DST schnell via FFT zu berechnen. Wegen den
zusätzlichen Symmetrien gäbe es aber eigentlich noch ein paar
Rechenoperationen zu sparen, jedoch nicht viel, wenn man dem Eintrag
in Wikipedia glauben will (geschrieben von Stephen G Johnson, Autor
von der beinahe schon legendären Software FFTW). Hat man eine
effiziente DCT und DST (sagen wir eine FCT und eine FST), kann man
umgekehrt daraus wieder eine FFT basteln. Du siehst, alles dreht sich
im Kreise, falls mir ein kleine Wortspiel erlaubt sei :-).

Gruss,
Andor
.

Relevant Pages

  • Re: dft : property of symmetry for real & even seq
    ... you should use a discrete cosine transform (DCT). ... is why people normally have a complex-output DFT (even if they have ... positive frequencies (as I understand it when the time domain samples ... The relationship between the real DFT polar form and the complex DFT ...
    (comp.dsp)
  • Re: FFT and DFT in matlab
    ... AnFFTis an algorithm for computing the DFT (the name of the abstract ... mathematical transformation, not a specific method to compute this ... the best rectangular approximation to the integral ...
    (comp.soft-sys.matlab)
  • Re: Query DCT and DFT
    ... So to compute the fourier series, ... For DFT, ... For DCT, the sequence is mirrored and then ... applications) or of type-I corresponds to even boundary conditions at ...
    (sci.image.processing)
  • Re: DCT by convolution and convolution theorem ?
    ... > Cpu-eme coefficient of a n point DCT on the signal S with pixel ... > to write Cp as a convolution product: ... > equation a DFT of G and obtain a relation as describe in lots of book by ...
    (sci.image.processing)
  • Re: Computing DFT of a signal from its DCT coefficients?
    ... signal x, but what we really want is the N-point DFT of x, Xdft. ... between DFT and DCT. ... The DCT boundary condition is that the derivative is zero at the ends, the DST has the function going to zero at the ends, where the DFT is a compromise between the two, with periodic boundary conditions. ...
    (comp.dsp)
Loading