Corrección de errores de Reed-Solomon

Los códigos Reed-Solomon son un grupo de códigos de corrección de errores que fueron introducidos por Irving S. Reed y Gustave Solomon en 1960. Tienen muchas aplicaciones, las más destacadas incluyen tecnologías de consumo como MiniDiscs, CD, DVD, discos Blu-ray, códigos QR, tecnologías de transmisión de datos como DSL y WiMAX, sistemas de transmisión como comunicaciones por satélite, DVB y ATSC, y sistemas de almacenamiento como RAID 6.

Los códigos Reed-Solomon operan en un bloque de datos tratados como un conjunto de elementos de campo finito llamados símbolos. Los códigos Reed-Solomon pueden detectar y corregir múltiples errores de símbolos. Agregando t = n − k símbolos de verificación en los datos, un código Reed–Solomon puede detectar (pero no corregir) cualquier combinación de hasta t símbolos erróneos, o ubique y corrija 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 combinaciones correctas de errores y tachaduras. 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 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, 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 & Salomón 1960). El esquema de codificación original descrito en Reed & El artículo de Solomon usó un polinomio variable basado en el mensaje a codificar donde solo se conoce un conjunto fijo de valores (puntos de evaluación) para codificar y decodificar. El decodificador teórico original generaba polinomios potenciales basados en subconjuntos de valores k (longitud del mensaje no codificado) de n (longitud del mensaje codificado) de un mensaje recibido, eligiendo el polinomio más popular como el correcto, lo que no era práctico para todos los casos excepto para los más simples. Esto se resolvió inicialmente cambiando el esquema original a un esquema similar al código BCH basado en un polinomio fijo conocido tanto por el codificador como por el decodificador, pero luego se desarrollaron decodificadores prácticos basados en el esquema original, aunque más lentos que los esquemas BCH. El resultado de esto es que hay dos tipos principales de códigos Reed Solomon, los que usan el esquema de codificación original y los que usan el esquema de codificación BCH.

También en 1960, un práctico decodificador polinomial fijo para códigos BCH desarrollado por Daniel Gorenstein y Neal Zierler se describió en un informe del MIT Lincoln Laboratory de Zierler en enero de 1960 y luego en un artículo en junio de 1961. El decodificador Gorenstein-Zierler y el trabajo relacionado con los códigos BCH se describe en un libro Error Correcting Codes de W. Wesley Peterson (1961). 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, lo que hacía que dichos códigos fueran una clase especial de códigos BCH, pero los códigos Reed Solomon se basaban en la codificación original. esquema, 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, y desde entonces se conoce como el algoritmo de decodificación Berlekamp-Massey.

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

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 están ampliamente implementados 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 usan en el estándar DVB-S de Digital Video Broadcasting (DVB), junto con un código interno convolucional, pero los códigos BCH se usan 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; consulte Algoritmo de decodificación de lista de Guruswami–Sudan.

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

Aplicaciones

Almacenamiento de datos

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

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

El resultado es un CIRC que puede corregir por completo ráfagas de error 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 seguridad por errores de seguimiento que hacen que el láser salte de pista, no por ráfagas de errores incorregibles.

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

La corrección de errores de Reed–Solomon también se usa en archivos de archivo que se publican comúnmente junto con archivos multimedia en USENET. El servicio de almacenamiento en línea distribuido Wuala (descontinuado en 2015) también usó Reed-Solomon al dividir archivos.

Código de barras

Casi todos los códigos de barras bidimensionales como PDF-417, MaxiCode, Datamatrix, QR Code y Aztec Code utilizan la corrección de errores Reed-Solomon para permitir una lectura correcta incluso si una parte del código de barras está dañada. Cuando el 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 simbología PostBar la utiliza.

Transmisión de datos

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

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

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

Transmisión espacial

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

Una aplicación significativa 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 extendido mucho en el espacio profundo y las comunicaciones por satélite (por ejemplo, la transmisión digital directa).

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

Las versiones modernas de la codificación convolucional concatenada Reed-Solomon/Viterbi-decoded se utilizaron y se utilizan en las misiones Mars Pathfinder, Galileo, Mars Exploration Rover y Cassini, donde funcionan dentro de aproximadamente 1 a 1,5 dB del límite último, el Shannon capacidad.

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

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 q, una longitud de bloque n y un longitud del mensaje k, con k < n ≤ q. El conjunto de símbolos del alfabeto se interpreta como el campo finito de orden q y, por lo tanto, q 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 R = k/n es una constante y, además, la longitud del bloque es igual o inferior al tamaño del alfabeto, es decir, n = q o n = q − 1.

Reed &amperio; La visión original de Solomon: la palabra clave como una secuencia de valores

Hay diferentes procedimientos de codificación para el código Reed-Solomon, y por lo tanto, hay diferentes maneras de describir el conjunto de todas las palabras clave. En la vista original de Reed & Solomon (1960), cada palabra clave del código Reed-Solomon es una secuencia de valores de función de un polinomio de grado menos que k. Para obtener una palabra clave del código Reed-Solomon, los símbolos de mensaje (cada uno dentro del alfabeto tamaño q) se tratan como los coeficientes de un polinomio p de grado inferior a k, sobre el campo finito F con q elementos. A su vez, el polinomio p se evalúa en n ≤ q puntos distintos a1,...... ,an{displaystyle a_{1},dotsa_{n} sobre el terreno 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, α, α²,... αⁿ⁻²}, o para n. q, {1, α, α²,... αⁿ⁻¹}, donde... α es un elemento primitivo F.

Formally, el set C{displaystyle mathbf {C} de las palabras clave del código Reed-Solomon se define como sigue:

k{displaystyle k}

k− − 1{displaystyle k-1}

n− − ()k− − 1)=n− − k+1{displaystyle n-(k-1)=n-k+1}

k− − 1{displaystyle k-1}

d=n− − k+1{displaystyle d=n-k+1}

δ δ =d/n=1− − k/n+1/n=1− − R+1/n♪ ♪ 1− − R{displaystyle delta =d/n=1-k/n+1/n=1-R+1/nsim 1-R}

R=k/n{displaystyle R=k/n

δ δ +R≤ ≤ 1+1/n{displaystyle delta +Rleq 1+1/n}

Mientras que el número de polinomios diferentes de grado menos que k y el número de mensajes diferentes son iguales qk{displaystyle q^{k}, y por lo tanto cada mensaje se puede mapear de forma única a tal polinomio, hay diferentes maneras de hacer esta codificación. La construcción original de Reed & Solomon (1960) interpreta el mensaje x como coeficientes del polinomio p, mientras que construcciones posteriores interpretan el mensaje como valores del polinomio en el primero k puntos a1,...... ,ak{displaystyle a_{1},dotsa_{k} y obtener el polinomio p interpolando estos valores con un polinomio de grado inferior a k. Este último procedimiento de codificación, siendo 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.

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

En la construcción original de Reed & Solomon (1960), el mensaje x=()x1,...... ,xk)▪ ▪ Fk{displaystyle x=(x_{1},dotsx_{k}in F^{k} es mapeado al polinomio px{displaystyle p_{x} con

px()a)=.. i=1kxiai− − 1.{displaystyle p_{x}(a)=sum ¿Qué?

x{displaystyle x}

px{displaystyle p_{x}

n{displaystyle n}

a1,...... ,an{displaystyle a_{1},dotsa_{n}

F{displaystyle F}

C:Fk→ → Fn{displaystyle C:F^{k}to F^{n}

C()x)=()px()a1),...... ,px()an)).{displaystyle C(x)={bigl (}p_{x}(a_{1}),dotsp_{x}(a_{n}){bigr)},}

C{displaystyle C}

C()x)=xTA{displaystyle C(x)=x^{T}A}

k× × n{displaystyle ktimes n}

A{displaystyle A}

F{displaystyle F}

A=[1...... 1...... 1a1...... ak...... ana12...... ak2...... an2⋮ ⋮ ⋮ ⋮ ⋮ ⋮ a1k− − 1...... akk− − 1...... ank− − 1]{displaystyle A={begin{bmatrix}1 limitdots &1 limitdots &1a_{1} limitdots &a_{k} limitdots ¿Qué? ¿Qué? ################################################################################################################################################################################################################################################################ ¿Qué? {fn}fn}

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

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

Hay un procedimiento alternativo de codificación que también produce el código Reed-Solomon, pero eso lo hace de manera sistemática. Aquí, la asignación del mensaje x{displaystyle x} al polinomio px{displaystyle p_{x} trabaja de manera diferente: el polinomio px{displaystyle p_{x} ahora se define como el polinomio único de grado menos que k{displaystyle k} tales que

px()ai)=xipara todosi▪ ▪ {}1,...... ,k}.{displaystyle p_{x}(a_{i})=x_{i}{text{ for all }iin {1,dotsk}

px{displaystyle p_{x}

x{displaystyle x}

ak+1,...... ,an{displaystyle a_{k+1},dotsa_{n}

C:Fk→ → Fn{displaystyle C:F^{k}to F^{n}

C()x)=()px()a1),...... ,px()an)).{displaystyle C(x)={bigl (}p_{x}(a_{1}),dotsp_{x}(a_{n}){bigr)},}

k{displaystyle k}

C()x){displaystyle C(x)}

x{displaystyle x}

C{displaystyle C}

C()x)=xG{displaystyle C(x)=xG}

G=()A's izquierda submatrix cuadrado)− − 1⋅ ⋅ A=[100...... 0g1,k+1...... g1,n010...... 0g2,k+1...... g2,n001...... 0g3,k+1...... g3,n⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0...... 0...... 1gk,k+1...... gk,n]{displaystyle G=(A{text{'s left square submatrix}}})^{-1}cdot A={begin{bmatrix}1 Pulso0 ventajadots > } {1,k+1} {dots > {1,n}} limit1} > > ##### {2,n} âTMa âTMa < > > > > }vdots &vdots &vdots &vdots > 'vdots &vdots > 'vdots > } > {}}

Transformada discreta de Fourier y su inversa

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

C()x)=()px()a1),...... ,px()an)).{displaystyle C(x)={bigl (}p_{x}(a_{1}),dotsp_{x}(a_{n}){bigr)},}

La transformada inversa de Fourier podría usarse para convertir un conjunto libre de errores de n < Los valores del mensaje q vuelven al polinomio de codificación de los coeficientes k, 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 α:

ai=α α i− − 1{displaystyle A_{i}=alpha ^{i-1}

a1,...... ,an={}1,α α ,α α 2,...... ,α α n− − 1}{displaystyle a_{1},dotsa_{n}={1,alphaalpha ^{2},dotsalpha ^{n-1}}}

Sin embargo, la interpolación de Lagrange realiza la misma conversión sin la restricción en el conjunto de puntos de evaluación o el requisito de un conjunto de valores de mensaje sin 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

A este respecto, el mensaje se interpreta como los coeficientes de un polinomio p()x){displaystyle p(x)}. El remitente calcula un polinomio relacionado s()x){displaystyle s(x)} grado n− − 1{displaystyle n-1} Donde n≤ ≤ q− − 1{displaystyle nleq q-1} y envía el polinomio s()x){displaystyle s(x)}. El polinomio s()x){displaystyle s(x)} se construye multiplicando el mensaje polinomio p()x){displaystyle p(x)}, que tiene grado k− − 1{displaystyle k-1}, con un polinomio generador g()x){displaystyle g(x)} grado n− − k{displaystyle No. que es conocido tanto por el remitente como por el receptor. El polinomio del generador g()x){displaystyle g(x)} se define como el polinomio cuyas raíces son poderes secuenciales del campo Galois primitivo α α {displaystyle alpha }

g()x)=()x− − α α i)()x− − α α i+1)⋯ ⋯ ()x− − α α i+n− − k− − 1)=g0+g1x+⋯ ⋯ +gn− − k− − 1xn− − k− − 1+xn− − k{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 - ¿Qué?

Para un "código de sentido estrecho", i=1{displaystyle i=1}.

C={}()s1,s2,...... ,sn)Silencios()a)=.. i=1nsiaies un polinomio que tiene al menos las raícesα α 1,α α 2,...... ,α α n− − k}.{displaystyle mathbf {C} =left{left} (s_{1},s_{2},dotss_{n}right);{\ Grandes vidas Es un polinomio que tiene al menos las raíces.

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 clave contiene el mensaje como prefijo, y simplemente anexa símbolos de corrección de errores como sufijo. Aquí, en lugar de enviar s()x)=p()x)g()x){displaystyle s(x)=p(x)g(x)}, el encoder construye el polinomio transmitido s()x){displaystyle s(x)} tales que los coeficientes de los k{displaystyle k} monomiales más grandes son iguales a los coeficientes correspondientes de p()x){displaystyle p(x)}, y los coeficientes de orden inferior de s()x){displaystyle s(x)} son elegidos exactamente de tal manera que s()x){displaystyle s(x)} se vuelve divisible por g()x){displaystyle g(x)}. Luego los coeficientes de p()x){displaystyle p(x)} son una subsequencia de los coeficientes de s()x){displaystyle s(x)}. Para obtener un código que sea sistemático, construimos el polinomio del mensaje p()x){displaystyle p(x)} interpretando el mensaje como la secuencia de sus coeficientes.

Formalmente, la construcción se realiza multiplicando p()x){displaystyle p(x)} por xt{displaystyle x^{t} para hacer espacio para el t=n− − k{displaystyle T=n-k comprobar símbolos, dividir ese producto por g()x){displaystyle g(x)} encontrar el resto, y luego compensar por el resto restante restándolo. El t{displaystyle t} los símbolos de verificación se crean computando el resto sr()x){displaystyle s_{r}(x)}:

sr()x)=p()x)⋅ ⋅ xtmodg()x).{displaystyle s_{r}(x)=p(x)cdot x^{t} {bmod { }g(x).}

El resto tiene título en la mayoría t− − 1{displaystyle t-1}, mientras que los coeficientes de xt− − 1,xt− − 2,...... ,x1,x0{displaystyle x^{t-1},x^{t-2},dotsx^{1},x^{0} en el polinomio p()x)⋅ ⋅ xt{displaystyle p(x)cdot x^{t} son cero. Por lo tanto, la siguiente definición de la palabra clave s()x){displaystyle s(x)} tiene la propiedad que el primero k{displaystyle k} los coeficientes son idénticos a los coeficientes de p()x){displaystyle p(x)}:

s()x)=p()x)⋅ ⋅ xt− − sr()x).{displaystyle s(x)=p(x)cdot x^{t}-s_{r}(x),}

Como resultado, las palabras clave s()x){displaystyle s(x)} son, en efecto, elementos C{displaystyle mathbf {C}, es decir, son divisibles por el polinomio generador g()x){displaystyle g(x)}:

s()x)↑ ↑ p()x)⋅ ⋅ xt− − sr()x)↑ ↑ sr()x)− − sr()x)↑ ↑ 0modg()x).{displaystyle s(x)equiv p(x)cdot x^{t}-s_{r}(x)equiv s_{r}(x)-s_{r}(x)equiv 0mod g(x),}

Propiedades

El código Reed-Solomon es un [n, k, n − k + 1] código; en otras palabras, es un código de bloque lineal de longitud n (sobre F) con dimensión k y mínima distancia Hamming dmin=n− − k+1.{textstyle d_{min }=n-k+1.} 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. Dicho código también se llama un código separable de distancia máxima (MDS).

La capacidad de corrección de errores de un código Reed-Solomon se determina por su distancia mínima, o equivalentemente, por n− − k{displaystyle No., la medida de redundancia en el bloque. Si las ubicaciones de los símbolos de error no se conocen por adelantado, entonces un código Reed-Solomon puede corregir hasta ()n− − k)/2{displaystyle (n-k)/2} símbolos erróneos, es decir, puede corregir la mitad de los errores, ya que hay símbolos redundantes añadidos al bloque. A veces, las ubicaciones de errores se conocen de antemano (por ejemplo, "información del lado" en las ratios de señal a ruido de demodulador) —se llaman borrados. Un código Reed-Solomon (como cualquier código MDS) es capaz de corregir el doble de borraciones como errores, y cualquier combinación de errores y borraciones puede ser corregido mientras la relación 2E + S ≤ n − k está satisfecho, donde E{displaystyle E} es el número de errores y S{displaystyle S. es el número de borrados en el bloque.

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

El límite de error teórico se puede describir a través de la siguiente fórmula para el canal AWGN para FSK:

Pb.. 2m− − 12m− − 11n.. l l =t+1nl l ()nl l )Psl l ()1− − Ps)n− − l l {fnMicroc {2}{2}{m}{m} {f} {f}} {f}} {f}}} {f}}}} {f}}}} {f}}}}}} {f}}} {f} {1}{n}sum _{ell =t+1}{n}ell {nchoose ell }P_{s} {ell } {fn} {fnfn} {fnfn}}} {fn}} {fnfn}} {fnfnfn}} {fn}}} {fnfn}}}}fnfn}}}fn}}}}fnfn}}fnfn}fn}fnfnfnfn}fnfnfnfnfn}fnfnfn}fn}fn}fncfncfnfnfnfn}fn}fn}fn}fn}fn}fnfnfncfn}fnfn

Pb.. 1m1n.. l l =t+1nl l ()nl l )Psl l ()1− − Ps)n− − l l {displaystyle P_{b}approx {fnMicroc} {fnMicroc} {fnMicroc}} {fnMicroc}} {fn}} {fnMicroc}}}} {fn}} {fnMicroc} {fn}} {fnMicroc}}}} {fnMicroc}}} {f}}} {f}}} {f}}}}} {f}}}} {f}} {f}}} {f} {f}} {f} {f} {fnMicroc}} {f}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {f}}}} {f}}}} {fnMicroc} {f}} {f}}}}}} {fn}}}}}}}}}}}}}}}}}}}}}}}}}}}} {1}{n}sum _{ell =t+1}{n}ell {nchoose ell }P_{s} {ell } {fn} {fnfn} {fnfn}}} {fn}} {fnfn}} {fnfnfn}} {fn}}} {fnfn}}}}fnfn}}}fn}}}}fnfn}}fnfn}fn}fnfnfnfn}fnfnfnfnfn}fnfnfn}fn}fn}fncfncfnfnfnfn}fn}fn}fn}fn}fn}fnfnfncfn}fnfn

t=12()dmin− − 1){textstyle t={frac {2} {fnMincrosoft Sans Serif}

Ps=1− − ()1− − s)h{displaystyle P_{s}=1-(1-s)

h=mlog2⁡ ⁡ M{displaystyle h={frac {m}{log} ¿Qué?

s{displaystyle s}

M{displaystyle M}

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

Las propiedades del código Reed-Solomon discutidas anteriormente los hacen especialmente adecuados para aplicaciones donde los errores ocurren en ráfagas. Esto se debe a que al código no le importa cuántos bits en un símbolo están erróneos; si varios bits en un símbolo están dañados, solo cuenta como un solo error. Por el contrario, si un flujo de datos no se caracteriza por ráfagas de errores o abandonos, 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 de los canales se han invertido en algún lugar 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. Los "desaparecidos" los bits en un código abreviado deben completarse con ceros o unos, dependiendo de si los datos se complementan o no. (Para decirlo de otra manera, si los símbolos están invertidos, entonces el relleno cero debe invertirse en un relleno). Por esta razón, es obligatorio que el sentido de los datos (es decir, verdadero o complementado) se resuelva. antes de la decodificación Reed-Solomon.

Si el código Reed-Solomon es cíclico o no depende de detalles sutiles de la construcción. En la vista original de Reed y Salomón, 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 cíclico. En particular, si α α {displaystyle alpha } es una raíz primitiva del campo F{displaystyle F}, entonces por definición todos los elementos no cero de F{displaystyle F} tomar el formulario α α i{displaystyle alpha ^{i} para i▪ ▪ {}1,...... ,q− − 1}{displaystyle iin {1,dotsq-1}, donde q=SilencioFSilencio{displaystyle q=viviendaF. Cada polinomio p{displaystyle p} sobre F{displaystyle F} da lugar a una palabra clave ()p()α α 1),...... ,p()α α q− − 1)){displaystyle (p(alpha ^{1}),dotsp(alpha ^{q-1})}. Desde la función a↦ ↦ p()α α a){displaystyle amapsto p(alpha a)} es también un polinomio del mismo grado, esta función da lugar a una palabra clave ()p()α α 2),...... ,p()α α q)){displaystyle (p(alpha ^{2}),dotsp(alpha ^{q})}; desde α α q=α α 1{displaystyle alpha ^{q}=alpha ^{1} sostiene, esta palabra clave es la izquierda cíclica de la palabra clave original derivada de p{displaystyle p}. Así que elegir una secuencia de poderes raíz primitivos como los puntos de evaluación hace la vista original Reed–Solomon code cyclic. Los códigos Reed-Solomon en la vista BCH siempre son cíclicos porque los códigos BCH son cíclicos.

Observaciones

Los diseñadores no están obligados a utilizar el "natural" tamaños de 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 ampliamente utilizado (255,223) se puede convertir en un código (160,128) rellenando la parte no utilizada del bloque fuente con 95 ceros binarios y no transmitiéndolos. En el decodificador, la misma porción del bloque se carga localmente con ceros binarios. El teorema de Delsarte-Goethals-Seidel ilustra un ejemplo de una aplicación de códigos abreviados de Reed-Solomon. Paralelamente al acortamiento, una técnica conocida como punción permite omitir algunos de los símbolos de paridad codificados.

BCH ver decodificadores

Los decodificadores descritos en esta sección utilizan la vista BCH de una palabra clave 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 de junio de 1961. El decodificador Gorenstein-Zierler y el trabajo relacionado con los códigos BCH se describen en un libro Códigos de corrección de errores de W. Wesley Peterson (1961).

Formulación

El mensaje transmitido, ()c0,...... ,ci,...... ,cn− − 1){displaystyle (c_{0},ldotsc_{i},ldotsc_{n-1}}, se considera como los coeficientes de un polinomio s()x):

s()x)=.. i=0n− − 1cixi{displaystyle s(x)=sum ¿Qué?

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

g()x)=∏ ∏ j=1n− − k()x− − α α j),{displaystyle g(x)=prod _{j=1}{n-k}(x-alpha ^{j}),}

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

s()x)mod()x− − α α j)=g()x)mod()x− − α α j)=0{displaystyle s(x){bmod {}x-alpha ^{j})=g(x){bmod {}x-alpha ^{j}=0}

s()α α j)=0,j=1,2,...... ,n− − k{displaystyle s(alpha ^{j})=0, j=1,2,ldotsn-k}

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

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

e()x)=.. i=0n− − 1eixi{displaystyle e(x)=sum ¿Qué?

El coeficiente e_i será cero si no hay error a esa potencia de x y distinto de cero si hay error. Si hay ν errores en distintas potencias i_k de x, entonces

e()x)=.. k=1.. eikxik{displaystyle e(x)=sum _{k=1}{nu }

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_ik). De ellos, e(x) se puede calcular y restar de r(x) para obtener el envío original mensaje s(x).

Descodificación del síndrome

El decodificador comienza evaluando el polinomio tal como se recibe en puntos α α 1...... α α n− − k{displaystyle alpha ^{1}dots alpha ^{n-k}. Llamamos a los resultados de esa evaluación los "syndromes", S_j. Se definen como:

Sj=r()α α j)=s()α α j)+e()α α j)=0+e()α α j)=e()α α j)=.. k=1.. eik()α α j)ik,j=1,2,...... ,n− − k{displaystyle {begin{aligned}S_{j} limit=r(alpha ^{j})=s(alpha ^{j})+e(alpha ^{j})=0+e(alpha ^{j})}\\alpha ^{j})\\sum= ¿Por qué? }e_{i_{k}left(alpha ^{j}right)}quad j=1,2,ldotsn-kend{aligned}}

s()α α j)=0{displaystyle s(alpha ^{j})=0}

s()x){displaystyle s(x)}

α α j{displaystyle alpha ^{j}

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

Localizadores de error y valores de error

Para mayor comodidad, defina los localizadores de errores X_k y valores de error Y _k como:

Xk=α α ik,Yk=eik{displaystyle ¿Qué? Sí.

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

Sj=.. k=1.. YkXkj{displaystyle S_{j}=sum _{k=1}{nu Sí.

Esta definición de los valores del síndrome es equivalente a la anterior desde ()α α j)ik=α α jAlternativa Alternativa ik=()α α ik)j=Xkj{displaystyle (alpha ^{j})}=alpha ^{j*i_{k}=(alpha) ¿Qué?.

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

[X11X21⋯ ⋯ X.. 1X12X22⋯ ⋯ X.. 2⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ X1n− − kX2n− − k⋯ ⋯ X.. n− − k][Y1Y2⋮ ⋮ Y.. ]=[S1S2⋮ ⋮ Sn− − k]{displaystyle {begin{bmatrix}X_{1}{1} {2}^{1}cdots ################################################################################################################################################################################################################################################################ ¿Qué? {begin{bmatrix}S_{1}S_{2}\\vdots {cHFF}}

En consecuencia, el problema es encontrar la X_k, porque entonces se conocería la matriz más a la izquierda, y ambos lados de la ecuación podrían multiplicarse por su inversa, dando como resultado 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 erroresX_k) ya son conocidos por algún otro método (por ejemplo, en una transmisión FM, las secciones donde el bitstream no estaba claro o superado con interferencia son probabilísticamente determinantes del análisis de frecuencias). En este escenario, hasta n− − k{displaystyle No. se pueden corregir errores.

El resto del algoritmo sirve para localizar los errores, y requerirá valores de síndrome hasta 2v{displaystyle 2v}, en lugar de sólo el v{displaystyle v} utilizado hasta ahora. Es por eso que 2x como muchos símbolos de corrección de errores necesitan ser añadidos como se puede corregir sin conocer sus ubicaciones.

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

▪ ▪ ()x)=∏ ∏ k=1.. ()1− − xXk)=1+▪ ▪ 1x1+▪ ▪ 2x2+⋯ ⋯ +▪ ▪ .. x.. {displaystyle Lambda (x)=prod ¿Por qué? Lambda - ¿Qué? Lambda ##{2}x^{2}+cdots Lambda...

Los ceros de .x) son los recíprocos Xk− − 1{displaystyle ¿Qué?. Esto se deriva de la construcción de notación de productos arriba, ya que si x=Xk− − 1{displaystyle x=X_{k} {-1} entonces uno de los términos multiplicados será cero ()1− − Xk− − 1⋅ ⋅ Xk)=1− − 1=0{displaystyle (1-X_{k}{-1}cdot X_{k}=1-1=0}, haciendo que todo el polinomio evalúe a cero.

▪ ▪ ()Xk− − 1)=0{displaystyle Lambda (X_{k}{-1}=0}

Vamos j{displaystyle j} ser cualquier entero tal que 1≤ ≤ j≤ ≤ .. {displaystyle 1leq jleqnu}. Multiplique ambos lados por YkXkj+.. {displaystyle Y... y todavía será cero.

YkXkj+.. ▪ ▪ ()Xk− − 1)=0.YkXkj+.. ()1+▪ ▪ 1Xk− − 1+▪ ▪ 2Xk− − 2+⋯ ⋯ +▪ ▪ .. Xk− − .. )=0.YkXkj+.. +▪ ▪ 1YkXkj+.. Xk− − 1+▪ ▪ 2YkXkj+.. Xk− − 2+⋯ ⋯ +▪ ▪ .. YkXkj+.. Xk− − .. =0.YkXkj+.. +▪ ▪ 1YkXkj+.. − − 1+▪ ▪ 2YkXkj+.. − − 2+⋯ ⋯ +▪ ▪ .. YkXkj=0.{displaystyle {begin{aligned} Lambda (X_{k} {-1})=0.[1ex] ¿Qué? Lambda ¿Qué? +Lambda _{nu ################################################################################################################################################################################################################################################################ }+Lambda - Sí. }X_{k} {-1}+ Lambda - Sí. }X_{k} {-2}+cdots +Lambda _{nu - Sí. }X_{k}{-nu }=0. }+Lambda - Sí. -1}+Lambda - Sí. -2}+cdots +Lambda _{nu - Sí.

La suma de k = 1 a ν y seguirá siendo cero.

.. k=1.. ()YkXkj+.. +▪ ▪ 1YkXkj+.. − − 1+▪ ▪ 2YkXkj+.. − − 2+⋯ ⋯ +▪ ▪ .. YkXkj)=0{displaystyle sum _{k=1}{nu }left(Y_{k}X_{k}^{j+nu }+Lambda - Sí. -1}+Lambda - Sí. -2}+cdots +Lambda _{nu Sí.

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

().. k=1.. YkXkj+.. )+().. k=1.. ▪ ▪ 1YkXkj+.. − − 1)+().. k=1.. ▪ ▪ 2YkXkj+.. − − 2)+⋯ ⋯ +().. k=1.. ▪ ▪ .. YkXkj)=0{displaystyle left(sum _{k=1}^{nu }Y_{k}X_{k}{j+nu }right)+left(sum) ¿Por qué? Lambda - Sí. -1}right)+left(sum) ¿Por qué? Lambda ¿Por qué? Lambda Sí.

Extraer los valores constantes ▪ ▪ {displaystyle Lambda } que no son afectados por la suma.

().. k=1.. YkXkj+.. )+▪ ▪ 1().. k=1.. YkXkj+.. − − 1)+▪ ▪ 2().. k=1.. YkXkj+.. − − 2)+⋯ ⋯ +▪ ▪ .. ().. k=1.. YkXkj)=0{displaystyle left(sum _{k=1}^{nu }Y_{k}X_{k}{j+nu }right)+ Lambda _{1}left(sum _{k=1}{nu Y... Lambda _{2}left(sum) ¿Por qué? Y... +Lambda _{nu }left(sum _{k=1}{nu Sí.

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

Sj+.. +▪ ▪ 1Sj+.. − − 1+⋯ ⋯ +▪ ▪ .. − − 1Sj+1+▪ ▪ .. Sj=0{displaystyle S_{j+nu }+Lambda _{1}S_{j+nu -1}+cdots +Lambda _{nu - 1}S_{j+1}+Lambda _{nu }S_{j}=0}

Subtracting Sj+.. {displaystyle S_{j+nu}} de ambas partes rendimientos

Sj▪ ▪ .. +Sj+1▪ ▪ .. − − 1+⋯ ⋯ +Sj+.. − − 1▪ ▪ 1=− − Sj+.. {displaystyle S_{j}Lambda _{nu Lambda -1}+cdots +S_{j+nu Lambda - Sí.

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

[S1S2⋯ ⋯ S.. S2S3⋯ ⋯ S.. +1⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ S.. S.. +1⋯ ⋯ S2.. − − 1][▪ ▪ .. ▪ ▪ .. − − 1⋮ ⋮ ▪ ▪ 1]=[− − S.. +1− − S.. +2⋮ ⋮ − − S.. +.. ]{displaystyle {begin{bmatrix}S_{1} limitS_{2} limitcdots & s_{nuts} }S_{2} limits_{3} limitcdots & s_{nu +1}\\vdots > 'ddots > ################################################################################################################################################################################################################################################################ Lambda... Lambda... ################################################################################################################################################################################################################################################################ ####-S_{nu +2}\vdots {fn}

Encuentra las raíces del polinomio localizador de errores

Use los coeficientes ≥_i encontrado en el último paso para construir la ubicación de error polinomial. Las raíces del polinomio de localización de errores se pueden encontrar por 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 revertir, en cuyo caso las raíces de ese polinomio inverso son los localizadores de errores Xk{displaystyle X_{k} (no sus recíprocos Xk− − 1{displaystyle ¿Qué?). La búsqueda de pollo es una implementación eficiente de este paso.

Calcular los valores de error

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

Calcular las ubicaciones de error

Cálculo i_k tomando la base de registro α α {displaystyle alpha } de X_k. Esto se hace generalmente utilizando una tabla de búsqueda precomputada.

Corrige los errores

Finalmente, e(x) se genera a partir de i_k y e _ik y luego se resta de r(x) para obtener el mensaje enviado originalmente s (x), con 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

g()x)=()x− − 3)()x− − 32)()x− − 33)()x− − 34)=x4+809x3+723x2+568x+522{displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}

sr()x)=p()x)xtmodg()x)=547x3+738x2+442x+455[displaystyle s_{r}(x)=p(x),x^{t}{bmod {}(x)=547x^{3}+738x^{2}+442x+455}

s()x)=p()x)xt− − sr()x)=3x6+2x5+1x4+382x3+191x2+487x+474{displaystyle s(x)=p(x),x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474}

r()x)=s()x)+e()x)=3x6+2x5+123x4+456x3+191x2+487x+474{displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474}

S1=r()31)=3⋅ ⋅ 36+2⋅ ⋅ 35+123⋅ ⋅ 34+456⋅ ⋅ 33+191⋅ ⋅ 32+487⋅ ⋅ 3+474=732{displaystyle S_{1}=r(3^{1})=3cdot 3^{6}+2cdot 3^{5}+123cdot 3^{4}+456cdot 3^{3}+191cdot 3^{2}+487cdot 3+474=732}

S2=r()32)=637,S3=r()33)=762,S4=r()34)=925{displaystyle S_{2}=r(3^{2})=637,;S_{3}=r(3^{3})=762,;S_{4}=r(3^{4})=925}

[732637637762][▪ ▪ 2▪ ▪ 1]=[− − 762− − 925]=[167004]{displaystyle {begin{bmatrix}732 limit637637}{bmatrix}{begin{bmatrix}Lambda Lambda {begin{bmatrix}}={begin{bmatrix}-762\-925end{bmatrix}={begin{bmatrix}16704end{bmatrix}}}}

Usando la eliminación gaussiana:

[001000000001][▪ ▪ 2▪ ▪ 1]=[329821]{displaystyle {begin{bmatrix}0000 recur001end{bmatrix}{begin{bmatrix}Lambda Lambda ######### {begin{bmatrix}329821end{bmatrix}}}}

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

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.

Subtracting e1x3+e2x4=74x3+122x4{displaystyle e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4} del polinomio recibido r()x) reproduce la palabra clave original s.

Decodificador Berlekamp-Massey

El algoritmo 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:

Δ Δ =Si+▪ ▪ 1Si− − 1+⋯ ⋯ +▪ ▪ eSi− − e{displaystyle Delta =S_{i}+Lambda # S_{i-1}+cdots +Lambda _{e} S_{i-e}

Ejemplo

Usando los mismos datos que 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 del localizador de errores como el polinomio del valor del error se basa en la adaptación de Sugiyama del algoritmo euclidiano extendido.

Defina S(x), Λ(x) y Ω(x) para t y errores e:

S()x)=Stxt− − 1+St− − 1xt− − 2+⋯ ⋯ +S2x+S1▪ ▪ ()x)=▪ ▪ exe+▪ ▪ e− − 1xe− − 1+⋯ ⋯ +▪ ▪ 1x+1Ω Ω ()x)=Ω Ω exe+Ω Ω e− − 1xe− − 1+⋯ ⋯ +Ω Ω 1x+Ω Ω 0{displaystyle {begin{aligned}S(x) limitada=S_{t}x^{t-1}+S_{t-1}x^{t-2}+cdots +S_{2}x+S_{1}[1ex]Lambda (x) reducida=Lambda ¿Por qué? Lambda ## {e-1}x^{e-1}+cdots +Lambda _{1}x+1[1ex]Omega (x) reducida= Omega... Omega ## {e-1}x^{e-1}+cdots +Omega _{1}x+ Omega...

La ecuación clave es:

▪ ▪ ()x)S()x)=Q()x)xt+Ω Ω ()x){displaystyle Lambda (x)S(x)=Q(x)x^{t}+ Omega (x)}

Para t = 6 y e = 3:

[▪ ▪ 3S6x8▪ ▪ 2S6+▪ ▪ 3S5x7▪ ▪ 1S6+▪ ▪ 2S5+▪ ▪ 3S4x6S6+▪ ▪ 1S5+▪ ▪ 2S4+▪ ▪ 3S3x5S5+▪ ▪ 1S4+▪ ▪ 2S3+▪ ▪ 3S2x4S4+▪ ▪ 1S3+▪ ▪ 2S2+▪ ▪ 3S1x3S3+▪ ▪ 1S2+▪ ▪ 2S1x2S2+▪ ▪ 1S1xS1]=[Q2x8Q1x7Q0x6000Ω Ω 2x2Ω Ω 1xΩ Ω 0]{displaystyle {begin{bmatrix} Lambda "Lambda" "Lambda" - ¿Qué? "Lambda" "Lambda" ################################################################################################################################################################################################################################################################ S_{5}+ Lambda "Lambda" - ¿Qué? "Lambda" "Lambda" - ¿Qué? S_{3}+ Lambda "Lambda" - ¿Qué? Lambda "Lambda" ################################################################################################################################################################################################################################################################ {1}={0}\0\\0\0\\\\\\\\\4\\\\\\\\\\\4\\\\\\\\\\\\\\\4\\\\4\\\\\\\\\\\\\\\\\\4\\\\\\\\\\\\\\\\\\4\\\4 Omega ¿Por qué? Omega...

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

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

B(x) y Q(x) no necesitan guardarse, por lo que el algoritmo se convierte en:

R−1:= xtR0:= S()x)
A−1:= 0
A0:= 1
i:= 0
mientras grado de Ri ≥ t/2
 i:= i + 1
 Q:= Ri-2 / Ri-1 Ri:= Ri-2 - Q Ri-1 Ai:= Ai-2 - Q Ai-1

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

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

Ejemplo

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

Decodificador usando transformada discreta de Fourier

Se puede utilizar una transformada de Fourier discreta para la decodificación. 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 discreta de Fourier es un operador lineal, R(x) = C( x) + E(x).

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

Rj=Ej=Sj=r()α α j)para1≤ ≤ j≤ ≤ t{displaystyle ¿Qué?

Uso R1{displaystyle R_{1} a través de Rt{displaystyle R_{t} como síndromes (son los mismos) y generan el polinomio localizador de errores utilizando los métodos de cualquiera de los decodificadores anteriores.

Vamos v = número de errores. Generar E()x) utilizando los coeficientes conocidos E1{displaystyle E_{1} a Et{displaystyle E_{t}, el polinomio localizador de errores, y estas fórmulas

Luego calcula C(x) = R(x) − E(x) y tome 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 por arriba por n − k + 1. Por lo general, 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 Sudán y Venkatesan Guruswami en el MIT publicaron "Decodificación mejorada de los códigos de raza-salomónica y geometría algebraica" introduciendo un algoritmo que permitió la corrección de errores más allá de la mitad de la distancia mínima del código. 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 clave (es un algoritmo de decodificación de listas) y se basa en la interpolación y la factorización de polinomios sobre GF()2m){displaystyle GF(2^{m}} y sus extensiones.

Descodificació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 del canal en la corrección del símbolo. El advenimiento 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 flexible en tiempo polinomial para códigos Reed-Solomon, que se basó en el trabajo de Sudan y Guruswami. En 2016, Steven J. Franke y Joseph H. Taylor publicaron un novedoso decodificador de decisión blanda.

Ejemplo de MATLAB

Codificador

Aquí presentamos una implementación sencilla de MATLAB para un codificador.

función codificado = rsEncoder()msg, m, prim_poly, n, k) % RSENCODER codificar el mensaje con el algoritmo Reed-Solomon % m es el número de bits por símbolo % prim_poly: Primitive polynomial p(x). Ie for DM is 301 % k es el tamaño del mensaje % n es el tamaño total (k+redundant) % Ejemplo: msg = uint8('Test') % enc_msg = rsEncoder(msg, 8, 301, 12, numel(msg)); % Coge el alfa alfa = gf()2, m, prim_poly); % Obtener el Reed-Solomon generando polinomial g(x) g_x = genpoly()k, n, alfa); % Multiplique la información por X^(n-k), o simplemente remo con ceros al final % conseguir espacio para añadir 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 % Reed-Solomon generando polinomial g(x) [~, resto] = deconv()msg_padded, g_x); % Ahora devuelva el mensaje con la información redundante codificado = msg_padded - resto;final% Encontrar el Reed-Solomon generando polinomial g(x), por cierto este es el% igual que la función rsgenpoly en matlabfunción g = genpoly()k, n, alpha) g = 1; % Una multiplicación en el campo galois es sólo una convolución para k = mod()1 : n - k, n) g = conv()g, [1 alfa .^ ()k)); finalfinal

Decodificador

Ahora la parte de decodificación:

función [decodificado, error_pos, error_mag, g, S] = rsDecoder()codificado, m, prim_poly, n, k) % RSDECODER Decodifica un mensaje codificado Reed-Solomon % Ejemplo: % [dec, ~, ~, ~, ~] = rsDecoder(enc_msg, 8, 301, 12, numel(msg)) max_errors = planta baja()n - k) / 2); orig_vals = codificado.x; % Inicializar el vector de error errores = ceros()1, n); g = []; S = []; % Coge el alfa alfa = gf()2, m, prim_poly); % Encontrar los síndromes (Comprobar si dividir el mensaje por el generador % polinomial el resultado es cero) Sindical = polivalente()codificado, alfa .^ ()1:n - k)); Síndromes = trim()Sindical); % Si todos los síndromes son ceros (perfectamente divisibles) no hay errores si isempty()Síndromes.x) decodificado = orig_vals()1:k); error_pos = []; error_mag = []; g = []; S = Sindical; retorno; final % Prepare para el algoritmo euclideano (Usado para encontrar el error localizar % polinomios) r0 = [1, ceros()1, 2 * max_errors); r0 = gf()r0, m, prim_poly); r0 = trim()r0); size_r0 = longitud()r0); r1 = Síndromes; f = gf[ceros()1, size_r0 - 1) 1] m, prim_poly); f1 = gf()ceros()1, size_r0), m, prim_poly); g0 = f1; g1 = f; % Haga el algoritmo euclidiano en los polinomios r0(x) y Síndromes(x) en % orden de encontrar el error localizar polinomial mientras verdadero % Haz una larga división [quotient, resto] = deconv()r0, r1); % Añadir algunos ceros quotient = almohadilla()quotient, longitud()g1)); % Encontrar quotient*g1 y pad c = conv()quotient, g1); c = trim()c); c = almohadilla()c, longitud()g0)); % Update g as g0-quotient*g1 g = g0 - c; % Compruebe si el grado de permanencia (x) es inferior a max_errores si Todos()resto()1:final - max_errors) == 0) descanso; final % Actualizar r0, r1, g0, g1 y eliminar los ceros principales r0 = trim()r1); r1 = trim()resto); g0 = g1; g1 = g; final % Eliminar los ceros principales g = trim()g); % Encontrar los ceros del polinomio de error en este campo galois eval Poly = polivalente()g, alfa .^ ()n - 1 : - 1 : 0)); error_pos = gf()encontrar()eval Poly == 0), m); % Si no se encuentra ninguna posición de error devolvemos el trabajo recibido, porque % básicamente no es nada que podamos hacer y devolvemos el mensaje recibido si isempty()error_pos) decodificado = orig_vals()1:k); error_mag = []; retorno; final % Prepare un sistema lineal para resolver el error polinomio y encontrar el error % magnitudes size_error = longitud()error_pos); Síndrome_Vals = Síndromes.x; b(: 1) = Síndrome_Vals()1:size_error); para idx = 1 : size_error e = alfa .^ ()idx * ()n - error_pos.x)); err = e.x; er()idx, :) = err; final % Resolver el sistema lineal error_mag = ()gf()er, m, prim_poly)  gf()b, m, prim_poly)'; % Ponga la magnitud del error en el vector de error errores()error_pos.x) = error_mag.x; % Traiga este vector al campo galois errors_gf = gf()errores, m, prim_poly); % Ahora para corregir los errores sólo añadir con el código codificado decoded_gf = codificado()1:k) + errors_gf()1:k); decodificado = decoded_gf.x;final% Quitar los ceros principales de la matriz Galoisfunción gt = trim()g) gx = g.x; gt = gf()gx()encontrar()gx, 1) : final), g.m, g.prim_poly);final% Añadir ceros líderesfunción xpad = almohadilla()x, k) Len = longitud()x); si Len . k xpad = [ceros()1, k - Len) x]; finalfinal

Decodificadores de vista originales de Reed Solomon

Los decodificadores descritos en esta sección utilizan la vista original de Reed Solomon de una palabra clave como una secuencia de valores polinómicos donde el polinomio se basa en el mensaje que se 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 " Solomon (1960) describió un decodificador teórico que corrigió errores encontrando el mensaje más popular polinomio. El decodificador sólo conoce el conjunto de valores a1{displaystyle A_{1} a an{displaystyle a_{n} y qué método de codificación se utilizó para generar la secuencia de valores de la palabra clave. 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 valores de n codeword tomado k a la vez para producir polinomios potenciales en repetidas ocasiones, hasta que se produzca un número suficiente de polinomios coincidentes para eliminar razonablemente cualquier error en la palabra clave recibida. Una vez que se determina un polinomio, se pueden corregir errores en la palabra clave, recalculando los valores correspondientes de la palabra clave. Desafortunadamente, en todos menos los casos más simples, hay demasiados subconjuntos, por lo que el algoritmo es poco práctico. El número de subconjuntos es el coeficiente binomio, ()nk)=n!()n− − k)!k!{fnMicrosoft} {n}={n! ¡Vamos!, y el número de subconjuntos es infeasible para códigos incluso modestos. Para un ()255,249){displaystyle (255,249)} código que puede corregir 3 errores, el decodificador teórico ingenuo examinaría 359 billones de subsets.

Decodificador Berlekamp Welch

En 1986, un decodificador conocido como el algoritmo Berlekamp-Welch fue desarrollado como un decodificador que es capaz de recuperar el mensaje original polinomio así como un error "locator" polinomio que produce ceros para los valores de entrada que corresponden a errores, con complejidad de tiempo O()n3){displaystyle O(n^{3}}, donde n{displaystyle n} es el número de valores en un mensaje. El polinomio recuperado se utiliza entonces para recuperar (recalcular según sea necesario) el mensaje original.

Ejemplo

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

Si el polinomio del mensaje es

La palabra clave es

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

Las ecuaciones clave son:

biE()ai)− − Q()ai)=0{displaystyle b_{i}E(a_{i})-Q(a_{i}=0}

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

bi()e0+e1ai)− − ()q0+q1ai+q2ai2+q3ai3+q4ai4)=− − biai2{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}{3}+q_{4}a_} {4} {4}}=-b_{i}a_}a_}a_}a_} {i}a_} {i} {i}{i} {i} {i} {i} {i} {i} {i} {i} {i}{i} {} {} {} {} {}} {}} {}}}} {} {} {}}}} {}} {}} {}}} {}}}} {} {} {}}}} {} {}}}} {}}}}}} {}}}}} {}}}} {} {}}} {}}}}}}}}}}} {}}}}}}}}}}}

[001000928000000000000006006928928928928928123246928927925921913456439928926920902848057228928925913865673086430928924904804304121726928923893713562][e0e1q0q1q2q3q4]=[000923437541017637289]{} {} {}}}4} {}}}}} {}}}}}} {}}} {}}}} {}}}} {}}}}}}}} {}}}}} {}}}}} {}}}}}}}}}}}} {}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}} {b} {}}}}} {b} {]}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}b}

Usando la eliminación gaussiana:

[001000000000000000000000001000000000000000000000001000000000000000000000001000000000000000000000001000000000000000000000001000000000000000000000001][e0e1q0q1q2q3q4]=[006924006007009916003]{0}} {0} {0}}}}b}}}}}}b} {0} {0} {0}}}}}}}}}}}}} {0} {0} {0}}}} {0} {0}}}

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

Decodificador Gao

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

Ejemplo

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

• R− − 1=∏ ∏ i=1n()x− − ai){displaystyle R_{-1}=prod ¿Qué?
• R0={displaystyle R_{0}= Lagrange interpolation of {}ai,b()ai)}{displaystyle {a_{i},b(a_{i}} para i = 1 a n
• A− − 1=0{displaystyle A_{-1}=0}
• A0=1{displaystyle A_{0}=1}

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

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