Make your own free website on Tripod.com
EL SITIO DE LOS MEDIOS DE TRANSMISIÓN GUIADOS
deteccion de errores

HOME

convertidor
convertidor
deteccion de errores
conmutaciones
Deportes
Musica
Peliculas
Computadoras

Enter subhead content here

Detección de errores             


No existe ningún sistema de comunicación de datos que pueda impedir que ocurran errores durante la transmisión, aunque la mayoría de estos pueden detectarse mediante diseños apropiados que permiten saber si la información recibida es la misma que se transmitió originalmente.

Entre las técnicas para la detección de errores podemos describir las siguientes:

Técnica del eco

Es una forma simple de detección de errores usada en situaciones interactivas. Cuando una estación recibe una transmisión, la almacena y retransmite de nuevo a la estación emisora (eco), ésta compara el eco con el mensaje original y de esta forma se puede determinar si se presentó un error y corregirlo. Esta técnica tiene la desventaja de requerir al menos el doble de transmisiones, y además está la posibilidad de una "corrección" espontánea durante la retransmisión.

Técnicas de detección automática de errores

Estas técnicas consisten en la adición al dato por enviar de un marco de verificación de secuencia o FCS (frame check sequence), el cual es obtenido a partir de los datos a transmitir por medio de un algoritmo. Una vez recibido el mensaje, la estación receptora aplica el mismo algoritmo a los datos recibidos y compara el FCS obtenido de esta forma con el que se adicionó a los datos originales. Si son iguales se toma el mensaje, de lo contrario se supone un error.

Estas técnicas están basadas en dos métodos comunes:

Verificación de paridad en dos coordenadas

Cuando se transmiten datos a un dispositivo que cuente con un buffer, es posible extender la verificación de paridad simple añadiendo un bloque de verificación de carácter (Block Check Character BCC) al final del bloque de datos, el cual realizará la segunda verificación de paridad a todo el bloque.

 

En la técnica de verificación de paridad en dos coordenadas se pueden dar los siguientes casos (en rojo están los bits erroneos).

 

Verificación por redundancia cíclica (CRC)

Esta técnica es ampliamente usada debido a que es fácil de implementar en los circuitos integrados a muy gran escala (VLSI) que forman el hardware. Un mensaje puede verse como un simple número binario, el cual puede ser dividido por una cantidad que consideraremos constante, al efectuar la división (a módulo 2) se obtiene un cociente y un residuo, este último es transmitido después del mensaje y es comparado en la estación receptora con el residuo obtenido por la división de los datos recibidos y el mismo valor constante. Si son iguales los residuos se acepta el mensaje, de lo contrario se supone un error de transmisión. En el proceso de datos comercial es ampliamente usada la verificación por redundancia cíclica de 16 bits de longitud, aunque también es posible usar 32 bits lo cual puede ser más efectivo.

Código Hamming de corrección automática de errores

Este sistema inventado por Richard W. Hamming (1950) asocia bits de paridad par con combinaciones únicas de bits de datos. Este método permite detectar y corregir con seguridad hasta un bit por cada bloque de información transmitida.

A cada n bits de datos se le añaden k bits de paridad de tal forma que el carácter transmitido tiene n+k bits de longitud. Los bits se numeran de izquierda a derecha (el 1º bit es el más significativo). Todo bit cuyo número sea potencia de 2 es un bit de paridad, los restantes serán bits de datos. Los bits de dato se acomodan en sus posiciones y los bits de paridad se calculan de modo que tengan una paridad par sobre los bits cuyo número de bit formen, por ejemplo: El bit 1 (paridad) es determinado por los bits de datos: 3 (1+2=3), 5 (1+4=5), 7 (1+2+4=7), 9 (1+8=9), etc...

De esta forma cada bit está verificado por una combinación única de bits de paridad, de modo que analizando los errores de paridad se puede determinar que bit es el que ha invertido su estado. A continuación se dan algunos ejemplos que muestran cómo se pueden localizar los bits alterados:

Paridad incorrecta en los bits

El error está en el bit número

4
1 y 4
1, 2 y 4
1 y 8

4
5
7
9

En el caso que exista más de un error en el bloque de información se llegan a producir varias situaciones que pueden llevar a la "corrección" de un bit no alterado (Ej: si cambian los bits 1 y 2 llevan a la corrección del bit sano 3), entre muchas otras situaciones.

Una variante del código Hamming es adicionarle 1 bit de paridad global. De esta forma es posible tener la seguridad de detección de 2 errores, manteniendo la capacidad de corrección si se produce sólo 1 error.

Desventajas del código Hamming

La cantidad de bits de paridad empleados en la transmisión de la información le restan eficiencia al proceso. Se define la eficiencia de transmisión con la siguiente fórmula:

Suponiendo que se desea transmitir bloques de 8 bits de información, se necesitan 4 bits de paridad para ello, con lo que se tiene un total de 12 bits. La eficiencia sería:

La eficiencia de este tipo de transmisión resulta de 66.66% debida solamente al plan de codificación. Además, dependiendo del método de transmisión puede decaer todavía más.

Distancia de Hamming.

       La primera subdivisión que se efectúa entre códigos es la siguiente. 

  • códigos de bloque: la longitud de sus palabras es constante. Son los más utilizados, y para entenderlos resulta fundamental el concepto de distancia.
  • códigos sin bloque: la longitud es variable.

       La distancia de Hamming entre dos palabras es el número de bits en que difieren una de la otra. Por ejemplo: 
 

10001110

 

11100101

00111000

 

11110111

d = 5

 

d = 2

       El peso de una palabra se define como el número de 1s que tiene. Utilizando este concepto podemos decir que la distancia entre dos palabras como el peso de la suma en módulo 2 del peso de las mismas. 
 
 

10001110

 

11100101

00111000

 

11110111

10110110  => peso 5

 

00010010  => peso 2

       Dos palabras serán tanto más fáciles de distinguir cuanto mayor sea su distancia Hamming, ya que si la distancia es d será necesario que se produzcan d errores para que una palabra pase a ser la otra. De este análisis se desprende que la eficacia de un código será función de su distancia Hamming, que se define como la mínima distancia que puede encontrarse entre dos palabras que pertenezcan a ese código. En general: 

  • Un código de distancia mínima de Hamming d será capaz de detectar d-1 errores.
  • Un código de distancia mínima de Hamming d será capaz de corregir (d-1)/2 errores.
    Un código que corrija t errores y detecte d (d>t) debe tener una distancia mínima igual a dm, siendo dm = t + d +1.

Códigos de Hamming.

Son un subconjunto de los códigos de control de paridad. En ellos se disponen los dígitos de paridad de tal manera que localicen la presencia de errores dentro del mensaje. Estos códigos tienen como muy poco distancia mínima 3. 

Supongamos palabras de L dígitos. Para detectar un error en una de los L bits, o la ausencia de error, necesitaremos al menos R de esos L bits,

cumpliendo la relación: 

L = 2R - 1

de donde se deduce que el código Hamming más sencillo tendrá 2 bits de paridad y 1 de información. A los códigos que cumplen la relación anterior se le denomina código óptimo, en el sentido en que contienen el número máximo posible de bits de información, para una longitud de palabra L y una distancia mínima determinada (en nuestro caso 3). 

Las principales reglas relativas al control de paridad en los códigos de Hamming son: 

  • Dos dígitos no pueden controlar la paridad de un mismo conjunto de dígitos de información.
  • No se puede incluir en el conjunto de dígitos controlado por uno, otros dígitos de paridad.
  • Un error en un bit de información debe afectar a dos o más bits de paridad.

Veamos un ejemplo: 

            p = 3 bits de paridad: p0, p1, p2. 
           
L = 7. 
            i = 7 -3 = 4 bits de información: i0, i1, i2, i3. 

     L = i0 i1 i2 i3 p0 p1 p2. 
 

p0

p1

p2

ERROR

0

0

0

  NO ERROR 

0

0

1

p2

0

1

0

p1

0

1

1

i3

1

0

0

p0

1

0

1

i2

1

1

0

i1

1

1

1

i0

      Se obtienen las ecuaciones: 
 

0 = p0 xor i2 xor  i1 xor i0 
0 = p1
xor i3 xor  i1 xor i0
0 = p2
xor i3 xor  i2 xor i0

      de manera que si se recibe una palabra se comprueban las tres ecuaciones, y, en función de las que no se cumplen, se detectará la situación de error o la ausencia. Así por ejemplo, si no se verifican la primera y la tercera, el error estará en i2, que es el único que no interviene en la segunda pero sí en las otras dos. 

       La probabilidad de no detectar error en este código depende de como se utilice. Si se utiliza como corrector existirá la probabilidad de que existan al menos dos errores (es decir, el código sólo puede corregir uno, si hay más no son corregibles), en un canal BSC con probabilidad de error p: 

Pe (corrector) = (n2) p2 (1-p)n-2

       Si se utiliza como corrector, la probabilidad de no detección será la de que al menos haya tres errores, es decir: 

Pe (detectar) = (n3) p3 (1-p)n-3

       Sin embargo, si una palabra contiene más errores de los que es capaz de detectar un código el decodificador entrega una palabra errónea. Debido a esto se utilizan muchas veces códigos con función doble: primero detectan los errores, después tratan de corregirlos, y si no es posible solucionar todos se pide la retransmisión.