Teoría de códigos para niños
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
| 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 solo detectase que la información es incorrecta no serviría para nada. Es necesario algo más, un código no solo 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.
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 
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 
, siendo 
. Si 
es un alfabeto de D "letras", ¿qué código debe asignársele a la palabra 
usando "letras" del alfabeto de tal manera que se consiga una codificación tan económica como sea posible? Formalmente una codificación es una aplicación 
del conjunto de "palabras" en el conjunto de secuencias finitas de "letras" del alfabeto. Un mensaje es una secuencia finita de palabras, 
, si se dispone de una codificación de palabras, ésta se extiende inmediatamente a mensajes mediante concatenación:
Algunos tipos de codificaciones interesantes son:
- Una codificación es unívocamente descifrable si cualquier secuencia finita de
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 y
tal que 
es una secuencia inicial de 
.
Desigualdad de Kraft
Desigualdad de McMillan
Codificación criptográfica
La criptografía o codificación criptográfica es la práctica y el estudio de técnicas de comunicación segura en presencia de terceros (llamados adversarios). En términos más generales, se trata de construir y analizar protocolos que bloquean a los adversarios; diversos aspectos de la seguridad de la información, como la confidencialidad, la integridad de los datos, la autenticación y el no repudio son fundamentales para la criptografía moderna. La criptografía moderna existe en la intersección de las disciplinas de matemáticas, informática e ingeniería eléctrica. Las aplicaciones de la criptografía incluyen tarjetas de cajero automático, contraseñas de ordenador y comercio electrónico.
La criptografía antes de la era moderna era efectivamente sinónimo de cifrado, la conversión de información de un estado legible a aparentes nonsense. El autor de un mensaje cifrado compartió la técnica de decodificación necesaria para recuperar la información original solo con los destinatarios previstos, evitando así que personas no deseadas hicieran lo mismo. Desde la Primera Guerra Mundial y el advenimiento del ordenador, los métodos utilizados para llevar a cabo la criptología se han vuelto cada vez más complejos y su aplicación más extendida.
La criptografía moderna se basa en gran medida en la teoría matemática y la práctica informática; Los algoritmos criptográficos están diseñados en torno a suposiciones de dureza computacional, lo que hace que dichos algoritmos sean difíciles de romper en la práctica por parte de cualquier adversario. En teoría, es posible romper un sistema de este tipo, pero no es factible hacerlo por ningún medio práctico conocido. Por lo tanto, estos esquemas se denominan computacionalmente seguros; Los avances teóricos, por ejemplo, las mejoras en los algoritmos de factorización de enteros y la tecnología informática más rápida requieren que estas soluciones se adapten continuamente. Existen esquemas de seguridad teórica de la información que probablemente no se pueden descifrar ni siquiera con un poder de cómputo ilimitado; un ejemplo es la libreta de un solo uso, pero estos esquemas son más difíciles de implementar que los mejores mecanismos teóricamente rompibles pero computacionalmente seguros.
Véase también
En inglés: Coding theory Facts for Kids
