Výstupom všetkých algoritmov na kompresiu zvuku je tok dát (v angl. sa používa aj termín bitstream, teda tok binárnych čísel) podľa špecifikácie daného formátu, v ktorom sú zakódované informácie o prenášanom zvuku. Tieto informácie sú prevažne (no nielen) číselné. Dôvod je prostý – už digitalizácia zvuku, o ktorej sme hovorili v predošlej časti práce, je zároveň „kvantifikáciou“ zvuku, premenou vlastností zvuku (v tomto prípade zmeny tlaku vzduchu) na číselný zápis. (Inými slovami: zvuk sa z analógového zmenil na diskrétny, v časovej i hodnotovej doméne.) Kompresný algoritmus môže analyzovať digitalizovaný zvuk z viacerých hľadísk, no jeho výstupom (popri rôznych iných dátových položkách, určených na úspešnú dekompresiu) je v prvom rade sled čísel, vyjadrujúci vlastnosti zvukového signálu. Kódovanie, teda zápis týchto čísel, je často rozhodujúcim faktorom, vplývajúcim na efektívnosť formátu, a teda aj jeho úspešnosť na trhu.
Táto časť práce pozostáva zo štyroch odsekov. Najprv čitateľovi predstavíme problematiku symbolického zápisu dát vo všeobecnosti (3.2.1 Kompresia a kompakcia, redundancia a irelevancia), jadro potom budú tvoriť jednotlivé druhy kódovania, ktoré sú v súčasnom svete zvukových formátov hojne používané (3.2.2 Huffmanov kód, 3.2.3 Aritmetické kódovanie, 3.2.4 Modifikácie Huffmanovho a aritmetického kódovania).
Pod slovom kompresia budeme rozumieť postup transformácie súboru alebo toku dát do inej reprezentácie, ktorá je svojím objemom menšia ako pôvodná reprezentácia. (Podotýkame, že všetky dáta, o ktorých uvažujeme, sú v skutočnosti spracúvané a ukladané binárne, teda aj ich objem sa hodnotí ako veľkosť ich binárneho zápisu; ten sa v praxi realizuje skôr po osmiciach bitov, teda bajtoch. Pod pojmom reprezentácia myslíme skôr vnútornú štruktúru a význam týchto dát.) Platí, že z novej reprezentácie (skomprimovaných dát) možno pôvodné dáta, alebo ich aproximáciu, získať tiež nejakým algoritmom. Ak sme na základe návrhu kompresného algoritmu vždy schopní získať pôvodné dáta späť bez straty, hovoríme o bezstratovej kompresii (zvukových dát), alebo len o kompakcii. Ak dochádza k nejakej strate, ide o stratovú kompresiu (zvukových dát) (čo je pôvodný význam slova kompresia).
Inými slovami, kompresia funguje na základe redukcie redundancie (teda nadbytočných dát – nižšie popisujeme kódovú a medzisymbolovú redundanciu) a / alebo irelevancie (dát, ktoré sú z nejakých dôvodov považované za nepodstatné – nižšie hovoríme o tzv. psychoakustickej redundancii). Ak dochádza k redukcii irelevancie, ide o nevratný proces, teda stratovú kompresiu, ináč o kompresiu bezstratovú, vratný proces. Úspešnosť kompresie sa dá vyjadriť rôznymi spôsobmi, v tejto práci budeme používať skôr zápis jej neúspešnosti – pomeru veľkostí výstupného a vstupného súboru.
Pod kódovou redundanciou myslíme zápis dát, v ktorom je výskyt jednotlivých vstupných symbolov (zväčša uvažujeme o bajtoch alebo iných väčších informačných jednotkách) štatisticky nerovnomerne rozdelený, tzn. pravdepodobnosť výskytu niektorých symbolov je omnoho vyššia ako pre iné symboly. Riešením by bol algoritmus prevádzajúci vstupné symboly na kódové slová (tiež vyjadrené číselným zápisom) taký, že kódové slová prislúchajúce symbolom s malým výskytom v zdroji budú mať väčšiu dĺžku ako kódové slová prislúchajúce symbolom často používaným. To by prinieslo redukciu veľkosti zápisu dát. Toto kódovanie možno vyjadriť slovníkom, zoznamom kódových slov prislúchajúcich jednotlivým vstupným symbolom. Entropia (prvého rádu) je potom vyjadrenie neusporiadanosti systému, zároveň dolná hranica dĺžky binárneho zápisu. Vypočítame ju ako
kde P={p0, p1,... , pn−1} je rozdelenie pravdepodobností výskytu jednotlivých n symbolov v danom súbore dát (teda ich početnosť, ak ju poznáme). V nasledujúcich odsekoch si predstavíme niekoľko entropických kódov, teda kódov, ktoré využívajú kódovú redundanciu zdroja. Ide zároveň o kódy s variabilnou dĺžkou slova.
Pod medzisymbolovou redundanciou budeme rozumieť štatistickú závislosť dát. Prax ukazuje, že väčšina dát vykazuje nejakú štatistickú závislosť (korelovanosť) so sebou samým. Zvukové dáta nie sú výnimkou. V časti 2.3 sme hovorili o charakteristikách zvukov – tie sa prejavujú práve v korelovanosti. Ak znie vo zvukovom zázname napr. určitý tón, má graf zvuku nejaký charakteristický tvar, ktorý sa v čase opakuje. Pri kódovaní je dôležité popísať jestvujúcu korelovanosť a odstrániť ju zo zdroja, čím sa značne zredukuje množstvo redundantných dát. Presnejšie, definujme celkovú (binárnu) entropiu zdroja (v tomto prípade kanálu s pamäťou) ako limitnú hodnotu
Odstrániť korelovanosť (dekorelácia) znamená premeniť medzisymbolovú redundanciu na redundanciu kódovú (teda priblížiť entropiu prvého rádu celkovej entropii zdroja, ktorú znížiť nemožno)Pozn. 1. S tou sa potom možno vysporiadať entropickým kódovaním.
Pod psychoakustickou redundanciou chápeme prítomnosť dát, ktoré sú vzhľadom na používateľa (či už pre obmedzenie sluchu, alebo pre požiadavky kladené na reprodukciu) nepodstatné (irelevantné), resp. sú menej podstatné ako iné, dominantné. Stratová kompresia je vždy kompromisom medzi kvalitou a výslednou veľkosťou, predsa však existujú oprávnené prípady, kedy možno dáta redukovať (napr. frekvencie nad 20 kHz, alebo zbytočné 24-bitové kvantovanie vzoriek, keď je zvuk reprodukovaný malým reproduktorom na mobile atď.)
Poznámka 1: Zdroj: LIEBCHEN, Tilman. Realisierung einer verlustlosen Transformationscodierung zur Datenkompression von Mono- und Stereo-Audiosignalen. 1998. str. 4.
Entropické kódovanie, ktoré v r. 1952 navrhol Američan David A. HuffmanPozn. 1, sa stalo synonymom pre efektívny kód odstraňujúci redundanciu – v prípade kódovej redundancie je dokonca optimálny. Mnohé ďalšie formy kódovania, ktoré si predstavíme neskôr, z neho akýmsi spôsobom vychádzajú.
Proces kódovania prebieha v dvoch krokoch. Podľa možností sa vykoná prvý „prechod“ vstupnými dátami – zistenie početnosti vstupných symbolov. Následne sa zostaví tabuľka kódov (tzv. kódový strom). Všetkým vstupným symbolom sa na začiatku priradí „aktívny“ vrchol. Pre dva aktívne vrcholy s najmenšou frekvenciou (početnosťou, pravdepodobnosťou výskytu) sa vytvorí nový aktívny vrchol, s ktorým sa spoja; jeho frekvencia je rovná súčtu pôvodných vrcholov, teraz už vyradených zo zoznamu aktívnych vrcholov. Nový vrchol je stromom reprezentujúcim pôvodné dva vrcholy, pričom číslo 0 určuje prvý z nich, číslo 1 ten druhý. Znova sa vyberú dva aktívne vrcholy s najmenšou frekvenciou a postup sa opakuje, kým nevznikne jeden súvislý strom. Jediný aktívny vrchol je potom koreň, každý list je vrcholom vyjadrujúcim vstupný symbol, pričom kódové slovo, ktoré mu je priradené, je binárny zápis „cesty“ (sled núl a jednotiek – hodnoty bitov) od koreňa k nemu. Dá sa ukázať, že tento kód je úplný, tzn. pre ľubovoľnú postupnosť bitov (núl a jednotiek) je táto buď prefixom práve jedného kódového slova, alebo práve jedno kódové slovo je jej prefixom. (Alternatívou k postupu uvedenému v tomto odstavci je použiť statický kódový slovník – v tom prípade možno rovno pristúpiť k druhému kroku, no optimálnosť kódu závisí od zhody predpokladanej a skutočnej distribúcie vstupných symbolov.)
Druhým krokom je samotné kódovanie, realizované pri druhom „prechode“ dátami. Výsledkom kódovania je kódový slovník, teda tabuľka kódových slov priradených k vstupným symbolom (resp. frekvencie vstupných symbolov, z ktorých ju možno skonštruovať) a samotné zakódované dáta.
Dá sa ukázať, že priemerná dĺžka kódového slova výstupu (pri zachovaní rozdelenia pravdepodobností, na základe ktorej bola vypočítaná tabuľka kódu) je nanajvýš o jednotku horšia oproti binárnej entropii. Pri vyššej entropii zdroja je to veľmi dobrý výsledok, pri nízkej je to nebezpečné. Ako vidno, medzisymbolovú redundanciu Huffmanov kód vôbec nevyužíva. Pritom napr. celková binárna entropia zdroja (teda entropia, ktorá ráta aj s medzisymbolovou redundanciou) pre anglický jazyk je 1 bit na znakPozn. 2! Riešením oboch problémov by mohlo byť rozšírenie Huffmanovho kódu (združovanie vstupných symbolov), alebo použitie efektívnejšieho, napr. aritmetického kódovania.
Poznámka 1: Huffman, David A. A Method for the Construction of Minimum-Redundancy Codes. 1952.
Poznámka 2: SHANNON, Claude E. A mathematical theory of communication. Bell System Technical Journal 27. 1948. In MACKAY, D. J. C. Information Theory, … 2005. str. 113.
Toto kódovanie oddeľuje pravdepodobnostný model zdroja od samotného procesu kódovaniaPozn. 1. To nám umožňuje prejsť od statického riešenia k dynamickému (tiež „spätne adaptívnemu“) riešeniu (tzn. dáta stačí spracovať len raz – v jednom „prechode“ dochádza priamo ku kódovaniu; navyše, so zmenou rozdelenia pravdepodobnosti vstupných symbolov a zmenou medzisymbolovej redundancie sa menia aj kódové slová – rovnako na strane kodéra i dekodéra). Ďalším pozitívom je, že sa vstupným symbolom akoby prideľuje neceločíselný počet bitov kódového slova – vďaka tomu každý ďalší vstupný symbol môže predĺžiť výstup kodéra o menej než jeden bit.
Pre jednoduchosť si popíšeme len adaptívny model prvého rádu (tzn. model bez využitia medzisymbolovej redundancie). Na začiatku máme základné rozdelenie pravdepodobnosti vstupných symbolov P={p1, p2,... , pn−1} (môže byť napr. pi=1/n , alebo môže vychádzať z vlastností zdroja). Rozdelením intervalu #lt;a,b> budeme rozumieť lineárne zobrazenie intervalu I=<0, p0, p0+p1, ... , p0+p1+...+pn−1) na interval <a,b) . Nech je počiatočný interval <0,1) . Rozdelíme ho podľa distribúcie symbolov P. Kód vstupného symbolu pi vyjadruje obraz intervalu <p0+p1+...+pi−1, p0+p1+...+ pi−1+pi) (teda symbol p0 je vyjadrený obrazom intervalu <0,p0) , symbol p1 obrazom intervalu <p0,p0+p1) atď.). Po zakódovaní prvého vstupného symbolu získavame interval, ktorý opäť rozdelíme podľa distribúcie P. Keď dokončíme kódovanie vstupných dát, získavame dve reálne čísla – krajné hodnoty intervalu vyjadrujúceho zakódované dáta. Vstupné dáta teraz možno vyjadriť ako desatinný rozvoj reálneho čísla (ktoré je logicky v rozsahu <0,1) ) nachádzajúceho sa v tomto intervale. Distribúciu P následne aktualizujeme podľa spracovaných symbolov.
Tento popis je zjednodušený. Zdanlivo potrebuje nekonečnú presnosť počítania. V praxi sa však používajú rôzne metódy, ako aritmetické kódovanie realizovať pri obmedzených schopnostiach počítačov. Ráta sa len s istou presnosťou, pričom ak sú nejaké číslice (teda bity – binárny aritmetický kodér) výsledku (teda všetkých čísel v intervale) nemenné, tieto sa zapíšu na výstup, „zabudnú sa“ a miesto nich získavame nové bity na zvýšenie presnosti. Druhý problém je, že algoritmus by musel preniesť informáciu o počte zakódovaných symbolov (dekódovanie by ináč prebiehalo donekonečna). V praxi sa to skôr rieši dodaním symbolu
Spomínanými výhodami aritmetického kódovania sú vysoká úspešnosť a najmä dynamickosť, nevýhodou potom časová náročnosť a čiastočná patentovanosť v rámci USAPozn. 2. Ide o prúdové kódovanie, keďže je vhodné na kódovanie dát prichádzajúcich sekvenčne, v reálnom čase, na rozdiel od Huffmanovho kódu, ktorý potrebuje dva prechody, aby zostavil tabuľku vhodnú pre zdroj. Aritmetické kódovanie vďaka adaptívnosti žiadnu tabuľku prenášať nemusí.
Poznámka 1: OLEJÁR, D., STANEK, M. Úvod do teórie kódovania. 2006. str. 59 (kapitola 4.4). Alebo: MACKAY, D. J. C. Information Theory, … 2005. str. 111 (Chapter 6.2). Obe spomenuté kapitoly podrobnejšie rozoberajú konštrukciu aritmetických kódov.
Poznámka 2: Väčšinu patentov vlastní firma IBM. Pozri napr. http://en.wikipedia.org/wiki/Arithmetic_coding.
Kódovania spomenuté v predošlých dvoch odsekoch sú veľmi kvalitné, predsa však akýmsi spôsobom nepohodlné. V tomto odseku si predstavíme tri ich modifikácie alebo špeciálne prípady.
Začneme dynamickým (resp. adaptívnym) Huffmanovým kódom. Vysvetlime si však najprv tzv. súrodenecké kritérium: očíslujme vrcholy v binárnom strome kódovej tabuľky vzostupne zľava doprava, zdola (od najväčšej hĺbky) hore. Každý vrchol spomedzi vrcholov rovnakej hĺbky má číslo menšie než ľubovoľný vrchol o úroveň vyššie (väčšie než ľubovoľný vrchol o úroveň nižšie). Zároveň má každý rodič väčšie číslo než obaja jeho potomci. Ak platí, že s rastúcim číslom vrchola rastie aj frekvencia znaku, ktorý reprezentuje, tento binárny strom (vyjadrujúci kódový slovník) spĺňa súrodenecké kritérium. Princíp dynamického Huffmanovho kódu je nasledovný: Na začiatku je tabuľka prázdna a existuje spôsob dodávania nových symbolov. Prijatím už známeho znaku sa zvýši jeho frekvencia. Aktuálny kódový slovník sa mení priebežne pre každý prijatý symbol, nezostavuje sa však celý nanovo, ale v každom kroku sa len upraví tak, aby spĺňal súrodenecké kritérium. Odpadá tak potreba dvojnásobného prechodu zdroja (na zistenie frekvencie pred kódovaním) a prenosu tabuľky spolu so zakódovanými dátami. Efektívnosťou sa tento kód podobá aritmetickému kódovaniu.
Ďalšou spomenutou modifikáciou je rozsahové kódovanie (angl. range encoding), ktoré je len transformáciou aritmetického kódovania do sféry celých čísel. Miesto intervalu <0,1) sa používa interval medzi nulou a ohraničene „najväčším“ kladným číslom (binárne samé jednotky). Ako pribúdajú známe (nemenné) číslice na výstupe, rozširuje sa aj aktuálny rozsah dodaním ďalších číslic (analógia so zvyšovaním presnosti v aritmetickom kódovaní). Výhodami sú menšia výpočtová náročnosť a nezaťaženosť patentmi. Viac informácií možno nájsť v článku MARTIN, 1997.
Do tretice, Golombovo kódovanie nesie meno po svojom autorovi, známom americkom profesorovi Solomonovi Wolfovi Golombovi. Je určené na kódovanie zdrojov s malými kladnými (nenulovými) číslami, pričom s rastúcim číslom n klesá pravdepodobnosť jeho výskytu. (V ideálnom prípade ide o geometrické rozloženie – pravdepodobnosť výskytu čísla n je P(n)=(1−p)n−1p pre nejaké 0≤p≤1 .) Schéma používa nastaviteľný parameter b. Ak pravdepodobnosť vyšších čísel klesá rýchlo, b je nízke, ináč je vyššie. (Presnejšie: volí sa také b, aby (1−p)b+(1−p)b+1≤1<(1−p)b-1+(1−p)b.) Vypočíta sa q=floor((n−1)/b), r=n−qb−1 a c=floor(log2b). Kód čísla n je potom unárny zápis čísla q+1 (tzn. q binárnych jednotiek a jedna nula – bity s vyššou hodnotou), za ktorým nasleduje binárny zápis čísla r (bity s nižšou hodnotou). Číslo r je zapísané „orezaným binárnym kódovaním“, pri ktorom sa na prvých 2c+1−r hodnôt použijú c-bitové čísla (vzostupne od nuly), na zvyšné sa použijú c+1-bitové čísla. (Napr. pre b=5 a c=2 sú to postupnosti 00, 01, 10, 110, 111.) Ak chceme kódovať celé čísla, stačí vytvoriť ich bijektívne zobrazenie na množinu kladných čísel. Pôvodný autorov popis kódovania možno nájsť v článku GOLOMB, 1966Pozn. 1.
V prípade Golombových kódov takých, že b je mocnina dvojky, hovoríme o Riceovom kódovaní (resp. Golombove-Riceove kódy). Výhodou je ľahká implementovateľnosť v prostredí počítačov (miesto delenia a násobenia sa používajú binárne posuny).
Poznámka 1: Text je však zložitý a popretkávaný vtipným príbehom. Na internete možno nájsť aj jednoduchšie opisy (napr. http://urchin.earth.li/~twic/Golomb-Rice_Coding.html a i.).
