[Math] Uniquely Decodable and Instantaneous

information theory

Which of the following codes are (a) uniquely decodable? (b) instantaneous?

$C_1={00,01,0}$

$C_2={00,01,100,101,11}$

$C_3={0,10,110,1110,…}$

$C_4={0,00,000,0000}$

For part a, I think only $C_3$ is uniquely decodable, since combinations of the other codes could result in multiple answers. For part b, I also think $C_3$ is the only instantaneous code, since the prefix of each code is not shared by another.

Best Answer

Plainly $C_1$ and $C_4$ are not uniquely decodable (and hence not instantaneous), since in each of them $00$ is ambiguous between the single codeword $00$ and the sequence $0\mid 0$ of two codewords. Both $C_2$ and $C_3$ are instantaneous and therefore uniquely decodable. This is immediately clear in the case of $C_3$. As for $C_2$, $00$ is not a prefix of $01,100,101$, or $11$; $01$ is not a prefix of $00,100,101$, or $11$; $100$ is not a prefix of $00,01,101$, or $11$; $101$ is not a prefix of $00,01,100$, or $11$; and $11$ is not a prefix of $00,01,100$, or $101$.

Related Question