Código unívocamente descodificable

De Wikipedia, la enciclopedia libre

(Redirigido desde Códigos unívocamente decodificables)

Un código unívocamente descodificable es un tipo de código no-singular si cualquier secuencia finita de signos del alfabeto usado por el código es la imagen de como mucho un mensaje, es decir, la función de codificación E es una función inyectiva.

[editar] Definición formal

Código cuya extensión es no-singular. Sea A un alfabeto fuente y B un alfabeto código. Se llama función codificadora a cualquier función. f: A+ -> B+. El código correspondiente es Unívocamente Decodificable (UD) si f es inyectiva. Hace parte del área de la matemática discreta y los algoritmos computacionales.

Una forma de calcular la mejor longitud media es mediante la Inecuación de Kraft. La idea básica es asignar longitudes mayores a las palabras con menor probabilidad.

Para aclarar todo esto, debemos ir por pasos:

Un código es una asignación de palabras código $w_{i}$ , a una fuente de información ya sea de memoria nula o con memoria (fuente de Markov). Estas palabras código $w_{i}$ , no son más que combinaciones de símbolos de una alfabeto $T$ . Por ejemplo: si tenemos la siguiente fuente de memoria nula. $S = \{s_{1}, s_{2}, s_{3}\}$ y tenemos el siguiente alfabeto $T = \{0, 1\}$ , podemos asignar el siguiente código a $S$ , $C = \{0, 10, 11\}$ . Cuyo código es U.D.
Pero que quiere decir, con exactitud código Unívocamente Decodificable. Significa que cualquier codificación que se realice con ese código no debe ser ambigua es decir, un posible mensaje de la fuente $0100 \dots 11$ o cualquier otro, tenga una y solo una interpretación $s_{1} s_{2} s_{1} \dots s_{3}$ , es decir carezca de ambigüedad.
En efecto el Teorema de Patterson-Sardinas nos ayudan a verificar si un código es U.D. o no, pero aquí debemos notar que para demostrar que un código no es unívocamente decodificable, bastaría con encontrar una cadena que sea ambigua.