Cómo detectar y corregir errores (II)

Códigos eficientes y el problema del empaquetamiento de esferas.

Naranjas y teoría de la información: El diseño de códigos eficientes y robustos frente a errores de transmisión guarda relación con la manera más eficiente de empaquetar esferas. En 1611, Johannes Kepler conjeturó que la solución vendría dada por el método que emplean los fruteros para apilar naranjas. La demostración formal de la conjetura, sin embargo, tuvo que esperar hasta 1998. [©DGSTUDIODG/ISTOCKPHOTO]

En mi última columna [«Cómo detectar y corregir errores», por Alejandro Pérez Carballo; Investigación y Ciencia, junio de 2017] nos preguntábamos por códigos apropiados para enviar mensajes a través de un canal ruidoso; es decir, con posibles errores de transmisión. Vimos que tales códigos estaban sujetos a tres condiciones. En primer lugar, el receptor ha de poder saber si el mensaje se ha corrompido o no durante la transmisión. Segundo, en caso de que se hayan producido errores, el receptor tiene que poder reconstruir el mensaje original. Por último, nos gustaría que el código fuese lo más eficiente posible. Como vimos, la idea general consistía en introducir algún tipo de redundancia en el mensaje original; sin embargo, no queremos vernos obligados a emplear una gran cantidad de bits para comunicar un mensaje sencillo.

Recordemos algunas definiciones que introdujimos entones. Llamamos «secuencia corta» a cada mensaje inicial posible; en nuestro ejemplo, tales secuencias constaban de 4 bits. Un código de longitud k > 4 consiste en una función que, a cada secuencia corta, le asigna una de k bits. Por último, dada una secuencia de k bits cualquiera, diremos que es «limpia» si coincide con una de las que nuestro código asigna a las secuencias cortas. El problema con el que concluimos la columna anterior planteaba diseñar un código de longitud 7 que nos permitiese enviar mensajes de longitud 4 a lo largo de un canal de transmisión que, debido al ruido, puede alterar uno de los bits enviados.

Antes de analizar una solución, vale la pena tomar un pequeño desvío para observar un aspecto bastante curioso de nuestro problema.

Puedes obtener el artículo en...

¿Tienes acceso a la revista?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.

Responsable: Prensa Científica, S.A. Finalidad: enviarle por correo electrónico los boletines que haya solicitado recibir. Derechos: tiene derecho a acceder, rectificar y suprimir sus datos, así como a otros derechos, como se explica en la información adicional y detallada que puede consultar en nuestra Política de Privacidad.