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

Оптимальное кодирование

Как выбрать кодовые слова, чтобы средняя длина сообщения была минимальной
2 мин чтенияСложность: Обновлено 29 сентября 2026

Оптимальное кодирование — это выбор кодовых слов для символов сообщения так, чтобы при заданных вероятностях символов средняя длина закодированного сообщения была как можно меньше. Обычно рассматривают двоичные кодовые слова и кодирование без потерь: исходное сообщение должно однозначно восстанавливаться.

Оптимальное кодированиеСлово «оптимальный» означает «наилучший» по выбранному критерию; здесь критерий — минимальная средняя длина.
Способ построения кода переменной длины, при котором средняя длина кодового слова минимальна среди допустимых кодов для заданных вероятностей символов. Для однозначного декодирования часто используют префиксный код: ни одно кодовое слово не является началом другого.

Как вычисляют среднюю длину

Пусть символы \(a_1,a_2,\ldots,a_n\) имеют вероятности \(p_1,p_2,\ldots,p_n\), а длины их кодовых слов равны \(l_1,l_2,\ldots,l_n\). Средняя длина показывает, сколько двоичных разрядов в среднем приходится на один символ сообщения.

\[L=\sum_{i=1}^{n}p_i\cdot l_i\]

Нужно подобрать длины и сами кодовые слова так, чтобы \(L\) было минимальным и код можно было однозначно декодировать. Более вероятным символам обычно назначают короткие слова, а менее вероятным — длинные. При этом длины должны удовлетворять ограничению префиксного кода: \(\sum_{i=1}^{n}2^{-l_i}\le 1\).

№
Пример

Пусть символы имеют вероятности \(0{,}5\), \(0{,}25\) и \(0{,}25\). Код \(A=0\), \(B=10\), \(C=11\) даёт среднюю длину \(L=0{,}5\cdot1+0{,}25\cdot2+0{,}25\cdot2=1{,}5\) бита на символ. Если назначить короткое слово редкому символу, средняя длина обычно увеличится.

!
Не путайте

Оптимальный код не обязательно имеет одинаковую длину слов. Код фиксированной длины проще, но не использует различия в вероятностях символов. Кодирование Хаффмана — один из способов построить оптимальный префиксный код по известным вероятностям.

Проверка

Какой символ следует кодировать более коротким словом при прочих равных условиях?

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

Главное

  • Оптимальное кодирование минимизирует среднюю длину сообщения при заданных вероятностях.
  • Средняя длина вычисляется как \(L=\sum p_i\cdot l_i\).
  • Частым символам обычно назначают короткие кодовые слова, сохраняя возможность однозначного декодирования.