Corrección de errores de Reed-Solomon

Error-correcting codes

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, incluidas tecnologías de consumo como MiniDiscs , CD , DVD , discos Blu-ray , códigos QR , Data Matrix , 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 sobre 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ímbolo. Al agregar t = n  −  k símbolos de verificación a los datos, un código Reed-Solomon puede detectar (pero no corregir) cualquier combinación de hasta t símbolos erróneos, o localizar y corregir hasta ⌊ t /2⌋ símbolos erróneos en ubicaciones desconocidas. Como código de borrado , puede corregir hasta t borrados 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 bit de ráfaga múltiple, ya que una secuencia de b  + 1 errores de bit consecutivos 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 original.

Historia

Los códigos Reed-Solomon fueron desarrollados en 1960 por Irving S. Reed y Gustave Solomon , que en ese entonces eran miembros del personal del Laboratorio Lincoln del MIT . Su artículo seminal se tituló "Códigos polinómicos sobre ciertos campos finitos" (Reed y Solomon 1960). El esquema de codificación original descrito en el artículo de Reed y Solomon utilizaba un polinomio variable basado en el mensaje a codificar, donde solo un conjunto fijo de valores (puntos de evaluación) a codificar son conocidos por el codificador y el decodificador. El decodificador teórico original generaba polinomios potenciales basados ​​en subconjuntos de k (longitud del mensaje no codificado) de n (longitud del mensaje codificado) valores de un mensaje recibido, eligiendo el polinomio más popular como el correcto, lo que era poco práctico para todos los casos, excepto para los más simples. Esto se resolvió inicialmente cambiando el esquema original por 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 lentos que los esquemas BCH. El resultado de esto es que hay dos tipos principales de códigos Reed Solomon, los que utilizan el esquema de codificación original y los que utilizan el esquema de codificación BCH.

También en 1960, un decodificador polinomial fijo práctico 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 describen 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 Reed Solomon podí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 , que desde entonces se conoce como algoritmo de decodificación 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 . Hoy en día, 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 los códigos Bose-Chaudhuri-Hocquenghem (BCH) . Por ejemplo, los códigos Reed-Solomon se utilizan en el estándar de transmisión de video digital (DVB) DVB-S , junto con un código interno convolucional , pero los códigos BCH se utilizan con LDPC en su sucesor, DVB-S2 .

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

En 1996, Madhu Sudan y otros desarrollaron variaciones de los decodificadores de esquema originales llamados decodificadores de lista o decodificadores suaves, y el trabajo continúa en este tipo de decodificadores (véase el algoritmo de decodificación de lista de Guruswami–Sudan) .

En 2002, Shuhong Gao desarrolló otro decodificador de esquema original basado en el algoritmo euclidiano extendido . ^[6]

Aplicaciones

Almacenamiento de datos

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

La codificación Reed-Solomon es un componente clave del disco compacto . Fue el primer uso de codificación de corrección de errores fuerte en un producto de consumo producido en masa, y DAT y DVD utilizan 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 de intercalación 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 hasta 2 errores de bytes por bloque de 32 bytes. Más importante aún, marca como borrados cualquier bloque incorregible, es decir, bloques con más de 2 errores de bytes. Los bloques decodificados de 28 bytes, con indicaciones de borrado, luego son distribuidos por el desentrelazador a diferentes bloques del código externo (28,24). Gracias al desentrelazado, un bloque de 28 bytes borrado del código interno se convierte en un único byte borrado en cada uno de los 28 bloques del código externo. 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 por completo 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 son causados ​​casi con certeza por errores de seguimiento que hacen que el láser salte de pista, no por ráfagas de errores incorregibles. ^[7]

Los DVD utilizan 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 Reed-Solomon también se utiliza en archivos de parchivos que se suelen publicar junto con archivos multimedia en USENET . El servicio de almacenamiento en línea distribuido Wuala (interrumpido en 2015) también utilizaba Reed-Solomon para 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 escáner 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 se utiliza en 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 supone un código de RS( N ,  K ) que da como resultado N palabras de código de longitud N símbolos que almacenan cada una K símbolos de datos, que se generan y 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 observe que es menor. En conclusión, N es generalmente 2 K , lo que significa que se debe recibir al menos la mitad de todas las palabras de código enviadas para reconstruir todas las palabras de código enviadas.

Los códigos Reed-Solomon también se utilizan en sistemas xDSL y en las especificaciones del protocolo de comunicaciones espaciales del CCSDS como una forma de corrección de errores de avance .

Transmisión espacial

Sistema de codificación concatenado de espacio profundo. ^[8] 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 vuelto muy extendida en las comunicaciones por espacio profundo y por satélite (por ejemplo, en la transmisión digital directa).

Los decodificadores Viterbi tienden a producir errores en ráfagas cortas. La mejor manera de corregir estos errores de ráfaga es mediante códigos Reed-Solomon cortos o simplificados.

Las versiones modernas de la codificación convolucional decodificada Reed–Solomon/Viterbi concatenada se utilizaron y se utilizan en las misiones Mars Pathfinder , Galileo , Mars Exploration Rover y Cassini , donde funcionan dentro de aproximadamente 1–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 :

Construcciones (codificación)

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 , una longitud de bloque y una longitud de mensaje , con . El conjunto de símbolos del alfabeto se interpreta como el cuerpo finito de orden , y por lo tanto, debe 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 es una constante y, además, la longitud del bloque es igual o uno menos que el tamaño del alfabeto, es decir, o . ^{[ cita requerida ]} ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k<n\leq q}$ ${\displaystyle F}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle R={\frac {k}{n}}}$ ${\displaystyle n=q}$ ${\displaystyle n=q-1}$

La visión original de Reed y Solomon: la palabra 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 de código del código Reed-Solomon es una secuencia de valores de función de un polinomio de grado menor que . Para obtener una palabra de código 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 de grado menor que k , sobre el campo finito con elementos. A su vez, el polinomio p se evalúa en n ≤ q puntos distintos del campo 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, α , α ² , ..., α ^{n −1} }, ... , donde α es un elemento primitivo de F . ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle F}$ ${\displaystyle q}$ ${\displaystyle a_{1},\dots ,a_{n}}$

Formalmente, el conjunto de palabras clave del código Reed-Solomon se define de la siguiente manera: Dado que dos polinomios distintos de grado menor que concuerdan en la mayoría de los puntos, esto significa que dos palabras clave del código Reed-Solomon difieren en al menos posiciones. Además, hay dos polinomios que concuerdan 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. Este equilibrio entre la distancia relativa y la tasa es asintóticamente óptimo ya que, por el límite Singleton , cada código satisface . Al ser un código que logra este equilibrio óptimo, el código Reed-Solomon pertenece a la clase de códigos separables por distancia máxima . ${\displaystyle \mathbf {C} }$ $${\displaystyle \mathbf {C} ={\Bigl \{}\;{\bigl (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\bigr )}\;{\Big |}\;p{\text{ is a polynomial over }}F{\text{ of degree }}<k\;{\Bigr \}}\,.}$$ ${\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}$

Si bien el número de polinomios diferentes de grado menor que k y el número de mensajes diferentes son ambos iguales a , y por lo tanto cada mensaje puede mapearse de manera única a 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 . El último procedimiento de codificación, si bien es ligeramente menos eficiente, 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. ${\displaystyle q^{k}}$ ${\displaystyle a_{1},\dots ,a_{k}}$

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 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: Esta función es una asignación lineal , es decir, satisface para la siguiente matriz con elementos de : ${\displaystyle m=(m_{0},\dots ,m_{k-1})\in F^{k}}$ ${\displaystyle p_{m}}$ $${\displaystyle p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}\,.}$$ ${\displaystyle m}$ ${\displaystyle p_{m}}$ ${\displaystyle n}$ ${\displaystyle a_{0},\dots ,a_{n-1}}$ ${\displaystyle F}$ ${\displaystyle C:F^{k}\to F^{n}}$ $${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$ ${\displaystyle C}$ ${\displaystyle C(m)=Am}$ ${\displaystyle n\times k}$ ${\displaystyle A}$ ${\displaystyle F}$ $${\displaystyle C(m)=Am={\begin{bmatrix}1&a_{0}&a_{0}^{2}&\dots &a_{0}^{k-1}\\1&a_{1}&a_{1}^{2}&\dots &a_{1}^{k-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&a_{n-1}&a_{n-1}^{2}&\dots &a_{n-1}^{k-1}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

Esta matriz es 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ásica, su matriz generadora es . ${\displaystyle F}$ ${\displaystyle A}$

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

Existe un procedimiento de codificación alternativo que produce un código Reed-Solomon sistemático . Aquí, utilizamos un polinomio diferente . En esta variante, el polinomio se define como el único polinomio de grado menor que tal que Para calcular este polinomio a partir de , se puede utilizar la interpolación de Lagrange . Una vez que se ha encontrado, se evalúa en los otros puntos . ${\displaystyle p_{m}}$ ${\displaystyle p_{m}}$ ${\displaystyle k}$ $${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$ ${\displaystyle p_{m}}$ ${\displaystyle m}$ ${\displaystyle a_{k},\dots ,a_{n-1}}$

$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$

Esta variante es sistemática ya que las primeras entradas, , son exactamente por la definición de . ${\displaystyle k}$ ${\displaystyle p_{m}(a_{0}),\dots ,p_{m}(a_{k-1})}$ ${\displaystyle m_{0},\dots ,m_{k-1}}$ ${\displaystyle p_{m}}$

Transformada de Fourier discreta y su inversa

Una transformada de Fourier discreta es esencialmente lo mismo que el procedimiento de codificación; utiliza el polinomio generador para mapear un conjunto de puntos de evaluación en los valores del mensaje como se muestra arriba: ${\displaystyle p_{m}}$ $${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$

La transformada de Fourier inversa podría utilizarse para convertir un conjunto libre de errores de valores de mensajes n < q 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 utilizados para codificar el mensaje debe ser un conjunto de potencias crecientes de α : $${\displaystyle a_{i}=\alpha ^{i}}$$ $${\displaystyle a_{0},\dots ,a_{n-1}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$$

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

La visión del BCH: La palabra clave como una secuencia de coeficientes

En esta vista, el mensaje se interpreta como los coeficientes de un polinomio . El emisor 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 del 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)=\left(x-\alpha ^{i}\right)\left(x-\alpha ^{i+1}\right)\cdots \left(x-\alpha ^{i+n-k-1}\right)=g_{0}+g_{1}x+\cdots +g_{n-k-1}x^{n-k-1}+x^{n-k}}$$

Para un "código de sentido estricto", . ${\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ática

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 añade 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 eligen exactamente de tal manera que se vuelven divisibles por . Entonces, los coeficientes de son una subsecuencia de los coeficientes de . Para obtener un código que sea sistemático en general, construimos el polinomio del mensaje interpretando el mensaje como la secuencia de sus coeficientes. ${\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)}$

Formalmente, la construcción se realiza multiplicando por para dejar lugar a los símbolos de verificación, dividiendo ese producto por para hallar 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 lo tanto, la siguiente definición de la palabra clave 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 de hecho elementos de , es decir, son divisibles por el polinomio generador : ^[10] ${\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 de Hamming mínima 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 límite Singleton . Un código de este tipo también se denomina código separable por distancia máxima (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, equivalentemente, 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, las ubicaciones de los errores se conocen de antemano (por ejemplo, "información secundaria" en las relaciones señal-ruido del demodulador ); estas se denominan borrados . 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 se puede corregir siempre que se cumpla la relación 2 E + S ≤ n − k , donde es el número de errores y es el número de borrados en el bloque. ${\displaystyle n-k}$ ${\displaystyle (n-k)/2}$ ${\displaystyle E}$ ${\displaystyle S}$

Rendimiento teórico de la 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 : ^[11] y para otros esquemas de modulación: donde , , , es la tasa de error de símbolo en el caso AWGN no codificado y es el orden de modulación. $${\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 }}$$ $${\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 }}$$ ${\textstyle 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 utilizar un campo finito con elementos. En este caso, cada símbolo puede representarse como un valor de -bit. El emisor envía los puntos de datos como bloques codificados, y el número de símbolos en el bloque codificado es . Por lo 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 código y es capaz de corregir hasta 16 errores de símbolo por bloque. ${\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)}$

Las propiedades del código Reed-Solomon que se analizaron anteriormente lo hacen especialmente adecuado para aplicaciones en las que los errores ocurren en ráfagas . Esto se debe a que al código no le importa cuántos bits de un símbolo tienen errores: si varios bits de un símbolo están dañados, solo se considera un error único. 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 opción en comparación con un código binario.

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 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 acorta ( consulte "Observaciones" al final de esta sección ). Los bits "faltantes" en un código acortado deben completarse con ceros o unos, dependiendo de si los datos se complementan o no. (Para decirlo de otra manera, si los símbolos se invierten, entonces el relleno de ceros debe invertirse a un relleno de uno). Por esta razón, es obligatorio que el sentido de los datos (es decir, verdaderos o complementados) se resuelva antes de la decodificación Reed-Solomon.

El que el código Reed-Solomon sea cíclico o no depende de detalles sutiles de la construcción. En la visión original de Reed y Solomon, donde las palabras clave son los valores de un polinomio, se 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 cuerpo , entonces por definición todos los elementos no nulos 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 clave ; dado que se cumple, esta palabra clave es el desplazamiento cíclico a la izquierda de la palabra clave original derivada de . Por lo tanto, elegir una secuencia de potencias de raíces primitivas como puntos de evaluación hace que el código Reed-Solomon de la visión original sea cíclico . Los códigos Reed-Solomon en la visión BCH son siempre cíclicos porque los códigos BCH son cíclicos . ${\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}}$ ${\displaystyle p}$

Observaciones

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 de origen con 95 ceros binarios y no transmitiéndolos. En el decodificador, la misma parte del bloque se carga localmente con ceros binarios.

El código QR, versión 3 (29×29) utiliza bloques intercalados. El mensaje tiene 26 bytes de datos y está codificado utilizando dos bloques de código Reed-Solomon. Cada bloque es un código Reed Solomon (255,233) abreviado a un código (35,13).

El teorema de Delsarte–Goethals–Seidel ^[12] ilustra un ejemplo de aplicación de códigos Reed–Solomon acortados. Paralelamente al acortamiento, una técnica conocida como perforació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 decodificador.

Decodificador Peterson-Gorenstein-Zierler

Daniel Gorenstein y Neal Zierler desarrollaron un decodificador que Zierler describió en un informe del Laboratorio Lincoln del MIT en enero de 1960 y más tarde en un artículo en junio de 1961. ^[13] El decodificador Gorenstein-Zierler y el trabajo relacionado con los códigos BCH se describen en un libro Error Correcting Codes de W. Wesley Peterson (1961). ^[14]

Formulación

El mensaje transmitido, , se considera 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 Reed-Solomon, s ( x ) es divisible por el polinomio generador g ( x ): donde α es un elemento primitivo. $${\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}$$

Como s ( x ) es un múltiplo del generador g ( x ), se deduce que "hereda" todas sus raíces. Por lo tanto, $${\displaystyle s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0}$$ $${\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}}$$

El coeficiente e _i será cero si no hay error en esa potencia de x y distinto de cero si hay error. Si hay ν errores en potencias distintas i _k de x , entonces $${\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}}$$

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

Descodificación del síndrome

El decodificador comienza evaluando el polinomio tal como se recibe en los puntos . Llamamos a los resultados de esa evaluación "síndromes", S _j . Se definen como: Tenga en cuenta que debido a que tiene raíces en , como se muestra en la sección anterior. ${\displaystyle \alpha ^{1}\dots \alpha ^{n-k}}$ $${\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}\left(\alpha ^{j}\right)^{i_{k}},\quad j=1,2,\ldots ,n-k\end{aligned}}}$$ ${\displaystyle s(\alpha ^{j})=0}$ ${\displaystyle s(x)}$ ${\displaystyle \alpha ^{j}}$

La ventaja de observar los síndromes es que el polinomio del mensaje se elimina. 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 está transmitiendo. Si todos los síndromes son cero, el algoritmo se detiene aquí e informa que el mensaje no se corrompió durante el tránsito.

Localizadores de errores y valores de error

Para mayor comodidad, 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 errores 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 ya que . ${\displaystyle (\alpha ^{j})^{i_{k}}=\alpha ^{j*i_{k}}=(\alpha ^{i_{k}})^{j}=X_{k}^{j}}$

Los síndromes dan un sistema de ecuaciones n − k ≥ 2 ν con 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 se puede resolver fácilmente para los valores de error de 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 &\ddots &\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 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, obteniéndose Y _k

En la variante de este algoritmo en la que ya se conocen las ubicaciones de los errores (cuando se utiliza como código de borrado ), este es el final. Las ubicaciones de los errores ( X _k ) ya se conocen mediante algún otro método (por ejemplo, en una transmisión FM, las secciones en las que el flujo de bits no era claro o estaba superado por interferencias se pueden determinar de forma probabilística 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 de hasta , en lugar de solo los utilizados hasta ahora. Por eso es necesario agregar el doble de símbolos correctores de errores de los que se pueden corregir sin conocer sus ubicaciones. ${\displaystyle 2v}$ ${\displaystyle v}$

Polinomio localizador de errores

Existe una relación de recurrencia lineal que da lugar a un sistema de ecuaciones lineales. Al resolver dichas ecuaciones se identifican las ubicaciones de error X _k .

Defina el polinomio 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 desprende de la construcción de notación de producto anterior, ya que si entonces uno de los términos multiplicados será cero , lo que hace que todo el polinomio evalúe a 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 entero tal que . Multiplique 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.\\[1ex]&Y_{k}X_{k}^{j+\nu }\left(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu }\right)=0.\\[1ex]&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.\\[1ex]&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}}}$$

Sume k = 1 a ν y seguirá siendo cero. $${\displaystyle \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}$$

Reúne cada término en su propia suma. $${\displaystyle \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}$$

Extrae los valores constantes que no se ven afectados por la suma. ${\displaystyle \Lambda }$ $${\displaystyle \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}$$

Estas sumas son ahora equivalentes a los valores del síndrome, que conocemos y podemos sustituir. Esto, por tanto, 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 obtenemos ${\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 }}$$

Recordemos que se eligió j como cualquier número entero entre 1 y v inclusive, y esta equivalencia es verdadera para todos y cada uno de esos valores. Por lo tanto, tenemos v ecuaciones lineales, no solo una. Este sistema de ecuaciones lineales puede, por lo tanto, resolverse para los coeficientes Λ _i del polinomio de ubicación de error: 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 supone el valor más grande para un ensayo ν y establece 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 ensayo es el número de errores. Si el sistema lineal no se puede resolver, entonces el ensayo ν se reduce en uno y se examina el siguiente sistema más pequeño. (Gill nd, p. 35) $${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\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}}}$$

Encuentra las raíces del polinomio localizador de errores

Utilice los coeficientes Λ _i encontrados en el último paso para construir el polinomio de localización de errores. Las raíces del polinomio de localización de errores se pueden encontrar mediante una búsqueda exhaustiva. Los localizadores de errores X _k son los recíprocos de esas raíces. El orden de los coeficientes del polinomio de localización de errores se puede invertir, en cuyo caso las raíces de ese polinomio invertido son los localizadores de errores (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 utilizando el algoritmo de Forney .

Calcular las ubicaciones de error

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 códigos de barras PDF417 ) para un código RS(7,3). El polinomio generador es 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. Los errores en la transmisión pueden hacer que se reciba esta en su lugar. Los síndromes se calculan evaluando r en potencias de α . $${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}$$ $${\displaystyle s_{r}(x)=p(x)\,x^{t}{\bmod {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}$$ $${\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474}$$ $${\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 la 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 utiliza:

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

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

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

Ω(x) = S(x) Λ(x) módulo x ⁴ = 546 x + 732

Λ'(x) = 658 x + 821

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

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

Restando del polinomio recibido r ( x ) se reproduce la palabra clave original s . ${\displaystyle e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}}$

Descodificador Berlekamp–Massey

El algoritmo de Berlekamp–Massey es un procedimiento iterativo alternativo para hallar el polinomio localizador de errores. Durante cada iteración, calcula una discrepancia en función de una instancia actual de Λ( x ) con un número supuesto de errores e : y luego ajusta Λ( x ) y e de modo que un Δ recalculado sea cero. El artículo Algoritmo de Berlekamp–Massey contiene una descripción detallada del procedimiento. En el siguiente ejemplo, se utiliza C ( x ) para representar Λ( x ). $${\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}$$

Ejemplo

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

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

Decodificador euclidiano

Otro método iterativo para calcular tanto el polinomio localizador de error como el polinomio de valor de 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 {\begin{aligned}S(x)&=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}\\[1ex]\Lambda (x)&=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1\\[1ex]\Omega (x)&=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}\end{aligned}}}$$

La ecuación clave es: $${\displaystyle \Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)}$$

Para t = 6 y e = 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 medios son cero debido a la relación entre Λ y los síndromes.

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

A _i ( x ) S ( x ) + B _i ( x ) x ^t = R _i ( x )

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

A _i ( x ) = Λ( x )

B _i ( x ) = −Q( x )

R _i ( x ) = Ω( x ).

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

R −1  := x t R 0  := S ( x ) A −1  := 0 A 0  := 1 i  := 0 mientras que el grado de R i ≥ t /2 i  := i + 1 Q  := R i -2 / R i -1  R i  := R i -2 - Q  R i -1  A i  := A i -2 - Q  A i -1

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

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

Ω( _x ) = Ri _/ Ai (0 )

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

Ejemplo

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

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

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

Decodificador que utiliza transformada de Fourier discreta

Se puede utilizar una transformada de Fourier discreta para la decodificación. ^[15] Para evitar conflictos con los nombres de los síndromes, sea c ( x ) = s ( x ) la palabra clave codificada. r ( x ) y e ( x ) son iguales a los anteriores. Defina C ( x ), E ( x ) y R ( x ) como las transformadas de Fourier discretas de c ( x ), e ( x ) y r ( x ). Dado que r ( x ) = c ( x ) + e ( x ), y dado que una transformada de Fourier discreta es un operador lineal, R ( x ) = C ( x ) + E ( x ).

Transformar r ( x ) en R ( x ) utilizando la transformada de Fourier discreta. Dado que el cálculo de una transformada de Fourier discreta 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})\qquad {\text{for }}1\leq j\leq t}$$

Utilice como síndromes (son lo mismo) y genere el polinomio localizador de errores utilizando los métodos de cualquiera de los decodificadores anteriores. ${\displaystyle R_{1}}$ ${\displaystyle R_{t}}$

Sea v = número de errores. Genere E ( x ) utilizando los coeficientes conocidos para , el polinomio localizador de errores y estas fórmulas ${\displaystyle E_{1}}$ ${\displaystyle E_{t}}$ $${\displaystyle {\begin{aligned}E_{0}&=-{\frac {1}{\Lambda _{v}}}(E_{v}+\Lambda _{1}E_{v-1}+\cdots +\Lambda _{v-1}E_{1})\\E_{j}&=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{v}E_{j-v})&{\text{for }}t<j<n\end{aligned}}}$$

Luego calcula C ( x ) = R ( x ) − E ( x ) y toma la transformada inversa (interpolación polinomial) de C ( x ) para producir c ( x ).

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

El límite Singleton establece que la distancia mínima d de un código de bloque lineal de tamaño ( n , k ) está limitada superiormente por n − k + 1 . Generalmente, 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 hasta ⌊( n − k ) / 2⌋ errores. Sin embargo, este límite de corrección de errores no es exacto.

En 1999, Madhu Sudan y Venkatesan Guruswami del MIT publicaron "Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes" (Descodificación mejorada de códigos Reed–Solomon y de geometría algebraica), en el que se presentaba un algoritmo que permitía la corrección de errores más allá de la mitad de la distancia mínima del código. ^[16] Se aplica a los códigos Reed–Solomon y, de forma más general, 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 sobre y sus extensiones. ${\displaystyle GF(2^{m})}$

En 2023, basándose en tres trabajos interesantes, ^{[17] [18] [19]} los teóricos de la codificación demostraron que los códigos Reed-Solomon definidos sobre puntos de evaluación aleatorios pueden alcanzar una capacidad de decodificación de listas (hasta n − k errores) sobre alfabetos de tamaño lineal con alta probabilidad. Sin embargo, este resultado es combinatorio en lugar de algorítmico.

Descodificación suave

Los métodos de decodificación algebraica descritos anteriormente son métodos de decisión dura, lo que significa que para cada símbolo se toma una decisión dura 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 corrección del símbolo. La llegada de los códigos LDPC y 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 Vardy presentaron un algoritmo de decodificación de lista algebraica de decisión suave en tiempo polinomial para códigos Reed-Solomon, que se basó en el trabajo de Sudan y Guruswami. ^[20] En 2016, Steven J. Franke y Joseph H. Taylor publicaron un novedoso decodificador de decisión suave. ^[21]

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 Codifica el 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(msg, 8, 301, 12, número(msg)); % Obtenga el alfa alfa = gf ( 2 , m , prim_poly );     % Obtenga el polinomio generador de Reed-Solomon g(x) g_x = genpoly ( k , n , alfa );     % Multiplica la información por X^(nk), o simplemente rellena con ceros al final para % obtiene espacio para agregar la información redundante msg_padded = gf ([ msg ceros ( 1 , n - k )], m , prim_poly );         % Obtener el resto de la división del mensaje extendido por el % Polinomio generador de Reed-Solomon g(x) [ ~ , resto ] = deconv ( msg_padded , g_x );     % Ahora devuelve el mensaje con la información redundante codificado = msg_padded - resto ;    fin% Encuentra 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, alfa )   g = 1 ;   % Una multiplicación en el campo de Galois es simplemente una convolución para k = mod ( 1 : n - k , n )         g = conv ( g , [ 1 alfa .^ ( k )]);       finfin

Descifrador

Ahora la parte de decodificación:

función [decodificada, error_pos, error_mag, g, S] = rsDecoder ( codificada, m, prim_poly, n, k )  % RSDECODER Decodifica un mensaje codificado Reed-Solomon % Ejemplo: % [dec, ​​~, ~, ~, ~] = rsDecoder(enc_msg, 8, 301, 12, número(msg)) max_errors = piso (( n - k ) / 2 );       orig_vals = codificado . x ;   % Inicializar el vector de error errores = ceros ( 1 , n );    g = [];   S = [];   % Obtenga el alfa alfa = gf ( 2 , m , prim_poly );     % Encuentra los síndromes (Comprueba si divides el mensaje por el generador) % polinomio el resultado es cero) Synd = polival ( codificado , alfa .^ ( 1 : n - k ));        Síndromes = trim ( Synd );   % Si todos los síndromes son ceros (perfectamente divisibles) no hay errores si esta vacio ( Síndromes . x )  decodificado = orig_vals ( 1 : k );   error_pos = [];   error_mag = [];   g = [];   S = Sínd ;   devolver ; fin % Prepárese para el algoritmo euclidiano (se utiliza para encontrar la ubicación del error) % polinomios) r0 = [ 1 , ceros ( 1 , 2 * max_errors )]; r0 = gf ( r0 , m , prim_poly ); r0 = trim ( r0 );               tamaño_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 ;      % ¿Se aplica el algoritmo euclidiano a los polinomios r0(x) y Síndromes(x) en % orden para encontrar el error al localizar el polinomio Aunque es cierto  % Hacer una división larga [ cociente , resto ] = deconv ( r0 , r1 );     % Añade algunos ceros cociente = pad ( cociente , longitud ( g1 ));    % Encuentra el cociente*g1 y rellena c = conv ( cociente , g1 );    c = recortar ( c );   c = almohadilla ( c , longitud ( g0 ));    % Actualizar g como g0-cociente*g1 g = g0 - c ;     % Comprueba si el grado del resto(x) es menor que max_errors si todo ( resto ( 1 : fin - max_errors ) == 0 )      romper ; fin % Actualizar r0, r1, g0, g1 y eliminar los ceros iniciales r0 = trim ( r1 ); r1 = trim ( resto );      g0 = g1 ; g1 = g ;      fin % Eliminar ceros iniciales g = recorte ( g );   % Encuentra los ceros del polinomio de error en este campo de Galois evalPoly = polyval ( g , alfa .^ ( n - 1 : - 1 : 0 ));             error_pos = gf ( find ( 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 esta vacio ( error_pos )  decodificado = orig_vals ( 1 : k );   error_mag = [];   devolver ; fin % Prepare un sistema lineal para resolver el polinomio de error y encuentre el error. % magnitudes tamaño_error = longitud ( error_pos );   Síndrome_Vals = Síndromes . x ;   b (:, 1 ) = Síndrome_Vals ( 1 : error_de_tamaño );    para idx = 1 : error de tamaño      e = alfa .^ ( idx * ( n - error_pos . x ));         err = e . x ;   er ( idx , :) = err ;    fin % Resolver el sistema lineal error_mag = ( gf ( er , m , prim_poly ) \ gf ( b , m , prim_poly )) ' ;         % Coloque la magnitud del error en el vector de error errores ( error_pos . x ) = error_mag . x ;   % Lleva este vector al campo de Galois errores_gf = gf ( errores , m , prim_poly );     % Ahora para corregir los errores solo agrega el código codificado decodificado_gf = codificado ( 1 : k ) + errores_gf ( 1 : k );     decodificado = decodificado_gf . x ;  fin% Eliminar ceros iniciales de la matriz de Galoisfunción  gt = trim ( g )   gx = g . x ;   gt = gf ( gx ( find ( gx , 1 ) : fin ), g . m , g . prim_poly );       fin% Agregar ceros a la izquierdafunción  xpad = pad ( x, k )   len = longitud ( x );   si len < k    xpad = [ ceros ( 1 , k - len ) x ];       finfin

Decodificadores de la vista original de Reed Solomon

The decoders described in this section use the Reed Solomon original view of a codeword as a sequence of polynomial values where the polynomial is based on the message to be encoded. The same set of fixed values are used by the encoder and decoder, and the decoder recovers the encoding polynomial (and optionally an error locating polynomial) from the received message.

Theoretical decoder

Reed & Solomon (1960) described a theoretical decoder that corrected errors by finding the most popular message polynomial. The decoder only knows the set of values ${\displaystyle a_{1}}$ to ${\displaystyle a_{n}}$ and which encoding method was used to generate the codeword's sequence of values. The original message, the polynomial, and any errors are unknown. A decoding procedure could use a method like Lagrange interpolation on various subsets of n codeword values taken k at a time to repeatedly produce potential polynomials, until a sufficient number of matching polynomials are produced to reasonably eliminate any errors in the received codeword. Once a polynomial is determined, then any errors in the codeword can be corrected, by recalculating the corresponding codeword values. Unfortunately, in all but the simplest of cases, there are too many subsets, so the algorithm is impractical. The number of subsets is the binomial coefficient, ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$, and the number of subsets is infeasible for even modest codes. For a ${\displaystyle (255,249)}$ code that can correct 3 errors, the naïve theoretical decoder would examine 359 billion subsets.

Berlekamp Welch decoder

In 1986, a decoder known as the Berlekamp–Welch algorithm was developed as a decoder that is able to recover the original message polynomial as well as an error "locator" polynomial that produces zeroes for the input values that correspond to errors, with time complexity ${\displaystyle O(n^{3})}$, where ${\displaystyle n}$ is the number of values in a message. The recovered polynomial is then used to recover (recalculate as needed) the original message.

Example

Using RS(7,3), GF(929), and the set of evaluation points a_i = i − 1

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

If the message polynomial is

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

The codeword is

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

Errors in transmission might cause this to be received instead.

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

The key equations are:

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

Assume maximum number of errors: e = 2. The key equations become:

$${\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}}}$$

Using Gaussian elimination:

$${\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

Recalculate P(x) where E(x) = 0 : {2, 3} to correct b resulting in the corrected codeword:

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

Gao decoder

In 2002, an improved decoder was developed by Shuhong Gao, based on the extended Euclid algorithm.^[6]

Example

Using the same data as the Berlekamp Welch example above:

• ${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$
• ${\displaystyle R_{0}=}$ Lagrange interpolation of ${\displaystyle \{a_{i},b(a_{i})\}}$ for i = 1 to n
• ${\displaystyle A_{-1}=0}$
• ${\displaystyle A_{0}=1}$

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

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

divide Q(x) and E(x) by most significant coefficient of E(x) = 708. (Optional)

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

Recalculate P(x) where E(x) = 0 : {2, 3} to correct b resulting in the corrected codeword:

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

See also

• BCH code
• Berlekamp–Massey algorithm
• Berlekamp–Welch algorithm
• Chien search
• Cyclic code
• Folded Reed–Solomon code
• Forward error correction

Notes

1. Authors in Andrews et al. (2007), provide simulation results which show that for the same code rate (1/6) turbo codes outperform Reed-Solomon concatenated codes up to 2 dB (bit error rate).^[9]

References

1. Reed & Solomon (1960)
2. Gorenstein, D.; Zierler, N. (June 1961). "A class of cyclic linear error-correcting codes in p^m symbols". J. SIAM. 9 (2): 207–214. doi:10.1137/0109020. JSTOR 2098821.
3. Peterson, W. Wesley (1961). Error Correcting Codes. MIT Press. OCLC 859669631.
4. Peterson, W. Wesley; Weldon, E.J. (1996) [1972]. Error Correcting Codes (2nd ed.). MIT Press. ISBN 978-0-585-30709-1. OCLC 45727875.
5. Sugiyama, Y.; Kasahara, M.; Hirasawa, S.; Namekawa, T. (1975). "A method for solving key equation for decoding Goppa codes". Information and Control. 27 (1): 87–99. doi:10.1016/S0019-9958(75)90090-X.
6. Gao, Shuhong (January 2002), New Algorithm For Decoding Reed-Solomon Codes (PDF), Clemson
7. Immink, K. A. S. (1994), "Reed–Solomon Codes and the Compact Disc", in Wicker, Stephen B.; Bhargava, Vijay K. (eds.), Reed–Solomon Codes and Their Applications, IEEE Press, ISBN 978-0-7803-1025-4
8. Hagenauer, J.; Offer, E.; Papke, L. (1994). "11. Matching Viterbi Decoders and Reed-Solomon Decoders in a Concatenated System". Reed Solomon Codes and Their Applications. IEEE Press. p. 433. ISBN 9780470546345. OCLC 557445046.
9. Andrews, K.S.; Divsalar, D.; Dolinar, S.; Hamkins, J.; Jones, C.R.; Pollara, F. (2007). "The development of turbo and LDPC codes for deep-space applications" (PDF). Proceedings of the IEEE. 95 (11): 2142–56. doi:10.1109/JPROC.2007.905132. S2CID 9289140.
10. See Lin & Costello (1983, p. 171), for example.
11. "Analytical Expressions Used in bercoding and BERTool". Archived from the original on 2019-02-01. Retrieved 2019-02-01.
12. Pfender, Florian; Ziegler, Günter M. (September 2004), "Kissing Numbers, Sphere Packings, and Some Unexpected Proofs" (PDF), Notices of the American Mathematical Society, 51 (8): 873–883, archived (PDF) from the original on 2008-05-09, retrieved 2009-09-28. Explains the Delsarte-Goethals-Seidel theorem as used in the context of the error correcting code for compact disc.
13. D. Gorenstein and N. Zierler, "A class of cyclic linear error-correcting codes in p^m symbols," J. SIAM, vol. 9, pp. 207–214, June 1961
14. Error Correcting Codes by W Wesley Peterson, 1961
15. Shu Lin and Daniel J. Costello Jr, "Error Control Coding" second edition, pp. 255–262, 1982, 2004
16. Guruswami, V.; Sudan, M. (September 1999), "Improved decoding of Reed–Solomon codes and algebraic geometry codes", IEEE Transactions on Information Theory, 45 (6): 1757–1767, CiteSeerX 10.1.1.115.292, doi:10.1109/18.782097
17. Brakensiek, Joshua; Gopi, Sivakanth; Makam, Visu (2023-06-02). "Generic Reed-Solomon Codes Achieve List-Decoding Capacity". Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. New York, NY, USA: Association for Computing Machinery. pp. 1488–1501. arXiv:2206.05256. doi:10.1145/3564246.3585128. ISBN 978-1-4503-9913-5.
18. Guo, Zeyu; Zhang, Zihan (2023). "Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). FOCS 2023, Santa Cruz, CA, USA, 2023. pp. 164–176. arXiv:2304.01403. doi:10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4.
19. Alrabiah, Omar; Guruswami, Venkatesan; Li, Ray (2023-08-18), Randomly punctured Reed--Solomon codes achieve list-decoding capacity over linear-sized fields, arXiv:2304.09445, retrieved 2024-02-08
20. Koetter, Ralf; Vardy, Alexander (2003). "Algebraic soft-decision decoding of Reed–Solomon codes". IEEE Transactions on Information Theory. 49 (11): 2809–2825. CiteSeerX 10.1.1.13.2021. doi:10.1109/TIT.2003.819332.
21. Franke, Steven J.; Taylor, Joseph H. (2016). "Open Source Soft-Decision Decoder for the JT65 (63,12) Reed–Solomon Code" (PDF). QEX (May/June): 8–17. Archived (PDF) from the original on 2017-03-09. Retrieved 2017-06-07.

Further reading

• Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, archived from the original (PDF) on June 30, 2014, retrieved April 21, 2010
• Hong, Jonathan; Vetterli, Martin (August 1995), "Simple Algorithms for BCH Decoding" (PDF), IEEE Transactions on Communications, 43 (8): 2324–33, doi:10.1109/26.403765
• Lin, Shu; Costello, Jr., Daniel J. (1983), Error Control Coding: Fundamentals and Applications, Prentice-Hall, ISBN 978-0-13-283796-5
• Massey, J. L. (1969), "Shift-register synthesis and BCH decoding" (PDF), IEEE Transactions on Information Theory, IT-15 (1): 122–127, doi:10.1109/tit.1969.1054260, S2CID 9003708
• Peterson, Wesley W. (1960), "Encoding and Error Correction Procedures for the Bose-Chaudhuri Codes", IRE Transactions on Information Theory, IT-6 (4): 459–470, doi:10.1109/TIT.1960.1057586
• Reed, Irving S.; Solomon, Gustave (1960), "Polynomial Codes over Certain Finite Fields", Journal of the Society for Industrial and Applied Mathematics, 8 (2): 300–304, doi:10.1137/0108018
• Welch, L. R. (1997), The Original View of Reed–Solomon Codes (PDF), Lecture Notes
• Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy, OCLC 45195002, AD0669824
• Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory (Revised ed.), Laguna Hills, CA: Aegean Park Press, ISBN 978-0-89412-063-3
• Cipra, Barry Arthur (1993), "The Ubiquitous Reed–Solomon Codes", SIAM News, 26 (1)
• Forney, Jr., G. (October 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), archived from the original on 2013-03-13
• MacWilliams, FJ; Sloane, NJA (1977), La teoría de los códigos de corrección de errores, North-Holland, ISBN 978-0-444-85010-2
• Reed, Irving S. ; Chen, Xuemin (2012) [1999], Codificación de control de errores para redes de datos, Springer, ISBN 9781461550051

Enlaces externos

Información y tutoriales

• Introducción a los códigos Reed-Solomon: principios, arquitectura e implementación (CMU)
• Un tutorial sobre codificación Reed-Solomon para tolerancia a fallos en sistemas tipo RAID
• Descodificación algebraica suave de códigos Reed-Solomon
• Wikiversidad:Códigos Reed-Solomon para programadores
• Libro blanco sobre I+D de la BBC WHP031
• Geisel, William A. (agosto de 1990), Tutorial sobre codificación de corrección de errores Reed-Solomon, Memorándum técnico, NASA , TM-102162
• Códigos concatenados por el Dr. Dave Forney (scholarpedia.org).
• Reid, Jeff A. (abril de 1995), CRC y Reed Solomon ECC (PDF)

Implementaciones

• La biblioteca FEC en C de Phil Karn (también conocido como KA9Q) incluye el códec Reed–Solomon, tanto la versión arbitraria como la optimizada (223,255)
• Códec C++ Reed–Solomon de código abierto de Schifra
• Biblioteca RSCode de Henry Minsky, codificador/descodificador Reed-Solomon
• Biblioteca de decodificación suave Reed–Solomon de código abierto para C++
• Implementación de Matlab de errores y borrados Descodificación Reed-Solomon
• Implementación de Octave en el paquete de comunicaciones
• Implementación en Python puro de un códec Reed–Solomon