Paper 3, Section I, I

Coding and Cryptography | Part II, 2014

Let AA be a random variable that takes values in the finite alphabet A\mathcal{A}. Prove that there is a decodable binary code c:A{0,1}c: \mathcal{A} \rightarrow\{0,1\}^{*} that satisfies

H(A)E(l(A))H(A)+1H(A) \leqslant \mathbb{E}(l(A)) \leqslant H(A)+1

where l(a)l(a) is the length of the code word c(a)c(a) and H(A)H(A) is the entropy of AA.

Is it always possible to find such a code with E(l(A))=H(A)?\mathbb{E}(l(A))=H(A) ? Justify your answer.

Typos? Please submit corrections to this page on GitHub.