Corrección de errores de Reed-Solomon

Códigos de corrección de errores

En teoría de la información y teoría de la codificación , 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 , quienes 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 usaba 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 los más simples. Esto se resolvió inicialmente cambiando el esquema original por uno 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 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 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), J. J. 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 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 gestionar 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 parchís que suelen publicarse 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 los 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 no concuerdan 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

Existen procedimientos de codificación alternativos que producen un código Reed-Solomon sistemático . Un método utiliza la interpolación de Lagrange para calcular un polinomio tal que Then se evalúe en los otros puntos . ${\displaystyle p_{m}}$ $${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$ ${\displaystyle p_{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 función es una función lineal. Para generar la matriz de codificación sistemática G correspondiente, multiplique la matriz de Vandermonde A por la inversa de la submatriz cuadrada izquierda de A. ${\displaystyle C}$

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

${\displaystyle C(m)=Gm}$para la siguiente matriz con elementos de : ${\displaystyle n\times k}$ ${\displaystyle G}$ ${\displaystyle F}$ $${\displaystyle C(m)=Gm={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

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 espacio para los símbolos de verificación, 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 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)\,.}$$

Esta función es una función de mapeo lineal. Para generar la matriz de codificación sistemática G correspondiente, establezca la submatriz cuadrada izquierda de G en la matriz identidad y luego codifique cada fila: ${\displaystyle s}$

$${\displaystyle G={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$Ignorando los ceros iniciales, la última fila = . ${\displaystyle g(x)}$

${\displaystyle C(m)=Gm}$para la siguiente matriz con elementos de : ${\displaystyle n\times k}$ ${\displaystyle G}$ ${\displaystyle F}$ $${\displaystyle C(m)=Gm={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

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 el límite Singleton . Un código de este tipo también se denomina código de distancia máxima separable (MDS) . ${\textstyle d_{\min }=n-k+1.}$

La capacidad de corrección de errores de un código Reed-Solomon está determinada por su distancia mínima o, 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 el código ( ver 'Observaciones' al final de esta sección ). Los bits "faltantes" en un código acortado deben rellenarse 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 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) acortado 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 ${\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 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 para producir el polinomio recibido $${\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}$$ $${\displaystyle r(x)=s(x)+e(x).}$$

El coeficiente e _i será cero si no hay error en esa potencia de x y no será 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 Nótese 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}}{(\alpha ^{j})}^{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}},\quad 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\cdot 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), 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 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 2\nu }$ ${\displaystyle \nu }$

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,\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\end{aligned}}}$$

Suma para k = 1 a ν y seguirá siendo cero: $${\displaystyle \sum _{k=1}^{\nu }(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.}$$

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.}$$

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 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 entero entre 1 y v inclusive, y esta equivalencia es verdadera para todos 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 errores: 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 esto en su lugar: Los síndromes se calculan evaluando r en potencias de α : obteniendo el sistema $${\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,\quad S_{3}=r(3^{3})=762,\quad 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}}.}$$

Utilizando la eliminación gaussiana , con raíces x ₁ = 757 = 3 ⁻³ y x ₂ = 562 = 3 ⁻⁴ . Los coeficientes se pueden invertir: para producir raíces 27 = 3 ³ y 81 = 3 ⁴ con exponentes positivos, pero normalmente esto no se utiliza. El logaritmo de las raíces correspondientes a las ubicaciones de error (de derecha a izquierda, la ubicación 0 es el último término en la palabra clave). $${\displaystyle {\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}},}$$ $${\displaystyle \Lambda (x)=329x^{2}+821x+001,}$$ $${\displaystyle R(x)=001x^{2}+821x+329,}$$

Para calcular los valores de error, aplique el algoritmo de Forney : $${\displaystyle \Omega (x)=S(x)\Lambda (x){\bmod {x}}^{4}=546x+732,}$$ $${\displaystyle \Lambda '(x)=658x+821,}$$ $${\displaystyle e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=074,}$$ $${\displaystyle e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=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 (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 ) = R2 /544 = 546x + ₇₃₂

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

Transforme 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 Syndromes(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

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 polinómicos, 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.

Descodificador teórico

Reed y Solomon (1960) describieron un decodificador teórico que corrigió errores al encontrar el polinomio de mensaje más popular. El decodificador solo conoce el conjunto de valores y qué método de codificación se utilizó para generar la secuencia de valores de la palabra de código. El mensaje original, el polinomio y cualquier error son desconocidos. 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 una cantidad suficiente de polinomios coincidentes para eliminar razonablemente cualquier error en la palabra de código recibida. Una vez que se determina un polinomio, entonces cualquier error en la palabra de código se puede corregir, recalculando los valores de la palabra de código correspondientes. Desafortunadamente, en todos los casos, excepto en los más simples, hay demasiados subconjuntos, por lo que el algoritmo es poco práctico. El número de subconjuntos es el coeficiente binomial , y el número de subconjuntos es inviable incluso para códigos modestos. Para un código que puede corregir tres errores, el decodificador teórico ingenuo 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)}$

Descodificador Berlekamp Welch

En 1986, se desarrolló un decodificador conocido como algoritmo Berlekamp–Welch , 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 los errores, con una complejidad temporal , donde es el número de valores de un mensaje. El polinomio recuperado se utiliza entonces para recuperar (recalcular según sea necesario) el mensaje original. ${\displaystyle O(n^{3})}$ ${\displaystyle n}$

Ejemplo

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

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

Si el polinomio del mensaje es

p ( x ) = 003x2 + ^002x + 001

La palabra clave es

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

Es posible que errores en la transmisión provoquen que se reciba esto.

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

Las ecuaciones clave son:

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

Supongamos que el número máximo de errores es e = 2. Las ecuaciones clave son:

$${\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 la eliminación gaussiana :

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

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

E ( x ) = 001x2 + ^924x + 006

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

Recalcule P(x) donde E(x) = 0: {2, 3} para corregir b, lo que da como resultado la palabra de código corregida:

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

Decodificador Gao

En 2002, Shuhong Gao desarrolló un decodificador mejorado basado en el algoritmo Euclid extendido. ^[6]

Ejemplo

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

• ${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$
• ${\displaystyle R_{0}=}$Interpolación de Lagrange para i = 1 a n ${\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

E ( x ) = A2 = _708x2 ⁺ 176x + 532

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

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

E ( x ) = 001x2 + ^924x + 006

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

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

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

Véase también

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

Notas

1. Los 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 Reed-Solomon hasta 2 dB ( tasa de error de bits ). ^[9]

Referencias

1. Reed 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 . MIT Press. OCLC  859669631.
4. Peterson, W. Wesley; Weldon, EJ (1996) [1972]. Códigos de corrección de errores (2.ª ed.). MIT Press. ISBN 978-0-585-30709-1.OCLC 45727875  .
5. Sugiyama, Y.; Kasahara, M.; Hirasawa, S.; Namekawa, T. (1975). "Un método para resolver la ecuación clave para decodificar los 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), "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.; Offer, E.; Papke, L. (1994). "11. Coincidencia de decodificadores Viterbi y decodificadores Reed-Solomon en un sistema concatenado". Códigos Reed Solomon y sus aplicaciones . IEEE Press. pág. 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 en el 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ág. 171), por ejemplo.
11. "Expresiones analíticas utilizadas en bercoding y BERTool". Archivado desde el original el 2019-02-01 . Consultado el 2019-02-01 .
12. Pfender, Florian; Ziegler, Günter M. (septiembre de 2004), "Kissing Numbers, Sphere Packings, and Some Unexpected Proofs" (PDF) , Avisos de la American Mathematical Society , 51 (8): 873–883, archivado (PDF) desde el original el 2008-05-09 , consultado el 2009-09-28Explica 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, "Error Control Coding", segunda edición, págs. 255-262, 1982, 2004
16. Guruswami, V.; Sudan, M. (septiembre de 1999), "Descodificació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, Joshua; Gopi, Sivakanth; Makam, Visu (2 de junio de 2023). "Los códigos genéricos Reed-Solomon alcanzan la capacidad de decodificación de listas". Actas del 55.º Simposio anual de la ACM sobre teoría de la computación . STOC 2023. Nueva York, NY, EE. UU.: Association for Computing Machinery. 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 alcanzan la capacidad de decodificación de listas sobre alfabetos de tamaño polinomial". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) . FOCS 2023, Santa Cruz, CA, EE. UU., 2023. págs. 164–176. 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), Los códigos Reed-Solomon perforados aleatoriamente 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, Alexander (2003). "Decodificación algebraica de códigos Reed-Solomon mediante decisión suave". 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 (mayo/junio): 8–17. Archivado (PDF) desde el original el 9 de marzo de 2017. Consultado el 7 de junio de 2017 .

Lectura adicional

• Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, 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 registros 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 de Bose-Chaudhuri", IRE Transactions on Information Theory , IT-6 (4): 459–470, doi :10.1109/TIT.1960.1057586
• Reed, Irving S. ; Solomon, Gustave (1960), "Códigos polinomiales sobre ciertos campos finitos", Revista de la Sociedad de Matemáticas Industriales y Aplicadas , 8 (2): 300–304, doi :10.1137/0108018
• Welch, LR (1997), La visión original de los códigos Reed-Solomon (PDF) , Notas de la conferencia
• Berlekamp, ​​Elwyn R. (1967), Descodificació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 (Video), 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, 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 la codificación Reed-Solomon para la 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