Paper 2, Section II, I

Coding and Cryptography
Part II, 2014

Let c:A{0,1}c: \mathcal{A} \rightarrow\{0,1\}^{*} be a decodable binary code defined on a finite alphabet A\mathcal{A}. Let l(a)l(a) be the length of the code word c(a)c(a). Prove that

aA2l(a)1\sum_{a \in \mathcal{A}} 2^{-l(a)} \leqslant 1

Show that, for the decodable code c:A{0,1}c: \mathcal{A} \rightarrow\{0,1\}^{*} described above, there is a prefixfree code p:A{0,1}p: \mathcal{A} \rightarrow\{0,1\}^{*} with each code word p(a)p(a) having length l(a)l(a). [You may use, without proof, any standard results from the course.]