TecnicaCorrecciondeErrores

UNIVERSIDAD CENTRAL DE VENEZUELA
Facultad de Ciencias
Postgrado en Ciencias de la Computación
Lecturas de Docencia











Fundamentos de la Tecnología Inalámbrica: Técnicas de Corrección y Detección de Errores






Profesora Agregado Maria Elena Villapol









Noviembre del 2006.

1. Técnicas de Control de Errores en Redes Inalámbricas

Las técnicas de control de errores incluyenaquellas para detectar y/o corregir errores. Las aproximaciones más comunes son:

Códigos para la detección de errores, tales como Chequeo de Paridad y Chequeo Cíclico Redundante (Cyclic Redundancy Check, CRC): son capaces de detectar la presencia de errores en una secuencia de bits más no pueden corregirlos. Ellos confían en técnicas tales como la de Requerimiento de Repetición Automática yRetransmisiones para el tratamiento de tramas con errores.
Códigos para la corrección de errores, entre los que se encuentran: Códigos para la Corrección de Errores de Bloque, Código de Hamming, Códigos Cíclicos, Códigos BCH, Intercalamiento de Bloques, Códigos Convolucionales, Codificación Turbo, son usualmente usados en ambientes de comunicación inalámbricas, dada su propiedad de poder detectar y corregiralgunos errores, lo que reduce el uso de retransmisiones que pueden ocasionar mucho overhead en éste tipo de enlaces, caracterizados por tener poco ancho de banda.
Requerimiento de Repetición Automática (Automatic Repeat Request, ARQ): incluyen técnicas para la retransmisión de tramas no reconocidas después de cierto intervalo de tiempo.

1.1. Principios Generales de la Corrección y Detección deErrores

Cada bloque de m bits es codificado con un bloque de (m+r) bits denominado palabra código (codeword). El algoritmo suma r bits al bloque de datos de m bits con la finalidad de poder detectar o incluso corregir errores. La palabra código es la que se transmite.

En el receptor varias cosas pueden pasar:

Si no hay errores, la salida de decodificador es igual al código original.
Paraciertos errores, el decodificador puede detectar y corregir los mismos.
Para ciertos patrones de errores, el decodificador puede detectar el error pero no corregirlo.
Para ciertos errores el decodificador no puede detectar el error y produce una señal de salida que difiere de la original.

Adicionalmente, se puede medir la cantidad de bits en las cuales dos secuencias difieren. Esta es conocida comola distancia de Hamming, d. Así, d(v1,v2) se define como el número de bits en los cuales las siguientes secuencias, v1 y v2, difieren. La distancia mínima para una palabra código que consiste de w1,w2, …ws donde s = 2n.



Por ejemplo, si v1 = 011011 y v2 = 110001, entonces d(v1,v2) = 3

Para detectar d errores se requiere una distancia de d+1. Para corregir d errores, se requiere una distanciade 2d+1 [3].

El radio de redundancia (o solamente redundancia) es r/m. Mientras que la tasa del código es m/(m+r) y mide la cantidad adicional de ancho de banda que se necesita.

1.2. Detección de Errores

A continuación se describirá una técnica muy común para la detección de errores en sistemas de comunicación, tal como lo es el Chequeo Cíclico Redundante (CRC). Otra técnica ampliamenteconocida es el chequeo de paridad, la cual no es descrita en este documento, pero cuya descripción puede ser encontrada en [3].

1.2.1. Chequeo Cíclico Redundante (CRC)

Para un bloque de k bits, el transmisor genera una secuencia de n bits. El transmisor transmite una secuencia de k+n bits, la cual es exactamente divisible por un número. La secuencia de n bits se llama secuencia de chequeo de trama(Frame Check Sequence, FCS).

Sea T la trama de (n+k) bits, n