Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 224 / 2 / b

Table of contents
- Solution b

Solution

The code-distribution correspondence starts from the Kraft inequality. For codeword lengths

L (x)

put

K = \sum_{x} 2^{- L (x)} \leq 1, R (x) = \frac{2 ^{- L (x)}}{K} .

Conversely, a probability mass function determines ideal lengths

- lo g_{2} R (x)

, up to integer rounding. For the source law

P_{n}

,

E L (X_{1}^{n}) = - x \sum P_{n} (x) lo g_{2} {K R (x)} = H (P_{n}) + D (P_{n} ∥ R) - lo g_{2} K \geq H (X_{1}^{n}),

using nonnegativity of Kullback-Leibler divergence and

K \leq 1

.

 Ancestors (10)

 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