Corrección de errores de Reed-Solomon
Los códigos Reed-Solomon son un grupo de códigos de corrección de errores que fueron introducidos por Irving S. Reed y Gustave Solomon en 1960. [1] Tienen muchas aplicaciones, las más destacadas incluyen tecnologías de consumo como MiniDiscs , CD , DVD , Discos Blu-ray , códigos QR , tecnologías de transmisión de datos como DSL y WiMAX , sistemas de transmisión como comunicaciones por satélite, DVB y ATSC , y sistemas de almacenamiento como RAID 6.
Los códigos Reed-Solomon operan en un bloque de datos tratados como un conjunto de elementos de campo finito llamados símbolos. Los códigos Reed-Solomon pueden detectar y corregir múltiples errores de símbolos. Mediante la adición de t = n - k símbolos de verificación para los datos, un código de Reed-Solomon puede detectar (pero no correcta) cualquier combinación de hasta t símbolos erróneos, o localizar y correcta hasta ⌊ t / 2⌋ símbolos erróneos en lugares desconocidos . Como código de borrado , puede corregir hasta tborrados en ubicaciones que son conocidas y proporcionadas al algoritmo, o puede detectar y corregir combinaciones de errores y borrados. Los códigos Reed-Solomon también son adecuados como códigos de corrección de errores de bits de ráfagas múltiples , ya que una secuencia de errores de bits consecutivos b + 1 puede afectar como máximo a dos símbolos de tamaño b . La elección de t depende del diseñador del código y puede seleccionarse dentro de amplios límites.
Hay dos tipos básicos de códigos Reed-Solomon - vista original y BCH vista - con vista al BCH siendo los más comunes, como visión BCH decodificadores son más rápidas y requieren menos almacenamiento de trabajo de los decodificadores vista original.
Los códigos Reed-Solomon fueron desarrollados en 1960 por Irving S. Reed y Gustave Solomon , que eran entonces miembros del personal del Laboratorio Lincoln del MIT . Su artículo fundamental se tituló "Códigos polinomiales sobre ciertos campos finitos". ( Reed y Solomon 1960 ). El esquema de codificación original descrito en el artículo de Reed & Solomon utilizaba un polinomio variable basado en el mensaje que se codificaría, en el que el codificador y el decodificador solo conocen un conjunto fijo de valores (puntos de evaluación) que se codificarán. El decodificador teórico original generó polinomios potenciales basados en subconjuntos de k (longitud de mensaje no codificado) de n(longitud del mensaje codificado) valores de un mensaje recibido, eligiendo el polinomio más popular como el correcto, lo cual no era práctico para todos los casos excepto el más simple. Esto se resolvió inicialmente cambiando el esquema original a un esquema similar al código BCH basado en un polinomio fijo conocido tanto por el codificador como por el decodificador, pero más tarde, se desarrollaron decodificadores prácticos basados en el esquema original, aunque más lento que los esquemas BCH. El resultado de esto es que hay dos tipos principales de códigos Reed Solomon, los que usan el esquema de codificación original y los que usan el esquema de codificación BCH.
También en 1960, un práctico decodificador polinomial fijo para códigos BCH desarrollado por Daniel Gorenstein y Neal Zierler fue descrito en un informe del Laboratorio Lincoln del MIT por Zierler en enero de 1960 y más tarde en un artículo en junio de 1961. [2] El decodificador Gorenstein-Zierler y el trabajo relacionado con los códigos BCH se describe en un libro Error Correcting Codes de W. Wesley Peterson (1961). [3] En 1963 (o posiblemente antes), JJ Stone (y otros) reconocieron que los códigos de Reed Solomon podrían usar el esquema BCH de usar un polinomio generador fijo, haciendo de dichos códigos una clase especial de códigos BCH, [4]pero los códigos Reed Solomon basados en el esquema de codificación original, no son una clase de códigos BCH y, dependiendo del conjunto de puntos de evaluación, ni siquiera son códigos cíclicos .
En 1969, Elwyn Berlekamp y James Massey desarrollaron un decodificador de esquema BCH mejorado , conocido desde entonces como el algoritmo de decodificación de Berlekamp-Massey .
