Teoría de códigos

Teoría de códigos

La teoría de códigos es una especialidad matemática que trata de las leyes de la codificación de la información. A grandes rasgos, codificar es transformar una información en una señal convenida para su comunicación. Decodificar sería el proceso inverso y complementario del anterior por el cual la señal comunicada es transformada en la información original. El auge de las comunicaciones a partir de la segunda mitad del siglo XX motivó un fuerte desarrollo de la teoría de códigos.

Contenido

Introducción e historia

Cronología[1]
Año Acontecimiento
55 a.C. Julio César, al invadir Gran Bretaña, utiliza
códigos para enviar mensajes a sus generales.
1750 d.C. Leonhard Euler sienta las bases de la criptografía
de clave pública con su teorema.
1844 Samuel Morse transmite su primer mensaje
utilizando su código.
Década
de 1920		 Se desarrolla la máquina Enigma.
1950 Richard Hamming publica un artículo fundamental
para crear códigos que detectan y corrigen errores.
Década
de 1970		 Desarrollo de la criptografía de clave pública.



Puesto que los códigos se usan para comunicar información, uno de los problemas a los que todo código se enfrenta es el error sistemático y, también, el fortuito. La redundancia es el único medio de prevenir el error. Los lenguajes humanos tienen una gran redundancia que les da flexibilidad a costa, eso sí, de eficacia. Los códigos matemáticos utilizan una redundancia más racional.

Hay códigos llamados de detección de errores, que permiten detectar alteraciones en un mensaje codificado. Se utilizan sobre todo en entornos donde el mensaje puede ser reenviado tantas veces como se necesite. Los protocolos de Internet, por ejemplo, están formados por un anidamiento de codificaciones desde el nivel de transporte hasta el nivel físico, teniendo cada nivel su propio sistema de detección de errores.

Este tipo de códigos resulta inadecuado en entornos donde la comunicación no se puede repetir y se necesita asegurar hasta cierto punto que se va a recibir la información correcta. Un ejemplo típico y vistoso es cuando se envía una nave espacial a los confines del sistema solar y desde allí debe enviar una serie de fotografías antes de que se le acaben, digamos, las pilas. Se trata de una situación delicada, porque si las ondas electromagnéticas que portan la información llegan distorsionadas toda la misión fracasa. Un código que sólo detectase que la información es incorrecta no serviría para nada. Es necesario algo más, un código no sólo detector sino corrector de errores.

Por ejemplo, el sistema de codificación más sencillo puede consistir en que un "0" se representa un "no" y con un "1" un sí. En este caso, si quiero transmitir un "si", y se comete un error al transmitir un "0" en vez del "1", el receptor del mensaje hará lo opuesto a lo pedido. Pero si en cambio se conviene que "00" sea "no" y "11" sea "sí", entonces, si se comete un error en un dígito, y por ejemplo el receptor recibe un "01", detectará que hubo un error, aunque no sabrá cual es el mensaje correcto. En cambio si la convención es que "000" es "no" y "111" un sí, y se supiese que al transmitir un mensaje solo es posible, por la metodología utilizada, cometer un solo error de dígito, entonces, si al recibir un "001", el receptor sabrá que se trata de un "no". Así siguiendo, si transmitimos un bloque de ceros, o un bloque de unos, aunque se cometan algunos errores en la transmisión de algunos dígitos, se tendrá la casi certeza de cual es el error cometido en el mensaje recibido, y corregirlo.[2]

En la actualidad, los avances que se están produciendo en esta disciplina están encaminados hacia la utilización de las bases de Groebner como herramienta para la codificación y decodificación en los códigos detectores de errores.

El problema de la codificación eficiente

Uno de los principales problemas de la teoría de códigos es el siguiente. Supongamos que tenemos una fuente de información que emite o transmite "símbolos" de cierto conjunto \scriptstyle W = \{w_1, \dots, w_n \} que por propósitos pedagógicos llamaremos simplemente "palabras", de forma que la probabilidad de emisión de una palabra sea independiente del símbolo anterior \scriptstyle P(w^{(t)}) = w_k|w^{(t-1)}=w_j) = P(w=w_k), siendo \scriptstyle p_i = P(w = w_i). Si \scriptstyle \Sigma es un alfabeto de D "letras", ¿qué código debe asignársele a la palabra \scriptstyle w_i usando "letras" del alfabeto de tal manera que se consiga una codificación tan económica como sea posible?[3] Formalmente una codificación es una aplicación \scriptstyle E:W \to \mathcal{P}_0(\Sigma) del conjunto de "palabras" en el conjunto de secuencias finitas de "letras" del alfabeto. Un mensaje es una secuencia finita de palabras, \scriptstyle m = w_{i_1}\dots w_{i_n}, si se dispone de una codificación de palabras, ésta se extiende inmediatamente a mensajes mediante concatenación:

E(m) = E(w_{i_1}) \dots E(w_{i_n})

Algunos tipos de codificaciones interesantes son:

  • Una codificación es unívocamente descifrable si cualquier secuencia finita de \scriptstyle \mathcal{P}_0(\Sigma) es la imagen de como mucho un mensaje, es decir, cuando la aplicación E es inyectiva.
  • Una codificación es instantáneamente descifrable, o de tipo prefijo, si no existen dos palabras diferentes \scriptstyle w_i y \scriptstyle w_j tal que \scriptstyle E(w_i) es una secuencia inicial de \scriptstyle E(w_j).

Desigualdad de Kraft

Artículo principal: Desigualdad de Kraft

Desigualdad de McMillan

Artículo principal: Desigualdad de McMillan

Teorema de codificación de Shannon

Referencias

Notas

  1. ↑ Basado en "50 cosas que hay que saber sobre matemáticas", de Tony Crilly. }}
  2. ↑ Ejemplo obtenido en el libro de "50 cosas que hay que saber sobre matemáticas", de Tony Crilly
  3. ↑ Dominic Welsh, 1988, p. 15

Bibliografía

Tony Crilly (2011). 50 cosas que hay que saber sobre matemáticas. Ed. Ariel. ISBN 978-987-1496-09-9. </ref>

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

Enlaces externos

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Teoría de códigos — es aquel estudio basado a partir de axiomas, Teoremas o Hipótesis matemáticas para obtener un resultado planteado al principio del problema. Son muchos los autores/as que han apostado sobre la Teoría de Códigos como explicación matemática del… …   Enciclopedia Universal

  • Códigos detectores y correctores de error — Los códigos detectores y correctores de error se refieren a los errores de transmisión en las líneas se deben a mucho a diversos factores, como el ruido térmico, ruido impulsivo y ruido de intermodulación. Dependiendo del medio de transmisión y… …   Wikipedia Español

  • Teoría de cuerpos — La teoría de cuerpos es una rama de la matemática que estudia las propiedades de los cuerpos. Un cuerpo es una entidad matemática para la cual la adición, sustracción, multiplicación y división están bien definidas. Contenido 1 Historia 2… …   Wikipedia Español

  • Teoría del delito — Saltar a navegación, búsqueda La teoría del delito es un sistema de categorización por niveles, conformado por el estudio de los presupuestos jurídico penales de carácter general que deben concurrir para establecer la existencia de un delito, es… …   Wikipedia Español

  • Teoría de la información — Este artículo está siendo desarrollado y forma parte de un proyecto educativo. Es posible que a causa de ello haya lagunas de contenido o deficiencias de formato. Si quieres puedes ayudar y editar, pero por favor antes de realizar correcciones… …   Wikipedia Español

  • Teoría jurídica del delito — Este artículo o sección sobre derecho necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 3 de abril de 2010. También puedes ayudar… …   Wikipedia Español

  • Teoría de la reproducción — Se ha sugerido que este artículo o sección sea fusionado con Teorías de la reproducción (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí …   Wikipedia Español

  • Teoría conspirativa — La exactitud de la información en este artículo o sección está discutida. En la página de discusión puedes consultar el debate al respecto …   Wikipedia Español

  • Códigos NRZ — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Códigos regionales DVD — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”