Modifizierte diskrete Kosinustransformation - Modified discrete cosine transform

Die modifizierte diskrete Kosinustransformation ( MDCT ) ist eine Transformation, die auf der diskreten Kosinustransformation vom Typ IV (DCT-IV) basiert , mit der zusätzlichen Eigenschaft, überlappt zu werden : Sie ist so konzipiert, dass sie an aufeinanderfolgenden Blöcken eines größeren Datensatzes durchgeführt wird , wenn nachfolgend Blöcke werden überlappt, so dass die letzte Hälfte eines Blocks mit der ersten Hälfte des nächsten Blocks übereinstimmt. Diese Überlappung, zusätzlich zu den Energieverdichtungseigenschaften des DCT, macht das MDCT besonders attraktiv für Signalkompressionsanwendungen, da es hilft, Artefakte zu vermeiden , die von den Blockgrenzen herrühren. Aufgrund dieser Vorteile ist MDCT die am weitesten verbreitete verlustbehaftete Kompressionstechnik bei der Audiodatenkompression . Es wird in den meisten modernen Audiocodierungsstandards verwendet , darunter MP3 , Dolby Digital (AC-3), Vorbis (Ogg), Windows Media Audio (WMA), ATRAC , Cook , Advanced Audio Coding (AAC), High-Definition Coding (HDC .). ), LDAC , Dolby AC-4 und MPEG-H 3D Audio sowie Sprachcodierungsstandards wie AAC-LD (LD-MDCT), G.722.1 , G.729.1 , CELT und Opus .

Die diskrete Kosinustransformation (DCT) wurde erstmals 1972 von Nasir Ahmed vorgeschlagen und 1974 von Ahmed mit T. Natarajan und KR Rao demonstriert . Die MDCT wurde später von John P. Princen, AW Johnson und Alan B. Bradley an der University of Surrey im Jahr 1987, nach früheren Arbeiten von Princen und Bradley (1986), um das dem MDCT zugrunde liegende Prinzip der Zeitbereichs-Aliasing-Aufhebung (TDAC) zu entwickeln, das unten beschrieben wird. (Es gibt auch eine analoge Transformation, die MDST, die auf der diskreten Sinustransformation basiert, sowie andere, selten verwendete Formen der MDCT, die auf verschiedenen Arten von DCT oder DCT/DST-Kombinationen basieren.)

Bei MP3 wird die MDCT nicht direkt auf das Audiosignal angewendet, sondern auf den Ausgang einer 32-Band Polyphase Quadratur Filter (PQF) Bank. Die Ausgabe dieser MDCT wird durch eine Alias-Reduktionsformel nachbearbeitet, um das typische Aliasing der PQF-Filterbank zu reduzieren. Ein solche Kombination aus einer Filterbank mit einer MDCT ist eine sogenannte Hybridfilterbank oder ein Subband MDCT. AAC hingegen verwendet normalerweise ein reines MDCT; nur die (selten verwendete) MPEG-4 AAC-SSR- Variante (von Sony ) verwendet eine Vierband-PQF-Bank gefolgt von einer MDCT. Ähnlich wie MP3 verwendet ATRAC gestapelte Quadraturspiegelfilter (QMF), gefolgt von einem MDCT.

Definition

Als überlappte Transformation ist die MDCT im Vergleich zu anderen Fourier-bezogenen Transformationen etwas ungewöhnlich, da sie halb so viele Ausgaben wie Eingaben hat (statt der gleichen Anzahl). Insbesondere handelt es sich um eine lineare Funktion (wobei R die Menge der reellen Zahlen bezeichnet ). Die 2 N reellen Zahlen x ₀ , ..., x _{2 N -1} werden nach der Formel in die N reellen Zahlen X ₀ , ..., X _{N -1 umgewandelt} : ${\displaystyle F\colon\mathbf{R}^{2N}\to\mathbf{R}^{N}}$

${\displaystyle X_{k}=\sum _{n=0}^{2N-1}x_{n}\cos \left[{\frac {\pi}{N}}\left(n+{\frac { 1}{2}}+{\frac{N}{2}}\right)\left(k+{\frac{1}{2}}\right)\right]}$

(Der Normalisierungskoeffizient vor dieser Transformation, hier Eins, ist eine willkürliche Konvention und unterscheidet sich zwischen den Behandlungen. Nur das Produkt der Normalisierungen der MDCT und der IMDCT unten ist eingeschränkt.)

Inverse Transformation

Die inverse MDCT ist als IMDCT bekannt . Da es unterschiedliche Anzahlen von Ein- und Ausgängen gibt, mag es auf den ersten Blick scheinen, dass der MDCT nicht invertierbar sein sollte. Jedoch perfekte Invertierbarkeit wird erreicht durch Zugabe der überlappten IMDCTs von nachfolgenden überlappenden Blöcken, wodurch die Fehler zu annullieren , und die ursprünglichen Daten wiedergewonnen werden; diese Technik ist als Time-Domain-Aliasing-Aufhebung ( TDAC ) bekannt.

Die IMDCT transformiert N reelle Zahlen X ₀ , ..., X _{N -1} in 2 N reelle Zahlen y ₀ , ..., y _{2 N -1} nach der Formel:

${\displaystyle y_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}\cos \left[{\frac {\pi}{N }}\left(n+{\frac{1}{2}}+{\frac{N}{2}}\right)\left(k+{\frac{1}{2}}\right)\right] }$

(Wie bei der DCT-IV , einer orthogonalen Transformation, hat die Inverse die gleiche Form wie die Vorwärtstransformation.)

Im Fall einer gefensterten MDCT mit der üblichen Fensternormierung (siehe unten) sollte der Normierungskoeffizient vor der IMDCT mit 2 multipliziert werden (dh zu 2/ N ).

Berechnung

Obwohl die direkte Anwendung der MDCT-Formel O( N ² ) Operationen erfordern würde , ist es möglich, dasselbe mit nur O( N log N ) Komplexität zu berechnen, indem die Berechnung rekursiv faktorisiert wird, wie bei der schnellen Fourier-Transformation (FFT). Man kann MDCTs auch über andere Transformationen berechnen, typischerweise eine DFT (FFT) oder eine DCT, kombiniert mit O( N ) Vor- und Nachbearbeitungsschritten. Außerdem stellt, wie unten beschrieben, jeder Algorithmus für die DCT-IV sofort ein Verfahren zum Berechnen der MDCT und IMDCT mit gerader Größe bereit.

Fensterfunktionen

In typischen Signalkompressionsanwendungen werden die Transformationseigenschaften weiter verbessert, indem eine Fensterfunktion w _n ( n = 0, ..., 2 N −1) verwendet wird, die mit x _n und y _n in den MDCT- und IMDCT-Formeln multipliziert wird. oben, um Diskontinuitäten an den Grenzen von n = 0 und 2 N zu vermeiden, indem man die Funktion an diesen Punkten glatt auf Null gehen lässt. (Das heißt, wir fenstern die Daten vor der MDCT und nach der IMDCT.) Im Prinzip könnten x und y unterschiedliche Fensterfunktionen haben, und die Fensterfunktion könnte sich auch von einem Block zum nächsten ändern (insbesondere für den Fall, dass Datenblöcke unterschiedlicher Größe kombiniert), aber der Einfachheit halber betrachten wir den üblichen Fall identischer Fensterfunktionen für gleich große Blöcke.

Die Transformation bleibt invertierbar (d. h. TDAC funktioniert), für ein symmetrisches Fenster w _n = w _{2 N −1− n} , solange w die Princen-Bradley-Bedingung erfüllt:

${\displaystyle w_{n}^{2}+w_{n+N}^{2}=1}$.

Es werden verschiedene Fensterfunktionen verwendet. Ein Fenster, das eine Form erzeugt, die als modulierte überlappte Transformation (MLT) bekannt ist, ist gegeben durch

${\displaystyle w_{n}=\sin\left[{\frac {\pi}{2N}}\left(n+{\frac{1}{2}}\right)\right]}$

und wird für MP3 und MPEG-2 AAC verwendet, und

${\displaystyle w_{n}=\sin\left({\frac{\pi}{2}}\sin^{2}\left[{\frac {\pi}{2N}}\left(n+{\ frac {1}{2}}\right)\right]\right)}$

für Vorbis. AC-3 verwendet ein von Kaiser-Bessel abgeleitetes (KBD) Fenster und MPEG-4 AAC kann auch ein KBD-Fenster verwenden.

Beachten Sie, dass sich Fenster, die auf die MDCT angewendet werden, von Fenstern unterscheiden, die für einige andere Arten der Signalanalyse verwendet werden, da sie die Princen-Bradley-Bedingung erfüllen müssen. Einer der Gründe für diesen Unterschied ist, dass MDCT-Fenster zweimal angewendet werden, sowohl für die MDCT (Analyse) als auch für die IMDCT (Synthese).

Beziehung zu DCT-IV und Ursprung von TDAC

Wie aus der Betrachtung der Definitionen ersichtlich ist, ist die MDCT sogar für N im Wesentlichen äquivalent zu einer DCT-IV, bei der die Eingabe um N /2 verschoben wird und zwei N- Datenblöcke gleichzeitig transformiert werden. Durch genauere Untersuchung dieser Äquivalenz können wichtige Eigenschaften wie TDAC leicht abgeleitet werden.

Um die genaue Beziehung zum DCT-IV zu definieren, muss man erkennen, dass das DCT-IV abwechselnd gerade/ungerade Randbedingungen entspricht: gerade am linken Rand (um n  = −1/2), ungerade am rechten Rand (um n  =  N  − 1/2), und so weiter (statt periodischer Grenzen wie bei einer DFT ). Dies folgt aus den Identitäten und . Somit kann , wenn seine Eingänge ein Array sind x der Länge N , können wir dieses Array vorstellen erstreckt bis ( x - x _R , - x , x _R , ...) und so weiter, wo x _R Bezeichnet x in umgekehrter Reihenfolge. ${\displaystyle \cos \left[{\frac {\pi }{N}}\left(-n-1+{\frac {1}{2}}\right)\left(k+{\frac {1} {2}}\right)\right]=\cos\left[{\frac{\pi}{N}}\left(n+{\frac{1}{2}}\right)\left(k+{\ frac {1}{2}}\right)\right]}$${\displaystyle \cos \left[{\frac {\pi }{N}}\left(2N-n-1+{\frac {1}{2}}\right)\left(k+{\frac {1 }{2}}\right)\right]=-\cos \left[{\frac{\pi}{N}}\left(n+{\frac{1}{2}}\right)\left(k+ {\frac{1}{2}}\right)\right]}$

Betrachten Sie eine MDCT mit 2 N Eingängen und N Ausgängen, wobei wir die Eingänge in vier Blöcke ( a , b , c , d ) jeweils der Größe N /2 aufteilen . Wenn wir diese um N /2 nach rechts verschieben (vom + N /2-Term in der MDCT-Definition), dann erstrecken sich ( b , c , d ) über das Ende der N DCT-IV-Eingänge hinaus, also müssen wir "falten " sie entsprechend den oben beschriebenen Randbedingungen zurück.

Somit ist die MDCT von 2 N Eingängen ( a , b , c , d ) genau äquivalent zu einer DCT-IV der N Eingänge: (− c _R − d , a − b _R ), wobei R die Umkehrung wie oben bezeichnet.

(Auf diese Weise kann jeder Algorithmus zur Berechnung der DCT-IV trivial auf die MDCT angewendet werden.)

In ähnlicher Weise ist die obige IMDCT-Formel genau 1/2 der DCT-IV (die ihre eigene Inverse ist), wobei die Ausgabe (über die Randbedingungen) auf eine Länge von 2 N erweitert und um N /2 . nach links verschoben wird . Die inverse DCT-IV würde einfach die Eingaben (− c _R − d , a − b _R ) von oben zurückgeben. Wird diese über die Randbedingungen erweitert und verschoben, erhält man:

IMDCT (MDCT ( a , b , c , d )) = ( a − b _R , b − a _R , c + d _R , d + c _R ) / 2.

Die Hälfte der IMDCT-Ausgaben ist somit redundant, da b − a _R = −( a − b _R ) _R , und ebenso für die letzten beiden Terme. Wenn wir die Eingabe in größere Blöcke A , B der Größe N gruppieren , wobei A  = ( a , b ) und B  = ( c , d ) ist, können wir dieses Ergebnis einfacher schreiben:

IMDCT (MDCT ( A , B )) = ( A − A _R , B + B _R ) / 2

Man kann jetzt verstehen, wie TDAC funktioniert. Angenommen, man berechnet die MDCT des nachfolgenden, zu 50% überlappenden 2N- Blocks ( B , C ). Die IMDCT ergibt dann analog zu obigem: ( B − B _R , C + C _R ) / 2. Wenn dies mit dem vorherigen IMDCT-Ergebnis in der überlappenden Hälfte addiert wird, heben sich die umgekehrten Terme auf und man erhält einfach B , wiederhergestellt die Originaldaten.

Herkunft von TDAC

Der Ursprung des Begriffs "Zeitdomänen-Aliasing-Aufhebung" ist jetzt klar. Die Verwendung von Eingangsdaten , die über die Grenzen der logischen DCT-IV erstrecken bewirkt , dass die Daten zu aliased in der gleichen Art und Weise , dass die Frequenzen jenseits der Nyquist - Frequenz sind aliased Frequenzen zu senken, mit der Ausnahme , dass dieser Aliasing tritt auf in der Zeitdomäne anstelle dem Frequenzbereich: Wir können die Beiträge von a und b _R zur MDCT von ( a , b , c , d ) oder äquivalent zum Ergebnis von nicht unterscheiden

IMDCT (MDCT ( a , b , c , d )) = ( a − b _R , b − a _R , c + d _R , d + c _R ) / 2.

Die Kombinationen c − d _R usw. haben genau die richtigen Vorzeichen, damit sich die Kombinationen beim Addieren aufheben.

Für ungerade N (die in der Praxis selten verwendet werden) ist N /2 keine ganze Zahl, so dass die MDCT nicht einfach eine Verschiebungspermutation einer DCT-IV ist. In diesem Fall bedeutet die zusätzliche Verschiebung um eine halbe Probe, dass die MDCT/IMDCT der DCT-III/II entspricht, und die Analyse ist analog zu oben.

Glätte und Diskontinuitäten

Wir haben oben gesehen, dass die MDCT von 2 N Eingängen ( a , b , c , d ) äquivalent zu einer DCT-IV der N Eingänge (− c _R − d , a − b _R ) ist. Das DCT-IV ist für den Fall konzipiert, dass die Funktion an der rechten Grenze ungerade ist und daher die Werte nahe der rechten Grenze nahe 0 sind. Wenn das Eingangssignal glatt ist, ist dies der Fall: die ganz rechten Komponenten von a und b _R sind in der Eingabesequenz ( a , b , c , d ) aufeinanderfolgend , und daher ist ihre Differenz klein. Schauen wir uns die Mitte des Intervalls an: Wenn wir den obigen Ausdruck umschreiben als (− c _R − d , a − b _R ) = (− d , a )−( b , c ) _R , der zweite Term, ( b , c ) _R , ergibt einen glatten Übergang in der Mitte. Im ersten Term (− d , a ) gibt es jedoch eine potentielle Diskontinuität, wo das rechte Ende von − d auf das linke Ende von a trifft . Dies ist der Grund für die Verwendung einer Fensterfunktion, die die Komponenten nahe den Grenzen der Eingabesequenz ( a , b , c , d ) gegen 0 reduziert .

TDAC für das Fenster-MDCT

Oben wurde die TDAC-Eigenschaft für die gewöhnliche MDCT bewiesen, was zeigt, dass das Hinzufügen von IMDCTs von nachfolgenden Blöcken in ihrer überlappenden Hälfte die ursprünglichen Daten wiederherstellt. Die Ableitung dieser inversen Eigenschaft für die gefensterte MDCT ist nur geringfügig komplizierter.

Betrachten Sie für Blöcke A , B , C der Größe N überlappende aufeinanderfolgende Sätze von 2 N Eingängen ( A , B ) und ( B , C ) . Erinnern Sie sich von oben, dass, wenn und MDCTed, IMDCTed und in ihrer überlappenden Hälfte hinzugefügt werden, wir die Originaldaten erhalten. ${\displaystyle (A,B)}$${\displaystyle (B,C)}$${\displaystyle (B+B_{R})/2+(B-B_{R})/2=B}$

Nun nehmen wir an, dass wir sowohl die MDCT-Eingänge als auch die IMDCT-Ausgänge mit einer Fensterfunktion der Länge 2 N multiplizieren . Wie oben nehmen wir eine symmetrische Fensterfunktion an, die daher die Form hat, in der W ein Vektor der Länge N ist und R wie zuvor die Umkehrung bezeichnet. Dann kann die Princen-Bradley-Bedingung als geschrieben werden , wobei die Quadrate und Additionen elementweise ausgeführt werden. ${\displaystyle (W,W_{R})}$${\displaystyle W^{2}+W_{R}^{2}=(1,1,\ldots)}$

Daher wird anstelle von MDCTing jetzt MDCT (wobei alle Multiplikationen elementweise durchgeführt werden). Wenn dies IMDCTed und erneut (elementweise) mit der Fensterfunktion multipliziert wird, wird die letzte N- Hälfte zu: ${\displaystyle (A,B)}$${\displaystyle (WA,W_{R}B)}$

${\displaystyle W_{R}\cdot (W_{R}B+(W_{R}B)_{R})=W_{R}\cdot (W_{R}B+WB_{R})=W_{R }^{2}B+WW_{R}B_{R}}$.

(Beachten Sie, dass wir die Multiplikation mit 1/2 nicht mehr haben, da sich die IMDCT-Normalisierung im gefensterten Fall um den Faktor 2 unterscheidet.)

Ebenso die gefensterte MDCT und IMDCT der Renditen in ihrer ersten N- Hälfte: ${\displaystyle (B,C)}$

${\displaystyle W\cdot (WB-W_{R}B_{R})=W^{2}B-WW_{R}B_{R}}$.

Wenn wir diese beiden Hälften addieren, erhalten wir:

${\displaystyle (W_{R}^{2}B+WW_{R}B_{R})+(W^{2}B-WW_{R}B_{R})=\left(W_{R}^ {2}+W^{2}\right)B=B,}$

Wiederherstellung der Originaldaten.

Siehe auch

• Diskrete Kosinustransformation
• Andere überlappende gefensterte Fourier-Transformationen umfassen:
  • Modulierte komplexe überlappte Transformation
  • Kurzzeit-Fourier-Transformation
  • Welchs Methode
• Audiocodierungsformat
• Audiokomprimierung (Daten)

Verweise

Literaturverzeichnis

• Henrique S. Malvar, Signal Processing with Lapped Transforms (Artech House: Norwood MA, 1992).
• AW Johnson und AB Bradley, "Adaptive Transformationscodierung mit Zeitdomänen-Aliasing-Aufhebung", Speech Comm. 6 , 299-308 (1987).
• Für Algorithmen siehe Beispiele:
  • Chi-Min Liu und Wen-Chieh Lee, " Ein vereinheitlichter schneller Algorithmus für kosinusmodulierte Filterbänke in aktuellen Audiostandards ", J. Audio Engineering 47 (12), 1061-1075 (1999).
  • V. Britanak und KR Rao, "Ein neuer schneller Algorithmus für die vereinheitlichte Vorwärts- und inverse MDCT/MDST-Berechnung", Signal Processing 82 , 433-459 (2002)
  • Vladimir Nikolajevic und Gerhard Fettweis, "Berechnung von vorwärts und inverser MDCT mit Clenshaws Rekursionsformel", IEEE Trans. Sig. Proz. 51 (5), 1439-1444 (2003)
  • Che-Hong Chen, Bin-Da Liu und Jar-Ferr Yang, "Rekursive Architekturen zur Realisierung einer modifizierten diskreten Kosinustransformation und ihrer Umkehrung", IEEE Trans. Schaltungen Syst. II: Analoge Dig. Sig. Proz. 50 (1), 38-45 (2003)
  • JS Wu, HZ Shu, L. Senhadji und LM Luo, "Mixed-Radix-Algorithmus zur Berechnung von Vorwärts- und inversen MDCTs", IEEE Trans. Schaltungen Syst. Ich: Reg.-Nr. Papiere 56 (4), 784-794 (2009)
  • V. Britanak, "Eine Übersicht über effiziente MDCT-Implementierungen im MP3-Audiocodierungsstandard: Retrospektive und Stand der Technik", Signal. Verfahren. 91 (4), 624-672 (2011)