Úvod
Rýchla Fourierova transformácia (FFT) je efektívny algoritmus na výpočet diskrétnej Fourierovej transformácie (DFT). DFT sa používa na dekompozíciu signálu na frekvenčné zložky. FFT výrazne znižuje výpočtovú náročnosť DFT, čím umožňuje efektívnu analýzu signálov v rôznych aplikáciách.
Ortogonálne Transformácie a Dekorelovanosť Dát
Úlohou ortogonálnych transformácií je zmenšiť korelovanosť dát. Z praktických dôvodov ide o bloky dát určitej veľkosti, ktoré možno chápať aj ako vektory (napr. dĺžky n). Vzájomné závislosti v hodnotách ich prvkov sa dajú vyjadriť matematicky, a to použitím báz, ktoré tieto závislosti budú odzrkadľovať. Ak vektory nebudeme vyjadrovať v jednotkovej báze, teda v báze e1, e2, …, en (kde ei={0,…,0,1,0,…,0} s jednotkou na i-tom mieste), čo je princíp PCM, ale v báze obsahujúcej napr. sinusoidy rozličných frekvencií (ktoré viac odzrkadľujú štruktúru zvuku), môže dôjsť k značnej redukcii medzisymbolovej redundancie. Táto zmena vyjadrenia vektorov je vlastne zmenou súradníc, známou z algebry, ktorú možno vyjadriť maticou prechodu A obsahujúcou zápis pôvodnej (jednotkovej) bázy vyjadrenej v novej báze. Presnejšie, pre vstupný signál vyjadrený n-rozmerným (stĺpcovým) vektorom x a transformačnú maticu An×n (ide o maticu prechodu medzi jednotkovou bázou a novou bázou) vypočítame dekorelovaný vektor ako t=Ax . Ak je matica A ortonormálna (jej vektory majú jednotkovú veľkosť a platí A−1=AT ), nedochádza k zmene energie vektorov, teda tT⋅t=xT⋅x . Prvky vektora t možno vyjadriť aj z jednotlivých riadkov a0 ,a1 ,…
Fourierova Transformácia: Základný Princíp
Fourierova transformácia je špeciálny prípad ortogonálnej transformácie. Nesie meno po francúzskom matematikovi a fyzikovi Jeanovi Baptistovi Josephovi Fourierovi, ktorý na začiatku 19. storočia ukázal, že každú funkciu periodickú s istou frekvenciou možno vyjadriť ako súčet sínusových vĺn harmonických násobkov tejto frekvencie s rôznymi amplitúdami a počiatočnými fázami.
V diskrétnej doméne času (teda nespojitej, čo je náš prípad) sa využíva diskrétna Fourierova transformácia, ktorou možno dekomponovať vstupný signál na frekvenčné zložky. Tieto sú vyjadrené komplexnými číslami, ktoré zachytávajú nielen amplitúdu (veľkosť prvku), ale aj fázu vlnenia danej frekvencie (vyjadrenej ako arkus tangens podielu reálnej a imaginárnej zložky prvku) . (pričom podľa Eulerovej formuly eis=cos(s)+isin(s) ). Táto transformácia má zjavne výpočtovú náročnosť O(n2).
Rýchla Fourierova Transformácia (FFT)
Existuje však mnoho algoritmov patriacich do skupiny FFT (fast Fourier transform), ktoré ju redukujú na O(n log n). Vstup je v našom prípade podmnožinou oboru reálnych (nie komplexných) čísel. Pozornému čitateľovi preto neušlo, že najvyššia frekvencia skúmaná algoritmami FFT je zhodná s frekvenciou vzorkovania, teda dvojnásobne prekračuje Nyquistovu frekvenciu. Ak vieme, že v zdroji nie sú takéto vysoké frekvencie prítomné, dochádzame k záveru, že merané veličiny sú prejavom aliasingu. Inými slovami, aspoň polovica výsledných dát je (pre reálny vstup) redundantná.
Prečítajte si tiež: Blesková Večera
Diskrétna Kosínusová Transformácia (DCT)
Jedným so spôsobov, ako túto redundanciu odstrániť, je miesto sínusu a kosínusu (ktoré majú rovnaký tvar a líšia sa len fázou) pracovať len s jedným z nich, a to tiež v obore reálnych čísel (čím stratíme informáciu o fáze frekvenčných zložiek). Diskrétna kosínusová transformácia (DCT, angl. discrete cosine transform) je špeciálny prípad diskrétnej Fourierovej transformácie; keďže kosínus je párna funkcia, DCT je vhodné predovšetkým na frekvenčný rozklad párnych funkcií. Existuje niekoľko rozšírených druhov definícií DCT (najznámejšie sú označované DCT I, DCT II, DCT III, DCT IV). V kompresii obrazu je najpoužívanejšia DCT II (označovaná často len ako „DCT“), ktorej inverzná funkcia je DCT III prenásobená vhodným číslom (často len „IDCT“).
Modifikovaná Diskrétna Kosínusová Transformácia (MDCT)
Pri kompresii zvuku sa však viac osvedčila modifikovaná DCT (MDCT), založená na DCT IV. Tá funguje na princípe prekrývania okien (skúmaných blokov vzoriek) - každá vzorka patrí do dvoch okien, pričom druhá polovica predchádzajúceho okna sa prekrýva s prvou polovicou nasledujúceho okna. Počet koeficientov je však oproti veľkosti okná polovičná, čo toto zdvojnásobenie dát kompenzuje. V prípade IMDCT získame dva výsledky pre každú vzorku - tie jednoducho sčítame a získame želané xj. Táto technika prekrývania sa tiež nazýva TDAC (angl. time domain aliasing cancellation, teda anulovanie aliasingu v časovej doméne).
V praxi sa používa symetrický škálovací vektor (teda párna funkcia), ktorý sa líši od formátu k formátu. Nižšie uvedené príklady používajú formáty MP3 a MPEG-2 AAC (ai) a Vorbis (bi). AC-3 používa tzv. Kaiser-Besselovo derivované okno (s netriviálnym výpočtom), rovnako ho môže použiť i MPEG-4 AAC. Prvky výsledného vektora t získané z IMDCT (korešpondujúce s amplitúdami skúmaných frekvencií.
Kvantovanie a Psychoakustika
Treba si uvedomiť, že aj keď sú vstupné dáta ortogonálnych transformácií (v tomto prípade hovoríme najmä o MDCT) celočíselné, výsledné koeficienty budú vo všeobecnosti reálne. Ak teda chceme pracovať s frekvenčnými zložkami, musíme ich zaokrúhliť, kvantovať. Možnosť presnej rekonštrukcie pôvodných signálov teda nepripadá do úvahy. Koeficienty možno kvantovať s rôznou presnosťou, v závislosti od frekvencie, vzhľadom na psychoakustiku a želaný dátový tok. V praxi sa používa logaritmické kvantovanie - rozlíšenie hodnôt blízko malých čísel je presnejšie než v prípade vyšších hodnôt.
Statický Čas a Prekrývanie Okien
Ďalším aspektom je „statický čas“ riešenia. Zatiaľ sme hovorili o jednom spracúvanom bloku dát, problémom je však sekvenčnosť zvukových dát; tie vo všeobecnosti nevykazujú periodickosť zhodnú s veľkosťou bloku. Riešením je napr. prekrývanie okien, ako sme si ho spomenuli vyššie. Objavuje sa problém zachovania fázovej informácie (ktorá v koeficientoch nie je vyjadrená) - možnosťou je napr. stanoviť počiatočnú fázu v „čase 0“, zabezpečiac tak súvislosť fázy pri prechode oknami pre ľubovoľnú frekvenciu.
Prečítajte si tiež: Hrachová polievka: Recepty pre každodenné varenie
Veľkosť Okna a Frekvenčný Rozsah
Zvolenie veľkosti okna tiež nie je jednoduché. Malé okno znamená dobré rozlíšenie v čase (ľahko sa vyjadrí presný čas, kedy sa v zázname vyskytol daný zvuk), ale slabý frekvenčný rozsah (frekvencie s menšou vlnovou dĺžkou než veľkosť okna sa vo výpočte MDCT nezohľadňujú). Veľké okno naopak zvyšuje frekvenčný rozsah za cenu straty časovej informácie. Riešenia sú rôzne, napr. meniť adaptívne veľkosť okna vzhľadom na prevažujúce kmitočty, alebo rozdeliť frekvenčné pásmo na viac častí a každé spracúvať osve, s osobitnými veľkosťami okna. Výsledkom je lepšia presnosť výsledku vo frekvencii i čase, transformácia však ostáva naďalej silno stratová.
Zvlnenie a Predozvena
Medzi známe prejavy tejto stratovosti patrí jav nazývaný zvlnenie (angl. ringing). Frekvenčnou charakteristikou signálu s náhlou zmenou priebehu je impulz so širokým frekvenčným spektrom a amplitúdou. Pri spätnej rekonštrukcii z frekvenčných zložiek sa v signáli objavia predtým neprítomné zvlnenia pred a za impulzom (tzv. Gibbsov fenomén - znemožňuje napr. presnú rekonštrukciu štvorcovej vlny). Keďže okná pokrývajú istý časový úsek, frekvenčná dekompozícia a spätná kompozícia spôsobia utlmenie impulznej charakteristiky pôvodného signálu a jeho rozloženie na tento časový úsek.
Príbuzným negatívnym fenoménom je aj tzv. predozvena (angl. pre-echo). Tiež sa prejavuje pri výskyte signálu s vysokou energiou. Kodér, v snahe udržať vyrovnaný dátový tok, zväčša znižuje kvalitu kvantovania pre celý korešpondujúci rámec. Výsledkom je šum prítomný v celom rámci; signál s vysokou energiou, ktorý by ho maskoval, sa však objaví až od istého časového okamihu. Obe spomenuté deformácie teda vznikajú časovo pred i za impulzom - hovorí sa však len o „predozvene“. Dôvodom je nižšia citlivosť sluchu na skreslenie za hlasným zvukom (impulzom), tzv. dopredné maskovanie.
Subpásmové Kódovanie
Najväčší problém je náročnosť výpočtu ortogonálnych transformácií. Je vhodné počítať ich pomocou matíc (podobne ako pri kompresii obrazu), pri relevantných veľkostiach okien (napr. MP2 používa 512 vzoriek, čo je pri 44,1 kHz len 11,6 ms!) je to však veľmi náročné. Riešením môže byť subpásmové kódovanie. Pomocou vhodne zvolených digitálnych filtrov, zoskupených do tzv. banky filtrov, možno rozdeliť pôvodné skúmané okno na frekvenčné pásma (napr. 32 frekvenčných pásiem rovnomerne deliacich počuteľný frekvenčný rozsah zdroja - subpásmová analýza). Subpásma sú následne kriticky podvzorkované (ak je 32 subpásiem, tak faktorom 32 - pri veľkosti okna 512 vzoriek sa tak subpásmo podvzorkuje na 16 vzoriek), čo umožní odstrániť zbytočnú redundanciu: všetky pôvodné frekvencie v subpásme ostanú po podvzorkovaní zachované vďaka aliasingu, v nepárnych subpásmach však budú „prevrátené“ - najmenšia frekvencia sa stane najvyššou a naopak. Na subpásma, vďaka malej veľkosti, možno neskôr efektívne aplikovať ortogonálnu transformáciu.
Subpásmová analýza a syntéza (zloženie pôvodného zvuku zo subpásiem) vnáša do zvuku skreslenie spôsobené nedokonalosťou použitých filtrov. Navyše, rovnomerné rozdelenie frekvenčného rozsahu nekorešponduje s vnímaním frekvenčných rozdielov ľudským sluchom. Výhodou je možnosť osobitného spracovania signálu podľa jeho frekvenčných zložiek, a to bez transformácie z časovej do frekvenčnej domény. Najčastejšie používanými filtrami na subpásmovú dekompozíciu signálu sú kvadratúrny zrkadlový filter, deliaci frekvenčné spektrum pôvodného signálu na dva podvzorkované signály (kriticky, teda na polovicu, pričom v prvom subpásme sa nachádza nižšia polovica frekvenčného spektra, v druhom vyššia), a všeobecnejší polyfázový kvadratúrny filter, deliaci spektrum na niekoľko uniformne rozdelených subpásiem.
Prečítajte si tiež: Salkova Torta bez pečenia
Rozbor Rámca a Psychoakustický Model
Po frekvenčnej analýze nasleduje rozbor rámca. Identifikujú sa dominantné frekvenčné zložky, na základe psychoakustického modelu sa vytvorí krivka - prah maskovania (akoby maskovací signál prítomný v zázname) pre rôzne frekvencie. Frekvenčné zložky s intenzitami pod prahom maskovania (preto „nepočuteľné“, aspoň podľa rozhodnutia psychoakustického modelu toho-ktorého algoritmu) možno celkom zanedbať. Zložkám len mierne prekračujúcim prah maskovania (majú nízky odstup signálu od maskovacieho signálu - signal to mask ratio, SMR) možno priradiť nižšie rozlíšenie pri kvantovaní (snaha udržať nízky odstup šumu od maskovacieho signálu - noise to mask ratio, NMR). Prah maskovania z predošlého rámca sa po miernom utlmení zvykne použiť pri spracúvaní ďalšieho rámca, simulujúc tak časové maskovanie.
Kódovanie a Dátový Tok
Kvantované hodnoty sa kódujú vhodným kódovaním, od nízkych frekvencií k vysokým. Ak má byť želaný dátový tok nízky, zmenšuje sa presnosť kvantovania koeficientov, resp. postupne sa úplne potláčajú frekvencie na okraji psychoakustického pásma vnímania (najmä vysoké frekvencie). Niektoré formáty umožňujú umelo zvýšiť amplitúdu skupiny frekvenčných zložiek alebo subpásma - toto zhlasnenie (angl. gain) sa prenáša ako dodatočná informácia. Zvyšovať „kvalitu“ zaznamenaného zvuku zas možno presnejším kvantovaním koeficientov, použitím viacerých okien pre rôzne frekvenčné pásma, osobitným kódovaním jednotlivých kanálov atď. Treba si uvedomiť, že nemožno zvyšovaním dátového toku dosiahnuť bezstratovosť riešenia, aj keď, vzhľadom na návrh algoritmu, možno ľubovoľne zvyšovať psychoakustickú kvalitu, posluchovú „zhodnosť“ s originálom, tzv.
Aplikácia Ortogonálnych Transformácií
Medzi rôznymi ortogonálnymi transformáciami sa ujala predovšetkým DCT. Zvuk vo forme PCM (občas rozdelený na subpásma) je vstupným vektorom pre ortogonálnu transformáciu A. Na výstupné koeficienty sa aplikuje kvantovanie podľa potreby (na základe frekvenčnej a psychoakustickej analýza zvuku), výsledok sa zakóduje entropickým kódom a pošle na výstup.
Gapless Playback
S ortogonálnymi transformáciami a subpásmovým kódovaním úzko súvisí i tzv. gapless playback (dalo by sa preložiť ako súvislá, nepretržitá reprodukcia, záznam bez medzier). Veľkosť rámcov tej-ktorej kompresnej schémy nutne určuje najmenšiu časovú jednotku skomprimovaného záznamu. Riešením je doplnenie ticha („vypchatie“, angl. padding) na začiatku alebo konci zvukového záznamu, s cieľom dosiahnuť dĺžku deliteľnú veľkosťou rámca. Prehrávanie sledu záznamov, ktoré predtým tvorili súvislý celok (napr. skladby na niektorých CD).
Wavelety
Na dôvažok treba spomenúť, že zvuk sa „neodohráva“ len v časovej (PCM) alebo frekvenčnej doméne (MDCT), ale v oboch súčasne. Použitie okien znamená skombinovanie oboch domén. Svojou prirodzenosťou by však wavelety omnoho lepšie vystihovali charakteristiku skutočného signálu.
Vektorové Kvantovanie (VQ)
Najjednoduchším spôsobom zápisu vektorovej informácie je vymenovanie jednotlivých prvkov vektora. Ak je však signál zmysluplná informácia, obsahuje nejaké charakteristické prvky. V predošlom texte sme považovali signál za kompozíciu základných tónov, sinusoíd. Transformáciou sme získali súbor koeficientov, ktoré vyjadrovali „mieru“ zastúpenia tej-ktorej frekvenčnej zložky. Keďže sa pohybujeme v diskrétnej doméne, možno sa na jednotlivé frekvenčné zložky (sinusoidy) pozerať ako na vektory. Výsledný signál je kompozíciou týchto vektorov vynásobených príslušnými „mierami“ (koeficientmi).
Vo všeobecnosti sa na princíp VQ dá pozerať nasledovne: majme kódový slovník - súbor vektorov, ktorými aproximujeme vstupný vektor (signál). Rozmer vektorov je n, preto ich možno chápať ako body v n-rozmernom priestore. Skonštruujme Voronoiove diagramy z kódových vektorov. Vstupný vektor spadá do jedného z diagramov, prislúchajúceho konkrétnemu kódovému vektoru. Pri kompresii zvuku metódou VQ sa obyčajne tento postup aplikuje na vektor koeficientov, teda vyjadrenie signálu vo frekvenčnej doméne (kde je oproti časovej doméne signálu ľahšie badať štruktúru a korelovanosť). Z kódového slovníka sa vyberie vektor, ktorý najlepšie reprezentuje vektor koeficientov. Keďže slovník oproti pôvodnému vektorovému priestoru obsahuje len obmedzený počet vektorov (vďaka čomu nastáva samotná kompresia, teda úspora v popise pôvodných dát), vzniká skreslenie (akási forma kvantovacieho šumu) - reziduálny signál, teda rozdiel medzi vstupným vektorom a vybraným kódovým vektorom. V prípade potreby možno ďalším krokom (tzv.