Past exam of the information theory course of the University of Oxford / 2021 / 2 / b / i

Table of contents
- Solution i

Solution

Exchange the two complete codewords while leaving the code tree unchanged. The prefix code property is preserved because the set of codewords is unchanged. If

p_{i} > p_{j}

but

l_{i} > l_{j}

, the change in expected codeword length is

(p_{i} l_{j} + p_{j} l_{i}) - (p_{i} l_{i} + p_{j} l_{j}) = (p_{i} - p_{j}) (l_{j} - l_{i}) < 0,

contradicting optimality. Hence $p_{i} > p_{j}$ implies $l_{i} \leq l_{j}$ . This probability monotonicity of optimal prefix-code lengths is valid even if some probabilities are zero; equal probabilities impose no order.^[ref]

 Ancestors (12)

 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