Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 3I / b / iii

Table of contents
- Solution iii

Solution

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.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version