Corrección de errores de Reed-Solomon

Códigos de corrección de errores

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 , 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ímbolos. 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 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 b  + 1 errores de bits 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 originales.

Historia

Los códigos Reed-Solomon fueron desarrollados en 1960 por Irving S. Reed y Gustave Solomon , que entonces eran miembros del personal del Laboratorio Lincoln del MIT . Su artículo fundamental se tituló "Códigos polinomiales sobre ciertos campos finitos". (Reed y Salomón 1960). El esquema de codificación original descrito en el artículo de Reed & Solomon utilizaba un polinomio variable basado en el mensaje a codificar, donde el codificador y el decodificador solo conocen un conjunto fijo de valores (puntos de evaluación) a codificar. 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 cual no era práctico para todos excepto para el más simple. casos. Esto se resolvió inicialmente cambiando el esquema original a un esquema similar a un 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 existen 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 polinómico fijo práctico para códigos BCH desarrollado por Daniel Gorenstein y Neal Zierler fue descrito en un informe del Laboratorio Lincoln del MIT realizado por Zierler en enero de 1960 y posteriormente en un artículo de junio de 1961. ^[2] El decodificador Gorenstein-Zierler y El trabajo relacionado sobre códigos BCH se describe en un libro Códigos de corrección de errores de W. Wesley Peterson (1961). ^[3] En 1963 (o posiblemente antes), JJ Stone (y otros) reconocieron que los códigos de Reed Solomon podían utilizar el esquema BCH de utilizar un polinomio generador fijo, lo que convertía dichos códigos en una clase especial de códigos BCH, [ ^4] pero Reed Solomon Los códigos basados ​​en el esquema de codificación original no son una clase de códigos BCH y, según el 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 entrelazados . 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 códigos Bose-Chaudhuri-Hocquenghem (BCH) . Por ejemplo, los códigos Reed-Solomon se utilizan en el estándar DVB-S de transmisión de vídeo digital (DVB) , 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 esquemas original conocido como algoritmo de Berlekamp-Welch .

En 1996, Madhu Sudan y otros desarrollaron variaciones de los decodificadores de esquemas originales llamados decodificadores de listas o decodificadores suaves, y el trabajo continúa en estos tipos 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 . ^[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 una fuerte codificación de corrección de errores 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 entrelazador convolucional de 28 vías producen un esquema llamado codificación Reed-Solomon entrelazada ( CIRC ). El primer elemento de un decodificador CIRC es un código Reed-Solomon interno (32,28) relativamente débil, 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 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 distribuidos 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 único byte borrado en cada uno de los 28 bloques de 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 completamente 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 casi con certeza causados ​​por errores de seguimiento que hacen que el láser salte la 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 de Reed-Solomon también se utiliza en archivos de archivo que comúnmente se publican junto con archivos multimedia en USENET . El servicio de almacenamiento distribuido en línea Wuala (descontinuado en 2015) también utilizó 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ódigo 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 supone un código de RS ( N ,  K ) que da como resultado N palabras de código de longitud N símbolos, cada una de las cuales almacena K símbolos de datos, que se generan y 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 pueda modelarse adecuadamente y se considere menor. En conclusión, N suele ser 2 K , lo que significa que se debe recibir al menos la mitad de todas las palabras de código enviadas para poder 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 de CCSDS como una forma de corrección de errores directos .

Transmisión espacial

Sistema de codificación concatenado del espacio profundo. ^[8] Notación: RS(255, 223) + CC ("longitud de restricción" = 7, velocidad 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 en las comunicaciones por satélite (por ejemplo, radiodifusió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 breves o simplificados.

Las versiones modernas de codificación convolucional concatenada decodificada por Reed-Solomon/Viterbi se utilizaron y se utilizan en las misiones Mars Pathfinder , Galileo , Mars Exploration Rover y Cassini , donde funcionan entre 1 y 1,5 dB del límite final, 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 campo finito de orden y, por 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 velocidad es constante y, además, la longitud del bloque es igual o uno menor que el tamaño del alfabeto. , es decir, o . ^{[ cita necesaria ]} ${\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 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 en 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 . 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 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 clave 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: ${\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 \}}\,.}$$

distintosdistancialímite Singletoncadacódigos separables por distancia máxima ${\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 iguales a y, por lo tanto, cada mensaje se puede asignar de forma única a dicho polinomio, existen diferentes formas de realizar esta codificación. La construcción original de Reed & Solomon (1960) interpreta el mensaje x como los coeficientes del polinomio p , mientras que 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 . Este ú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 clave. ${\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 y Solomon (1960), el mensaje se asigna al polinomio con ${\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}}}$$

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

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

Existe un procedimiento de codificación alternativo que produce un código Reed-Solomon sistemático . Aquí usamos un polinomio diferente . En esta variante, el polinomio se define como el único polinomio de grado menor que tal que ${\displaystyle p_{m}}$ ${\displaystyle p_{m}}$ ${\displaystyle k}$

$${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$

la interpolación de Lagrange ${\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, , corresponden exactamente a 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 discreta de Fourier y su inversa

Una transformada de Fourier discreta es esencialmente el mismo que el procedimiento de codificación; utiliza el polinomio generador para asignar un conjunto de puntos de evaluación a 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 inversa de Fourier podría usarse para convertir un conjunto libre de errores de n < q valores de mensaje nuevamente 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 mensaje 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 remitente calcula un polinomio de grado relacionado donde y envía el polinomio . El polinomio se construye multiplicando el polinomio del mensaje , que tiene grado , por un polinomio generador de grado 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 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 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 en general sistemático, 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 espacio para los símbolos de cheque, dividiendo ese producto por 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 como máximo grado , mientras que los coeficientes de en el polinomio son cero. Por tanto, la siguiente definición de 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 en 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 ( norte ,  k ); esto se conoce como límite Singleton . Este código también se denomina código de máxima distancia 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, las ubicaciones de los errores se conocen de antemano (por ejemplo, "información secundaria" en las relaciones señal-ruido del demodulador ); esto se denomina borrados . Un código Reed-Solomon (como cualquier código MDS ) es capaz de corregir el doble de borrados que errores, y cualquier combinación de errores y borrados puede corregirse 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 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]

$${\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 se puede representar como un valor de bits. El remitente envía los puntos de datos como bloques codificados y la cantidad 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 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 comúnmente utilizado 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 indica como un código y es capaz de corregir hasta 16 errores de símbolos 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 analizadas anteriormente los hacen especialmente adecuados para aplicaciones donde 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 cuenta como un único error. Por el contrario, si un flujo de datos no se caracteriza por ráfagas o interrupciones de errores 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, 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. Los bits "faltantes" en un código abreviado deben completarse con ceros o unos, dependiendo de si los datos están complementados o no. (Para decirlo de otra manera, si los símbolos están invertidos, entonces el relleno cero debe invertirse a un relleno único). Por esta razón, es obligatorio que se resuelva el sentido de los datos (es decir, verdadero o complementado). antes de la decodificación Reed-Solomon.

Si el código Reed-Solomon es cíclico o no depende de detalles sutiles de la construcción. En la visión original de Reed y Solomon, donde las palabras de código 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 campo , entonces, por definición, todos los elementos distintos de cero toman la forma para , donde . Cada polinomio 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 ; Como se mantiene, esta palabra en clave es el desplazamiento cíclico hacia la izquierda de la palabra en clave original derivada de . Entonces, elegir una secuencia de potencias de raíz primitivas 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 siempre son 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

No se requiere que los diseñadores utilicen 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 sin transmitirlos. En el decodificador, la misma porción del bloque se carga localmente con ceros binarios. El teorema de Delsarte-Goethals-Seidel ^[12] ilustra un ejemplo de aplicación de códigos Reed-Solomon abreviados. 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 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 posteriormente en un artículo de junio de 1961. ^[13] El decodificador Gorenstein-Zierler y el trabajo relacionado sobre códigos BCH se describen en un libro Códigos de corrección de errores de W. Wesley Peterson (1961). ^[14]

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 Reed-Solomon, s ( x ) es divisible por el polinomio generador g ( x ):

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

α

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

$${\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 a 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 los puntos . A los resultados de esa evaluación los llamamos "síndromes", S _j . Se definen como: ${\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 desaparece. En otras palabras, los síndromes sólo 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ó durante el tránsito.

Localizadores de errores y valores de error

Por conveniencia, defina los localizadores de errores 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 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 es no 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 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, lo que daría 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 los errores ( Xk ₎ ya se conocen mediante algún otro método (por ejemplo, en una transmisión de FM, las secciones en las que el flujo de bits no estaba claro o estaba superado por interferencias 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 de 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 de los que se pueden corregir sin conocer su ubicación. ${\displaystyle 2v}$ ${\displaystyle v}$

Polinomio 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 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 del producto anterior, ya que si uno de los términos multiplicados será cero , todo el polinomio 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.\\[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úna 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}$$

Extraiga los valores constantes de 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 ahora son equivalentes a los valores del síndrome, que conocemos y podemos sustituir! Esto por lo 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}$$

Restar de ambos lados produce ${\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 se eligió j para que fuera 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 &\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 ubicación del error. Las raíces del polinomio de ubicació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 ubicació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 errores _Xk , se pueden determinar los valores de error. Esto se puede hacer mediante una solución directa para Y _k en la matriz de ecuaciones de error proporcionada anteriormente, o utilizando 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 previamente calculada. ${\displaystyle \alpha }$

Corregir 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 s ( x ) enviado originalmente , 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}$$

p ( x ) = 3 x ² + 2 x + 1

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

rα

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

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 clave).

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

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

Λ'(x) = 658 x + 821

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

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

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

Decodificador Berlekamp-Massey

El algoritmo de Berlekamp-Massey es un procedimiento iterativo alternativo para encontrar el polinomio 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}}$$

xeAlgoritmo de Berlekamp-MasseyCxx

Ejemplo

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

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 errores como el polinomio del 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 _yo ( x ) S ( x ) + B _yo ( x ) x ^t = R _yo ( 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 _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 queda:

R −1  := x t R 0  := S ( x ) A −1  := 0 A 0  := 1 i  := 0 mientras que 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 Ai ₍ 0):

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

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

Ai (0) es el término constante (orden inferior) _{de Ai} .

Ejemplo

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

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

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

Decodificador que utiliza transformada discreta de Fourier

Se puede utilizar una transformada de Fourier discreta para decodificar. ^[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 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 de Fourier discreta 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 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}$$

Úselo como síndromes (son iguales) y genere el polinomio localizador de errores usando los métodos de cualquiera de los decodificadores anteriores. ${\displaystyle R_{1}}$ ${\displaystyle R_{t}}$

Sea v = número de errores. Genere E ( x ) usando los coeficientes conocidos de , 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 calcule C ( x ) = R ( x ) − E ( x ) y tome la transformada inversa (interpolación polinómica) de C ( x ) para producir c ( x ).

Decodificació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 "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. ^[16] 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 en 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})}$

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

Decodificación suave

Los métodos de decodificación algebraica 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 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 listas algebraicas 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 decisiones suaves. ^[21]

ejemploMATLAB

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: mensaje = uint8('Prueba') % enc_msg = rsEncoder(msg, 8, 301, 12, numerel(msg)); % Consigue el alfa alfa = gf ( 2 , m , prim_poly );     % Obtener el polinomio generador de Reed-Solomon g(x) g_x = genpoly ( k , n , alfa );     % Multiplique la información por X^(nk), o simplemente rellene con ceros al final para % obtiene espacio para agregar la información redundante msg_padded = gf ([ msg ceros ( 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. codificado = msg_padded - resto ;    fin% 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, alfa )   gramo = 1 ;   % Una multiplicación en el campo de Galois es solo 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 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 );    gramo = [];   S = [];   % Consigue el alfa alfa = gf ( 2 , m , prim_poly );     % Encuentra los síndromes (Marca si dividiendo el mensaje por el generador % polinomio el resultado es cero) Synd = polival ( codificado , alfa . ^ ( 1 : n - k ));        Síndromes = recortar ( 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 = [];   gramo = [];   S = Síndrome ;   devolver ; fin % Prepárese para el algoritmo euclidiano (se utiliza para encontrar el error al localizar % polinomios) r0 = [ 1 , ceros ( 1 , 2 * max_errors )]; r0 = gf ( r0 , m , prim_poly ); r0 = recortar ( 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 ;      % ¿El algoritmo euclidiano sobre los polinomios r0(x) y Síndromes(x) en % de orden para encontrar el error al localizar el polinomio si bien es cierto  % Haz una división larga [ cociente , resto ] = deconv ( r0 , r1 );     % Añade algunos ceros cociente = pad ( cociente , longitud ( g1 ));    % Encuentra cociente*g1 y pad c = conv ( cociente , g1 );    c = recortar ( c );   c = pad ( c , longitud ( g0 ));    % Actualizar g como cociente g0*g1 gramo = g0 - c ;     % Compruebe 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 ceros a la izquierda r0 = recortar ( r1 ); r1 = recortar ( resto );      g0 = g1 ; g1 = g ;      fin % Eliminar ceros a la izquierda g = recortar ( g );   % Encuentra los ceros del polinomio de error en este campo de Galois. evalPoly = polival ( g , alfa .^ ( 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 está vacío ( error_pos )  decodificado = orig_vals ( 1 : k );   error_mag = [];   devolver ; fin % Prepare un sistema lineal para resolver el polinomio de error y encontrar el error % magnitudes tamaño_error = longitud ( error_pos );   Syndrome_Vals = Síndromes . X ;   b (:, 1 ) = Síndrome_Vals ( 1 : tamaño_error );    para idx = 1 : tamaño_error      e = alfa .^ ( idx * ( n - error_pos . x ));         errar = e . X ;   er ( idx , :) = errar ;    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 simplemente agregue con el código codificado decodificado_gf = codificado ( 1 : k ) + errores_gf ( 1 : k );     decodificado = decodificado_gf . X ;  fin% Eliminar ceros a la izquierda de la matriz de Galoisfunción  gt = recortar ( g )   gx = g . X ;   gt = gf ( gx ( buscar ( gx , 1 ) : fin ), g . m , g . prim_poly );       fin% Añadir ceros a la izquierdafunción  xpad = pad ( x, k )   len = longitud ( x );   si len < k    xpad = [ ceros ( 1 , k - len ) x ];       finfin

Decodificadores de vista original de Reed Solomon

Los decodificadores descritos en esta sección utilizan la visión 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 decodificador utilizan el mismo conjunto de valores fijos, y el decodificador 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 corrigía errores encontrando el polinomio de mensaje más popular. El decodificador sólo conoce el conjunto de valores y qué método de codificación se utilizó para generar la secuencia de valores de la palabra clave. Se desconocen el mensaje original, el polinomio y cualquier error. Un procedimiento de decodificación podría utilizar 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 polinomios potenciales repetidamente, 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 clave se puede corregir recalculando los valores correspondientes de la palabra clave. Desafortunadamente, en todos los casos, excepto en los más simples, hay demasiados subconjuntos, por lo que el algoritmo no es práctico. El número de subconjuntos es el coeficiente binomial , y el número de subconjuntos no es factible ni siquiera para códigos modestos. Para un código que pueda corregir tres errores, el ingenuo decodificador teórico examinaría 359 mil millones de subconjuntos. ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$ ${\displaystyle (255,249)}$

Decodificador Berlekamp Welch

En 1986, se desarrolló un decodificador conocido como algoritmo 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. , donde es el número de valores en un mensaje. Luego, el polinomio recuperado se utiliza para recuperar (recalcular según sea necesario) el mensaje original. ${\displaystyle O(n^{3})}$ ${\displaystyle n}$

Ejemplo

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

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

Si el polinomio del mensaje es

pag ( x ) = 003x2 ⁺ 002x + 001

La palabra clave es

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

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

segundo = c + mi = {001, 006, 123, 456, 057, 086, 121}

Las ecuaciones clave son:

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

Supongamos un 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 ) = 003x4 + ^{916x3 +} 009x2 ⁺ 007x + 006​

mi ( 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 , lo que dará como resultado la palabra clave 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. ^[6]

Ejemplo

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

• ${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$
• ${\displaystyle R_{0}=}$Interpolación de Lagrange para i = 1 an ${\displaystyle \{a_{i},b(a_{i})\}}$
• ${\displaystyle A_{-1}=0}$
• ${\displaystyle A_{0}=1}$

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

mi ( x ) = un ₂ = 708 x ² + 176 x + 532

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

Q ( x ) = 003x4 + ^{916x3 +} 009x2 ⁺ 007x + 006​

mi ( 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 , lo que dará como resultado la palabra clave corregida:

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

Ver también

• código BCH
• Algoritmo de Berlekamp-Massey
• Algoritmo de Berlekamp-Welch
• búsqueda de perro
• código cíclico
• Código Reed-Salomón plegado
• Corrección de errores hacia adelante

Notas

1. Autores en Andrews et al. (2007), 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 ). ^[9]

Referencias

1. Caña y Salomón (1960)
2. Gorenstein, D.; Zierler, N. (junio de 1961). "Una clase de códigos de corrección de errores lineales cíclicos en símbolos p ^ m". J. SIAM . 9 (2): 207–214. doi :10.1137/0109020. JSTOR  2098821.
3. Peterson, W. Wesley (1961). Códigos de corrección de errores . Prensa del MIT. OCLC  859669631.
4. Peterson, W. Wesley; Weldon, EJ (1996) [1972]. Códigos de corrección de errores (2ª ed.). Prensa del MIT. ISBN 978-0-585-30709-1. OCLC  45727875.
5. Sugiyama, Y.; Kasahara, M.; Hirasawa, S.; Namekawa, T. (1975). "Un método para resolver ecuaciones clave para decodificar códigos Goppa". Información y Control . 27 (1): 87–99. doi : 10.1016/S0019-9958(75)90090-X .
6. Gao, Shuhong (enero de 2002), Nuevo algoritmo para decodificar códigos Reed-Solomon (PDF) , Clemson
7. Immink, KAS (1994), "Los 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
8. Hagenauer, J.; Oferta, E.; Papke, L. (1994). "11. Emparejamiento de decodificadores Viterbi y decodificadores Reed-Solomon en un sistema concatenado". Códigos Reed Solomon y sus aplicaciones . Prensa IEEE. pag. 433.ISBN​ 9780470546345. OCLC  557445046.
9. Andrews, KS; Divsalar, D.; Dolinar, S.; Hamkins, J.; Jones, CR; Pollara, F. (2007). "El desarrollo de códigos turbo y LDPC para aplicaciones del espacio profundo" (PDF) . Actas del IEEE . 95 (11): 2142–56. doi :10.1109/JPROC.2007.905132. S2CID  9289140.
10. Véase Lin y Costello (1983, p. 171), por ejemplo.
11. "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 .
12. Pfender, Florián; 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 09/05/2008 , consultado el 28 de septiembre de 2009.. Explica el teorema de Delsarte-Goethals-Seidel tal como se utiliza en el contexto del código de corrección de errores para discos compactos .
13. 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
14. Códigos de corrección de errores de W Wesley Peterson, 1961
15. Shu Lin y Daniel J. Costello Jr, segunda edición de "Error Control Coding", págs. 255-262, 1982, 2004
16. Guruswami, V.; Sudán, 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 
17. Brakensiek, Josué; Gopi, Sivakanth; Makam, Visu (2 de junio de 2023). "Los códigos genéricos Reed-Solomon logran capacidad de decodificación de listas". Actas del 55º Simposio Anual de ACM sobre Teoría de la Computación . STOC 2023. Nueva York, NY, EE. UU.: Asociación de Maquinaria de Computación. págs. 1488-1501. arXiv : 2206.05256 . doi :10.1145/3564246.3585128. ISBN 978-1-4503-9913-5.
18. Guo, Zeyu; Zhang, Zihan (2023). "Los códigos Reed-Solomon perforados aleatoriamente logran la capacidad de decodificación de listas sobre alfabetos de tamaño polinómico". 2023 64.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS) . FOCS 2023, Santa Cruz, CA, EE. UU., 2023. págs. arXiv : 2304.01403 . doi :10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4.
19. Alrabiah, Omar; Guruswami, Venkatesan; Li, Ray (18 de agosto de 2023), Reed perforado aleatoriamente: los códigos Solomon logran capacidad de decodificación de listas en campos de tamaño lineal, arXiv : 2304.09445 , consultado el 8 de febrero de 2024
20. Koetter, Ralf; Vardy, Alejandro (2003). "Decodificación algebraica por 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. 
21. Franke, Steven J.; Taylor, José H. (2016). "Decodificador de decisión suave de código abierto para el código Reed-Solomon JT65 (63,12)" (PDF) . QEX (mayo/junio): 8-17. Archivado (PDF) desde el original el 9 de marzo de 2017 . Consultado el 7 de junio de 2017 .

Otras lecturas

• Gill, John (sin fecha), EE387 Notas n.° 7, Folleto n.° 28 (PDF) , Universidad de Stanford, archivado desde el 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–33, doi :10.1109/26.403765
• Lin, Shu; Costello, Jr., Daniel J. (1983), Codificación de control de errores: fundamentos y aplicaciones , 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, S2CID  9003708
• Peterson, Wesley W. (1960), "Procedimientos de codificación y corrección de errores para los códigos Bose-Chaudhuri", Transacciones IRE sobre teoría de la información , IT-6 (4): 459–470, doi :10.1109/TIT.1960.1057586
• Caña, Irving S .; Solomon, Gustave (1960), "Códigos polinómicos 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 visión 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, OCLC  45195002, AD0669824
• 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 omnipresentes códigos Reed-Solomon", SIAM News , 26 (1)
• Forney, Jr., G. (octubre de 1965), "Sobre la decodificación de códigos BCH", IEEE Transactions on Information Theory , 11 (4): 549–557, doi :10.1109/TIT.1965.1053825
• Koetter, Ralf (2005), Códigos Reed-Solomon, MIT Lecture Notes 6.451 (vídeo), archivado desde el original el 13 de marzo de 2013
• MacWilliams, FJ; Sloane, NJA (1977), La teoría de los códigos de corrección de errores, Holanda Septentrional, ISBN 978-0-444-85010-2
• Caña, 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
• Decodificación suave algebraica de códigos Reed-Solomon
• Wikiversidad: 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 de Reed-Solomon, Memorando 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 conocida como KA9Q) incluye el códec Reed-Solomon, tanto en versión arbitraria como optimizada (223,255)
• Códec C++ Reed-Solomon de código abierto de Schifra
• Biblioteca RSCode de Henry Minsky, codificador/decodificador Reed-Solomon
• Biblioteca de decodificación suave C++ Reed-Solomon de código abierto
• Implementación en Matlab de errores y borrados de decodificación Reed-Solomon
• Implementación de octava en paquete de comunicaciones.
• Implementación en Pure-Python de un códec Reed-Solomon