Reed-solomon

CODIGOS

REED-SOLOMON

MARIO MOYANO HERNÁNDEZ
GRUPO A
DNI: 70818367X

REED- SOLOMON

Códigos de corrección de errores Reed-Solomon IntroducciónEl 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 aplicación en áreas como los CDs, telefonía móvil y sondas espaciales (la sonda Galileo a Júpiter en 1989, lasonda 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), así como en los sistemas xDSL de comunicación por cable.

El codificador Reed-Solomon toma un bloque de información digital y añade bits redundantes. Los errores puedenocurrir durante la transmisión o almacenamiento de información por varios motivos (p. Ej. Ruido o interferencia, ralladuras en los discos compactos etc.). El decodificador Reed-Solomon procesa cada bloque e intenta corregir los errores y recuperar la información original. El número y tipo de errores que pueden ser corregidos depende de las características del código Reed-Solomon.
Propiedades delos códigos Reed-SolomonEl código Reed-Solomon es un subconjunto de los códigos BCH y son de bloques lineales. Un código Reed-Solomon se especifica como RS(n,k) con símbolos de s bits. Lo anterior significa que el codificador toma k símbolos de los s bit y añade símbolos de paridad para hacer una palabra de código de n símbolos. Existen n-k símbolos de paridad de s bits cada uno. Un decodificadorpuede corregir hasta t símbolos que contienen errores en una palabra de código, donde 2t=n-k.
El siguiente diagrama muestra una típica palabra de código Reed-Solomon (este se conoce como un código sistemático puesto que los datos se dejan inalterados y los símbolos de paridad se anexan):
Ejemplo: Un código popular Reed-Solomon es RS(255,223) con símbolos de 8 bits. Cada palabra de código contiene255 bytes de palabra de código, de los cuales 223 bytes son datos y 32 bytes son paridad. Para este código se tiene:
N=255, k=223, s=8
2t=32, t=16
El decodificador puede corregir cualquier error de 16 símbolos en la palabra de código, es decir, errores de hasta 16 bytes en cualquier lugar de la palabra pueden ser automáticamente corregidos.
Dado un tamaño de símbolo s, la máximalongitud de la palabra de código (n) para un código Reed-Solomon es n=2s − 1. Por ejemplo, la máxima longitud de un código con símbolos de 8 bits (s=8) es de 255 bytes. Los códigos Reed-Solomon pueden ser acortados haciendo un número de símbolos de datos igual a cero en el codificador, no transmitiendo estos, y reinsertando éstos en el decodificador.

EjemploEl código (255,223) descrito anteriormentepuede ser acortado a (200,168). El codificador toma un bloque de 168 bytes de datos añade 55 bytes cero, crea una palabra de código de (255,223) y transmite solo los 168 bytes de datos y 32 bytes de paridad.
La cantidad de poder de procesamiento para codificar y decodificar códigos Reed-Solomon se relaciona con el número de símbolos de paridad por palabra de código. Un valor grande de t significaque un gran número de errores pueden ser corregidos pero requiere mayor poder computacional que un valor pequeño de t.
Errores de SímboloUn error de símbolo ocurre cuando al menos un bit de un símbolo es erróneo.
EjemploRS(255,223) pude corregir 16 errores de símbolos. En el peor caso, errores de 16 bits pueden ocurrir, cada uno en un símbolo distinto (byte) de forma que el decodificadorcorrige errores de 16 bits. En el mejor caso, 16 errores de byte completos ocurren de tal forma que el decodificador corrige 16x8 errores de bit.
Los códigos Reed-Solomon son particularmente útiles para corregir burst error (cuando una serie de bits en el código de palabra se reciben con error).
DecodificaciónLos procedimientos algebraicos de decodificación de Reed-Solomon pueden corregir errores y...