Modifizierte diskrete Kosinustransformation

Die modifizierte diskrete Kosinustransformation (englisch {{Modul:Vorlage:lang}} Modul:Multilingual:153: attempt to index field 'data' (a nil value), kurz: MDCT) ist eine reellwertige, diskrete, lineare, orthogonale Transformation, die zu der Gruppe der diskreten Fouriertransformationen (DFT) zählt und eine Modifikation der namensgebenden diskreten Kosinustransformation (DCT) ist.

Die MDCT wurde in den Jahren 1986, 1987 von John P. Princen, A. W. Johnson und Alan B. Bradley entwickelt.<ref>John P. Princen, Alan B. Bradley: Analysis/Synthesis filter bank design based on time domain aliasing cancellation. In: IEEE Transactions on Acoustics, Speech and Signal Processing. Band 34, Nr. 5, Oktober 1986, S. 1153–1161, doi:10.1109/TASSP.1986.1164954. </ref><ref>J. Princen, A. Johnson, A. Bradley: Subband/Transform coding using filter bank designs based on time domain aliasing cancellation. In: Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP ’87. Band 12, 1987, S. 2161–2164, doi:10.1109/ICASSP.1987.1169405 (Erstmalige Erwähnung des Begriffes MDCT). </ref>

Daneben existiert die ähnlich aufgebaute modifizierte diskrete Sinustransformation (MDST), die auf der diskreten Sinustransformation basiert, die aber im Bereich der digitalen Signalverarbeitung keine wesentliche Bedeutung hat.

Motivation

Die MDCT basiert auf dem Typ IV der diskreten Kosinustransformation, auch als DCT-IV bezeichnet, und verwendet am Anfang der zu transformierenden Eingangssignalfolge, beispielsweise ist dies eine endliche Anzahl von Abtastwerten eines Audiosignals, eine gerade Fortsetzung und am Ende der Signalfolge eine ungerade Fortsetzung. Das Eingangssignal wird in aufeinander folgende Blöcke unterteilt, wobei jeder Block getrennt der Transformation unterworfen wird. Bei der MDCT werden die Signalfolgen zur Bildung der einzelnen Blöcke teilweise miteinander überlappt, um die geraden bzw. ungeraden Fortsetzungen der Blockbildung zu kompensieren. In der meist englischsprachigen Fachliteratur wird dies als {{Modul:Vorlage:lang}} Modul:Multilingual:153: attempt to index field 'data' (a nil value) bezeichnet. Ähnliche Verfahren finden im Rahmen der DFT beim Overlap-Add-Verfahren und dem Overlap-Save-Verfahren Anwendung, um die dort periodische Fortsetzung der DFT in die aperiodische Faltungsoperation zu überführen.

Die MDCT vermeidet das, was bei der DCT der JPEG-Kompression als Blockartefakte bekannt ist: Sprünge zwischen Abtastwerten benachbarter Transformationsblöcken. Das menschliche Gehör reagiert auf diese Form von Störungen noch wesentlich empfindlicher als das Auge, sodass ein Verfahren gefunden werden musste, das zwischen benachbarten Blöcken nicht schlagartig, sondern allmählich wechselt. Dies erfolgt durch eine Vergrößerung der in eine Transformation eingehenden Abtastwerte unter Verwendung einer Fensterfunktion. Dabei besteht aber das Problem, dass damit normalerweise die Datenmenge vergrößert würde, da Abtastwerte in Berechnungen mehrfach eingehen und redundant abgespeichert würden. Dieses Problem umgeht die MDCT, indem zwar <math>\mathrm{2N}</math> Abtastwerte als Ausgangswerte in die Transformation eingehen, aber nur <math>\mathrm{N}</math> Spektralwerte entstehen. Normalerweise wäre so eine Transformation hochgradig verlustbehaftet, allerdings löschen sich diese Fehler bei der Rücktransformation und beim Addieren von benachbarten rücktransformierten Blöcken unter gewissen Bedingungen wieder aus.

So besteht die Möglichkeit, eine Spektraltransformation mit Fensterfunktion durchzuführen, ohne dass sich die Anzahl der Werte vergrößert. Diese Fensterfunktion führt zu einer besseren Spektralauflösung bei der MDCT und zu weniger Artefakten bei der IMDCT.

Definition

Transformation

Durch die Überlappung ist bei der MDCT und im Unterschied zu symmetrischen Frequenztransformationen die Menge der Eingangssamples aus dem Zeitbereich doppelt so groß wie die daraus gebildeten spektralen Ausgangsdaten. Formal werden bei der Transformation <math>2\mathrm{N}</math> reelle Zahlen <math>x_0, \;\dots, x_{2\mathrm{N}-1}</math> auf <math>\mathrm{N}</math> reelle Zahlen <math>X_0, \;\dots, X_{\mathrm{N}-1}</math> nach folgender Beziehung abgebildet:

<math>X_k = \sum_{n=0}^{2\mathrm{N}-1} x_n \cos \left[\frac{\pi}{\mathrm{N}} \left(n+\frac{1}{2}+\frac{\mathrm{N}}{2}\right) \left(k+\frac{1}{2}\right) \right]\;</math> mit <math>\;k = 0, \;\dots, \mathrm{N}-1</math>

In der Literatur werden manchmal, in nicht einheitlicher Form und zur Normierung, in dieser Beziehung zusätzliche konstante Faktoren eingebracht, welche aber die Transformation nicht grundsätzlich verändern.

Inverse Transformation

Die inverse MDCT, abgekürzt IMDCT, stellt die Umkehrung zur obigen Transformation dar. Da die Eingangs- bzw. Ausgangsfolge eine unterschiedliche Anzahl umfassen, ist zur Umkehrung eine Addition im Zeitbereich der aufeinander folgenden Blöcke und der zeitlich überlappenden Bereiche im Rahmen der {{Modul:Vorlage:lang}} Modul:Multilingual:153: attempt to index field 'data' (a nil value) nötig.

Formal werden bei der IMDCT <math>\mathrm{N}</math> reelle Zahlen <math>X_0, \;\dots, X_{\mathrm{N}-1}</math> in <math>2\mathrm{N}</math> reelle Zahlen <math>y_0, \;\dots, y_{2\mathrm{N}-1}</math> übergeführt:

<math>y_n = \frac{1}{\mathrm{N}} \sum_{k=0}^{\mathrm{N}-1} X_k \cos \left[\frac{\pi}{\mathrm{N}} \left(n+\frac{1}{2}+\frac{\mathrm{N}}{2}\right) \left(k+\frac{1}{2}\right) \right]\;</math> mit <math>\;n = 0, \;\dots, 2\mathrm{N}-1</math>

Wie bei der DCT-IV, als eine Form von orthogonaler Transformation, ist die Rücktransformation bis auf einen Faktor identisch zu der Vorwärtstransformation.

Verwendung

Datei:TDAC-MDCTs of a sweep.png

Mehrere überlappende TDAC-MDCTs für Frequenzgang y(t) = cos (ct³)

Die MDCT ist die Basisoperation moderner Audiokompressionsverfahren. Dazu wird das Eingangssignal in sich zur Hälfte überlappende Blöcke <math>b = 0, 1, 2, \;\dots\,</math> der Länge <math>2\mathrm{N}</math> geteilt, die jeweils vom Abtastwert <math>x_{_{b\mathrm{N}-\mathrm{N}}}, \,\,\dots,\, x_{_{b\mathrm{N}+\mathrm{N}-1}}\,</math> reichen.

Die Transformation wird blockweise jeweils für jeden Block <math>b</math> unter Verwendung einer Fensterfunktion <math>w_n</math> (die gewisse Eigenschaften haben muss) durchgeführt:

<math>X_{b,k} \;=\; \sum_{n=0}^{2\mathrm{N}-1} w_n \;x_{_{b\mathrm{N}-\mathrm{N}+n}}\;\;\; \cos \left[\frac{\pi}{\mathrm{N}} \left(n+\frac{1}{2}+\frac{\mathrm{N}}{2}\right) \left(k+\frac{1}{2}\right) \right]\quad </math> mit <math>\;k = 0, \;\dots, \mathrm{N}-1, \;b \in \mathbb{N}</math>

Die Rücktransformation erfolgt für ein Sample <math>y_{_{b\mathrm{N}+n}}</math> mit <math>n = 0, \;\dots, \mathrm{N}-1</math> und <math>b \in \mathbb{N}</math>

<math>

\begin{align} y_{_{b\mathrm{N}+n}} = \frac{2}{\mathrm{N}} \Bigg( w_{n} \sum_{k=0}^{\mathrm{N}-1} & X_{b+1,k} \;\!\! \cos \left[\frac{\pi}{\mathrm{N}} \left(n+\frac{1}{2}+\frac{\mathrm{N}}{2}\right) \left(k+\frac{1}{2}\right) \right] \\

                                            -      w_{n+\mathrm{N}}  \sum_{k=0}^{\mathrm{N}-1} & X_{b  ,k} \quad\!\cos \left[\frac{\pi}{\mathrm{N}} \left(n+\frac{1}{2}+\frac{\mathrm{N}}{2}\right) \left(k+\frac{1}{2}\right) \right] \Bigg)

\end{align} </math>

Datei:MDCT WF.png

MDCT Fensterfunktionen
blau: Kosinus, rot: Sinus-Kosinus,
grün/d'grün: modifizierte Kaiser-Bessel mit α=6 bzw. 4

Datei:MDCT WF Leak.png

Leakage der MDCT Fensterfunktionen
blau: Kosinus, rot: Sinus-Kosinus,
grün/d'grün: modifizierte Kaiser-Bessel mit α=6 bzw. 4

Die Fenster-Funktion <math>w_n</math> muss folgende Eigenschaften haben:

Für die Analyse wie die Synthese eines Blocks <math>b</math> ist die gleiche Funktion zu verwenden. Sonst funktioniert das TDAC nicht.
Für jeden Abtastwert wird die Fensterfunktion sowohl bei der Analyse wie bei der Synthese je 2-mal angewendet. Diese beiden Werte müssen ohne Beschränkung der Allgemeinheit die Gleichung <math>w_{\mathrm{prev}}^2 + w_{\mathrm{next}}^2 = 1</math> erfüllen. Die Bedingung nennt sich Princen-Bradley-Bedingung. Ein Nebeneffekt dieser Bedingung erzwingt, dass die Funktionen bei <math>1/4</math> und <math>3/4</math> ihrer Fensterbreite den Wert <math>\sqrt{2}/2 \approx 0{,}7071</math> annehmen.
<math>w_n</math> sollte eine möglich glatte Funktion sein, um den Leck-Effekt gering zu halten, der
- bei der Analyse die Konzentration dominierender Signalkomponenten verringern würde und
- bei der Synthese Störsignale entfernt von dominierenden Signalkomponenten erzeugen würde (DC-Anteile würden z. B. durch Sprünge an Blockgrenzen ein Knattern verursachen).

Durch die zweite Bedingung unterscheidet sich die Fensterfunktion erheblich von den normalerweise üblichen Fensterfunktionen. Im Wesentlichen finden folgende drei Fensterfunktionen Anwendung:

Kosinusfenster (MPEG Layer-3, AAC)
modifizierte Kaiser-Bessel-Fenster (AAC, AC-3)
Sinus-Kosinus-Fenster (Ogg Vorbis)

Berechnungsaufwand

Die direkte Berechnung der MDCT nach obiger Formel benötigt <math>O(N^2)</math> Operationen. Ähnlich wie bei der schnellen Fourier-Transformation (FFT), als eine Form der effizienten Berechnung der DFT, existieren auch bei der MDCT-Algorithmen die ähnlich wie der Radix-2-Algorithmus aufgebaut sind, um die Anzahl der Rechenoperationen auf O(N log N) zu reduzieren.

Zudem lässt sich die MDCT mittels Pre- und Postprocessing und einer FFT berechnen.

Literatur

Henrique S. Malvar: Signal Processing with Lapped Transforms. Artech House, 1992, ISBN 0-89006-467-9.

Einzelnachweise