Задание № 4 · ЕГЭ

Неравенство Крафта

Условие существования префиксного кода по длинам кодовых слов

2 мин чтенияСложность: Обновлено 29 сентября 2026

Неравенство Крафта позволяет проверить, могут ли заданные длины кодовых слов образовать префиксный код. Для двоичного кода сумма величин \(2^{-l_i}\) не должна превышать 1.

Неравенство КрафтаНазвано в честь Леона Крафта, сформулировавшего это условие.

Для префиксного кода над алфавитом из \(q\) символов с длинами кодовых слов \(l_1,l_2,\ldots,l_n\) выполняется условие \(\sum_{i=1}^{n}q^{-l_i}\le 1\). Более того, для заданных целых положительных длин это условие является не только необходимым, но и достаточным: если оно выполнено, префиксный код с такими длинами существует.

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

Формула

\[\sum_{i=1}^{n} q^{-l_i} \le 1\]

Здесь \(q\) — количество символов кодового алфавита, \(n\) — число кодовых слов, а \(l_i\) — длина \(i\)-го кодового слова. Для двоичного кода \(q=2\), поэтому каждое слово длины \(l\) занимает долю \(2^{-l}\) всех возможных бесконечных последовательностей.

№

Пример проверки

Пусть нужны три двоичных кодовых слова длины 1, 2 и 2. Проверим условие: \(2^{-1}+2^{-2}+2^{-2}=\frac{1}{2}+\frac{1}{4}+\frac{1}{4}=1\). Неравенство выполнено, значит, такой префиксный код существует. Например: 0, 10, 11.

Не путайте

Если сумма больше 1, префиксный код с такими длинами невозможен. Если сумма меньше либо равна 1, это не означает, что любая случайно выбранная таблица кодирования будет префиксной; условие говорит о существовании подходящей таблицы.

Проверь себя

Можно ли построить двоичный префиксный код с длинами 1, 2 и 3?

Главное за минуту

Главное

Для алфавита из \(q\) символов проверяют сумму \(\sum q^{-l_i}\).
Условие \(\sum q^{-l_i}\le1\) необходимо и достаточно для существования префиксного кода с заданными длинами.
Для двоичного кода используют степени двойки: \(2^{-l_i}\).