CODIGO DE REED-SOLOMON

 Reed-Solomon  es un código cíclico no binario. Los códigos cíclicos son una subclase de los  códigos de bloque  estándar de  detección y corrección de errores  que protege la  información  contra errores en los datos transmitidos sobre un canal de comunicaciones. Este tipo de código pertenece a la categoría  FEC  ( Corrección de errores de reenvío ), es decir, corrige los datos alterados en el receptor y para ello utiliza unos  bits  adicionales que permiten esta recuperación a posteriori.

Este código debe su nombre a  Irving S. Reed  y  Gustave Solomon , quienes lo crearon en los años ´60. Este código se encuentra actualmente aplicado en áreas como los  CD ,  telefonía móvil  y  sondas espaciales   (la sonda  Galileo  a  Júpiter  en  1989 , la sonda  Magallanes  a  Venus  ese mismo año o la sonda  Ulises  al  Sol  en  1990 , por citar algunos ejemplos).También es de destacar el empleo del código Reed-Solomon en las comunicaciones por satélite  Digital Video Broadcasting (DVB) , en la transmisión digital de televisión  ISDB-T , en la radio digital  DAB+ , así como en los sistemas  xDSL  de comunicación por cable, y en los códigos QR.

En el mural se ve un ejemplo muy sencillo, donde se quiere transmitir un mensaje del alfabeto A={0,1,2,3,4}, que tenga longitud 3, en este caso el mensaje a transmitir es 102. Primero se codifica el mensaje asociándole un polinomio de grado dos, con coeficientes en A, de la siguiente manera: p(x)=1.x^2+0.x+2 y luego se calcula los restos de dividir por 5 al polinomio evaluado en cada uno de los elementos de A: 

p(0)=2=5.0+2

p(1)=3=5.0+3

p(2)=6=5.1+1

p(3)=11=5.2+1

p(4)=18=5.3+3

Entonces el mensaje codificado es 23113. Este mensaje tiene datos sobre el mensaje enviado, que permite reconstruirlo a pesar de que se pierda algún dígito en la transmisión, o de que haya algún error al ser transmitido.

 

¿QUÉ SUCEDE SI SE PIERDE INFORMACIÓN?

 

Supongamos que el mensaje recibido es el siguiente: 23??3. Como ya sabemos que proviene de un polinomio de la forma p(x)=ax^2+b.x+c, dónde a,b,c son elementos de A y verifican que 

p(0)=c tiene resto 2 en la división por 5, entonces c=2.

p(1)=a+b+2 tiene resto 3 en la división por 5, entonces a+b tiene resto 1 en la división por 5.

p(4)=16.a+4.b+2=15.a+a+b+3.b+2 tiene resto 3 en la división por 5, entonces (como a+b tiene resto 1), b tiene resto 0 en la división por 5, por lo tanto b=0 ya=1.

De esta forma, recuperamos el polinomio p(x)=1.x^2+0.x+2 y entonces podemos recuperar el mensaje transmitido, 102.

 

DETECCIÓN Y CORRECCIÓN

 

Supongamos que recibimos el siguiente mensaje: 21113. Para saber si es correcto, buscamos un polinomio p(x)=ax^2+b.x+c, dónde a,b,c son elementos de A y verifican que 

Los restos de dividir por 5 a p(0), p(1), p(2), p(3) y p(4) son 2,1,1,1 y 3, respectivamente.

Para encontrar los coeficientes de ese polinomio, recordemos que dados tres puntos, existe una única parábola que los contiene. Entonces elegimos todas las combinaciones posibles de 3 dígitos del mensaje recibido (que son 10), y armamos el polinomio (de interpolación).

Por ejemplo, si la terna es 211_ _ queremos una parábola que pase por los puntos

(0, p(0)), (1,p(1)) y (2,p(2)) y el polinomio que lo cumple es p(x)=3.x^2+1.x+2.

Si calculamos los 10 diez polinomios, como aparece en el mural, vemos que no son todos iguales! Lo cual significa que (0, p(0)), (1,p(1)), (2,p(2)), (3,p(3)) y (4,p(4)), no son puntos de la misma parábola, es decir, HAY UN ERROR!

Para encontrar el error, nos quedamos con el polinomio que más se repite, en este caso p(x)=1.x^2+0.x+2, y calculamos el resto de dividir por 5, el valor de este polinomio en 1. En el ejemplo p(1)=3 (tiene resto 3 en la división por 5). Así es como detectamos y podemos corregir el error.