1) Энтропия источника H$X$

H = -∑ p$x$ log2 p$x$ = -$$0.5\cdot log20.5+0.3\cdot log20.3+0.2\cdot log20.2$$ = 0.5·1 + 0.3·1.7369656 + 0.2·2.3219281
≈ 0.5 + 0.5210897 + 0.4643856
≈ 1.4855 бит/символ.

$ОкруглённоH\approx 1.4855б/симв.$

2) Оптимальный префиксный код $Huffman$

Построим Хаффмана: объединяем наименьшие вероятности B$0.3$ и C$0.2$ → узел 0.5, затем с A$0.5$.
Код $одноизоптимальныхрешений$:
A → 0
B → 10
C → 11

Это префиксный код $ниодинкоднеявляетсяпрефиксомдругого$.

3) Средняя длина кода L

L = ∑ p$x$ · l$x$ = 0.5·1 + 0.3·2 + 0.2·2 = 0.5 + 0.6 + 0.4 = 1.5 бит/символ.

Избыточность: L − H ≈ 1.5 − 1.4855 = 0.0145 бит/символ $оченьмала$.

4) Связь с теоремой Шеннона о сжатии $безшумов$

Энтропия H — фундаментальный нижний предел средней длины кодирования: для любого $удаляемого$ префиксного или однозначно декодируемого кода справедливо L ≥ H $вбитах/символ$. Для кодов, кодирующих символы по одному, Хаффман даёт оптимальное целочисленное $длинавцелыхбитах$ решение, и выполняется неравенство
H ≤ L < H + 1.

Теорема о безошибочном кодировании $Shannon$: кодируя блоки длины n $тоестьгруппируяnсимволоввместе$ и используя оптимальные блоковые схемы или арифметическое кодирование, можно добиться средней длины на символ L_n/n, которая при n → ∞ приближается к H произвольно близко. То есть предел сжимаемости равен H: нельзя в среднем кодировать меньше чем H бит/символ, но можно приближаться к H сколь угодно близко, увеличивая блоки или применяя континуальные методы $арифметическоекодирование,энтропийныекодерысучётомисточника$.

Итого: для данного распределения H ≈ 1.4855 б/симв; оптимальный префиксный код $Хаффман$ даёт L = 1.5 б/симв, что почти достигает теоретического минимума H.