I want to examine the following encodings for letters $a,b,c,d$:
1) $C_1(a) = 10, C_1(b) = 00, C_1(c) = 11, C_1(d) = 110$.
2) $C_2(a) = 00, 1C_2(b) = 01, C_2(c) = 10, C_2(d) = 11$.
3) $C_3(a) = 001, C_3(b) = 01, C_3(c) = 101, C_3(d) = 111$.
For 1) I want to know whether this is uniquely decodeable and in my opinion it is because given any code string read from the beginning:
- if the first two bits are 10 or 00 it is $a$ or $b$.
- if the first two bits are 11 and the next is 1: the first symbol is $c$. if the first two bits are 11 and the next is 0: the first symbol is $d$ if the length of the 0-sequence which follows is odd or $c$ if it is even.
Are my thoughts enough to prove uniquely decodability?
For 2) I want to know whether it is prefix free. It is because no codeword is a prefix of another one. Can I say that for any encoding where the length of all codewords are equal, the code is prefix free?
For 3) I want to show that it is not postfix/sufffix free (because $C_3(b)$ is a postfix of $C_3(c)$ but it is prefix free. Additionally, if I referse all codes (so $C_3'(a) = 100, C_3'(b) = 10, C_3'(c) = 101, C_3'(d) = 111$) I get a code which is not prefix free but still uniquely decodable. How can I show that it is uniquely decodeable?
I'd say yes.
Yes, if you know that the code is nonsingular.
$C_3': a \to 100$, $b\to10$, $c\to101$, $d\to111$ is uniquely decodable because the reversed code ($C_3$) is prefix free (and hence uniquely decodable).
Supposed $C'_3$ is not uniquely decodable. Then there should exist a string of bits (received message) that correspond to two different original sequence of messages. But then, reversing all the bits, it would correspond to two different sequences of $C_3$. But this is impossible because $C_3$ is uniquely decodable.