Is the product of uniquely decipherable codes uniquely decipherable?

469 Views Asked by At

A code $C$ is prefix-free if no codeword in $C$ is a prefix of another codeword in $C$. For example, $C=\{0,10,110\}$ is prefix-free but $D=\{0,10,100\}$ is not.

A code $C$ is uniquely decipherable if given any combination of codewords in $C$ there is a unique way to decipher it. For example, $C=\{0,011,101 \}$ is uniquely decipherable but $D=\{010,10,101\}$ is not.

The product of codes $C$ and $D$ is the set $C \times D = \{ cd : c \in C\ and\ d \in D \}$

It is also known that prefix-free implies uniquely decipherable, but the converse is false. I've proved that the product of prefix-free code is prefix-free, so it would imply that the product of prefix-free code is uniquely decipherable.

I'm pretty sure the answer to the question is no, but I still cannot find any counter-examples.

1

There are 1 best solutions below

0
On

Your hunch is right. Consider this case $A = {0, 10, 11}$ and $B = {1,00, 10}$ (B is the reverse of a prefix free) Now $A \times B = {01,000,010,101,111,1000,1010,1100,1110}$.

There should be easier ones as well but this is what I got,

01 010 101 01

010 1010 101