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 mucho 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.

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 donde, 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 [editar]

Hasta el momento, los mecanismos que hemos estudiado se encuadran dentro de los
métodos de detección de errores, con capacidad de detección pero no de corrección. A
continuación vamos a desarrollar los métodos de 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 bits necesarios. Por ello
normalmente los códigos correctores de error se reducen a la corrección de 1,2 ó
3 bits.

 Distancia Hamming. La distancia Hamming H entre dos secuencias binarias

S1yS2 de la misma longitud, viene definida por él número de bits en que difieren.
  Código Hamming. Código corrector de errores, desarrollado por R.W.
Hamming en 1950, y se basa en los conceptos de bits redundantes y Distancia
Hamming.

Un Hamming puede utilizarse en mensajes de caracteres de cualquier longitud, aunque

ilustraremos su utilización con caracteres ASCII de 7 bits y paridad par. Necesitamos 4
bits (24 > 7 + 4 + 1), que se situaran en las posiciones 1,2,4 y 8 (posiciones potencia de
2). Nos referimos a los bits redundantes como r1,r2,r4 y r8.

 En este apartado vamos a centrarnos en un tipo concreto de código corrector de

errores: los códigos Reed-Solomon

Códigos de correción de errores Reed-Solomon [editar]

Introducción [editar]

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 [editar]

El código Reed-Solomon es un subconjunto de los códigos BCH y son de bloques

lineales. 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=8

 2t=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=25 − 1. 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 [editar]

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 [editar]

Un error de símbolo ocurre cuando al menos un bit de un símbolo es erróneo.

Ejemplo [editar]

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 [editar]

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:

1. Si 2s + r < 2t (s errores, r "borrados") 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.

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 [editar]

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 mas 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 [editar]

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) [editar]

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 [editar]

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:

y la palabra de código se construye utilizando: 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 “a” se conoce como un elemento primitivo del campo.

Ejemplo: Generador para RS(255,249)

Arquitectura del codificador [editar]

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 [editar]

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 [editar]

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 [editar]

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:

1. 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.
2. Encontrar las raíces del polinomio anterior. Esto se hace con el algoritmo de
búsqueda de Chien.
3. 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
[editar]

Implementación Hardware [editar]

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.

Implementación Software [editar]

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.

Un bit de paridad es un dígito binario que indica si el número de bits con un valor de 1
en un conjunto de bits es par o impar. Los bits de paridad conforman el método de
detección de errores más simple.

Hay dos tipos de bits de paridad: bit de paridad par y bit de paridad impar.

 El bit de paridad par se pone a 1 si el número de unos en un conjunto de bits es

impar, haciendo de esta forma que el número total de bits (datos+paridad) sea
par.
 El bit de paridad impar se pone a 1 si el número de unos en un conjunto de bits
es par, haciendo de esta forma que el número total de bits (datos+paridad) sea
impar.

La paridad par es un caso especial del control de redundancia cíclica (CRC), donde el
bit de CRC se genera por el polinomio x+1.
Nótese que este método detecta los errores, pero no los corrige (salvo en el caso de que
la palabra transmitida sea de tamaño 1 bit).

El bit de redundancia es un bit (o conjunto de ellos) que, a veces, se introducen

deliberadamente en la transmisión o grabación de información sin ser parte de ésta, pero
sirven para detectar posibles errores.

Por ejemplo, si queremos representar cuatro símbolos {1,2,3,4} y hacemos un código

sin redundancias, se necesitan dos bits para representarlo.

 Si por algún error, obtenemos otro símbolo del alfabeto, no tenemos manera de
detectarlo.
 Si al código anterior le añadimos un bit al final, se podrán detectar algunos
errores determinados.
 Si el bit que hemos añadido lo ponemos a cero, y por un error se produce un
cambio en el último bit, se detectaría que ese símbolo recibido es un símbolo
inválido.

Por ejemplo si recibimos un 001 en vez de un 000, sabríamos que el símbolo recibido es
erróneo puesto que no existe en nuestro alfabeto.

Normalmente el valor del bit o de los bits de redundancia se pone con un valor que sea
función de alguno o algunos de los bits anteriores, de forma que ayude a identificar
errores de comunicación en otros bits. Habitualmente esta función es la suma o XOR de
todos los bits anteriores.

Los códigos de paridad se usan en Telecomunicaciones para detectar, y en algunos

casos corregir, errores en la transmisión. Para ellos se añade en origen un bit extra
llamado bit de paridad a los n bits que forman el carácter original.

Este bit de paridad se determina de forma que el número total de bits 1 a transmitir sea
par (código de paridad par) o impar (código de paridad impar).

Código de paridad par

El bit de paridad será un 0 si el número total de 1 a transmitir es par, y un 1 si el
número total de 1 es impar.
Código de paridad impar
El bit de paridad será un 1 si el número total de 1 a transmitir es par y un 0 si el
número total de 1 es impar.

Normalmente el bit de paridad se añade a la izquierda del carácter original.

Ejemplos: Tenemos el carácter original 0111001. Vemos que la trama a transmitir tiene
un número par de unos (4). Al añadir el bit de paridad obtendremos el siguiente carácter,
que es el que se transmitirá a destino:

 Si usamos paridad par, ya hay un número par de unos, por tanto se añade un 0, y
transmitiremos 00111001
 Si usamos paridad impar, como hay un número par de unos, hemos de añadir
otro 1 para conseguir un número impar, y transmitiremos 10111001
Si se envía un dato y durante la transmisión se produce un único error, el destinatario
puede detectarlo al comprobar la paridad en destino. Usando los ejemplos anteriores, y
alterando un solo bit de la trama transmitida, nos quedaría.

 Paridad par: se recibe 00110001 en vez de 00111001. Al comprobar el número

de unos nos salen 3 (impar), luego se ha producido un error.
 Paridad impar, se recibe 10110001 en vez de 10111001. Al comprobar el número
de unos nos salen 4 (par), luego se ha producido un error.

Este método, aunque resulta satisfactorio en general, sólo es útil si los errores no
cambian un número par de bits a la vez, ya que un número par de errores no afecta a la
paridad final de los datos.

Por tanto, el método de paridad puede detectar un número impar de errores de

transmisión. Siguiendo los ejemplos anteriores, y alterando dos bits en la transmisión,
tenemos:

 Paridad par: se recibe 00110101 en vez de 00111001. Al comprobar el número

de unos nos salen 4 (par), y no detecta los errores.
 Paridad impar, se recibe 10110101 en vez de 10111001. Al comprobar el número
de unos nos salen 5 (impar), y no detecta los errores.

Además de esta paridad simple, véase también los códigos de paridad de bloques para
detectar y corregir errores en un bloque de datos transmitidos