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

Энтропия источника — это фундаментальная мера неопределённости (или информационной ёмкости) дискретного источника сообщений, определяющая среднее количество информации, приходящееся на один символ, генерируемый этим источником. Понятие введено Клодом Шенноном в 1948 году в работе «Математическая теория связи» и является центральным в теории информации. Энтропия источника характеризует степень непредсказуемости последовательности символов: чем выше энтропия, тем больше информации в среднем несёт каждый символ и тем труднее его предсказать.

Определение и математическая формулировка

Пусть дискретный источник без памяти генерирует последовательность символов из конечного алфавита \( X = \{x_1, x_2, \dots, x_n\} \), причём каждый символ \( x_i \) появляется с вероятностью \( p_i \), где \( \sum_{i=1}^{n} p_i = 1 \). Энтропия источника \( H(X) \) определяется по формуле:

\[ H(X) = -\sum_{i=1}^{n} p_i \log_2 p_i \]

Единицей измерения энтропии является бит (двоичная единица), если логарифм берётся по основанию 2. При использовании натурального логарифма единица называется нат, а при десятичном — дит (или хартли). Выбор основания соответствует количеству состояний, необходимых для кодирования одного символа: 1 бит позволяет различать два равновероятных исхода.

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

1. Неотрицательность: \( H(X) \geq 0 \). Равенство нулю достигается только в случае детерминированного источника, когда один из символов имеет вероятность 1, а все остальные — 0.
2. Максимальность: Для фиксированного числа символов \( n \) энтропия максимальна, когда все символы равновероятны: \( p_i = 1/n \). Тогда \( H_{\max} = \log_2 n \).
3. Аддитивность для независимых источников: Если два источника \( X \) и \( Y \) независимы, то энтропия их совместного распределения равна сумме энтропий: \( H(X, Y) = H(X) + H(Y) \).
4. Выпуклость: Энтропия является вогнутой функцией распределения вероятностей.

Энтропия для источников с памятью

Для реальных источников (например, текстов на естественном языке) символы не являются независимыми — вероятность появления следующего символа зависит от предыдущих. В таких случаях вводится понятие энтропии источника с памятью, или условной энтропии.

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

Пусть источник генерирует последовательность символов \( X_1, X_2, \dots, X_k \). Условная энтропия \( H(X_k | X_1, \dots, X_{k-1}) \) показывает среднюю неопределённость \( k \)-го символа при известных предыдущих. Для стационарного источника энтропия на символ в пределе при \( k \to \infty \) определяется как:

\[ H_{\infty} = \lim_{k \to \infty} \frac{1}{k} H(X_1, X_2, \dots, X_k) \]

Эта величина называется предельной энтропией источника и отражает истинную информационную ёмкость последовательности с учётом всех статистических зависимостей. Например, для русского языка предельная энтропия оценивается примерно в 1,0–1,5 бита на символ, в то время как энтропия равномерного распределения по 33 буквам составляет около 5,0 бит.

Энтропия и кодирование

Энтропия источника напрямую связана с минимальной средней длиной кодового слова при оптимальном кодировании. Согласно первой теореме Шеннона (теореме о кодировании источника без потерь), для дискретного источника без памяти существует такой префиксный код, что средняя длина кодового слова \( L \) удовлетворяет неравенству:

\[ H(X) \leq L < H(X) + 1 \]

Таким образом, энтропия задаёт нижнюю границу сжатия данных без потерь. Коды, достигающие этой границы (например, код Хаффмана или арифметическое кодирование), называются оптимальными.

Избыточность источника

Разность между максимально возможной энтропией (при равномерном распределении) и фактической энтропией источника называется избыточностью:

\[ R = \log_2 n - H(X) \]

Избыточность характеризует степень предсказуемости источника. Высокая избыточность (например, в текстах на естественном языке) позволяет эффективно сжимать данные и исправлять ошибки при передаче.

Примеры расчёта энтропии

Пример 1: Монета

Источник генерирует два символа: «орёл» (вероятность 0,5) и «решка» (вероятность 0,5). Энтропия: \[ H = - (0,5 \log_2 0,5 + 0,5 \log_2 0,5) = 1 \text{ бит} \]

Пример 2: Несимметричная монета

Вероятность «орла» — 0,9, «решки» — 0,1. Энтропия: \[ H = - (0,9 \log_2 0,9 + 0,1 \log_2 0,1) \approx 0,469 \text{ бит} \]

Пример 3: Равномерное распределение по 8 символам

\[ H = \log_2 8 = 3 \text{ бита} \]

Применение энтропии источника

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

Энтропия служит теоретическим пределом сжатия. Алгоритмы сжатия (ZIP, JPEG, MP3) стремятся минимизировать среднюю длину кода, приближаясь к энтропии источника. Например, в аудиокодировании MP3 используется психоакустическая модель, которая оценивает энтропию звукового сигнала с учётом восприятия человека.

Криптография

Энтропия источника используется для оценки стойкости генераторов случайных чисел. Высокая энтропия означает, что последовательность трудно предсказать, что критично для ключей шифрования. Низкая энтропия (например, в паролях, составленных из словарных слов) делает систему уязвимой к атакам перебором.

Теория связи

В системах передачи данных энтропия источника определяет минимальную пропускную способность канала, необходимую для безошибочной передачи информации. Совместно с пропускной способностью канала (вторая теорема Шеннона) энтропия позволяет оценить возможность надёжной связи при наличии шумов.

Лингвистика и анализ текстов

Энтропия естественных языков используется для оценки сложности текстов, сравнения языков, а также в задачах автоматического распознавания речи и машинного перевода. Например, энтропия английского языка оценивается в 1,0–1,5 бита на букву, а китайского (иероглифического) — около 3,0 бит на иероглиф.

Физика и статистическая механика

Понятие энтропии в теории информации тесно связано с энтропией Больцмана в термодинамике. В статистической механике энтропия системы определяется через логарифм числа микросостояний, что аналогично формуле Шеннона для равновероятных исходов.

Критика и ограничения

• Энтропия источника не учитывает семантику (смысл) сообщений. Два текста с одинаковой энтропией могут нести совершенно разную смысловую нагрузку.
• Для реальных источников с долговременными зависимостями (например, музыка или видео) точное вычисление предельной энтропии затруднительно и требует больших объёмов данных.
• Понятие энтропии применимо только к вероятностным моделям; для детерминированных последовательностей (например, цифровых сигналов с известным алгоритмом генерации) энтропия может быть нулевой, хотя они несут информацию.

Источники

• Шеннон К. Математическая теория связи // Работы по теории информации и кибернетике. — М.: ИЛ, 1963.
• Клод Э. Шеннон. Предсказание и энтропия печатного английского языка // Bell System Technical Journal, 1951.
• Томас М. Ковер, Джой А. Томас. Элементы теории информации. — М.: Мир, 2006.
• Роберт Галлагер. Теория информации и надёжная связь. — М.: Советское радио, 1974.