Pr3 Ej 5

Pr3 Ej 5

de Ignacio Faget -
Número de respuestas: 2

Buenas,

en este ejercicio te dice que se codifica en cadenas a partir de un alfabeto de salida de D símbolos de manera que su codificación es unívocamente decodificable.

Como te pide una cota, supongo que hay que usar el Teo. de Kraft. Pero Kraft te dice que, dado cualquier código que es instantáneo la cota vale. 

Mi duda es: este caso como puede saber que el código es instantáneo, porque que sea unívocamente decodificable no implica que sea instantáneo. Tampoco entiendo que implica que los S_i se codifiquen en cadenas, esto te esta diciendo que son de prefijo?

Saludos,

Ignacio
En respuesta a Ignacio Faget

Re: Pr3 Ej 5

de Maximo Pirri -
Hola Ignacio,
La idea del ejercicio es la que planteas, usar la desigualdad de Kraft. Sin embargo, no es necesario que el código se instantáneo para que se cumpla dicha desigualdad. Si bien todo código instantáneo la cumple, basta con que el código sea UD. En las diapositivas del teórico se muestra que los códigos UD la cumplen y la letra ya te afirma que el código del ejercicio es de este tipo.

Saludos.
En respuesta a Maximo Pirri

Re: Pr3 Ej 5

de Maria Simon -
Un comentario más, sobreentendido en lo que dice Máximo:
Se prueba que las longitudes de las palabras de un código UD cumplen la desigualdad de Kraft. Un código UD no es necesariamente instantáneo, pero dado un código UD, se puede hacer un código instantáneo con iguales longitudes de palabras. Es decir, la propiedad de ser instantáneo, que resulta ventajosa, es "gratis".