Código unívocamente descodificable


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 como mucho un mensaje, es decir, la función de codificación E es una función inyectiva.

Contenido

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 wi, a una fuente de información ya sea de memoria nula o con memoria (fuente de Markov). Estas palabras código wi, no son más que combinaciones de símbolos de una alfabeto T. Por ejemplo: si tenemos la siguiente fuente de memoria nula. S = {s1,s2,s3} 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


Wikimedia foundation. 2010.