2.I.4G

Coding and Cryptography
Part II, 2006

Let Σ1\Sigma_{1} and Σ2\Sigma_{2} be alphabets of sizes mm and aa. What does it mean to say that an aa-ary code f:Σ1Σ2f: \Sigma_{1} \rightarrow \Sigma_{2}^{*} is decipherable? Show that if ff is decipherable then the word lengths s1,,sms_{1}, \ldots, s_{m} satisfy

i=1masi1\sum_{i=1}^{m} a^{-s_{i}} \leqslant 1

Find a decipherable binary code consisting of codewords 011, 0111, 01111, 11111, and three further codewords of length 2. How do you know the example you have given is decipherable?