Reed-Solomon
Reed-Solomon es un código cíclico no binario y constituye una subclase de los códigos BCH. Los códigos cíclicos son una subclase de los códigos de bloque estándar de detección y corrección de errores que protege la información contra errores en los datos transmitidos sobre un canal de comunicaciones. Este tipo de código pertenece a la categoría FEC (Forward Error Correction), es decir, corrige los datos alterados en el receptor y para ello utiliza unos bits adicionales que permiten esta recuperación a posteriori.
El código fue inventado por Irving S. Reed y Gustave Solomon (de ahí su nombre) en el año 1960. Este código se encuentra actualmente aplicado en áreas como los CD, telefonía móvil y sondas espaciales (la sonda Galileo a Júpiter en 1989, la sonda Magallanes a Venus ese mismo año o la sonda Ulises al Sol en 1990, por citar algunos ejemplos). También es de destacar el empleo del código Reed-Solomon en las comunicaciones por satélite Digital Video Broadcasting (DVB), en la transmisión digital de televisión ISDB-T, en la radio digital DAB+, así como en los sistemas xDSL de comunicación por cable, y en los códigos QR.
Características
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: símbolos,(longitud= expresada en n.º de bit).
- Se establece la relación: entre la longitud de la palabra código (n) y el número de símbolos ( ).
- Es capaz de corregir errores en "t" símbolos, donde .
Reed-Solomon Original
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 Cq, un elemento primitivo α∈Cq y finalmente un entero 1≤N≤q-1. Consideramos la palabra
m= (m0,m1,m2,...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 Cq:
- Vector-> V=(m(α0),m(α1),m(α2),...,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 Cq2de 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:
- RSq(N)={(m(α0),m(α1),m(α2),...,m(αq-2))∈ Cqq-1}
Definición actual
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 Cq un cuerpo finito, un elemento primitivo α∈Cq 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.