Reed-Solomon

Este código se forma sobre la base de grupos de bits que se denominan símbolos. El código Reed-Solomon trabaja con los símbolos en vez de con los bits individuales.

Un símbolo es una secuencia de "m" bits individuales que aparecen en serie. Un símbolo es erróneo cuando al menos un bit del símbolo tiene error.

El código Reed-Solomon tiene las siguientes características:

• Cada símbolo está constituido por "m" bits consecutivos agrupados.
• Cada palabra-código consta de "k" símbolos de información (en lugar de bits), y "r" símbolos de paridad.
• La longitud de la palabra-código es: ${\displaystyle n=k+r}$ símbolos,(longitud=${\displaystyle nm}$ expresada en n.º de bit).
• Se establece la relación: ${\displaystyle n=2^{m}-1}$ entre la longitud de la palabra código (n) y el número de símbolos (${\displaystyle 2^{m}}$).
• Es capaz de corregir errores en "t" símbolos, donde ${\displaystyle t=r/2}$.

La versión pensada por Irving S. Reed y Gustave Solomon era muy sencilla. Pero tenía un problema, se comprobó que a la práctica era ineficiente si los valores de los parámetros eran grandes.

Definición Original

La idea es que a partir de una información, creamos un polinomio. Inicialmente fijamos un cuerpo finito C_q, un elemento primitivo α∈C_q y finalmente un entero 1≤N≤q-1. Consideramos la palabra

m= (m₀,m₁,m₂,...m_α^q-2) la cual identificaremos con el polinomio

A partir de aquí, se trata de codificar m por el vector que contiene las evaluaciones de m(x)en cada uno de los elementos C_q:

Vector-> V=(m(α⁰),m(α¹),m(α²),...,m(α^q-2))

Si consideramos el teorema de Interpolación solo existe un único polinomio de grado ≤N-1 que pase por N puntos dados de C_q²de abscisas. Cualquiera N coordenadas de la palabra codificada V son suficientes para recuperar la información inicial m. Entonces, aunque se pierdas algunos símbolos o se hayan corrompido algunos, la palabra m se podrá recuperar siempre que queden como mínimo N símbolos correctos. La finalidad es que, si el número de errores es suficientemente pequeño, a partir de este método podremos descodificar la información recibida en el receptor y a la vez corregirla, recuperando la información enviada por el emisor tal y como ha sido enviada. Por lo tanto, finalmente definimos el código Reed-Solomon como:

RS_q(N)={(m(α⁰),m(α¹),m(α²),...,m(α^q-2))∈ C_q^q-1}

La definición inicial de Irving Reed y Gustave Solomon necesitaba muchas interpolaciones para poder corregir la información, ya que, por ejemplo, si usamos los valores q=16 y N=7, es necesario realizar 6435 interpolaciones, hecho que merma eficiencia al código inicial.

Por esta razón se decidió utilizar un método más eficiente, mediante la Transformada Discreta de Fourier. Consideramos C_q un cuerpo finito, un elemento primitivo α∈C_q y finalmente imponemos N=q-1. Consideramos otra vez la palabra m y la evaluación en todas las potencias de α, tal y como se ha hecho el caso original. Ahora definimos una matriz tal y que el nombre de filas y columnas van de 0 a N-1. Por ejemplo: Consideremos N=5

El proceso de evaluación coincide con la multiplicación por C_α. Entonces lo podemos expresar como:

De esta forma es mucho más fácil y eficiente.

Este código se utiliza en:

• DVB (Digital Video Broadcasting).
• TDT.
• En sistemas de almacenamiento como el DVD.
• DAB+ (Digital Audio Broadcasting plus).
• Código QR

• Algoritmo de Berlekamp-Welch
• Teoría de la información
• Códigos detectores y correctores de error

• Más información de una página personal