Теория информации: энтропия и каналы связи

Энтропия и взаимная информация используют вероятностные модели стохастического анализа тридцать седьмой статьи.

Энтропия и неравенство Гиббса

Энтропия источника (H(X) = -sum p_i log p_i), максимум при равномерном распределении (H leq log |X|). Условная (H(Y|X) = -sum p(x,y) log p(y|x)), взаимная информация (I(X;Y) = H(X) - H(X|Y)). Неравенство Гиббса: (H(p) leq log n) для (n) исходов.

Энтропия как функция вероятностей с максимумом при равномерности . График показывает выпуклость.

Теорема Шеннона о кодировании источника

Префиксные коды Хаффмана достигают скорости (R geq H(X)), асимптотически (R o H(X)). Канальная ёмкость (C = max I(X;Y)), теорема Шеннона: надёжная передача при (R < C). Турбокоды и LDPC приближают предел Шеннона.

Теория кодирования содержится в пособиях МГУ https://math.msu.ru/sites/default/files/posobie_po_predelam.pdf. Лекции НГУ http://old.math.nsc.ru/~matanalyse/basic2.pdf.

Компрессия и алгоритмы

Арифметическое кодирование, LZW, Burrows-Wheeler для безпотерьной компрессии. JPEG, MP3 — с потерями, удаляя малозначимые коэффициенты вейвлетов тридцать первой статьи. Колмогоровская сложность как фундаментальный предел.

Кодовое дерево с префиксными кодами оптимальной длины (-log p_i) . Схема показывает эффективность.

Связь с машинным обучением

Кросс-энтропия как функция потерь, информационная бутылка для автоэнкодеров.

Рекомендуемые книги по теории информации

Полезны материалы https://mathprofi.com/knigi_i_kursy/files/predely_demo.pdf и анализ https://www.tstu.ru/book/elib2/pdf/2015/vasilev_2.pdf. Источники содержат кодирование.