Рассчёт энтропии:
Пусть $p=\{0.5,0.25,0.25\}$. Энтропия Шеннона определяется как
$$H(X)=-\sum _i{p}_i{\log }_2{p}_i.$$ Подставляя значения,
$$H(X)=-(0.5{\log }_{2}0.5+0.25{\log }_{2}0.25+0.25{\log }_{2}0.25).$$ Так как ${\log }_{2}0.5=-1$ и ${\log }_{2}0.25=-2$,
$$0.5{\log }_{2}0.5=-0.5,0.25{\log }_{2}0.25=-0.5,$$ и
$$H(X)=-(-0.5-0.5-0.5)=1.5\text{бит/символ}.$$
Интерпретация и связь с сжатием:
- Энтропия $H(X)=1.5$ бита — это средняя минимальная неопределённость (количество информации) о символе источника в битах.
- Для безошибочного (без потерь) кодирования средняя длина кода на символ $L$ удовлетворяет оценке для префиксных кодов
$$H(X)\le L<H(X)+1.$$ - Если вероятности являются степенями $1/2$ (диадические), то можно достичь $L=H(X)$ с целочисленными длинами кода. В нашем случае распределение диадическое, поэтому оптимальный префиксный код даёт именно среднюю длину $1.5$ бита/символ.
Пример оптимального кода (например, Huffman):
- Символы: A с $p=0.5$, B с $p=0.25$, C с $p=0.25$.
- Один корректный оптимальный префиксный код: A → 0, B → 10, C → 11.
Средняя длина
$$L=0.5\cdot 1+0.25\cdot 2+0.25\cdot 2=1.5\text{бит/символ}=H(X).$$
Простой псевдокод (Python-подобный) для кодирования/декодирования:
Кодировщик:
```
code = {'A': '0', 'B': '10', 'C': '11'}
function encode(symbols):
bits = ""
for s in symbols:
bits += code[s]
return bits
```
Декодировщик (жадное префиксное чтение):
```
inverse = {'0':'A', '10':'B', '11':'C'}
function decode(bits):
out = []
i = 0
while i < len(bits):
# пробуем 1 бит, затем 2 бита (так как максимальная длина = 2)
if bits[i:i+1] in inverse:
out.append(inverse[bits[i:i+1]])
i += 1
else:
out.append(inverse[bits[i:i+2]])
i += 2
return out
```
Заключение: энтропия даёт фундаментальную нижнюю границу средней длины кода; для данного распределения можно достичь этой границы простым префиксным кодом.