NeoFronteras

Los códigos de corrección de errores presentes en toda línea digital de comunicación moderna permiten usar Internet o un teléfono móvil con fiabilidad.

Claude Shannon. Fuente: Bell Labs.

Lo más probable es que usted, amigo lector, lea esto a través de la pantalla de su ordenador, pero para que lo pueda leer la información que constituye esta nota ha tenido que viajar un largo trecho. Primero desde un ordenador corriente a un servidor en Utah, y luego desde ese servidor hasta su ordenador (o eventualmente a cualquier otro del mundo). Parte del tramo ha sido por viejos cables de cobre telefónicos y parte por otras vías. Gracias a que la velocidad de transmisión es lo suficientemente alta usted puede ver esta página en una fracción de segundo y ver todas las fotos contenidas en ella en unos pocos segundos más. Pero para que eso sea posible ahora ha habido que recorrer un largo camino teórico. Detrás de ese click de ratón sobre un icono hay mucha tecnología y ciencia.
Hasta hace no tanto los usuarios de ordenadores se conectaban a otros ordenadores a través del módem. En los primeros años ochenta la velocidad de transmisión a través de esos dispositivos llegaba a un máximo de 9,6 kilobits por segundo. Si se intentaba transmitir a más velocidad aparecía un intolerable número de errores que destruían los datos.
Entonces, un grupo de ingenieros desarrollaron un sistema de corrección de errores que aumentó la velocidad de transmisión de los modems en un 25%. ¿Se podía aumentar aún más? Todos sabemos ahora que sí fue posible, pero los ingenieros que desarrollaron esos nuevos sistemas contaban con una ventaja: sabían el límite teórico máximo al que se podía transmitir información.
Al igual que un ingeniero industrial sabe que puede aumentar el rendimiento de una máquina térmica (un motor de gasolina por ejemplo) hasta el rendimiento teórico máximo alcanzado por una máquina de Carnot (maquina termodinámica conceptual diseñada en el siglo XIX), los ingenieros de comunicaciones conocían el límite de Shannon.
Claude Shannon publicó en 1948 un artículo que esencialmente creó la disciplina de la teoría de la información. Este trabajo es probablemente uno de los más brillantes trabajos científicos a los ojos de los que lo han leído.
Shanon, que trabajo en el MIT desde 1956 al 1978, demostró que un canal de comunicación cualquiera puede ser caracterizado por dos factores: el ancho de banda y el ruido. El ancho de banda es la gama de frecuencias (ópticas, electromagnéticas, eléctricas, etc) que pueden ser usadas para la transmisión de la señal, mientras que el ruido es cualquier cosa que afecta negativamente a esa señal.
Shannon mostró que, dado un canal con un particular ancho de banda y un ruido característico, se puede calcular la velocidad máxima a la que se puede enviar información sin sufrir errores. Llamó a esta velocidad o ritmo de transmisión “capacidad del canal”, pero se conoce ahora como límite de Shannon.
En un canal ruidoso la única manera de alcanzar cero errores es añadir cierta redundancia en la transmisión. Por ejemplo, si usted trata de transmitir un mensaje de tres bits, como 001, puede enviarlo tres veces: 001001001. Si hay un error y se recibe 001011001 en lugar de lo enviado entonces la persona que lo recibe puede estar segura de que lo correcto es 001.
Tal método de añadido de información extra a un mensaje para corregir los errores se denomina código de corrección de errores. Cuanto más ruidoso es el canal más necesidad hay de añadir información extra para compensar los errores. Pero según crece el código la transmisión se hace más lenta, pues se envían más bits de información. El código ideal minimiza el número extra de bits de corrección (con lo que aumenta la velocidad de transmisión de información útil) y maximiza la capacidad de corrección de errores.
Obviamente la estrategia de enviar un mensaje repetido tres veces es un código de corrección terrible. Con este método se disminuye el ritmo de transmisión de información útil a un tercio. Encima es todavía vulnerable a errores, pues si se dan dos errores simultáneos en los lugares adecuados no se puede recuperar el mensaje original.
Shannon creía que era posible construir códigos de corrección mejores. De hecho, fue capaz de demostrar que para un canal de comunicación cualquiera debe haber un código de corrección que permita la transmisión muy cerca del límite de Shannon.
En dicha demostración no se proporcionaba ninguna receta de cómo construir dicho código. En su lugar el trabajo descansaba en el cálculo de probabilidades. Si, por ejemplo, usted quiere enviar cuatro bits a través de un canal ruidoso entonces hay 16 posibles mensajes de cuatro bits. La demostración de Shannon asignaría a cada unos de esos posibles mensajes su propio código de corrección aleatorio.
Centrémonos en el caso en el caso para el cual el canal ruidoso requiera 8 bits para transmitir mensajes de 4 bits.
En este caso, el receptor, al igual que el emisor, tendrá un “libro de códigos” que correlacionará los 16 posibles mensajes de 4 bits con 16 códigos de 8 bits. Como hay 256 secuencias posibles de 8 bits hay, como mínimo, 240 que no aparecerán en el libro de códigos. Si el receptor recibe una de esas 240 secuencias sabrá que un error se ha introducido en el mensaje. Pero de los 16 códigos permitidos sólo habrá probablemente uno que encaje mejor con la secuencia recibida.
Shannon mostró que, estadísticamente, si se consideran todas las posibles asignaciones a los mensajes con códigos al azar, debe de haber uno que se aproxime al límite de Shannon. Cuanto más largo sea el código más cerca estará de ese límite. Un sistema de 8 bits para codificar mensajes de 4 bits no queda muy cerca de ese límite, pero un código de 2000 bits para un mensaje de 1000 bits sí que se aproxima bastante.
Obviamente el esquema de Shannon no es práctico, pues un libro de códigos que use un código asignado al azar para cualquier mensaje posible, de pongamos 1000 bits, sería enorme (no cabría en ningún disco duro del mundo). Pero la demostración de Shannon nos dice que siempre existe la posibilidad de que existan códigos que se acerquen al mencionado límite, aunque no los conozcamos.
La búsqueda de tales códigos duró hasta la década de los noventa, pero sólo porque el mejor código conocido, e inventado en el MIT, fue ignorado durante 30 años: el creado por Robert Gallager.

En 1993 Alain Glavieux y Claude Berrou de la École Nationale Supérieure des Télécommunications de Bretagne presentaron en un congreso una serie de códigos sobre los que afirmaban que estaban a mitad de camino del límite Shanon (todo un logro). Como no venían del campo de la Teoría de la Información y no tenían pruebas formales elegantes para defender tal afirmación, los asistentes casi se rieron de ellos en sus caras. Sin embargo, más tarde se demostró que tenían razón. A estos códigos se les llamó “turbo-códigos”.
Los turbo-códigos son iterativos y se basan en suponer cuál es el mensaje codificado. Cada suposición sucesiva se utiliza de semilla en el decodificador y como resultado se obtiene con el tiempo una propuesta cada vez más refinada. Idealmente, repitiendo el proceso una y otra vez, se puede conseguir que el error sea tan pequeño como se quiera.
Los buenos resultados obtenidos por los turbo-códigos hicieron que algunos científicos investigarán en el campo, descubriendo por el camino que un conjunto de códigos descubiertos en 1960 por Robert Gallager funcionaban tan bien como los turbo-códigos. Al parecer esos códigos tan buenos habían pasado desapercibidos hasta entonces.
Los códigos Gallaer usan lo que se llama bits de paridad, que son bits extras que contienen información acerca del mensaje. Un bit de paridad puede indicar, por ejemplo, si la suma de un triplete específico de bits de un mensaje es par o impar, el siguiente bit de paridad dice lo mismo sobre el siguiente triplete y así sucesivamente. Bajo este esquema, la información de dos bits del triplete expresa información relevante acerca del tercero. Iterativamente se pueden ir probando sucesivas suposiciones al mensaje que converjan a una que se aproxime todo lo que se quiera al mensaje original.
A día de hoy los códigos de Gallager son la mejor aproximación conocida al límite de Shannon para un canal de comunicación dado, incluso mejores que los turbo-códigos. Están integrados en las líneas de transmisión de datos. Incluso en cada ordenador o teléfono móvil actuales se pueden encontrar chips dedicados para decodificar códigos de Gallager. Mientras tanto Gallager, que no sospechó lo buenos que sus códigos podían ser, es todavía profesor emérito en el MIT.
Así que si ahora usted puede usar su teléfono celular o descargarse esta página web es porque antes, unos señores, con lápiz y papel, desarrollaron los trucos necesarios para que eso sea posible.

Copyleft: atribuir con enlace a http://neofronteras.com/?p=2984

Fuentes y referencias:
Nota sobre Shannon del MIT.
Nota sobre gallager del MIT.