Компресија података

Циљ и исход предмета

Циљ предавања и вежби је да се стекну основна знања и изуче технике за компресију података без губитака података (lossless compression) и са губитком дела података (lossy compression). Студент познаје врсте компресије података и појам функције оштећења информације. Зна алгоритме недеструктивне компресије – адаптивни Huffman-ов код, Golomb-ов код, Rice-ов код, Tunstall-ов код и аритметичко кодовање. Разуме технике на бази речника. Зна основне технике недеструктивне компресије – скаларну и векторску квантизацију. Познаје диференцијало кодовање и делта модулацију.

Теоријска настава

Технике компресије. Моделовање и кодовање. Хафманови кодови. Golomb-ови кодови. Rice-ови кодови. Tunstall-ови кодови. Аритметичко кодовање. Технике на бази речника. Апликације: Unix compress, GIF, модемска компресија v.42 bis. Предиктивно кодовање. Динамичка Марковљева компресија. Компресија са губицима. Критеријуми дисторзије. Скаларна квантизација. Униформна квантизација. Адаптивна квантизација. Неуниформна квантизација. Ентропијска квантизација. Векторска квантизација. Linde-Buzo- Gray алгоритам. Структурирана векторска квантизација. Диференцијално кодовање. DPCM. Delta модулација. Кодовање говора. Кодовање слике. Кодовање путем трансформације. Квантизација и кодовање трансформационих коефицијената. Примена на компресију слике – JPEG. Примена на компресију audio сигнала. Кодовање у подопсегу. Примена на кодовање говорног сисгнала – G.726. Примена на кодовање аудио сигнала – MPEG аудио. Примена на компресију слике. Wavelet компресија. Шеме анализе и синтезе. Видео компресија. Компресија покрета. Алгоритми за видео конференције и видео телефоне – H.264. Асиметричне апликације – MPEG (1, 2, 4 и 7).

Практична настава

Ентропија дискретних извора без меморије. Дијаграм стања, стационарне вероватноће стања и симбола, трелис дијаграм и ентропија Марковљевих извора. Особине бинарних кодова. Статистичко кодовање. Адаптивни Хафманов алгоритам. Golomb-ов код и скраћени Golomb-ов код. Tunstall-ов код. Средња дужина кодне речи и редуданса кода. Аритметичко кодовање и декодовање. Адаптивно аритметичко кодовање. Аритметичко кодовање/декодовање са скалирањем. Технике кодовања на бази речника. Lempel-Ziv 77 (LZ77), Lempel-Ziv 78 (LZ78) и Lempel-Ziv-Welch (LZW) алгоритам. Скаларна квантиѕација, signal to quantization noise ratio (SQNR). Униформни и неуниформни скаларни квантизер. Mid-rise i mid-tread квантизер. Оптимални квантизер, Max-Lloyd-ов алгоритам. Квантизација са компандовањем. А- и μ-закон компандовања. Векторска квантизација, средња квадратна грешка квантизације, рате квантизера, Veronoi-еве области. Диференцијално кодовање. Предиктор првог реда, оптимални коефицијент предикције, добитак предикције. Однос PCM и DPCM, bit rate и QSNR. Делта модулација, преоптерећење услед стрмине.