Количество информации при равновероятных событиях
Если событие может произойти одним из нескольких равновероятных способов, количество информации в сообщении о результате зависит только от числа возможных вариантов. Чем больше вариантов нужно различить, тем больше бит информации содержит сообщение.
Основная идея
Представим, что нужно узнать результат некоторого испытания. До получения сообщения возможны \(N\) вариантов, и каждый из них имеет одинаковую вероятность. Сообщение сообщает, какой именно вариант произошёл. В двоичной системе информация измеряется в битах, поэтому используется двоичный логарифм.
События или варианты называются равновероятными, если вероятность каждого из них одинакова. Если всего вариантов \(N\), то вероятность одного варианта равна \(\frac{1}{N}\).
Если сообщение выбирается из \(N\) равновероятных вариантов, то количество информации в сообщении равно двоичному логарифму числа вариантов.
Здесь \(I\) — количество информации в битах, а \(N\) — число равновероятных вариантов. Основание \(2\) означает, что информация измеряется в битах: один бит позволяет различить два равновероятных варианта.
Подробнее о смысле основания логарифма можно прочитать на странице «Двоичный логарифм». Формула количества информации является частным случаем общей формулы количества информации.
Почему появляется логарифм
Один вопрос с ответами «да» или «нет» делит множество вариантов примерно пополам и даёт \(1\) бит информации. Два независимых двоичных вопроса дают уже четыре возможных комбинации ответов: 00, 01, 10, 11. Значит, двумя битами можно различить \(4\) варианта.
Чтобы найти число бит \(I\), нужно решить это равенство относительно показателя степени. Поэтому получаем \(I=\log_2N\). Если число вариантов является степенью двойки, ответ можно найти устно: \(N=2^k\) означает \(I=k\) бит.
| Число вариантов \(N\) | Количество информации \(I\) |
|---|---|
| \(2\) | \(1\) бит |
| \(4=2^2\) | \(2\) бита |
| \(8=2^3\) | \(3\) бита |
| \(16=2^4\) | \(4\) бита |
| \(32=2^5\) | \(5\) бит |
| \(64=2^6\) | \(6\) бит |
Ищите ближайшую степень двойки. Например, \(N=32=2^5\), поэтому сообщение содержит \(5\) бит. Если \(N\) не является степенью двойки, используйте калькулятор или преобразование логарифмов.
Как решать задачи
- Определите, что именно считается вариантом: число граней, символов, результатов выбора или комбинаций.
- Проверьте, что варианты равновероятны. Если вероятности различаются, нужна другая формула.
- Найдите общее число вариантов \(N\).
- Подставьте \(N\) в формулу \(I=\log_2N\).
- Запишите единицу измерения — бит, если основание логарифма равно \(2\).
Монету подбрасывают три раза. Сколько информации содержит сообщение о последовательности результатов?
Ответ: сообщение о последовательности трёх бросков содержит \(3\) бита информации. Это также понятно без вычисления логарифма: каждый бросок даёт один двоичный результат, то есть один бит.
Составные выборы и кодирование
В задачах часто встречается не один выбор, а несколько последовательных действий. Если на первом шаге есть \(N_1\) вариантов, на втором — \(N_2\), а на третьем — \(N_3\), то общее число комбинаций при независимом выборе равно произведению:
Тогда количество информации можно вычислять так:
Например, пароль состоит из одной буквы русского алфавита, одной цифры и одного символа, причём вариантов соответственно \(33\), \(10\) и \(4\). Если все комбинации равновероятны, число паролей равно \(33\cdot10\cdot4=1320\), а количество информации в сообщении о выбранном пароле — \(\log_2 1320\approx10{,}37\) бита.
Сколько бит информации содержит сообщение о результате выбора одного из 16 равновероятных вариантов?
Если требуется закодировать один из \(N\) равновероятных вариантов двоичными кодами одинаковой длины, длина кода должна быть не меньше \(\log_2N\). При \(N=2^k\) достаточно ровно \(k\) бит. Общие принципы построения кодов разобраны на странице «Принципы кодирования информации», а таблицы соответствий — на странице «Построение таблицы кодирования».
Что делать, если число вариантов не является степенью двойки
Если \(N\) не равно степени двойки, значение \(\log_2N\) может быть дробным. Это нормально: формула показывает среднее теоретическое количество информации в сообщении. Однако обычный двоичный код фиксированной длины не может иметь дробное число бит на один вариант.
Например, для \(N=5\) получаем \(I=\log_2 5\approx2{,}32\) бита. Чтобы закодировать каждый из пяти вариантов одинаковым числом целых бит, понадобится \(3\) бита, поскольку \(2^2=4\) недостаточно, а \(2^3=8\) достаточно. Часть кодовых комбинаций останется неиспользованной.
Здесь \(k\) — минимальная длина фиксированного двоичного кода, а знак \(\lceil\ \rceil\) означает округление вверх. Не следует смешивать эту длину с количеством информации \(I\): для \(N=5\) они равны соответственно \(3\) бита и примерно \(2{,}32\) бита.
1. Используют \(\log_{10}\) вместо \(\log_2\). В задачах о битах основание равно \(2\). 2. Берут число элементов только одного выбора, забывая перемножить варианты нескольких независимых выборов. 3. Считают количество предметов, хотя нужно считать возможные комбинации. 4. Округляют \(\log_2N\) до ближайшего целого, хотя для фиксированного кода нужно округление вверх. 5. Применяют формулу \(I=\log_2N\) к неравновероятным событиям. Для них используется специальная формула, описанная на странице «Количество информации при неравновероятных событиях».
Единицы и связь с объёмом данных
В формуле \(I=\log_2N\) результат измеряется в битах. Восемь бит образуют один байт. Кратные единицы — килобайты, мегабайты и другие — применяются при измерении объёма файлов и сообщений. Это не следует путать с количеством информации одного события: «Объём информации» обычно рассматривает размер сообщения, файла или набора данных.
- \(1\) бит — информация о выборе одного из двух вариантов.
- \(1\) байт \(=8\) бит.
- Если вариантов стало в два раза больше, количество информации увеличилось на \(1\) бит.
- Если вариантов умножилось в \(k\) раз, добавка равна \(\log_2k\) бит.
Итоговая проверка
Главное
- Для \(N\) равновероятных вариантов количество информации равно \(I=\log_2N\) бит.
- Если \(N=2^k\), ответ сразу равен \(k\) битам.
- При нескольких независимых выборах общее число вариантов находят умножением.
- Для фиксированного двоичного кода минимальная длина равна \(\lceil\log_2N\rceil\).
- Формула применима только к равновероятным вариантам; при разных вероятностях используется другая модель.