Условие:
Закодируйте двоичным кодом Шеннона-Фано ансамбль сообщений Х = х1, х2,
..., х8, если все кодируемые сообщения равновероятны. Показать оптимальный характер
полученного кода.
Решение:
Найдем оптимальное двоичное кодирование ансамбля из 8 равновероятных сообщений методом Шеннона–Фано.
Шаг 1. Определим вероятности и энтропию. Все сообщения x₁, x₂, …, x₈ равновероятны, то есть для каждого p(xᵢ) = 1/8. Энтропия H(X) равна: H(X) = –Σ p(xᵢ) log₂ p(xᵢ) = –8 · (1/8) · log₂(1/8) = log₂ 8 = 3 бита.
Шаг 2. Определим оптимальную длину кодовых слов. Для оптимального префиксного кода кодовая длина lᵢ должна удовлетворять неравенству Крафта: Σ 2^(–lᵢ) ≤ 1. При равных вероятностях и равных оптимальных длинах lᵢ = L для всех сообщений получаем: 8 · 2^(–L) = 1 ⇒ 2^(–L) = 1/8 ⇒ L = ...