DOI:https://doi.org/10.26910/issn.2528-8083vol3issJIEE2018.2018pp17-25p
Cristian Oñate
Escuela Politécnica Nacional, Ecuador.
tcristian697@gmail.com
Fecha de recepción: 16 de agosto de 2018 — Fecha de aceptación: 30 de octubre de 2018
Estudiante del Departamento de Electrónica, Telecomunicaciones y Redes de Información.
Resumen
En este artículo se realiza un análisis de la teoría del código Reed-Solomon, para luego describir específicamente la codificación y decodificación del código Reed-Solomon (204, 188) en VHDL. Posterior a eso, se implementó el código descrito en la tarjeta FPGA Virtex 5 XUPV5-LX110T. El diseño del codificador se lo realizó usando su arquitectura genérica, mientras que para el decodificador se usaron como base los algoritmos de Euclides Modificado, Chien y Forney. Finalmente, se verificó su correcto funcionamiento y se determinó la cantidad de recursos utilizados de la tarjeta al implementar el algoritmo estudiado.
Palabras Claves Algoritmo de Euclides Modificado, Corrección de errores, Reed Solomon.
Abstract
This article performs an analysis of the Reed-Solomon code theory, and then specifically describes the coding and decoding of the Reed-Solomon code (204, 188) in VHDL. After that, the code described in the Virtex 5 XUPV5-LX110T FPGA card was implemented. The encoder design was made using its generic architecture, while the decoder was used as the basis of the algorithms of Euclid Modified, Chien and Forney. Finally, the correct operation was verified and the amount of resources used on the card was determined when implementing the studied algorithm.
Keywords Euclid’s Modified Algorithm, Bug fixes, Reed Solomon.
INTRODUCCIÓN
En el intercambio de información a través de un canal de comunicaciones poco confiable o ruidoso, es inevitable encontrarse con errores en la recepción, esto es inadmisible si se pretende brindar una comunicación confiable y de calidad entre un emisor y un receptor, por lo que es necesario el uso de técnicas de codificación para el control de los errores (Castiñeira y Farrell, 2012).
En 1960 Irvin S. Reed y Gustave Solomon publicaron un artículo titulado “Polinomial Codes over Certain Finite Fields” presentando la creación del código que lleva sus nombres. Reed Solomon es un código usado para la detección y corrección de errores. La aplicación de este código fue complementada con la invención del algoritmo decodificador creado por Elwyn Berlekamp. Su primera aplicación significativa fue la codificación de imágenes digitales en la sonda espacial Voyager (Serrano, 2004).
En la actualidad tiene un amplio rango de aplicaciones en comunicaciones digitales y es usado para corregir errores en muchos sistemas de comunicación como: Wifi, Wimax (Lujan, Almagro, Cabrera, Suardíaz y Cerdan, n.d.), CDs y sondas espaciales (Bateman, 2003). También se destaca la aplicación del código Reed-Solomon en algunas tecnologías de comunicación digital, como: Digital Video Broadcasting (DVB), Integrated Services Digital Broadcasting Terrestrial (ISDB-T) y en Digital Audio Broadcasting (DAB) (Serrano, 2004).
MARCO TEÓRICO
Los códigos Reed Solomon se representan como RS(n,k), en donde los parámetros definidos se expresan de la siguiente manera (Serrano, 2004):
n: número de símbolos a la salida del codificador (longitud de la palabra código).
K: número de símbolos de información que van a ser codificados.
2t = n k : número de símbolos de paridad añadidos dentro de los n símbolos.
t = (nk)=2 : número máximo de errores que puede corregir el código.
Normalmente se los representa de manera sistemática, eso quiere decir que después de la codificación la palabra original se la puede distinguir claramente en la palabra codificada (Serrano, 2004) (ver Figura 1).
Codificación Reed Salomon
La codificación tiene como función principal generar la palabra código, para esto la codificación sistemática añade n-k símbolos de paridad a la palabra original que ingresa al codificador, así ingresan k símbolos de información y salen n símbolos y esta es la palabra código. Los símbolos de paridad se los calcula multiplicando la palabra original por el polinomio X y este resultado se lo divide para el polinomio generador g(x), el residuo de esta división es el conjunto de los símbolos de paridad que se añade a la palabra original (Castiñeira y Farrell, 2012).
El polinomio generador es un polinomio de grado X sobre el campo de Galois, cuyo valor dependerá del campo sobre el que se est´e trabajando. El polinomio generador g(x) de manera general se lo calcula de la siguiente manera (Castiñeira y Farrell, 2012).
Se presenta la descripción matemática de la codificación sistemática.
Decodificación Reed Salomon
El proceso de decodificación consiste en tomar la palabra enviada por el codificador y recuperar la palabra original. Si la palabra que se recibe tiene errores, el código Reed Solomon se encargará de detectar y corregir los errores que se produjeron en la transmisión, como este proceso es el inverso de la codificación ingresarán n símbolos al decodificador y se obtendrán los k símbolos correspondientes al mensaje original que se envió (Castiñeira y Farrell, 2012). El proceso de decodificación se lo describe a continuación:
Cálculo del síndrome
La manera más sencilla de calcular el síndrome es evaluar la palabra codificada c(x) en cada una de las raíces del polinomio generador g(x), se necesitan 2t síndromes para poder detectar y corregir t errores, con esto se calculará el polinomio síndrome S(x), que permitirá determinar si la palabra código recibida tienen errores o no (Castiñeira y Farrell, 2012). El cálculo del polinomio síndrome se lo puede expresar matemáticamente de la siguiente manera:
Si el polinomio síndrome es distinto de cero, esto indica que existen errores en la palabra recibida por lo que se deberá iniciar el proceso de detección y corrección de errores, detallado a continuación:
Detección y corrección de errores
Para la detección de errores es necesario calcular el polinomio localizador de errores y el polinomio magnitud de errores, para esto se pueden usar varios algoritmos como el de Berlekamp, Berlekamp-Masey, Euclides extendido o Euclides modificado, debido a las ventajas que ofrece el algoritmo de Euclides modificado respecto a la facilidad de ejecución y uso de recursos, en este proyecto se usa el algoritmo de Euclides modificado, el cual se lo ejecuta de la siguiente manera (Serrano, 2004):
Algoritmo de Euclides modificado
Este algoritmo está basado en el algoritmo de Euclides, el cual es usado para calcular el máximo común divisor de dos factores, sin embargo el algoritmo de Euclides modificado evita el cálculo de los cocientes en cada división, por lo que su ejecución es más rápida y consume menos recursos. A continuación, se describen las ecuaciones y sus condiciones iniciales para el uso del Algoritmo de Euclides modificado (Serrano, 2004):
El polinomio magnitud de errores se calcula así (Serrano, 2004):
El polinomio localizador de errores se determina de la siguien- te manera (Serrano, 2004):
El último algoritmo a ejecutar es el algoritmo de Forney, este permite calcular el valor del error localizado mediante la evaluación de la siguiente fórmula (Serrano, 2004):
Corrección de errores
Una vez ejecutados los algoritmos de Euclides modificado, Chien y Forney se ha encontrado el polinomio error e(x).
Si existe más de un error, cada uno tendrá su valor y posición correspondiente. La corrección de errores se lo hace realizando la operación XOR entre el polinomio error y la palabra recibida (Castiñeira y Farrell, 2012).
Este método de codificación es general y puede ser aplicado para códigos Reed Solomon de cualquier magnitud.
Descripción en VHDL
Para la descripción del código Reed Solomon (204,188) se usará el lenguaje VHDL, que es un acrónimo de VHSIC Hardaware Description Languaje, en donde VHSIC es otro acrónimo de Very High Speed Integrated Circuit (Chu, 2006). Este lenguaje es ampliamente usado en la industria y permite realizar una descripción de circuitos síncronos y asíncronos (Sanchez, n.d.).
La descripción en VHDL inicia con el diseño de un UART (Universal Asynchronous Receiver-Transmitter), el cual usará el estándar RS-232 para la comunicación entre el computador y la FPGA (Chu, 2006).
Para la descripción del codificador Reed Solomon se usará una arquitectura genérica que puede ser usada en cualquier codificador Reed Solomon sin importar los valores de n y k (Sandoval y Fedon, 2008). Esta arquitectura se muestra en la Figura 2.
A continuación, se definen los elementos más importantes en la arquitectura genérica y su funcionamiento.
El circuito inicia su proceso con el ingreso del primer símbolo de la palabra original, el cual se sumará con el valor almacenado en el registro n k 1 que será el valor 0, ya que es el valor inicial en cada registro, este resultado es multiplicado por cada coeficiente del polinomio generador g(x); G 0 ; G 1 ;...,G . El resultado entre el primer elemento y el coeficiente G nk1 es almacenado en su correspondiente registro de memoria, mientras que los demás resultados de cada multiplicación en cambio son sumados con el dato almacenado previamente en cada registro, que como se sabe tiene el valor inicial 0, realizada la suma el resultado se almacenará en su registro correspondiente. 0
Luego ingresará el segundo símbolo y se ejecutará el mismo proceso, el proceso se repetirá hasta que todos los símbolos de la palabra original hayan ingresado, una vez que se han procesado todos los símbolos, los últimos valores almacenados en cada registro se agregarán a la palabra original para obtener la palabra completa codificada. Una vez descrito el funcionamiento de cada señal, en la Figura 3 se muestra la arquitectura del codificador Reed Solomon (204,188) con UART.
El diseño del decodificador presenta una alta complejidad, por lo que se ha dividido su descripción en 3 bloques, el primero encargado de calcular el polinomio síndrome, el segundo ejecutará el algoritmo de Euclides modificado para hallar los polinomios localizador y magnitud de error, y el último bloque, será el encargado de hallar la magnitud y posición de los errores y realizar la corrección de los mismos, esta arquitectura se la muestra en la Figura 4. Para el cálculo
El bloque del algoritmo de Euclides modificado está implementado mediante la máquina de estados que se muestra en la Figura 6. En la máquina de estados se ejecutan las iteraciones necesarias para hallar los polinomios localizador y magnitud de errores.
Como se explicó anteriormente el algoritmo de Chien detecta la posición del error y esto se logra evaluando el polinomio localizador en un , por lo que su arquitectura se ajusta a lo mostrado en la Figura 7 y será muy similar a la usada para el cálculo del polinomio síndrome. Esta arquitectura se repetirá 3 veces en la descripción para evaluar el polinomio localizador de errores, su derivada y el polinomio magnitud de errores. Una vez evaluados los 3 polinomios, se toma el valor calculado.
en VHDL del decodificador, se instancia con su respectivo transmisor y receptor serial para obtener el decodificador Reed Solomon (204,188) con UART mostrado en la siguiente Figura 9.
Una descripción detallada de la implementación de los algoritmos de codificación y decodificación que se desarrollaron, se puede encontrar en la referencia [8] que pertenece a los mismos autores del presente artículo.
RESULTADOS Y DISCUSIÓN
En esta sección se muestran los resultados obtenidos luego de la implementación en la FPGA del código descrito en VHDL, tanto para el codificador como para el decodificador Reed Solomon (204, 188).
Evaluación y pruebas de la implementación del codificador Reed Solomon (204, 188) con UART
En la siguiente la Tabla 1 se muestran los recursos utilizados para la implementación del codificador Reed Solomon (204,188) en la tarjeta FPGA empleada.
A continuación, se muestran los resultados obtenidos en la interfaz gráfica tras ejecutar las pruebas prácticas del codificador Reed Solomon (204,188) en la FPGA, en este ejemplo se enviaron 188 símbolos con valor 01 , y se obtiene el dato codificado mostrado en la Figura 10. En las Figuras 11 y 12 se puede ver el dato codificado obtenido en Matlab e ISE respectivamente luego de ingresar 188 símbolos con valor 01 H .
Se observa que los símbolos de paridad que se añaden a
la palabra original luego de la codificación hecha en la FPGA coinciden con los datos obtenidos en Matlab e ISE, con esto se puede concluir que el código descrito en VHDL cumple con los parámetros de diseño establecidos y se ejecuta de manera correcta la codificación Reed Solomon (204, 188).
Evaluación y pruebas de la implementación del decodificador Reed Solomon (204, 188) con UART
Se presenta el cuadro resumido del porcentaje de utilización de la FPGA para el caso del decodificador.
La correcta ejecución del decodificador se comprueba comparando la palabra decodificada enviada por la FPGA con la palabra codificada sin errores, retirando los 16 símbolos de paridad. Si las dos coinciden, se habrá comprobado el correcto funcionamiento del decodificador.
Adicional se verificarán los valores del síndrome, el polinomio localizador y magnitud de errores enviados desde la FPGA con los valores obtenidos en la simulación de ISE.
Pruebas con la palabra código sin errores
Para esta prueba se usa la palabra codificada que se mostró en la Figura 11, la cual será enviada a la FPGA sin insertarle errores, como se muestra en la Figura 13. Como la palabra código enviada a la FPGA no tiene errores, es obvio que el polinomio síndrome y los errores localizados sean cero, lo cual se obtuvo en la decodificación de acuerdo a las Figuras 13 y 14.
Pruebas con 1 error
Nuevamente se usa la palabra codificada de la Figura 11, pero esta vez se inserta un error en la posición cero, cambiando el valor 50 por el 35 en hexadecimal, como se muestra en la Figura 15.
La detección y corrección de errores se resume en la tabla 1, el error se localiza efectivamente en la posición cero, pero su valor es 65, esto es porque se realiza la operación XOR entre65 y 35, para recuperar el valor original 50, esta operación se muestra en la tabla 3 y se la puede también verificar observando las Figuras 16 y 17.
Pruebas con 8 errores
Ahora se ingresan 8 errores para comprobar la capacidad máxima de corrección del código Reed Solomon (204,188). Los procesos de detección y corrección de errores se muestran en las siguientes figuras, mientras que en la tabla 4 se presentan las operaciones realizadas y se puede observar que fue posible la recuperación del dato original.
Pruebas con 9 errores
Se presenta la siguiente prueba para observar el comportamiento del decodificador ante la presencia de una cantidad de errores mayor a la capacidad de detección y corrección del codificador Reed Solomon (204,188). En la Figura 22, se muestran los 9 errores ingresados en la palabra codificada. La interfaz gráfica se diseñó para el ingreso máximo de 8
errores, ya que es la capacidad teórica máxima de detección y corrección del código Reed Solomon (204,188). Por esto, el noveno error se lo ingresa directamente en el código de la interfaz, en la posición 203 con el valor 12 en decimal (0C ). Luego de ejecutar las pruebas con 9 errores se observa que el decodificador no recupera el dato original, ya que el decodificador no logra localizar ningún error (Figura 22 y 23), y por esto, el dato decodificado contiene los mismos errores.
Se observa que todas las pruebas realizadas son exitosas, el código diseñado corrige un máximo de 8 símbolos erróneos
y recupera la palabra original enviada, con esto se puede concluir que el código descrito en VHDL cumple con los parámetros de diseño establecidos y ejecuta de manera correcta la decodificación Reed Solomon (204, 188).
CONCLUSIONES
El codificador y decodificador implementados en este proyecto utilizan una cantidad reducida de recursos en comparación a los disponibles en una tarjeta FPGA Virtex 5 XUPV5-LX110T. En el caso del codificador, el recurso más utilizado son los FFs, alcanzando un porcentaje de utilizaci´on del 15 %; en cambio, en el decodificador el recurso más utilizado son los LUTs con un 22 %.
Con la aplicación del algoritmo de Euclides modificado se reduce la complejidad del decodificador, gracias a la ejecución de operaciones matemáticas más sencillas en los procesos de cálculo del polinomio localizador y polinomio magnitud de errores en comparación a otros algoritmos. Esto además, facilita su programación en VHDL.
El codificador y decodificador Reed Solomon (204,188) presentados en este trabajo, podrán ser usados en futuros proyectos de mayor complejidad que requieran la detección y corrección de errores.
REFERENCIAS
[1] A. Bateman, Comunicaciones Digitales, Diseño para el Mundo Real, España: Marcombo, 2003.
[2] P. Chu, RTL hardware design using VHDL, Hoboken, N.J.: WileyInterscience, 2006.
[3] S. Lujan, S. Almagro, A. Cabrera, J. Suardíaz, F. Cerdan, Códigos RS y su aplicación a la capa física de 802.16 en FPGAs, Colombia: Universidad Politécnica de Cartagena. [En línea]. Disponible en: http://repositorio.upct.es/bitstream/handle/10317/2041/crs.pdf;jsessionid =E2390EE86A7EABE6999707C8EDACF9F0?sequence=1.
[4] J. Castiñeira y P. Farrell, Codificación para el control de errores, Mar del Plata, Argentina: Eudem, 2012.
[5] C. Sandoval, A. Fedon, Descripción modular de un esquema de codificación concatenado para corrección de errores con programación de hardwareIngeniare. Revista chilena de ingeniería, 16(3), pp. 310-317, 2008.
[6] M. Serrano, Análisis de un codificador-decodificador ReedSolomon.Universidad de Sevilla, 2004 [En línea]. Disponible en: http://encore.fama.us.es/iii/encore/search/C SPT. %200912;jsessionid= D7F57127392E53B8338EF44A11E6BEE1?lang=spi
[7] M. Sánchez, Introducción a la programación en VHDLUniversidad Complutense de Madrid. Obtenido de: http://eprints.ucm.es/26200/1/intro VHDL.pdf,Julio, 2014.
[8] C. Oñate Castillo, P. Lupera-Morillo, Implementación de un codificador y decodificador Reed Solomon (204,188) en una tarjeta FPGA con el algoritmo de Euclides modificado,trabajo de titulación de ingeniería, Escuela Politécnica Nacional, 2017 [En línea]. Disponible en: http://bibdigital.epn.edu.ec/handle/15000/18825.