REGRESA AL MENU PRINCIPAL

METODOS PARA DETECCION DE ERRORES EN TRANSMICION DE DATOS CLUB DEPORTIVO MANCHESTER UNITED

Make your own free website on Tripod.com

¡¡¡METODOS PARA DETECCION DE ERRORES EN TRANSMICION DE DATOS!!!






                   

                     

 ELÈCTRONICA Y AUTOMATIZACION

FIBRA OPTICA

COAXIAL

CABLE UTP

OTRO SITIO

 

   

 

 

El código Hamming

Es un código corrector de errores, voy a intentar explicarlo siguiendo el ejemplo del libro. Consideraciones:

 

-  pretendemos transmitir los bits de datos: D1, D2, D3 y D4

- entre estos bis de datos se intercalan bits de paridad par P1, P2 y P3

- ¿dónde los intercalamos?:  para poder entenderlo, os propongo que cojáis una hoja en blanco y tengáis a la vista la fig. 6.4 que vamos a intentar reconstruir desde el principio:

 

- construimos la columna de “Nº de orden” que es simplemente poner en binario una numeración desde 001 hasta 111 (hay que saber el código binario natural)

 

- si el número de orden es potencia exacta de dos (ósea 1, 2, 4, ...) entonces en esa posición pondremos un bit de paridad (es decir P1 en la posición Nº 1: 001;  P2 en la posición Nº 2: 010 y P3 en la posición Nº 4: 100)

 

- en las posiciones vacías se intercalan los bits de datos que realmente son la información que queremos transmitir (D1, D2, D3 y D4). En este momento ya tendremos hechas las dos primeras columnas de la tabla.

 

¿Qué hemos hecho hasta el momento?: hemos construido la cadena de bits que vamos a enviar y en que orden se enviaran: P1, P2, D1, P3, D2, D3, D4. (hago notar que el código Hamming consiste en añadir varios bits de paridad intercalados entre los bits de datos)

 

Nos falta la tercera y  última columna: “cadenas de bits asociados”: (las otras columnas son un ejemplo, un caso concreto, que veremos luego):

 

- Observar: el número en binario correspondiente al número de orden donde hemos puesto los bits de paridad P1,P2 y P3 sólo tiene un uno (001, 010, 100) (por eso son potencias exactas de dos). Pues bien las cadenas son aquellas posiciones que tienen un uno en el mismo lugar que este bit. Por ejemplo de las tres cadenas, la de más a la derecha (la correspondiente a P1: 001) coge las posiciones: 001, 011, 101 y 111, porque son las que tienen un 1 en el primer bit de la derecha del número binario. Las otras dos cadenas siguen la misma lógica.

 

 Veamos los ejemplos que plantea el libro:

 

Columna “Transmisión”, consiste en un ejemplo de qué señales se transmiten si deseamos enviar los bits de datos D1=1, D2=1 , D3=0 y D4=1, (escribimos estos bits en la posición correspondiente de la columna, nos quedaran vacías las posiciones de los bits de paridad, que vamos a calcular seguidamente):

 

P1: hay que poner 0 o 1, para que la paridad de los bits de la primera cadena (la de la derecha que forma D1, D2 y D4) sea par, como tenemos D1=1, D2=1 y D4=1 hará falta un 1 para tener paridad par, luego P1 lo pondremos a 1. El resto de paridades P2 y P3 se calculan con la misma lógica.

 

Columna: “Recepción”. Consiste en un ejemplo que simula que hemos recibido los bits indicados en la columna y tenemos que comprobar si el dato es correcto o ha habido un error en la transmisión (si miramos los bits enviados y los recibidos veremos que hay un error en bit 6 (D3), hemos enviado un 0 y hemos recibido un 1, por un error en los cables de transmisión.  Pero se supone que no sabemos lo que se ha enviado, solo lo que hemos recibido y vamos a realizar el proceso para comprobar si es o no correcta:

 

- columna “detección”, copiamos las tres cadenas de bits asociados, pero en vez de poner “circulitos” ponemos los bits reales, respetando la posición de la cadena, ( por ejemplo la cadena de mas a la derecha que comprende P1, D1,D2 y D4, corresponde a la columna de “detección” de mas a la derecha (1,1,1,1). Igualmente las otras dos columnas.

 

- finalmente comprobamos la paridad des tres columnas (“posición de error”). La de la derecha tiene 1,1,1,1 como es par es correcta, ponemos un 0. La del medio tiene: 0,1,1,1  como es impar es incorrecta, ponemos un 1. La de la izquierda tiene 0,1,1,1 también es impar, incorrecta ponemos un 1.

 

 - El numero en binario que aparece en “posición de error” en  nuestro caso 110 que es un 6 significa que el bit sexto de la transmisión ha habido un error. El bis sexto corresponde a D3, Si ha llegado un 1 y es erróneo es que valía 0.

 

 

 

 

 

 

 

 

 

 

GRACIAS POR SU VISITA

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ódigos de CRC

  • Un método más usado es el código polinomial (también llamado el cyclic redundancy code, o CRC). Se trata los strings de bits como polinomios con coeficientes de solamente 0 y 1. Un mensaje de k bits con un grado de k-1 corresponde a

bit0xk-1 + ...+ bitnxk-1-n + ...+ bitk-1x0

La aritmética con estos polinomios es módulo 2 sin llevar, es decir la adición y la sustracción son equivalentes a XOR. La división usa XOR en ves de sustracción y A se divide en B si el número de bits en B es mayor de o igual a el número en A.

  • El remitente y el receptor usan el mismo polinomio de generación, G(x), con bits alto y bajo de 1.
  • Para calcular el checksum de r bits, que también es el grado de G(x),
    • Añade r bits de 0 a M(x), el mensaje, produciendo xrM(x).
    • Divide xrM(x) por G(x), produciendo un resto.
    • Transmite T(x) = xrM(x) - resto. T(x) es divisible por G(x). Sus últimos r bits son el checksum.
  • Si hay errores en la transmisión recibiremos T(x)+E(x) en vez de T(x). El receptor divide T(x)+E(x) por G(x). Ya que el resto debido a T(x) es 0, el resto obtenido es completamente debido a E(x). Si E(x) tiene G(x) como un factor, el resto será 0 y no detectaremos el error, de otro modo, sí.
  • Si hay un error de un bit, E(x) = xi. Si G(x) tiene más de un término, no puede dividir E(x). Entonces podemos detectar todos los errores de un bit.
  • Con dos errores tendremos E(x) = xi + xj = xj(xi-j+1). Podemos usar un G(x) que no divide xk+1 para cualquier k hasta el valor máximo de i-j (que es la longitud del marco). Por ejemplo, x15+x14+1 no divide xk+1 para k<32768.
  • Si x+1 es un factor de G(x), podemos detectar todos los errores que consisten en un número impar de bits invertidos. Prueba por contradicción: Asume que E(x) tiene un número impar de términos y es divisible por x+1. Entonces E(x) = (x+1)Q(x) por algún Q(x). E(1) = (1+1)Q(1) = (0)Q(1) = 0. Pero E(1) debe ser 1 porque consiste en la suma de un número impar de 1's.
  • Podemos detectar todos los errores en grupo con longitudes menos de o igual a r. Si el grupo tiene una longitud de k, lo podemos escribir como xi(xk-1+...+1) (i ubica el grupo en el marco). Si G(x) contiene un término de x0, xi no puede ser un factor y G(x) no puede ser igual a xk-1+...+1 (el grado k-1 es menos de r). Si el grupo tiene una longitud de r+1, la probabilidad que el grupo es G(x) es la probabilidad que los r-1 bits intermedios del grupo son iguales (por definición el primer y el último bits del grupo son 1), que es (1/2)r-1.
  • Para los grupos con longitudes mayor de r+1, la probabilidad es (1/2)r.
  • Estándares internacionales:
    • CRC-12 = x12 + x11 + x3 + x2 + x + 1
    • CRC-16 = x16 + x15 + x2 + 1
    • CRC-CCITT = x16 + x12 + x5 + 1

Los dos últimos detectan todos los errores de uno y dos bits, los errores con un número impar de bits invertidos, los grupos de errores con longitudes menos de o igual a 16, 99,997% con longitudes de 17, y 99,998% con longitudes mayor o igual a 18.