Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 3I (Coding and Cryptography)

Table of contents
- a 3I
  - Solution a
- b 3I
  - i b
    - Solution i
  - ii b
    - Solution ii
  - iii b
    - Solution iii

a

Solution

In Shannon-Fano coding, a symbol of probability

p_{i}

is assigned length

ℓ_{i} = ⌈ - lo g_{2} p_{i} ⌉,

and codewords of those lengths are chosen in lexicographic probability intervals; the Kraft inequality guarantees that a binary prefix code exists. Huffman coding repeatedly merges the two least probable current symbols, builds a binary tree from the resulting merges, and labels its two branches by zero and one. Reading from the root to each leaf gives an optimal prefix code.

b

i

Solution

The Shannon-Fano lengths are

(ℓ_{1}, ℓ_{2}, ℓ_{3}, ℓ_{4}) = (4, 3, 2, 2) .

One corresponding prefix-free assignment is

1 \mapsto 1010, 2 \mapsto 100, 3 \mapsto 00, 4 \mapsto 01 .

Its expected word length is

\overline{ℓ}_{SF} = \frac{1}{10} 4 + \frac{2}{10} 3 + \frac{3}{10} 2 + \frac{4}{10} 2 = 2.4 .

ii

Solution

The Huffman coding merges are

\frac{1}{10} + \frac{2}{10} = \frac{3}{10}, \frac{3}{10} + \frac{3}{10} = \frac{6}{10}, \frac{4}{10} + \frac{6}{10} = 1.

For example, the resulting code may be

1 \mapsto 110, 2 \mapsto 111, 3 \mapsto 10, 4 \mapsto 0 .

Its expected length is

\overline{ℓ}_{H} = \frac{1}{10} 3 + \frac{2}{10} 3 + \frac{3}{10} 2 + \frac{4}{10} 1 = 1.9 .

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 (9)

 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