Códigos detectores y correctores de error
Los 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.
Estrategias
Se han diseñado dos estrategias diferentes para el tratamiento de los errores
- Códigos detectores de error: Consiste en incluir en los datos transmitidos, una cantidad de bits redundantes de forma que permita al receptor detectar que se ha producido un error, pero no qué tipo de error ni dónde, de forma que tiene que solicitar retransmisión.
- Códigos correctores de error: Consiste en la misma filosofía que el anterior, incluir información redundante pero en este caso, la suficiente como para permitirle al receptor deducir cual fue el carácter que se transmitió, por lo tanto, el receptor tiene capacidad para corregir un número limitado de errores.
Corrección de errores
La corrección de errores se puede tratar de dos formas:
- Cuando se detecta el error en un determinado fragmento de datos, el receptor solicita al emisor la retransmisión de dicho fragmento de datos.
- El receptor detecta el error, y si están utilizando información redundante suficiente para aplicar el método corrector, automáticamente aplica los mecanismos necesarios para corregir dicho error.
- Bits redundantes. Teóricamente es posible corregir cualquier fragmento de código binario automáticamente. Para ello, en puesto de los códigos detectores de errores utilizando los códigos correctores de errores, de mayor complejidad matemática y mayor número de bits redundantes necesarios. La necesidad de mayor número de bits redundantes hace que a veces la corrección de múltiples bits sea inviable e ineficiente por el elevado número de bits necesarios. Por ello normalmente los códigos correctores de error se reducen a la corrección de 1,2 o 3 bits.
- Distancia Hamming. La distancia Hamming H entre dos secuencias binarias de la misma longitud, viene definida por el número de bits en que difieren.
- Código Hamming. Es un código corrector y detector de errores, desarrollado por R.W. Hamming en 1950, y se basa en los conceptos de bits redundantes y Distancia Hamming.
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-Solomon
Propiedades de los códigos Reed-Solomon
Un 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:
N=255, k=223, s=82t=32, t=16
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.
Ejemplo
El 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ímbolo
Un error de símbolo ocurre cuando al menos un bit de un símbolo es erróneo.
Ejemplo
RS(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ón
Los 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:
- Si (s errores, r "borrados") entonces la palabra de código original transmitida puede ser siempre recuperada.
- El decodificador detectará que no puede recuperar la palabra de código original e indicará este hecho.
- El decodificador decodificará erróneamente y recuperará una palabra de código incorrecta sin indicación.
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ón
La 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-Solomon
La 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 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. 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 codificador
Los 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 decodificador
La arquitectura general para decodificar códigos Reed-Solomon se muestra en el siguiente diagrama:
Donde:
- r(x)= Palabra de código recibida
- Si = Síndromes
- L(x)= Polinomio localizador de errores
- Xi = Localización de errores
- Yi = Magnitud de errores
- c(x)= Palabra de código recuperada
- v = Número de errores
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índrome
Este 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óneo
Encontrar 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:
- Encontrar un polinomio localizador de error: Esto se puede lograr utilizando el algoritmo Berlekamp-Massey o el algoritmo de Euclides. El algoritmo de Euclides tiende a ser el más utilizado en la práctica debido a que es más fácil de implementar, sin embargo el algoritmo Berlekamp-Massey tiende a llevar a una implementación hardware y software más eficientes.
- Encontrar las raíces del polinomio anterior. Esto se hace con el algoritmo de búsqueda de Chien.
- Encontrando los valores del símbolo erróneo. Nuevamente, esto implica resolver ecuaciones con t incógnitas. Un algoritmo usado ampliamente es el algoritmo de Forney.
Implementación de Codificadores y Decodificadores Reed-Solomon
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 "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 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. 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...