jueves, 9 de mayo de 2013

PUNTOS EXTRA: REED-SOLOMON CODES

Los códigos Reed-Solomon son códigos cíclicos no binarios. Los códigos cíclicos son una subclase de los códigos de bloque estándar de detección y corrección de errores. Este tipo de códigos tiene un amplio rango de aplicaciones en comuniaciones digitales y almacenaje y se usan para corregir errores en muchos sistemas como:
  • Dispositivos de almacenamiento (CD, DVD, Códigos de Barras,etc.)
  • Comunicaciones inamámbricas o móviles
  • Comunicaciones satelitales
  • Televisión Digital
  • Modems de alta velocidad tales como ADSL, xDSL, etc.
La siguiente figura representa un caso típico:


 El funcionamiento es el siguiente:
- El codificador Reed Solomon toma un bloque de información digital y añade bits extras "redundantes".
- Los errores ocurren durante la transmisión o el almacenamiento por varias razones (por ejemplo ruido o interferencia, o rayaduras en un CD).
- El decodificador Reed-Solomon procesa cada bloque y trata de corregir los errores y recuperar la información original.

Propiedades de los Códigos Reed-Solomon
Los códigos Reed-Solomon son bloques de códigos lineales. Un código Reed-Solomon es representado como RS(n,k) con símbolos s-bits.

Lo anterior significa que el codificador toma k símbolos de información de s bits cada uno y añade símbolos de paridad para hacer una palabra clave de símbolo n. Hay n-k símbolos de paridad  de s bits cada uno. Un decodificador Reed-Solomon puede corregir hasta t símbolos que contengan errores en una palabra clave, donde 2t = n-k.

La siguiente es úna palabra clave común de Reed-Solomon:


Ejemplo:
Un código popular de Reed-Solomon es el RS(255,223) con símbolos de 8-bit. Cada palabra clave contiene 255 bytes de palabra clave, de los cuales 223 bytes son información y 32 bytes son paridad. Para este código:

n=255, k = 223, s=8
2t = 32, t=16

El codificador puede corregir cualesquiera 16 errores en la palabra clave.

Aplicaciones
La codificación Reed-Solomon es ampliamente usada en sistems almacenamiento en masa para corregir los errores de ráfaga de asociados con efectos de media.

También es un componente clave de los discos compactos. Este fue el primer uso de correción de error fuerte en un producto consumidor producido en masa. El DVD usa un esquema similar al usado por el CD.

El corrector de errores Reed-Solomon también es usado en archivos "parchive" (parity archive volumen set), los cuales comúnmente son son publicados acompañando archivos multimedia de USENET. El servicio de almacenamiento distribuido en línea llamado Wuala también usa el Reed-Solomon al partir los archivos.

 Código de Barras
Casi todos los códigos de barras bidimensionales usan la corrección de errores Reed-Solomon. Cuando el scanner de código de barras no puede reconocer el símbolo, lo tratará como una raspadura.



Referencias
http://es.wikipedia.org/wiki/Reed-Solomon
http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/reedsolomon/reed_solomon_codes.html

1 comentario:

  1. A las referencias les falta todo el formato :/ 2 pts.

    ResponderEliminar