Reed Solomon

40 %
60 %
Information about Reed Solomon

Published on May 10, 2008

Author: bonnzai

Source: slideshare.net

Reed-Solomon “ Detección y Corrección de Errores en CD ” Esperanza Romero Andrés Marroquín

Detección y Corrección de Errores en CD Un frame es la unidad básica de almacenamiento de datos en un CD y se compone de: - Combinación de Sincronismo : 27 Bits. - Código de Sub-canal: 17 Bits. - Datos de usuario: 408 Bits. - Detección y corrección de errores: 36 Bits. Total: 588 bits

Un frame es la unidad básica de almacenamiento de datos en un CD y se compone de:

- Combinación de Sincronismo : 27 Bits.

- Código de Sub-canal: 17 Bits.

- Datos de usuario: 408 Bits.

- Detección y corrección de errores: 36 Bits.

Total: 588 bits

Detección y Corrección de Errores en CD Al leer los datos del CD, lo primero que hace el dispositivo es quitar los 27 bits de sincronismo. Los restantes 561 bits de canal son convertidos mediante la modulación de ocho a catorce inversa (Eight to Fourteen Modulation, EFM) en 33 bytes. Uno de estos bytes, el del subcanal, es enviado a un decodificador especial y 8 bytes se usan para la Detección Y Corrección De Errores. Todos los reproductores de CD y las unidades CD-ROM disponen de un hardware especial de detección y corrección de errores para estos 8 bytes. Si no hay errores, o tras corregirlos, se eliminan estos 8 bytes. Quedan, por tanto, 24 bytes de datos de usuario en un frame.

Al leer los datos del CD, lo primero que hace el dispositivo es quitar los 27 bits de sincronismo. Los restantes 561 bits de canal son convertidos mediante la modulación de ocho a catorce inversa (Eight to Fourteen Modulation, EFM) en 33 bytes. Uno de estos bytes, el del subcanal, es enviado a un decodificador especial y 8 bytes se usan para la Detección Y Corrección De Errores.

Todos los reproductores de CD y las unidades CD-ROM disponen de un hardware especial de detección y corrección de errores para estos 8 bytes. Si no hay errores, o tras corregirlos, se eliminan estos 8 bytes. Quedan, por tanto, 24 bytes de datos de usuario en un frame.

Detección y Corrección de Errores en CD Todos los métodos de corrección de errores están basados en información redundante en combinación con algoritmos matemáticos para detectar el error y reconstruir los datos originales. Estos métodos se llaman EDC (error detection code), ECC (error correction code) y EDAC (error detection and correction code). El código de corrección de errores de un CD se basa en el conocido código de corrección llamado Reed Solomon Code. Los reproductores de CD de audio y las unidades CD-ROM usan un método internacional de corrección denominado Cross Interleaved Reed Solomon Code (CIRC). El decodificador esta integrado en el hardware.

Todos los métodos de corrección de errores están basados en información redundante en combinación con algoritmos matemáticos para detectar el error y reconstruir los datos originales. Estos métodos se llaman EDC (error detection code), ECC (error correction code) y EDAC (error detection and correction code).

El código de corrección de errores de un CD se basa en el conocido código de corrección llamado Reed Solomon Code. Los reproductores de CD de audio y las unidades CD-ROM usan un método internacional de corrección denominado Cross Interleaved Reed Solomon Code (CIRC). El decodificador esta integrado en el hardware.

Reed-Solomon El código fue inventado por Irving S. Reed y Gustave Solomon (de ahí su nombre) en el año 1960. Este código encuentra actualmente aplicación en áreas como los CDs, 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), así como en los sistemas xDSL de comunicación por cable.

El código fue inventado por Irving S. Reed y Gustave Solomon (de ahí su nombre) en el año 1960. Este código encuentra actualmente aplicación en áreas como los CDs, 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), así como en los sistemas xDSL de comunicación por cable.

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.

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.

Códigos de Bloque El principio que se utiliza en los códigos de bloque consiste en estructurar los datos en bloques de longitud fija y añadir a cada bloque un cierto número de bits llamados bits de redundancia. Sólo ciertas combinaciones de bits son aceptables y forman una colección de palabras de código válidas. Cuando los datos se transmiten y llegan al receptor hay dos posibilidades: 1. Que la palabra que se recibe sea una palabra de código válido. 2. Que la palabra que se recibe no sea un código válido, en cuyo caso hay dos posibilidades: * El receptor puede recrear el bloque original (código autocorrector). * El receptor puede pedir que se retransmita el bloque (código de autochequeo).

El principio que se utiliza en los códigos de bloque consiste en estructurar los datos en bloques de longitud fija y añadir a cada bloque un cierto número de bits llamados bits de redundancia.

Sólo ciertas combinaciones de bits son aceptables y forman una colección de palabras de código válidas.

Cuando los datos se transmiten y llegan al receptor hay dos posibilidades:

1. Que la palabra que se recibe sea una palabra de código válido.

2. Que la palabra que se recibe no sea un código válido, en cuyo caso hay dos posibilidades:

* El receptor puede recrear el bloque original (código autocorrector).

* El receptor puede pedir que se retransmita el bloque (código de autochequeo).

Reed-Solomon Los códigos Reed-Solomon se basan en un área especialista de la Matemática llamada campos Galois o campos finitos. Un campo finito tiene la propiedad de que las operaciones aritméticas (+,-,x,/,etc.) en elementos del campo siempre tienen un resultado en el campo. Un codificador o decodificador Reed-Solomon debe ser capaz de realizar estas operaciones aritméticas.

Los códigos Reed-Solomon se basan en un área especialista de la Matemática llamada campos Galois o campos finitos. Un campo finito tiene la propiedad de que las operaciones aritméticas (+,-,x,/,etc.) en elementos del campo siempre tienen un resultado en el campo. Un codificador o decodificador Reed-Solomon debe ser capaz de realizar estas operaciones aritméticas.

Como Funciona Reed-Solomon El codificador Reed-Solomon toma un bloque de información digital y añade bits redundantes. Los errores pueden ocurrir 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.

El codificador Reed-Solomon toma un bloque de información digital y añade bits redundantes. Los errores pueden ocurrir 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 De Los Códigos Reed-Solomon El total de Bytes de paridad es igual al Mensaje Total menos Mensaje Inicial n-k

Ejemplo Un código popular Reed-Solomon es RS(255,223) con símbolos de 8 bits. Cada palabra de código contiene 255 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

Un código popular Reed-Solomon es RS(255,223) con símbolos de 8 bits. Cada palabra de código contiene 255 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

Decodificación Reed-Solomon Los procedimientos algebraicos de decodificación de Reed-Solomon pueden corregir errores y datos perdidos. Un &quot;borrado&quot; ocurre cuando la posición de un símbolo errado es conocido. Un decodificador puede corregir hasta t errores o hasta 2t &quot;borrados&quot;. Información sobre los &quot;borrados&quot; puede ser frecuentemente otorgada por el demodulador en un sistema de comunicación digital, es decir, el demodulador &quot;marca&quot; los símbolos recibidos que con probabilidad contienen errores. Cuando una palabra de código es decodificada, existen tres posibilidades 1. Si 2s + r < 2t (s errores, r &quot;borrados&quot;) entonces la palabra de código original transmitida puede ser siempre recuperada. 2. El decodificador detectará que no puede recuperar la palabra de código original e indicará este hecho. 3. El decodificador decodificará erróneamente y recuperará una palabra de código incorrecta sin indicación.

Los procedimientos algebraicos de decodificación de Reed-Solomon pueden corregir errores y datos perdidos. Un &quot;borrado&quot; ocurre cuando la posición de un símbolo errado es conocido. Un decodificador puede corregir hasta t errores o hasta 2t &quot;borrados&quot;. Información sobre los &quot;borrados&quot; puede ser frecuentemente otorgada por el demodulador en un sistema de comunicación digital, es decir, el demodulador &quot;marca&quot; los símbolos recibidos que con probabilidad contienen errores.

Cuando una palabra de código es decodificada, existen tres posibilidades

1. Si 2s + r < 2t (s errores, r &quot;borrados&quot;) entonces la palabra de código original transmitida puede ser siempre recuperada.

2. El decodificador detectará que no puede recuperar la palabra de código original e indicará este hecho.

3. El decodificador decodificará erróneamente y recuperará una palabra de código incorrecta sin indicación.

Implementación Hardware Existe una cantidad implementaciones hardware. Muchos de estos sistemas utilizan circuitos integrados comerciales que codifican y decodifican códigos Reed-Solomon. Estos circuitos integrados soportan un cierto grado de programación (p. Ej. RS(255,k) donde t=1 a 16 símbolos). Una tendencia reciente es hacia VHDL o diseños Verilog. Estos tienen una cantidad importante de ventajas sobre los circuitos integrados estándar. Estos diseños pueden ser integrados con otros VHDL o diseños Verilog y ser sintetizados en un FPGA (Field Programmable Gate Array) o ASIC (Application Specific Integrated Circuit). lo que permite diseños &quot;Sistemas sobre Chip&quot; donde múltiples módulos pueden ser combinados en un solo circuito integrado. Dependiendo en los volúmenes de producción los diseños anteriores pueden llevar a reducir costos en comparación con los circuitos integrados usuales. Con lo anterior se evita que un usuario deba comprar &quot;de por vida&quot; un mismo circuito integrado.

Existe una cantidad implementaciones hardware. Muchos de estos sistemas utilizan circuitos integrados comerciales que codifican y decodifican códigos Reed-Solomon. Estos circuitos integrados soportan un cierto grado de programación (p. Ej. RS(255,k) donde t=1 a 16 símbolos). Una tendencia reciente es hacia VHDL o diseños Verilog. Estos tienen una cantidad importante de ventajas sobre los circuitos integrados estándar. Estos diseños pueden ser integrados con otros VHDL o diseños Verilog y ser sintetizados en un FPGA (Field Programmable Gate Array) o ASIC (Application Specific Integrated Circuit). lo que permite diseños &quot;Sistemas sobre Chip&quot; donde múltiples módulos pueden ser combinados en un solo circuito integrado. Dependiendo en los volúmenes de producción los diseños anteriores pueden llevar a reducir costos en comparación con los circuitos integrados usuales. Con lo anterior se evita que un usuario deba comprar &quot;de por vida&quot; un mismo circuito integrado.

Implementación Software Hasta hace poco implementación en software para aplicaciones en tiempo real requería demasiado poder computacional para todos excepto los más simples códigos Reed-Solomon (es decir, códigos con pequeños valores de t). El mayor problema de implementar los códigos Reed-Solomon en software es que procesadores de propósito general no soportan aritmética de campo de Galois. Por ejemplo, para implementar un campo de Galois que multiplique en software requiere un test de cero, dos revisiones en tablas logarítmicas, sumatoria en módulo, y búsqueda en tabla de antilogaritmo. Sin embargo con el aumento en el rendimiento de los procesadores y un diseño cuidadoso significa que implementación en software pueden trabajar con tasas de bits relativamente altas.

Hasta hace poco implementación en software para aplicaciones en tiempo real requería demasiado poder computacional para todos excepto los más simples códigos Reed-Solomon (es decir, códigos con pequeños valores de t). El mayor problema de implementar los códigos Reed-Solomon en software es que procesadores de propósito general no soportan aritmética de campo de Galois. Por ejemplo, para implementar un campo de Galois que multiplique en software requiere un test de cero, dos revisiones en tablas logarítmicas, sumatoria en módulo, y búsqueda en tabla de antilogaritmo. Sin embargo con el aumento en el rendimiento de los procesadores y un diseño cuidadoso significa que implementación en software pueden trabajar con tasas de bits relativamente altas.

Add a comment

Related presentations

Related pages

Reed-Solomon-Code – Wikipedia

Reed-Solomon-Codes (kurz RS-Codes) sind eine Klasse von zyklischen Blockcodes und werden im Rahmen der Kanalkodierung zum Erkennen und Korrigieren von ...
Read more

Reed-Solomon Codes - CMU Computer Science

Reed-Solomon Codes. An introduction to Reed-Solomon codes: principles, architecture and implementation. 1. Introduction. Reed-Solomon codes are block-based ...
Read more

Reed–Solomon codes for coders - Wikiversity

The function qr_decode_format returns -1 if the format code could not be unambiguously decoded. This happens when two or more format codes have the same ...
Read more

Codice Reed-Solomon - Wikipedia

Nella teoria dei codici, il codice Reed-Solomon è un tipo di codice lineare (ciclico) non binario di rilevazione e correzione d'errore, inventato da ...
Read more

Reed Solomon Identifikation – Wikipedia

Reed Solomon Identifikation (RSID) ist ein digitales Kommunikationsprotokoll für Funkamateure, das es ermöglicht, viele digitale Betriebsarten ...
Read more

Reed-Solomon-Code :: reed solomon code :: RS - itwissen.info

Der Reed-Solomon-Code (RS) ist ein Fehlerkorrekturverfahren, das in der Mobilkommunikation bei Cellular Digital Packet Data (CDPD), in der ...
Read more

R&D White Paper - BBC

White Paper WHP 031 Reed-Solomon Error Correction C. K. P. Clarke Abstract Reed-Solomon error correction has several applications in broadcasting, in ...
Read more

Suchergebnis auf Amazon.de für: Reed-Solomon Code ...

Online-Einkauf von Fremdsprachige Bücher aus großartigem Angebot von Wirtschaftswissenschaften, Industriezweige & Berufe, Management & Führung und mehr ...
Read more

Error Correction with Reed-Solomon | Dr Dobb's

Reed-Solomon might well be the most ubiquitously implemented algorithm: Barcodes use it; every CD, DVD, RAID6, and digital tape device uses it; so do ...
Read more

Reed-Solomon-Calculator for QR-Code - Download - heise.de

Download: Reed-Solomon-Calculator for QR-Code, kostenlos. Über Reed-Solomon-Calculator for QR-Code: Online-Generator für Fehlerkorrektur-Werte nach dem ...
Read more