Reed-Solomon
La corrección de errores Reed-Solomon es un código de corrección de errores hacia adelante. Funciona mediante el sobremuestreo de un polinomio construido a partir de los datos. El polinomio se evalúa en varios puntos y estos valores se envían o registran. El muestreo del polinomio con más frecuencia de la necesaria hace que el polinomio esté sobredeterminado. Mientras reciba correctamente "muchos" de los puntos, el receptor puede recuperar el polinomio original incluso en presencia de unos "pocos" puntos malos.
Los códigos Reed-Solomon se utilizan en muchos tipos de aplicaciones comerciales, por ejemplo en CD, DVD y discos Blu-ray, en tecnologías de transmisión de datos como DSL y WiMAX, y en sistemas de radiodifusión como DVB y ATSC.
Resumen
Los códigos Reed-Solomon son códigos de bloque. Esto significa que un bloque fijo de datos de entrada se transforma en un bloque fijo de datos de salida. En el caso del código R-S más utilizado (255, 223), 223 símbolos Reed-Solomon de entrada (cada uno de ocho bits) se codifican en 255 símbolos de salida.
- La mayoría de los esquemas R-S ECC son sistemáticos. Esto significa que una parte del código de salida contiene los datos de entrada en su forma original.
- Se eligió un tamaño de símbolo Reed-Solomon de ocho bits porque los descodificadores para tamaños de símbolo mayores serían difíciles de implementar con la tecnología actual. Esta elección de diseño obliga a que la longitud más larga de la codificación sea de 255 símbolos.
- El código Reed-Solomon estándar (255, 223) es capaz de corregir hasta 16 errores de símbolo Reed-Solomon en cada codeword. Dado que cada símbolo es en realidad ocho bits, esto significa que el código puede corregir hasta 16 ráfagas cortas de error debido al decodificador convolucional interno.
El código Reed-Solomon, al igual que el código convolucional, es un código transparente. Esto significa que si los símbolos del canal se han invertido en algún punto de la línea, los descodificadores seguirán funcionando. El resultado será el complemento de los datos originales. Sin embargo, el código Reed-Solomon pierde su transparencia si se utiliza el relleno de cero virtual. Por esta razón, es obligatorio que el sentido de los datos (es decir, verdadero o complementado) se resuelva antes de la decodificación Reed-Solomon.
En el caso del programa Voyager, los códigos R-S alcanzan un rendimiento casi óptimo cuando se concatenan con el código interno convolucional (Viterbi) (7, 1/2). Dado que se necesitan dos símbolos de comprobación para cada error que se debe corregir, esto da como resultado un total de 32 símbolos de comprobación y 223 símbolos de información por cada código.
Además, las palabras de código Reed-Solomon pueden intercalarse por símbolos antes de ser codificadas por convolución. Como esto separa los símbolos de una palabra de código, es menos probable que una ráfaga del decodificador Viterbi perturbe más de un símbolo Reed-Solomon en cualquier palabra de código.
Idea básica
La idea clave de un código Reed-Solomon es que los datos codificados se visualizan primero como un polinomio. El código se basa en un teorema del álgebra que afirma que cualesquiera k puntos distintos determinan de forma única un polinomio de grado como máximo k-1.
El emisor determina un polinomio de grado k - 1 {\displaystyle k-1}
, sobre un campo finito, que representa los k {\displaystyle k}
puntos de datos. El polinomio es entonces "codificado" por su evaluación en varios puntos, y estos valores son los que se envían realmente. Durante la transmisión, algunos de estos valores pueden corromperse. Por lo tanto, se envían realmente más de k puntos. Mientras se reciban suficientes valores correctamente, el receptor puede deducir cuál era el polinomio original y decodificar los datos originales.
Del mismo modo que se puede corregir una curva interpolando un hueco, un código Reed-Solomon puede salvar una serie de errores en un bloque de datos para recuperar los coeficientes del polinomio que dibujó la curva original.
Historia
El código fue inventado en 1960 por Irving S. Reed y Gustave Solomon, entonces miembros del Laboratorio Lincoln del MIT. Su artículo seminal se titulaba "Polynomial Codes over Certain Finite Fields". Cuando se escribió, la tecnología digital no estaba lo suficientemente avanzada como para aplicar el concepto. La primera aplicación, en 1982, de los códigos RS en productos de producción masiva fue el disco compacto, donde se utilizan dos códigos RS intercalados. En 1969, Elwyn Berlekamp y James Massey desarrollaron un algoritmo de descodificación eficaz para códigos RS de gran distancia. En la actualidad, los códigos RS se utilizan en unidades de disco duro, DVD, telecomunicaciones y protocolos de transmisión digital.
