← Назад к темам

Теория информации

Энтропия, кодирование, сжатие данных и информационная сложность

🌟 Введение в теорию информации

Теория информации — это математическая теория, изучающая передачу, обработку и хранение информации. Она была основана Клодом Шенноном в 1948 году и стала фундаментом для развития цифровых технологий.

Определение: Информация

Информация — это мера неопределенности или "сюрприза" в сообщении. Чем менее вероятно событие, тем больше информации оно несет.

История и мотивация

Представьте ситуацию: вы хотите передать сообщение через телеграф. Каждый символ стоит денег. Как минимизировать стоимость, не теряя информацию? Этот практический вопрос привел к рождению теории информации.

Пример: Интуитивное понимание информации

Рассмотрим два сообщения:

  • Сообщение A: "Завтра будет день" (очень вероятно)
  • Сообщение B: "Завтра упадет метеорит" (крайне маловероятно)

Какое сообщение несет больше информации? Очевидно, сообщение B, поскольку оно менее ожидаемо.

📊 Основные понятия

Количество информации

Определение: Количество информации

Количество информации в событии с вероятностью $p$ определяется как:

$$I(x) = -\log_2(p) = \log_2\left(\frac{1}{p}\right) \text{ бит}$$
Почему именно эта формула?
  1. Более редкие события должны нести больше информации
  2. Информация о независимых событиях должна складываться
  3. При $p = 1/2$ получаем 1 бит информации
Пример: Расчет количества информации
Подбрасываем честную монету. Вероятность выпадения орла: $p = 1/2$
Количество информации: $I = -\log_2(1/2) = \log_2(2) = 1$ бит
Подбрасываем честную игральную кость. Вероятность выпадения конкретного числа: $p = 1/6$
Количество информации: $I = -\log_2(1/6) = \log_2(6) \approx 2.58$ бит

🎲 Энтропия Шеннона

Определение: Энтропия

Энтропия — это мера неопределенности случайной величины, среднее количество информации, которое мы получаем при наблюдении исхода.

$$H(X) = -\sum_{i=1}^{n} p_i \log_2(p_i) \text{ бит}$$

где $p_i$ — вероятность $i$-го исхода.

Свойства энтропии

Основные свойства энтропии
  1. Неотрицательность: $H(X) \geq 0$
  2. Максимальность: $H(X) \leq \log_2(n)$, где n — число исходов
  3. Равномерное распределение максимально: $H(X) = \log_2(n)$ когда все $p_i = 1/n$
  4. Детерминированность: $H(X) = 0$ когда один исход имеет вероятность 1
Пример: Расчет энтропии для разных распределений

1. Честная монета

$p_1 = p_2 = 1/2$ (орел и решка равновероятны)
$H = -\frac{1}{2}\log_2\frac{1}{2} - \frac{1}{2}\log_2\frac{1}{2} = -\frac{1}{2}(-1) - \frac{1}{2}(-1) = 1$ бит

2. Нечестная монета

$p_1 = 0.9$, $p_2 = 0.1$ (орел выпадает в 90% случаев)
$H = -0.9\log_2(0.9) - 0.1\log_2(0.1)$
$H = -0.9(-0.152) - 0.1(-3.322) = 0.137 + 0.332 = 0.469$ бит

3. Игральная кость

Все грани равновероятны: $p_i = 1/6$ для $i = 1,2,3,4,5,6$
$H = -6 \cdot \frac{1}{6}\log_2\frac{1}{6} = -\log_2\frac{1}{6} = \log_2(6) \approx 2.58$ бит

Графическое представление энтропии

💾 Теория кодирования

Основы кодирования

Кодирование — это процесс преобразования информации в последовательность символов для эффективной передачи или хранения.

Определение: Код

Код — это правило соответствия между символами источника и кодовыми словами.

Длина кода — среднее количество символов, необходимых для кодирования сообщения.

Типы кодов

Тип кода Описание Пример Применение
Фиксированной длины Все символы кодируются словами одинаковой длины ASCII (8 бит на символ) Простота реализации
Переменной длины Частые символы — короткие коды, редкие — длинные Код Хаффмана Сжатие данных
Префиксный Ни одно кодовое слово не является префиксом другого Код Хаффмана Однозначное декодирование
Теорема Шеннона о источнике без помех

Для любого источника с энтропией $H$ существует код со средней длиной $L$, такой что:

$$H \leq L < H + 1$$

Это означает, что энтропия — это теоретический минимум средней длины кода.

Пример: Сравнение кодов

Пусть у нас есть алфавит {A, B, C, D} с вероятностями:

  • A: 0.5 (50%)
  • B: 0.25 (25%)
  • C: 0.125 (12.5%)
  • D: 0.125 (12.5%)

1. Код фиксированной длины

A = 00, B = 01, C = 10, D = 11 Средняя длина: 2 бита на символ

2. Оптимальный код (Хаффмана)

A = 0, B = 10, C = 110, D = 111 Средняя длина: 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 бита на символ

3. Энтропия источника

$H = -0.5\log_2(0.5) - 0.25\log_2(0.25) - 0.125\log_2(0.125) - 0.125\log_2(0.125)$
$H = -0.5(-1) - 0.25(-2) - 0.125(-3) - 0.125(-3) = 0.5 + 0.5 + 0.375 + 0.375 = 1.75$ бит
Вывод: Код Хаффмана достиг теоретического минимума! Это происходит, когда все вероятности являются степенями 1/2.

🎯 Практические задачи

Легкая
За какое минимальное число вопросов, на которые можно отвечать только «да» или «нет», можно угадать задуманное число от 1 до 100?
📝 Подробное решение
Стратегия: Используем бинарный поиск для минимизации количества вопросов.
Теоретический анализ: У нас есть 100 возможных чисел. Каждый вопрос "да/нет" может разделить множество максимум пополам.
Информационный подход: Чтобы различить 100 вариантов, нужно $\log_2(100) \approx 6.64$ бит информации.
Практическая стратегия: Каждый вопрос должен максимально делить оставшееся множество пополам.
Алгоритм бинарного поиска
Начальный диапазон: [1, 100] Вопрос 1: "Число ≤ 50?" - Да → [1, 50] - Нет → [51, 100] Вопрос 2: "Число ≤ 25?" (если да на 1) или "Число ≤ 75?" (если нет на 1) - продолжаем деление... Максимум вопросов: ⌈log₂(100)⌉ = 7
Ответ: За 7 вопросов можно гарантированно угадать любое число от 1 до 100.
Легкая
Среди 12 одинаковых по виду монет одна фальшивая (легче настоящих). За какое минимальное число взвешиваний на чашечных весах без гирь можно найти фальшивую монету?
📝 Подробное решение
Стратегия: Используем троичную логику — каждое взвешивание может дать 3 результата: левая чаша тяжелее, правая тяжелее, или равновесие.

Информационный анализ

У нас 12 монет, нужно найти 1 фальшивую. Это 12 возможных исходов.
Каждое взвешивание дает 3 возможных результата (тернарная информация).
Минимальное число взвешиваний: $\log_3(12) \approx 2.26$, округляем до 3.

Оптимальный алгоритм

Взвешивание 1: Разделим монеты на 3 группы по 4: A(1,2,3,4), B(5,6,7,8), C(9,10,11,12)
Взвешиваем A против B.
Случай 1 — Равновесие: Фальшивая в группе C.
Взвешивание 2: Берем 3 монеты из C и взвешиваем 2 против 2 настоящих.
Взвешивание 3: Если неравенство — фальшивая среди 2 легких. Если равенство — фальшивая оставшаяся.
Случай 2 — A легче B: Фальшивая в группе A.
Взвешивание 2: Из группы A взвешиваем монету 1 против монеты 2.
Взвешивание 3: Если неравенство — фальшивая легкая. Если равенство — фальшивая 3 или 4.

Дерево решений

Ответ: За 3 взвешивания можно гарантированно найти фальшивую монету среди 12.
Средняя
Докажите, что любой префиксный код имеет среднюю длину не меньше энтропии источника.
📝 Доказательство неравенства Крафта-Шеннона
Неравенство Крафта

Для префиксного кода с длинами кодовых слов $l_1, l_2, \ldots, l_n$ выполняется:

$$\sum_{i=1}^{n} 2^{-l_i} \leq 1$$

Доказательство основной теоремы

Дано: Источник с вероятностями $p_1, p_2, \ldots, p_n$ и префиксный код с длинами $l_1, l_2, \ldots, l_n$.
Цель: Доказать, что $L \geq H$, где $L = \sum p_i l_i$ и $H = -\sum p_i \log_2 p_i$.
Определим вспомогательные вероятности: $q_i = \frac{2^{-l_i}}{\sum_j 2^{-l_j}}$
Используем неравенство Йенсена для выпуклой функции $f(x) = x \log x$:
$$L - H = \sum p_i l_i + \sum p_i \log_2 p_i = \sum p_i \log_2 \frac{2^{l_i}}{p_i}$$
Перепишем через $q_i$: $L - H = \sum p_i \log_2 \frac{q_i \cdot C}{p_i}$, где $C = \sum 2^{-l_j}$
$L - H = \log_2 C + \sum p_i \log_2 \frac{q_i}{p_i}$
По неравенству Йенсена: $\sum p_i \log_2 \frac{q_i}{p_i} \geq 0$
Из неравенства Крафта: $C = \sum 2^{-l_i} \leq 1$, значит $\log_2 C \leq 0$
Для префиксного кода равенство в неравенстве Крафта, поэтому $C = 1$ и $L - H \geq 0$
Вывод: Энтропия источника является теоретическим пределом эффективности любого префиксного кода.
Сложная
Постройте код Хаффмана для источника с символами {A, B, C, D, E} и вероятностями {0.4, 0.2, 0.2, 0.1, 0.1}. Сравните его эффективность с теоретическим пределом.
📝 Построение кода Хаффмана

Шаг 1: Построение дерева Хаффмана

Начальное состояние: A(0.4), B(0.2), C(0.2), D(0.1), E(0.1)
Объединение 1: D(0.1) + E(0.1) = DE(0.2)
Состояние: A(0.4), B(0.2), C(0.2), DE(0.2)
Объединение 2: B(0.2) + C(0.2) = BC(0.4)
Состояние: A(0.4), DE(0.2), BC(0.4)
Объединение 3: DE(0.2) + BC(0.4) = DEBC(0.6)
Состояние: A(0.4), DEBC(0.6)
Объединение 4: A(0.4) + DEBC(0.6) = корень(1.0)

Дерево Хаффмана

Шаг 2: Получение кодов

Проходим от корня к листьям: - Левый путь: 0 - Правый путь: 1 A: 0 (длина 1) B: 100 (длина 3) C: 101 (длина 3) D: 110 (длина 3) E: 111 (длина 3)

Шаг 3: Анализ эффективности

Средняя длина кода:
$L = 0.4 \times 1 + 0.2 \times 3 + 0.2 \times 3 + 0.1 \times 3 + 0.1 \times 3$
$L = 0.4 + 0.6 + 0.6 + 0.3 + 0.3 = 2.2$ бита на символ
Энтропия источника:
$H = -0.4\log_2(0.4) - 0.2\log_2(0.2) - 0.2\log_2(0.2) - 0.1\log_2(0.1) - 0.1\log_2(0.1)$
$H = -0.4(-1.32) - 0.2(-2.32) - 0.2(-2.32) - 0.1(-3.32) - 0.1(-3.32)$
$H = 0.528 + 0.464 + 0.464 + 0.332 + 0.332 = 2.12$ бит
Эффективность: $\frac{H}{L} = \frac{2.12}{2.2} \approx 96.4\%$
Результат: Код Хаффмана достиг эффективности 96.4%, что очень близко к теоретическому пределу. Небольшая потеря связана с тем, что не все вероятности являются степенями 1/2.

🔬 Дополнительные темы

Взаимная информация

Определение: Взаимная информация

Взаимная информация между случайными величинами X и Y показывает, насколько знание одной переменной уменьшает неопределенность другой:

$$I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)$$

Условная энтропия

Определение: Условная энтропия

Условная энтропия $H(X|Y)$ — это средняя энтропия X при известном Y:

$$H(X|Y) = \sum_{y} p(y) H(X|Y=y) = -\sum_{x,y} p(x,y) \log_2 p(x|y)$$

Сжатие данных

Практическое применение: Алгоритмы сжатия
Алгоритм Принцип Сжатие Применение
Хаффман Переменная длина кода Без потерь Текстовые файлы
LZ77 Словарное сжатие Без потерь ZIP, GZIP
JPEG Дискретное косинусное преобразование С потерями Изображения
MP3 Психоакустическая модель С потерями Аудио

📡 Канал связи и передача информации

Определение: Канал связи

Канал связи — это среда для передачи информации от источника к получателю. Характеризуется пропускной способностью и уровнем шума.

Двоичный симметричный канал (BSC)

Простейшая модель канала с шумом, где каждый бит передается с вероятностью ошибки $p$.

Схема BSC

Вход: 0 ──→ [1-p] ──→ 0 :Выход └──→ [p] ────→ 1 :Выход Вход: 1 ──→ [p] ────→ 0 :Выход └──→ [1-p] ──→ 1 :Выход
Пропускная способность BSC

Пропускная способность двоичного симметричного канала с вероятностью ошибки $p$:

$$C = 1 - H(p) = 1 + p\log_2(p) + (1-p)\log_2(1-p)$$

где $H(p)$ — двоичная энтропийная функция.

Пример: Расчет пропускной способности
Случай 1: $p = 0$ (канал без шума)
$C = 1 - H(0) = 1 - 0 = 1$ бит на использование канала
Случай 2: $p = 0.1$ (10% ошибок)
$H(0.1) = -0.1\log_2(0.1) - 0.9\log_2(0.9) \approx 0.469$
$C = 1 - 0.469 = 0.531$ бит на использование
Случай 3: $p = 0.5$ (максимальный шум)
$C = 1 - H(0.5) = 1 - 1 = 0$ бит на использование

Теорема Шеннона о канале с шумом

Основная теорема теории информации

Для любого канала с пропускной способностью $C$ и любой скорости передачи $R < C$ существуют коды, позволяющие передавать информацию с произвольно малой вероятностью ошибки.

Если $R > C$, то надежная передача невозможна.

🛠️ Коды, исправляющие ошибки

Определение: Код, исправляющий ошибки

Код, исправляющий ошибки — это способ кодирования, который позволяет обнаруживать и исправлять ошибки, возникающие при передаче или хранении данных.

Расстояние Хэмминга

Определение: Расстояние Хэмминга

Расстояние Хэмминга между двумя строками одинаковой длины — это количество позиций, в которых соответствующие символы различны.

$$d_H(x,y) = |\{i : x_i \neq y_i\}|$$
Пример: Расстояния Хэмминга
  • $d_H(1001, 1010) = 2$ (различия в позициях 3 и 4)
  • $d_H(0000, 1111) = 4$ (различия во всех позициях)
  • $d_H(1010, 1010) = 0$ (строки идентичны)

Коды Хэмминга

Коды Хэмминга — это линейные коды, исправляющие одиночные ошибки.

Свойства кода Хэмминга
  • Параметры: Код Хэмминга $(2^r-1, 2^r-r-1, 3)$
  • Исправляет: 1 ошибку
  • Обнаруживает: 2 ошибки
  • Минимальное расстояние: $d_{min} = 3$
Пример: Код Хэмминга (7,4)

Построение кода

4 информационных бита: $d_1, d_2, d_3, d_4$
3 проверочных бита: $p_1, p_2, p_3$
Расположение: $p_1, p_2, d_1, p_3, d_2, d_3, d_4$

Проверочные соотношения

p₁ = d₁ ⊕ d₂ ⊕ d₄ p₂ = d₁ ⊕ d₃ ⊕ d₄ p₃ = d₂ ⊕ d₃ ⊕ d₄

Алгоритм исправления

Вычисляем синдром: $s_1 = p_1 \oplus d_1 \oplus d_2 \oplus d_4$
$s_2 = p_2 \oplus d_1 \oplus d_3 \oplus d_4$, $s_3 = p_3 \oplus d_2 \oplus d_3 \oplus d_4$
Позиция ошибки: $error\_pos = s_1 + 2s_2 + 4s_3$
Если $error\_pos = 0$ — ошибок нет, иначе исправляем бит в позиции $error\_pos$

🎲 Дополнительные задачи

Средняя
В урне 64 шара, из которых некоторое количество белых, остальные — черные. За какое минимальное число вопросов «да/нет» можно определить точное количество белых шаров?
📝 Подробное решение
Анализ задачи: Количество белых шаров может быть от 0 до 64, итого 65 различных значений.
Информационная оценка: Для различения 65 вариантов нужно $\lceil\log_2(65)\rceil = 7$ бит информации.
Стратегия: Используем бинарный поиск по количеству белых шаров.
Оптимальная стратегия:
Вопрос: "Количество белых шаров ≤ X?"
Начинаем с X = 32, затем делим диапазон пополам в зависимости от ответа.
Ответ: За 7 вопросов можно точно определить количество белых шаров.
Сложная
Докажите, что для исправления $t$ ошибок минимальное расстояние кода должно быть не менее $2t + 1$.
📝 Теорема о границе исправления ошибок
Граница Хэмминга

Для исправления $t$ ошибок необходимо $d_{min} \geq 2t + 1$

Доказательство

Предположение: Пусть код исправляет $t$ ошибок и имеет $d_{min} = 2t$.
Конструкция контрпримера: Возьмем два кодовых слова $c_1$ и $c_2$ с $d_H(c_1, c_2) = 2t$.
Создание неоднозначности: Рассмотрим слово $w$, находящееся на расстоянии $t$ от $c_1$ и $t$ от $c_2$.
Противоречие: Если в $c_1$ произошло $t$ ошибок, результат — $w$. Если в $c_2$ произошло $t$ ошибок, результат тоже $w$.
Вывод: Невозможно однозначно определить, какое слово было передано. Значит, $d_{min} \geq 2t + 1$.

Геометрическая интерпретация

Сферы исправления ошибок радиуса t вокруг кодовых слов не должны пересекаться: c₁ ●────t────●w●────t────● c₂ └─────── 2t ──────┘ Для непересечения нужно расстояние ≥ 2t + 1
Сложная
Сколько информации содержится в результате $n$ независимых подбрасываний нечестной монеты с вероятностью выпадения орла $p$?
📝 Информационное содержание последовательности

Теоретический анализ

Пространство исходов: Всего $2^n$ возможных последовательностей длины $n$.
Вероятность конкретной последовательности:
Для последовательности с $k$ орлами: $P = p^k(1-p)^{n-k}$
Информационное содержание: $I = -\log_2(P) = -k\log_2(p) - (n-k)\log_2(1-p)$

Среднее информационное содержание

Математическое ожидание числа орлов: $E[K] = np$
Средняя информация:
$E[I] = -E[K]\log_2(p) - (n-E[K])\log_2(1-p)$
$E[I] = -np\log_2(p) - n(1-p)\log_2(1-p) = n[-p\log_2(p) - (1-p)\log_2(1-p)]$
Окончательный результат: $E[I] = nH(p)$
$$\boxed{I_{среднее} = n \cdot H(p) = n[-p\log_2(p) - (1-p)\log_2(1-p)]}$$
Численный пример

Для честной монеты ($p = 0.5$) и $n = 100$ подбрасываний:

$I_{среднее} = 100 \cdot H(0.5) = 100 \cdot 1 = 100$ бит

Это означает, что результат содержит в среднем 100 бит информации.

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

🎯 Заключение

Теория информации — это фундаментальная область математики, которая:

Ключевые выводы:
  • Энтропия — универсальная мера неопределенности
  • Кодирование — способ эффективного представления информации
  • Сжатие — устранение избыточности в данных
  • Исправление ошибок — обеспечение надежности передачи
  • Пропускная способность — предел скорости передачи информации
Практические применения:
• Сжатие файлов (ZIP, JPEG, MP3)
• Передача данных (интернет, мобильная связь)
• Хранение информации (жесткие диски, CD/DVD)
• Криптография и защита информации
• Машинное обучение и искусственный интеллект