Shannon entropy

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 27 · page 27.3
Shannon entropy
H = -· pi·log2pi · properties · U-creative · Coding.
Shannon entropy
It generalizes Hartley's formula in case of uneven events and sets the theoretical minimum code length.
GEF
PIF
EEG No. 8.11
Relationship to Chapter 26.
Shannon Encoding Theorem: average length of optimal code (Huffman Algorithm)
Chapter 26
) aims to entropy H from the bottom.
01
Shannon formula
For a source with N symbols with probabilities p1, p2, ..., pn:
H = −Σ pᵢ · log₂(pᵢ) = Σ pᵢ · log₂(1/pᵢ)
Each folded:
pᵢ · log₂(1/pᵢ)
is the contribution of a symbol with pi probability. If pi = 0, folded to 0 (adopted by agreement: 0·log20 = 0).
Example of calculation
Three characters: p1 = 0.5, p2 = 0.3, p3 = 0.2
−0.5·log₂(0.5) = 0.5·1 = 0.5
−0.3·log₂(0.3) ≈ 0.3·1.737 ≈ 0.521
−0.2·log₂(0.2) ≈ 0.2·2.322 ≈ 0.464
H ≈ 0.5 + 0.521 + 0.464 =
1.485 bits
02
Entropy properties
H ≥ 0
- Entropy is always positive.
H = 0
- One of the outcomes is likely to be 1 (no uncertainty).
H = log₂N
- maximum for even distribution (all pi = 1/N).
H is monotonous
at a distance from uniform distribution.
H Additive:
for independent sources H(X.Y) = H(x) + H(Y).
03
Entropy calculator
📊
Calculate H(p1, p2, ...)
Probability through a gap (e.g.: 0.5 0.3 0.2)
Введите вероятности и нажмите «Рассчитать».
04
U-cry: H(p) for two events
For a source with two symbols (p and 1 to p):
H(p) = −p·log₂p − (1−p)·log₂(1−p)
Graph is a symmetrical bell-shaped curve with maximum
H = 1 bit at p = 0.5
and zeros at p = 0 and p = 1.
📈
U-crying: H(p) at two outcomes
p =
p = 0.50
H = 1.000
05
Communication with coding
Shannon's source coding theory:
The average length of the optimum code L should satisfy:
H ≤ L̄ < H + 1
This means that you can't squeeze data harder than the entropy of the source without loss -- H is the lower compression line.
Example: Symbols with different frequencies
Source: A 50%, B 25%, B 12.5%, G 12.5%
H = -(0.5·log₂0.5 + 0.25·log₂0.25 + 0.125·log₂0.125 + 0.125·log₂0.125) = 0.5 + 0.5 + 0.375 + 0.375 =
1.75 bits
Huffman code: A=0, B=10, B=110, G=111
1.75 bits
= H ✓
06
Game: balloons and information
🎱
How many balls are in the urn?
There's balls of different colours in the urn.
Welcome back
Every ball you deliver gives you information on Shannon. 95 percent of the information on the composition of the urn.
Press it.
Get the ball.
Balls removed:
Accumulated:
0%
07
Build Huffman's code.
🌳
Haffman Interactive Tree
The symbols are sorted by probability.
least
The knot is click on them. You'll see after you've finished the drawing of the tree with the codes.
08
Randomeiser to task H
🎲
Trainer: Calculate source entropy
Generates random tasks to calculate H using the Shannon formula.
Нажми «Новая задача» для начала.
🎯
Mini-test: 5 questions
XP: 0
🧩
Check yourself out.
5 questions on Shannon entropy · 20 XP for each correct answer