Upravená diskrétní kosinová transformace - Modified discrete cosine transform

Modifikovaná diskrétní kosinová transformace ( MDCT ) je transformace na základě typu IV diskrétní kosinové transformace (DCT-IV), s další vlastnost, že budou lapované : je navržen tak, aby se provádí na po sobě následujících bloků větší datové sady , kde následná bloky se překrývají, takže poslední polovina jednoho bloku se shoduje s první polovinou dalšího bloku. Toto překrývání, kromě vlastností zhutňování energie DCT, činí MDCT obzvláště atraktivní pro aplikace komprese signálu, protože pomáhá vyhnout se artefaktům pocházejícím z hranic bloku. V důsledku těchto výhod je MDCT nejpoužívanější technikou ztrátové komprese při kompresi zvukových dat . Používá se ve většině moderních standardů kódování zvuku , včetně 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 a MPEG-H 3D zvuk , stejně jako kódování řeči standardy jako AAC-LD (LD-MDCT), G.722.1 , G.729.1 , Kelt a opus .

Diskrétní kosinová transformace (DCT), byla poprvé navržena Nasir Ahmed v roce 1972, a prokázat Ahmed s T. Natarajan a KR Rao v roce 1974. MDCT byl později navržené John P. Princen, AW Johnson a Alan B. Bradley u University of Surrey v roce 1987, v návaznosti na dřívější práci Princena a Bradleyho (1986) na vývoji základního principu MDCT o zrušení aliasingu v časové oblasti (TDAC), popsaného níže. (Existuje také analogická transformace, MDST, založená na diskrétní sinusové transformaci , stejně jako jiné, zřídka používané, formy MDCT založené na různých typech kombinací DCT nebo DCT/DST.)

V MP3 není MDCT aplikován na zvukový signál přímo, ale spíše na výstup banky 32-pásmového polyfázového kvadraturního filtru (PQF). Výstup této MDCT je dodatečně zpracován pomocí vzorce pro redukci aliasů, aby se omezilo typické aliasing banky filtrů PQF. Taková kombinace banky filtrů s MDCT se nazývá hybridní banka filtrů nebo subpásmová MDCT. AAC, na druhé straně, normálně používá čistou MDCT; pouze (zřídka používaná) varianta MPEG-4 AAC-SSR (od Sony ) používá čtyřpásmovou banku PQF následovanou MDCT. Podobně jako MP3, ATRAC používá skládané kvadraturní zrcadlové filtry (QMF) následované MDCT.

Definice

Jako překrytá transformace je MDCT ve srovnání s jinými Fourierovými transformacemi trochu neobvyklé v tom, že má polovinu výstupů než vstupy (místo stejného počtu). Zejména se jedná o lineární funkci (kde R označuje množinu reálných čísel ). 2 N reálná čísla x 0 , ..., x 2 N -1 jsou transformována do N reálných čísel X 0 , ..., X N -1 podle vzorce:

(Normalizační koeficient před touto transformací, zde jednota, je libovolná konvence a liší se mezi léčbami. Omezen je pouze součin normalizací MDCT a IMDCT níže.)

Inverzní transformace

Inverzní MDCT je známý jako IMDCT . Protože existují různé počty vstupů a výstupů, na první pohled by se mohlo zdát, že MDCT by nemělo být invertibilní. Nicméně, perfektní invertibility je dosaženo přidáním překrývajících IMDCTs následných překrývajících se bloků, což způsobuje chyby zrušit a k načtení původních dat; tato technika je známá jako zrušení aliasu v časové doméně ( TDAC ).

IMDCT transformuje N reálných čísel X 0 , ..., X N -1 na 2 N reálných čísel y 0 , ..., y 2 N -1 podle vzorce:

(Stejně jako u DCT-IV , ortogonální transformace, má inverze stejnou formu jako dopředná transformace.)

V případě MDCT s okny s obvyklou normalizací okna (viz níže) by měl být normalizační koeficient před IMDCT vynásoben 2 (tj. Stát se 2/ N ).

Výpočet

Přestože by přímá aplikace vzorce MDCT vyžadovala operace O ( N 2 ), je možné rekurzivně faktorizovat výpočet stejně jako v případě složitosti O ( N log N ) to samé jako v rychlé Fourierově transformaci (FFT). Lze také vypočítat MDCT pomocí jiných transformací, obvykle DFT (FFT) nebo DCT, kombinovaných s kroky O ( N ) před a po zpracování. Jak je popsáno níže, jakýkoli algoritmus pro DCT-IV okamžitě poskytuje metodu pro výpočet MDCT a IMDCT stejné velikosti.

Funkce okna

Funkce okna MDCT:
modrá: kosinus, červená: sinus-kosinus, zelená: upravený Kaiser-Bessel

V typických aplikacích pro kompresi signálu jsou transformační vlastnosti dále vylepšeny pomocí funkce okna w n ( n = 0, ..., 2 N −1), která je ve vzorcích MDCT a IMDCT vynásobena x n a y n , výše, aby se zabránilo nespojitostem na hranicích n = 0 a 2 N tím, že funkce v těchto bodech přejde hladce na nulu. (To znamená, že data ukládáme před MDCT a po IMDCT.) V zásadě x a y mohly mít různé funkce okna a funkce okna se také mohla měnit z jednoho bloku do druhého (zejména v případě, kdy datové bloky různé velikosti jsou kombinovány), ale pro jednoduchost uvažujeme běžný případ identických okenních funkcí pro stejně velké bloky.

Transformace zůstává invertibilní (to znamená, že TDAC funguje), pro symetrické okno w n = w 2 N −1− n , pokud w splňuje podmínku Princen-Bradley:

.

Používají se různé funkce okna. Okno, které produkuje formu známou jako modulovaná lapovaná transformace (MLT), je dáno pomocí

a používá se pro MP3 a MPEG-2 AAC, a

pro Vorbis. AC-3 používá okno odvozené od Kaiser-Bessel (KBD) a MPEG-4 AAC může také použít okno KBD.

Všimněte si toho, že okna aplikovaná na MDCT se liší od oken používaných pro některé jiné typy analýzy signálu, protože musí splňovat podmínku Princen-Bradley. Jedním z důvodů tohoto rozdílu je, že okna MDCT jsou použita dvakrát, a to jak pro MDCT (analýza), tak pro IMDCT (syntéza).

Vztah k DCT-IV a původu TDAC

Jak je patrné z inspekce definic, pro sudý N je MDCT v podstatě ekvivalentní DCT -IV , kde je vstup posunut o N /2 a transformovány jsou dva N -bloky dat najednou. Pečlivějším zkoumáním této ekvivalence lze snadno odvodit důležité vlastnosti, jako je TDAC.

Aby bylo možné definovat přesný vztah k DCT-IV, je třeba si uvědomit, že DCT-IV odpovídá střídajícím se sudým/lichým okrajovým podmínkám: i na jeho levé hranici (kolem n  = −1/2), liché na pravé hranici (kolem n  =  N  - 1/2) atd. (místo periodických hranic jako u DFT ). Vyplývá to z identit a . Pokud jsou tedy jeho vstupy pole x délky N , můžeme si představit rozšíření tohoto pole na ( x , - x R , - x , x R , ...) a tak dále, kde x R označuje x v opačném pořadí.

Uvažujme MDCT se 2 N vstupy a N výstupy, kde vstupy rozdělíme do čtyř bloků ( a , b , c , d ), každý o velikosti N /2. Pokud je posuneme doprava o N /2 (z + N /2 členu v definici MDCT), pak ( b , c , d ) přesahují konec N vstupů DCT-IV, takže musíme „složit „zpět podle hraničních podmínek popsaných výše.

MDCT 2 N vstupů ( a , b , c , d ) je tedy přesně ekvivalentní DCT-IV z N vstupů: ( -c R - d , a - b R ), kde R označuje obrácení, jak je uvedeno výše.

(Tímto způsobem lze na MDCT triviálně použít jakýkoli algoritmus pro výpočet DCT-IV.)

Podobně výše uvedený vzorec IMDCT je přesně 1/2 DCT-IV (což je jeho vlastní inverze), kde je výstup prodloužen (přes okrajové podmínky) na délku 2 N a posunut zpět doleva o N /2 . Inverzní DCT-IV by jednoduše vrátilo vstupy ( -c R - d , a - b R ) shora. Když je toto rozšířeno přes okrajové podmínky a posunuto, získá se:

IMDCT (MDCT ( a , b , c , d )) = ( a - b R , b - a R , c + d R , d + c R ) / 2.

Polovina výstupů IMDCT je tedy nadbytečná, jako b - a R = - ( a - b R ) R , a podobně pro poslední dva termíny. Pokud vstup seskupíme do větších bloků A , B velikosti N , kde A  = ( a , b ) a B  = ( c , d ), můžeme tento výsledek napsat jednodušeji:

IMDCT (MDCT ( A , B )) = ( A - A R , B + B R ) / 2

Nyní lze pochopit, jak TDAC funguje. Předpokládejme, že se vypočítá MDCT následujícího, 50% překrývajícího se 2 N bloku ( B , C ). IMDCT pak poskytne analogicky k výše uvedenému: ( B - B R , C + C R ) / 2. Když je toto přidáno k předchozímu výsledku IMDCT v překrývající se polovině, obrácené termíny se zruší a jeden získá jednoduše B , zotavení původní data.

Původ TDAC

Původ pojmu „zrušení aliasu v časové oblasti“ je nyní jasný. Použití vstupních údajů, které přesahují hranice logického DCT-IV způsobí, že data mají být alias stejným způsobem, že frekvence nad rámec Nyquistovy frekvence jsou aliasem na nižší frekvence, s výjimkou, že tato chyba rušení se vyskytuje v časové doméně namísto frekvenční doména: nemůžeme rozlišit příspěvky a a b R k MDCT ( a , b , c , d ), nebo ekvivalentně, k výsledku

IMDCT (MDCT ( a , b , c , d )) = ( a - b R , b - a R , c + d R , d + c R ) / 2.

Kombinace c - d R atd. Mají přesně ta správná znaménka, která se mají kombinace při přidání zrušit.

Pro liché N (které se v praxi používají jen zřídka), N /2 není celé číslo, takže MDCT není jednoduše permutací posunu DCT-IV. V tomto případě další posun o polovinu vzorku znamená, že MDCT/IMDCT se stane ekvivalentem DCT-III/II a analýza je analogická s výše uvedeným.

Hladkost a nespojitosti

Výše jsme viděli, že MDCT 2 N vstupů ( a , b , c , d ) je ekvivalentní DCT-IV N vstupů ( -c R - d , a - b R ). DCT-IV je navržen pro případ, kdy je funkce na pravé hranici lichá, a proto jsou hodnoty blízko pravé hranice blízké 0. Pokud je vstupní signál plynulý, je tomu tak: nejsnáznější součásti a a b R jsou ve vstupní sekvenci po sobě jdoucí ( a , b , c , d ), a proto je jejich rozdíl malý. Podívejme se na střed intervalu: přepíšeme -li výše uvedený výraz jako ( - c R - d , a - b R ) = ( - d , a ) - ( b , c ) R , druhý člen, ( b , c ) R , dává hladký přechod uprostřed. V prvním termínu ( - d , a ) však existuje potenciální nespojitost, kde se pravý konec - d setkává s levým koncem a . To je důvod pro použití funkce okna, která snižuje komponenty blízko hranic vstupní sekvence ( a , b , c , d ) směrem k 0.

TDAC pro MDCT s okny

Výše byla vlastnost TDAC prokázána pro běžné MDCT, což ukazuje, že přidání IMDCT následných bloků do jejich překrývající se poloviny obnoví původní data. Odvození této inverzní vlastnosti pro MDCT s okny je jen o něco složitější.

U bloků A , B , C velikosti N zvažte překrývající se po sobě jdoucí sady 2 N vstupů ( A , B ) a ( B , C ) . Připomeňme shora, že když a jsou MDCTed, IMDCTed a přidány do jejich překrývající se poloviny, získáme původní data.

Nyní se domníváme, že vynásobíme obě MDCT vstupy a na IMDCT výstupy podle funkce okna o délce 2 N . Jak je uvedeno výše, předpokládáme symetrickou funkci okna, která má tedy tvar, kde W je vektor délky N a R označuje obrácení jako dříve. Pak lze podmínku Princen-Bradley zapsat jako se čtverci a sčítáním provedenými elementárně.

Proto místo MDCTing nyní MDCT (se všemi násobeními provedenými elementárně). Když je toto IMDCTed a znovu vynásobeno (po částech) funkcí okna, poslední polovina N se stane:

.

(Všimněte si, že již nemáme násobení o 1/2, protože normalizace IMDCT se v případě s okénkem liší o faktor 2.)

Podobně okno MDCT a IMDCT výnosů v první polovině N :

.

Když tyto dvě poloviny sečteme, získáme:

obnovení původních dat.

Viz také

Reference

Bibliografie

  • Henrique S.Malvar, zpracování signálu s lapovanými transformacemi (Artech House: Norwood MA, 1992).
  • AW Johnson a AB Bradley, „Adaptivní transformační kódování zahrnující zrušení aliasu časové domény“, Speech Comm. 6 , 299-308 (1987).
  • Algoritmy najdete v příkladech:
    • Chi-Min Liu a Wen-Chieh Lee, „ Jednotný rychlý algoritmus pro kosinově modulované filtrační banky v současných audio standardech “, J. Audio Engineering 47 (12), 1061-1075 (1999).
    • V. Britanak a KR Rao, „Nový rychlý algoritmus pro sjednocený dopředný a inverzní výpočet MDCT/MDST,“ zpracování signálu 82 , 433-459 (2002)
    • Vladimir Nikolajevic a Gerhard Fettweis, „Výpočet dopředného a inverzního MDCT pomocí Clenshawova opakovacího vzorce,“ IEEE Trans. Sig. Proč. 51 (5), 1439-1444 (2003)
    • Che-Hong Chen, Bin-Da Liu a Jar-Ferr Yang, „Rekurzivní architektury pro realizaci modifikované diskrétní kosinové transformace a její inverzní“, IEEE Trans. Obvody Syst. II: Analog Dig. Sig. Proč. 50 (1), 38-45 (2003)
    • JS Wu, HZ Shu, L. Senhadji a LM Luo, „Algoritmus smíšeného radixu pro výpočet dopředných a inverzních MDCT“, IEEE Trans. Obvody Syst. Já: Reg. Papíry 56 (4), 784-794 (2009)
    • V. Britanak, „Průzkum efektivních implementací MDCT do standardu kódování zvuku MP3: retrospektivní a nejmodernější,“ Signal. Proces. 91 (4), 624-672 (2011)