Newtonpedia EN
Inicio › Informática › Reed-Solomon
Informática · 1960

Reed-Solomon

Familia de códigos que añaden símbolos de paridad a un mensaje para detectar y corregir errores en datos transmitidos o almacenados.

Año
1960
Protagonistas
Irving Stoy Reed, Gustave Solomon
Sección
Informática

Historia

Los códigos Reed-Solomon permiten recuperar información aunque parte de ella llegue alterada o se pierda, algo que resulta esencial en comunicaciones, almacenamiento y lectura de datos. Su idea básica es tratar los datos como grupos de bits, llamados símbolos, y añadir a cada bloque unos símbolos extra calculados a partir de un polinomio. Si el receptor recibe el bloque con algunos símbolos dañados, puede reconstruir el original siempre que el número de errores no supere cierto límite.

Antes de estos códigos existían otros métodos de corrección, como los códigos de bloque sencillos y los códigos cíclicos, que trabajaban con bits individuales y resultaban menos adecuados para errores agrupados en ráfagas. Los ingenieros del MIT Lincoln Laboratory Irving S. Reed y Gustave Solomon publicaron en 1960 el artículo titulado «Polynomial Codes over Certain Finite Fields», donde propusieron codificar el mensaje como los valores de un polinomio evaluado en los elementos de un cuerpo finito. Un polinomio de grado N-1 queda determinado por N puntos, de modo que cualquier N valores correctos bastan para reconstruirlo. La dificultad estaba en el decodificador: el método original exigía probar muchísimos subconjuntos de valores y elegir el polinomio más repetido, un procedimiento impracticable salvo en casos muy sencillos. Por ejemplo, con determinados parámetros pequeños, hacían falta miles de interpolaciones.

Para resolverlo, se adoptó en la práctica un esquema alternativo basado en un polinomio fijo, conocido por emisor y receptor, que permite aplicar métodos algebraicos mucho más rápidos. Daniel Gorenstein y Neal Zierler desarrollaron en 1960 un decodificador práctico para los códigos BCH, y en 1969 Elwyn Berlekamp y James Massey presentaron un algoritmo de decodificación que se convirtió en un estándar de referencia. Con los años aparecieron otras mejoras, como la basada en el algoritmo de Euclides extendido en 1975. Así surgieron dos grandes familias: la de la versión original y la compatible con BCH, que hoy son ambas objeto de estudio.

La primera aplicación de gran escala llegó en 1977 con las sondas Voyager, que usaron una versión combinada con otro código para enviar imágenes desde el espacio profundo. En 1982 el disco compacto lo incorporó en productos de consumo masivo, con dos capas entrelazadas que pueden corregir ráfagas de errores de hasta unos 4000 bits, es decir, un fallo de unos 2,5 milímetros en la superficie del disco. Desde entonces su uso se ha extendido a los DVD, la televisión digital terrestre y por satélite, la radio digital DAB+, las líneas xDSL, sistemas de almacenamiento como RAID 6 y prácticamente todos los códigos de barras bidimensionales, como los códigos QR. Hoy en día sigue siendo uno de los pilares de la fiabilidad de los datos digitales, aunque en algunas normas se está sustituyendo por códigos más modernos.

Cronología

  • 1960Irving S. Reed y Gustave Solomon publican en el MIT Lincoln Laboratory el artículo fundacional sobre estos códigos.
  • 1969Berlekamp y Massey presentan un algoritmo de decodificación mejorado que se sigue usando como referencia.
  • 1977Las sondas Voyager emplean estos códigos combinados con otro código para enviar imágenes desde el espacio.
  • 1982El disco compacto los incorpora en un producto de consumo masivo, primera aplicación de este tipo.
  • 1989La sonda Galileo a Júpiter y la sonda Magallanes a Venus usan este código en sus comunicaciones.

Curiosidades y anécdotas

Ráfagas de errores

Al tratar los datos por símbolos, una ráfaga de errores seguidos afecta a pocos símbolos, y el código puede corregirla con facilidad.

Un código con muchos usos

Las mismas ideas sirven para un disco de música, una imagen de un código QR y una sonda que vuela a otro planeta.

Protagonistas

Otros hitos de informática