Минимальная разрядность равномерного кода
Сколько бит нужно для равномерного кода всех символов алфавита?
2 в степени i ≥ N
- i
- наименьшая одинаковая длина двоичного кода символа, при которой 2 в степени i не меньше N, бит на символ
- N
- число разных символов алфавита; здесь N ≥ 2, символов
Двоичных слов длиной i ровно 2 в степени i. Для N разных символов нужны N различных слов одной длины; не обязательно использовать все возможные коды.
Пример: алфавит содержит 26 символов. Четырёх бит мало: 2⁴ = 16 < 26. Пяти достаточно: 2⁵ = 32 ≥ 26.
Ответ: минимально 5 бит на символ, при этом 32 − 26 = 6 кодов останутся свободными. Предполагается независимое посимвольное кодирование фиксированной длины без добавления проверочных бит.
Ловушка: равенство N = 2 в степени i требуется не всегда — кодов может быть больше, чем символов. Для неравномерного кода или хранения каждого символа в отдельном целом числе байтов расчёт другой.

