Ingenieria electronica

Fundamentos de la Informática

Códigos detectores y correctores de error

1

8
1.- INTRODUCCIÓN

Códigos detectores y correctores de error

Estudiada la fiabilidad de los canales de transmisión, vamos a centrarnos en este tema en la posibilidad de transmitir mensajes confiables por canales no confiables. Una conclusión importante del tema anterior es que existe la posibilidad de que elmensaje recibido no sea el transmitido. Ningún canal real está libre de error , por lo que por muy pequeña que sea la probabilidad de éste en los canales actuales: del orden de 10-6, 10-8 e inferiores, su existencia impone la necesidad de mecanismos ajenos al medio de transmisión que mejoren la calidad de ésta. El mecanismo más inmediato es la simple repetición de cada símbolo transmitido unnúmero n de veces. Si los n símbolos recibidos son iguales, se supondrá que en ninguna de las transmisiones ha existido error y, por lo tanto, el centro receptor identificará como símbolo transmitido el n veces repetido. Si los n símbolos recibidos no son todos iguales, implicará error en alguna de las transmisiones y se identificará como símbolo transmitido más probable al que aparezca repetido másveces en la recepción. Es fácil observar como éste simple mecanismo mejora la fiabilidad de la transmisión. Veámoslo con un ejemplo: Ej.1.- Consideremos un canal BSC con una probabilidad de error p de 0.01, es decir, el 99% de los símbolos binarios transmitidos es recibido correctamente. Con objeto de aumentar la fiabilidad del canal repetimos el envío de cada dígito binario 3 veces. El proceso serepresenta en el siguiente esquema de emisión-transmisión de un dígito binario: Centro Emisor Dígito a enviar Se repite 3 veces Transmisión Centro Receptor Posibles secuencias Dígito enviado recibidas 000 001 010 011 100 101 110 111 0 1

0 1

000 111

Fundamentos de la Informática

Códigos detectores y correctores de error

2

La probabilidad de que no exista error en la transmisiónes: (1 - p) 3 = ( p ) 3. La probabilidad de un solo error es: 3 p p 2. La probabilidad de 2 errores es: 3 p2 p . Y la probabilidad de que los tres símbolos binarios recibidos sean erróneos es: p3. Aplicando la regla de decisión indicada se tiene que la probabilidad de interpretar el mensaje erróneamente es igual a la suma de las probabilidades de que varíen dos o tres símbolos binarios durante latransmisión, o sea: p3 + 3 p2 p ≈ 3*10 -4. La probabilidad de error ha pasado de 10 -2 si no existe repetición en la transmisión a 3*10 -4 si repetimos 3 veces cada símbolo emitido. Vista la mejora de la fiabilidad de la transmisión, es fácil de inducir que la probabilidad de error disminuirá con el número de repeticiones, pero a costa de incrementar el tiempo de la transmisión, por lo que elprocedimiento repetitivo descrito plantea un compromiso entre la velocidad de los mensajes y su fiabilidad. Por ejemplo, en el caso anterior se ha disminuido el porcentaje de error pero a costa de pasar de la transmisión de un mensaje por dígito binario a la de uno por cada tres dígitos binarios. Este método de corrección de errores aunque efectivo, no es el más eficaz que se puede utilizar; acontinuación vamos a estudiar métodos más sofisticados que logran una mayor velocidad en la transmisión de los mensajes mediante una adecuada codificación de estos. En los apartados siguientes hablaremos de la transmisión de palabras de código, para su mejor comprensión, y evitar así cualquier error, es conveniente señalar que en realidad los canales utilizados son binarios, por lo que la transmisión deuna palabra de código supone la transmisión individual de cada uno de los n caracteres binarios que la componen. Dicho de otra forma, el proceso de transmisión de una palabra de código por un canal binario, hay que verlo como la extensión de orden n (n=longitud de la palabra de código) del canal binario.

2.- CÓDIGOS DETECTORES DE ERROR Vamos a estudiar una serie de códigos cuya principal...