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.

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

• Teoría de la información