Códigos detectores y correctores de errorLos códigos detectores y correctores de error se refieren a los errores de transmisión en las líneas. Se deben a diversos factores, como el ruido térmico, ruido impulsivo y ruido de intermodulación. Dependiendo del medio de transmisión y del tipo de codificación empleado, se pueden presentar otros tipos de anomalías como ruido de redondeo y atenuación, así como cruce de líneas y eco durante la transmisión. EstrategiasSe han diseñado dos estrategias diferentes para el tratamiento de los errores
Corrección de erroresLa corrección de errores se puede tratar de dos formas:
Hoy, el código de Hamming se refiere al (7.4). El código de Hamming agrega tres bits adicionales de comprobación por cada cuatro bits de datos del mensaje. El algoritmo de Hamming (7.4) puede corregir cualquier error de un solo bit, pero cuando hay errores en más de un bit, la palabra transmitida se confunde con otra con error en un solo bit, siendo corregida, pero de forma incorrecta, es decir que la palabra que se corrige es otra distinta a la original, y el mensaje final será incorrecto sin saberlo. Códigos de corrección de errores Reed-SolomonPropiedades de los códigos Reed-SolomonUn 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 decodificador puede 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 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:
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áxima longitud de la palabra de código (n) para un código Reed-Solomon es n=. 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 anteriormente puede 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 significa que 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 decodificador corrige 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 datos perdidos. Un "borrado" ocurre cuando la posición de un símbolo errado es conocido. Un decodificador puede corregir hasta t errores o hasta 2t "borrados". Información sobre los "borrados" puede ser frecuentemente otorgada por el demodulador en un sistema de comunicación digital, es decir, el demodulador "marca" los símbolos recibidos que con probabilidad contienen errores. Cuando una palabra de código es decodificada, existen tres posibilidades:
La probabilidad de ocurrencia de cada una de las tres posibilidades anteriores depende del código Reed-Solomon en particular y en el número y la distribución de errores. Ganancia de CodificaciónLa ventaja de utilizar códigos Reed-Solomon es que la probabilidad de que quede un error en los datos decodificados es, usualmente, mucho menor que la probabilidad de ocurrencia de un error si Reed-Solomon no es utilizado. Esto se conoce usualmente como ganancia de codificación. Ejemplo: Un sistema digital de comunicaciones se diseña para operar a un BER de 10e-9, es decir, no más de uno en 10e9 bits (1000 millones de bits) se recibe con error. Esto puede ser obtenido aumentando la potencia del transmisor o añadiendo códigos correctores de errores. Reed-Solomon permite al sistema obtener este BER con una potencia de salida menor del transmisor. El "ahorro" de potencia dado por el código Reed-Solomon (en decibeles) es la ganancia de código. Arquitecturas para codificar y decodificar códigos Reed-SolomonLa codificación y decodificación Reed-Solomon puede ser llevada a cabo por software o hardware de propósito especial. Aritmética de Campo Finita (Galois)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. Generador PolinomialUna 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. La forma general de este polinomio es: g(x) = (x − α)(x − α^2)· · ·(x − α^(n−k)) y la palabra de código se construye utilizando: 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 “a” se conoce como un elemento primitivo del campo. Ejemplo: Generador para RS(255,249) Arquitectura del codificadorLos 2t símbolos de paridad en una palabra de código sistemático Reed-Solomon están dados por: El siguiente diagrama muestra una arquitectura para un codificador sistemático RS(255,249): Cada uno de los seis registros contiene un símbolo (8bits). Los operadores aritméticos llevan la suma o multiplicación de campo finito en un símbolo completo. Arquitectura del decodificadorLa arquitectura general para decodificar códigos Reed-Solomon se muestra en el siguiente diagrama: Donde:
La palabra recibida r(x) es la original (transmitida) c(x) más los errores: Un decodificador Reed-Solomon intenta identificar la posición y magnitud de hasta t errores (o 2t "borrados") y corregir los errores o "borrados". Cálculo del SíndromeEste es 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). Encontrando el lugar del símbolo erróneoEncontrar el lugar del símbolo erróneo implica resolver de forma simultánea ecuaciones con t incógnitas. Varios algoritmos rápidos existen para realizar lo anterior. Estos algoritmos toman ventaja de la estructura matricial especial de los códigos Reed-Solomon y reducen de gran forma el esfuerzo computacional requerido. En general dos pasos se requieren:
Implementación de Codificadores y Decodificadores Reed-SolomonImplementación HardwareExiste 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 "Sistemas sobre Chip" 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 "de por vida" un mismo circuito integrado.PONI Implementación SoftwareHasta 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. La siguiente tabla muestra un ejemplo de pruebas hechas en un Pentium de 166MHz PC: Estas tasas de datos son solamente para decodificación, para la codificación se vuelve mucho más rápido debido a que requiere menos cálculos... Véase tambiénEnlaces externos
|