Código unívocamente descodificable

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, a lo sumo, 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 , a una fuente de información ya sea de memoria nula o con memoria (fuente de Markov). Estas palabras código , no son más que combinaciones de símbolos de un alfabeto . Por ejemplo: si tenemos la siguiente fuente de memoria nula. y tenemos el siguiente alfabeto , podemos asignar el siguiente código a , . 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 o cualquier otro, tenga una y solo una interpretación , 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.

Referencias

Bibliografía

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

Enlaces externos

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.