Zmodyfikowana dyskretna transformata kosinusowa - Modified discrete cosine transform
Zmodyfikowaną dyskretną transformatę kosinusową ( MDCT ) jest przekształcenie na podstawie typu IV dyskretnej transformacji kosinusowej (DCT-IV), z dodatkową właściwość, że docierane : jest zaprojektowany do wykonania w kolejnych blokach większej zestawu danych , gdzie poszczególne bloki zachodzą na siebie tak, że ostatnia połowa jednego bloku pokrywa się z pierwszą połową następnego bloku. To nakładanie się, oprócz właściwości zagęszczania energii DCT, czyni MDCT szczególnie atrakcyjnym dla zastosowań kompresji sygnału, ponieważ pomaga uniknąć artefaktów wynikających z granic bloków. W wyniku tych zalet MDCT jest najczęściej stosowaną techniką kompresji stratnej w kompresji danych audio . Jest stosowany w większości nowoczesnych standardów kodowania dźwięku , w tym 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 i MPEG-H 3D Audio , a także standardy kodowania mowy, takie jak AAC-LD (LD-MDCT), G.722.1 , G.729.1 , CELT i Opus .
Dyskretnej transformaty cosinus (DCT), została zaproponowana przez Nasir Ahmed, 1972, i wykazano Ahmed T. Natarajan i KR Rao 1974. MDCT później zaproponowano John P. Princena AW Johnson i Alan B. Bradleya u University of Surrey w 1987 roku, po wcześniejszych pracach Princena i Bradleya (1986) nad opracowaniem podstawowej zasady MDCT dotyczącej anulowania aliasingu w dziedzinie czasu (TDAC), opisanej poniżej. (Istnieje również analogiczna transformata MDST, oparta na dyskretnej transformacji sinusoidalnej , a także inne, rzadko używane formy MDCT oparte na różnych typach kombinacji DCT lub DCT/DST.)
W MP3 MDCT nie jest nakładana bezpośrednio na sygnał audio, ale raczej na wyjście 32- pasmowego banku filtrów kwadraturowych (PQF). Wyjście tego MDCT jest przetwarzane przez formułę redukcji aliasów w celu zmniejszenia typowego aliasingu banku filtrów PQF. Taka kombinacja banku filtrów z MDCT nazywana jest hybrydowym bankiem filtrów lub podpasmem MDCT. Z drugiej strony AAC zwykle używa czystego MDCT; tylko (rzadko używany) wariant MPEG-4 AAC-SSR (firmy Sony ) wykorzystuje czterozakresowy bank PQF, po którym następuje MDCT. Podobnie jak w przypadku formatu MP3, ATRAC wykorzystuje ułożone filtry lustrzane kwadraturowe (QMF), po których następuje MDCT.
Definicja
Jako transformata lapped, MDCT jest nieco nietypowa w porównaniu do innych transformacji Fouriera, ponieważ ma o połowę mniej wyjść niż wejść (zamiast tej samej liczby). W szczególności jest to funkcja liniowa (gdzie R oznacza zbiór liczb rzeczywistych ). 2 N liczb rzeczywistych x 0 , ..., x 2 N -1 przekształca się w N liczb rzeczywistych X 0 , ..., X N -1 według wzoru:
(Współczynnik normalizacji przed tą transformacją, tutaj jedność, jest arbitralną konwencją i różni się w zależności od leczenia. Ograniczony jest tylko iloczyn normalizacji MDCT i IMDCT poniżej.)
Odwrotna transformata
Odwrotna MDCT jest znana jako IMDCT . Ponieważ istnieją różne liczby wejść i wyjść, na pierwszy rzut oka może się wydawać, że MDCT nie powinno być odwracalne. Jednak idealną odwracalność uzyskuje się przez dodanie nakładających się IMDCT kolejnych nakładających się bloków, co powoduje anulowanie błędów i odzyskanie oryginalnych danych; ta technika jest znana jako anulowanie aliasingu w dziedzinie czasu ( TDAC ).
IMDCT przekształca N liczb rzeczywistych X 0 , ..., X N -1 na 2 N liczb rzeczywistych y 0 , ..., y 2 N -1 według wzoru:
(Podobnie jak w przypadku DCT-IV , transformacji ortogonalnej, odwrotność ma taką samą postać jak transformata w przód.)
W przypadku okienkowanej MDCT ze zwykłą normalizacją okienkową (patrz poniżej), współczynnik normalizacji przed IMDCT powinien być pomnożony przez 2 (tj. stając się 2/ N ).
Obliczenie
Chociaż bezpośrednie zastosowanie wzoru MDCT wymaga O ( N 2 ) operacji, możliwe jest obliczenie samo z tylko O ( N log N ) złożoności przez rekurencyjnie factorizing obliczeń, jak w szybkiej transformaty Fouriera (FFT). Można również obliczyć MDCT za pomocą innych przekształceń, zwykle DFT (FFT) lub DCT, w połączeniu z etapami przetwarzania wstępnego i końcowego O( N ). Ponadto, jak opisano poniżej, dowolny algorytm dla DCT-IV natychmiast zapewnia sposób obliczania MDCT i IMDCT o parzystym rozmiarze.
Funkcje okna
W typowych zastosowaniach sygnał kompresji właściwości przekształcić można jeszcze poprawić przez zastosowanie funkcji okna wagowo N ( n = 0, ..., 2 N -1) mnożona x n i a n we wzorze MDCT i IMDCT, powyżej, w celu uniknięcia nieciągłości na granicach n = 0 i 2 N poprzez spowodowanie, że funkcja przejdzie gładko do zera w tych punktach. (Oznacza to, że okienkujemy dane przed MDCT i po IMDCT.) W zasadzie x i y mogą mieć różne funkcje okna, a funkcja okna może również zmieniać się z jednego bloku do następnego (szczególnie w przypadku, gdy bloki danych różnych rozmiarów), ale dla uproszczenia rozważamy wspólny przypadek identycznych funkcji okna dla bloków o jednakowych rozmiarach.
Transformacja pozostaje odwracalna (tj. TDAC działa), dla okna symetrycznego w n = w 2 N −1− n , o ile w spełnia warunek Princena-Bradleya:
- .
Wykorzystywane są różne funkcje okna. Okno, które tworzy formę znaną jako modulowana transformacja złożona (MLT) jest podane przez
i jest używany do plików MP3 i MPEG-2 AAC oraz
dla Vorbisa. AC-3 używa okna pochodnego Kaisera-Bessela (KBD) , a MPEG-4 AAC może również używać okna KBD.
Należy zauważyć, że okna zastosowane do MDCT różnią się od okien używanych do niektórych innych typów analizy sygnału, ponieważ muszą spełniać warunek Princen-Bradley. Jedną z przyczyn tej różnicy jest to, że okna MDCT są stosowane dwukrotnie, zarówno dla MDCT (analiza), jak i IMDCT (synteza).
Związek z DCT-IV i pochodzenie TDAC
Jak można zauważyć, sprawdzając definicje, nawet dla N MDCT jest zasadniczo równoważne DCT-IV, gdzie wejście jest przesuwane o N /2 i dwa N- bloki danych są transformowane jednocześnie. Dzięki dokładniejszemu zbadaniu tej równoważności można łatwo wyprowadzić ważne właściwości, takie jak TDAC.
Aby określić dokładny związek z DCT-IV, należy zdać sobie sprawę, że DCT-IV odpowiada naprzemiennym parzystym/nieparzystym warunkom brzegowym: parzysty na swojej lewej granicy (około n = -1/2), nieparzysty na swojej prawej granicy (około n = N − 1/2) i tak dalej (zamiast okresowych granic jak dla DFT ). Wynika to z tożsamości i . Tak więc, jeśli jego dane wejściowe są tablicą x o długości N , możemy sobie wyobrazić rozszerzenie tej tablicy do ( x , − x R , − x , x R , ...) i tak dalej, gdzie x R oznacza x w odwrotnej kolejności.
Rozważ MDCT z 2 N wejściami i N wyjściami, gdzie dzielimy wejścia na cztery bloki ( a , b , c , d ) każdy o rozmiarze N /2. Jeśli przesuniemy je w prawo o N /2 (od wyrażenia + N /2 w definicji MDCT), to ( b , c , d ) rozciągają się poza koniec wejść N DCT-IV, więc musimy „złożyć " je z powrotem zgodnie z warunkami brzegowymi opisanymi powyżej.
- Zatem MDCT 2 N wejść ( a , b , c , d ) jest dokładnie równoważne DCT-IV z N wejść: (- c R - d , a - b R ), gdzie R oznacza odwrócenie jak powyżej.
(W ten sposób każdy algorytm do obliczania DCT-IV może być trywialnie zastosowany do MDCT.)
Podobnie, powyższa formuła IMDCT to dokładnie 1/2 DCT-IV (co jest swoją odwrotnością), gdzie wyjście jest rozszerzone (poprzez warunki brzegowe) do długości 2 N i przesunięte z powrotem w lewo o N /2 . Odwrotność DCT-IV po prostu zwróci dane wejściowe (− c R − d , a − b R ) z góry. Po rozszerzeniu przez warunki brzegowe i przesunięciu otrzymujemy:
- IMDCT (MDCT ( a , b , c , d )) = ( a − b R , b − a R , c + d R , d + c R ) / 2.
Połowa wyjść IMDCT jest zatem zbędna, ponieważ b - a R = - ( a - b R ) R , i podobnie dla dwóch ostatnich składników. Jeśli zgrupujemy dane wejściowe w większe bloki A , B o rozmiarze N , gdzie A = ( a , b ) i B = ( c , d ), możemy zapisać ten wynik w prostszy sposób:
- IMDCT (MDCT ( , B )) = ( - R , B + B R ) / 2
Teraz można zrozumieć, jak działa TDAC. Załóżmy, że oblicza się MDCT kolejnego, nakładającego się w 50%, bloku 2N ( B , C ). IMDCT następnie poddaje się, analogicznie jak w powyższym ( B - B R , C + C, R ) / 2. Kiedy ten dodano do poprzedniego związku IMDCT w zakładkowej połowie odwróconych warunki anulowania i otrzymuje się po prostu B , odzyskiwanie oryginalne dane.
Pochodzenie TDAC
Pochodzenie terminu „anulowanie aliasingu w dziedzinie czasu” jest teraz jasne. Użycie danych wejściowych, które wykraczają poza granice logicznego DCT-IV powoduje, że dane są aliasowane w ten sam sposób, w jaki częstotliwości poza częstotliwością Nyquista są aliasowane do niższych częstotliwości, z wyjątkiem tego, że ten aliasing występuje w dziedzinie czasu zamiast dziedzina częstotliwości: nie możemy rozróżnić wkładów a i b R do MDCT ( a , b , c , d ) lub równoważnie do wyniku
- IMDCT (MDCT ( a , b , c , d )) = ( a − b R , b − a R , c + d R , d + c R ) / 2.
Kombinacje c - d R i tak dalej, mają dokładnie odpowiednie znaki, aby kombinacje zostały anulowane po ich dodaniu.
Dla nieparzystego N (które są rzadko używane w praktyce), N /2 nie jest liczbą całkowitą, więc MDCT nie jest po prostu przesuniętą permutacją DCT-IV. W tym przypadku dodatkowe przesunięcie o połowę próbki oznacza, że MDCT/IMDCT staje się równoważna DCT-III/II, a analiza przebiega analogicznie do powyższej.
Gładkość i nieciągłości
Widzieliśmy powyżej, że MDCT 2 N wejść ( a , b , c , d ) jest równoważne DCT-IV z N wejść ( - c R - d , a - b R ). DCT-IV jest przeznaczony do przypadku, gdy funkcja na prawej granicy jest nieparzysta, a zatem wartości w pobliżu prawej granicy są bliskie 0. Jeśli sygnał wejściowy jest gładki, to jest to przypadek: skrajne prawe składowe a i b R są kolejne w ciągu wejściowym ( a , b , c , d ), a zatem ich różnica jest niewielka. Spójrzmy na środek przedziału: jeśli przepiszemy powyższe wyrażenie jako (− c R − d , a − b R ) = (− d , a )−( b , c ) R , drugi wyraz, ( b , c ) R , daje płynne przejście w środku. Jednak w pierwszym członie (− d , a ) istnieje potencjalna nieciągłość, w której prawy koniec − d styka się z lewym końcem a . To jest powód używania funkcji okna, która redukuje komponenty w pobliżu granic sekwencji wejściowej ( a , b , c , d ) do 0.
TDAC dla okienkowego MDCT
Powyżej, właściwość TDAC została udowodniona dla zwykłego MDCT, pokazując, że dodanie IMDCT kolejnych bloków w ich nakładającej się połowie przywraca oryginalne dane. Wyprowadzenie tej odwrotnej właściwości dla okienkowanej MDCT jest tylko nieco bardziej skomplikowane.
Rozważyć nakładania kolejnych zestawów 2 N wejściami ( , B ) i ( B , C ), dla bloków , B , C o rozmiarze N . Przypomnijmy z powyższego, że kiedy i są MDCTed, IMDCTed i dodawane w ich nakładającej się połowie, otrzymujemy oryginalne dane.
Załóżmy teraz, że mnożymy zarówno wejścia MDCT, jak i wyjścia IMDCT przez funkcję okna o długości 2 N . Jak powyżej, zakładamy symetryczną funkcję okna, która ma zatem postać, w której W jest wektorem długości N, a R oznacza odwrócenie jak poprzednio. Wtedy warunek Princena-Bradleya można zapisać jako , z kwadratami i dodatkami wykonanymi elementarnie.
Dlatego zamiast MDCTing , teraz MDCT (ze wszystkimi mnożeniami wykonywanymi elementarnie). Kiedy jest to IMDCTed i ponownie pomnożone (elementwise) przez funkcję okna, ostatnia połowa N staje się:
- .
(Zauważ, że nie mamy już mnożenia przez 1/2, ponieważ normalizacja IMDCT różni się o współczynnik 2 w przypadku okienkowym).
Podobnie, okienkowane MDCT i IMDCT plonów, w swojej pierwszej połowie N :
- .
Gdy dodamy te dwie połówki razem, otrzymamy:
odzyskiwanie oryginalnych danych.
Zobacz też
- Dyskretna transformata cosinus
- Inne nakładające się okienkowane transformaty Fouriera obejmują:
- Format kodowania dźwięku
- Kompresja audio (dane)
Bibliografia
Bibliografia
- Henrique S. Malvar, Przetwarzanie sygnału z docieranymi transformacjami (Artech House: Norwood MA, 1992).
- AW Johnson i AB Bradley, „Kodowanie adaptacyjne z transformacją obejmującą eliminację aliasingu w dziedzinie czasu”, Speech Comm. 6 , 299-308 (1987).
- Aby zapoznać się z algorytmami, zobacz przykłady:
- Chi-Min Liu i Wen-Chieh Lee, „ Ujednolicony szybki algorytm dla banków filtrów z modulacją kosinusową w obecnych standardach audio ”, J. Audio Engineering 47 (12), 1061-1075 (1999).
- V. Britanak i KR Rao, „Nowy szybki algorytm do ujednoliconego obliczania MDCT/MDST w przód i w tył”, Przetwarzanie sygnału 82 , 433-459 (2002)
- Vladimir Nikolajevic i Gerhard Fettweis, „Obliczanie do przodu i do tyłu MDCT przy użyciu formuły rekurencyjnej Clenshawa”, IEEE Trans. Syg. Proc. 51 (5), 1439-1444 (2003)
- Che-Hong Chen, Bin-Da Liu i Jar-Ferr Yang, „Architektury rekurencyjne do realizacji zmodyfikowanej dyskretnej transformacji kosinusowej i jej odwrotności”, IEEE Trans. System obwodów. II: Cyfry analogowe. Syg. Proc. 50 (1), 38-45 (2003)
- JS Wu, HZ Shu, L. Senhadji i LM Luo, „Algorytm o mieszanej podstawie do obliczania MDCT w przód i w tył”, IEEE Trans. System obwodów. I: Rozp. Zeszyty 56 (4), 784-794 (2009)
- V. Britanak, „Badanie wydajnych implementacji MDCT w standardzie kodowania audio MP3: retrospektywne i najnowocześniejsze”, Signal. Proces. 91 (4), 624-672 (2011)