Corrección de errores de Reed-Solomon

Códigos de corrección de errores

Códigos Reed-Solomon
Lleva el nombre de	Irving S. Reed y Gustave Solomon
Clasificación
Jerarquía	Código de bloque lineal Código polinomial Código Reed-Solomon
Longitud del bloque	norte
Longitud del mensaje	k
Distancia	n - k + 1
Tamaño del alfabeto	q = p m ≥ n   ( p primo) A menudo n = q - 1.
Notación	[ n , k , n - k + 1] código q
Algoritmos
Berlekamp – Massey Euclidean et al.
Propiedades
Código separable de distancia máxima
v t mi

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 minidiscos , 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 e incluyendo t símbolos erróneos, o localizar y corregir hasta e incluyendo ⌊ t / 2⌋ errónea símbolos en ubicaciones desconocidas. Como código de borrado , puede corregir hasta e incluyendo 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 vista BCH - siendo la vista BCH la más común, ya que los decodificadores de vista BCH son más rápidos y requieren menos almacenamiento de trabajo que los decodificadores de vista originales.

Historia

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 utilizó un polinomio variable basado en el mensaje que se codificará, en el que el codificador y el descodificador 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 de 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 .

En 1975, Yasuo Sugiyama desarrolló otro decodificador de esquema BCH mejorado, basado en el algoritmo euclidiano extendido . ^[5]

En 1977, los códigos Reed-Solomon se implementaron en el programa Voyager en forma de códigos de corrección de errores concatenados . La primera aplicación comercial en productos de consumo producidos en masa apareció en 1982 con el disco compacto , donde se utilizan dos códigos Reed-Solomon intercalados . En la actualidad, los códigos Reed-Solomon se implementan ampliamente en dispositivos de almacenamiento digital y estándares de comunicación digital , aunque están siendo reemplazados lentamente por códigos más modernos de verificación de paridad de baja densidad (LDPC) o códigos turbo . Por ejemplo, los códigos Reed-Solomon se utilizan en el estándar DVB-S de transmisión de video digital (DVB)., pero los códigos LDPC se utilizan en su sucesor, DVB-S2 .

En 1986, se desarrolló un decodificador de esquema original conocido como el algoritmo de Berlekamp-Welch .

En 1996, Madhu Sudan y otros desarrollaron variaciones de los decodificadores de esquemas originales llamados decodificadores de lista o decodificadores de software, y el trabajo continúa en este tipo de decodificadores; consulte el algoritmo de decodificación de listas de Guruswami-Sudan .

En 2002, Shuhong Gao desarrolló otro decodificador de esquema original, basado en el algoritmo euclidiano extendido Gao_RS.pdf .

Aplicaciones

Almacenamiento de datos

La codificación Reed-Solomon se utiliza mucho en los sistemas de almacenamiento masivo para corregir los errores de ráfaga asociados con los defectos de los medios.

La codificación Reed-Solomon es un componente clave del disco compacto . Fue el primer uso de una fuerte codificación de corrección de errores en un producto de consumo de producción masiva, y DAT y DVD usan esquemas similares. En el CD, dos capas de codificación Reed-Solomon separadas por un intercalador convolucional de 28 vías producen un esquema llamado Codificación Reed-Solomon entrelazada cruzada ( CIRC). El primer elemento de un decodificador CIRC es un código Reed-Solomon interno relativamente débil (32,28), abreviado de un código (255,251) con símbolos de 8 bits. Este código puede corregir errores de hasta 2 bytes por bloque de 32 bytes. Más importante aún, marca como borrado cualquier bloque incorregible, es decir, bloques con errores de más de 2 bytes. Los bloques decodificados de 28 bytes, con indicaciones de borrado, son luego esparcidos por el desintercalador a diferentes bloques del código externo (28, 24). Gracias al desintercalado, un bloque de 28 bytes borrado del código interno se convierte en un solo byte borrado en cada uno de los 28 bloques de código externos. El código externo corrige esto fácilmente, ya que puede manejar hasta 4 borrados de este tipo por bloque.

El resultado es un CIRC que puede corregir completamente las ráfagas de errores de hasta 4000 bits, o aproximadamente 2,5 mm en la superficie del disco. Este código es tan fuerte que la mayoría de los errores de reproducción de CD se deben casi con certeza a errores de seguimiento que hacen que el láser salte de pista, no a ráfagas de errores incorregibles. ^[6]

Los DVD usan un esquema similar, pero con bloques mucho más grandes, un código interno (208,192) y un código externo (182,172).

La corrección de errores de Reed-Solomon también se usa en archivos parchive que comúnmente se publican adjuntos a archivos multimedia en USENET . El servicio de almacenamiento distribuido en línea Wuala (descontinuado en 2015) también solía hacer uso de Reed – Solomon al dividir archivos.

Código de barras

Casi todos los códigos de barras bidimensionales como PDF-417 , MaxiCode , Datamatrix , QR Code y Aztec Code utilizan la corrección de errores Reed-Solomon para permitir una lectura correcta incluso si una parte del código de barras está dañada. Cuando el lector de códigos de barras no puede reconocer un símbolo de código de barras, lo tratará como un borrado.

La codificación Reed-Solomon es menos común en los códigos de barras unidimensionales, pero la utiliza la simbología PostBar .

Transmisión de datos

Se pueden utilizar formas especializadas de códigos Reed-Solomon, específicamente Cauchy -RS y Vandermonde -RS, para superar la naturaleza poco confiable de la transmisión de datos a través de canales de borrado . El proceso de codificación asume un código de RS ( N ,  K ) que da como resultado N palabras de código de longitud N símbolos, cada uno de los cuales almacena K símbolos de datos, que se generan, que luego se envían a través de un canal de borrado.

Cualquier combinación de K palabras de código recibidas en el otro extremo es suficiente para reconstruir todas las N palabras de código. La tasa de código generalmente se establece en 1/2 a menos que la probabilidad de borrado del canal se pueda modelar adecuadamente y se considere que es menor. En conclusión, N suele ser 2 K , lo que significa que al menos la mitad de todas las palabras de código enviadas deben recibirse para reconstruir todas las palabras de código enviadas.

Los códigos Reed-Solomon también se utilizan en los sistemas xDSL y las Especificaciones del Protocolo de Comunicaciones Espaciales de CCSDS como una forma de corrección de errores hacia adelante .

Transmisión espacial

Sistema de codificación concatenado de espacio profundo. ^[7] Notación: RS (255, 223) + CC ("longitud de restricción" = 7, tasa de código = 1/2).

Una aplicación importante de la codificación Reed-Solomon fue codificar las imágenes digitales enviadas por el programa Voyager .

La Voyager introdujo la codificación Reed-Solomon concatenada con códigos convolucionales , una práctica que desde entonces se ha generalizado mucho en el espacio profundo y las comunicaciones por satélite (p. Ej., Radiodifusión digital directa).

Los decodificadores de Viterbi tienden a producir errores en ráfagas cortas. La corrección de estos errores de ráfaga es un trabajo que se realiza mejor mediante códigos Reed-Solomon breves o simplificados.

En las misiones Mars Pathfinder , Galileo , Mars Exploration Rover y Cassini se utilizaron versiones modernas de codificación convolucional concatenada Reed-Solomon / Viterbi decodificada , donde funcionan entre 1 y 1,5 dB del límite máximo, la capacidad de Shannon .

Estos códigos concatenados ahora están siendo reemplazados por códigos turbo más potentes :

Esquemas de codificación de canales utilizados por las misiones de la NASA ^[8]

Años	Código	Misión (s)
1958-presente	Sin codificar	Explorer, Mariner, muchos otros
1968-1978	códigos convolucionales (CC) (25, 1/2)	Pioneer, Venus
1969-1975	Código Reed-Muller (32, 6)	Marinero, Vikingo
1977-presente	Código binario de Golay	Viajero
1977-presente	RS (255, 223) + CC (7, 1/2)	Voyager, Galileo, muchos otros
1989-2003	RS (255, 223) + CC (7, 1/3)	Viajero
1958-presente	RS (255, 223) + CC (14, 1/4)	Galileo
1996-presente	RS + CC (15, 1/6)	Cassini, Mars Pathfinder, otros
2004-presente	Códigos turbo [nb 1]	Messenger, Stereo, MRO, otros
est. 2009	Códigos LDPC	Constelación, MSL

Construcciones

El código Reed-Solomon es en realidad una familia de códigos, donde cada código se caracteriza por tres parámetros: un tamaño de alfabeto q , una longitud de bloque n y una longitud de mensaje k, con k <n ≤ q. El conjunto de símbolos del alfabeto se interpreta como el campo finito de orden q y, por tanto, q tiene que ser una potencia prima . En las parametrizaciones más útiles del código Reed-Solomon, la longitud del bloque suele ser un múltiplo constante de la longitud del mensaje, es decir, la tasa R = k / nes una constante y, además, la longitud del bloque es igual o uno menor que el tamaño del alfabeto, es decir, n = q o n = q - 1 . ^{[ cita requerida ]}

Vista original de Reed & Solomon: La palabra en clave como una secuencia de valores

Existen diferentes procedimientos de codificación para el código Reed-Solomon y, por lo tanto, existen diferentes formas de describir el conjunto de todas las palabras de código. En la visión original de Reed y Solomon (1960) , cada palabra clave del código Reed-Solomon es una secuencia de valores de función de un polinomio de grado menor que k . Para obtener una palabra clave del código Reed-Solomon, los símbolos del mensaje (cada uno dentro del alfabeto de tamaño q) se tratan como los coeficientes de un polinomio p de grado menor que k , sobre el campo finito F con q elementos. A su vez, el polinomio p se evalúa en n ≤ q puntos distintos del campo${\displaystyle a_{1},\dots ,a_{n}}$F , y la secuencia de valores es la palabra de código correspondiente. Las opciones comunes para un conjunto de puntos de evaluación incluyen {0, 1, 2, ..., n - 1}, {0, 1, α , α ² , ..., α ^{n −2} } o para n < q , {1, α , alfa ² , ..., α ^{n -1} }, ..., donde α es un elemento primitivo de F .

Formalmente, el conjunto de palabras en clave del código Reed-Solomon se define de la siguiente manera:${\displaystyle \mathbf {C} }$

${\displaystyle \mathbf {C} ={\Big \{}\;{\big (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\big )}\;{\Big |}\;p{\text{ is a polynomial over }}F{\text{ of degree }}<k\;{\Big \}}\,.}$

Dado que dos polinomios distintos de grado menor que concuerdan en la mayoría de los puntos, esto significa que dos palabras de código cualesquiera del código Reed-Solomon no concuerdan en al menos posiciones. Además, hay dos polinomios que coinciden en puntos pero no son iguales y, por lo tanto, la distancia del código Reed-Solomon es exactamente . Entonces la distancia relativa es , donde es la tasa. Esta compensación entre la distancia relativa y la tasa es asintóticamente óptima ya que, por el límite de Singleton , todo código satisface . Al ser un código que logra esta compensación óptima, el código Reed-Solomon pertenece a la clase de${\displaystyle k}$${\displaystyle k-1}$${\displaystyle n-(k-1)=n-k+1}$${\displaystyle k-1}$${\displaystyle d=n-k+1}$${\displaystyle \delta =d/n=1-k/n+1/n=1-R+1/n\sim 1-R}$${\displaystyle R=k/n}$${\displaystyle \delta +R\leq 1+1/n}$códigos separables de distancia máxima .

Si bien el número de polinomios diferentes de grado menor que k y el número de mensajes diferentes son ambos iguales y , por lo tanto, cada mensaje puede mapearse de forma única en dicho polinomio, existen diferentes formas de realizar esta codificación. La construcción original de Reed y Solomon (1960) interpreta el mensaje x como los coeficientes del polinomio p , mientras que las construcciones posteriores interpretan el mensaje como los valores del polinomio en los primeros k puntos y obtienen el polinomio p interpolando estos valores con un polinomio de grado menor que k${\displaystyle q^{k}}$${\displaystyle a_{1},\dots ,a_{k}}$. El último procedimiento de codificación, aunque es algo menos eficaz, tiene la ventaja de que da lugar a un código sistemático , es decir, el mensaje original siempre está contenido como una subsecuencia de la palabra de código.

Procedimiento de codificación simple: el mensaje como una secuencia de coeficientes

En la construcción original de Reed & Solomon (1960) , el mensaje se asigna al polinomio con${\displaystyle x=(x_{1},\dots ,x_{k})\in F^{k}}$${\displaystyle p_{x}}$

${\displaystyle p_{x}(a)=\sum _{i=1}^{k}x_{i}a^{i-1}\,.}$

La palabra clave de se obtiene evaluando en diferentes puntos del campo . Por lo tanto, la función de codificación clásica para el código Reed-Solomon se define de la siguiente manera: ${\displaystyle x}$${\displaystyle p_{x}}$${\displaystyle n}$${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle F}$${\displaystyle C:F^{k}\to F^{n}}$

${\displaystyle C(x)={\big (}p_{x}(a_{1}),\dots ,p_{x}(a_{n}){\big )}\,.}$

Esta función es un mapeo lineal , es decir, satisface para la siguiente -matriz con elementos de :${\displaystyle C}$${\displaystyle C(x)=x\cdot A}$${\displaystyle (k\times n)}$${\displaystyle A}$${\displaystyle F}$

${\displaystyle A={\begin{bmatrix}1&\dots &1&\dots &1\\a_{1}&\dots &a_{k}&\dots &a_{n}\\a_{1}^{2}&\dots &a_{k}^{2}&\dots &a_{n}^{2}\\\vdots &&\vdots &&\vdots \\a_{1}^{k-1}&\dots &a_{k}^{k-1}&\dots &a_{n}^{k-1}\end{bmatrix}}}$

Esta matriz es la transpuesta de una matriz de Vandermonde sobre . En otras palabras, el código Reed-Solomon es un código lineal y, en el procedimiento de codificación clásico, su matriz generadora es .${\displaystyle F}$${\displaystyle A}$

Procedimiento de codificación sistemático: el mensaje como secuencia inicial de valores

Existe un procedimiento de codificación alternativo que también produce el código Reed-Solomon, pero que lo hace de forma sistemática . Aquí, el mapeo del mensaje al polinomio funciona de manera diferente: el polinomio ahora se define como el polinomio único de grado menor que tal que${\displaystyle x}$${\displaystyle p_{x}}$${\displaystyle p_{x}}$${\displaystyle k}$

${\displaystyle p_{x}(a_{i})=x_{i}}$vale para todos .${\displaystyle i\in \{1,\dots ,k\}}$

Para calcular este polinomio a partir de , se puede utilizar la interpolación de Lagrange . Una vez encontrado, se evalúa en los demás puntos del campo. La función de codificación alternativa para el código Reed-Solomon es nuevamente solo la secuencia de valores: ${\displaystyle p_{x}}$${\displaystyle x}$${\displaystyle a_{k+1},\dots ,a_{n}}$${\displaystyle C:F^{k}\to F^{n}}$

${\displaystyle C(x)={\big (}p_{x}(a_{1}),\dots ,p_{x}(a_{n}){\big )}\,.}$

Dado que las primeras entradas de cada palabra de código coinciden con , este procedimiento de codificación es de hecho sistemático . Dado que la interpolación de Lagrange es una transformación lineal, es un mapeo lineal. De hecho, tenemos , donde${\displaystyle k}$${\displaystyle C(x)}$${\displaystyle x}$${\displaystyle C}$${\displaystyle C(x)=x\cdot G}$

${\displaystyle G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$

Transformada discreta de Fourier y su inversa

Una transformada discreta de Fourier es esencialmente lo mismo que el procedimiento de codificación; utiliza el polinomio generador p (x) para mapear un conjunto de puntos de evaluación en los valores del mensaje como se muestra arriba:

${\displaystyle C(x)={\big (}p_{x}(a_{1}),\dots ,p_{x}(a_{n}){\big )}\,.}$

La transformada de Fourier inversa podría usarse para convertir un conjunto libre de errores de n < q valores de mensaje de nuevo en el polinomio de codificación de k coeficientes, con la restricción de que para que esto funcione, el conjunto de puntos de evaluación usados ​​para codificar el mensaje debe ser un conjunto de potencias crecientes de α :

${\displaystyle a_{i}=\alpha ^{i-1}}$

${\displaystyle a_{1},\dots ,a_{n}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$

Sin embargo, la interpolación de Lagrange realiza la misma conversión sin la restricción sobre el conjunto de puntos de evaluación o el requisito de un conjunto libre de errores de valores de mensaje y se utiliza para la codificación sistemática y en uno de los pasos del decodificador Gao .

La vista BCH: la palabra de código como una secuencia de coeficientes

En esta vista, el mensaje se interpreta como los coeficientes de un polinomio . El remitente calcula un polinomio relacionado de grado donde y envía el polinomio . El polinomio se construye multiplicando el polinomio del mensaje , que tiene grado , con un polinomio generador de grado que es conocido tanto por el emisor como por el receptor. El polinomio generador se define como el polinomio cuyas raíces son potencias secuenciales de la primitiva de campo de Galois.${\displaystyle p(x)}$${\displaystyle s(x)}$${\displaystyle n-1}$${\displaystyle n\leq q-1}$${\displaystyle s(x)}$${\displaystyle s(x)}$${\displaystyle p(x)}$${\displaystyle k-1}$ ${\displaystyle g(x)}$${\displaystyle n-k}$${\displaystyle g(x)}$${\displaystyle \alpha }$

${\displaystyle g(x)=(x-\alpha ^{i})(x-\alpha ^{i+1})\cdots (x-\alpha ^{i+n-k-1})=g_{0}+g_{1}x+\cdots +g_{n-k-1}x^{n-k-1}+x^{n-k}}$

Para una "estrecha código de sentido", . ${\displaystyle i=1}$

${\displaystyle \mathbf {C} =\left\{\left(s_{1},s_{2},\dots ,s_{n}\right)\;{\Big |}\;s(a)=\sum _{i=1}^{n}s_{i}a^{i}{\text{ is a polynomial that has at least the roots }}\alpha ^{1},\alpha ^{2},\dots ,\alpha ^{n-k}\right\}\,.}$

Procedimiento de codificación sistemático

El procedimiento de codificación para la vista BCH de los códigos Reed-Solomon se puede modificar para producir un procedimiento de codificación sistemático , en el que cada palabra de código contiene el mensaje como prefijo y simplemente agrega símbolos de corrección de errores como sufijo. Aquí, en lugar de enviar , el codificador construye el polinomio transmitido de manera que los coeficientes de los monomios más grandes sean iguales a los coeficientes correspondientes de , y los coeficientes de orden inferior de se elijan exactamente de tal manera que se vuelvan divisibles por . Entonces los coeficientes de son una subsecuencia (específicamente, un prefijo) de los coeficientes de . Para obtener un código que sea sistemático en general, construimos el polinomio del mensaje${\displaystyle s(x)=p(x)g(x)}$${\displaystyle s(x)}$${\displaystyle k}$${\displaystyle p(x)}$${\displaystyle s(x)}$${\displaystyle s(x)}$${\displaystyle g(x)}$${\displaystyle p(x)}$${\displaystyle s(x)}$${\displaystyle p(x)}$ interpretando el mensaje como la secuencia de sus coeficientes.

Formalmente, la construcción se realiza multiplicando por para dejar espacio para los símbolos de verificación, dividiendo ese producto entre para encontrar el resto y luego compensando ese resto restándolo. Los símbolos de verificación se crean calculando el resto :${\displaystyle p(x)}$${\displaystyle x^{t}}$${\displaystyle t=n-k}$${\displaystyle g(x)}$${\displaystyle t}$${\displaystyle s_{r}(x)}$

${\displaystyle s_{r}(x)=p(x)\cdot x^{t}\ {\bmod {\ }}g(x).}$

El resto tiene grado como máximo , mientras que los coeficientes de en el polinomio son cero. Por tanto, la siguiente definición de la palabra de código tiene la propiedad de que los primeros coeficientes son idénticos a los coeficientes de :${\displaystyle t-1}$${\displaystyle x^{t-1},x^{t-2},\dots ,x^{1},x^{0}}$${\displaystyle p(x)\cdot x^{t}}$${\displaystyle s(x)}$${\displaystyle k}$${\displaystyle p(x)}$

${\displaystyle s(x)=p(x)\cdot x^{t}-s_{r}(x)\,.}$

Como resultado, las palabras de código son elementos de , es decir, son divisibles por el polinomio generador : ^[9]${\displaystyle s(x)}$${\displaystyle \mathbf {C} }$${\displaystyle g(x)}$

${\displaystyle s(x)\equiv p(x)\cdot x^{t}-s_{r}(x)\equiv s_{r}(x)-s_{r}(x)\equiv 0\mod g(x)\,.}$

Propiedades

El código Reed-Solomon es un código [ n , k , n - k + 1]; en otras palabras, es un código de bloque lineal de longitud n (sobre F ) con dimensión k y distancia mínima de Hamming El código Reed-Solomon es óptimo en el sentido de que la distancia mínima tiene el valor máximo posible para un código lineal de tamaño ( n ,  k ); esto se conoce como el límite de Singleton . Este código también se denomina código de distancia máxima separable (MDS) .${\textstyle d_{\min }=n-k+1.}$

La capacidad de corrección de errores de un código Reed-Solomon está determinada por su distancia mínima o, de manera equivalente, por la medida de redundancia en el bloque. Si las ubicaciones de los símbolos de error no se conocen de antemano, entonces un código Reed-Solomon puede corregir hasta símbolos erróneos, es decir, puede corregir la mitad de errores que símbolos redundantes agregados al bloque. A veces ubicaciones de error se conocen de antemano (por ejemplo, "información lateral" en demodulador relaciones de señal a ruido ) -estos son llamados borraduras . Un código Reed-Solomon (como cualquier código MDS ) puede corregir el doble de borrados que errores, y cualquier combinación de errores y borrados puede corregirse siempre que la relación 2 E  + ${\displaystyle n-k}$${\displaystyle (n-k)/2}$ Se satisface S  ≤  n  -  k , donde es el número de errores y es el número de borrados en el bloque.${\displaystyle E}$${\displaystyle S}$

Rendimiento teórico de BER del código Reed-Solomon (N = 255, K = 233, QPSK, AWGN). Característica escalonada.

El límite de error teórico se puede describir mediante la siguiente fórmula para el canal AWGN para FSK : ^[10]

${\displaystyle P_{b}\approx {\frac {2^{m-1}}{2^{m}-1}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$

y para otros esquemas de modulación:

${\displaystyle P_{b}\approx {\frac {1}{m}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$

donde , , , es la tasa de error de símbolo en el caso AWGN no codificado y es el orden de modulación.${\displaystyle t={\frac {1}{2}}(d_{\min }-1)}$${\displaystyle P_{s}=1-(1-s)^{h}}$${\displaystyle h={\frac {m}{\log _{2}M}}}$${\displaystyle s}$${\displaystyle M}$

Para usos prácticos de los códigos Reed-Solomon, es común usar un campo finito con elementos. En este caso, cada símbolo se puede representar como un valor de -bit. El remitente envía los puntos de datos como bloques codificados y el número de símbolos en el bloque codificado es . Por tanto, un código Reed-Solomon que opera con símbolos de 8 bits tiene símbolos por bloque. (Este es un valor muy popular debido a la prevalencia de los sistemas informáticos orientados a bytes ). El número , con , de símbolos de datos en el bloque es un parámetro de diseño. Un código de uso común codifica símbolos de datos de ocho bits más 32 símbolos de paridad de ocho bits en un bloque de símbolos ; esto se denota como un${\displaystyle F}$${\displaystyle 2^{m}}$${\displaystyle m}$${\displaystyle n=2^{m}-1}$${\displaystyle n=2^{8}-1=255}$${\displaystyle k}$${\displaystyle k<n}$${\displaystyle k=223}$${\displaystyle n=255}$${\displaystyle (n,k)=(255,223)}$ código, y es capaz de corregir hasta 16 errores de símbolo por bloque.

Las propiedades del código Reed-Solomon discutidas anteriormente los hacen especialmente adecuados para aplicaciones donde los errores ocurren en ráfagas . Esto se debe a que no le importa al código cuántos bits de un símbolo tienen errores; si varios bits de un símbolo están dañados, solo cuenta como un solo error. Por el contrario, si un flujo de datos no se caracteriza por ráfagas de errores o pérdidas, sino por errores aleatorios de un solo bit, un código Reed-Solomon suele ser una mala elección en comparación con un código binario.

El código Reed-Solomon, como el código convolucional , es un código transparente. Esto significa que si los símbolos de canal se han invertido en algún lugar a lo largo de la línea, los decodificadores seguirán funcionando. El resultado será la inversión de los datos originales. Sin embargo, el código Reed-Solomon pierde su transparencia cuando se abrevia. Los bits "faltantes" en un código abreviado deben completarse con ceros o unos, dependiendo de si los datos se complementan o no. (Para decirlo de otra manera, si los símbolos están invertidos, entonces el relleno con cero debe invertirse en un relleno). 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.

Si el código Reed-Solomon es cíclico o no depende de los detalles sutiles de la construcción. En la vista original de Reed y Solomon, donde las palabras de código son los valores de un polinomio, uno puede elegir la secuencia de puntos de evaluación de tal manera que el código sea cíclico. En particular, si es una raíz primitiva del campo , entonces, por definición, todos los elementos distintos de cero de toman la forma para , donde . Cada polinomio sobre da lugar a una palabra clave . Dado que la función también es un polinomio del mismo grado, esta función da lugar a una palabra de código ; ya que se mantiene, esta palabra de código es el desplazamiento cíclico a la izquierda${\displaystyle \alpha }$${\displaystyle F}$${\displaystyle F}$${\displaystyle \alpha ^{i}}$${\displaystyle i\in \{1,\dots ,q-1\}}$${\displaystyle q=|F|}$${\displaystyle p}$${\displaystyle F}$${\displaystyle (p(\alpha ^{1}),\dots ,p(\alpha ^{q-1}))}$${\displaystyle a\mapsto p(\alpha a)}$${\displaystyle (p(\alpha ^{2}),\dots ,p(\alpha ^{q}))}$${\displaystyle \alpha ^{q}=\alpha ^{1}}$de la palabra de código original derivada de . Por lo tanto, elegir una secuencia de poderes de raíz primitivos como puntos de evaluación hace que la vista original del código Reed-Solomon sea cíclica . Los códigos Reed-Solomon en la vista BCH son siempre cíclicos porque los códigos BCH son cíclicos .${\displaystyle p}$

Comentarios

Los diseñadores no están obligados a utilizar los tamaños "naturales" de los bloques de código Reed-Solomon. Una técnica conocida como "acortamiento" puede producir un código más pequeño de cualquier tamaño deseado a partir de un código más grande. Por ejemplo, el código (255,223) ampliamente utilizado se puede convertir en un código (160,128) rellenando la parte no utilizada del bloque fuente con 95 ceros binarios y no transmitiéndolos. En el decodificador, la misma porción del bloque se carga localmente con ceros binarios. El teorema de Delsarte-Goethals-Seidel ^[11] ilustra un ejemplo de una aplicación de códigos abreviados de Reed-Solomon. Paralelamente al acortamiento, una técnica conocida como punción permite omitir algunos de los símbolos de paridad codificados.

Decodificadores de vista BCH

Los decodificadores descritos en esta sección utilizan la vista BCH de una palabra de código como una secuencia de coeficientes. Utilizan un polinomio generador fijo conocido tanto por el codificador como por el descodificador.

Decodificador Peterson-Gorenstein-Zierler

Artículo principal: algoritmo Peterson-Gorenstein-Zierler

Daniel Gorenstein y Neal Zierler desarrollaron un decodificador que 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. ^[12] El decodificador Gorenstein-Zierler y el trabajo relacionado en códigos BCH se describen en libro Error Correcting Codes de W. Wesley Peterson (1961). ^[13]

Formulación

El mensaje transmitido`` se ve como los coeficientes de un polinomio s ( x ):${\displaystyle (c_{0},\ldots ,c_{i},\ldots ,c_{n-1})}$

${\displaystyle s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}}$

Como resultado del procedimiento de codificación de Reed-Solomon, s ( x ) es divisible por el polinomio generador g ( x ):

${\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}$

donde α es una raíz primitiva.

Dado que s ( x ) es un múltiplo del generador g ( x ), se deduce que "hereda" todas sus raíces:

${\displaystyle s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k}$

El polinomio transmitido se corrompe en tránsito por un polinomio de error e ( x ) para producir el polinomio recibido r ( x ).

${\displaystyle r(x)=s(x)+e(x)}$

${\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}$

donde e _i es el coeficiente para la i -ésima potencia de x . El coeficiente e _i será cero si no hay error en esa potencia de x y distinto de cero si hay un error. Si hay ν errores en distintas potencias i _k de x , entonces

${\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}}$

El objetivo del decodificador es encontrar el número de errores ( ν ), las posiciones de los errores ( i _k ) y los valores de error en esas posiciones ( e _{i k} ). A partir de ellos, e ( x ) se puede calcular y restar de r ( x ) para obtener el mensaje enviado originalmente s ( x ).

Decodificación del síndrome

El decodificador comienza evaluando el polinomio recibido en ciertos puntos. Llamamos a los resultados de esa evaluación los "síndromes", S _j . Se definen como:

${\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})=e(\alpha ^{j}),\ j=1,2,\ldots ,n-k\\&=\sum _{k=1}^{\nu }e_{i_{k}}\left(\alpha ^{j}\right)^{i_{k}}\end{aligned}}}$

La ventaja de observar los síndromes es que el polinomio del mensaje desaparece. En otras palabras, los síndromes solo se relacionan con el error y no se ven afectados por el contenido real del mensaje que se transmite. Si todos los síndromes son cero, el algoritmo se detiene aquí e informa que el mensaje no se corrompió en tránsito.

Localizadores de errores y valores de error

Por conveniencia, defina los localizadores de error X _k y los valores de error Y _k como:

${\displaystyle X_{k}=\alpha ^{i_{k}},\ Y_{k}=e_{i_{k}}}$

Luego, los síndromes se pueden escribir en términos de estos localizadores de error y valores de error como

${\displaystyle S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}}$

Esta definición de los valores del síndrome es equivalente a la anterior desde .${\displaystyle (\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}}$

Los síndromes dan un sistema de n  -  k ≥ 2 ν ecuaciones en 2 ν incógnitas, pero ese sistema de ecuaciones no es lineal en X _k y no tiene una solución obvia. Sin embargo, si se conociera X _k (ver más abajo), entonces las ecuaciones del síndrome proporcionan un sistema lineal de ecuaciones que puede resolverse fácilmente para los valores de error Y _k .

${\displaystyle {\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &&\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}}}$

En consecuencia, el problema es encontrar la X _k , porque entonces se conocería la matriz más a la izquierda, y ambos lados de la ecuación podrían multiplicarse por su inversa, dando Y _k

En la variante de este algoritmo donde ya se conocen las ubicaciones de los errores (cuando se utiliza como código de borrado ), este es el final. Las ubicaciones de error ( X _k ) ya se conocen mediante algún otro método (por ejemplo, en una transmisión de FM, las secciones en las que el tren de bits no estaba claro o se superó con interferencia se pueden determinar probabilísticamente a partir del análisis de frecuencia). En este escenario, se pueden corregir hasta errores.${\displaystyle n-k}$

El resto del algoritmo sirve para localizar los errores y requerirá valores de síndrome hasta , en lugar de solo los utilizados hasta ahora. Esta es la razón por la que es necesario agregar el doble de símbolos de corrección de errores que se puedan corregir sin conocer su ubicación.${\displaystyle 2v}$${\displaystyle v}$

Polinomio del localizador de errores

Existe una relación de recurrencia lineal que da lugar a un sistema de ecuaciones lineales. Resolver esas ecuaciones identifica esas ubicaciones de error X _k .

Defina el polinomio del localizador de errores Λ ( x ) como

${\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }}$

Los ceros de Λ ( x ) son los recíprocos . Esto se sigue de la construcción de la notación del producto anterior, ya que si entonces uno de los términos multiplicados será cero , el polinomio completo se evaluará como cero.${\displaystyle X_{k}^{-1}}$${\displaystyle x=X_{k}^{-1}}$${\displaystyle (1-X_{k}^{-1}\cdot X_{k})=1-1=0}$

${\displaystyle \Lambda (X_{k}^{-1})=0}$

Sea cualquier número entero tal que . Multiplica ambos lados por y seguirá siendo cero. ${\displaystyle j}$${\displaystyle 1\leq j\leq \nu }$${\displaystyle Y_{k}X_{k}^{j+\nu }}$

${\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0.\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0.\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0.\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\\\end{aligned}}}$

Suma para k = 1 a ν y seguirá siendo cero.

${\displaystyle {\begin{aligned}&\sum _{k=1}^{\nu }\left(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0\\\end{aligned}}}$

Reúna cada término en su propia suma.

${\displaystyle {\begin{aligned}&\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0\end{aligned}}}$

Extraiga los valores constantes de que no se vean afectados por la suma.${\displaystyle \Lambda }$

${\displaystyle {\begin{aligned}&\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0\end{aligned}}}$

¡Estas sumas son ahora equivalentes a los valores del síndrome, que conocemos y podemos sustituir! Por tanto, esto se reduce a

${\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0\,}$

Restando de ambos lados se obtiene${\displaystyle S_{j+\nu }}$

${\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }\ }$

Recuerde que j se eligió para ser cualquier número entero entre 1 y v inclusive, y esta equivalencia es cierta para todos y cada uno de esos valores. Por lo tanto, tenemos v ecuaciones lineales, no solo una. Por tanto, este sistema de ecuaciones lineales se puede resolver para los coeficientes Λ _i del polinomio de localización del error:

${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &&\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}}$

Lo anterior supone que el decodificador conoce el número de errores ν , pero ese número aún no se ha determinado. El decodificador PGZ no determina ν directamente, sino que lo busca probando valores sucesivos. El decodificador primero asume el valor más grande para una prueba ν y configura el sistema lineal para ese valor. Si las ecuaciones se pueden resolver (es decir, el determinante de la matriz es distinto de cero), entonces ese valor de prueba es el número de errores. Si el sistema lineal no se puede resolver, entonces la prueba ν se reduce en uno y se examina el siguiente sistema más pequeño. ( Gill nd , pág. 35)

Encuentre las raíces del polinomio del localizador de errores

Utilizar los coeficientes Λ _i encontré en el último paso para construir el polinomio ubicación del error. Las raíces del polinomio de ubicación del error se pueden encontrar mediante una búsqueda exhaustiva. Los localizadores de error X _k son los recíprocos de esas raíces. El orden de los coeficientes del polinomio de ubicación del error puede invertirse, en cuyo caso las raíces de ese polinomio invertido son los localizadores de error (no sus recíprocos ). La búsqueda de Chien es una implementación eficiente de este paso.${\displaystyle X_{k}}$${\displaystyle X_{k}^{-1}}$

Calcular los valores de error

Una vez que se conocen los localizadores de error X _k , se pueden determinar los valores de error. Esto se puede hacer mediante la solución directa de Y _k en la matriz de ecuaciones de error dada anteriormente, o usando el algoritmo de Forney .

Calcular las ubicaciones de los errores

Calcule i _k tomando la base logarítmica de X _k . Esto generalmente se hace usando una tabla de búsqueda precalculada.${\displaystyle \alpha }$

Corrija los errores

Finalmente, e (x) se genera a partir de i _k y e _{i k} y luego se resta de r (x) para obtener el mensaje enviado originalmente s (x), con los errores corregidos.

Ejemplo

Considere el código Reed-Solomon definido en GF (929) con α = 3 y t = 4 (esto se usa en los códigos de barras PDF417 ) para un código RS (7,3). El polinomio generador es

${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}$

Si el polinomio del mensaje es p ( x ) = 3 x ² + 2 x + 1 , entonces una palabra de código sistemática se codifica de la siguiente manera.

${\displaystyle s_{r}(x)=p(x)\,x^{t}\mod g(x)=547x^{3}+738x^{2}+442x+455}$

${\displaystyle s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474}$

Los errores en la transmisión pueden causar que esto se reciba en su lugar.

${\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474}$

Los síndromes se calculan evaluando r en potencias de α .

${\displaystyle S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732}$

${\displaystyle S_{2}=r(3^{2})=637,\;S_{3}=r(3^{3})=762,\;S_{4}=r(3^{4})=925}$

${\displaystyle {\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}}$

Usando eliminación gaussiana :

${\displaystyle {\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}}}$

Λ (x) = 329 x ² + 821 x + 001, con raíces x ₁ = 757 = 3 ⁻³ y x ₂ = 562 = 3 ⁻⁴

Los coeficientes se pueden invertir para producir raíces con exponentes positivos, pero normalmente esto no se usa:

R (x) = 001 x ² + 821 x + 329, con raíces 27 = 3 ³ y 81 = 3 ⁴

con el registro de las raíces correspondientes a las ubicaciones de error (de derecha a izquierda, la ubicación 0 es el último término de la palabra de código).

Para calcular los valores de error, aplique el algoritmo de Forney .

Ω (x) = S (x) Λ (x) mod x ⁴ = 546 x + 732

Λ '(x) = 658 x + 821

e ₁ = −Ω (x ₁ ) / Λ '(x ₁ ) = 074

e ₂ = −Ω (x ₂ ) / Λ '(x ₂ ) = 122

Restando e ₁ x ³ y e ₂ x ⁴ desde el polinomio recibido r reproduce la palabra de código original de s .

Decodificador Berlekamp – Massey

El algoritmo de Berlekamp-Massey es un procedimiento iterativo alternativo para encontrar el polinomio del localizador de errores. Durante cada iteración, calcula una discrepancia basada en una instancia actual de Λ (x) con un número supuesto de errores e :

${\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}$

y luego ajusta Λ ( x ) ye para que un Δ recalculado sea cero. El artículo algoritmo de Berlekamp-Massey tiene una descripción detallada del procedimiento. En el siguiente ejemplo, C ( x ) se usa para representar Λ ( x ).

Ejemplo

Utilizando los mismos datos que en el ejemplo anterior de Peterson Gorenstein Zierler:

norte	S n +1	D	C	B	B	metro
0	732	732	197 x + 1	1	732	1
1	637	846	173 x + 1	1	732	2
2	762	412	634 x 2 + 173 x + 1	173 x + 1	412	1
3	925	576	329 x 2 + 821 x + 1	173 x + 1	412	2

El valor final de C es el polinomio localizador de errores, Λ ( x ).

Decodificador euclidiano

Otro método iterativo para calcular tanto el polinomio del localizador de errores como el polinomio del valor del error se basa en la adaptación de Sugiyama del algoritmo euclidiano extendido .

Defina S (x), Λ (x) y Ω (x) para los síndromes t y los errores e :

${\displaystyle S(x)=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}}$

${\displaystyle \Lambda (x)=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1}$

${\displaystyle \Omega (x)=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}}$

La ecuación clave es:

${\displaystyle \Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)}$

Para t = 6 ye = 3:

${\displaystyle {\begin{bmatrix}\Lambda _{3}S_{6}&x^{8}\\\Lambda _{2}S_{6}+\Lambda _{3}S_{5}&x^{7}\\\Lambda _{1}S_{6}+\Lambda _{2}S_{5}+\Lambda _{3}S_{4}&x^{6}\\S_{6}+\Lambda _{1}S_{5}+\Lambda _{2}S_{4}+\Lambda _{3}S_{3}&x^{5}\\S_{5}+\Lambda _{1}S_{4}+\Lambda _{2}S_{3}+\Lambda _{3}S_{2}&x^{4}\\S_{4}+\Lambda _{1}S_{3}+\Lambda _{2}S_{2}+\Lambda _{3}S_{1}&x^{3}\\S_{3}+\Lambda _{1}S_{2}+\Lambda _{2}S_{1}&x^{2}\\S_{2}+\Lambda _{1}S_{1}&x\\S_{1}\end{bmatrix}}={\begin{bmatrix}Q_{2}x^{8}\\Q_{1}x^{7}\\Q_{0}x^{6}\\0\\0\\0\\\Omega _{2}x^{2}\\\Omega _{1}x\\\Omega _{0}\end{bmatrix}}}$

Los términos intermedios son cero debido a la relación entre Λ y síndromes.

El algoritmo euclidiano extendido puede encontrar una serie de polinomios de la forma

Una _yo ( x ) S ( x ) + B _yo ( x ) x ^t = R _yo ( x )

donde el grado de R disminuye a medida que aumenta i . Una vez que el grado de R _i ( x ) < t / 2, entonces

Una _yo (x) = Λ (x)

B _yo (x) = −Q (x)

R _yo (x) = Ω (x).

No es necesario guardar B (x) y Q (x), por lo que el algoritmo se convierte en:

R ₋₁ = x ^t

R ₀ = S (x)

A ₋₁ = 0

A ₀ = 1

i = 0

mientras que el grado de R _i ≥ t / 2

yo = yo + 1

Q = R _i-2 / R _i-1

R _yo = R _i-2 - QR _i-1

A _yo = A _i-2 - QA _i-1

para establecer el término de orden inferior de Λ (x) en 1, divida Λ (x) y Ω (x) por A _i (0):

Λ (x) = A _yo / A _yo (0)

Ω (x) = R _yo / A _yo (0)

A _i (0) es el término constante (de orden inferior) de A _i .

Ejemplo

Con los mismos datos que en el ejemplo de Peterson – Gorenstein – Zierler anterior:

I	R i	A yo
−1	001 x 4 + 000 x 3 + 000 x 2 + 000 x + 000	000
0	925 x 3 + 762 x 2 + 637 x + 732	001
1	683 x 2 + 676 x + 024	697 x + 396
2	673 x + 596	608 x 2 + 704 x + 544

Λ (x) = A ₂ /544 = 329 x ² + 821 x + 001

Ω (x) = R ₂ /544 = 546 x + 732

Decodificador usando transformada discreta de Fourier

Se puede usar una transformada discreta de Fourier para decodificar. ^[14] Para evitar conflictos con los nombres de los síntomas, sea c ( x ) = s ( x ) la palabra en clave codificada. r ( x ) ye ( x ) son los mismos que los anteriores. Defina C ( x ), E ( x ) y R ( x ) como las transformadas discretas de Fourier de c ( x ), e ( x ) y r ( x ). Dado que r (x ) = c ( x ) + e ( x ), y dado que una transformada discreta de Fourier es un operador lineal, R ( x ) = C ( x ) + E ( x ).

Transforme r ( x ) en R ( x ) usando la transformada discreta de Fourier. Dado que el cálculo de una transformada discreta de Fourier es el mismo que el cálculo de los síndromes, los coeficientes t de R ( x ) y E ( x ) son los mismos que los de los síndromes:

${\displaystyle R_{j}=E_{j}=S_{j}=r(\alpha ^{j})}$

${\displaystyle {\text{for }}1\leq j\leq t}$

Uso a través de como síndromes (que son la misma) y generar el polinomio localizador de errores utilizando los métodos de cualquiera de los decodificadores de arriba.${\displaystyle R_{1}}$${\displaystyle R_{t}}$

Sea v = número de errores. Genere E (x) usando los coeficientes conocidos de , el polinomio del localizador de errores y estas fórmulas${\displaystyle E_{1}}$${\displaystyle E_{t}}$

${\displaystyle E_{0}=-{\frac {1}{\Lambda _{v}}}(E_{v}+\Lambda _{1}E_{v-1}+\cdots +\Lambda _{v-1}E_{1})}$

${\displaystyle E_{j}=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{v}E_{j-v})}$

${\displaystyle {\text{for }}t<j<n}$

Luego calcule C ( x ) = R ( x ) - E ( x ) y tome la transformada inversa (interpolación polinomial) de C ( x ) para producir c ( x ).

Decodificación más allá del límite de corrección de errores

El límite de Singleton establece que la distancia mínima d de un código de bloque lineal de tamaño ( n , k ) está delimitada en la parte superior por n  -  k  + 1. Se entendía que la distancia d limitaba la capacidad de corrección de errores a ⌊ (d- 1) / 2⌋. El código Reed-Solomon logra este límite con igualdad y, por lo tanto, puede corregir errores de hasta ⌊ (nk) / 2⌋. Sin embargo, este límite de corrección de errores no es exacto.

En 1999, Madhu Sudan y Venkatesan Guruswami del MIT publicaron "Decodificación mejorada de códigos Reed-Solomon y de geometría algebraica" introduciendo un algoritmo que permitía la corrección de errores más allá de la mitad de la distancia mínima del código. ^[15] Se aplica a los códigos Reed-Solomon y más generalmente a los códigos geométricos algebraicos . Este algoritmo produce una lista de palabras de código (es un algoritmo de decodificación de listas ) y se basa en la interpolación y factorización de polinomios y sus extensiones.${\displaystyle GF(2^{m})}$

Decodificación suave

Los métodos de decodificación algebraicos descritos anteriormente son métodos de decisión difícil, lo que significa que para cada símbolo se toma una decisión difícil sobre su valor. Por ejemplo, un decodificador podría asociar con cada símbolo un valor adicional correspondiente a la confianza del demodulador de canal en la exactitud del símbolo. El advenimiento de LDPC y códigos turbo , que emplean métodos iterados de decodificación de propagación de creencias de decisión suave para lograr un rendimiento de corrección de errores cercano al límite teórico , ha estimulado el interés en aplicar la decodificación de decisión suave a los códigos algebraicos convencionales. En 2003, Ralf Koetter y Alexander Vardypresentó un algoritmo de decodificación de lista algebraica de decisión suave en tiempo polinómico para códigos Reed-Solomon, que se basó en el trabajo de Sudan y Guruswami. ^[16] En 2016, Steven J. Franke y Joseph H. Taylor publicaron un nuevo decodificador de decisión suave. ^[17]

Ejemplo de Matlab

Codificador

Aquí presentamos una implementación simple de Matlab para un codificador.

función  [codificada] = rsEncoder ( msg, m, prim_poly, n, k )   % RSENCODER Codificar mensaje con el algoritmo Reed-Solomon % m es el número de bits por símbolo % prim_poly: polinomio primitivo p (x). Es decir, para DM es 301 % k es el tamaño del mensaje % n es el tamaño total (k + redundante) % Ejemplo: msg = uint8 ('Prueba') % enc_msg = rsEncoder (mensaje, 8, 301, 12, numel (mensaje));  % Obtener el alfa alfa = gf ( 2 , m , prim_poly );      % Obtener el polinomio generador de Reed-Solomon g (x) g_x = genpoly ( k , n , alpha );      % Multiplique la información por X ^ (nk), o simplemente rellene con ceros al final para % consigue espacio para agregar la información redundante msg_padded = gf ([ msg zeros ( 1 , n - k )], m , prim_poly );          % Obtiene el resto de la división del mensaje extendido por el % Reed-Solomon generando polinomio g (x) [ ~ , resto ] = deconv ( msg_padded , g_x );      % Ahora devuelve el mensaje con la información redundante encoded = msg_padded - resto ;     final% Encuentre el polinomio generador de Reed-Solomon g (x), por cierto, este es el% igual que la función rsgenpoly en matlabfunción  g = genpoly ( k, n, alpha )   g = 1 ;   % Una multiplicación en el campo galois es solo una convolución para k = mod ( 1 : n - k , n )         g = conv ( g , [ 1 alpha . ^ ( k )]);       finalfinal

Decodificador

Ahora la parte de decodificación:

función [decodificado, error_pos, error_mag, g, S] = rsDecoder ( codificado, m, prim_poly, n, k )  % RSDECODER Decodificar un mensaje codificado Reed-Solomon % Ejemplo: % [dec, ​​~, ~, ~, ~] = rsDecoder (enc_msg, 8, 301, 12, numel (msg)) max_errors = piso (( n - k ) / 2 );       orig_vals = codificado . x ;   % Inicializar el vector de error errores = ceros ( 1 , n );    g = [];   S = [];    % Obtener el alfa alfa = gf ( 2 , m , prim_poly );      % Encuentre los síndromes (marque si divide el mensaje por el generador % polinomio el resultado es cero) Synd = polyval ( codificado , alfa . ^ ( 1 : n - k ));        Síndromes = trim ( Synd );    % Si todos los síndromes son ceros (perfectamente divisibles) no hay errores si está vacío ( Síndromes . x )  decodificado = orig_vals ( 1 : k );   error_pos = [];   error_mag = [];   g = [];   S = Synd ;   volver ; final  % Prepárese para el algoritmo euclidiano (se utiliza para encontrar el error de localización % polinomios) r0 = [ 1 , ceros ( 1 , 2 * max_errors )]; r0 = gf ( r0 , m , prim_poly ); r0 = recorte ( r0 );               size_r0 = longitud ( r0 );   r1 = síndromes ;   f0 = gf ([ ceros ( 1 , tamaño_r0 - 1 ) 1 ], m , prim_poly );         f1 = gf ( ceros ( 1 , tamaño_r0 ), m , prim_poly );      g0 = f1 ; g1 = f0 ;       % ¿El algoritmo euclidiano sobre los polinomios r0 (x) y los síndromes (x) en % orden para encontrar el error al localizar el polinomio si bien es cierto  % Haz una división larga [ cociente , resto ] = deconv ( r0 , r1 );     % Agrega algunos ceros cociente = almohadilla ( cociente , longitud ( g1 ));     % Hallar cociente * g1 y pad c = conv ( cociente , g1 );    c = recorte ( c );   c = almohadilla ( c , longitud ( g0 ));     % Actualizar g como cociente g0 * g1 g = g0 - c ;      % Compruebe si el grado del resto (x) es menor que max_errors si todo ( resto ( 1 : end - max_errors ) == 0 )      romper ; final  % Actualice r0, r1, g0, g1 y elimine los ceros iniciales r0 = recorte ( r1 ); r1 = recortar ( resto );      g0 = g1 ; g1 = g ;      final  % Eliminar ceros a la izquierda g = recorte ( g );    % Encuentre los ceros del polinomio de error en este campo de Galois evalPoly = polyval ( g , alpha . ^ ( n - 1 : - 1 : 0 ));             error_pos = gf ( buscar ( evalPoly == 0 ), m );       % Si no se encuentra ninguna posición de error devolvemos el trabajo recibido, porque % básicamente no es nada que podamos hacer y devolvemos el mensaje recibido si isEmpty ( error_pos )  decodificado = orig_vals ( 1 : k );   error_mag = [];   volver ; final  % Preparar un sistema lineal para resolver el polinomio de error y encontrar el error % magnitudes size_error = longitud ( error_pos );   Syndrome_Vals = Síndromes . x ;   b (:, 1 ) = Syndrome_Vals ( 1 : size_error );    para idx = 1 : size_error      e = alpha . ^ ( idx * ( n - error_pos . x ));         err = e . x ;   er ( idx , :) = err ;    final  % Resuelve el sistema lineal error_mag = ( gf ( er , m , prim_poly ) \ gf ( b , m , prim_poly )) ' ;         % Ponga la magnitud del error en el vector de error errores ( error_pos . x ) = error_mag . x ;   % Trae este vector al campo galois errors_gf = gf ( errores , m , prim_poly );      % Ahora para corregir los errores, simplemente agregue con el código codificado decoded_gf = codificado ( 1 : k ) + errores_gf ( 1 : k );     decodificado = decoded_gf . x ;   final% Eliminar ceros a la izquierda de la matriz de Galoisfunción  gt = recortar ( g )   gx = g . x ;   gt = gf ( gx ( encontrar ( gx , 1 ) : fin ), g . m , g . prim_poly );       final% Agregar ceros a la izquierdafunción  xpad = pad ( x, k )   len = longitud ( x );   si ( len < k )    xpad = [ ceros ( 1 , k - len ) x ];       finalfinal

Decodificadores de vista originales de Reed Solomon

Los decodificadores descritos en esta sección utilizan la vista original de Reed Solomon de una palabra de código como una secuencia de valores polinomiales donde el polinomio se basa en el mensaje que se va a codificar. El codificador y el descodificador utilizan el mismo conjunto de valores fijos, y el descodificador recupera el polinomio de codificación (y, opcionalmente, un polinomio de localización de errores) del mensaje recibido.

Decodificador teórico

Reed y Solomon (1960) describieron un decodificador teórico que corrigió errores al encontrar el polinomio de mensajes más popular. El decodificador sólo conoce el conjunto de valores de${\displaystyle a_{1}}$${\displaystyle a_{n}}$y qué método de codificación se utilizó para generar la secuencia de valores de la palabra de código. Se desconocen el mensaje original, el polinomio y cualquier error. Un procedimiento de decodificación podría usar un método como la interpolación de Lagrange en varios subconjuntos de n valores de palabras de código tomados k a la vez para producir repetidamente polinomios potenciales, hasta que se produzca un número suficiente de polinomios coincidentes para eliminar razonablemente cualquier error en la palabra de código recibida. Una vez que se determina un polinomio, cualquier error en la palabra de código puede corregirse volviendo a calcular los valores de la palabra de código correspondiente. Desafortunadamente, en todos los casos, excepto en el más simple, hay demasiados subconjuntos, por lo que el algoritmo no es práctico. El número de subconjuntos es el coeficiente binomial ,${\displaystyle \textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$, y el número de subconjuntos es inviable incluso para códigos modestos. Para un código que pueda corregir 3 errores, el decodificador teórico ingenuo examinaría 359 mil millones de subconjuntos. ${\displaystyle (255,249)}$

Decodificador Berlekamp Welch

En 1986, se desarrolló un decodificador conocido como el algoritmo de Berlekamp-Welch como un decodificador que es capaz de recuperar el polinomio del mensaje original así como un polinomio "localizador" de errores que produce ceros para los valores de entrada que corresponden a errores, con complejidad temporal O (n ^ 3), donde n es el número de valores en un mensaje. El polinomio recuperado se utiliza para recuperar (recalcular según sea necesario) el mensaje original.

Ejemplo

Usando RS (7,3), GF (929) y el conjunto de puntos de evaluación a _i = i - 1

a = {0, 1, 2, 3, 4, 5, 6}

Si el polinomio del mensaje es

p ( x ) = 003 x ² + 002 x + 001

La palabra clave es

c = {001, 006, 017, 034, 057, 086, 121}

Los errores en la transmisión pueden causar que esto se reciba en su lugar.

b = c + e = {001, 006, 123, 456, 057, 086, 121}

Las ecuaciones clave son:

${\displaystyle b_{i}E(a_{i})-Q(a_{i})=0}$

Suponga el número máximo de errores: e = 2. Las ecuaciones clave se convierten en:

${\displaystyle b_{i}(e_{0}+e_{1}a_{i})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+q_{3}a_{i}^{3}+q_{4}a_{i}^{4})=-b_{i}a_{i}^{2}}$

${\displaystyle {\begin{bmatrix}001&000&928&000&000&000&000\\006&006&928&928&928&928&928\\123&246&928&927&925&921&913\\456&439&928&926&920&902&848\\057&228&928&925&913&865&673\\086&430&928&924&904&804&304\\121&726&928&923&893&713&562\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}000\\923\\437\\541\\017\\637\\289\end{bmatrix}}}$

Usando eliminación gaussiana :

${\displaystyle {\begin{bmatrix}001&000&000&000&000&000&000\\000&001&000&000&000&000&000\\000&000&001&000&000&000&000\\000&000&000&001&000&000&000\\000&000&000&000&001&000&000\\000&000&000&000&000&001&000\\000&000&000&000&000&000&001\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}006\\924\\006\\007\\009\\916\\003\end{bmatrix}}}$

Q ( x ) = 003 x ⁴ + 916 x ³ + 009 x ² + 007 x + 006

E ( x ) = 001 x ² + 924 x + 006

Q ( x ) / E ( x ) = P ( x ) = 003 x ² + 002 x + 001

Vuelva a calcular P (x) donde E (x) = 0: {2, 3} para corregir b dando como resultado la palabra de código corregida:

c = {001, 006, 017, 034, 057, 086, 121}

Decodificador Gao

En 2002, Shuhong Gao desarrolló un decodificador mejorado, basado en el algoritmo extendido de Euclid Gao_RS.pdf .

Ejemplo

Utilizando los mismos datos que en el ejemplo de Berlekamp Welch anterior:

${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$

${\displaystyle R_{0}=}$Interpolación de Lagrange de para i = 1 an${\displaystyle \{a_{i},b(a_{i})\}}$

${\displaystyle A_{-1}=0}$

${\displaystyle A_{0}=1}$

I	R i	A yo
−1	001 x 7 + 908 x 6 + 175 x 5 + 194 x 4 + 695 x 3 + 094 x 2 + 720 x + 000	000
0	055 x 6 + 440 x 5 + 497 x 4 + 904 x 3 + 424 x 2 + 472 x + 001	001
1	702 x 5 + 845 x 4 + 691 x 3 + 461 x 2 + 327 x + 237	152 x + 237
2	266 x 4 + 086 x 3 + 798 x 2 + 311 x + 532	708 x 2 + 176 x + 532

Q ( x ) = R ₂ = 266 x ⁴ + 086 x ³ + 798 x ² + 311 x + 532

E ( x ) = UNA ₂ = 708 x ² + 176 x + 532

dividir Q (x) y E (x) por el coeficiente más significativo de E (x) = 708. (Opcional)

Q ( x ) = 003 x ⁴ + 916 x ³ + 009 x ² + 007 x + 006

E ( x ) = 001 x ² + 924 x + 006

Q ( x ) / E ( x ) = P ( x ) = 003 x ² + 002 x + 001

Vuelva a calcular P ( x ) donde E ( x ) = 0: {2, 3} para corregir b dando como resultado la palabra de código corregida:

c = {001, 006, 017, 034, 057, 086, 121}

Ver también

• Código BCH
• Código cíclico
• Búsqueda de Chien
• Algoritmo de Berlekamp-Massey
• Corrección de errores hacia adelante
• Algoritmo de Berlekamp-Welch
• Código plegado Reed-Solomon

Notas

1. autores en ^[8] proporcionan resultados de simulación que muestran que para la misma tasa de código (1/6) los códigos turbo superan a los códigos concatenados de Reed-Solomon hasta 2 dB ( tasa de error de bits ).

Referencias

1. Reed y Solomon (1960)
2. D. Gorenstein y N. Zierler, "Una clase de códigos de corrección de errores lineales cíclicos en símbolos p ^ m", J. SIAM, vol. 9, págs.207-214, junio de 1961
3. Error al corregir códigos de W_Wesley_Peterson, 1961
4. Error al corregir códigos de W_Wesley_Peterson, segunda edición, 1972
5. Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa y Toshihiko Namekawa. Un método para resolver la ecuación clave para decodificar códigos Goppa. Information and Control, 27: 87–99, 1975.
6. Immink, KAS (1994), "Códigos Reed-Solomon y el disco compacto", en Wicker, Stephen B .; Bhargava, Vijay K. (eds.), Códigos Reed-Solomon y sus aplicaciones , IEEE Press , ISBN 978-0-7803-1025-4
7. J. Hagenauer, E. Offer y L. Papke, Códigos de Reed Solomon y sus aplicaciones. Nueva York IEEE Press, 1994 - p. 433
8. Andrews, Kenneth S., et al. "El desarrollo de códigos turbo y LDPC para aplicaciones en el espacio profundo". Actas del IEEE 95.11 (2007): 2142-2156. Error de cita: la referencia denominada "Andrews, 2007" se definió varias veces con contenido diferente (consulte la página de ayuda ).
9. Ver Lin y Costello (1983 , p. 171), por ejemplo.
10. "Expresiones analíticas utilizadas en bercoding y BERTool" . Archivado desde el original el 1 de febrero de 2019 . Consultado el 1 de febrero de 2019 .
11. Pfender, Florian; Ziegler, Günter M. (septiembre de 2004), "Kissing Numbers, Sphere Packings, and Some Unexpected Proofs" (PDF) , Notices of the American Mathematical Society , 51 (8): 873–883, archivado (PDF) desde el original en 2008-05-09 , consultado el 2009-09-28 . Explica el teorema de Delsarte-Goethals-Seidel como se usa en el contexto del código de corrección de errores para discos compactos .
12. D. Gorenstein y N. Zierler, "Una clase de códigos de corrección de errores lineales cíclicos en símbolos p ^ m", J. SIAM, vol. 9, págs. 207–214, junio de 1961
13. Error al corregir códigos por W Wesley Peterson, 1961
14. Shu Lin y Daniel J. Costello Jr, "Codificación de control de errores" segunda edición, págs. 255-262, 1982, 2004
15. Guruswami, V .; Sudan, M. (septiembre de 1999), "Decodificación mejorada de códigos Reed-Solomon y códigos de geometría algebraica", IEEE Transactions on Information Theory , 45 (6): 1757-1767, CiteSeerX 10.1.1.115.292 , doi : 10.1109 / 18.782097 
16. Koetter, Ralf; Vardy, Alexander (2003). "Decodificación algebraica de decisión suave de códigos Reed-Solomon". Transacciones IEEE sobre teoría de la información . 49 (11): 2809-2825. CiteSeerX 10.1.1.13.2021 . doi : 10.1109 / TIT.2003.819332 . 
17. Franke, Steven J .; Taylor, Joseph H. (2016). "Decodificador de decisión suave de código abierto para el código JT65 (63,12) Reed-Solomon" (PDF) . QEX (mayo / junio): 8–17. Archivado (PDF) desde el original el 9 de marzo de 2017 . Consultado el 7 de junio de 2017 .

Lectura adicional

• Gill, John (sf), EE387 Notes # 7, Handout # 28 (PDF) , Stanford University, archivado del original (PDF) el 30 de junio de 2014 , consultado el 21 de abril de 2010
• Hong, Jonathan; Vetterli, Martin (agosto de 1995), "Algoritmos simples para decodificación BCH" (PDF) , IEEE Transactions on Communications , 43 (8): 2324-2333, doi : 10.1109 / 26.403765
• Lin, Shu; Costello, Jr., Daniel J. (1983), Codificación de control de errores: fundamentos y aplicaciones , Nueva Jersey, Nueva Jersey: Prentice-Hall, ISBN 978-0-13-283796-5
• Massey, JL (1969), "Síntesis de registro de desplazamiento y decodificación BCH" (PDF) , IEEE Transactions on Information Theory , IT-15 (1): 122-127, doi : 10.1109 / tit.1969.1054260
• Peterson, Wesley W. (1960), "Procedimientos de codificación y corrección de errores para los códigos Bose-Chaudhuri", IRE Transactions on Information Theory , IT-6 (4): 459–470, doi : 10.1109 / TIT.1960.1057586
• Reed, Irving S .; Solomon, Gustave (1960), "Códigos polinomiales sobre ciertos campos finitos", Revista de la Sociedad de Matemáticas Industriales y Aplicadas , 8 (2): 300-304, doi : 10.1137 / 0108018
• Welch, LR (1997), La vista original de los códigos Reed-Solomon (PDF) , Notas de la conferencia
• Berlekamp, ​​Elwyn R. (1967), decodificación BCH no binaria , Simposio internacional sobre teoría de la información, San Remo, Italia
• Berlekamp, ​​Elwyn R. (1984) [1968], Teoría de la codificación algebraica (edición revisada), Laguna Hills, CA: Aegean Park Press, ISBN 978-0-89412-063-3
• Cipra, Barry Arthur (1993), "Los códigos ubicuos Reed-Solomon" , SIAM News , 26 (1)
• Forney, Jr., G. (octubre de 1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory , 11 (4): 549–557, doi : 10.1109 / TIT.1965.1053825
• Koetter, Ralf (2005), Reed-Solomon Codes , MIT Lecture Notes 6.451 (video), archivado desde el original el 13 de marzo de 2013
• MacWilliams, FJ; Sloane, NJA (1977), The Theory of Error-Correcting Codes , Nueva York, NY: North-Holland Publishing Company
• Reed, Irving S .; Chen, Xuemin (1999), Codificación de control de errores para redes de datos , Boston, MA: Kluwer Academic Publishers

Enlaces externos

Información y tutoriales

• Introducción a los códigos Reed-Solomon: principios, arquitectura e implementación (CMU)
• Un tutorial sobre la codificación Reed-Solomon para la tolerancia a fallas en sistemas similares a RAID
• Decodificación suave algebraica de códigos Reed-Solomon
• Wikiversity: códigos Reed-Solomon para codificadores
• Informe técnico de investigación y desarrollo de la BBC WHP031
• Geisel, William A. (agosto de 1990), Tutorial sobre codificación de corrección de errores Reed-Solomon (PDF) , Memorando técnico, NASA , TM-102162
• Gao, Shuhong (enero de 2002), nuevo algoritmo para decodificar códigos Reed-Solomon (PDF) , Clemson
• Códigos concatenados por el Dr. Dave Forney (scholarpedia.org).

Implementaciones

• Códec Schifra de código abierto C ++ Reed-Solomon
• Biblioteca RSCode de Henry Minsky, codificador / decodificador Reed-Solomon
• Biblioteca de decodificación suave C ++ Reed – Solomon de código abierto
• Implementación de Matlab de errores y borrados Decodificación Reed-Solomon
• Implementación de octava en paquete de comunicaciones
• Implementación en Python puro de un códec Reed-Solomon