DivulgaMAT
Inicio - DivulgaMAT Facebook - DivulgaMAT Twitter - DivulgaMAT

187. (Noviembre 2020) Códigos de Reed-Solomon
PDF Imprimir Correo electrónico
Escrito por Pedro Alegría (Universidad del País Vasco)   
Lunes 02 de Noviembre de 2020

Códigos de Reed-Solomon[Resultado de la corrección de errores en la imagen de la Mona Lisa mediante un código de Reed-Solomon, Wikipedia.]

Dentro de la especialidad matemática llamada Teoría de Códigos son importantes las técnicas de corrección de errores, que se utilizan de forma cotidiana en multitud de dispositivos digitales. Estamos muy familiarizados con los códigos que detectan errores, como la letra del DNI, los billetes de la zona euro, los pitidos que escuchamos en la zona de cajas del supermercado al pasar los códigos de barras por el lector óptico, los mensajes de error del cajero (o del ordenador (o del móvil)) cuando tecleamos la clave equivocada, etc., pero, lamentablemente —o por suerte—, estos códigos no son capaces de adivinar el valor correcto, no corrigen el error. Aunque no seamos conscientes de ello, los que sí son capaces de corregir errores se utilizan en el proceso de almacenamiento de datos en dispositivos como CDs, DVDs, lápices de memoria, etc., para que podamos recuperar los datos que contienen a pesar de tener algunas zonas defectuosas o degradadas.

Algunas de las técnicas sobre corrección de errores han sido objeto de varias aportaciones a la magia, aunque bajo la denominación de detección de mentiras lo que permite simular poderes adivinatorios por parte del artista. Ya se han desarrollado algunos ejemplos en este rincón: por ejemplo, los códigos de Hamming aparecieron en la transmisión telepática del número 80 (febrero de 2011), en el detector de mentiras del número 104 (abril de 2013) y en el juego del número 150 (junio de 2017); otros tipos de códigos aparecieron en el lápiz octal del número 128 (junio de 2015) o en el de adivinación que describimos en el número 163 (septiembre de 2018). También puedes encontrar información adicional sobre el uso de la magia en la teoría de códigos en el artículo «Códigos secretos y teoría de la información en la magia», publicado el año 2005 en el número 26 de la revista Sigma.

Siempre con el ánimo de facilitar la comprensión de los códigos correctores de errores, muchos docentes e investigadores sugieren enfoques desenfadados para el desarrollo de estos temas y a veces podemos encontrar juegos de magia como los ya mencionados. En esta ocasión nos referiremos a dos trabajos de Todd Mateer, profesor de matemáticas en Howard Community College (Maryland, EEUU). El primero de ellos, titulado «A magic trick based on the Hamming code» se publicó en noviembre de 2013 en la revista Math Horizons y, como su título indica, aprovecha los códigos de Hamming para diseñar un juego de magia similar al que describimos en el ya citado detector de mentiras del número 104 (abril de 2013) pero que puede realizarse sin apoyo de un programa informático. El segundo trabajo es el titulado «A Reed-Solomon code magic trick» y se publicó en abril de 2014 en la revista Mathematics Magazine. En el artículo se describen las características principales de los códigos correctores de errores de Reed- Solomon (llamados así en honor de sus creadores, Irving Reeds y Gustave Solomon), las cuales se aplican en un juego de magia que vamos a versionar a continuación.


Irving Reed y Gustave Solomon

Para este juego se necesitan 16 cartas, de modo que busca una baraja y quédate con las cuatro figuras —incluyendo el as— de cada palo. Sólo usaremos la jota (J), dama (Q), rey (K) y as (A) de los palos de picas (P), corazones (C), tréboles (T) y rombos (R). Utilizaremos como motivo alegórico la rosa de los vientos que, como sabes, es un símbolo inventado por el teólogo mallorquín Ramon Llull en el que están marcados los rumbos en que se divide la circunferencia del horizonte, aunque aquí nos limitaremos a los cuatro puntos cardinales, norte, sur, este y oeste.

Primera fase:

  1. Selecciona una de dichas cartas.

  2. Como verás, en las siguientes figuras se representan las rosas de los vientos en diferentes colores, azul y amarillo, y con las 16 cartas repartidas en los diferentes cuadrantes, cuatro de ellas apuntando al norte, cuatro al este, cuatro al sur y las otras cuatro al oeste. Busca la carta elegida en cada figura y anota el cuadrante en que se encuentra dicha carta.

  3. Ya puedo saber qué carta has elegido: se trata de la única carta que aparece repetida en los cuadrantes seleccionados. Para descubrirla fácilmente, gira cada círculo de modo que el cuadrante que contiene la carta elegida apunte hacia el norte.
    Por ejemplo, si has elegido la jota de picas (JP), verás que está situada al oeste en el círculo azul y al sur en el círculo amarillo. Si las giras como he indicado, las verás así:

    Se observa fácilmente que la JP es la única carta repetida entre las que están en el cuadrante superior.

Segunda fase:

Vamos a complicar un poco el proceso de adivinación de la carta elegida: vas a poder mentir una vez sobre la posición de la carta elegida. Como no será posible con las dos figuras anteriores, esta vez utilizaremos cuatro rosas de los vientos: además de la azul y amarilla, necesitaremos una roja y una verde, como las que aparecen a continuación.


  1. El proceso es el mismo de antes, así que debes elegir una carta entre las dieciséis seleccionadas y buscarla en cada uno de los cuatro círculos.

  2. A continuación, debes anotar las situaciones geográficas de la carta, pero puedes mentir en una de ellas, en la que quieras.
    Por ejemplo, supongamos que has apuntado: norte en la carta azul, oeste en la carta amarilla, norte en la carta roja y este en la carta verde.

  3. Pues bien, a pesar de la mentira, todavía puedo saber cuál es la carta elegida.
    En el caso del ejemplo propuesto, la carta elegida es el rey de corazones (KC) y la mentira se ha producido en el círculo azul.

La respuesta es similar al caso anterior. Basta colocar los cuatro círculos de modo que todas las orientaciones correspondientes al cuadrante elegido señalen hacia arriba. La carta que aparezca repetida al menos tres veces será la elegida. Además, el círculo en el que no aparezca dicha carta señalando en la misma dirección será en el que se ha mentido.

En el ejemplo propuesto, debemos disponer los cuatro círculos así:


Se comprueba fácilmente que el rey de corazones (KC) aparece en el cuadrante superior de los círculos amarillo, rojo y verde, pero no en el círculo azul. Si interpretamos el resultado según la teoría de códigos, hemos podido detectar el error (círculo azul) y corregirlo (se trata de la KC y debemos girar ese círculo de modo que el sur señale hacia arriba).

OBSERVACIONES FINALES:

  • En la página Fun with RS Codes se ofrece una lista de actividades divertidas utilizando los códigos de Reed-Solomon.

  • El artículo de Ricardo Teixeira titulado «Magical data restoration» y publicado en Math Horizons en febrero de 2017 contiene una nueva versión del juego de adivinación utilizando los códigos de Hamming.

Esta dirección electrónica esta protegida contra spambots. Es necesario activar Javascript para visualizarla
(Universidad del País Vasco - Euskal Herriko Unibertsitatea)

 

© Real Sociedad Matemática Española. Aviso legal. Desarrollo web