Código unívocamente descodificable

Este artículo o sección tiene contenido demasiado complejo para lectores que no son expertos en el tema. Si puedes, por favor edítalo y contribuye a hacerlo más accesible para el público general, sin eliminar los detalles técnicos que interesan a los especialistas.

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.

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:

1. 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₁,s₂,s₃} 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.
2. 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.
3. 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.

Referencia

Notas

Bibliografía

• Dominic Welsh (1988): Codes and Cryptography, Clarendon Press, Oxford, ISBN 0-19-853287-3

Enlaces externos

• Códigos Unívocamente Decodificables - Una aplicación en línea que permite identificar un código unívocamente decodificable (UD) usando el teorema de Sardinas-Patterson