Introducción

Los códigos Reed-Solomon son códigos de corrección de errores basados ​​en bloques con una amplia gama de aplicaciones en comunicaciones digitales y almacenamiento. Los códigos de Reed-Solomon se utilizan para corregir errores en muchos sistemas, incluidos:

• Dispositivos de almacenamiento (incluyendo cinta, disco compacto, DVD, códigos de barras, etc.)
• Comunicaciones inalámbricas o móviles (incluidos teléfonos celulares, enlaces de microondas, etc.)
• Comunicaciones satelitales
• Televisión digital / DVB
• Módems de alta velocidad como ADSL, xDSL, etc.

Un sistema típico se muestra aquí:

El codificador Reed-Solomon toma un bloque de datos digitales y agrega bits «redundantes» adicionales. Los errores se producen durante la transmisión o el almacenamiento por varios motivos (por ejemplo, ruido o interferencia, rayaduras en un CD, etc.). El decodificador Reed-Solomon procesa cada bloque e intenta corregir errores y recuperar los datos originales. La cantidad y el tipo de errores que se pueden corregir dependen de las características del código Reed-Solomon.Lo

Entre otras técnicas, tecnologías como WiFi o WiMAX hacen uso de códigos de corrección de errores RS para combatir el desvanecimiento. Estos también están muy presentes en multitud de aplicaciones cotidianas de telefonia, comunicaciones por cable (xDSL) y de video (DVB) o audio (DAB) digitales, como por ejemplo las emisiones vía satélite de radio-televisión o la implantada Televisión Digital Terrestre.

Por otro lado, la gran flexibilidad que ofrecen las FPGAs hace factible la implementación de codificadores RS en ellas. Además, la posibilidad de realizar diseños divididos en módulos o bloques funcionales permite llevar a cabo las optimizaciones oportunas, incluso servir como base de un gran número de sistemas básicos de comunicación digital que utilicen este tipo de codificación.

Por otro lado, la gran flexibilidad que ofrecen las FPGAs hace factible la implementación de codificadores RS en ellas. Además, la posibilidad de realizar diseños divididos en módulos o bloques funcionales permite llevar a cabo las optimizaciones oportunas, incluso servir como base de un gran número de sistemas básicos de comunicación digital que utilicen este tipo de codificación.

Propiedades de los códigos Reed-Solomon.

Los códigos Reed Solomon son un subconjunto de códigos BCH y son códigos de bloque lineales. Un código Reed-Solomon se especifica como RS ( n, k ) con símbolos de s -bit.

Esto significa que el codificador toma k símbolos de datos de s bits cada uno y agrega símbolos de paridad para hacer una n palabra de código de símbolo. Hay n-k símbolos de paridad de s bits cada uno. Un decodificador Reed-Solomon puede corregir hasta t símbolos que contienen errores en una palabra de código, donde 2t = n-k .

El siguiente diagrama muestra una palabra de código típica de Reed-Solomon (esto se conoce como un código sistemático porque los datos no se modifican y se añaden los símbolos de paridad):

Ejemplo: un código Reed-Solomon popular 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:

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, los errores de hasta 16 bytes en cualquier parte de la palabra de código se pueden corregir automáticamente.

CAMPOS DE GALOIS APLICADOS A LA CODIFICACIÓN REED-SOLOMON

Los códigos Reed-Solomon se basan en un área especializada de la matemática llamada campos de Galois o campos finitos. Un campo finito tiene la propiedad de que las operaciones aritméticas sobre 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.

GENERADOR POLINOMIAL

Una palabra de código Reed-Solomon es generada usando un polinomio especial. Todas las palabras de código válidas son divisibles exactamente por el polinomio generador representado por la Ecuación :

g(x) = (x − α)(x − α^2)· · ·(x − α^(n−k))

La palabra de código se genera de c(x)=g(x)*i(x), donde g(x) es el polinomio generador, i(x) es el bloque de información, c(x) es una palabra de código válida y á se conoce como un elemento primitivo del campo.

El primer paso corresponde a la definición del campo de Galois para la codificación, el cual estará definido en función de la longitud del símbolo entiéndase m bits/símbolo, el cual permite conocer el polinomio reducible del campo de Galois GF(2^m).

BLOQUES FUNCIONALES DEL DECODIFICADOR

Para el estudio del decodificador se considera el diagrama de bloques presentado en la Figura:

CÁLCULO DEL SÍNDROME

Se trata de un cálculo similar al cálculo de paridad. Un código de palabra Reed-Solomon tiene 2t síndromes que dependen solamente de los errores –no de la palabra transmitida–. Los síndromes pueden ser calculados al sustituir las 2t raíces del polinomio generador g(x) en r(x).

LOCALIZADOR DE ERRORES

Encontrar el lugar del símbolo erróneo implica resolver de forma simultánea ecuaciones con t incógnitas. Existen varios algoritmos rápidos para hacerlo, los cuales toman ventaja de la estructura matricial especial de los códigos Reed-Solomon y reducen de gran forma el esfuerzo computacional requerido.

POLINOMIO LOCALIZADOR DE ERROR

Este polinomio localizador de error se puede lograr utilizando el algoritmo Berlekamp-Massey o el algoritmo de Euclides. Para localizar los símbolos erróneos se debe seguir un procedimiento que implica resolver unos sistemas de ecuaciones, el primero de los cuales se representa mediante la fórmula general de la Ecuación:

CORRECCIÓN DE ERRORES

Este paso también implica resolver ecuaciones con t incógnitas para poder encontrar los valores verdaderos que deberán ser sustituidos en las posiciones correspondientes, para así poder reproducir el mensaje correcto que se intentó enviar. Esto se hace con el algoritmo de búsqueda de Chien. Donde 1<= j <= t los fi son las incógnitas y Si los componentes del síndrome calculado. La posición en la que están los errores se obtiene de los exponentes de las raíces de un polinomio f(x):

GENERADOR DEL ERROR

A continuación se debe resolver un sistema de ecuaciones con tantas incógnitas como errores hayan sido detectados de acuerdo con la Ecuación:

Finalmente se realizará la adición del módulo-2 (xor) entre el dato de entrada que fue recibido por el decodificador –que se mantiene registrado en una memoria RAM– y el error generado con lo que se obtiene el código recuperado.

DISEÑO DEL CODIFICADOR RS (7,3)

Para comprender en forma práctica el cálculo del código se asume un campo GF(8), es decir, m=3 bits/símbolo. La representación de los elementos del campo estará comprendida por el polinomio irreducible p(x)= x^3+x+1, el cual tiene raíz á, por lo que al igualar a cero el polinomio se obtiene á^3+á+1=0, tal que á^3= á +1 será la representación para sustituir el elemento que se desborda del campo, con lo que se
puede convertir a un elemento perteneciente al campo.
A partir de la expresión de G(x), para un codificador RS(7,3) se obtuvo el polinomio generador de la forma:

G(x) = á^(2)x^(3)+ á^(5)x^(2)+ á^(5)x+ á^6

el cual es sustituido en función de los valores de los elementos del campo de Galois:
G(x) = 4x^3+ 7x^2+ 7x+ 5

El campo de Galois permite obtener la palabra codificada compuesta por tres símbolos de datos y cuatro símbolos de paridad.

Al aplicar los datos de entrada D=[1,3,7,0,0,0,0] se obtiene a la salida C=[1,3,7,0,1,1,5]. Se definieron igualmente los multiplicadores para el campo de Galois, los cuales son componentes que obtienen a su salida el resultado del producto en el campo en función de la entrada, donde el módulo en VHDL para la multiplicación del coeficiente 4 por los símbolos de entrada se muestra en la Tabla.

El manejo de los registros y la XOR entre los elementos procesados se muestra en la Tabla

El cálculo del campo de Galois se realizó también usando la herramienta Matlab; el comando para obtener el arreglo de Galois (gf) se aplicó a la matriz de datos a enviar y al número de bits por símbolo, en este caso tres bits por símbolo, es decir, msn = gf([matriz de datos],m), en tanto que la palabra de código se obtiene al aplicar el comando de codificación (rsenc) al arreglo de Galois (msn) y a la longitud de la palabra de código, con la longitud del mensaje. El código en Matlab se muestra en la Tabla:

DISEÑO DEL DECODIFICADOR RS (7,3)

Se definen las señales de entrada y salida que están disponibles desde los pines del FPGA, lo que produce por parte del software Xilinx ISE 6.1 la entidad mostrada en la Figura:

Con base en el diagrama de bloques se definieron los componentes representados por cada bloque funcional para los cuales se describe la estructura y sus funciones específicas. La descripción de la estructura bajo la sintaxis VHDL se muestra en la Tabla:

Cada uno de los módulos internos se describe como componentes. El diagrama RTL a nivel de registros de transferencia para la implementación se muestra en la Figura:

Avances en las implementaciones de los códigos RS sobre FPG As

Una de las posibles implementaciones de los bloques codificador y decodificador RS en hardware 73, la cual puede extenderse para cualquier código RS.
Con el fin de desarrollar el sistema de detección y corrección de errores FEC del estándar 802.16, se ha implementado un modelo de codificador RS(255, 239) bajo la sintaxis VHDL y basada en una implementación que utiliza el algoritmo Berlekamp Massey . Este modelo permite alcanzar unas mayores velocidades de trabajo ya que se puede extender la arquitectura de forma que se trabaje con más de un símbolo al mismo tiempo. Este aspecto tiene un gran interés en los sistemas de comunicaciones digitales que se caractericen por tener grandes tasas de transmisiones de datos, como es el caso de WiMAX.