Мощность алфавита

Как пользоваться формулой

1. Определите, сколько бит выделено на один символ.
2. Возведите 2 в эту степень.
3. Сравните результат с требуемым количеством символов.
4. Если алфавит больше результата, нужно увеличить число бит.

Историческая справка

Двоичное представление данных стало центральным для вычислительной техники XX века, но идея счета комбинаций из двух состояний старше компьютеров и относится к комбинаторике. Для i независимых двоичных выборов правило умножения дает 2^i вариантов.

В теории информации Клод Шеннон связал число возможных сообщений с логарифмической мерой информации. Если вариантов N и они различаются двоичными вопросами, количество бит связано с log2 N. Школьная формула N=2^i является обратной формой этой связи для равномерных кодов.

В практике программирования и хранения данных степени двойки стали естественными из-за двоичных разрядов памяти. Поэтому мощности 2, 4, 8, 16, 32, 64 и 256 часто встречаются в задачах о кодировках, цветах, адресах и наборах битов.

Пример

Задача. На кодирование одного символа отводится 6 бит. Сколько разных символов можно закодировать таким способом? Дано: i=6 бит. По формуле N=2^i получаем N=2^6=64. Значит кодовые слова длиной 6 бит дают 64 разных комбинации. Ответ: можно закодировать 64 символа. Проверка: каждый бит имеет 2 состояния, 0 или 1. Для 6 независимых позиций число наборов равно 2·2·2·2·2·2=64, что совпадает с формулой. Дополнительная проверка: 5 бит дали бы только 32 комбинации, а 6 бит дают 64. Значит при добавлении одного бита число кодируемых символов удваивается.

Частая ошибка

Часто вместо возведения в степень умножают 2 на i и получают 12 для 6 бит вместо 64. Вторая ошибка — путать N и i: мощность алфавита измеряется количеством символов, а i — битами на символ. Если N не является степенью двойки, минимальное i выбирают округлением log2 N вверх. Еще нельзя применять формулу к кодам переменной длины без дополнительных условий.