Código Reed-Solomon: definición y aplicaciones de corrección de errores
Código Reed-Solomon: definición, funcionamiento y aplicaciones de corrección de errores y recuperación de datos en CD, DVD, Blu-ray, DSL, WiMAX y sistemas de difusión digital.
La corrección de errores Reed-Solomon es un código de corrección de errores hacia adelante que opera a nivel de símbolos (no de bits). Su principio básico consiste en el sobremuestreo de un polinomio construido a partir de los datos: se interpreta el bloque de datos como coeficientes de un polinomio, se evalúa ese polinomio en varios puntos de un campo finito y los valores resultantes se envían o almacenan. Muestrear el polinomio más veces de las estrictamente necesarias hace que el conjunto de ecuaciones esté sobredeterminado, de modo que si se reciben correctamente "suficientes" puntos, el receptor puede recuperar el polinomio original incluso cuando algunos puntos están corruptos o faltan.
Parámetros y capacidad de corrección
Un código Reed-Solomon se describe habitualmente como RS(n, k) sobre un campo finito GF(2^m), donde:
- n es el número total de símbolos por bloque (normalmente n ≤ 2^m − 1).
- k es el número de símbolos de datos (útiles).
- n − k son los símbolos de redundancia (paridad).
La capacidad de corrección de errores en símbolos es t = floor((n − k) / 2): el código puede corregir hasta t símbolos erróneos por bloque. Si las posiciones de error son conocidas (es decir, si se trata de erasure o borrados), puede recuperar hasta n − k símbolos. Es importante recordar que un "símbolo" suele ser un conjunto de m bits; por ejemplo, RS(255,223) sobre GF(256) usa símbolos de 8 bits y corrige hasta 16 símbolos erróneos (16 bytes).
Codificación y decodificación (visión general)
- Codificación: los datos se toman como coeficientes de un polinomio p(x) de grado < k; se eligen n puntos distintos en el campo finito y se envían los pares (x_i, p(x_i)) o simplemente los valores p(x_i) si las ubicaciones son implícitas. En la práctica se genera paridad mediante multiplicación matricial o evaluaciones rápidas en GF(2^m).
- Decodificación: incluye varios pasos: cálculo de síndromes, localización de errores (encontrar un polinomio localizador de errores), determinación de magnitudes de error y corrección. Los algoritmos más usados son el algoritmo de Berlekamp–Massey, el algoritmo euclidiano extendido aplicado a polinomios y el procedimiento de Forney para calcular magnitudes.
La decodificación es más compleja que la codificación y requiere aritmética en el campo finito (sumas, multiplicaciones, inversos). Existen implementaciones optimizadas que utilizan tablas de log/antilog, transformadas de Fourier sobre campos finitos y técnicas de intercalado para manejar errores en ráfaga.
Propiedades teóricas
- Los códigos Reed-Solomon son MDS (Maximum Distance Separable): alcanzan la cota de Singleton, lo que significa que con n − k símbolos de paridad se obtiene la máxima distancia mínima y, por tanto, la máxima capacidad de corrección para esos parámetros.
- Corrección a nivel de símbolo: es especialmente eficaz contra errores en ráfagas (cuando varios bits contiguos fallan dentro del mismo símbolo).
Aplicaciones prácticas
Los códigos Reed-Solomon se usan en multitud de sistemas comerciales e industriales por su robustez y flexibilidad. Algunos ejemplos notables:
- Medios ópticos y almacenamiento: CD (mediante el código CIRC — Cross-Interleaved Reed-Solomon Code—), DVD y discos Blu-ray (empleados solos o combinados con otros códigos de corrección).
- Transmisión de datos y telecomunicaciones: tecnologías como DSL, WiMAX y otros enlaces físicos o radiofrecuenciales utilizan RS para proteger tramas contra interferencias transitorias.
- Radiodifusión digital y televisión: estándares como DVB y ATSC incorporan Reed-Solomon como parte de la cadena de corrección (a menudo concatenado con un código de corrección interno como convolucional o LDPC).
- Códigos de barras y códigos 2D: los códigos QR y otros códigos de matriz usan Reed-Solomon para recuperar datos cuando la imagen está dañada o parcialmente oculta.
- Almacenamiento en servidores y arreglos RAID: implementaciones tipo RAID-6 o esquemas de paridad en sistemas distribuidos usan variantes de Reed-Solomon para tolerar fallos de discos.
- Comunicaciones espaciales y satelitales: por su capacidad frente a eventos de error concentrados y su eficiencia en tasa/robustez, se usan en enlaces con altas tasas de pérdida o ruido.
Mejoras y consideraciones prácticas
- Intercalado (interleaving): combinado con RS para convertir ráfagas largas de errores en errores dispersos en varios bloques, facilitando la corrección.
- Concatenación: a menudo se concatena Reed-Solomon con otros códigos (por ejemplo, un código externo RS y un código interno convolucional o LDPC) para mejorar el rendimiento en distintos tipos de canal.
- Implementación: la codificación es relativamente sencilla; la decodificación precisa operaciones en GF(2^m) y puede ser costosa en recursos. Se suelen usar tablas de búsqueda y optimizaciones por hardware para implementaciones en tiempo real.
- Limitaciones: mientras RS es muy potente a nivel de símbolo, existen códigos modernos (LDPC, turbo codes) que ofrecen mejor rendimiento cercano a la capacidad de canal para largas longitudes de bloque en ciertos escenarios. No obstante, RS sigue siendo la elección preferida cuando se necesita corrección de errores a nivel de símbolo, simplicidad y propiedades MDS.
Ejemplos prácticos
- RS(255,223) sobre GF(256): muy usado en diversos estándares; n − k = 32 proporciona t = 16 símbolos corregibles por bloque.
- RS(15,11) sobre GF(16): ejemplo educativo con símbolos de 4 bits, n − k = 4 → t = 2 símbolos corregibles.
En resumen, los códigos Reed-Solomon son una herramienta fundamental en la corrección de errores por su capacidad para recuperar datos ante errores concentrados, su carácter óptimo (MDS) y su amplia adopción en medios físicos, telecomunicaciones y aplicaciones industriales. Su elección y parametrización dependen del tipo de canal, la unidad de símbolo (m bits), la latencia aceptable y los requisitos de hardware/software para la decodificación.
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.
Buscar dentro de la enciclopedia