Paper 1, Section I, H

Coding and Cryptography
Part II, 2010

Explain what is meant by saying that a binary code C\mathcal{C} is a decodable code with words CjC_{j} of length ljl_{j} for 1jn1 \leqslant j \leqslant n. Prove the MacMillan inequality which states that, for such a code,

j=1n2lj1\sum_{j=1}^{n} 2^{-l_{j}} \leqslant 1