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?

Typos? Please submit corrections to this page on GitHub.