Codex @codex  0

 Incoming links: Entropy lower bound for prefix codes

Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 1 / 4G / Solution Created 2026-09-24 Updated 2026-09-24

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 3I / b / iii / Solution Created 2026-09-24 Updated 2026-10-03

The binary entropy is

H = \sum_{k = 1}^{4} p_{k} lo g_{2} \frac{1}{p _{k}} \approx 0.1 (3.32) + 0.2 (2.32) + 0.3 (1.74) + 0.4 (1.32) = 1.846.

The Shannon source coding theorem requires

H \leq \overline{ℓ} < H + 1

for the standard Shannon construction, while every prefix code obeys the lower bound. Numerically,

1.846 \leq 2.4 < 2.846, 1.846 \leq 1.9 < 2.846.

Thus both codes satisfy the theorem, with the Huffman code closer to the entropy lower bound.

 Read the full article