Краткий ответ
\[ N = 2^{i} \]
\(N\) — сколько различных вариантов (символов, сообщений, кодов) можно закодировать, \(i\) — сколько бит (или знаков двоичного кода) на это уходит. Каждый новый бит удваивает число вариантов.
Что стоит за формулой
- \(i\) бит дают \(2 \cdot 2 \cdot \ldots \cdot 2 = 2^{i}\) разных комбинаций.
- 1 бит → 2 варианта (0 и 1);
- 2 бита → 4 варианта (00, 01, 10, 11);
- 3 бита → 8 вариантов;
- 8 бит (1 байт) → 256 вариантов.
Обратная задача (чаще всего и встречается): известно \(N\), нужно найти \(i\):
\[ i = \log_{2} N \]
Если \(N\) не является степенью двойки, берём ближайшую степень двойки сверху, то есть округляем вверх: кодов должно хватить на все варианты.
Пример с проверкой
В алфавите 30 символов. Сколько бит нужно на один символ?
Смотрим степени двойки: \(2^{4} = 16\) — мало, \(2^{5} = 32 \ge 30\) — хватает.
\[ i = 5 \text{ бит} \]
Проверка: 5 битами можно записать \(2^{5} = 32\) разных кода, а символов 30, значит, каждому достанется свой код, ещё 2 кода останутся лишними. Ответ согласуется.
Две типичные ловушки
- Нельзя писать \(i = \log_{2} 30 \approx 4{,}9\) и оставлять так — число бит целое, поэтому 5.
- Если \(N = 1\), то \(i = 0\): один вариант не требует информации вообще. Это редкий, но корректный случай.