Cilj i ishod predmeta
Cilj predavanja i vežbi je da se steknu osnovna znanja i izuče tehnike za kompresiju podataka bez gubitaka podataka (lossless compression) i sa gubitkom dela podataka (lossy compression). Student poznaje vrste kompresije podataka i pojam funkcije oštećenja informacije. Zna algoritme nedestruktivne kompresije – adaptivni Hafmanov kod, Golombov kod, Rajsov kod, Tunstalov kod i aritmetičko kodovanje. Razume tehnike na bazi rečnika. Zna osnovne tehnike nedestruktivne kompresije – skalarnu i vektorsku kvantizaciju. Poznaje diferencijalo kodovanje i delta modulaciju.
Teorijska nastava
Tehnike kompresije. Modelovanje i kodovanje. Hafmanovi kodovi. Golombovi kodovi. Rajsovi kodovi. Tunstalovi kodovi. Aritmetičko kodovanje. Tehnike na bazi rečnika. Aplikacije: Unix compress, GIF, modemska kompresija v.42 bis. Prediktivno kodovanje. Dinamička Markovljeva kompresija. Kompresija sa gubicima. Kriterijumi distorzije. Skalarna kvantizacija. Uniformna kvantizacija. Adaptivna kvantizacija. Neuniformna kvantizacija. Entropijska kvantizacija. Vektorska kvantizacija. Linde-Buzo-Grej algoritam. Strukturirana vektorska kvantizacija. Diferencijalno kodovanje. DPCM. Delta modulacija. Kodovanje govora. Kodovanje slike. Kodovanje putem transformacije. Kvantizacija i kodovanje transformacionih koeficijenata. Primena na kompresiju slike – JPEG. Primena na kompresiju audio signala. Kodovanje u podopsegu. Primena na kodovanje govornog signala – G.726. Primena na kodovanje audio signala – MPEG audio. Primena na kompresiju slike. Wavelet kompresija. Šeme analize i sinteze. Video kompresija. Kompresija pokreta. Algoritmi za video konferencije i video telefone – H.264. Asimetrične aplikacije – MPEG (1, 2, 4 i 7).
Praktična nastava
Entropija diskretnih izvora bez memorije. Dijagram stanja, stacionarne verovatnoće stanja i simbola, trelis dijagram i entropija Markovljevih izvora. Osobine binarnih kodova. Statističko kodovanje. Adaptivni Hafmanov algoritam. Golombov kod i skraćeni Golombov kod. Tunstalov kod. Srednja dužina kodne reči i redudansa koda. Aritmetičko kodovanje i dekodovanje. Adaptivno aritmetičko kodovanje. Aritmetičko kodovanje/dekodovanje sa skaliranjem. Tehnike kodovanja na bazi rečnika. Lempel-Ziv 77 (LZ77), Lempel-Ziv 78 (LZ78) i Lempel-Ziv-Welch (LZW) algoritam. Skalarna kvantizacija, signal to quantization noise ratio (SQNR). Uniformni i neuniformni skalarni kvantizer. Mid-rise i mid-tread kvantizer. Optimalni kvantizer, Maks-Lojdov algoritam. Kvantizacija sa kompandovanjem. A- i μ-zakon kompandovanja. Vektorska kvantizacija, srednja kvadratna greška kvantizacije, rate kvantizera, Veronojeve oblasti. Diferencijalno kodovanje. Prediktor prvog reda, optimalni koeficijent predikcije, dobitak predikcije. Odnos PCM i DPCM, bit rate i QSNR. Delta modulacija, preopterećenje usled strmine.