Descodificabilidad única

Question

Demostrar que el código C es unívocamente decodificable si la extensión $C^k(x_1,x_2,...,x_k)=C(x_1)C(x_2)...C(x_k)$ es una correspondencia unívoca entre $\mathcal{X}^k$ a $D^*$ para cada $k\geq1$ .

Sé que para que los códigos sean unívocamente decodificables deben ser representaciones uno a uno, pero creo que afirmarlo como prueba es demasiado simplista: tendría que demostrar que tiene que ser un mapeo uno a uno en lugar de basarme en esa definición. Y no puedo "demostrarlo" aquí, como podría hacerlo con los códigos de 2 bits de ejemplo.

Answer 1

CONSEJO: Si $C$ no es unívocamente decodificable, hay $k$ , $\ell$ , $\langle x_1,\ldots,x_k\rangle\in\mathscr{X}^k$ y $\langle y_1,\ldots,y_\ell\rangle\in\mathscr{X}^\ell$ tal que $\langle x_1,\ldots,x_k\rangle\ne\langle y_1,\ldots,y_\ell\rangle$ pero $C^k(x_1,\ldots,x_k)=C^\ell(y_1,\ldots,y_\ell)$ . Utilízalo para demostrar que $C^{k+\ell}$ no es uno a uno.

Answer 2

Brian ya ha dado la pista, intentaré darte alguna intuición. Porque, si el problema parece trivial, es que no lo has entendido del todo.

Sea $a,b,c \cdots...$ sean los símbolos de entrada. Sabemos que la extensión 1 es uno a uno, es decir $C(a) \ne C(b)$ (código no singular). Por supuesto, esto no es suficiente para garantizar la decodificabilidad única, ya que podría ocurrir, por ejemplo, que $C(ab)=C(de)$ .

Supongamos que sabemos que la extensión 2 es unívoca. Entonces, sabemos que $C(ab) \ne C(de)$ (y así sucesivamente, para cualquier par). Además, supongamos que también sabemos que la extensión 3 es unívoca. Entonces, sabemos que, digamos $C(abc) \ne C(def)$ (y así sucesivamente, para cualquier triple).

Ahora bien, cuidado: ¿basta con lo anterior para garantizar que el código es descodificable de forma única para extensiones de hasta 3? No. Porque podría ocurrir, por ejemplo, que $C(ab)=C(def)$

(Es esencial aquí entender esto: la propiedad "todas las extensiones 1,2,3 son uno a uno" no implican " $C(ab) \ne C(def)$ ")

Por ello, el requisito de tener todos Las extensiones uno a uno son (no trivialmente) necesarias para garantizar la descodificabilidad única.

¿Cómo sabemos, entonces, que algo como $C(ab)=C(def)$ ¿es imposible? No porque la extensión 2 sea uno a uno, no porque la extensión 3 sea uno a uno... ¡sino porque la extensión 5 lo es! Porque, suponiendo $C(ab)=C(def)$ tendríamos $C(ab|def)=C(def|ab)$ - lo cual es imposible.