Unique Decodability

Question

Prove that code C is uniquely decodable if the extension $C^k(x_1,x_2,...,x_k)=C(x_1)C(x_2)...C(x_k)$ is a one-to-one mapping from $\mathcal{X}^k$ to $D^*$ for every $k\geq1$.

I know that for uniquely decodable codes, they must be one-to-one representations, but I think stating that as a proof is too simplistic—I'd expect I need to show that it has to be a one-to-one mapping rather than relying on such a definition. And I can't 'show' it here, as I could with example 2 bit codes.

Answer 1

HINT: If $C$ is not uniquely decodable, there are $k$, $\ell$, $\langle x_1,\ldots,x_k\rangle\in\mathscr{X}^k$, and $\langle y_1,\ldots,y_\ell\rangle\in\mathscr{X}^\ell$ such that $\langle x_1,\ldots,x_k\rangle\ne\langle y_1,\ldots,y_\ell\rangle$, but $C^k(x_1,\ldots,x_k)=C^\ell(y_1,\ldots,y_\ell)$. Use this to show that $C^{k+\ell}$ is not one-to-one.

Answer 2

Brian has already given the hint, I'll try to give you some intuition. Because, if the problem seems trivial, then you've not quite grasped it.

Let $a,b,c \cdots...$ be the input symbols. We know that the extension 1 is one-to-one, i.e. $C(a) \ne C(b)$ (non-singular code). Of course, this is not enough to guarantee unique-decodability, beacuse it could happen, for example that $C(ab)=C(de)$.

Suppose we know that the extension 2 is one-to-one. Then, we know that, say $C(ab) \ne C(de)$ (and so on, for any pair). Further, suppose we also know that the extension 3 is one-to-one. Then, we know that, say $C(abc) \ne C(def)$ (and so on, for any triple).

Now, be careful here: is the above enough to guarantee that the code is uniquely decodable for extensions up to 3? No! Because it could happen, for example, that $C(ab)=C(def)$

(It's essential here to understand this: the property "all extensions 1,2,3 are one to one" does not imply "$C(ab) \ne C(def)$")

This is why the requirement of having all extensions one-to-one is (non trivially) necessary to guarantee unique decodability.

How do we know, then, that something like $C(ab)=C(def)$ is impossible? Not because the extension 2 is one-to-one, not because the extension 3 is one-to-one ... but because the extension 5 is! Because, assuming $C(ab)=C(def)$, we'd have $C(ab|def)=C(def|ab)$ - which is impossible.