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

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

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

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

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

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

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

3038-kompresija-podataka